首页 > 其他分享 >Codeforces Round #786 (Div. 3) 补题记录

Codeforces Round #786 (Div. 3) 补题记录

时间：2022-11-13 17:00:18浏览次数：81  
标签：786 cout int Codeforces long cin 补题 tie define

小结：

A,B,F 切，C 没写 1ll 对照样例才发现，E,G 对照样例过，D 对照样例+看了其他人代码（主要急于看后面的题，能调出来的但偷懒了。

CF1674A Number Transformation

考虑若 \(y\) 不能整除 \(x\) 则无解，否则一定存在一组解 \(a=1,b=y\div x\)。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0);
#define int long long
using namespace std;
int T,n,a[200005],x,y ;
string s;
void solve(){
	cin>>x>>y;
	if(y%x){
		cout<<"0 0"<<endl;
		return ;
	}
	int tmp=y/x;
	cout<<1<<' '<<tmp<<endl;
}
signed main(){
	IOS;TIE;
	T=1;
	cin>>T;
	while(T--) solve();
	return 0;
}

CF1674B Dictionary

直接用 \(\text{map}\) 映射，用两个字符或字符串对应数字，注意两个字符相同的要跳过。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0);
#define int long long
#define mk(x,y) make_pair(x,y)
using namespace std;
int T,n,a[200005],x,y,tot;
string s;
map<pair<char,char>,int> mp;
void solve(){
	cin>>s;
	cout<<mp[mk(s[0],s[1])]<<endl;
}
signed main(){
	IOS;TIE;
	T=1;
	for(char i='a';i<='z';i++){
		for(char j='a';j<='z';j++){
			if(i==j) continue;
			mp[mk(i,j)]=++tot;
		}
	}
	cin>>T;
	while(T--) solve();
	return 0;
}

CF1674C Infinite Replacement

分类讨论：

  • 若替换串中有 a，且替换串长度 \(>1\)，则可以无限替换，输出 \(-1\)
  • 若替换串中有 a，且替换串长度 \(=1\)，则只有一种情况，即原串
  • 否则，考虑原串中每一位是否替换，可能情况有 \(2^{原串长度}\) 种情况
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0);
#define int long long
#define mk(x,y) make_pair(x,y)
using namespace std;
int T;
string s,t;
void solve(){
	cin>>s>>t;
	bool fl=0;
	for(int i=0;i<t.size();i++){
		if(t[i]=='a') fl=1;
	}
	if(fl&&t.size()>1){
		cout<<-1<<endl;
		return ;
	}
	if(fl){
		cout<<1<<endl;
		return ;
	}
	cout<<(1ll<<s.size())<<endl;
}
signed main(){
	IOS;TIE;
	cin>>T;
	while(T--) solve();
	return 0;
}

CF1674D A-B-C Sort

容易发现这样操作之后只可以改变相邻两个数的位置，若原长度为奇数则第一个数会多出来，否则看两两是否相等即可。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0);
#define int long long
#define mk(x,y) make_pair(x,y)
using namespace std;
int T,n,a[200005],b[200005];
int l[1000005],r[1000005];
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);
	if(n%2){
		if(a[0]!=b[0]){
			cout<<"NO"<<endl;
			return ;
		}
	}
	for(int i=1+(n%2);i<=n;i+=2){
		if(!(a[i]==b[i]&&a[i+1]==b[i+1]||a[i]==b[i+1]&&a[i+1]==b[i])){
			cout<<"NO"<<endl;
			return ;
		}
	}
	cout<<"YES"<<endl;
}
signed main(){
	IOS;TIE;
	cin>>T;
	while(T--) solve();
	return 0;
}

CF1674E Breaking the Wall

分类讨论：

  1. 取原串中最小的两个数 \(x,y\)（不一定相邻），使它们变零。分别一直 \(-2\)，代价为 \(⌈\frac{x}{2}⌉+⌈\frac{y}{2}⌉\)
  2. 取原串中相邻两个数 \(a_i,a_{i+1}\)，使他们变零。设 \(x\) 为较大数，\(y\) 为较小数：
    1. 若 \(x>y\times2\)，则一直在 \(x\) 处 \(-2\)，代价为 \(y+⌈\frac{x-2\times y}{2}⌉\)
    2. 否则，看大小灵活 \(-2\)，代价为 \(⌈\frac{x+y}{3}⌉\)
  3. 取原串中间隔一数的两个数 \(a_i,a_{i+2}\)，使他们变零。设 \(x\) 为较大数，\(y\) 为较小数。先一直使中间数 \(-2\) 直到 \(x,y\) 中任意一个变 \(0\)，随后剩下的一直 \(-2\)，代价为 \(y+⌈\frac{x-y}{2}⌉\)

