A count takahashi
问题:
思路：字符串比较
代码：
#include <bits/stdc++.h>using namespace std;int main() {int n;cin >> n;int ans = 0;for(int i = 1; i <= n; i ++ ) {string s;cin >> s;if(s[0] == 'T') ans ++;}cout << ans;return 0;
}B couples
问题：
思路：找出所有a[i - 1]与a[i + 1]相等的pair
代码：
#include <bits/stdc++.h>using namespace std;int main() {int n;cin >> n;vector<int> a(2 * n + 1);for(int i = 1; i <= 2 * n; i ++ ) cin >> a[i];int pre = a[1];int ans = 0;for(int i = 2; i <= 2 * n - 1; i ++ ) {if(a[i + 1] == pre) ans ++;pre = a[i];}cout << ans;return 0;
}C tile distance2
问题：
思路：
注意到每次竖直方向上走一个可以在水平方向上多增加一个偏移量，因此只要先解决竖直方向，然后可以得到一个水平方向的最大范围，只要水平坐标在这个范围内就不用计算水平方向上的花费，反之计算差值除2即可。为了简化计算，可以把所有坐标在水平方向上偏移到砖块的左边部分。
代码：
#include <bits/stdc++.h>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);long long x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;long long yy = abs(y1 - y2);long long t = min(x1, x2);x1 = max(x1, x2);x2 = t;if((y1 + x1) & 1) x1 --;if((y2 + x2) & 1) x2 --;//long long tmp = x1;x1 -= yy;if(x1 <= x2) cout << yy;else cout << yy + abs(x1 - x2) / 2;return 0;
}D - Avoid K Palindrome
问题：
思路：
注意到k很小，话不多说，状态压缩。A为1，B为0
很显然只有一维的状态无法构造状态转移方程。再加一维索引dp[i][j]表示以下标i开头的字符串且状态为j的所有good string 的数量
则有dp[i][j] += dp[i - 1][k]
j与k之间又有什么联系呢，让他们错开一位上下摆放，就可以发现除了第一位和最后一位，其他位都是相同的。这时候让j减去最右边的数，并且整体右移一位！！！很重要，就因为这里，我调了一个小时代码。然后再加上str[i - 1]对应的数。
代码：
#include <bits/stdc++.h>using namespace std;const int mod = 998244353;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, k;cin >> n >> k;vector<char> str(n + 1);for(int i = 1; i <= n; i ++ ) cin >> str[i];vector<vector<int>> dp((n + 1), vector<int>(1 << k));for(int j = 0; j <= (1 << k) - 1; j ++ ) {bool flag = true;vector<char> s(k);for(int i = 0; i < k; i ++ ) {if(j >> i & 1) s[i] = 'A';else s[i] = 'B';if(str[i + 1] != '?' && str[i + 1] != s[i]) flag = false;}if(flag) {reverse(s.begin(), s.end());int num = 0;for(int i = 0; i < k; i ++ ) {if(s[i] == 'A') num += (1 << i) * 1;}if(num != j) dp[1][j] = 1;}}for(int i = 2; i <= n - k + 1; i ++ ) {for(int j = 0; j <= (1 << k) - 1; j ++ ) {bool flag = true;vector<char> s(k);for(int u = 0; u < k; u ++ ) {if(j >> u & 1) s[u] = 'A';else s[u] = 'B';if(str[i + u] != '?' && str[i + u] != s[u]) flag = false;}if(flag) {reverse(s.begin(), s.end());int num = 0;for(int u = 0; u < k; u ++ ) {if(s[u] == 'A') num += 1 << u;}if(num != j) {int tmp = j;if(s[0] == 'A') tmp -= 1 << k - 1;tmp <<= 1;//if(j == 14) cout << tmp << " ";if(str[i - 1] != 'A') (dp[i][j] += dp[i - 1][tmp]) %= mod;if(str[i - 1] != 'B') {tmp ++;//if(j == 14 && i == 2) for(auto t: s) cout << t;//if(dp[i - 1][tmp] && i == 2) cout <<j;(dp[i][j] += dp[i - 1][tmp]) %= mod;}}}}}int ans = 0;for(int i = 0; i <= (1 << k) - 1; i ++ ) (ans += dp[n - k + 1][i]) %= mod;cout << ans;return 0;
}E
F
G
