A
题意：罗里吧嗦，什么开始时候有a和b两种人，a这种人每过一秒会把右边如果是b种人就会把他变成a，
不就是求A后面的P最长连续有几个？
int n;
char s[200005];
void test_case() {
scanf("%d%s", &n, s + 1);
int cnt = 0, ans = 0;
int b = 1;
while(b <= n && s[b] == ‘P‘)
++b;
for(int i = b; i <= n; ++i) {
if(s[i] == ‘P‘)
++cnt;
else {
ans = max(ans, cnt);
cnt = 0;
}
}
ans = max(ans, cnt);
printf("%d\n", ans);
}
题意：每个属性只有3种值。定义三张牌是一个SET，当他们每个位置要么全等要么两两不同。
题解：枚举两张牌，可以确定第三张牌，放到
unordered_map里面查找
#include <bits/stdc++.h>
#define MIN(a,b) ((((a)<(b)?(a):(b))))
#define MAX(a,b) ((((a)>(b)?(a):(b))))
#define ABS(a) ((((a)>0?(a):-(a))))
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef vector<LL> VL;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
int main(void) {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int n,m;
cin>>n>>m;
unordered_map<string,int> qwq;
qwq.clear();
string s[n+1];
for(int i=0;i<n;++i){
cin>>s[i];
qwq[s[i]]=i+1;
}
int ans=0;
for(int i=0;i<n-2;++i)
for(int j=i+1;j<n-1;++j){
string ss;
for(int k=0;k<m;++k){
if (s[i][k]==s[j][k]) ss+=s[i][k];
else if (s[i][k]!=‘S‘&&s[j][k]!=‘S‘) ss+=‘S‘;
else if (s[i][k]!=‘T‘&&s[j][k]!=‘T‘) ss+=‘T‘;
else if (s[i][k]!=‘E‘&&s[j][k]!=‘E‘) ss+=‘E‘;
}
if (qwq[ss]>j) ++ans;
}
cout<<ans<<endl;
return 0;
}
C
心模拟了半天，最后放弃了
题意
给你一串从1−n 1-n1−n的序列，其中部分未知（表示为0），补全序列使得相邻数值奇偶性相反的数量最少
相邻数值的奇偶性相反：两个相邻的两个数值，其中一个为奇数另外一个为偶数
分析
一开始用了贪心，结果卡在第十二个样例，然后改成dp
定义dp数组如下
int dp[120][60][2];
dp[i][j][0/1] 表示第i+1个位置放了偶/奇数，且到第i+1处总共放了j个奇数，有多少个奇偶性相反
1
2
得到状态转移方程
dp[i][j][1] = min(dp[i - 1][j - 1][0] + 1, dp[i - 1][j - 1][1]);
dp[i][j][0] = min(dp[i - 1][j][1] + 1, dp[i - 1][j][0]);
1
2
当然这得看这个位置本身是不是已经有了数值，如果为0则两个都需要，如果已经有数值了就按照原来的数值进行dp
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
int dp[120][60][2], v[120];
cin>>n;
for(int i=0;i<n;++i) {
cin >> v[i];
}
memset(dp, 0x3f, sizeof(dp));
if(v[0] == 0)
dp[0][1][1] = dp[0][0][0] = 0;
else
dp[0][v[0] & 1][v[0] & 1] = 0;
for (int i = 1; i < n; ++i) {
for (int j = 0; j <= min(i + 1, (n + 1) / 2); ++j) {
if ((v[i] & 1 || v[i] == 0) && j > 0)
dp[i][j][1] = min(dp[i - 1][j - 1][0] + 1, dp[i - 1][j - 1][1]);
if (!(v[i] & 1))
dp[i][j][0] = min(dp[i - 1][j][1] + 1, dp[i - 1][j][0]);
}
}
cout << min(dp[n-1][(n+1)/2][1], dp[n-1][(n+1)/2][0]) << endl;
}
int main() {
solve();
return 0;
}
Codeforces Round #612 (Div. 2)
原文：https://www.cnblogs.com/hgangang/p/12189983.html