codeforces 792A-D

先刷前四题，剩下的有空补。

题意：给出x 轴上的n 个点，问两个点之间的最短距离是多少，有多少个最短距离。

思路：排序后遍历。

代码：

 1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std;
 4 #define N 200005
 5 int w[N];
 6 int main(){
 7   int n;
 8   while(~scanf("%d", &n)){
 9     for(int i=0; i<n; i++){
10       scanf("%d", &w[i]);
11     }
12     sort(w, w+n);
13     int mint=w[1]-w[0], co=1;
14     for(int i=2; i<n; i++){
15       if(w[i]-w[i-1]<mint){
16         mint=w[i]-w[i-1];
17         co=1;
18       }
19       else if(w[i]-w[i-1]==mint) co++;
20     }
21     printf("%d %d
", mint, co);
22   }
23   return 0;
24 }

792A AC代码

792B Counting-out Rhyme

题意：1-n n个数围成一圈，初始位置为1，有m 个操作，每个操作给一个整数x，表示前进x 步后删去当前位置的数，再前进一步，输出每次操作删除的数

思路：模拟，用pos表示当前位置，循环m 次。注意得到x 后先取余当前剩余数量。

代码：

 1 #include<stdio.h>
 2 
 3 int main(){
 4   int n, m, x;
 5   while(~scanf("%d%d", &n, &m)){
 6     bool vis[110]={0}, flag=false;
 7     int pos=0, num=n;
 8     while(m--){
 9       scanf("%d", &x);
10       x=x%num;
11       while(x--){
12         do
13         {
14           pos++;
15           pos%=n;
16         }while(vis[pos]==1);
17       }
18       if(flag) printf(" ");
19       flag=true;
20       printf("%d", pos+1);
21       vis[pos]=1;
22       do
23       {
24         pos++;
25         pos%=n;
26       }while(vis[pos]==1);
27       num--;
28     }
29     printf("
");
30   }
31   return 0;
32 }

792B AC代码

792C Divide by Three

题意：给一个数，问最少删除多少位后可以被3 整除。

思路：

　　有一个大数取余要先理解。用sum 保存所有位和取余3 的结果。

　　如果sum==0，不需要删除；

　　如果sum==1，有可能删除一位1（取余后），有可能删除两位2；

　　如果sum==2，有可能删除一位2，有可能删除两位1。

　　写一个函数del（char *s, int k）表示从s 里删除一个数字k 并且去除前导0。接着几个if、else判断一下就可以了。

代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 void del(char *s, int k){
 4   int ls=strlen(s), i;
 5   for(i=ls-1; i>=0; i--){
 6     if((s[i]-'0')%3==k) break;
 7   }
 8   if(i==-1) return ;
 9   for(int j=i; j<ls; j++) s[j]=s[j+1];
10   if(s[0]==0){
11     s[0]='-';
12     s[1]='1';
13     s[2]=0;
14     return ;
15   }
16   for(i=0; s[i]; i++){
17     if(s[i]!='0') break;
18   }
19   if(s[i]==0) s[0]='0', s[1]=0;
20   else{
21     for(int j=i; j<ls; j++){
22       s[j-i]=s[j];
23     }
24   }
25 }
26 char s[100005], ts[100005];
27 int main(){
28   while(~scanf("%s", s)){
29     int sum=0;
30     for(int i=0; s[i]; i++){
31       sum+=s[i]-'0';
32       sum%=3;
33     }
34     if(sum==0) printf("%s
", s);
35     else{
36       int n1=0, n2=0;
37       for(int i=0; s[i]; i++){
38         if((s[i]-'0')%3==1) n1++;
39         else if((s[i]-'0')%3==2) n2++;
40       }
41       if(sum==1){
42         if(n2<2){
43           del(s, 1);
44           printf("%s
", s);
45         }
46         else if(n1==0){
47           del(s, 2);
48           del(s, 2);
49           printf("%s
", s);
50         }
51         else{
52           strcpy(ts, s);
53           int ls1, ls2;
54           del(ts, 1);
55           ls1=strlen(ts);
56           del(s, 2);
57           del(s, 2);
58           ls2=strlen(s);
59           if(ls1>ls2) printf("%s
", ts);
60           else printf("%s
", s);
61         }
62       }
63       else{
64         if(n2==0){
65           del(s, 1);
66           del(s, 1);
67           printf("%s
", s);
68         }
69         else if(n1<2){
70           del(s, 2);
71           printf("%s
", s);
72         }
73         else{
74           strcpy(ts, s);
75           int ls1, ls2;
76           del(ts, 1);
77           del(ts, 1);
78           ls1=strlen(ts);
79           del(s, 2);
80           ls2=strlen(s);
81           if(ls1>ls2) printf("%s
", ts);
82           else printf("%s
", s);
83         }
84       }
85     }
86   }
87   return 0;
88 }

792C AC代码

792D Paths in a Complete Binary Tree

题意：给一个n ，一个m ，n 表示有n 个结点的完整二叉树，m 表示m 个询问，每次询问给出初始结点编号和移动序列，问移动后的结点编号。（树结点编码依据中序遍历）

思路：

　　预处理+模拟。

　　可以先通过一个dfs找到初始位置的层数，这个dfs里面同时求出初始位置到根的路径（用于判断当前位置是父结点的左孩子或右孩子）。

　　接着根据初始位置的层数，先预处理一下移动序列，把不合理的操作去掉。（简化后续操作难度）

　　接着模拟当前位置变化即可。分三种情况处理即可（重点的子树结点数量可以通过当前层数求出）

代码：

  1 #include<stdio.h>
  2 #define LL long long
  3 
  4 int getNum(LL n){
  5   int ret=0;
  6   while(n){
  7     n>>=1;
  8     ret++;
  9   }
 10   return ret;
 11 }
 12 
 13 int dfs(LL l, LL r, LL p, bool *ss, int &ssp, int ceng){  // 确定初始位置的行
 14   LL mid=(l+r)/2;
 15   if(mid==p) return ceng;
 16   else if(mid>p){
 17     ss[ceng]=0;
 18     ssp=ceng;
 19     return dfs(l, mid-1, p, ss, ssp, ceng+1);
 20   }
 21   else{
 22     ss[ceng]=1;
 23     ssp=ceng;
 24     return dfs(mid+1, r, p, ss, ssp, ceng+1);
 25   }
 26 }
 27 
 28 void init(char *s, int rp, int num){
 29   int j=0;
 30   for(int i=0; s[i]; i++){
 31     if(s[i]=='L' || s[i]=='R'){
 32       if(rp==num);
 33       else{
 34         rp++;
 35         s[j++]=s[i];
 36       }
 37     }
 38     else{
 39       if(rp==1);
 40       else{
 41         rp--;
 42         s[j++]=s[i];
 43       }
 44     }
 45   }
 46   s[j]=0;
 47 }
 48 
 49 LL dp[100];
 50 LL solve(char *s, bool *ss, int ssp, LL p, int rp, int num){
 51   if(s[0]==0) return p;
 52   if(s[0]=='L'){
 53     LL ln=dp[num-rp]-1;
 54     p=p-ln+(ln-1)/2;
 55     rp++;
 56     ss[++ssp]=0;
 57   }
 58   else if(s[0]=='R'){
 59     LL rn=dp[num-rp]-1;
 60     p=p+1+(rn-1)/2;
 61     rp++;
 62     ss[++ssp]=1;
 63   }
 64   else{
 65     if(ss[ssp]==0){
 66       LL rn=dp[num-rp]-1;
 67       p=p+1+rn;
 68     }
 69     else{
 70       LL ln=dp[num-rp]-1;
 71       p=p-1-ln;
 72     }
 73     ssp--;
 74     rp--;
 75   }
 76 
 77   return solve(s+1, ss, ssp, p, rp, num);
 78 }
 79 
 80 char s[100005];
 81 bool ss[100];
 82 int main(){
 83   dp[0]=1;
 84   for(int i=1; dp[i-1]<=1e18; i++){
 85     dp[i]=dp[i-1]*2;
 86   }
 87   LL n, p;
 88   int m;
 89   while(~scanf("%I64d%d", &n, &m)){
 90     int num = getNum(n);
 91     while(m--){
 92       scanf("%I64d%s", &p, s);
 93       int ssp=1;
 94       int rp = dfs(1, n, p, ss, ssp, 1);
 95       init(s, rp, num);
 96 
 97       printf("%I64d
", solve(s, ss, ssp, p, rp, num));
 98     }
 99   }
100   return 0;
101 }

792D AC代码