开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【Codeforces Round #786 (Div. 3)】【A~E题解】 -> 正文阅读

[数据结构与算法]【Codeforces Round #786 (Div. 3)】【A~E题解】

2022年5月3日15:12:06

A. Number Transformation

题目大意：

给你两个整数 x 和 y。您想选择两个严格的正（大于零）整数 a 和 b，然后将以下操作应用于 x 恰好 a 次：将 x 替换为 b?x。

您想找到两个正整数 a 和 b，使得在此过程之后 x 等于 y。如果有多个可能的对，您可以选择其中任何一个。如果没有这样的对，请报告。

例如：

如果x=3，y=75，可以选择a=2，b=5，这样x就等于3?5?5=75；
如果x=100，y=100，可以选择a=3，b=1，这样x就等于100?1?1?1=100；
如果 x=42 且 y=13，则没有答案，因为您不能使用给定的操作减少 x。
输入
第一行包含一个整数 t (1≤t≤10^4)——测试用例的数量。

每个测试用例由一行组成，其中包含两个整数 x 和 y (1≤x,y≤100)。

输出
如果可以选择一对正整数 a 和 b，使 x 在上述过程后变为 y，则打印这两个整数。您打印的整数应不小于 1 且不大于 10^9（可以证明，如果答案存在，则存在一对满足这些约束的整数 a 和 b）。如果有多个这样的对，打印其中任何一个。

如果不可能选择一对整数 a 和 b 以使 x 变为 y，则打印整数 0 两次。

测试样例：

inputCopy
3
3 75
100 100
42 13
outputCopy
2 5
3 1
0 0

题解：

按照题意模拟很明显考虑 y%x==0 ，如果可以直接输出最简单的一种组合，即为1 y/x;否则输出0 0；

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const int maxn=1e6+5;
void solve(){
    int a,b;
    cin >> a >> b;
    if(b%a==0){
        cout << 1 << " " << b / a<<"\n";
    }else{
        cout << "0 0\n";
    }
}

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

B. Dictionary

题目大意：

Berland 语言由恰好有两个字母的单词组成。此外，单词的第一个字母与第二个字母不同。两个不同的 Berland 字母（顺便说一下，与拉丁字母的小写字母相同）的任何组合都是 Berland 语言中的正确单词。

Berland 词典包含该语言的所有单词。单词的列出方式通常在字典中排序。形式上，如果以下条件之一成立，则单词 a 在字典中的出现早于单词 b：

a的首字母小于b的首字母；
a和b的第一个字母相同，a的第二个字母小于b的第二个字母。
所以，字典看起来像这样：

Word 1: ab
Word 2: ac
…
Word 25: az
Word 26: ba
Word 27: bc
…
Word 649: zx
Word 650: zy

给你一个来自 Berland 语言的单词 s。你的任务是在字典中找到它的索引。

输入
第一行包含一个整数 t (1≤t≤650)——测试用例的数量。

每个测试用例由一行包含 s 组成——一个由两个不同的小写拉丁字母组成的字符串（即，Berland 语言的正确单词）。

输出
对于每个测试用例，打印一个整数——单词 s 在字典中的索引。

测试样例：

inputCopy
7
ab
ac
az
ba
bc
zx
zy
outputCopy
1
2
25
26
27
649
650

题解：

翻译题意，s[0]和s[1]分别代表第一个字母和第二个字母，s[0]和s[1]不相同，所以需要考虑s[0]<s[1]这种情况，像26进制转换的问题，但是需要减去重复的情况即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const int maxn=1e6+5;
void solve(){
    string s;
    cin >> s;
    int sum = (s[0] - 'a') * 26 + (s[1] - 'a');
    // cout << sum << endl;
    // cout <<"cheshi:" <<(s[1] - 'a') - (s[0] - 'a') << endl;
    if(s[1]-'a'>s[0]-'a'){
        cout << sum - (s[0] - 'a')  << endl;
    }else{
        cout << sum - (s[0] - 'a') + 1 << endl;
    }
}

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

C. Infinite Replacement

题目大意：

给定一个字符串 s，仅由拉丁字母 ‘a’ 组成，以及一个字符串 t，由小写拉丁字母组成。

在一个步骤中，您可以将字符串 s 中的任何字母 ‘a’ 替换为字符串 t。请注意，在替换字符串 s 之后可能包含“a”以外的字母。

您可以执行任意数量的移动（包括零）。您可以获得多少种不同的字符串？打印数字，或报告它是无限大的。

如果两个字符串具有不同的长度，或者它们在某个索引处不同，则它们被认为是不同的。

输入
第一行包含一个整数 q (1≤q≤10^4)——测试用例的数量。

每个测试用例的第一行包含一个非空字符串 s，仅由拉丁字母 ‘a’ 组成。 s 的长度不超过 50。

第二行包含一个非空字符串 t，由小写拉丁字母组成。 t 的长度不超过 50。

输出
对于每个测试用例，打印在任意移动量（包括零）之后可以获得的不同字符串 s 的数量。如果数字无限大，则打印 -1。否则，打印号码。

测试样例：

