CODEFORCES-PROBLEMSET

悠悠 2021-12-24 03:43 264阅读 0赞

[1A][]

水题 然而看不仔细爆int了

c++

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 int main(){
     5     double n, m, a;
     6     cin >> n >> m >> a;
     7     ll ans = ll(ceil(n / a)) * ll(ceil(m / a));
     8     cout << ans << endl;
     9     return 0;
    10 }

py3

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 import math
    2 t = input().split()
    3 n, m, a = map(int, t)
    4 print(int(math.ceil(n / a) * math.ceil(m / a)))

[1B][]

有毒的模拟水题......

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 int main(){
     5     int n;
     6     cin >> n;
     7     while(n--){
     8         string s;
     9         cin >> s;
    10         bool flag = false;
    11         int i = 0;
    12         while(i < s.size() && 'A' <= s[i] && s[i] <= 'Z') ++i;
    13         for(; i < s.size(); ++i){
    14             if('A' <= s[i] && s[i] <= 'Z'){
    15                 flag = true;
    16                 break;
    17             }
    18         }
    19         if(flag){
    20             int c = 0;
    21             int index = s.find('C');
    22             string ans = "";
    23             for(int i = index + 1; i < s.size(); ++i) c = 10 * c + s[i] - '0';
    24             while(c){
    25                 int k = c % 26;
    26                 if(k == 0){
    27                     ans += 'Z';
    28                     --c;
    29                 }
    30                 else ans += ('A' + k - 1);
    31                 c /= 26;
    32             }
    33             reverse(ans.begin(), ans.end());
    34             cout << ans << s.substr(1, index-1) << endl;
    35         }
    36         else{
    37             int index = 0;
    38             string ans = "R";
    39             int r = 0;
    40             for(; index < s.size(); ++index){
    41                 if('0' <= s[index] && s[index] <= '9') break;
    42                 r = 26 * r + (s[index] - 'A' + 1);
    43             }
    44             ans += s.substr(index, s.size());
    45             ans += 'C';
    46             cout << ans << r << endl;
    47         }
    48     }
    49     return 0;
    50 }

[1C][]

mdzz。。。

余弦定理求三角形内角，也是圆上的圆周角，乘以2得圆心角

求三圆心角最大公约数得正多边形每一份的圆心角ang，2\*pi/ang得出边数n

海伦公式+正弦定理得三角形外接圆半径r = (a \* b \* c) / (4 \* s)

s = n \* r \* r \* sin(ang) / 2

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 const double eps = 1e-2;
     4 double fgcd(double a, double b){
     5      if (fabs(a) < eps)
     6          return b;
     7      if (fabs(b) < eps)
     8          return a;
     9      return fgcd(b, fmod(a, b));
    10 }
    11 double diameter(double a, double b, double c) {
    12     double p = (a + b + c) / 2;
    13     double s = sqrt(p * (p - a) * (p - b) * (p - c));
    14     return a * b * c / (4 *s);
    15 }
    16 int main() {
    17     double x[3], y[3], line[3];
    18     for(int i = 0; i < 3; ++i) scanf("%lf %lf", &x[i], &y[i]);
    19     for(int i = 0; i < 3; ++i)
    20         line[i] = sqrt((x[i] - x[(i+1)%3]) * (x[i] - x[(i+1)%3]) + (y[i] - y[(i+1)%3]) * (y[i] - y[(i+1)%3]));
    21     double r = diameter(line[0], line[1], line[2]);
    22     double angle[3];
    23     for(int i = 0; i < 2; ++i)
    24         angle[i] = acos(1 - line[i] * line[i] / (2 * r * r));
    25     angle[2] = 2 * acos(-1) - angle[0] - angle[1];
    26     double ang = fgcd(angle[0], fgcd(angle[1], angle[2]));
    27     printf("%.6f\n", r * r * sin(ang) / 2 * (2 * acos(-1) / ang));
    28     return 0;
    29 }

[2A][]

模拟水题 略麻烦(说到底是思路不清淅不严谨+弱)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 struct info{
     5     string name;
     6     int score;
     7 }aaa[1111];
     8 map<string, int> game;
     9 int main(){
    10     int n;
    11     cin >> n;
    12     string name, ans;
    13     int score;
    14     for(int i = 0; i < n; ++i){
    15         cin >> name >> score;
    16         aaa[i].name = name;
    17         aaa[i].score = score;
    18         game[name] += score;
    19     }
    20     int maxScore = -1;
    21     for(int i = 0; i < n; ++i) maxScore = max(maxScore, game[aaa[i].name]);
    22     map<string, int> tmp;
    23     for(int i = 0; i < n; ++i){
    24         if(game[aaa[i].name] < maxScore) continue;
    25         tmp[aaa[i].name] += aaa[i].score;
    26         if(tmp[aaa[i].name] >= maxScore){
    27             ans = aaa[i].name;
    28             break;
    29         }
    30     }
    31     cout << ans << endl;
    32     return 0;
    33 }

[2B][]

然后就2B了.....

