第一cf rank进500，虽然是div3 ==
A. Candies and Two Sisters
题意：
求a+b=n，且0<b<a的所有方案数。
思路：
如果是偶数就有n/2-1，奇数就有n/2
代码：
#include<iostream>
#include<string.h>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<string>
#include<set>
#include<map>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
int main(){
int T;
cin>>T;
while(T--){
long long n;
cin>>n;
if(n<=2) cout<<"0
";
else {
if(n%2)
cout<<n/2<<endl;
else cout<<n/2-1<<endl;
}
}
return 0;
}
B. Construct the String
题意：
构造一个长度为n的字符串，使得每一个长度为a的子串都包含b个不同的字母。(1≤a≤n≤2000,1≤b≤min(26,a))
思路：
构造一个长度为b的循环串就可以了
代码：
#include<iostream>
#include<string.h>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<string>
#include<set>
#include<map>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
int main(){
int T;
cin>>T;
while(T--){
int n,a,b;
cin>>n>>a>>b;
char c=0;
for(int i=1;i<=n;++i){
cout<<char(c+'a');
c++;
c%=b;
}
cout<<endl;
}
return 0;
}
C. Two Teams Composing
题意：
求将一个包含n个数的集合划分成两类，一类中的数都互不相同，二类中的数都相同，一二类的数字个数相同，求数字个数的最大值。
思路：
枚举集合二的数字情况，求最大值。
代码：
#include<iostream>
#include<string.h>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<string>
#include<set>
#include<map>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
set<int> S;
map<int,int> mmp;
int main(){
int T;
cin>>T;
while(T--){
int n;
scanf("%d",&n);
mmp.clear();
S.clear();
for(int i=1,x;i<=n;++i){
scanf("%d",&x);
mmp[x]++;
S.insert(x);
}
int ans=0;
for(auto it:S){
ans=max(ans,min((int)S.size()-1,mmp[it]));
ans=max(ans,min((int)S.size(),mmp[it]-1));
}
cout<<ans<<endl;
}
return 0;
}
D. Anti-Sudoku
题意：
将一个合法的数独矩阵，操作最多九次，使得每一行每一列每个一3×3的格子都包含至少两个相同的数字。
思路：
枚举每一行，不同行改变属于不同列和不同3×3的方格的小格子就可以了
代码：
#include<iostream>
using namespace std;
const int N=100,M=9;
int a[N][N];
int main(){
int T;
scanf("%d",&T);
while(T--){
for(int i=1;i<=M;++i){
for(int j=1;j<=M;++j){
scanf("%1d",&a[i][j]);
}
}
a[1][1]=a[1][2];a[2][4]=a[2][5];a[3][7]=a[3][8];
a[4][2]=a[4][3];a[5][5]=a[5][6];a[6][8]=a[6][9];
a[7][3]=a[7][4];a[8][6]=a[8][7];a[9][9]=a[9][1];
for(int i=1;i<=M;++i){
for(int j=1;j<=M;++j){
printf("%d",a[i][j]);
}puts("");
}
}
return 0;
}
E1. Three Blocks Palindrome (easy version)
题意：
给出一个字符串构造出一个子序列，使得是一个ABA(A和B可以一样)型的回文串。(a_i<=26,n<=2000)
思路：
一上来就想的E2没思路，然后先过E1。先求每种数字的前缀和，枚举ABA之间的分割点。
代码：
#include<iostream>
#include<string.h>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<string>
#include<set>
#include<map>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
const int N=2010;
int a[N],f[N][30];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
memset(f,0,sizeof f);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;++i){
f[i][a[i]]++;
for(int j=1;j<=26;++j){
f[i][j]+=f[i-1][j];
}
}
int ans=0;
for(int j=1;j<=26;++j){
ans=max(ans,f[n][j]);
}
for(int i=1;i<=n;++i){
for(int j=i;j<=n;++j){
int ll=0,mid=0,rr=0,mid2=0;
for(int k=1;k<=26;++k){
ll=f[i-1][k];
rr=f[n][k]-f[j][k];
mid2=max(mid2,min(ll,rr));
}
for(int k=1;k<=26;++k){
mid=max(mid,f[j][k]-f[i-1][k]);
}
ans=max(ans,mid2*2+mid);
}
}
cout<<ans<<endl;
}
return 0;
}
E2. Three Blocks Palindrome (hard version)
题意：
给出一个字符串构造出一个子序列，使得是一个ABA(A和B可以一样)型的回文串。(a_i<=200,n<=200000)
思路：
看着复杂度还以为是DP，想了半个小时其实还是虾搞。先求每种数字的前缀和，然后从前向后枚举A，遍历到第i，求以i~n中所有a[i]为右边A的情况，假设有x个，然后二分左右和i~n包含相同数量a[i]的位置j，再求j+1~i-1中包含最多数量的相同数y，更新答案2*x+y
代码：
#include<iostream>
#include<string.h>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<string>
#include<set>
#include<map>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
const int N=200100;
int a[N],f[210][N];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
for(int i=0;i<=n;++i){
for(int j=0;j<=200;++j) f[j][i]=0;
}
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}int ans=0;
for(int i=1;i<=n;++i){
f[a[i]][i]++;
for(int j=1;j<=200;++j){
f[j][i]+=f[j][i-1];
}
}
for(int i=1;i<=200;++i) ans=max(ans,f[i][n]);
for(int i=n;i>=1;--i){
int x=f[a[i]][n]-f[a[i]][i-1];
int j=lower_bound(f[a[i]]+1,f[a[i]]+n,x)-f[a[i]];
if(j>=i) continue;
int y=0;
for(int k=1;k<=200;++k){
y=max(y,f[k][i-1]-f[k][j]);
}
ans=max(ans,y+2*x);
}
cout<<ans<<endl;
}
return 0;
}