Codeforces Round #553 (Div. 2)
A. Maxim and Biology
题意：
给出一个串s，问最少需要多少步操作使得串s包含"ACTG"这个子串，输出最少操作次数；
题解：
枚举每个位置 i，求出将 i,i+1,i+2,i+3 变为 "ACTG" 所需的最少操作次数即可；
AC代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define INF 0x3f3f3f3f 4 #define ll long long 5 #define mem(a,b) memset(a,b,sizeof(a)) 6 7 int n; 8 char s[100]; 9 10 int Step(char x1,char x2)//求解x1变为x2所需的最少操作步骤 11 { 12 if(x1 <= x2) 13 return min(x2-x1,x1-'A'+'Z'-x2+1); 14 else 15 return min(x1-x2,'Z'-x1+x2-'A'+1); 16 } 17 //求解以index位置开始使得其连续的四个字符变为"ACTG"所需的最小操作步骤 18 int F(int index) 19 { 20 int ans=0; 21 ans += Step(s[index],'A'); 22 ans += Step(s[index+1],'C'); 23 ans += Step(s[index+2],'T'); 24 ans += Step(s[index+3],'G'); 25 return ans; 26 } 27 int Solve() 28 { 29 int ans=INF; 30 int len=strlen(s); 31 for(int i=0;i+4 <= len;++i) 32 ans=min(ans,F(i)); 33 return ans; 34 } 35 int main() 36 { 37 // freopen("C:\Users\hyacinthLJP\Desktop\in&&out\contest","r",stdin); 38 while(~scanf("%d",&n)) 39 { 40 scanf("%s",s); 41 printf("%d ",Solve()); 42 } 43 return 0; 44 }
B. Dima and a Bad XOR
题意：
给出一个 n*m 的矩阵a[][]，每一行任选一个元素，判断选出的这 n 个元素的异或和是否大于0；
如果存在大于0的选法，输出 "TAK" ，并且输出每一行选择的元素的列标；
如果不存在，输出 "NIE"；
题解：
令 ans = a[1][1]^a[2][1]^........^a[n][1]；
①ans > 0 : 输出 n 个 1
②ans == 0 : 判断是否可以将a[1][1] 或 a[2][1] 或 ..... 或 a[n][1] 变成同一行的其他元素；
如果可以，输出 "TAK"，并将任意一个a[ i ][1]变为同行中的其他元素；
反之，输出"NIE"；
AC代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int n,m; 5 int a[600][600]; 6 int tmp[600]; 7 8 bool isSat()//判断是否存在去重后的元素个数 > 1 的行 9 { 10 for(int i=1;i <= n;++i) 11 { 12 /** 13 如果想要从tmp[1]位置作为起始位置，第一个参数为tmp+1 14 a[i]数组第一个位置的下标为a[i][1],所以第二个参数为a[i]+1 15 第三个参数不是指数组个数，而是指要复制的数据的总字节数长度 16 */ 17 memcpy(tmp+1,a[i]+1,m*sizeof(int));//将a[i]数组拷贝给tmp数组 18 sort(tmp+1,tmp+m+1); 19 int t=unique(tmp+1,tmp+m+1)-tmp;//去重 20 t--; 21 if(t > 1) 22 return true; 23 } 24 return false; 25 } 26 void Solve() 27 { 28 int ans=0; 29 for(int i=1;i <= n;++i) 30 ans ^= a[i][1]; 31 32 if(ans != 0 || ans == 0 && isSat()) 33 { 34 printf("TAK "); 35 bool flag=(ans != 0);//如果ans != 0,输出n个1 36 for(int i=1;i <= n;++i) 37 { 38 if(!flag) 39 { 40 for(int j=2;j <= m;++j) 41 if(a[i][j] != a[i][1]) 42 { 43 flag=true;//如果ans=0,找到第一个相异与a[i][1]的元素的列标即可 44 printf("%d ",j); 45 break;//记得break,不然，printf("%d ",j) 可能会调用多次 46 } 47 if(!flag) 48 printf("1 "); 49 } 50 else 51 printf("1 "); 52 } 53 printf(" "); 54 } 55 else 56 printf("NIE "); 57 } 58 int main() 59 { 60 while(~scanf("%d%d",&n,&m)) 61 { 62 for(int i=1;i <= n;++i) 63 for(int j=1;j <= m;++j) 64 scanf("%d",a[i]+j); 65 Solve(); 66 } 67 return 0; 68 }