求2最少几个5最少几个然后min(num\_two, num\_five)就是答案 剩下输出路径

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 int matrix[1111][1111][2];
     5 int dp[1111][1111][2];
     6 int step[1111][1111][2];
     7 
     8 void print(int nx, int ny, int k){
     9     if(nx == 1 && ny == 1) return ;
    10     if(step[nx][ny][k]){
    11         print(nx-1, ny, k);
    12         printf("D");
    13     }
    14     else{
    15         print(nx, ny-1, k);
    16         printf("R");
    17     }
    18 }
    19 int main(){
    20     int n;
    21     scanf("%d", &n);
    22     int zerox = 0, zeroy = 0;
    23     for(int i = 1; i <= n; ++i){
    24         for(int j = 1; j <= n; ++j){
    25             int k;
    26             scanf("%d", &k);
    27             if(k == 0){
    28                 zerox = i;
    29                 zeroy = j;
    30                 continue;
    31             }
    32             int numtwo = 0, numfive = 0;
    33             while(!(k & 1)){
    34                 ++numtwo;
    35                 k >>= 1;
    36             }
    37             while(k % 5 == 0){
    38                 ++numfive;
    39                 k /= 5;
    40             }
    41             matrix[i][j][0] = numtwo;
    42             matrix[i][j][1] = numfive;
    43         }
    44     }
    45     memset(dp, 0x3f, sizeof(dp));
    46     dp[1][1][0] = matrix[1][1][0];
    47     dp[1][1][1] = matrix[1][1][1];
    48     for(int i = 1; i <= n; ++i){
    49         for(int j = 1; j <= n; ++j){
    50             if(i == 1 && j == 1) continue;
    51             for(int k = 0; k < 2; ++k){
    52                 dp[i][j][k] = matrix[i][j][k] + min(dp[i-1][j][k], dp[i][j-1][k]);
    53                 if(dp[i-1][j][k] < dp[i][j-1][k]) step[i][j][k] = 1;
    54             }
    55         }
    56     }
    57     int ans = min(dp[n][n][0], dp[n][n][1]);
    58     if(ans == 0) puts("0");
    59     else if(zerox && zeroy){
    60         puts("1");
    61         int nx = 1, ny = 1;
    62         while(nx < zerox) ++nx, printf("D");
    63         while(ny < zeroy) ++ny, printf("R");
    64         while(nx < n) ++nx, printf("D");
    65         while(ny < n) ++ny, printf("R");
    66         return 0;
    67     }
    68     else printf("%d\n", ans);
    69     int k = dp[n][n][0] < dp[n][n][1] ? 0 : 1;
    70     print(n, n, k);
    71     return 0;
    72 }

[2C][]

模拟退火 先放着

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <cmath>
     2 #include <cstdio>
     3 #include <cstdlib>
     4 #include <cstring>
     5 #include <iostream>
     6 #include <algorithm>
     7 using namespace std;
     8 typedef long long ll;
     9 #define _pow(a) ((a)*(a))
    10 const double eps = 1e-6;
    11 
    12 struct circle{ double x, y, r; }c[3];
    13 double angle[3];
    14 int cx[] = {
          0, 0, 1, -1}, cy[] = {
          1, -1, 0, 0};
    15 
    16 double dis(double x1, double y1, double x2, double y2){
    17     return sqrt(_pow(x1 - x2) + _pow(y1 - y2));
    18 }
    19 
    20 double calc(double x, double y){
    21     for(int i = 0; i < 3; ++i) angle[i] = dis(x, y, c[i].x, c[i].y) / c[i].r;
    22     double value = 0;
    23     for(int i = 0; i < 3; ++i) value += _pow(angle[i] - angle[(i + 1) % 3]);
    24     return value;
    25 }
    26 
    27 int main(){
    28     double x = 0, y = 0;
    29     for(int i = 0; i < 3; ++i){
    30         scanf("%lf %lf %lf", &c[i].x, &c[i].y, &c[i].r);
    31         x += c[i].x / 3.0;
    32         y += c[i].y / 3.0;
    33     }
    34     double deviation = calc(x, y);
    35     double step = 1;
    36     for(int i = 0; i <= 1e5; ++i){
    37         bool flag = false;
    38         double xx, yy;
    39         for(int j = 0; j < 4; ++j){
    40             double nx = x + cx[j] * step, ny = y + cy[j] * step;
    41             double nDeviation = calc(nx, ny);
    42             if(nDeviation < deviation){
    43                 deviation = nDeviation;
    44                 flag = true;
    45                 xx = nx;
    46                 yy = ny;
    47             }
    48         }
    49         if(flag){
    50             x = xx;
    51             y = yy;
    52         }
    53         else step /= 2.0;
    54     }
    55     if(deviation <= eps) printf("%.5f %.5f\n", x, y);
    56     return 0;
    57 }

[3A][]

水题 但是大神的代码总是让我amazing，简单清晰直接

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 int main(){
     5     char s[3], t[3];
     6     scanf("%s %s", s, t);
     7     int a = s[0] - t[0], b = s[1] - t[1];
     8     char c = a > 0 ? 'L' : (a = -a, 'R');
     9     char d = b > 0 ? 'D' : (b = -b, 'U');
    10     printf("%d", a > b ? a : b);
    11     while(a || b){
    12         puts("");
    13         if(a) --a, putchar(c);
    14         if(b) --b, putchar(d);
    15     }
    16     return 0;
    17 }

[3B][]

分开按capacity排序 再维护前缀和 再枚举space为1的船的数量