去三种情况的最小答案即可。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0);
#define int long long
#define mk(x,y) make_pair(x,y)
using namespace std;
int T,n,a[200005],ans=1e18,mn,semn;
void case0(){
	mn=semn=1e18;
	for(int i=1;i<=n;i++){
		if(a[i]<mn) semn=mn,mn=a[i];
		else if(a[i]<semn) semn=a[i];
	}
	ans=min(ans,(int)ceil(mn/2.0)+(int)ceil(semn/2.0));
}
void case1(){
	for(int i=1;i<n;i++){
		int x=a[i],y=a[i+1];
		if(x<y) swap(x,y);
		if(y*2<x) ans=min(ans,y+(int)ceil((x-y*2)/2.0));
		else ans=min(ans,(int)ceil((x+y)/3.0));
	}
}
void case2(){
	for(int i=1;i<n-1;i++){
		int x=a[i],y=a[i+2];
		ans=min(ans,min(x,y)+(int)ceil(abs(x-y)/2.0));
	}
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	case0();case1();case2();
	cout<<ans<<endl;
}
signed main(){
	IOS;TIE;
	T=1;
	while(T--) solve();
	return 0;
}

CF1674F Desktop Rearrangement

题意实为要求将所有 * 移动到这种状态：

image

即优先填满靠左的列。

所以每次要做的就是统计出当前棋盘上有多少 *，这是左侧该有 * 的数量，然后算出该有 * 的位置有多少是空的，即为最小移动步数。

考虑对于每一列维护前缀和，每次更新一个点加一列，询问只要从左往右扫即可。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0);
#define int long long
#define mk(x,y) make_pair(x,y)
using namespace std;
int T,n,m,x,y,q,s[1005][1005],sum;
bool a[1005][1005];
char c;
void solve(){
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c;
			if(c=='*') a[i][j]=1,sum++;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) s[i][j]=s[i-1][j]+a[i][j];
	}
	while(q--){
		cin>>x>>y;
		if(a[x][y]){
			sum--;
			for(int i=x;i<=n;i++) s[i][y]--;
		}
		else{
			sum++;
			for(int i=x;i<=n;i++) s[i][y]++;
		}
		a[x][y]^=1;
		int tmp=sum,ans=0;
		for(int j=1;j<=m;j++){
			if(tmp>n) tmp-=n,ans+=n-s[n][j];
			else{
				ans+=tmp-s[tmp][j];
				break;
			}
		}
		cout<<ans<<endl;
	}
}
signed main(){
	IOS;TIE;
	T=1;
	while(T--) solve();
	return 0;
}

CF1674G Remove Directed Edges

首先手玩样例，可以发现一个性质：删边之后若可以从 \(u\to v\)，则需满足 \(u\) 的出度 \(>1\)，\(v\) 的入度 \(>1\)。

同时，\(\text{DAG}\) 中要取一个点集，使可以从其中一点走向另一点，则此点集一定可以构成一条链。具体可以根据拓扑序来理解。

