Codeforces Round#516 Div.1 翻车记
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=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 100010 int n; char s[N]; int main() { n=read(); scanf("%s",s+1);sort(s+1,s+n+1); printf("%s",s+1); return 0; }
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=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 2010 int n,m,r,c,x,y,p[N*N],t,ans=0; int a[N][N],d[N*N]; bool flag[N*N]; struct data{int to,nxt,len; }edge[N*N<<2]; 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-1)*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,42,sizeof(d));d[start]=0;q.push((data2){start,0}); memset(flag,0,sizeof(flag)); for (int i=1;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]=1; 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=1;i<=n;i++) for (int j=1;j<=m;j++) { char c=getchar(); while (c!='.'&&c!='*') c=getchar(); if (c=='.') a[i][j]=1; } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (a[i][j]) { if (i>1&&a[i-1][j]) addedge(trans(i,j),trans(i-1,j),0); if (j>1&&a[i][j-1]) addedge(trans(i,j),trans(i,j-1),1); if (i<n&&a[i+1][j]) addedge(trans(i,j),trans(i+1,j),0); if (j<m&&a[i][j+1]) addedge(trans(i,j),trans(i,j+1),1); } dijkstra(trans(r,c)); for (int i=1;i<=n;i++) for (int j=1;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)/2,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 0; }