Aquabet

Talk is cheap. Show me the code.

0%

Codeforces Good Bye 2021: 2022 is NEAR

发表于 更新于 分类于

  这次补了题，发现好多东西都不会了。

先放题目

  Good Bye 2021: 2022 is NEAR

A. Integer Diversity

题目大意

  给定一个数组a，可以对其中任意个数变为相反数 $x \rightarrow -x$ 。问最多可以有多少个不同的数。

思路

  计算每个数的绝对值出现的次数。出现次数大于2的取2，0取1。求和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve() {
    int ans = 0;
    int num;
    cin>>num;
    int nums[101];
    memset(nums, 0, sizeof(nums));
    int thenum;
    for(int i = 0; i < num; i++) {
        cin>>thenum;
        nums[abs(thenum)]++;
    }
    for(int i = 0; i <= 100; i++) {
        if(i == 0 && nums[i] != 0) {
            ans += 1;
        }
        else if(nums[i] > 2) {
            ans += 2;
        } else {
            ans += nums[i];
        }
    }
    cout<<ans<<endl;
}

B. Mirror in the String

题目大意

  题意：给定字符串，选定 $k$，使得 $s_1s_2…s_ks_ks_{k-1}…s_1$ 的字典序最小。

思路

  贪心。

  • 若 $s_1 = s_2$ ，显然 $s_1s_2$ 是最优解。
  • 否则，取最长的一段不上升的前缀。

代码

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
void solve() {
    int n;
    string s;
    cin>>n>>s;
    if(n >= 2 && s[0] == s[1]) {
        cout<<s[0]<<s[0]<<'\n';
        return;
    }
    for(int i = 0; i < n-1; i++) {
        if(s[i] < s[i+1]) {
            for(int j = 0; j <= i; j++) {
                cout<<s[j];
            }
            for(int j = i; j >= 0; j--){
                cout<<s[j];
            }
            cout<<'\n';
            return;
        }
    }
    for(int j = 0; j < n; j++) {
        cout<<s[j];
    }
    for(int j = n-1; j >= 0; j--) {
        cout<<s[j];
    }
    cout<<'\n';
}

C. Representative Edges

题目大意

  给定数组，至少要修改几个元素，才能使得数组变为等差数列。

思路

  不变的数最少是2个，直接枚举不变的2个数，计算其他位置是否可以不变，取最小。$1 \leq n \leq 70$，$O(n^3)$，能过。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve() {
    int n;
    cin>>n;
    int a[n];
    for(int i = 0;i < n; i++) cin>>a[i];
    int ans = 99;
    if(n <= 2) {
        cout<<0<<'\n';
        return;
    }
    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            double d = (a[j] - a[i]) * 1.0 / (j-i);
            int tot = n;
            for(int k = 0; k < n; k++) {
                if(abs(a[k] - (a[i] + (k-i) * d)) <= 1e-10) tot--;
            }
            ans = min(ans, tot);
        }
    }
    cout<<ans<<'\n';
}

D. Keep the Average High

题目大意

  给一个数组a和一个数x。要在a中选择尽可能多的数，使得任意一个长度大于1的子数组 $a_l, a_{l+1} ,…,a_r$ 满足以下条件：

  • 子数组中存在某个数没有被选择
  • $a_l+a_{l+1}+…+a_r \geq x \cdot (r-l+1)$

  问可以选多少个。

