当前位置： 首页 > article >正文

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

article 2024/11/16 16:50:25

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 * 10
	LL 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;
}

        


http://www.kler.cn/a/159255.html

相关文章：

  • CSS Modules中的 :global
  • 【机器学习导引】ch6-支持向量机
  • 【链路层】空口数据包详解(4)：数据物理通道协议数据单元（PDU）
  • 【机器学习】机器学习中用到的高等数学知识-1.线性代数 (Linear Algebra)
  • 24.11.13 机器学习 特征降维(主成份分析) KNN算法 交叉验证(K-Fold) 超参数搜索
  • 操作系统实验：在linux下用c语言模拟进程调度算法程序
  • 网络安全威胁——中间人攻击
  • 牛客算法心得——kotori和素因子（dfs）
  • RK356x U-Boot研究所（命令篇）3.12 mtd命令的用法
  • WeakMap
  • Python实现FA萤火虫优化算法优化卷积神经网络回归模型(CNN回归算法)项目实战
  • 17.认识下Docker之docker的核心原理（2）
  • 商务助理个人简历10篇
  • 轻量封装WebGPU渲染系统示例＜40＞- 多层材质的Mask混合(源码)
  • 解决终Linux端中文乱码问题及设置UTF-8编码
  • HarmonyOS4.0开发应用——【ArkUI组件使用】
  • 第二十一章 网络通信
  • 软著项目推荐 深度学习的水果识别 opencv python
  • Java数据结构之《最短路径》(难度系数100)
  • Android Native Crash 收集
  • vsftpd.confg 常用配置,Beyond Compare 测试可用
  • Mycat关键配置记录
  • WSL2+tensorflow-gpu 2.3.0 C++ 源码编译（Linux）
  • 图数据库知识点9 | 大数据框架与图数据架构异同
  • 集成开发环境PyCharm的使用【侯小啾python基础领航计划 系列（三）】
  • pyqt5使用pyqtgraph实现动态热力图