http://codeforces.com/contest/382
A . Ksenia and Pan Scales
题意 ： 每个大写字母都占相同的重量，第一个字符串指的是天平两边现在有的砝码分布，而第二个字符串是想让你把第二个字符串全部的砝码放到第一个字符串上，看“|”两边的字母是不是一样多。
思路 ：算是一个简单小模拟吗？
#include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> using namespace std ; int main() { char str[110] ; char str1[110] ; while(scanf("%s",str)!=EOF) { scanf("%s",str1) ; int len = strlen(str) ; int len1 = 0 ; int len2 = 0,len3 = strlen(str1) ; for(int i = 0 ; i < len ; i++) { if(str[i] != '|') len1++ ; else break ; } len2 = len-len1-1 ; int maxx = max(len1,len2) ; int minn = min(len1,len2) ; if(maxx - minn > len3) { printf("Impossible ") ; continue ; } else { int x = len3-(maxx-minn) ; if(x%2 == 1) printf("Impossible ") ; else { if(len1 > len2) { for(int i = 0 ; i < len1 ; i++) printf("%c",str[i]) ; for(int i = 0 ; i < x/2 ; i++) printf("%c",str1[i]) ; printf("|") ; for(int i = len1+1 ; i < len ; i++) printf("%c",str[i]) ; for(int i = x/2 ; i < len3 ; i++) printf("%c",str1[i]) ; printf(" ") ; } else { for(int i = 0 ; i < len1 ; i++) printf("%c",str[i]) ; for(int i = 0 ; i < x/2 +maxx-minn; i++) printf("%c",str1[i]) ; printf("|") ; for(int i = len1+1 ; i < len ; i++) printf("%c",str[i]) ; for(int i = x/2 +maxx-minn ; i < len3 ; i++) printf("%c",str1[i]) ; printf(" ") ; } } } } return 0 ; }
B. Number Busters
题意 ：Arthur手中有4个数字，a, b, w, x (0 ≤ b < w, 0 < x < w) ，Alexander手中有一个数字 c。两个人手中的数字同时操作，Alexander每一秒进行的操作是c = c-1。Arthur每一秒进行的操作是：如果b>=x ， 则进行b = b-x。否则，同时进行两步， a = a - 1; b = w - (x - b)，每一秒都进行这两个人的操作，直到c<= a为止，求过了多少秒。
思路 ：这个题的话如果真的按照它的这个顺序去做肯定会超时的，因为在我交的那一瞬间我就意识到了，，，结果真的超时了，奈何我当时电脑自动关机了，，一般来说可以选择去找循环结，因为肯定是有规律，后来看到人家的代码，竟然用一个小公式搞定了，表示真的没看懂那个小公式，不过循环结的我倒是看懂了，，，，
#include <stdio.h> #include <iostream> #include <string.h> #include <stdlib.h> using namespace std ; #define ll long long ll vis[1110] ; int main() { ll a,b,w,x,c ; while(~scanf("%I64d %I64d %I64d %I64d %I64d",&a,&b,&w,&x,&c)) { memset(vis,0,sizeof(vis)) ; ll cnt = 0 ;//最终的秒数 while(b >= x)//如果b是大于x的，那么这里的秒数都容易数出 { if(c >= a) break ; b = b-x ; c-- ; cnt++ ; } if(c <= a) { printf("%I64d ",cnt) ; continue ; } ll st = 0,b1 = b ,acnt = 0 ; while(vis[b1] == 0)//找循环结，等vis[b1]为1的时候，就说明里边的这些步骤就是重复进行的了 { vis[b1] = 1 ; st ++ ;//在一个循环结内，进行了几次c--操作。 if(b1 >= x) b1 = b1-x ; else { b1 = w-x+b1 ; acnt++ ;//进行了几次a--操作。 } } ll cnt1 = 0; if((c - a - acnt) >0)//这里的(c-a-acnt)减acnt是为了防止最后一次循环结的时候若是不够容易减出负数 cnt1 = (c-a-acnt)/(st-acnt) ;//剩下的还能进行几次循环 cnt += cnt1*st ; c = c-st*cnt1 ;//最后那一次剩下的a和c a = a-acnt*cnt1 ; while(c > a) { if(b >= x) { b = b-x ; c-- ; cnt++ ; } else { b = w+b-x ; c-- ; a-- ; cnt++ ; } } printf("%I64d ",cnt) ; } return 0 ; }
#include <stdio.h> #include <string.h> #include <math.h> long long a, b, w, x, c; int main() { scanf("%I64d%I64d%I64d%I64d%I64d", &a, &b, &w, &x, &c); if (c <= a) printf("0 ") ; else printf("%I64d ", (long long)ceil((x * (c - a) - b) * 1.0 / (w - x)) + (c - a)); return 0; }
C. Arithmetic Progression
题意 ：给你一组数字，要求加上一个数字，使这组数字构成等差数列，要求输出有几种加法，分别要加上哪个数字，如果有无穷个，就输出-1 。
思路 ：这个题就是分情况的：
1个元素时，根据定义，任两个数都能构成等差数列，所以只能输出-1
2个元素时，若为a和b，当a == b时，只有一个可插入的，即为a或b；当max（a，b）-min（a，b）%2 == 0时，则除了再两头插入之外，中间还可以再插入；若%2为1时，只能在两头插入了。
大于2个元素时，如果原来的数列本身就是一个等差数列时，只能在两头插入；如果原来的数列本身只有一个元素构成，即这个数列所有的元素都想等，那就只能插入一个数；求出相邻两元素的差di，如果di只有两个的话，若是大的那个还是小的那个两倍的话，则可以在大的那个间距那里插入一个；除了上述3种情况，其余全为0。
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std ; int a[101200] ; int main() { int n ; while(~scanf("%d",&n)) { for(int i = 0 ; i < n ; i++) scanf("%d",&a[i]) ; if(n == 1) { printf("-1 ") ; continue ; } if(n == 0) { printf("0 ") ; continue ; } sort(a,a + n) ; if(n == 2) { if(a[1] == a[0]) printf("1 %d",a[0]) ; else if((a[1]-a[0]) % 2 == 0) printf("3 %d %d %d ",a[0]-(a[1]-a[0]),(a[1]-a[0])/2+a[0],a[1]+a[1]-a[0]) ; else printf("2 %d %d ",a[0]-(a[1]-a[0]),a[1]+a[1]-a[0]) ; } else if(n > 2) { int pos = 0 ; int d = 2100000000 ; for(int i = 0 ; i < n-1 ; i++) { if(a[i+1]-a[i] < d) d = a[i+1]-a[i] ; } int count = 0 ; for(int i = 0 ; i < n-1 ; i++) { if((a[i+1]-a[i] )!= d) { pos = i ; count++ ; } } if(count == 0 && d != 0) printf("2 %d %d ",a[0]-d,a[n-1]+d) ; else if(count == 0 && d == 0) printf("1 %d ",a[0]) ; else if(count == 1 && (a[pos+1]-a[pos]) == 2*d) printf("1 %d ",a[pos]+d) ; else printf("0 ") ; } } return 0 ; }