思路

  贪心。$a_l+a_{l+1}+…+a_r \geq x \cdot (r-l+1)$ 表明子数组平均值不小于$x$。所以不能取两个相邻且都小于$x$的数。

  首先观察如何判断一个取法是否可行。让大于等于x的标记为x，小于的标记为y，则所有可行的取法的子数组必须满足如下模式：

  • y或者没有y接着若干个x，然后接着一个y再接着若干个x…。比如yxxy,yxyxyxxy, xxy等等。

  注意到：

  • 如果有连续的x，则两部分可以分开判断，子数组为aaaaax xbbbbb，则只需分别判断子数组aaaax 以及xbbbbb是否合法即可。因为两个数的平均数大于等于小的一个。
  • 同理yxyxyxy的情况只需分别判断每个yxy以及yx,xy是否满足条件即可。

  因此要判断一个取法是否可行，则只需判断长度为2和3的子数组即可。
  我们可以从头到尾贪心取，让前i个取尽量多的数，如果数目相同，则尽量让最后一个最靠前。当前位置为i，如果i - 1没取，那么当前位置就可以取，数目加1。
  如果前两个值都取，则判断 a[i] + a[i - 1] + a[i - 2] ≥ 3x 以及 a[i] + a[i - 1] ≥ 2x 是否成立，如果不成立，说明有冲突，选了a[i]就不能选择a[i - 1]，最优肯定是选择a[i - 1]而不是选择a[i]。所以成立就选，不成立不选。
  如果只有 a[i - 1] 被取了，a[i - 2] 没被取，则只需判断 a[i] + a[i - 1] ≥ 2x 是否成立。成立就可以选。

代码

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
void solve() {
    int n, x;
    cin>>n;
    int a[n], vis[n];
    for(int i = 0; i < n; i++) {
        cin>>a[i];
    }
    memset(vis, 0, sizeof(vis));
    cin>>x;
    int ans = 0;
    for(int i = 0; i < n; i++) {
        if (i==0 || !vis[i - 1]) {
            vis[i] = 1;
            ans++;
        }
        else if(i >= 2 && vis[i - 2]) {
            if((a[i] + a[i - 1]) >= 2 * x && (a[i] + a[i - 1] + a[i - 2]) >= 3 * x) {
                ans++;
                vis[i] = 1;
            }
        }
        else if (i >= 1 && (a[i] + a[i - 1]) >= 2 * x) {
            ans++;
            vis[i] = 1;
        }
    }
    cout<<ans<<"\n";
}

E. Lexicographically Small Enough

题目大意

  给定字符串 $s,t$ ，每次操作可以将 $s$ 中的相邻元素交换。问至少需要交换多少组相邻元素可以使得 $s < t$。

思路

  枚举相同前缀的长度，贪心。

  • 假设相同前缀已经固定，长度为 $i(0\le i \le n-1)$，那么最优的情况就是从后面选择一个小于 $t[i]$ 的字符交换过来。最优情况就是选择最近的。
  • 枚举每个$i$，从0开始，要么从后面选择一个最近的小于 $t[i]$ 的字符过来，要么选择一个等于的让前缀相同。每次选择一个等于的过来，维护剩下的字符后缀(i + 1 ~ n)。这样每次移动可能要 $O(n)$ 来维护，总的复杂度需要 $O(n^2)$。我们可以使用树状数组来维护，只需记录每个位置，有多少个本来位于其后的字符启动到前面去。我们用原来的位置加上这个数就是其当前的位置。复杂度 $O(nlogn)$。

代码

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
int n;
vector <int> pos[30];
string a, b;
pair<int, int> ST[4 * 100000];
bool Erase[100000];
 
void Build(int id, int l, int r) {
    ST[id] = {0, 0};
    if(l == r) {
        ST[id] = {l, 0};
        return;
    }
    int mid = (l + r) >> 1;
    Build(id << 1, l, mid);
    Build(id << 1 ^ 1, mid + 1, r);
    ST[id].first = max(ST[id << 1].first, ST[id << 1 ^ 1].first);
}
 
void Down(int id) {
    int tmp = ST[id].second;
    ST[id << 1].first += tmp;
    ST[id << 1].second += tmp;
    ST[id << 1 ^ 1].first += tmp;
    ST[id << 1 ^ 1].second += tmp;
    ST[id].second = 0;
}
 
void Update(int id, int l, int r, int x, int y) {
    if(r < x || y < l) return;
    if(x <= l && r <= y) {
        ST[id].first++;
        ST[id].second++;
        return;
    }
    Down(id);
    int mid = (l + r) >> 1;
    Update(id << 1, l, mid, x, y);
    Update(id << 1 ^ 1, mid + 1, r, x, y);
    ST[id].first = max(ST[id << 1].first, ST[id << 1 ^ 1].first);
}
 
