Educational Codeforces Round 134 (Rated for Div. 2)

Educational Codeforces Round 134 (Rated for Div. 2) A - E

A

==考察知识点：==找规律，重复数字过滤

#include 

std::mapmp;
int  t;
char temp;

int main(){
   std::ios::sync_with_stdio(false);
   std::cin >> t;
   while (t--)
   {
      mp.clear();
      for(int i = 0 ;  i < 4;i++){
        std::cin >> temp;
        mp[temp]++;
      }
      if(mp.size()==1){
        std::cout << 0 << std::endl;
      }
      else if(mp.size()==2){
        std::cout << 1 << std::endl;
      }
      else if(mp.size()==3){
        std::cout << 2 << std::endl;
      }
      else{
        std::cout << 3 << std::endl;
      }
      
   }
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

B

考察点：分类讨论（这个地方一定要把所有情况考虑清楚，最好手动画画图，左上，右下，上下，左右， 四种情况不行），画图

#include 
using namespace std;

int T;
int n, m, sx, sy, d;

bool check(int x, int y, int dep)
{

    int y1 = max(y - dep, 1);
    int x2 = max(x - dep, 1);
    int x3 = min(x + dep, n);
    int y4 = min(y + dep, m);
    // 1,
    if ((y1 == 1 && x2 == 1) || (x3 == n && y4 == m)) // 左上和右下
        return false;
    // 2,
    if (x3 == n && x2 == 1) //上下
        return false;
    if (y4 == m && y1 == 1) // 左右
        return false;

    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--)
    {
        cin >> n >> m >> sx >> sy >> d;
        // in

        if (check(sx, sy, d))
        {
            cout << (n + m - 2) << endl;
        }
        else
        {
            cout << -1 << endl;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

C

考察点：二分和贪心

主要是想到怎么贪心的问题，最小最好取与他最接近的值，最大最好取大于他并且距离他最远距离的值，同时在判断最大时，我们要考虑，最大值是不是能取，能取一次还是多少次，如果说仅能取一次或者最大值相同存在，我们要把右边界左移，目的是为了防止在下一步检测中，用不了或者不够用。二分就是找第一个比他大的元素。

#include 
using namespace std;
int t;
const int maxn = 2e5 + 10;
int dx[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin >> t;
    while (t--)
    {
        int n, temp;
        cin >> n;
        vector arr, brr;
        memset(dx, 0, sizeof dx);
        for (int i = 0; i < n; i++)
        {
            cin >> temp;
            arr.push_back(temp);
        }

        for (int i = 0; i < n; i++)
        {
            cin >> temp;
            brr.push_back(temp);
        }
      
        int index, index1, index2;
        index2 = n - 1;
        for (int i = 0; i < n; i++)
        {
            index = lower_bound(brr.begin(), brr.end(), arr[i]) - brr.begin();
            temp = brr[index] - arr[i]; // min
            cout << temp << " \n"[i == n - 1];
            // final
            index1 = lower_bound(brr.begin(), brr.end(), arr[n - i - 1]) - brr.begin();
            
            //cout << i <<" "<< index1 << " " << index2 << endl;
            if (n-i-1 == index1) // 注意这里是反向求
            { 
                dx[n - i - 1] = brr[index2] - arr[n - i - 1];
                index2 = index1 - 1; //如果说此时下标和bi匹配的下标相等，那么我们就让右边界左移
            } // 去除我们上面所说的两种因素，有一个或者存在重复
            else
            {
                dx[n - i - 1] = brr[index2] - arr[n - i - 1];
            }
        }
        for (int i = 0; i < n; i++)
        {
            cout << dx[i] << " \n"[i == n - 1];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

D

考察点：枚举，贪心，累计贡献求解，主要是能想到怎么贪心，其实根据异或条件，要使其最大，必须1和0成对出现，那么我们可以看看枚举到某一位时候，这时候1和0数量是否相同，如果相同那么累计贡献到temp, 反之，我们对当前此位的贡献清零，(因为不论是0多于1，还是1多于0，都会使得 最后该位为0) 这个只需要再异或一次即可实现。

#include 
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        vector a(n), b(n);
        for (int i = 0; i < n; i++)
            cin >> a[i];
        for (int i = 0; i < n; i++)
            cin >> b[i];
        int temp = 0;
        for (int j = 30; j >= 0; j--)
        { //从二进制高位到低位枚举
            temp |= (1 << j);
            map mp;
            for (int i = 0; i < n; i++)
            {
                mp[a[i] & temp]++;  // a 1000...
                                    // b1000...
                mp[~b[i] & temp]--; // 差分的思想，一增一减，判断是否相同。
            }
            bool flag = true;
            for (auto x : a)
            {
                if (mp[x & temp] != 0)
                {
                    //如果贡献没有抵消掉
                    flag = false;
                    break;
                }
            }
            if (!flag)
                temp ^= (1 << j); // 取消该位贡献。
        }
        cout << temp << endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

E

知识点：可持久化kmp优化, 动态规划

题意其实就是说当你拼接t到s后，求 s + t() 位对应的next（） 数组，知道这个后，就可以有很多种解法（e.g. AC自动机）

代码中采用dp的思路，大概就是用一个二维dp 和一个标记数组 sz() 记录 next()的大小，当求解的时候，只需要不断做向前回退动作（也有同学把这个叫做爬树 ，因为每一个nex[i]和i 的关系可以看成一个树结构)， 回退过程中把搜集的结果记录到dp中，最后把当前位记录到sz[i],方便该串的下一位使用。

#include 
using namespace std;
const int maxn = 1e6 + 10;
int dp[maxn][26];//a[前缀][后接字符] 
int sz[maxn]; // sz[i] <= i，最大前缀长度
 
string s; 
int calc(int i)
{
   int qwq = s[i] - 'a'; // 当前aci值
   fill(dp[i],dp[i]+qwq,0);
   for(int j=0; j <26;j++){
    dp[i][j] = (i && j!=qwq) ? dp[sz[i-1]][j]:(i+(j==qwq));
   }
   return sz[i]= (i ? dp[sz[i-1]][qwq]:0); // sz 的作用相当于next数组
}
int main()
{
   int T;
    cin >> s;
    int ls = s.length();
    for(int i = 0; i > T;
    while(T--){
        string temp; cin >> temp;
        int lt = temp.size();
        s += temp; //
        //cout << s << endl;
        for(int i = ls; i < ls+lt;i++){
            cout << calc(i) <<" \n"[i==ls+lt-1];
        }
        for(int i = 0; i < lt;i++) s.pop_back(); // 还原一下 s 
    }    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35