AtCoder Beginner Contest 359

https://atcoder.jp/contests/abc359/tasks

A - Count Takahashi

void solve() {
	int n;
	cin >> n;

	int ans = 0;
	while (n --){
		string s;
		cin >> s;
		if (s == "Takahashi"){
			ans ++;
		}
	}

	cout << ans << endl;
}

B - Couples
void solve() {
int n;
cin >> n;

	vector<int> a(2 * n);
	for (auto& x : a){
		cin >> x;
	}

	int m = 2 * n;
	int ans = 0;
	for (int i = 0; i < m - 2; ++i){
		if (a[i] == a[i + 2]){
			ans ++;
		}
	}

	cout << ans << '\n';
}

C - Tile Distance 2

题意：给定一个平面，平面内砖块(2 * 1)按一定规则排列，其中x + y是偶数时，代表砖块的左半部分。每次跨越砖块的代价是1， 给定两个2维坐标，问最少的代价。

思路：将x的坐标在砖块内向移动方向靠近，然后求出x和y方向的移动距离。然后x方向专门移动的距离要被y的距离抵消掉一部分，最后分情况讨论x和y方向的移动距离的大小关系即可。

总结：题目有点绕，赛时没注意到坐标为偶数在左边这个条件，硬是根据奇偶性相同来写了很多行代码。其次关于x砖块内移动坐标没有处理好，写的很乱。 算是个小思维题吧，没想清楚。

void solve() { 
	long long x1, x2, y1, y2;
	cin >> x1 >> y1 >> x2 >> y2;

	if (x1 < x2){
		if ((x1 + y1) % 2 == 0){
			x1 ++;
		}
		if (x1 != x2 && ((x2 + y2) & 1)){
			x2 --;
		}
	}
	else if (x1 > x2){
		if ((x1 + y1) & 1){
			x1 --;
		}
		if (x1 != x2 && ((x2 + y2) % 2 == 0)){
			x2 ++;
		}
	}

	long long dis_y = abs(y1 - y2);
	long long dis_x = abs(x1 - x2);

	if (dis_y >= dis_x){
		cout << dis_y << '\n';
	}
	else{
		cout << dis_y + ((dis_x - dis_y) + 1) / 2 << '\n';
	}

}

D - Avoid K Palindrome

题意：给定长度为n的字符串和k，字符串包含'A', 'B', 或'?'。 可以将'?'变为a和b，假设有q个?，则一共有1 << q种字符串。 在字符串中，任意长度为k的子串不是回文串，则该串ok。问所有串中有多少个ok串(k <= 10)。

思路：状压dp，A和B分别作为二进制中的0和1。先预处理前k位，看哪些掩码在s的前k为中符合条件。然后依此从k + 1到第n位开始遍历字符，找到所有合法的转移前的状态，并判断转移后的状态在s中是否合法，递推更新状态计数即可，最后统计数量。

总结：这种题目应该是第二次见，上次做到类似的题目是蓝桥杯的一个统计题，不过那个题目不给出一个模板，而是问所有可能的组合数中的合法元素数量，相较于这个题来说就是少了一些转移条件，不过那个字符串长度有1e5，这个才1000。很经典的题，感谢出题人。

void solve() { 
    int n, k;
    cin >> n >> k;

    string s;
    cin >> s;

    vector<vector<MInt>> dp(n, vector<MInt>(1 << k));
    for (int i = 0; i < (1 << k); ++i){
        if (valid(i, k)){
            bool ok = true;
            for (int j = 0; j < k; ++j){
                if ((s[j] - 'A') != ((i >> j) & 1) && s[j] != '?'){
                    ok = false;
                    break;
                }
            }
            if (ok){
                dp[k - 1][i] = 1;
            }
        }
    }

    for (int i = k; i < n; ++i){
        for (int j = 0; j < (1 << k); ++j){
            if (valid(j, k)){
                if (s[i] == 'A' || s[i] == '?'){
                    if (valid(j >> 1, k)){
                        dp[i][j >> 1] += dp[i - 1][j];
                    }
                }
                if (s[i] == 'B' || s[i] == '?'){
                    if (valid((j >> 1) | (1 << (k - 1)), k)){
                        dp[i][((j >> 1) | (1 << (k - 1)))] += dp[i - 1][j];
                    }
                }
            }
        }
    }

    MInt ans = 0;
    for (int i = 0; i < (1 << k); ++i){
        if (valid(i, k)){
            ans += dp[n - 1][i];
        }
    }

    cout << ans << '\n';
}

有模板写题就是好用，只要维护固定的几个函数即可。
模板放在了下面的仓库，如果使用，请点进去点个star。
https://github.com/yxc-s/programming-template/tree/master
该仓库是一个新仓库，旨在打造一个通用的C++算法编程竞赛模板，包含数据结构，数论等各种实用的算法编程模板。如果您使用的语言不是C++，也可以将对应的代码实现翻译成其他语言来使用。