http://codeforces.com/contest/1151/problem/A
题意：对于任意两个字符a，b，将a变成b的价值为他们的最小距离。其中z到a的距离是1。
求出将给定字符串变成一个含有 "ACTG" 子串的字符串最小价值。
思路：暴力模拟。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int dis(char a,char b){ 5 if(a > b){char c = a;a = b;b = c;} 6 int d = b - a; 7 return min(26 - d,d); 8 } 9 10 int main(){ 11 int n; 12 cin >> n; 13 char in[100]; 14 scanf("%s",in); 15 int ans = 99999999; 16 int maxx = 0; 17 for(int i(0);i+3<n;++i) { 18 maxx = 0; 19 maxx += dis(in[i],'A'); 20 maxx += dis(in[i+1],'C'); 21 maxx += dis(in[i+2],'T'); 22 maxx += dis(in[i+3],'G'); 23 ans = min(maxx,ans) ; 24 } 25 cout << ans << endl; 26 27 return 0; 28 }
http://codeforces.com/contest/1151/problem/B
题意：给定n行每行m个数字，问是否能在每一行都选出一个数字，使得这些共n个数字的异或和不为零。
思路：先求出某一列的异或和，如果不为0，则找到。
如果为0，那么就对某一行被选中的数字进行更换，如果更换后的数字和更换前的数字不同，则成功找到。
如果无论如何更换异或和都是0，那么就是找不到。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int a[505][505]; 5 int b[505]; 6 int main() 7 { 8 int n,m; 9 scanf("%d%d",&n,&m); 10 for(int i = 1;i <= n;i ++){ 11 for(int j = 1;j <= m;j ++){ 12 scanf("%d",&a[i][j]); 13 } 14 } 15 int ans = 0; 16 for(int i = 1;i <= n;i ++){ 17 ans ^= a[i][1]; 18 b[i] = 1; 19 } 20 if(!ans){ 21 int f = 0; 22 for(int i = 1;i <= n;i ++){ 23 int now = a[i][b[i]]; 24 f = 0; 25 for(int j = 2;j <= m;j ++){ 26 if(now != a[i][j]){b[i] = j;f = 1;break;} 27 } 28 if(f){break;} 29 } 30 if(!f){ 31 printf("NIE "); 32 } 33 else{ 34 printf("TAK "); 35 for(int i = 1;i <= n;i ++){ 36 if(i != 1){printf(" ");} 37 printf("%d",b[i]); 38 }printf(" "); 39 } 40 } 41 else{ 42 printf("TAK "); 43 for(int i = 1;i <= n;i ++){ 44 if(i != 1){printf(" ");} 45 printf("%d",b[i]); 46 }printf(" "); 47 } 48 49 return 0; 50 }
http://codeforces.com/contest/1151/problem/C
题意：列出两个数列：
A：1，3，5，7，9，11，13......
B：2，4，6，8，10，12，14......
由上面两个数列得到一个新的数列（一个A数组中的数，两个B数组中的数，四个A数组中的数，八个B数组中的数......）：
C：1，2，4，3，5，7，9，6，8，10，12，14，16，18，20......
求出任意区间的数字和并取模，总区间范围是 1e18 。
思路：写起来比较别扭，只需要模拟即可。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 long long mod = 1e9 + 7; 5 long long F(long long x){ 6 long long ans = 0; 7 long long now = 1; /// %2 8 long long sum = x; 9 long long len = 1; 10 long long j = 1; 11 long long o = 2; 12 while(sum){ 13 sum -= len; 14 if(now){ 15 ans += ((len % mod) * ((len + j - 1) % mod)); 16 ans %= mod; 17 j += ((len * 2) % mod); 18 j %= mod; 19 } 20 else{ 21 ans += ((len % mod) * ((len + o - 1) % mod)); 22 ans %= mod; 23 o += ((len * 2) % mod); 24 o %= mod; 25 } 26 now = 1 - now; 27 len = min(len * 2,sum); 28 } 29 return ans % mod; 30 } 31 32 int main(){ 33 long long l,r; 34 cin >> l >> r; 35 ///cout << F(r) << " " << F(l - 1) << endl; 36 long long ans = F(r) - F(l - 1); 37 ans = (((ans % mod) + mod) % mod); 38 cout << ans << endl; 39 40 return 0; 41 }
http://codeforces.com/contest/1151/problem/D
题意：给定n个人，每个人有两个权值a和b。要将这些人排队，如果一个人被排在第 i 个位置。那他的愤怒值是 a*(i - 1) + b*(n - j)。
求出如何排队使得总愤怒值最小。
思路：贪心，一个人的 b - a 越小，这个人越靠前。排序即可。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 struct Node{ 5 long long a,b; 6 }p[100005]; 7 8 bool cmp(Node x,Node y){ 9 return x.b - x.a < y.b - y.a; 10 } 11 12 int main(){ 13 int n; 14 cin >>n; 15 for(int i = 0;i < n;i ++){ 16 cin >> p[i].a >> p[i].b; 17 } 18 sort(p,p + n,cmp); 19 long long ans = 0; 20 for(int i = 0;i < n;i ++){ 21 ans += (p[i].a * i) + (p[i].b * (n - 1 - i)); 22 } 23 cout << ans << endl; 24 25 return 0; 26 }