codeforces专项

//专门用于记录日常刷的codeforces上面的题目

1.PawnChess(简单)

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <vector>
 5 #include <map>
 6 #include <set>
 7 #include <cstdio>
 8 #include <cstdlib>
 9 #include <cstring>
10 
11 using namespace std;
12 
13 char ch[10][10];
14 
15 int main()
16 {
17     for (int i = 0; i < 8; ++i)
18         scanf("%s", ch[i]);
19     int a = 10, b = 10;
20     for (int i = 0; i < 8; ++i)
21     {
22         for (int j = 0; j < 8; ++j)
23         {
24             if (ch[i][j] != '.')
25             {
26                 if (ch[i][j] == 'B')
27                 {
28                     int cnt = 0;
29                     int k;
30                     for (k = i+1; k < 8; ++k)
31                     {
32                         if (ch[k][j] != 'B' && ch[k][j] != 'W') cnt++;
33                         else break;
34                     }
35                     if (k == 8) b = min(b, cnt);
36                 }
37                 if (ch[i][j] == 'W')
38                 {
39                     int cnt = 0;
40                     int k;
41                     for (k = i-1; k >= 0; --k)
42                     {
43                         if (ch[k][j] != 'B' && ch[k][j] != 'W') cnt++;
44                         else break;    
45                     }    
46                     if (k < 0) a = min(a, cnt);
47                 }
48             }
49         }
50     }
51     puts(a > b ? "B" : "A");
52         
53     return 0;
54 }
View Code

 2.The Monster and the Squirrel(简单)

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <vector>
 5 #include <map>
 6 #include <set>
 7 #include <cstdio>
 8 #include <cstdlib>
 9 #include <cstring>
