「CF666X」 Codeforces Round #349 (Div. 1)
A. Reberland Linguistics
此题最重要的是理解题意！！！
英语渣伤不起
给定一个字符串，先去掉一个长度至少为5的前缀，要求把剩下的字符串划分成长度为2或3的串，这些串相邻之间不能完全相同，问可能有哪些长度为2或3的串
看错题意就写了个哈希+搜索一直wa，后来领悟了就没另起炉灶，改成了牵强的记搜
大概和dp差不多意思，f[i][0/1]表示前i个字符，最后一个串长度为2/3是否可行，转移显然。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pi acos(-1) #define eps 1e-13 #define mod 10000007 #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,top; char c[10005]; int path[10005],ans[20005],v[10005][3],mark[10005][3]; string q[20005]; int get(int x,int y) { if(y>n)return 0; int H=0; for(int i=x;i<=y;i++) H=H*27+c[i]-'a'+1; return H; } int dfs(int x,int K,int Last,int d) { if(x==n+1)return 1; if(x>=n)return 0; if(mark[x][d])return mark[x][d]; mark[x][d]=-1; for(int k=1;k<=2;k++) { int t=v[x][k]; if(Last!=t) { path[K]=t; if(dfs(x+k+1,K+1,t,k)==1) { mark[x][d]=1; ans[t]=1; } } } return mark[x][d]; } int main() { scanf("%s",c+1); n=strlen(c+1); for(int i=1;i<=n-1;i++)v[i][1]=get(i,i+1); for(int i=1;i<=n-2;i++)v[i][2]=get(i,i+2); for(int i=5;i<=n;i++) dfs(i+1,1,-1,0); for(int i=1;i<=n;i++) for(int k=1;k<=2;k++) if(i+k<=n&&ans[v[i][k]]) { string s=""; for(int t=0;t<=k;t++) s+=c[i+t]; ans[v[i][k]]=0; q[++top]=s; } sort(q+1,q+top+1); cout<<top<<endl; for(int i=1;i<=top;i++) cout<<q[i]<<endl; return 0; } |
B. World Tour
给定一张边权为1的有向图，求四个不同点A, B, C, D
使得dis(A, B) + dis(B, C) + dis(C, D)取最大值
先bfs出任意两点的距离，f(i, 0-2)表示从i出发的最远的三个点，g(i, 0-2)表示到i的最远的三个点
枚举B和C，再枚举3 * 3个点对，选出最优的A和D
保留三个点的原因是保证A, B, C, D互不相同
复杂度n^2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pa pair<int,int> #define pi acos(-1) #define eps 1e-13 #define mod 10000007 #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,ans,ans1,ans2,ans3,ans4; vector<int>e[5005]; queue<int>q; int d[3005][3005]; int f[3005][3],g[3005][3]; void get(int x) { q.push(x); for(int i=1;i<=n;i++)d[x][i]=inf; d[x][x]=0; while(!q.empty()) { int t=q.front();q.pop(); for(int i=0;i<e[t].size();i++) if(d[x][e[t][i]]==inf) { d[x][e[t][i]]=d[x][t]+1; q.push(e[t][i]); } } } void pre(int x) { for(int i=1;i<=n;i++) { int t=i; for(int j=0;j<3;j++) { int p=f[x][j]; if(d[p][x]<d[t][x]&&d[t][x]!=inf)swap(f[x][j],t); } t=i; for(int j=0;j<3;j++) { int p=g[x][j]; if(d[x][p]<d[x][t]&&d[x][t]!=inf)swap(g[x][j],t); } } } void solve(int u,int v) { if(d[u][v]==inf)return; for(int i=0;i<3;i++) for(int j=0;j<3;j++) { int p1=f[u][i],p2=g[v][j]; if(p1==0||p2==0)continue; if(p1!=p2&&p1!=v&&p2!=u&&d[p1][u]+d[u][v]+d[v][p2]>ans) { ans=d[p1][u]+d[u][v]+d[v][p2]; ans1=p1,ans2=u,ans3=v,ans4=p2; } } } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { int u,v; u=read();v=read(); e[u].push_back(v); } for(int i=1;i<=n;i++)get(i); for(int i=1;i<=n;i++)pre(i); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j) solve(i,j); cout<<ans1<<' '<<ans2<<' '<<ans3<<' '<<ans4<<endl; return 0; } |
Subscribe