Codeforces Round 913 (Div. 3)（A~G）

2023-12-06 07:28
文章标签 codeforces round div 913

本文主要是介绍Codeforces Round 913 (Div. 3)（A~G），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、编程模拟

2、栈模拟

3、找规律？（从终止状态思考）

4、二分

5、找规律，数学题

6、贪心（思维题）

7、基环树

A - Rook 

        题意：

        直接模拟

// Problem: A. Rook
// Contest: Codeforces - Codeforces Round 913 (Div. 3)
// URL: https://codeforces.com/contest/1907/problem/0
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{string s;cin >> s;char c = s[0];int k = s[1] - '0';for(int i = 0 ; i < 8 ; i++){char t = i + 'a';if(t == c){continue;}else{cout << t <<k<<endl;}}for(int i = 1 ; i < 9 ; i ++){if(i == k)continue;else{cout << c << i <<endl;}}
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

B - YetnotherrokenKeoard 

        题意：给定键入顺序，但是其中‘B’和‘b’不再代表字母，‘B’代表删除前面第一个大写字母，‘b’代表删除前面第一个小写字母，求最终键入的字符串结果。

        思路：‘第一个’自然想到了栈的后进后出原则，‘B’‘b’操作即是出栈操作。先不考虑最终结果，而是将其字母的键入时间放入栈当中。最后将栈中键入时间全部取出，再根据键入时间输出结果。

        

// Problem: B. YetnotherrokenKeoard
// Contest: Codeforces - Codeforces Round 913 (Div. 3)
// URL: https://codeforces.com/contest/1907/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{string s;cin >> s;stack<int>big , small;int len = s.size();for(int i = 0 ; i < len ; i ++){if(s[i] >= 'a' && s[i] <= 'z'){if(s[i] == 'b'){if(!small.empty()){small.pop();}}				else{small.push(i);}}else{if(s[i] == 'B'){if(!big.empty()){big.pop();}}else{big.push(i);}}}vector<int>ans;while(!big.empty()){ans.pb(big.top());big.pop();}while(!small.empty()){ans.pb(small.top());small.pop();}sort(ans.begin() , ans.end());len = ans.size();for(int i = 0 ; i < len ; i ++){cout <<s[ans[i]];}cout << endl;
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

C - Removal of Unattractive Pairs 

        题意：给定字符串，能够删除相邻两个不相同字符，求最终字符最短能为多少。

        思路：考虑最终状态：一定不存在字符或者只存在一种字符。因此考虑将其余字符全部删除，能将字符串变为多短。

// Problem: C. Removal of Unattractive Pairs
// Contest: Codeforces - Codeforces Round 913 (Div. 3)
// URL: https://codeforces.com/contest/1907/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{cin >> n;vector<int>cnt(26 , 0);string s;cin >>s;for(int i = 0;  i < n ; i ++){cnt[s[i] - 'a']++;}int maxx = 0;for(int i = 0 ; i < 26 ; i ++){maxx = max(maxx , cnt[i]);}cout << max( n & 1 ? 1 : 0 , n - 2 * (n - maxx)) << endl;
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

 D - Jumping Through Segments 

        题意：

        思路：直接二分求答案，每一轮的范围是[上一轮左端点 - k ， 上一轮右端点 + k ] ,然后和当前线段合并，若不相交则false。

        

// Problem: D. Jumping Through Segments
// Contest: Codeforces - Codeforces Round 913 (Div. 3)
// URL: https://codeforces.com/contest/1907/problem/D
// Memory Limit: 256 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
vector<pair<int,int>>range;
bool check(int len){pair<int,int> ran = {0 , 0};int t = range.size();for(auto to : range){
//		cout << ran.x << " " << ran.y << endl;int l = to.x;int r = to.y;ran.x -= len;ran.y += len;if(ran.x > r || ran.y < l)return false;ran.x = max(ran.x , l);ran.y = min(ran.y , r);}return true;
}
void solve() 
{cin >> n;for(int i = 0 ; i < n ; i ++){pair<int,int>tmp;cin >> tmp.x >> tmp.y;range.pb(tmp);}int l = 0 , r = 1e9;while(l < r){int mid = (l + r) / 2;if(check(mid)){r = mid;} else{l = mid + 1;}}cout << l << endl;range.clear();
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

E - Good Triples 

题意：

思路:可以发现，若要满足条件，那么三个数是不能进位的，因此本题中数据的每一位是不会影响的。满足乘法原则，将每一位所能带来的贡献相乘即可。

// Problem: E. Good Triples
// Contest: Codeforces - Codeforces Round 913 (Div. 3)
// URL: https://codeforces.com/contest/1907/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
int dig(int s){int cnt = 0;while(s){cnt += s % 10;s/=10;}return cnt;
}
void solve() 
{// 0 == 1 // 1 == 3// 2 == 6// 3 == 10// 4 == 15// 5 == 21// 6 == 28// 7 == 36// 8 == 45// 9 == 55// 3141 = 3 * 15 * 3 * 10LL mask[10] = {1 , 3 , 6 , 10 , 15 , 21 , 28 , 36 , 45 , 55};string s;cin >> s;int len = s.size();LL ans = 1;for(int i = 0 ; i < len ; i ++){ans *= mask[s[i] - '0'];}cout << ans << endl;
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

F - Shift and Reverse 

思路：将数组放到环上考虑， 假设环起初按顺时针排 ， 且有一个指针指向了环的第一位。现考虑操作变成了什么：

移位操作：将指针往前移动一格。

反转：将环变成逆时针（将非递减转化为非递增）。

因此，若要满足非递减排序，必然存在从环上某一点出发，顺时针是非递减顺序/非递增的。如何去模拟环，只需要将整个数组复制一遍到尾端即可模拟。然后就是找非递减序列和非递增序列即可。然后判断一下需要多少操作。

        

// Problem: F. Shift and Reverse
// Contest: Codeforces - Codeforces Round 913 (Div. 3)
// URL: https://codeforces.com/contest/1907/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{cin >> n;for(int i = 0 ; i < n ; i ++)cin >> a[i];vector<int>v(2 * n , 0);for(int i = 0 ; i < n ; i ++){v[i] = a[i];v[i + n] = a[i];}int ans = -1;//递减for(int i = 0 ; i < n ; ){int st = i;int cnt = 1;while(i < 2 * n - 1 && v[i] >= v[i + 1]){cnt++;i++;}if(cnt >= n){ans = min(1 + st, 1 + (n - st));}i ++;}//递增for(int i = 0 ; i < n ; ){int st = i;int cnt = 1;while(i < 2 * n - 1 && v[i] <= v[i + 1]){cnt++;i++;}if(cnt >= n){if(ans == -1){ans = min(n - st , st + 2);}else{ans = min(ans ,min(n - st , st + 2) );}if(st == 0)ans = 0;}i ++;}	cout << ans << endl;
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

G - Lights 

        题意：

思路：将相关联的灯建边，每次操作都对边两端处理。可以发现这是一颗基环树，也就是说：在非环上的点可以按照拓扑序来唯一的去处理（要么1变0，同时另一端也变化，要么不变）。现在就只剩下环上的一部分了，可以发现若环上剩余亮着的灯是奇数的话那么就不能全部熄灭了。

        接下来考虑输出最小操作：若环上某一条边的操作已经确定下来了（变或者不变），那么其余所有边操作都确定了，因此可以考虑类似于环形dp的思想。将所有边操作分为两类表示对一类中的每一条边操作后整个环都能变成0。最后比较两类边集大小考虑输出哪一类即可。

        

// Problem: G. Lights
// Contest: Codeforces - Codeforces Round 913 (Div. 3)
// URL: https://codeforces.com/contest/1907/problem/G
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{cin >> n;	vector<int>in(n + 5 , 0);vector<int>vis(n + 5 , 0);vector<int>e(n + 5 , 0) ;string s;cin >> s;s = " " + s;for(int i = 1 ; i <= n ; i ++){int u = i , v;cin >> v;e[u] = v;in[v]++;}	queue<int>q;for(int i = 1 ; i <= n ;i ++){if(in[i] == 0){q.push(i);}}vector<int>ans;while(!q.empty()){int x = q.front();q.pop();if(s[x] == '1'){s[x] = '0';ans.pb(x);if(s[e[x]] == '1'){s[e[x]] = '0';}else{s[e[x]] = '1';}}in[e[x]]--;if(in[e[x]] == 0){q.push(e[x]);}}for(int i = 1 ; i <= n ; i ++){if(in[i]){int j = i;int t = 0;//分为两组int len = 0;int res = 0;//t = 1 的组需要操作的数while(in[j]){if(s[j] == '1'){t ^= 1;}res += t;in[j] = 0;len ++;j = e[j];}if(t == 1){cout << "-1\n";return;}for(int k = 0 ; k < len ; k ++){if(s[j] == '1'){t ^= 1;}if(t == (res < len - res)){ans.pb(j);}j = e[j];}}}cout << ans.size() << endl;for(auto it : ans){cout << it <<" ";}
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

        

这篇关于Codeforces Round 913 (Div. 3)（A~G）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/460953。

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...
Codeforces Round #261 (Div. 2)小记

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件，我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m
阅读更多...
Codeforces Beta Round #47 C凸包 （最终写法）

Codeforces Beta Round #47 C凸包 （最终写法）

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op
阅读更多...
Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A， 多边形B， 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包，如果凸包上的点是B的某个点，则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法，只需在求凸包的时候， <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int
阅读更多...
Codeforces 482B 线段树

Codeforces 482B 线段树

求是否存在这样的n个数； m次操作，每次操作就是三个数 l ，r，val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja
阅读更多...
CSS实现DIV三角形

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor
阅读更多...
创建一个大的DIV，里面的包含两个DIV是可以自由移动

创建一个大的DIV，里面的包含两个DIV是可以自由移动

创建一个大的DIV，里面的包含两个DIV是可以自由移动 <body>         <div style="position: relative; background:#DDF8CF;line-height: 50px"> <div style="text-align: center; width: 100%;padding-top: 0px;"><h3>定&nbsp;位&nbsp;
阅读更多...
Codeforces Round 971 (Div. 4) (A~G1)

Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单，不做解释 C 对于 x y 两个方向，每一个方向至少需要 x / k 向上取整的步数，取最大值。 由于 x 方向先移动，假如 x 方向需要的步数多于 y 方向的步数，那么最后 y 方向的那一步就不需要了，答案减 1 代码 #include <iostream>#include <algorithm>#include <vector>#include <string>
阅读更多...
CF#271 (Div. 2) D.（dp）

CF#271 (Div. 2) D.（dp）

D. Flowers time limit per test 1.5 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接： http://codeforces.com/contest/474/problem/D We s
阅读更多...
CF #278 (Div. 2) B.（暴力枚举+推导公式+数学构造）

CF #278 (Div. 2) B.（暴力枚举+推导公式+数学构造）

B. Candy Boxes time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output 题目链接： http://codeforces.com/contest/488/problem/B There
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2