代码好丑...........

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 struct vihecle{
     5     int id;
     6     int cpa;
     7 }p1[111111], p2[111111];
     8 int presum1[111111], presum2[111111];
     9 
    10 bool cmp(vihecle a, vihecle b){
    11     return a.cpa > b.cpa;
    12 }
    13 
    14 int main(){
    15     int n, v;
    16     cin >> n >> v;
    17     int i1 = 0, i2 = 0;
    18     presum1[0] = presum2[0] = 0;
    19     for(int i = 0; i < n; ++i){
    20         int t, pp;
    21         cin >> t >> pp;
    22         if(t == 1){
    23             p1[i1].cpa=pp;
    24             p1[i1++].id=i+1;
    25         }
    26         else{
    27             p2[i2].cpa=pp;
    28             p2[i2++].id=i+1;
    29         }
    30     }
    31     sort(p1, p1 + i1, cmp);
    32     sort(p2, p2 + i2, cmp);
    33     for(int i = 1; i <= i1; ++i) presum1[i] = presum1[i-1] + p1[i-1].cpa;
    34     for(int i = 1; i <= i2; ++i) presum2[i] = presum2[i-1] + p2[i-1].cpa;
    35     int ans = 0, ii1 = 0, ii2 = 0;
    36     for(int i = 0; i <= i1; ++i){
    37         if(i > v) break;
    38         int tmp = presum1[i] + presum2[min((v-i)/2, i2)];
    39         if(tmp > ans){
    40             ans = tmp;
    41             ii1 = i;
    42             ii2 = min((v - i) / 2, i2);
    43         }
    44     }
    45     cout << ans << endl;
    46     for(int i = 0; i < ii1; ++i) cout << p1[i].id << " ";
    47     for(int i = 0; i < ii2; ++i) cout << p2[i].id << " ";
    48     return 0;
    49 }

[3C][]

恶心的模拟..........讲真......玩起来容易写起来恶心.......

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 char g[5][5];
     5 int c1, c2;
     6 bool f1, f2;
     7 
     8 int main(){
     9     for(int i = 0; i < 3; ++i) scanf("%s", g[i]);
    10     c1 = c2 = 0;
    11     f1 = f2 = false;
    12 
    13     for(int i = 0; i < 3; ++i)
    14         if(g[i][0] == g[i][1] && g[i][1] == g[i][2])
    15             if(g[i][0] == 'X') f1 = true;
    16             else if(g[i][0] == '0') f2 = true;
    17     for(int i = 0; i < 3; ++i)
    18         if(g[0][i] == g[1][i] && g[1][i] == g[2][i])
    19             if(g[0][i] == 'X') f1 = true;
    20             else if(g[0][i] == '0') f2 = true;
    21     if(g[0][0] == g[1][1] && g[1][1] == g[2][2])
    22         if(g[0][0] == 'X') f1 = true;
    23         else if(g[0][0] == '0') f2 = true;
    24     if(g[0][2] == g[1][1] && g[1][1] == g[2][0])
    25         if(g[1][1] == 'X') f1 = true;
    26         else if(g[1][1] == '0') f2 = true;
    27 
    28     for(int i = 0; i < 3; ++i)
    29         for(int j = 0; j < 3; ++j)
    30             if(g[i][j] == 'X') ++c1;
    31             else if(g[i][j] == '0') ++c2;
    32     if(c1 == c2 || c1 == c2 + 1){
    33         if(f1 && f2) puts("illegal");
    34         else if(f1 && !f2){
    35             if(c1 == c2 + 1) puts("the first player won");
    36             else puts("illegal");
    37         }
    38         else if(!f1 && f2){
    39             if(c1 == c2) puts("the second player won");
    40             else puts("illegal");
    41         }
    42         else{
    43             if(c1 + c2 == 9) puts("draw");
    44             else if(c1 + c2 < 9){
    45                 if(c1 == c2) puts("first");
    46                 else if(c1 == c2 + 1) puts("second");
    47             }
    48             else puts("illegal");
    49         }
    50     }
    51     else puts("illegal");
    52     return 0;
    53 }

[3D][]

对于处理中每一个过程都有'('不少于')'，将'?'置为')'，若'('少于')'则在前面的'?'中拿出转换价值最小的进行转换

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 
     5 int main(){
     6     string s;
     7     cin >> s;
     8     ll cnt = 0, ans = 0;
     9     priority_queue<pair<int, int> > q;
    10     for(int i = 0; i < s.size(); ++i){
    11         if(s[i] == '(') ++cnt;
    12         else if(s[i] == ')') --cnt;
    13         else{
    14             int a, b;
    15             cin >> a >> b;
    16             ans += b;
    17             --cnt;
    18             s[i] = ')';
    19             q.push(make_pair(b - a, i));
    20         }
    21         if(cnt < 0){
    22             if(q.empty()) break;
    23             pair<int, int> p = q.top();
    24             q.pop();
    25             ans -= p.first;
    26             s[p.second] = '(';
    27             cnt += 2;
    28         }
    29     }
    30     if(cnt) cout << "-1" << endl;
    31     else cout << ans << endl << s << endl;
    32     return 0;
    33 }

[4A][]

超级水......

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
    2 using namespace std;
    3 
    4 int main(){
    5     int n;
    6     cin >> n;
    7     cout << (((n & 1) || n == 2) ? "NO" : "YES") << endl;
    8     return 0;
    9 }

[4B][]

