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 1010 10 #define P 1000000007 11 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 else 35 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 1010 10 #define P 1000000007 11 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 else 30 if (tmp!=-1) 31 { 32 t=s[tmp];s[tmp]=s[len-1];s[len-1]=t; 33 } 34 else 35 { 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 1010 10 #define P 1000000007 11 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 "); 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 else 111 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 1010 10 #define P 1000000007 11 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 else 49 z=0; 50 f[L][R]=(f[L][R]|z); 51 } 52 if (f[1][n]==0) 53 printf("IMPOSSIBLE"); 54 else 55 { 56 dfs(1,n); 57 printf("%s",s); 58 } 59 }