首页 > 代码库 > Codeforces Round #288 (Div. 2)
Codeforces Round #288 (Div. 2)
A. Pasha and Pixels
题意就是给一个n*m的矩阵，k次操作，一开始矩阵全白，一次操作可以染黑一个格子，问第几次操作可以使得矩阵中存在一个2*2的黑色矩阵。直接模拟即可
代码:
1 #include<cstdio> 2 #include<algorithm> 3 #include<map> 4 #include<cstring> 5 #include<vector> 6 #include<cmath> 7 #include<string> 8 #define N 100010 9 #define M 101010 #define P 100000000711 using namespace std;12 int n,m,k,i,a[N],b[N],f[M][M];13 int check(int x,int xx,int y,int yy)14 {15 int w=0;16 w=f[x][y]+f[x][yy]+f[xx][y]+f[xx][yy];17 if (w==4) return 1;else return 0;18 }19 int main()20 {21 scanf("%d%d%d",&n,&m,&k);22 for (i=1;i<=k;i++)23 scanf("%d%d",&a[i],&b[i]);24 for (i=1;i<=k;i++)25 {26 f[a[i]][b[i]]=1;27 if (check(a[i]-1,a[i],b[i]-1,b[i])) break;28 if (check(a[i]-1,a[i],b[i],b[i]+1)) break;29 if (check(a[i],a[i]+1,b[i]-1,b[i])) break;30 if (check(a[i],a[i]+1,b[i],b[i]+1)) break;31 }32 if (i<=k)33 printf("%d",i);34 else35 printf("0");36 }
B. Anton and currency you all know
题意是给一个奇数，你可以交换其中两位，使得其变成一个偶数，并且要求这个偶数尽可能大。由于给的数字是奇数，因此必然是个位数和一个其他位上的数交换，并且交换的这个数得是偶数，如果数字全为奇数那明显不可以。如果交换的这个数大于个位，那么交换以后的数明显会比原数大，因此尽可能的选取高位的数字，使得其比个位数大，那么直接交换即可。若不存在交换的数比个位要大，说明交换后的数字一定会比原数小，那么则应选取一个位数最小的偶数，和个位交换。
代码:
1 #include<cstdio> 2 #include<algorithm> 3 #include<map> 4 #include<cstring> 5 #include<vector> 6 #include<cmath> 7 #include<string> 8 #define N 100010 9 #define M 101010 #define P 100000000711 using namespace std;12 char s[N],t;13 int tmp,len,i;14 int main()15 {16 tmp=-1;17 scanf("%s",s);18 len=strlen(s);19 for (i=0;i<len-1;i++)20 if (s[i]%2==0)21 {22 if (s[len-1]>s[i]) break;23 tmp=i;24 }25 if (i<len-1)26 {27 t=s[i];s[i]=s[len-1];s[len-1]=t;28 }29 else30 if (tmp!=-1)31 {32 t=s[tmp];s[tmp]=s[len-1];s[len-1]=t;33 }34 else35 {36 printf("-1");37 return 0;38 }39 printf("%s",s);40 }
C. Anya and Ghosts
首先需要注意这一题是允许蜡烛在0时之前点的，一时刻只能点亮一根蜡烛。要使蜡烛使用的最少，明显可以采取贪心的做法，能不放则不放，如果到了指定时刻蜡烛数目没有要求的数目，那么在放。
代码:
1 #include<cstdio> 2 #include<algorithm> 3 #include<map> 4 #include<cstring> 5 #include<vector> 6 #include<cmath> 7 #include<string> 8 #define N 100010 9 #define M 101010 #define P 100000000711 using namespace std;12 int m,t,r,i,j,L,R,v[N],w[N];13 map<int,int>ma;14 int main()15 {16 scanf("%d%d%d",&m,&t,&r);17 for (i=1;i<=m;i++)18 scanf("%d",&w[i]);19 L=1;R=0;20 for (i=1;i<=m;i++)21 { 22 while ((L<=R)&&(v[L]<w[i])) L++;23 if (R-L+1<r)24 for (j=r-(R-L+1);j>=1;j--)25 {26 R++;27 if (ma[w[i]-j+t]==1)28 {29 printf("-1");30 return 0;31 }32 ma[w[i]-j+t]=1;33 v[R]=w[i]-j+t;34 if (v[R]<w[i])35 {36 printf("-1");37 return 0;38 }39 }40 }41 printf("%d",R);42 }
D. Tanya and Password
这一题可以转换成求一个欧拉通路，具体的做法每个串都转化成一条边，例如"abc"这个串，可以转换成"ab"->"bc"。也就是前两个字母视为一个节点，后两个字母视为另一个节点，然后连一条有向边。
若有向图中存在一条欧拉通路，则(1)图联通(2)全部点的入度都等于出度或者有一个点入度=出度+1，并且还有一个点出度=入度+1。
代码:
1 #include<cstdio> 2 #include<algorithm> 3 #include<map> 4 #include<cstring> 5 #include<vector> 6 #include<cmath> 7 #include<string> 8 #include<iostream> 9 #define N 500010 10 #define M 1010 11 #define P 1000000007 12 using namespace std; 13 map<string,int> ma; 14 map<int,string> o; 15 string s,s1,s2; 16 int n,i,a,b; 17 int p[N],tt[N],pre[N],dp,tot,rd[N],cd[N],cnt1,cnt2,st,ed,f[N]; 18 char ans[N]; 19 void link(int x,int y) 20 { 21 dp++;pre[dp]=p[x];p[x]=dp;tt[dp]=y; 22 } 23 int gf(int x) 24 { 25 int p,t; 26 p=x; 27 while (p!=f[p])p=f[p]; 28 while (x!=t) 29 { 30 t=f[x]; 31 f[x]=p; 32 x=t; 33 } 34 return p; 35 } 36 void dfs(int x) 37 { 38 int i,tmp=0; 39 i=p[x]; 40 while (i) 41 { 42 p[x]=pre[i]; 43 dfs(tt[i]); 44 i=p[x]; 45 } 46 tot++;ans[tot]=o[x][1]; 47 } 48 int main() 49 { 50 scanf("%d",&n); 51 for (i=1;i<=n;i++) 52 { 53 cin>>s; 54 s1=""; 55 s1=s1+s[0]+s[1]; 56 s2=""; 57 s2=s2+s[1]+s[2]; 58 if (ma[s1]==0) 59 { 60 tot++; 61 ma[s1]=tot; 62 o[tot]=s1; 63 f[tot]=tot; 64 } 65 if (ma[s2]==0) 66 { 67 tot++; 68 ma[s2]=tot; 69 o[tot]=s2; 70 f[tot]=tot; 71 } 72 a=ma[s1]; 73 b=ma[s2]; 74 link(a,b); 75 rd[b]++;cd[a]++; 76 f[gf(a)]=gf(b); 77 } 78 for (i=1;i<=tot;i++) 79 if (gf(i)!=gf(1)) 80 { 81 printf("NO"); 82 return 0; 83 } 84 st=1; 85 for (i=1;i<=tot;i++) 86 { 87 if (cd[i]-rd[i]==1) { 88 st=i; 89 cnt1++; 90 } 91 else 92 if (rd[i]-cd[i]==1) 93 cnt2++; 94 else 95 if (cd[i]-rd[i]!=0) 96 { 97 printf("NO"); 98 return 0; 99 }100 }101 if ((cnt1+cnt2==0)||(cnt1*cnt2==1))102 {103 printf("YES\n");104 printf("%c",o[st][0]);105 tot=0;106 dfs(st);107 for (i=tot;i>=1;i--)108 printf("%c",ans[i]);109 }110 else111 printf("NO");112 }
E. Arthur and Brackets
题意是给一个n,表示有n个左括号，n个右括号，构成长度为2n的括号序列，接下来第i行给的L[i]和R[i]表示从左往右第i个左括号的对应的右括号与他的距离范围(注意给的是距离范围而不是在序列中的实际位置范围)，问是否存在一个合法的括号序列，如果存在，那么随意输出一个。
做法是dp，f[i][j]表示是否存在从第i对括号到第j对括号组成的合法括号序列，dp方程有两种情况
(1)假设i<=k<j,如果f[i][k]=1,f[k+1][j]=1,那么很明显f[i][j]=1，因为如果两个序列是合法的，那么他们左右拼接明显也是合法的。
(2)如果f[i+1][j]=1,那么如果要加上第i对括号后也合法，那么第i个左括号和其所对应的右括号的距离应该是(j-i)*2+1,如果这个距离在其的距离范围内，那么则可行，否则不存在这种情况。
复杂度O(n^3)
代码:
1 #include<cstdio> 2 #include<algorithm> 3 #include<map> 4 #include<cstring> 5 #include<vector> 6 #include<cmath> 7 #include<string> 8 #define N 100010 9 #define M 101010 #define P 100000000711 using namespace std;12 int tot,f[M][M],l[M],r[M],i,j,k,L,R,z,n;13 char s[N];14 void dfs(int l,int r)15 {16 int i;17 if (l>r) return;18 for (i=l;i<=r-1;i++)19 if ((f[l][i])&&(f[i+1][r]))20 {21 dfs(l,i);22 dfs(i+1,r);23 return;24 }25 if (f[l+1][r])26 {27 s[tot]=‘(‘;tot++;28 dfs(l+1,r);29 s[tot]=‘)‘;tot++;30 }31 32 }33 int main()34 {35 scanf("%d",&n);36 for (i=1;i<=n;i++)37 f[i+1][i]=1;38 for (i=1;i<=n;i++)39 scanf("%d%d",&l[i],&r[i]);40 for (i=1;i<=n;i++)41 for (j=1;j<=n-i+1;j++)42 {43 L=j;R=j+i-1;44 for (k=L;k<=R-1;k++)45 f[L][R]=(f[L][R]|(f[L][k]&f[k+1][R]));46 if ((f[L+1][R])&&(l[j]<=2*i-1)&&(2*i-1<=r[j]))47 z=1;48 else49 z=0;50 f[L][R]=(f[L][R]|z);51 }52 if (f[1][n]==0)53 printf("IMPOSSIBLE");54 else55 {56 dfs(1,n);57 printf("%s",s);58 }59 }
Codeforces Round #288 (Div. 2)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。