水，随便贪一下

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 struct {
     5     int mini, maxi;
     6 }p[33];
     7 
     8 int main(){
     9     int d, maxSum;
    10     cin >> d >> maxSum;
    11     int totalMin = 0, totalMax = 0;
    12     for(int i = 0; i < d; ++i) cin >> p[i].mini >> p[i].maxi, totalMin += p[i].mini, totalMax += p[i].maxi;
    13     if(totalMin > maxSum || totalMax < maxSum)
    14         cout << "NO" << endl;
    15     else{
    16         cout << "YES" << endl;
    17         int t = maxSum - totalMin;
    18         for(int i = 0; i < d; ++i){
    19             int ansi = p[i].mini;
    20             if(t){
    21                 ansi = min(p[i].maxi, ansi + t);
    22                 t -= (ansi - p[i].mini);
    23             }
    24             cout << ansi << " \n"[i == d-1];
    25         }
    26     }
    27     return 0;
    28 }

[4C][]

水，输入保证只有小写字母，map水过

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 int main(){
     5     int n;
     6     cin >> n;
     7     map<string, int> name;
     8     while(n--){
     9         string s;
    10         cin >> s;
    11         if(name[s] == 0) cout << "OK" << endl;
    12         else cout << s << name[s] << endl;
    13         ++name[s];
    14     }
    15     return 0;
    16 }

[4D][]

n^2的暴力dp.......

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 int n;
     5 struct env{
     6     int w, h;
     7 }p[5555];
     8 int dp[5555], pre[5555];
     9 
    10 int dfs(int k){
    11     if(dp[k]) return dp[k];
    12     for(int i = 1; i <= n; ++i){
    13         if(p[k].w < p[i].w && p[k].h < p[i].h){
    14             if(dfs(i) + 1 > dp[k]){
    15                 pre[k] = i;
    16                 dp[k] = dfs(i) + 1;
    17             }
    18         }
    19     }
    20     return dp[k];
    21 }
    22 
    23 int main(){
    24     cin >> n;
    25     for(int i = 0; i <= n; ++i)
    26         cin >> p[i].w >> p[i].h;
    27     cout << dfs(0) << endl;
    28     for(int i = pre[0]; i > 0; i = pre[i]) cout << i << " ";
    29     cout << endl;
    30     return 0;
    31 }

[5A][]

水

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 int main(){
     5     string s;
     6     int ans = 0, member = 0;
     7     while(getline(cin, s)){
     8         if(s[0] == '+') ++member;
     9         else if(s[0] == '-') --member;
    10         else{
    11             int len = s.end() - find(s.begin(), s.end(), ':') - 1;
    12             ans += member * len;
    13         }
    14     }
    15     cout << ans << endl;
    16     return 0;
    17 }

[5B][]

一眼样例明白大概但是奇数的情况要交替........

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 int main(){
     5     vector<string> v;
     6     string s;
     7     int len = 0;
     8     while(getline(cin, s)){
     9         v.push_back(s);
    10         len = max(len, int(s.size()));
    11     }
    12     cout << string(len+2, '*') << endl;
    13     int k = -1;
    14     for(vector<string>::iterator i = v.begin(); i != v.end(); ++i){
    15         int l = len - (*i).size();
    16         string fr = string(floor(double(l)/2), ' '), ba = string(ceil(double(l)/2), ' ');
    17         if(l & 1){
    18             if(!k) cout << "*" << ba << *i << fr << "*" << endl;
    19             else cout << "*" << fr << *i << ba << "*" << endl;
    20             k = ~k;
    21         }
    22         else cout << "*" << fr << *i << ba << "*" << endl;
    23     }
    24     cout << string(len+2, '*') << endl;
    25     return 0;
    26 }

[5C][]

dp，让我智障好久的题........

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 const int maxn = 1e6 + 7;
     5 int dp[maxn];
     6 
     7 int main(){
     8     ios::sync_with_stdio(false);
     9     memset(dp, 0, sizeof(dp));
    10     string s;
    11     cin >> s;
    12     stack<int> pos;
    13     while(!pos.empty()) pos.pop();
    14     int len = 0, sum = 1;
    15     for(int i = 0; i < s.size(); ++i){
    16         if(s[i] == '(') pos.push(i);
    17         else if(!pos.empty()){
    18             int j = pos.top();
    19             pos.pop();
    20             int tmpSize = i - j + 1;
    21             dp[i] = tmpSize + (j ? dp[j-1] : 0);
    22             if(dp[i] > len){
    23                 len = dp[i];
    24                 sum = 1;
    25             }
    26             else if(dp[i] == len) ++sum;
    27         }
    28     }
    29     cout << len << " " << sum << endl;
    30     return 0;
    31 }

[5D][]

运动学卧槽......放弃

