Codeforces CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!) A-D 题解

A. Two 0-1 Sequences

　大致翻译：

两个长度为n和m的二进制序列a和b（题目保证n >= m）

两个操作：

op1: 改变a(2) 为min(a(1), a(2)),并且移除a（1）

op2: 改变a(2) 为max(a(1), a(2)),并且移除a（1）

每次操作后，原先的a(i)变成a(i + 1), 长度减少1，即前移。

　　a二进制序列能否通过这两个操作变成b二进制序列？

解题思路：刚开始想的是判断a2后缀跟a1后缀是否相同，再判断，a1前面有没有1和0（因为有1和0，就表示op1和op2可以随意完成）。写的时候又陆陆续续发现需要几个特判，想a1长度为1等。

于是就debug，慢慢发现只要前面有a2的第一个数字，并且后缀相同就可以对了。最终写出来了。

不过我写的查找是自己造轮子，我发现大佬就是用stl中的count()来写的，就拿过来改进了改进自己的code

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stdio.h>
#include <algorithm>
using namespace std;
 
#define rep(i,x,n) for(int i = x; i <= n; i++)
 
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 10021;
 
void solve() {
    int n, m;
    cin>>n>>m;
    string a, b;
    cin>>a>>b;
    if(a.substr(n-m+1) == b.substr(1) && count(a.begin(), a.begin() +n - m + 1, b[0])) {
        puts("YES");
    } else puts("NO");
}
void test();
int main()
{
    int n;
    cin>>n;
    while(n--) solve();
 
    return 0;
}

B. Luke is a Foodie

　　大致翻译：

对于a数组中的每一个元素，满足 |v−ai|≤x， （x是固定的值，由题目给出， v是可以变化调动的值）

问最少需要调动几次v，才能使得a数组中所有元素满足|v−ai|≤x

解题思路：

用数组的话存不下1e9+21的int型，而且题目是要找改了几次v。由|v- ai| <= x这个可以发现，区间差的最大值小于二倍的x范围内，v就不会改。因此发现存max，min，每次相减，判断是否满足在范围内，满足不改，不满足将max，min赋值为k(读入值）

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stdio.h>
#include <algorithm>
using namespace std;
 
#define rep(i,x,n) for(int i = x; i <= n; i++)
 
typedef long long LL;
typedef pair<int,int> PII;
 
//const LL N = 1e9+21;
//LL arr[N];
void test();
int main()
{
    //test();
    LL t;
    cin>>t;
    while(t--) {
        LL n,x;
        scanf("%lld %lld", &n, &x);
        LL cnt = 0;
        LL ma, mi;
        scanf("%d", &ma);
        mi = ma;
        rep(i,2,n) {
            LL k;
            scanf("%lld", &k);
            if(mi > k) mi = k;
            if(ma < k) ma = k;
            if(abs(ma - mi) <= 2*x) {;}
            else {
                cnt++;
                ma = k;
                mi = k;
            }
        }
        printf("%lld/n",cnt);
    }
 
    return 0;
}
 

C. Virus

　　大致翻译：

一个圆圈内有n个房子（编号为：1、 2、 3 …… n 、 1），最初，其中的m个房子被感染了，每天被感染的房子会感染其相邻的房子（该房子未被感染或未被保护）.Cirno每天可以选择一个房子保护，使他永久免疫。问Cirno在最合理的操作下，使房子感染数量最少， 输出最终房屋感染的数量。

解题思路：n跟m较大，即开n数组会溢出，那么就先从m下手。由于是形成一个 ⚪ ，第几个第几个房子就不是那么重要，谁都可以从第一个开始。想一想，要想求最小感染房子，那反过来就是最大未感染房子（正难反易）。最大未感染房子个数，这个… 。 由于每一天房子都会有被感染的可能，怎么就最大未感染房子个数( •̀ ω •́ )y，当然是从两个感染房子间隔最大的先开始咯，从两个感染房子间隔最大的先开始，堵住一个后，第二天感染，未堵住的会向内(当然还有外）感染，然后堵住那个未堵住的房子，一个间隔用两天。通过递增减去4倍的i，可以得到到它时，还有几个未被感染。

里面有一些细节，例如怎么得到第一个跟最后一个的间隔，怎么让间隔由大到小去计算。

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stdio.h>
#include <algorithm>
using namespace std;

#define rep(i,x,n) for(int i = x; i <= n; i++)

typedef long long LL;
typedef pair<int,int> PII;

const int N = 100021;
int arr[N];
int diff[N];
void test();
int main()
{
    test();
    int t;
    scanf("%d", &t);
    while(t--) {
        int n,m;
        scanf("%d %d", &n, &m);
        rep(i,1,m) {
            scanf("%d", &arr[i]);
        }
        sort(arr+1, arr+m+1);
        diff[1] = arr[1] - 1 + n - arr[m];
        rep(i,2,m) diff[i] = arr[i] - arr[i-1] - 1;
        sort(diff+1, diff+m+1, greater<int>());
        int ans = 0;
        rep(i,1,m) {
            diff[i] -= 4*(i-1); // 每次两天，一前一后，形成永久隔离,那么里面的自然而然就是不会被感染的了
            if(diff[i]) {
                n -= (diff[i] == 1?1:(diff[i]-1));
            }
            
        }
        cout<<n<<endl;
    }


    return 0;
}

void test() {
    #define mytest
    #ifdef mytest
    freopen("ANSWER.txt", "w",stdout);
    #endif
}

D. Magical Array

　　大致翻译：

定义一个特殊行，执行操作2，其它行执行操作1（执行次数都至少有一次）

给出这些行，让你输出那个是特殊行，以及特殊行操作2的次数。

解题思路：前缀和和差分，思路简单。

学到了 min_element() max_element()

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stdio.h>
#include <algorithm>
#include <cstdlib>
#include <memory.h>
using namespace std;

#define rep(i,x,n) for(int i = x; i <= n; i++)

typedef long long LL;
typedef pair<int,int> PII;

const int N = 100021;
LL arr[N];
void test();
int main()
{
    //test();
    int t;
    cin>>t;
    while(t--) {
        int n, m;
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; ++i) {
            LL pre = 0;
            for(int j = 1; j <= m; ++j) {
                LL x;
                scanf("%lld", &x);
                pre += x;
                arr[i] += pre;
            }
        }
        LL mx = *max_element(arr+0, arr+n);
        LL mi = *min_element(arr+0, arr+n);
        cout<< min_element(arr+0, arr+n) - arr + 1<<" "
            <<mx - mi<<endl;
            memset(arr, 0, sizeof(arr));
    }
   

    return 0;
}

void test() {
    #define mytest
    #ifdef mytest
    freopen("ANSWER.txt", "w",stdout);
    #endif
}

总结：学了几个stl

count() —  返回个数 max_element()  min_element()  —  返回迭代器或地址（数组）。

第一次做codeforces，写的时候太着急了，有些题没理解透彻或者复杂化了，A题用时较长。

加油！！！