https://vjudge.net/contest/149692#overview 这周一VJ比赛，题解&源码已完成！
A.........................................................................................
题目链接→Codeforces Problem 712A Memory and Crow
【题意】
有n个数b1, b2, ..., bn
a1, a2, ..., an是通过等式ai = bi - bi + 1 + bi + 2 - bi + 3....(±)bn得到的
现给你a1, a2, ..., an这n个数,问b1, b2, ..., bn是多少
详解请参看我的随笔！下面给出AC代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 int n,a,b; 6 while(cin>>n) 7 { 8 for(int i=1;i<=n;i++) 9 { 10 cin>>a; 11 if(i>1) 12 cout<<a+b<<" "; 13 b=a; 14 } 15 cout<<a<<endl; 16 } 17 return 0; 18 }
B.........................................................................................
题目链接→Codeforces Problem 708A Letters Cyclic Shift
【题意】
从仅有小写字母组成的字符串s中挑选出一个非空子串
将该子串中的每个字母均替换成前一个字母,如'b'换成'a','c'换成'b',以此类推,特别的,'a'要换成'z'
问经过一次转换之后,字典序最小的字符串s为多少
详解请参看我的随笔！下面给出AC代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 int i,k=0; 6 char s[100005]; 7 gets(s); 8 int len=strlen(s); 9 for(i=0;s[i]!='\0';i++) 10 if(s[i]!='a') 11 break; 12 for(;s[i]!='\0';i++) 13 { 14 if(s[i]=='a') 15 break; 16 s[i]--; 17 k++; 18 } 19 if(!k) 20 s[strlen(s)-1]='z'; 21 puts(s); 22 return 0; 23 }
C.........................................................................................
题目链接→Codeforces Problem 712B Memory and Trident
【题意】
Memory从二维坐标系的原点出发,按字符串s的指示运动
R:向右;L:向左;U:向上;D:向下
Memory最终想回到原点,问至少需要改变字符串s中的几个字符
若无论如何改变都无法回到原点,输出"-1"
详解请参看我的随笔！下面给出AC代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 char s[100005]; 6 int len; 7 int a=0,b=0,c=0,d=0; 8 while(gets(s)) 9 { 10 len=strlen(s); 11 if(len%2==1) 12 { 13 printf("-1\n"); 14 } 15 else 16 { 17 for(int i=0;s[i]!='\0';i++) 18 { 19 if(s[i]=='U') 20 a++; 21 else if(s[i]=='D') 22 b++; 23 else if(s[i]=='L') 24 c++; 25 else if(s[i]=='R') 26 d++; 27 } 28 printf("%d\n",(abs(a-b)+abs(c-d))/2); 29 a=b=c=d=0; 30 } 31 } 32 return 0; 33 }
D.........................................................................................
题目链接→Codeforces Problem 712C Memory and De-Evolution
【题意】
现有边长为x的等边三角形,Memory想要将其变成边长为y的等边三角形
现规定Memory每秒能够改变一条边的大小,但要保证改变后的三条边仍能构成一个三角形
问,最少需要多少时间才能变为边长为y的等边三角形
详解请参看我的随笔！下面给出AC代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 int s[3]; 6 int x,y,i; 7 while(cin>>x>>y) 8 { 9 int ans=0; 10 s[0]=s[1]=s[2]=y; 11 for(i=0;s[0]<x||s[1]<x||s[2]<x;i++) 12 { 13 s[0]=s[1]+s[2]-1; 14 sort(s,s+3); 15 ans++; 16 } 17 cout<<ans<<endl; 18 } 19 return 0; 20 }
E.........................................................................................
题目链接→http://poj.org/problem?id=2352
题意：
就是求每个小星星左小角的星星的个数。坐标按照Y升序，Y相同X升序的顺序给出
由于y轴已经排好序，可以按照x坐标建立一维树状数组
详解请参看我的随笔！下面给出AC代码：
1 #include <stdio.h> 2 #include <string.h> 3 const int MAXN=32005; 4 const int MINN=15005; 5 int tree[MAXN];//下标为横坐标 6 int level[MINN];//下标为等级数 7 /*int lowerbit(int x) 8 { 9 return x&-x; 10 }*/ 11 void add(int k,int num) 12 { 13 while(k<=MAXN) 14 { 15 tree[k]+=num; 16 k+=k&-k; 17 } 18 } 19 int read(int k)//1~k的区间和 20 { 21 int sum=0; 22 while(k) 23 { 24 sum+=tree[k]; 25 k-=k&-k; 26 } 27 return sum; 28 } 29 int main() 30 { 31 int n,x,y,i; 32 memset(tree,0,sizeof(tree)); 33 memset(level,0,sizeof(level)); 34 while(scanf("%d",&n)!=EOF) 35 { 36 for(i=1;i<=n;i++) 37 { 38 scanf("%d%d",&x,&y); 39 int temp=read(x+1);//加入x+1，是为了避免0，X是可能为0的 40 level[temp]++; 41 add(x+1,1); 42 } 43 for(i=0;i<n;i++) 44 printf("%d\n",level[i]); 45 } 46 return 0; 47 }