分类还是渣的不成样子.....

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 const double eps = 1e-8;
     5 double a, v, l, d, w, t1, t2, vd, vt, r;
     6 
     7 int fcmp(double x){
     8     if(fabs(x) < eps) return 0;
     9     else return x < 0 ? -1 : 1;
    10 }
    11 
    12 int main(){
    13     scanf("%lf %lf %lf %lf %lf", &a, &v, &l, &d, &w);
    14     vt = sqrt(w * w / 2 + a * d);
    15     r = l - d;
    16     if(fcmp(d - v * v / 2 / a) <= 0 && fcmp(sqrt(2 * a * d) - w) <= 0){
    17         t1 = sqrt(2 * d / a);
    18         vd = sqrt(2 * a * d);
    19     }
    20     else if(fcmp(d - v * v / 2 / a) >= 0 && fcmp(w - v) >= 0){
    21         t1 = d / v + v / 2 / a;
    22         vd = v;
    23     }
    24     else if(fcmp(v - vt) >= 0 && fcmp(vt - w) >= 0){
    25         t1 = (2 * vt - w) / a;
    26         vd = w;
    27     }
    28     else{
    29         t1 = d / v + (2 * v - w) / a - (2 * v * v - w * w) / 2 / a / v;
    30         vd = w;
    31     }
    32     if(fcmp(r - (v * v - vd * vd) / 2 / a) >= 0)
    33         t2 = r / v + (v - vd) / a - (v * v - vd * vd) / 2 / a / v;
    34     else
    35         t2 = (sqrt(2 * a * r + vd * vd) - vd) / a;
    36     printf("%.10f\n", t1 + t2);
    37     return 0;
    38 }

[5E][]

找每个点左右分别严格高于这个点的点，有点像并查集的样子

还需要找处在中间的相同高度的点

每个点与左右两个高点及相同高度的点可以互相看到

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 
     5 const int maxn = 1e6 + 7;
     6 int height[maxn], l[maxn], r[maxn], same[maxn];
     7 ll ans = 0;
     8 
     9 int main(){
    10     int n;
    11     scanf("%d", &n);
    12     int maxi = -1, pos = 0;
    13     for(int i = 0; i < n; ++i){
    14         scanf("%d", &height[i]);
    15         if(height[i] > maxi){
    16             maxi = height[i];
    17             pos = i;
    18         }
    19     }
    20     rotate(height, height + pos, height + n);
    21     height[n] = maxi;
    22     same[n] = 0;
    23     for(int i = n - 1; i >= 0; --i){
    24         r[i] = i + 1;
    25         while(r[i] < n && height[i] > height[r[i]]) r[i] = r[r[i]];
    26         if(r[i] != n && height[i] == height[r[i]]){
    27             same[i] = same[r[i]] + 1;
    28             r[i] = r[r[i]];
    29         }
    30     }
    31     for(int i = 1; i <= n; ++i){
    32         l[i] = i - 1;
    33         while(l[i] && height[i] >= height[l[i]]) l[i] = l[l[i]];
    34     }
    35     for(int i = 1; i < n; ++i){
    36         ans += (2 + same[i]);
    37         if(l[i] == 0 && r[i] == n) --ans;
    38     }
    39     printf("%I64d\n", ans);
    40     return 0;
    41 }

[6A][]

水题

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 int a, b, c, d;
     5 
     6 void init(){
     7     int arr[4];
     8     cin >> arr[0] >> arr[1] >> arr[2] >> arr[3];
     9     sort(arr, arr + 4);
    10     a = arr[0]; b= arr[1]; c = arr[2]; d = arr[3];
    11 }
    12 int main(){
    13     init();
    14     if(a + b > c || a + b > d || a + c > d || b + c > d) puts("TRIANGLE");
    15     else if(a + b == c || a + b == d || a + c == d || b + c == d) puts("SEGMENT");
    16     else puts("IMPOSSIBLE");
    17     return 0;
    18 }

[6B][]

两层广搜过的，然而智障了......用一层广搜+set就行了

两层的辣鸡代码....:

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 const int maxsize = 111;
     5 int cx[] = {
          1, -1, 0, 0}, cy[] = {
          0, 0, 1, -1};
     6 struct pos{
     7     int x, y;
     8     pos(int xx = 0, int yy = 0): x(xx), y(yy){};
     9 };
    10 
    11 char room[maxsize][maxsize];
    12 bool flag[maxsize][maxsize];
    13 
    14 int main(){
    15     int n, m;
    16     char color;
    17     cin >> n >> m;
    18     cin.get();
    19     cin >> color;
    20     queue<pos> mainpos;
    21     memset(flag, false, sizeof(flag));
    22     for(int i = 0; i < n; ++i)
    23         for(int j = 0; j < m; ++j){
    24             cin >> room[i][j];
    25             if(room[i][j] == color){
    26                 mainpos.push(pos(i, j));
    27                 flag[i][j] = true;
    28             }
    29         }
    30     int ans = 0;
    31     while(!mainpos.empty()){
    32         int x = mainpos.front().x, y = mainpos.front().y;
    33         mainpos.pop();
    34         for(int i = 0; i < 4; ++i){
    35             int nx = x + cx[i], ny = y + cy[i];
    36             if(nx < 0 || n <= nx || ny < 0 || m <= ny || flag[nx][ny] || room[nx][ny] == '.') continue;
    37             ++ans;
    38             queue<pos> tpos;
    39             tpos.push(pos(nx, ny));
    40             flag[nx][ny] = true;
    41             char tcolor = room[nx][ny];
    42             while(!tpos.empty()){
    43                 int xx = tpos.front().x, yy = tpos.front().y;
    44                 tpos.pop();
    45                 for(int j = 0; j < 4; ++j){
    46                     int nxx = xx + cx[j], nyy = yy + cy[j];
    47                     if(nxx < 0 || n <= nxx || nyy < 0 || m <= nyy || room[nxx][nyy] != tcolor || flag[nxx][nyy]) continue;
    48                     flag[nxx][nyy] = true;
    49                     tpos.push(pos(nxx, nyy));
    50                 }
    51             }
    52         }
    53     }
    54     cout << ans << endl;
    55     return 0;
    56 }

