codeforces#516 Div2---ABCD

A---Make a triangle!

http://codeforces.com/contest/1064/problem/A

题意：

给定三个整数表示三角形的边。每次给边长可以加一，问至少要加多少才能使这三个边成为一个三角形。

思路：

找到最大的边，然后最大边 + 1减剩下两条边就行了。负数的话就是0。

 1 #include<iostream>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<stdio.h>
 5 #include<cstring>
 6 #include<vector>
 7 #include<map>
 8 #include<set>
 9 #include<bits/stdc++.h>
10 
11 #define inf 0x3f3f3f3f
12 using namespace std;
13 typedef long long LL;
14 
15 int a, b, c;
16 
17 int main(){
18 
19     while(scanf("%d%d%d", &a, &b, &c) != EOF){
20         int m = max(a, b);
21         m = max(m, c);
22         int ans = 0;
23         if(m == a){
24             if(b + c > m){
25                 ans = 0;
26             }
27             else{
28                 ans = m + 1 - b - c;
29             }
30         }
31         else if(m == b){
32             if(a + c > m){
33                 ans = 0;
34             }
35             else{
36                 ans = m + 1 - a - c;
37             }
38         }
39         else{
40             if(a + b > m){
41                 ans = 0;
42             }
43             else{
44                 ans = m + 1 - a - b;
45             }
46         }
47         printf("%d
", ans);
48     }
49     return 0;
50 }

View Code

B---Equations of Mathematical Magic

http://codeforces.com/contest/1064/problem/B

题意：

给定一个a，使得a - (a ^ x) - x = 0.问能有多少的x。

思路：

如果a的某一位是1， x的这一位是1，那么a^x这一位是0，a-（a^x)-x这一位是0

如果a的某一位是1， x的这一位是0，那么a^x这一位是1，a-（a^x)-x这一位是0

如果a的某一位是0， x的这一位是1，那么a^x这一位是1，a-（a^x)-x这一位是1

如果a的某一位是0， x的这一位是0，那么a^x这一位是0，a-（a^x)-x这一位是0

所以统计一下a的1的个数

 1 #include<iostream>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<stdio.h>
 5 #include<cstring>
 6 #include<vector>
 7 #include<map>
 8 #include<set>
 9 #include<bits/stdc++.h>