所以，就可以用拓扑排序求最长路的方法来做这道题。不同的是，有入度、出度 \(>1\) 的限制条件。具体处理方法是：记下每一个点的原始入度 \(In_i\) ，如果当前队首出度 \(<2\)，则按照常规拓扑排序的来搞，否则，若走向点的原始入度 \(>1\)，则可以更新那个点的答案。同时，减入度和入队还是和一般拓排序一样。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0);
#define int long long
#define mk(x,y) make_pair(x,y)
using namespace std;
int T,n,m,in[200005],In[200005],out[200005],f[200005],u,v,ans;
bool vis[200005];
vector<int> a[200005]; 
queue<int> q;
void solve(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		a[u].push_back(v);
		in[v]++,In[v]++,out[u]++;
	}
	for(int i=1;i<=n;i++) if(!in[i]) vis[i]=1,q.push(i);
	for(int i=1;i<=n;i++) f[i]=1;
	while(q.size()){
		int k=q.front();q.pop();
		if(out[k]<2){
			for(int i=0;i<a[k].size();i++){
				int tmp=a[k][i];
				if(!--in[tmp]) q.push(tmp);
			}
			continue;
		}
		for(int i=0;i<a[k].size();i++){
			int tmp=a[k][i];
			if(In[tmp]>1) f[tmp]=max(f[tmp],f[k]+1);
			if(!--in[tmp]) q.push(tmp);
		}
	}
	for(int i=1;i<=n;i++) ans=max(ans,f[i]);
	cout<<ans<<endl;
}
signed main(){
	IOS;TIE;
	T=1;
	while(T--) solve();
	return 0;
}

\[\]

\[\Huge{G\ L\ \&\ H\ F\ !} \]

标签：786,cout,int,Codeforces,long,cin,补题,tie,define
From： https://www.cnblogs.com/binary1110011/p/16886299.html

相关文章

  • Codeforces Round #833 (Div. 2) A-D.md
    比赛链接A题解知识点：数学。注意到\(n\)为奇数时，不考虑连续性，一共有\(\lceil\frac{n}{2}\rceil^2\)个格子，接下来证明一定能凑成方块。从下往上从大到小摆，第\(1......
  • Codeforces Round #833 (Div. 2) A-C题解
    比赛链接A、手摸不难发现，能做出的正方形大小就是当前的最大长度。所以直接输出向上取整即可。点击查看代码#include<bits/stdc++.h>usingnamespacestd;#defineN......
  • CodeForces - 1187E Tree Painting
    题意：给出一棵树，最开始所有节点都是白的。进行一些操作来计算树的价值。每次操作可以选一个节点，给价值加上包括这个结点在内的白色连通块大小。然后把这个结点染成黑色。除......
  • CodeForces-1005#C
    正文将原式\(a_i+a_j=2^p\)转化为\(a_j=2^p-a_i\)，对于，每个\(a_i\)，枚举\(p\)，可以有效地降低时间复杂度。设\(num\leftarrow0\)，若\(2^p-a_i\)存在相等的\(a_j\)，......
  • CodeForces - 1092F Tree with Maximum Cost
    题意：给出一棵树，每个结点有一个权值。定义一棵树以ai为根节点的价值为 剩下每个结点到根节点的距离乘权值 之和。求这棵树的最大价值。解：随便选一个结点为根，从下到上统......
  • Codeforces 1738 / Codeforces Global Round 22
    目录ContestLinkProblemAGloryAddictsProblemBPrefixSumAddictsProblemCEvenNumberAddictsProblemDPermutationAddictsProblemEBalanceAddictsProblemF......
  • 「题解」Codeforces 1342F Make It Ascending
    只会\(\mathcal{O}(3^nn^2)\)，打开题解一看怎么还真是这个玩意/jy首先集合之间形成一个sum和pos的二维偏序，那么思路就是对一维扫描线，然后另一维搞个什么东西。具体到......
  • 塔防（cover）Atcoder/Codeforces的某道题
    题目背景在某个塔防游戏中，有一种防御塔，可以攻击到上下左右四个方向以及自身位置的敌人。题目描述塔防游戏的⼀个关卡地图可以看作⼀个的矩阵，也就是⾏，列的矩阵。其......
  • Codeforces Round #172 (Div. 1) C. Game on Tree（期望的线性性质）
    题意是给出一棵有根树，每次等概率删除一个点以及以其为根的子树，问删完整棵树的期望步数。暴力枚举方案显然不可，考虑期望的线性性质，将问题转化为删除每个点的期望步数再求和......
  • Educational Codeforces Round 109 (Rated for Div. 2) E. Assimilation IV（期望的线性
    题意是有n个城市和m个点，已知每个城市到每个点的距离为\(a_{ij}\)，每秒进行一次操作，每次随机选一个没选过的城市建一个碑，其影响的范围每秒加一，求n秒后被影响的点数的期......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99