一层 + set：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

[6C][]

水题，第一次用deque

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 int main(){
     5     int n;
     6     cin >> n;
     7     deque<int> chb;
     8     for(int i = 0; i < n; ++i){
     9         int tmp;
    10         cin >> tmp;
    11         chb.push_back(tmp);
    12     }
    13     int t1 = chb.front(), ans1 = 1, t2 = 0, ans2 = 0;
    14     chb.pop_front();
    15     while(!chb.empty()){
    16         if(t1 <= t2){
    17             t1 += chb.front();
    18             ++ans1;
    19             chb.pop_front();
    20         }
    21         else{
    22             t2 += chb.back();
    23             ++ans2;
    24             chb.pop_back();
    25         }
    26     }
    27     cout << ans1 << " " << ans2 << endl;
    28     return 0;
    29 }

[6D][]

不会做.....题解看不懂....... dfs

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 const int MAXN = 22;
     5 int n, a, b, ans, h[MAXN], hh[MAXN];
     6 
     7 
     8 bool dfs(int curpos, int time, int hitpos){
     9     if(time == 0){
    10         for(int i = 1; i <= n; ++i)
    11             if(h[i] >= 0) return false;
    12         return true;
    13     }
    14     if(h[curpos] < 0) return dfs(curpos+1, time, hitpos);
    15     for(int i = min(n-1, max(hitpos, max(2, curpos))); i <= min(n-1, curpos+1); ++i){
    16         h[i] -= a; h[i-1] -= b; h[i+1] -= b;
    17         if(dfs(curpos, time-1, i)){
    18             hh[time] = i;
    19             return true;
    20         }
    21         h[i] += a; h[i-1] += b; h[i+1] += b;
    22     }
    23     return false;
    24 }
    25 
    26 
    27 int main(){
    28     cin >> n >> a >> b;
    29     for(int i = 1; i <= n; ++i) cin >> h[i];
    30     for(int i = 1; ; ++i){
    31         memset(hh, 0, sizeof(hh));
    32         if(dfs(1, i, 2)){
    33             cout << i << endl;
    34             for(int j = 1; j <= i; ++j)
    35                 cout << hh[j] << " ";
    36             return 0;
    37         }
    38     }
    39     return 0;
    40 }

[6E][]

求最大值最小值差不超过给定值的最长子串

ST表预处理区间最大值最小值，加个二分右边界...

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 const int maxn = 1e5 + 7;
     5 int n, k;
     6 int data[maxn];
     7 int premin[maxn][20], premax[maxn][20];
     8 struct tpoint{
     9     int l, r;
    10     tpoint(int _l, int _r): l(_l), r(_r) {};
    11 };
    12 
    13 void init_st(){
    14     for(int i = 1; i <= n; ++i)
    15         premin[i][0] = premax[i][0] = data[i];
    16     int k = floor(log(double(n)) / log(2.0));
    17     for(int j = 1; j <= k; ++j)
    18         for(int i = n; i >= 1; --i)
    19             if(i + (1<<(j-1)) <= n){
    20                 premin[i][j] = min(premin[i][j-1], premin[i+(1<<(j-1))][j-1]);
    21                 premax[i][j] = max(premax[i][j-1], premax[i+(1<<(j-1))][j-1]);
    22             }
    23 }
    24 
    25 int query_st(int l, int r){
    26     int k = floor(log(double(r-l+1)) / log(2.0));
    27     return max(premax[l][k], premax[r-(1<<k)+1][k]) - min(premin[l][k], premin[r-(1<<k)+1][k]);
    28 }
    29 
    30 int check(int i){
    31     int l = i, r = n + 1;
    32     while(l < r - 1){
    33         int mid = (l + r) >> 1;
    34         if(query_st(i, mid) <= k) l = mid;
    35         else r = mid;
    36     }
    37     return l;
    38 }
    39 
    40 int main(){
    41     scanf("%d %d", &n, &k);
    42     for(int i = 1; i <= n; ++i)
    43         scanf("%d", &data[i]);
    44     init_st();
    45     int amount = 0;
    46     vector<tpoint> vp;
    47     for(int l = 1; l <= n; ++l){
    48         int r = check(l);
    49         int num = r - l + 1;
    50         if(num > amount){
    51             vp.clear();
    52             vp.push_back(tpoint(l, r));
    53             amount = num;
    54         }
    55         else if(num == amount) vp.push_back(tpoint(l, r));
    56     }
    57     printf("%d %d\n", amount, vp.size());
    58     for(vector<tpoint>::iterator i = vp.begin(); i != vp.end(); ++i)
    59         printf("%d %d\n", (*i).l, (*i).r);
    60     return 0;
    61 }

[7A][]

水题但是有点意思(因为你还是个渣啊~)

记下每一行每一列多少个黑，凑齐8个答案+1，若答案是16就-8

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 char cb[10][10];
     5 int cnt[10][10];
     6 
     7 int main(){
     8     ios::sync_with_stdio(false);
     9     int ans = 0;
    10     for(int i = 0; i < 8; ++i)
    11         for(int j = 0; j < 8; ++j){
    12             cin >> cb[i][j];
    13             if(cb[i][j] == 'B'){
    14                 ++cnt[i][8];
    15                 ++cnt[8][j];
    16             }
    17             if(cnt[i][8] == 8) ++ans;
    18             if(cnt[8][j] == 8) ++ans;
    19         }
    20     if(ans == 16) ans -= 8;
    21     cout << ans << endl;
    22     return 0;
    23 }