inputCopy
3
aaaa
a
aa
abc
a
b
outputCopy
1
-1
2

题解：

很明显这题需要分情况讨论，首先替换串t 中是否含有a，其次t的串长是否为1。

如果串长为1且含a：陷入循环只有1种可能
如果串长大于1且含a：可以无限增长，输出-1；
此外考虑的问题就是替换了，可以不替换也可以全替换，所以方案数为 $2^{cnt}$ ，其中 $c n t$ 为主串s中a的个数。

当然不用快速幂也能过，但是记得开long long

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const int maxn=1e6+5;
ll ksm(ll a, ll b) {
    ll ans = 1, base = a;
    while(b != 0) {
        if(b & 1 != 0) {
            ans *= base;
        }
        base *= base;
        b >>= 1;
    }
    return ans;
}
void solve(){
    string s, t;
    cin >> s >> t;
    if(t.find('a')!=-1&&t.length()!=1){
        cout << "-1\n";
    }else if(t.find('a')!=-1&&t.length()==1){
        cout << "1\n";
    }else{
        ll sum = 0, cnt = 0;
        for (int i = 0; i < s.length();i++){
            if(s[i]=='a')
                cnt++;
        }
        //sum = (ll)pow(2, cnt);
        sum = ksm(2ll, cnt);
        cout << sum << "\n";
    }
}

D. A-B-C Sort

题目大意：

给定三个数组 a、b 和 c。最初，数组 a 由 n 个元素组成，数组 b 和 c 为空。

您正在执行由两个步骤组成的以下算法：

第 1 步：当 a 不为空时，从 a 中取出最后一个元素并将其移动到数组 b 的中间。如果 b 当前为奇数长度，您可以选择：将 a 中的元素放在 b 的中间元素的左侧或右侧。结果，a 变为空，b 由 n 个元素组成。
第 2 步：当 b 不为空时，从 b 中取出中间元素并将其移动到数组 c 的末尾。如果 b 当前具有偶数长度，您可以选择取两个中间元素中的哪一个。结果，b 变为空，c 现在由 n 个元素组成。
有关示例，请参阅注释部分。
你能让数组 c 按非递减顺序排序吗？

输入
第一行包含一个整数 $t (1≤t≤2?10^4)$ — 测试用例的数量。接下来是 t 个案例。

每个测试用例的第一行包含单个整数 $n (1≤n≤2?10^5)$ — 数组 a 的长度。

每个测试用例的第二行包含 n 个整数 $a_1,a_2,…,a_n (1≤a_i≤10^6)$ — 数组 a 本身。

保证n之和不超过2?10^5。

输出
对于每个测试，如果可以使数组 c 以非递减顺序排序，则打印 YES（不区分大小写）。否则，打印 NO（不区分大小写）。

测试样例：

inputCopy
3
4
3 1 5 3
3
3 2 1
1
7331
outputCopy
YES
NO
YES

题解：

题目的排序方法通过模拟可以得出，数组最终的排序就是每两位进行排序后的结果，所以只需要比较模拟排序后的结果是否为有序的即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define all(a) a.begin(), a.end()
#define nl "\n"
const int inf=0x3f3f3f3f;
const int maxn=1e6+5;
void solve(){
    int n;
    cin>>n;
    vi arr(n);
    for (int i = 0; i < n;i++)
        cin >> arr[i];
    vi b = arr;//排好序的数组
    sort(all(b));
    for (int i = n % 2; i < n; i += 2){
        if(arr[i]>arr[i+1])//每两位排一次序
            swap(arr[i], arr[i + 1]);
    }
    if(arr == b){
        cout<<"YES"<<nl;
    }
    else{
        cout<<"NO"<<nl;
    }
}

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

E. Breaking the Wall

题目大意：

Monocarp 玩“Rage of Empires II: Definitive Edition”——一款战略电脑游戏。现在他正打算在游戏中攻击他的对手，但是Monocarp的部队无法进入对手的领地，因为对手已经筑起了一道墙。

墙由 n 个部分组成，排成一排。第 i 个部分最初具有耐久性 ai。如果某个部分的耐久度变为 0 或更低，则认为该部分已损坏。

为了攻击对手，Monocarp 需要破坏至少两段墙（任意两段：可能相邻，可能不相邻）。为此，他计划使用 onager——一种特殊的攻城武器。 Onager可用于拍摄墙壁的任何部分；射击对目标部分造成 2 点伤害，对相邻部分造成 1 点伤害。换言之，如果幼虫在区间 x 射击，则区间 x 的持久性减少 2，区间 x-1 和 x+1（如果存在）的持久性各减 1。

Monocarp可以在任何部分射击任意次数，他甚至可以在破碎的部分射击。

Monocarp 想要计算打破至少两个部分所需的最小射击次数。帮助他！

输入
第一行包含一个整数 n (2≤n≤2?10^5) — 部分的数量。

第二行包含整数序列 a_1,a_2,…,a_n (1≤a_i≤10^6)，其中 a_i 是第 i 个部分的初始持久性。

输出
打印一个整数——至少打破两段墙所需的最小数量。

测试样例：

inputCopy
5
20 10 30 10 20
outputCopy
10

