小花生

study & life record.

Codeforces Round 993 (Div.4)

发表于 分类于 ，

12月15日 Codeforces 实战记录。

AC数7/9。
比赛跳转：Codeforces Round 993 (Div. 4)

题解

A. Easy Problem

输出 n-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n; cin >> n;
    cout << n - 1 << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

B. Normal Problem

模拟镜像。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    string s; cin >> s;
    string res;
    for(int i = s.size() - 1; i >= 0; i--){
        if(s[i] == 'p'){
            res += 'q';
        }
        if(s[i] == 'q'){
            res += 'p';
        }
        if(s[i] == 'w'){
            res += 'w';
        }
    }
    cout << res << '\n';
}

signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while(t--) solve();
  return 0;
}

C. Hard Problem

分类讨论题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int m, a, b, c; cin >> m >> a >> b >> c;
    if(a + c <= b){
        cout << min(a + c, m) + min(b, m) << '\n';
    }
    else if(b + c <= a){
        cout << min(b + c, m) + min(a, m) << '\n';
    }
    else{
        int res = (a + b + c) / 2;
        int o = (a + b + c) % 2;
        if(res >= m){
            cout << m * 2 << '\n';
        }
        else{
            cout << 2 * res + o << '\n';
        }
    }
}

signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while(t--) solve();
  return 0;
}

D. Harder Problem

构造题，保持 1~n 每一个数出现一次即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n; cin >> n;
    vector<int>v(n), vis(n + 1, 0);
    for(int i = 0; i < n; i++) cin >> v[i];

    int cur = 1;
    for(int i = 0; i < n; i++){
        if(!vis[v[i]]){
            vis[v[i]] = 1;		
        }
        else{
            while(vis[cur]){
                cur++;
            }
            vis[cur] = 1;
            v[i] = cur;
        }
    }
    for(auto &i : v) cout << i << ' ';
       cout << '\n';
}

signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while(t--) solve();
  return 0;
}

E. Insane Problem

枚举 n，获得每次的 y/x 值，从而用 y 范围倒推 x 范围，与原范围取交集，计算 x 范围长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int k, l1, r1, l2, r2; cin >> k >> l1 >> r1 >> l2 >> r2;
    int mul = 1, cnt = 0;
    while(l1 * mul <= r2){
        int newl = max((l2 + mul - 1) / mul, l1);
        int newr = min(r2 / mul, r1);
        cnt += max(0ll, newr - newl + 1);
        mul *= k;
    }
    cout << cnt << '\n';
}

signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while(t--) solve();
  return 0;
}

F. Easy Demon Problem

题目等价于：是否存在 a 中取 n-1 个数求和，b 中取 m - 1 个数求和，两数乘积为 x。

处理出所有 a 中每 n-1 个数的和，b 中每 m-1 个数的和，分别丢入两个 map 中。

对 x 做因式分解，看能否拆成两 map 中各取一个数的乘积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n, m, q; cin >> n >> m >> q;
    vector<int>a(n), b(m);
    unordered_map<int, bool>mpa, mpb;
    for(auto &i : a) cin >> i;
    for(auto &i : b) cin >> i;
    int suma = accumulate(a.begin(), a.end(), 0ll);
    int sumb = accumulate(b.begin(), b.end(), 0ll);
    for(int &i : a) mpa[suma - i] = 1;
    for(int &i : b) mpb[sumb - i] = 1;

    while(q--){
      int ok = 0;
      int x; cin >> x;
      for(int i = 1; i * i <= abs(x); i++){
        if(x % i) continue;
        if((mpa[i] && mpb[x / i]) || (mpa[-i] && mpb[-x / i])
          || (mpb[i] && mpa[x / i]) || (mpb[-i] && mpa[-x / i])){
          cout << "YES" << '\n';
          ok = 1; break;
        }
      }
      if(!ok) cout << "NO" << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

G1. Medium Demon Problem (easy version)

看作有向图，每次取出入度为0的点，没有点可以取出时stable。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n; cin >> n;
    vector<int>vec(n + 1), ind(n + 1, 0);
    for(int i = 1; i <= n; i++){
        cin >> vec[i];
        ind[vec[i]]++;
    }    

    queue<int>Q;
    for(int i = 1; i <= n; i++){
        if(!ind[i]) Q.emplace(i);
    }
    if(Q.empty()){
        cout << 2 << '\n';
        return;
    }

    int cnt = 1;
    while(cnt++){
        queue<int>q;
        while(!Q.empty()){
            int u = Q.front();
            Q.pop();
            ind[vec[u]]--;
            if(!ind[vec[u]]){
                q.emplace(vec[u]);
            }
        }
        Q = q;
        if(Q.empty()){
            break;
        }
    }
    cout << cnt + 1 << '\n';
}

signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while(t--) solve();
  return 0;
}

G2. Medium Demon Problem (hard version)

H. Hard Demon Problem

维护三个二维前缀和，结果由这三个二维前缀和的运算得到。

给出简单示意举例（数字表示该位置元素的系数）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
s:
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
s1:
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
s2:
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4

以 (2, 2) (3, 3) 为例：
希望得到的系数矩阵：
1 2
3 4
可以拆为：
1 2       0 0
1 2  and  2 2

左边可以由s1与s作简单运算得到，右边可以用s2与s作简单运算后乘上一个系数得到。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n, q; cin >> n >> q;
    vector<vector<int>>v(n + 1, vector<int>(n + 1, 0));
    vector<vector<int>>s(n + 1, vector<int>(n + 1, 0));
    vector<vector<int>>s1(n + 1, vector<int>(n + 1, 0));
    vector<vector<int>>s2(n + 1, vector<int>(n + 1, 0));
 
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> v[i][j];
            s[i][j] = v[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
            s1[i][j] = v[i][j] * j + s1[i - 1][j] + s1[i][j - 1] - s1[i - 1][j - 1];
            s2[i][j] = v[i][j] * i + s2[i - 1][j] + s2[i][j - 1] - s2[i - 1][j - 1];
        }
    }

    while(q--){
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        int u = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
        int u1 = s1[x2][y2] - s1[x1 - 1][y2] - s1[x2][y1 - 1] + s1[x1 - 1][y1 - 1];
        int u2 = s2[x2][y2] - s2[x1 - 1][y2] - s2[x2][y1 - 1] + s2[x1 - 1][y1 - 1];
        cout << u1 - (y1 - 1) * u + (u2 - x1 * u) * (y2 - y1 + 1) << ' ';
    }
    cout << '\n';
}

signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while(t--) solve();
  return 0;
}