题目链接
A.Candies and Two Sisters
void solve()
{
rd(n);
if(n%2==0) n--;
printf("%lld\n",n/2);
}
爱丽丝所获得的糖范围是 [(n+1)/2 , n]
B.Construct the String
#include
using namespace std;
typedef long long ll;
typedef pair pll;
templateinline void rd(T &x){x=0;
char o,f=1;
while(o=getchar(),o<48)if(o==45)f=-f;
do x=(x<<3)+(x<<1)+(o^48);
while(o=getchar(),o>47);
x*=f;
}
const int inf=~0u>>2;
//1073741823
const ll INF=~0ull>>2;
//4611686018427387903
const int maxn=1e3+10;
ll n,a,b;
void solve()
{
string s;
rd(n);
rd(a);
rd(b);
for(ll i=0;
i 构造一个满足a,b的字符串，然后循环打印
C.Two Teams Composing
#include
using namespace std;
typedef long long ll;
typedef pair pll;
templateinline void rd(T &x){x=0;
char o,f=1;
while(o=getchar(),o<48)if(o==45)f=-f;
do x=(x<<3)+(x<<1)+(o^48);
while(o=getchar(),o>47);
x*=f;
}
const int inf=~0u>>2;
//1073741823
const ll INF=~0ull>>2;
//4611686018427387903
const int maxn=2e5+10;
ll n,a[maxn],maxx,num;
void solve()
{
rd(n);
num=maxx=0;
mapm;
for(ll i=1;
i<=n;
i++)
{
rd(a[i]);
m[a[i]]++;
if(m[a[i]]==1) num++;
maxx=max(maxx,m[a[i]]);
}
if(maxx==num) printf("%lld\n",maxx-1);
else printf("%lld\n",min(maxx,num));
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("stdin.in","r",stdin);
//freopen("stdout.out","w",stdout);
#endif ll T;
rd(T);
while(T--) solve();
return 0;
} 【everyday|Codeforces Round #634 (Div. 3)】我们只需要知道maxx=同一个数最多出现的次数和num=所有出现数的种类，
如果二者相等，需要-1（因为maxx与num共用一个数）
不相等的话输出小的那个数
D.Anti-Sudoku
#include
using namespace std;
typedef long long ll;
typedef pair pll;
templateinline void rd(T &x){x=0;
char o,f=1;
while(o=getchar(),o<48)if(o==45)f=-f;
do x=(x<<3)+(x<<1)+(o^48);
while(o=getchar(),o>47);
x*=f;
}
const int inf=~0u>>2;
//1073741823
const ll INF=~0ull>>2;
//4611686018427387903
const int maxn=2e5+10;
string s[14];
void solve()
{
for(int i=0;
i<9;
i++) cin>>s[i];
s[0][3]=s[2][3];
s[1][0]=s[0][0];
s[2][6]=s[1][6];
s[3][4]=s[5][4];
s[4][1]=s[3][1];
s[6][5]=s[8][5];
s[5][7]=s[4][7];
s[7][2]=s[6][2];
s[8][8]=s[7][8];
for(int i=0;
i<9;
i++) cout<[i]< 在每个九宫格里改一个数,保证这个改的数与之前改的所有数不在同一行且不在同一列
E1.Three Blocks Palindrome (easy version) (这是一个蠢爆了的做法）
now[i][j]代表前i位出现j的次数
#include
using namespace std;
typedef long long ll;
typedef pair pll;
templateinline void rd(T &x){x=0;
char o,f=1;
while(o=getchar(),o<48)if(o==45)f=-f;
do x=(x<<3)+(x<<1)+(o^48);
while(o=getchar(),o>47);
x*=f;
}
const ll inf=~0u>>2;
//1073741823
const ll INF=~0ull>>2;
//4611686018427387903
const ll maxn=2e3+10;
ll a[maxn],n,now[maxn][30],mp[maxn][maxn],temp,maxx;
void solve()
{
rd(n);
temp=-1;
maxx=-INF;
for(ll i=1;
i<=n;
i++) rd(a[i]);
for(ll i=1;
i<=n;
i++)
for(ll j=1;
j<=26;
j++)
now[i][j]=((a[i]==j)?1:0)+now[i-1][j];
for(ll i=1;
i<=n;
i++)
for(ll j=1;
j<=i;
j++)
{
for(ll k=1;
k<=26;
k++) temp=max(temp,now[i][k]-now[j-1][k]);
mp[j][i]=temp;
temp=-1;
}
for(ll i=1;
i<=26;
i++) maxx=max(maxx,now[n][i]);
for(ll i=1;
i<=n;
i++)
for(ll j=1;
j<=i;
j++)
{
for(ll k=1;
k<=26;
k++)
{
ll ans=min(now[j-1][k],now[n][k]-now[i][k]);
maxx=max(maxx,ans*2+mp[j][i]);
}
}
printf("%lld\n",maxx);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("stdin.in","r",stdin);
//freopen("stdout.out","w",stdout);
#endif ll T;
rd(T);
while(T--) solve();
return 0;
} E2.Three Blocks Palindrome (hard version) 用longlong mle了导致没ac,自闭
#include
using namespace std;
typedef long long ll;
typedef pair pll;
templateinline void rd(T &x){x=0;
char o,f=1;
while(o=getchar(),o<48)if(o==45)f=-f;
do x=(x<<3)+(x<<1)+(o^48);
while(o=getchar(),o>47);
x*=f;
}
const int inf=~0u>>2;
//1073741823
const ll INF=~0ull>>2;
//4611686018427387903
const int maxn=2e5+10;
int a[maxn],sum[maxn][210],n;
vectormp[210];
void solve()
{
int n,ans=-inf;
rd(n);
for(int i=1;
i<=200;
i++) mp[i].clear();
for(int i=1;
i<=n;
i++)
{
for (int j=1;
j<=200;
j++)
{
sum[i][j]=0;
sum[i][j]=sum[i-1][j];
}
rd(a[i]);
sum[i][a[i]]++;
ans=max(ans,sum[i][a[i]]);
mp[a[i]].push_back(i);
}
for(int i=1;
i<=200;
i++)
{
if(mp[i].size()==0)continue;
for (int j=0;
j<=mp[i].size()/2;
j++)
{
int l=mp[i][j],r=mp[i][mp[i].size()-1-j];
if(l sum[i][j]存储前i位j出现的次数,mp[i][j]存储i第j次出现的位置(从0开始）
ans先存储了只取一种字符的答案(也就是一个字符出现次数的最大值）
我们先枚举a，再枚举a的数量，
[l,r]就是我们要选的大区间，然后我们这个区间内枚举b，
a的数量是2*j+2；
b的数量是sum[r-1][k]-sum[l][k]；
然后更新ans
F.Robots on a Grid （尽快补）
推荐阅读
- 补题|Educational Codeforces Round 85 (Rated for Div. 2)
- 补题|Codeforces Round #635 (Div. 2)
- 补题|Codeforces Round #633 (Div. 2)
- Codeforces Round #623
- 补题|Omkar and Bed Wars
- Codeforces Round #609 (Div. 2)
- 牛妹爱数列