10 
11 #define inf 0x3f3f3f3f
12 using namespace std;
13 typedef long long LL;
14 
15 int t;
16 LL a;
17 
18 int main(){
19 
20     while(scanf("%d", &t) != EOF){
21         for(int i = 0; i < t; i++){
22             scanf("%I64d", &a);
23             LL cnt = 1;
24             while(a){
25                 if(a & 1){
26                     cnt <<= 1;
27                 }
28                 a >>= 1;
29             }
30 
31             printf("%I64d
", cnt);
32         }
33 
34     }
35 
36 
37     return 0;
38 }

View Code

C---Oh Those Palindromes

http://codeforces.com/contest/1064/problem/C

题意：

给定一个字符串，使得他的是回文的子串数目最多，问应如何重新排列这个字符串。

思路：

让同一个字母都放在一起，输出就行了。sort一下就行，但是我竟然还统计了一下个数，蠢了。

 1 #include<iostream>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<stdio.h>
 5 #include<cstring>
 6 #include<vector>
 7 #include<map>
 8 #include<set>
 9 #include<bits/stdc++.h>
10 
11 #define inf 0x3f3f3f3f
12 using namespace std;
13 typedef long long LL;
14 
15 int n;
16 const int maxn = 1e5 + 5;
17 char str[maxn];
18 int cnt[30];
19 
20 
21 int main(){
22 
23     while(scanf("%d", &n) != EOF){
24         //scanf("%s", str);
25         cin>>str;
26         memset(cnt, 0, sizeof(cnt));
27         for(int i = 0; i < n; i++){
28             cnt[str[i] - 'a']++;
29         }
30         for(int i = 0; i < 26; i++){
31             for(int j = 0; j < cnt[i]; j++){
32                 printf("%c", i+'a');
33             }
34         }
35         printf("
");
36     }
37     return 0;
38 }

View Code

D---Labyrinth

http://codeforces.com/contest/1064/problem/D

题意：

一个n*m的格子，有的格子有障碍不能经过。现在从（r, c）处出发，向左最多只能走x次，向右最多走y次，问可以到达的格子有多少个。

思路：

最开始想的是dfs直接更新啥的。但是由于有先后顺序的问题，所以更新的时候左右的次数是不能直接减1的。需要用数组记录一下最大的左右次数。

而且如果发现vis过了这个格子就不更新了的话，也还是有先后顺序的问题。只有当经过这个格子的左右次数比原来大的时候才继续dfs更新这个格子。

但是这样dfs会T。

czc bfs过了，明天试一下....

先贴一下T了的代码。

 1 #include<iostream>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<stdio.h>
 5 #include<cstring>
 6 #include<vector>
 7 #include<map>
 8 #include<set>
 9 #include<bits/stdc++.h>
10 
11 #define inf 0x3f3f3f3f
12 using namespace std;
13 typedef long long LL;
14 
15 int n, m, r, c, x, y, cnt;
16 const int maxn = 2005;
17 bool vis[maxn][maxn];
18 int leftl[maxn][maxn], leftr[maxn][maxn];
19 int mvi[4] = {0, 0, 1, -1};
20 int mvj[4] = {1, -1, 0, 0};
21 bool g[maxn][maxn];
22 
23 
24 void dfs(int posi, int posj)
25 {
26     if(!vis[posi][posj]){
27         vis[posi][posj] = true;
28         //cout<<posi<<" "<< posj<<endl;
29         cnt++;
30     }
31     for(int k = 0; k < 4; k++){
32         int di = posi + mvi[k];
33         int dj = posj + mvj[k];
34         int mostl,mostr;
35         if(di > 0 && dj > 0 && di <= n && dj <= m && g[di][dj]){
36             if(k == 0){//向右
37                 mostr = leftr[posi][posj] - 1;
38                 mostl = leftl[posi][posj];
39                 if(mostr > leftr[di][dj] && mostr >= 0){
40                     leftr[di][dj] = mostr;
41                     leftl[di][dj] = mostl;
42                     dfs(di, dj);
43                 }
44             }
45             else if(k == 1){
46                 mostl = leftl[posi][posj] - 1;
47                 mostr = leftr[posi][posj];
48                 if(mostl > leftl[di][dj] && mostl >= 0){
49                     leftl[di][dj] = mostl;
50                     leftr[di][dj] = mostr;
51                     dfs(di, dj);
52                 }
53             }
54             else{
55                 mostl = leftl[posi][posj];
56                 mostr = leftr[posi][posj];
57                 if(mostl > leftl[di][dj]){
58                     leftl[di][dj] = mostl;
59                     leftr[di][dj] = mostr;
60                     dfs(di, dj);
61                 }
62             }
63         }
64     }
65 }
66 
67 int main(){
68 
69     while(scanf("%d%d", &n, &m) != EOF){
70         scanf("%d%d", &r, &c);
71         scanf("%d%d", &x, &y);
72         cnt = 0;
73         memset(vis, 0, sizeof(vis));
74         memset(leftr, -1, sizeof(leftr));
75         memset(leftl, -1, sizeof(leftl));
76 
77         for(int i = 1; i <= n; i++){
78             char str[maxn];
79             scanf("%s", str);
80             for(int j = 0; j < m; j++){
81                 if(str[j] == '*'){
82                     g[i][j + 1] = false;
83                 }
84                 else{
85                     g[i][j + 1] = true;
86                 }
87             }
88         }
89 
90         leftl[r][c] = x;
91         leftr[r][c] = y;
92         dfs(r, c);
93         printf("%d
", cnt);
94     }
95     return 0;
96 }

View Code

bfs写的 1A代码

  1 #include<iostream>
  2 #include<cmath>
  3 #include<algorithm>
  4 #include<stdio.h>
  5 #include<cstring>
  6 #include<vector>
  7 #include<map>
  8 #include<set>
  9 #include<bits/stdc++.h>
 10 
 11 #define inf 0x3f3f3f3f
 12 using namespace std;
 13 typedef long long LL;
 14 
 15 int n, m, r, c, x, y, cnt;
 16 const int maxn = 2005;
 17 bool vis[maxn][maxn];
 18 int leftl[maxn][maxn], leftr[maxn][maxn];
 19 int mvi[4] = {0, 0, 1, -1};
 20 int mvj[4] = {1, -1, 0, 0};
 21 bool g[maxn][maxn];
 22 
 23 
 24 void dfs(int posi, int posj)
 25 {
 26     if(!vis[posi][posj]){
 27         vis[posi][posj] = true;
 28         //cout<<posi<<" "<< posj<<endl;
 29         cnt++;
 30     }
 31     for(int k = 0; k < 4; k++){
 32         int di = posi + mvi[k];
 33         int dj = posj + mvj[k];
 34         int mostl,mostr;
 35         if(di > 0 && dj > 0 && di <= n && dj <= m && g[di][dj]){
 36             if(k == 0){//ÏòÓÒ
 37                 mostr = leftr[posi][posj] - 1;
 38                 mostl = leftl[posi][posj];
 39                 if(mostr > leftr[di][dj] && mostr >= 0){
 40                     leftr[di][dj] = mostr;
 41                     leftl[di][dj] = mostl;
 42                     dfs(di, dj);
 43                 }
 44             }
 45             else if(k == 1){
 46                 mostl = leftl[posi][posj] - 1;
 47                 mostr = leftr[posi][posj];
 48                 if(mostl > leftl[di][dj] && mostl >= 0){
 49                     leftl[di][dj] = mostl;
 50                     leftr[di][dj] = mostr;
 51                     dfs(di, dj);
 52                 }
 53             }
 54             else{
 55                 mostl = leftl[posi][posj];
 56                 mostr = leftr[posi][posj];
 57                 if(mostl > leftl[di][dj]){
 58                     leftl[di][dj] = mostl;
 59                     leftr[di][dj] = mostr;
 60                     dfs(di, dj);
 61                 }
 62             }
 63         }
 64     }
 65 }
 66 
 67 struct node{
 68     int i, j;
 69     node(){}
 70     node(int _i, int _j):i(_i), j(_j){}
 71 };
 72 
 73 void bfs()
 74 {
 75     queue<node>que;
 76     que.push(node(r, c));
 77     vis[r][c] = true;
 78     cnt = 1;
 79     while(!que.empty()){
 80         node now = que.front();
 81         que.pop();
 82         for(int k = 0; k < 4; k++){
 83             int di = now.i + mvi[k], dj = now.j + mvj[k];
 84             if(di > 0 && di <= n && dj > 0 && dj <= m && g[di][dj]){
 85                 /*if(!vis[di][dj]){
 86                     vis[di][dj] = true;
 87                     cnt++;
 88                 }*/
 89                 if(k == 0){
 90                     int mostl = leftl[now.i][now.j], mostr = leftr[now.i][now.j] - 1;
 91                     if(mostr >= 0 && !vis[di][dj]){
 92                         vis[di][dj] = true;
 93                         cnt++;
 94                     }
 95                     if(mostr >= 0 && mostr > leftr[di][dj]){
 96                         que.push(node(di, dj));
 97                         leftl[di][dj] = mostl;
 98                         leftr[di][dj] = mostr;
 99                     }
100                 }
101                 else if(k == 1){
102                     int mostl = leftl[now.i][now.j] - 1, mostr = leftr[now.i][now.j];
103                     if(mostl >= 0 && !vis[di][dj]){
104                         vis[di][dj] = true;
105                         cnt++;
106                     }
107                     if(mostl >= 0 && mostl > leftl[di][dj]){
108                         que.push(node(di, dj));
109                         leftl[di][dj] = mostl;
110                         leftr[di][dj] = mostr;
111                     }
112                 }
113                 else{
114                     int mostl = leftl[now.i][now.j], mostr = leftr[now.i][now.j];
115                     if(!vis[di][dj]){
116                         vis[di][dj] = true;
117                         cnt++;
118                     }
119                     if(mostl > leftl[di][dj]){
120                         que.push(node(di, dj));
121                         leftl[di][dj] = mostl;
122                         leftr[di][dj] = mostr;
123                     }
124                 }
125             }
126         }
127     }
128     printf("%d
", cnt);
129 }
130 
131 int main(){
132 
133     while(scanf("%d%d", &n, &m) != EOF){
134         scanf("%d%d", &r, &c);
135         scanf("%d%d", &x, &y);
136         cnt = 0;
137         memset(vis, 0, sizeof(vis));
138         memset(leftr, -1, sizeof(leftr));
139         memset(leftl, -1, sizeof(leftl));
140 
141         for(int i = 1; i <= n; i++){
142             char str[maxn];
143             scanf("%s", str + 1);
144             for(int j = 1; j <= m; j++){
145                 if(str[j] == '*'){
146                     g[i][j] = false;
147                 }
148                 else{
149                     g[i][j] = true;
150                 }
151             }
152         }
153 
154         leftl[r][c] = x;
155         leftr[r][c] = y;
156         bfs();
157         //cout<<"!"<<endl;
158         //dfs(r, c);
159         //printf("%d
", cnt);
160     }
161     return 0;
162 }

View Code

上了31分，ABC都卡了一下，C还RE了一发，还是太菜了啊。