[7B][]

粗暴地模拟，大概坑都是给我挖的....

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 const int maxn = 111;
     5 int n, k, mem[maxn];
     6 
     7 int main(){
     8     int counter = 0;
     9     scanf("%d %d", &n, &k);
    10     while(n--){
    11         char s[11];
    12         int x;
    13         scanf("%s", s);
    14         if(s[0] == 'a' || s[0] == 'e'){
    15             scanf("%d", &x);
    16             if(s[0] == 'a'){
    17                 bool flag = false;
    18                 int tmp = 0;
    19                 for(int i = 0; i < k; ++i){
    20                     if(mem[i] == 0) ++tmp;
    21                     else tmp = 0;
    22                     if(tmp == x){
    23                         printf("%d\n", ++counter);
    24                         int index = i;
    25                         while(tmp--) mem[index--] = counter;
    26                         flag = true;
    27                         break;
    28                     }
    29                 }
    30                 if(!flag) puts("NULL");
    31             }
    32             else{
    33                 bool flag = false;
    34                 for(int i = 0; i < k; ++i){
    35                     if(x == 0) break;
    36                     if(mem[i] == x){
    37                         mem[i] = 0;
    38                         flag = true;
    39                     }
    40                 }
    41                 if(!flag) puts("ILLEGAL_ERASE_ARGUMENT");
    42             }
    43         }
    44         else{
    45             for(int i = 0; i < k; ++i){
    46                 if(mem[i] != 0){
    47                     int j = i;
    48                     while(j > 0 && mem[j-1] == 0) --j;
    49                     swap(mem[i], mem[j]);
    50                 }
    51             }
    52         }
    53     }
    54     return 0;
    55 }

[7C][]

扩展欧几里得解不定方程组

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 
     5 ll ex_gcd(ll a, ll b, ll& x, ll& y){
     6     if(b == 0){
     7         x = 1;
     8         y = 0;
     9         return a;
    10     }
    11     int k = ex_gcd(b, a % b, x, y);
    12     int t = y;
    13     y = x - (a / b) * y;
    14     x = t;
    15     return k;
    16 }
    17 
    18 int main(){
    19     ios::sync_with_stdio(false);
    20     ll a, b, c, x, y;
    21     cin >> a >> b >> c;
    22     ll k = ex_gcd(a, b, x, y);
    23     c = -c;
    24     if(c % k) cout << "-1" << endl;
    25     else cout << (c / k * x) << " " << (c / k * y) << endl;
    26     return 0;
    27 }

[7D][]

字符串两个方向hash判回文+dp

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 
     5 const int maxn = 5e6 + 7;
     6 const int mod = 1e9 + 7;
     7 const int tmp = 137731735;
     8 char s[maxn];
     9 ll prefix[maxn], suffix[maxn], dp[maxn];
    10 
    11 int main(){
    12     gets(s);
    13     for(int i = 0; s[i]; ++i){
    14         if(s[i] >= '0' && s[i] <= '9')
    15             s[i] -= '0';
    16         else if(s[i] >= 'a' && s[i] <= 'z')
    17             s[i] -= ('a' - 10);
    18         else
    19             s[i] -= ('A' - 36);
    20     }
    21     ll len = strlen(s), base = 1;
    22     for(int i = 1; i <= len; ++i){
    23         prefix[i] = (prefix[i-1] + s[i-1] * base) % mod;
    24         base = (base * tmp) % mod;
    25         suffix[i] = (suffix[i-1] * tmp + s[i-1]) % mod;
    26     }
    27     ll ans = 0;
    28     for(int i = 1; i <= len; ++i){
    29         if(prefix[i] == suffix[i]){
    30             dp[i] = dp[i>>1] + 1;
    31             ans += dp[i];
    32         }
    33     }
    34     printf("%I64d\n", ans);
    35     return 0;
    36 }

[7E][]

arhgoiawhengiuehgoaijgioj........

[8A][]

水题，用py3写是因为.....懒......

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 s = input()
     2 s1 = input()
     3 s2 = input()
     4 
     5 forw = backw = False
     6 tmp = s.find(s1)
     7 if ~tmp:
     8     if ~s[tmp+len(s1):].find(s2):
     9         forw = True
    10 s = s[::-1]
    11 tmp = s.find(s1)
    12 if ~tmp:
    13     if ~s[tmp+len(s1):].find(s2):
    14         backw = True
    15 
    16 if forw and backw: print('both')
    17 elif forw: print('forward')
    18 elif backw: print('backward')
    19 else: print('fantasy')

[8B][]