int Get(int id, int l, int r, int i) {
    if(r < i || i < l) return 0;
    if(l == r) return ST[id].first;
    Down(id);
    int mid = (l + r) >> 1;
    return max(Get(id << 1, l, mid, i), Get(id << 1 ^ 1, mid + 1, r, i));
}
 
void solve() {
    pos->clear();
    memset(Erase, 0, sizeof(Erase));
    cin >> n >> a >> b;
    a = ' ' + a; b = ' ' + b;
    for(int i = 1; i <= n; i++)
        if(a[i] != b[i]) {
            if(a[i] < b[i]) {
                cout << 0 << endl;
                return;
            }
            break;
        }
    Build(1, 1, n);
    long long res = INT64_MAX, ans = 0;
    for(int i = n; i >= 1; i--)
        pos[a[i] - 'a'].push_back(i);
    int p = 1;
    for(int i = 1; i <= n; i++) {
        while(p <= n && Erase[p]) {
            p++;
        }
        int Min = n + 1;
        for(int j = 0; j < b[i] - 'a'; j++)
            if(!pos[j].empty()) {
                Min = min(Min, Get(1, 1, n, pos[j].back()));
            }
        if(Min <= n) res = min(res, ans + Min - i);
        if(a[p] == b[i]) {
            pos[a[p] - 'a'].pop_back();
            p++;
        }
        else if(a[p] < b[i]) {
            res = min(res, ans);
            break;
        }
        else {
            if(pos[b[i] - 'a'].empty()) break;
            ans += Get(1, 1, n, pos[b[i] - 'a'].back()) - i;
            Erase[pos[b[i] - 'a'].back()] = 1;
            Update(1, 1, n, 1, pos[b[i] - 'a'].back());
            pos[b[i] - 'a'].pop_back();
        }
    }
    cout << (res == INT64_MAX ? -1 : res) << endl;
}

F. Tricolor Triangles

题目大意

  给定一个无向图，至多64个点，至多256条边。要给这些边涂上3种颜色之一，其中有些边已经有颜色，有些未涂色。要求一个涂色方案，使得任何一个构成三角形的三条边颜色要么都相同，要么各不相同。如果不存在合法的涂色方案，输出-1。

思路

  三条边的颜色a,b,c满足相同或各不相同这个条件，可以转化为 $(a + b + c) \% 3 = 0$。

  建立一个矩阵A，每一行表示每个三角形，每一列表示一条边。每一行有三个位置为1，表示组成这个三角形的三条边。则问题等价于一个同余线性方程$Ax \equiv b mod 3$，其中$x$为每条边的颜色，b为全0。已知 $A,b$，求 $x$。

  线性同余方程可以用高斯消元求解。由于三角形的个数上界为$m\sqrt{m}$，所以总复杂度为$O(m^3 \sqrt{m})$。

后记 2021年度总结

  2021也是过的一塌糊涂。回望过去，发现又是啥都没干的一年，唯一收获的证书是驾照(x。绩点始终上不去，比赛参加一场崩一场，项目做一个烂一个，最后考雅思又被西安疫情打乱。
  天天在宿舍neet也不知道在干嘛。好像番也没看几部，游戏也没上分。只有偶尔刷刷题能抚慰下我焦躁的内心。然后发现好多算法、数据结构都忘了，或者只能口胡，打不出来。然后就跳过，也懒得复习，更不必说学新的算法了。
  新年愿望啊，愿望是啥呢？好像啥都没有。雅思上岸？绩点飞升？感觉都随缘了，我的人生如果能一直neet下去就好了。
  那就希望2022每天都能洗澡吧（x
      –来自西安疫区在宿舍隔离澡堂不开已经18天没洗澡的我
  Update：2022/1/2 看来愿望没实现呢，是说出来就不灵了吗：）