inputCopy
3
1 8 1
outputCopy
1

题解：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define all(a) a.begin(), a.end()
#define nl '\n'
const int inf=0x3f3f3f3f;
const int maxn=2e5+5;
void solve(){
    int n;
    int a[maxn] = {0};
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int ans = inf;
    a[0] = a[n + 1] = inf;
    for (int i = 1; i <= n; i++) {
        int g[3] = {a[i - 1], a[i + 1], (a[i] + 1) / 2};
        sort(g, g + 3);
        ans = min(ans, g[1]);
    }
    for (int i = 1; i < n; i++) {
        int t = max({(a[i] + 1) / 2, (a[i + 1] + 1) / 2, (a[i] + a[i + 1] + 2) / 3});
        ans = min(ans, t);
    }
 
    for (int i = 1; i + 2 <= n; i++) {
        ans = min(ans, a[i] / 2 + a[i + 2] / 2 + 1);
    }
    sort(a + 1, a + n + 1);
    ans = min(ans, (a[1] + 1) / 2 + (a[2] + 1) / 2);
    cout << ans << nl;
}

int main(){
    ios::sync_with_stdio(0);
    int t = 1;
   // cin>>t;
    while(t--)
        solve();
    return 0;
}

F. Desktop Rearrangement

题目大意：

你的朋友伊万让你帮他重新安排他的桌面。桌面可以表示为一个大小为 n×m 的矩形矩阵，由字符“.”（桌面的空白单元格）和“*”（图标）组成。

如果桌面的所有图标都占据了某个完整列的前缀，并且可能占据了下一列的前缀（该图之外没有图标），则桌面被称为good。换句话说，一些第一列将被图标填充，并且可能，下一列（在最后一个完整列之后）的一些第一个单元格也将被图标填充（桌面上的所有图标都属于这个图）。这与现实生活中的图标排列几乎相同。

一次移动，您可以将一个图标移动到桌面上的任何空白单元格。

Ivan 喜欢在他的桌面上添加一些图标并从中删除它们，所以他要求您回答 q 个问题：添加/删除一个图标后，使桌面good所需的最少移动次数是多少？

请注意，查询是永久性的，并且会更改桌面的状态。

输入
输入的第一行包含三个整数n、m和 q（1≤n,m≤1000;1≤q≤2?10^5）——桌面的行数，桌面的列数和数字的查询，分别。

接下来的 n 行包含桌面的描述。其中第 i 个包含 m 个字符 '.'和 ‘*’ - 桌面第 i 行的描述。

接下来的 q 行描述查询。其中第 i 个包含两个整数 $x_i$ 和 $y_i$ $1≤x_i≤n;1≤y_i≤m)$ — 改变其状态的单元格的位置（如果此单元格之前包含图标，则删除此图标，否则此单元格中会出现一个图标）。

输出
打印 q 个整数。其中第 i 个应该是应用前 i 个查询后使桌面正常所需的最少移动次数。

测试样例：

inputCopy
4 4 8
..**
.*..
*...
...*
1 3
2 3
3 1
2 3
3 4
4 3
2 3
2 2
outputCopy
3
4
4
3
4
5
5
5

inputCopy
2 5 5
*...*
*****
1 3
2 2
1 3
1 5
2 3
outputCopy
2
3
3
3
2

题解：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define all(a) a.begin(), a.end()
#define nl '\n'
const int inf=0x3f3f3f3f;
const int maxn=1010;

int g[maxn][maxn];
int col[maxn], cnt;

void solve(){
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            char c;
            cin >> c;
            g[i][j] = c == '*';
        }
    for (int j = 1; j <= m; ++j) {
        for (int i = 1; i <= n; ++i) {
            col[j] += g[i][j];
        }
        cnt += col[j];
    }
    while (q--) {
        int x, y;
        cin >> x >> y;
        int sign = 1;
        if (g[x][y]) {
            sign = -1;
        }
        g[x][y] ^= 1;//取反
        col[y] += sign;
        cnt += sign;
        int s = cnt / n, r = cnt % n;
        int sum = 0;
        for (int i = 1; i <= s; ++i)
            sum += col[i];
        for (int i = 1; i <= r; ++i)
            sum += g[i][s + 1];
        cout << cnt - sum << nl;
    }
}
int main(){
    ios::sync_with_stdio(0);
    int t = 1;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

//树状数组
void add(int x, int v){
	while (x<=n*m) {
		c[x] += v;
        x += (x & (-x));
    }
}
int getsum(int x) {
	int res = 0;
	while (x) {
        res += c[x];
        x -= (x & (-x));
    }
	return res;
}
void solve(){
    cin >> n >> m >> q;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mp[i][j];
            if (mp[i][j] == '*'){
                add((j - 1) * n + i, 1);
                sum++;
            }
        }
    }
    while (q--) {
        int x, y;
        cin >> x >> y;
        if (mp[x][y] == '*')
            add((y - 1) * n + x, -1), sum--, mp[x][y] = '.';
        else
            add((y - 1) * n + x, 1), sum++, mp[x][y] = '*';
        cout << sum - getsum(sum) << "\n";
    }
}