啊啊啊啊啊啊啊手贱啊啊啊啊啊啊啊 真·教育题 谢谢(微笑)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 typedef pair<int, int> point;
     4 map<point, int> check;
     5 int cx[] = {
          1, -1, 0, 0}, cy[] = {
          0, 0, -1, 1};
     6 int main(){
     7     string s;
     8     cin >> s;
     9     int x = 0, y = 0, xx = 0, yy = 0;
    10     ++check[point(x, y)];
    11     bool flag = true;
    12     for(int i = 0; i < s.size(); ++i){
    13         if(s[i] == 'L') --x;
    14         else if(s[i] == 'R') ++x;
    15         else if(s[i] == 'U') ++y;
    16         else --y;
    17         for(int i = 0; i < 4; ++i){
    18             int xxx = x + cx[i], yyy = y + cy[i];
    19             if(xxx == xx && yyy == yy) continue;
    20             if(check[point(xxx, yyy)]){
    21                 flag = false;
    22                 break;
    23             }
    24         }
    25         if(check[point(x, y)]) flag = false;
    26         if(!flag) break;
    27         ++check[point(x, y)];
    28         xx = x; yy = y;
    29     }
    30     cout << (flag ? "OK" : "BUG") << endl;
    31     return 0;
    32 }

[8C][]

状压dp，不需要绝对固定的顺序，所以每次只要取最前面可取的(line34的break)，每次拿一个或两个(最里层for从 j 开始)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 const int MAXN = 25;
     4 const int INF = 0x3f3f3f3f;
     5 struct point{
     6     int x, y;
     7     point(){}
     8     point(int xx, int yy): x(xx), y(yy) {}
     9 };
    10 point p[MAXN];
    11 int n, dp[1<<MAXN], pre[1<<MAXN], dis[MAXN][MAXN], ans[555];
    12 inline int calc(point a, point b){
    13     return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
    14 }
    15 int main(){
    16     cin >> p[0].x >> p[0].y >> n, p[n] = p[0];
    17     for(int i = 0; i < n; ++i) cin >> p[i].x >> p[i].y;
    18     for(int i = 0; i <= n; ++i) for(int j = 0; j <= n; ++j) dis[i][j] = calc(p[i], p[j]);
    19     memset(dp, INF, sizeof(dp));
    20     dp[0] = 0;
    21     for(int i = 0; i < (1<<n); ++i)
    22         if(dp[i] != INF)
    23             for(int j = 0; j < n; ++j)
    24                 if(!(i>>j&1)){
    25                     for(int k = j; k < n; ++k)
    26                         if(!(i>>k&1)){
    27                             int cur = i | (1<<j) | (1<<k);
    28                             int tmp = dp[i] + dis[n][j] + dis[j][k] + dis[k][n];
    29                             if(dp[cur] > tmp){
    30                                 dp[cur] = tmp;
    31                                 pre[cur] = i;
    32                             }
    33                         }
    34                     break;
    35                 }
    36     cout << dp[(1<<n)-1] << endl << 0;
    37     int cnt = 0;
    38     for(int i = (1<<n)-1; i; i = pre[i]){
    39         int tmp = pre[i] ^ i;
    40         ans[cnt++] = 0;
    41         for(int j = 0; j < n; ++j)
    42             if((1<<j)&tmp)
    43                 ans[cnt++] = j + 1;
    44     }
    45     for(int i = cnt-1; ~i; --i) cout << " " << ans[i];
    46     return 0;
    47 }

[8D][]

转载于:https://www.cnblogs.com/book-book/p/5496344.html

[1A]: http://codeforces.com/problemset/problem/1/A
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211223/ecc0a9fb846447eaa4ea19d540365d47.png
[1B]: http://codeforces.com/problemset/problem/1/B
[1C]: http://codeforces.com/problemset/problem/1/C
[2A]: http://codeforces.com/problemset/problem/2/A
[2B]: http://codeforces.com/problemset/problem/2/B
[2C]: http://codeforces.com/problemset/problem/2/C
[3A]: http://codeforces.com/problemset/problem/3/A
[3B]: http://codeforces.com/problemset/problem/3/B
[3C]: http://codeforces.com/contest/3/problem/C
[3D]: http://codeforces.com/contest/3/problem/D
[4A]: http://codeforces.com/problemset/problem/4/A
[4B]: http://codeforces.com/problemset/problem/4/B
[4C]: http://codeforces.com/problemset/problem/4/C
[4D]: http://codeforces.com/problemset/problem/4/D
[5A]: http://codeforces.com/problemset/problem/5/A
[5B]: http://codeforces.com/problemset/problem/5/B
[5C]: http://codeforces.com/problemset/problem/5/C
[5D]: http://codeforces.com/problemset/problem/5/D
[5E]: http://codeforces.com/problemset/problem/5/E
[6A]: http://codeforces.com/problemset/problem/6/A
[6B]: http://codeforces.com/problemset/problem/6/B
[6C]: http://codeforces.com/problemset/problem/6/C
[6D]: http://codeforces.com/problemset/problem/6/D
[6E]: http://codeforces.com/problemset/problem/6/E
[7A]: http://codeforces.com/problemset/problem/7/A
[7B]: http://codeforces.com/problemset/problem/7/B
[7C]: http://codeforces.com/problemset/problem/7/C
[7D]: http://codeforces.com/problemset/problem/7/D
[7E]: http://codeforces.com/problemset/problem/7/E
[8A]: http://codeforces.com/problemset/problem/8/A
[8B]: http://codeforces.com/problemset/problem/8/B
[8C]: http://codeforces.com/problemset/problem/8/C
[8D]: http://codeforces.com/problemset/problem/8/D

CODEFORCES-PROBLEMSET

发表评论取消回复

还没有评论，来说两句吧...

相关阅读