题目链接:
https://codeforces.com/contest/1151
A. Maxim and Biology
题解:
水题直接上代码
代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,ans=123456789; 4 string ss,s="ACTG"; 5 6 int main() 7 { 8 #ifndef ONLINE_JUDGE 9 freopen("aa.in","r",stdin); 10 #endif 11 ios::sync_with_stdio(false); 12 cin>>n; 13 //for(int i=1;i<=n;i++) 14 cin>>ss; 15 for(int i=0;i<=n-4;i++) 16 { 17 int tp=0; 18 for(int j=i;j<=i+3;j++) 19 { 20 int x=fabs(ss[j]-s[j-i]); 21 tp+=min(x,26-x); 22 } 23 ans=min(ans,tp); 24 } 25 cout<<ans; 26 }View Code
B. Dima and a Bad XOR
题意:
给你一个n*m的矩阵,每一行选一个数,是他们的异或和大于0.
题解:
这题惨遭hack,其实不难,还是太菜了,分类讨论能力不够导致思维有些小混乱。
因为只需要大于零,我们可以枚举每一位二进制位。
对于某一位某一行只有三种情况:
(1) 这一行每个数这一位都为1
(2)这一位都为0
(3)这一位既有0又有1
显然如果某一行满足(3),就一定有解(想一想为什么),然后我们先假定所有满足(3)的行都选择放0。
如果没有(3),则每一行这一位都是固定的,算一下等不等于1就行了。
代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 600 4 int n,m,ans=123456789; 5 int mp[N][N]; 6 int a[N][20],b[N][20]; 7 int flag[N],c[N]; 8 int main() 9 { 10 #ifndef ONLINE_JUDGE 11 freopen("aa.in","r",stdin); 12 #endif 13 ios::sync_with_stdio(false); 14 cin>>n>>m; 15 for(int i=1;i<=n;i++) 16 for(int j=1;j<=m;j++) 17 cin>>mp[i][j]; 18 for(int k=0;k<=9;k++) 19 { 20 for(int i=1;i<=n;i++) 21 { 22 for(int j=1;j<=m;j++) 23 { 24 25 if ((mp[i][j]>>k)&1) 26 a[i][k]=j;else b[i][k]=j; 27 } 28 if (a[i][k]>0&&b[i][k]>0)flag[k]=1; 29 if (a[i][k]>0&&b[i][k]==0)c[k]^=1; 30 } 31 } 32 for(int k=0;k<=9;k++) 33 { 34 if (flag[k]==1||c[k]==1) 35 { 36 cout<<"TAK"<<endl; 37 for(int i=1;i<=n;i++) 38 { 39 if (b[i][k]==0)cout<<a[i][k]<<" "; 40 if (a[i][k]==0)cout<<b[i][k]<<" "; 41 if (a[i][k]>0&&b[i][k]>0) 42 { 43 if (c[k]==0)cout<<a[i][k]<<" "; 44 if (c[k]==1)cout<<b[i][k]<<" "; 45 c[k]=1; 46 } 47 } 48 return 0; 49 } 50 } 51 cout<<"NIE"; 52 53 }View Code