A：开场懵逼。然后发现有人1min过，于是就sort了一下，于是就过了。正经证明的话，考虑回文串两端点一定是相同的，所以最多有Σcnti*(cnti+1)/2个，cnti为第i种字母出现次数。而sort是可以达到这个最大值的。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 100010
int n;
char s[N];
int main()
{
n=read();
scanf("%s",s+);sort(s+,s+n+);
printf("%s",s+);
return ;
}
B：注意到由一点到另一点向左和向右移动次数的差是固定的，所以只需要最小化他们的和。直接dij即可。实际上有一种01bfs的trick，用来跑边权只有01的最短路，使用一个deque，每次将0边扩展到的点放在队首，1边扩展到的点放在队尾，容易发现这样保证了队列里的点按距离排序。不过普通队列直接bfs的fst了一片。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 2010
int n,m,r,c,x,y,p[N*N],t,ans=;
int a[N][N],d[N*N];
bool flag[N*N];
struct data{int to,nxt,len;
}edge[N*N<<];
void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}
int trans(int x,int y){return (x-)*m+y;}
struct data2
{
int x,d;
bool operator <(const data2&a) const
{
return d>a.d;
}
};
priority_queue<data2> q;
void dijkstra(int start)
{
while (!q.empty()) q.pop();
memset(d,,sizeof(d));d[start]=;q.push((data2){start,});
memset(flag,,sizeof(flag));
for (int i=;i<=n*m;i++)
{
while (!q.empty()&&flag[q.top().x]) q.pop();
if (q.empty()) break;
data2 v=q.top();q.pop();
flag[v.x]=;
for (int j=p[v.x];j;j=edge[j].nxt)
if (v.d+edge[j].len<d[edge[j].to])
{
d[edge[j].to]=v.d+edge[j].len;
q.push((data2){edge[j].to,d[edge[j].to]});
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read(),m=read(),r=read(),c=read(),x=read(),y=read();swap(x,y);
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
{
char c=getchar();
while (c!='.'&&c!='*') c=getchar();
if (c=='.') a[i][j]=;
}
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
if (a[i][j])
{
if (i>&&a[i-][j]) addedge(trans(i,j),trans(i-,j),);
if (j>&&a[i][j-]) addedge(trans(i,j),trans(i,j-),);
if (i<n&&a[i+][j]) addedge(trans(i,j),trans(i+,j),);
if (j<m&&a[i][j+]) addedge(trans(i,j),trans(i,j+),);
}
dijkstra(trans(r,c));
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
if (d[trans(i,j)]<=n*m)
{
//cout<<i<<' '<<j<<' '<<d[trans(i,j)]<<endl;
int p=(d[trans(i,j)]+j-c)/,q=d[trans(i,j)]-p;
if (p<=x&&q<=y)ans++;
}
//x+y=d x-y=j-c x right
//x=(d+j-c)/2 y=d-x
cout<<ans;
return ;
}
C：将所有点放在一条线上，黑点划在一边白点划在一边，每次取未确定部分的中点，根据所给颜色继续划分。可能需要把第一个点放在最左或最右，不这么干的话最后可能会有重合点。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 35
int n,l,r;
int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
cin>>n;l=,r=;
cout<<<<' '<<<<endl;
char ch=getchar();while (ch!='b'&&ch!='w') ch=getchar();
for (int i=;i<=n;i++)
{
cout<<<<' '<<(l+r)/<<endl;
fflush(stdout);
char c=getchar();while (c!='b'&&c!='w') c=getchar();
if (c==ch) l=(l+r)/;else r=(l+r)/;
while (c>='a'&&c<='z') c=getchar();
}
cout<<<<' '<<l<<' '<<<<' '<<r<<endl;
fflush(stdout);
return ;
}
后面的神仙题不管了。
本来是手速场结果C想了1h，BC加起来还wa了四发，于是就没救了。
result：rank 226 rating +15