10 
11 using namespace std;
12 
13 int main()
14 {
15     int n;
16     scanf("%d", &n);
17     printf("%lld
", 1LL*(n-2)*(n-2));    
18     return 0;
19 }
View Code

 3.Super M(中等)

 1 //相当于建一颗包含所有重要的点，但是大小最小的虚树，然后再那个虚树里面找到字典序最小的直径
 2 //然后答案就是2*边长-直径长度就好了,做一下关于虚树的题
 3 #include <iostream>
 4 #include <string>
 5 #include <algorithm>
 6 #include <vector>
 7 #include <map>
 8 #include <set>
 9 #include <cstdio>
10 #include <cstdlib>
11 #include <cstring>
12 
13 using namespace std;
14 
15 const int maxn = 123500;
16 
17 int n, m, a, b;
18 vector<int> vec[maxn];
19 int attack[maxn];
20 int sizee[maxn];
21 int dis[maxn];
22 
23 void dfs(int p, int v)
24 {
25     sizee[v] = 0;
26     if (attack[v]) sizee[v] = 1;
27     for (int j = 0; j < vec[v].size(); ++j)
28     {
29         int u = vec[v][j];
30         if (u != p)
31         {
32             dis[u] = dis[v] + 1;
33             dfs(u, v);
34             sizee[v] += sizee[u];
35         }
36     }
37 }
38 
39 int main()
40 {
41     scanf("%d%d", &n, &m);
42     for (int i = 0; i < n-1; ++i)
43     {
44         scanf("%d%d", &a, &b);
45         a--, b--;
46         vec[a].push_back(b);
47         vec[b].push_back(a);        
48     }
49     for (int i = 0; i < m; ++i)
50     {
51         scanf("%d", &a);
52         attack[--a] = 1;
53     }
54     dfs(-1, 0);
55     int v = -1;
56     for (int i = 0; i < n; ++i)
57     {
58         if (attack[i] && (v == -1 || dis[i] > dis[v]))
59             v = i;
60     }
61     memset(dis, 0, sizeof(dis));
62     dfs(-1, v);
63     int sum = 0, mx = 0;
64     for (int i = 0; i < n; ++i)
65     {
66         if (sizee[i]>0 && m>sizee[i]) sum += 2;
67         if (attack[i]) mx = max(mx, dis[i]);
68     }
69     for (int i = 0; i < n; ++i)
70     {
71         if (dis[i] == mx && i < v && attack[i])
72         {
73             v = i;
74             break;
75         }
76     }
77     printf("%d
%d
", v+1, sum-mx);
78     
79     return 0;    
80 }
View Code

 4.Wizards' Duel(简单)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <string>
 6 #include <cstring>
 7 #include <vector>
 8 #include <list>
 9 #include <queue>
10 
11 using namespace std;
12 
13 int main()
14 {
15     double l, p, q;
16     scanf("%lf%lf%lf", &l, &p, &q);
17     printf("%lf
", p/(p+q)*l);
18 
19     return 0;
20 }
View Code

 5.Rebranding(简单)

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <vector>
 5 #include <map>
 6 #include <set>
 7 #include <cstdio>
 8 #include <cstdlib>
 9 #include <cstring>
10 
11 using namespace std;
12 
13 char ch[200010];
14 char dict[400];
15 
16 int main()
17 {
18     int n, m;
19     char c, d;
20     scanf("%d%d", &n, &m);
21     scanf("%s", ch);
22     for (int i = 'a'; i <= 'z'; ++i)
23         dict[i] = i;
24     for (int i = 0; i < m; ++i)
25     {
26         getchar();
27         scanf("%c %c", &c, &d);
28         for (int j = 'a'; j <= 'z'; ++j)
29         {
30             if (dict[j] == c) dict[j] = d;
31             else if (dict[j] == d) dict[j] = c;
32         }
33     }
34     for (int i = 0; i < n; ++i)
35         ch[i] = dict[ch[i]];
36     puts(ch);
37         
38     return 0;
39 }
View Code

 6.Median Smoothing(中等)

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <vector>
 5 #include <map>
 6 #include <set>
 7 #include <cstdio>
 8 #include <cstdlib>
 9 #include <cstring>
10 
11 using namespace std;
12 const int maxn = 500005;
13 
14 bool a[maxn];
15 int n;
16 
17 int main()
18 {
19     scanf("%d", &n);
20     for (int i = 1; i <= n; ++i)
21         scanf("%d", &a[i]);
22     int last = 1, ans = 0, l, r;
23     for (int i = 2; i <= n+1; ++i)
24     {
25         if (a[i]==a[i-1] || i==n+1)
26         {
27             ans = max(ans, (i-1-last)/2);
28             r = i-2, l = last+1;
29             while (l <= r)
30             {
31                 a[l++] = a[last];
32                 a[r--] = a[i-1];
33             }
34             last = i;
35         }
36     }
37     printf("%d
", ans);
38     for (int i = 1; i <= n; ++i)
39         printf("%d ", a[i]);
40         
41     return 0;
42 }
View Code

 7.Tricky Sum(简单)

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <vector>
 5 #include <map>
 6 #include <set>
 7 #include <cstdio>
 8 #include <cstdlib>
 9 #include <cstring>
10 
11 using namespace std;
12 
13 long long int pow(long long int a, long long int b)
14 {
15     long long int ans = 1;
16     for (int i = 0; i < b; ++i)
17         ans *= a;
18     return ans;
19 }
20 
21 int main()
22 {
23     int t;
24     scanf("%d", &t);
25     while (t--)
26     {
27         long long int n, ans, t = 1;
28         
29         scanf("%I64d", &n);
30         ans = (1+n)*n/2;
31         int i = 0;
32         while (t <= n) 
33         {
34             t *= 2;
35             i++;
36         }
37         ans -= 2LL*(1-pow(2,i))/(-1);
38         printf("%I64d
", ans);
39     }
40     return 0;
41 }
View Code

8.Queries on a String(简单)

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <vector>
 5 #include <map>
 6 #include <set>
 7 #include <cstdio>
 8 #include <cstdlib>
 9 #include <cstring>
10 
11 using namespace std;
12 
13 char ch[10010];
14 char ch1[10010];
15 int len;
16 
17 void work(int l, int r, int k)
18 {
19     for (int i = 0; i <= r-l; ++i)
20     {
21         if (i+k+l > r) ch1[i+k+l-r-1+l] = ch[i+l];
22         else ch1[i+l+k] = ch[l+i];
23     }
24     for (int i = 0; i <= r-l; ++i)
25         ch[i+l] = ch1[i+l];
26 }
27 
28 int main()
29 {
30     scanf("%s", ch);
31     len = strlen(ch);
32     int m;
33     scanf("%d", &m);
34     int l, r, k;
35     for (int i = 0; i < m; ++i)
36     {
37         scanf("%d%d%d", &l, &r, &k);
38         l -=1, r -= 1;
39         k = k%(r-l+1);
40         work(l, r, k);          
41     }   
42     puts(ch);
43         
44     return 0;
45 }
View Code

9.Igor In the Museum(简单)

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <vector>
 5 #include <map>
 6 #include <set>
 7 #include <queue>
 8 #include <cstdio>
 9 #include <cstdlib>
10 #include <cstring>
11 #include <cmath>
12 #define PI 3.141592654
13 #define MAXN 1010
14 using namespace std;
15 
16 int vis[MAXN][MAXN];
17 int pos[MAXN][MAXN];
18 int ans[MAXN*MAXN];
19 char ch[MAXN][MAXN];
20 int n, m, k;
21 int cnt;
22 int dir1[] = {1, 0, -1, 0};
23 int dir2[] = {0, 1, 0, -1};
24 
25 void work(int x, int y)
26 {
27     queue<pair<int, int>> qu;
28     while (!qu.empty()) qu.pop();
29     qu.push(make_pair(x, y));
30     cnt++;
31     pos[x][y] = cnt;
32     vis[x][y] = 1;
33     int s = 0;
34     while (!qu.empty())
35     {
36         x = qu.front().first;
37         y = qu.front().second;
38         qu.pop();
39         pos[x][y] = cnt;
40         for (int i = 0; i < 4; ++i)
41         {
42             int xx = x+dir1[i];
43             int yy = y+dir2[i];
44             if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
45             if (!vis[xx][yy] && ch[xx][yy] == '.')
46             {
47                 qu.push(make_pair(xx, yy));
48                 vis[xx][yy] = 1;
49             }
50             if (ch[xx][yy] == '*') s++;
51         }
52     }
53     ans[cnt] = s;
54 }
55 
56 int main()
57 {
58     cnt = -1;
59     scanf("%d%d%d", &n, &m, &k);
60     for (int i = 0; i < n; ++i)
61         scanf("%s", ch[i]);
62     for (int i = 0; i < n; ++i)
63         for (int j = 0; j < m; ++j)
64             if (!vis[i][j] && ch[i][j] == '.') work(i, j);
65     int x, y;
66     for (int i = 0; i < k; ++i)
67     {
68         scanf("%d%d", &x, &y);
69         if (ch[x-1][y-1] == '*') puts("0");
70         else printf("%d
", ans[pos[x-1][y-1]]);
71     }
72     return 0;
73 }
View Code

 10.Wilbur and Swimming Pool

 1 #include <cstdio>
 2 #include <string>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <ctime>
 6 #include <queue>
 7 
 8 using namespace std;
 9 
10 int main()
11 {
12     int n, ans;
13     int a[4], b[4];
14     scanf("%d", &n);
15     for (int i = 0; i < n; ++i)
16     {
17         scanf("%d%d", &a[i], &b[i]);
18     }
19     if (n == 1) ans = -1;
20     else if (n == 2)
21     {
22         ans = abs(a[1]-a[0])*(abs(b[1]-b[0]));
23     }
24     else if (n == 3)
25     {
26         int x, y;
27         if (a[0] == a[1]) x = a[2]-a[0];
28         else x = a[1]-a[0];
29         if (b[0] == b[1]) y = b[2]-b[1];
30         else y = b[1]-b[0];
31         ans = abs(x*y);
32     }
33     else
34     {
35         int x, y;
36         if (a[0] == a[1])
37         {
38             x = a[2]-a[1];    
39         }
40         else x = a[1]-a[0];
41         if (b[0] == b[1]) y = b[2]-b[1];
42         else y = b[1]-b[0];
43         ans = abs(x*y);
44     }
45     if (ans == 0) ans = -1;
46     printf("%d
", ans);
47     return 0;
48 }
View Code

 11.Wilbur and Array

 1 #include <cstdio>
 2 #include <string>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <ctime>
 6 #include <queue>
 7 
 8 using namespace std;
 9 
10 int main()
11 {
12     int n, b;
13     int val = 0;
14     long long int ans = 0;
15     scanf("%d", &n);
16     for (int i = 0; i < n; ++i)
17     {
18         scanf("%d", &b);
19         ans += abs(b-val);
20         val = b;
21     }    
22     printf("%I64d
", ans);
23     
24     return 0;
25 }
View Code

 12.Wilbur and Points

 1 #include <cstdio>
 2 #include <string>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <ctime>
 6 #include <queue>
 7 #include <set>
 8 #include <vector>
 9 
10 using namespace std;
11 
12 struct node
13 {
14     int x, y, val;    
15 };
16 
17 struct node1
18 {
19     int val, idx;
20 };
21 
22 int cmp(node& a, node& b)
23 {
24     return a.val-b.val;     
25 }
26 
27 int cmp1(node1& a, node1& b)
28 {
29     return a.val - b.val;
30 }
31 int ans[100010][2];
32 
33 int main()
34 {
35     vector<node> v;
36     int n, x, y;
37     scanf("%d", &n);
38     for (int i = 0; i < n; ++i)
39     {
40         scanf("%d%d", &x, &y);
41         node nd;
42         nd.x = x, nd.y = y, nd.val = y-x;
43         v.push_back(nd);
44     }
45     vector<node1> w;
46     for (int i = 0; i < n; ++i)
47     {
48         scanf("%d", &x);
49         node1 nd;
50         nd.val = x, nd.idx = i; 
51         w.push_back(nd);
52     }
53     sort(v.begin(), v.end(), cmp);
54     sort(w.begin(), w.end(), cmp1);
55     bool flag = true;
56     for (int i = 0; flag && i < n; ++i)            
57     {
58         if (v[i].val == w[i].val)
59         {
60             ans[w[i].idx][0] = v[i].x;
61             ans[w[i].idx][1] = v[i].y;
62         }
63         else flag = false;
64     }
65     if (flag)
66     {
67         puts("YES");
68         for (int i = 0; i < n; ++i)
69             printf("%d %d
", ans[i][0], ans[i][1]);
70     }
71     else puts("NO");
72     
73     return 0;    
74 }
View Code

 13.Patrick and Shopping

 1 #include <cstdio>
 2 #include <string>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <ctime>
 6 #include <queue>
 7 #include <set>
 8 #include <vector>
 9 
10 using namespace std;
11 
12 int main()
13 {
14     int d1, d2, d3;
15 
16     scanf("%d%d%d", &d1, &d2, &d3);
17 
18     int s1 = d1*2+d2*2;
19     int s2 = d1 + d2 + d3;
20     int s3 = d1 + d3 + d3 + d1;
21     int s4 = d2 + d3 + d2 + d3;
22 
23     printf("%d
", min(min(s1, s2), min(s3, s4)));
24 
25     return 0;
26 }
View Code

14.Spongebob and Joke

 1 #include <cstdio>
 2 #include <string>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <ctime>
 6 #include <queue>
 7 #include <set>
 8 #include <vector>
 9 #include <map>
10 
11 using namespace std;
12 
13 int vis[100010];
14 
15 int main()
16 {
17     int n, m;
18     scanf("%d%d", &n, &m);
19     vector<int> b, f;
20     f.clear(), b.clear();
21     int tmp = 0;
22     for (int i = 0; i < n; ++i)
23     {
24         scanf("%d", &tmp);
25         f.push_back(tmp);
26         vis[tmp]++;
27     }
28     for (int i = 0; i < m; ++i)
29     {
30         scanf("%d", &tmp);
31         b.push_back(tmp);
32     }
33     bool flag1 = true, flag2 = true;
34     for (int i = 0; i < m; ++i)
35     {
36         tmp = b[i];
37         if (vis[tmp] == 0)
38         {
39             flag1 = false;
40             break;
41         }
42         else if (vis[tmp] > 1) flag2 = false;
43     }
44     if (flag1)
45     {
46         if (!flag2) puts("Ambiguity");
47         else
48         {
49             puts("Possible");
50             for (int i = 0; i < n; ++i)
51                 vis[f[i]] = i+1;
52             for (int i = 0; i < m; ++i)
53             {
54                 if (i != 0) printf(" ");
55                 tmp = b[i];
56                 printf("%d", vis[tmp]);
57             }
58             puts("");
59         }
60     }
61     else puts("Impossible");
62     return 0;
63 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/JustForCS/p/4937407.html