首页 > 其他分享 >Codeforces Round 903 (Div. 3)

Codeforces Round 903 (Div. 3)

时间：2023-10-15 14:45:18浏览次数：37  
标签：903 int Codeforces long cin maxn Div include check

[比赛链接]

A. Don't Try to Count

直接用string的可加性，每次 s+=s 相当于翻倍了，因为 \(nm<=25\) 所以最多翻倍5次。

判断什么的直接模拟就行。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<iomanip>
#include<ctime>
#include<stack>
using namespace std;
int n,m;
string s,x;
bool check(string s,string t){
	for(int i=0;i<s.length();i++){
		for(int j=0;j<t.length();j++){
			if(i+j>=s.length()) break;
			if(s[i+j]!=t[j]) break;
			if(j==t.length()-1) return 1;
		}
	}
	return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
	cin>>t;
	while(t--){
		cin>>n>>m>>x>>s;
		for(int i=0;i<=5;i++){
			if(check(x,s)){
				cout<<i<<endl;
				break;
			}
			x+=x;
			if(i==5) cout<<-1<<endl;
		}
	}
    return 0;
}

B. Three Threadlets

根据切割的次数分类讨论，可以求出每种情况 若成功则最后每段长度是多少，判断即可。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<iomanip>
#include<ctime>
#include<stack>
using namespace std;
long long a,b,c;
bool check(long long a,long long b,long long c,long long x){
	if(a%x+b%x+c%x!=0) return 0;
	if(a<x||b<x||c<x) return 0;
	if(a/x+b/x+c/x<=6) return 1;
	return 0;
}
int main()
{
    ios::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--){
		cin>>a>>b>>c;
		long long x=a+b+c;
		if(check(a,b,c,x/3)||check(a,b,c,x/4)||check(a,b,c,x/5)||check(a,b,c,x/6)) cout<<"YES\n";
		else cout<<"NO\n";
	}

    return 0;
}

C. Perfect Square

旋转类型的题在草稿纸上模拟一下就知道规律了。

这个题就变成了把正方形矩阵划分成四个区域，让四个区域的某个特定位置都变成这四个特定位置的最大值（直接看代码方便些）。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<iomanip>
#include<ctime>
#include<stack>
using namespace std;
const int maxn=1005;
int T,n;
string s[maxn];

int main()
{
    ios::sync_with_stdio(false);
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>s[i];
			s[i]=' '+s[i];
		}
		int ans=0;
		for(int i=1;i<=n/2;i++){
			for(int j=1;j<=n/2;j++){
				ans+=max(max(max(s[i][j],s[n-j+1][i]),s[n-i+1][n-j+1]),s[j][n-i+1])*4-s[i][j]-s[n-j+1][i]-s[n-i+1][n-j+1]-s[j][n-i+1];
			}
		}
		cout<<ans<<endl;
	}
    return 0;
}

D. Divide and Equalize

可以发现规律 $(a_i \div x)\times (a_j \times x) = a_i \times a_j $ 即经过这些变换之后乘积恒定不变。

所以可以将每个数质因数分解，并统计每个质因数个数，最后只需要判断所有的质因数个数是否都是 \(n\) 的倍数（即能否平均分配到这 \(n\) 个数上）。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<iomanip>
#include<ctime>
#include<stack>
using namespace std;
const int maxn=1000005;
int vis[maxn],prime[maxn],cnt,num[500],T,n,a[maxn];
map<int,int> ma;
void work(int x){
	for(int i=1;i<=cnt;i++){
		while(x%prime[i]==0){
			x/=prime[i];
			ma[i]++;
		}
		if(x==1) break;
	}
	if(x>1) ma[x]++;
}
int main()
{
    ios::sync_with_stdio(false);
    for(int i=2;i<=2000;i++){
    	if(!vis[i]) prime[++cnt]=i;
    	for(int j=1;j<=cnt&&i*prime[j]<=2000;j++){
    		vis[i*prime[j]]=1;
    		if(i%prime[j]==0) break;
		}
	}
	cin>>T;
	while(T--){
		ma.clear();
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=n;i++) work(a[i]);
		int ans=1;
		for(auto i : ma){
			if(i.second%n!=0){
				cout<<"NO\n";
				ans=0;
				break;
			}
		}
		if(ans) cout<<"YES\n";
	}
    return 0;
}

E. Block Sequence

我们发现从一个位置 \(i\) 向后可以直接跳到 \(i+a_i\) 而与 \([i+1,i+a_i]\) 区间里的数没有关系。

像极了dp中的状态转移。

需要从后往前写dp，因为 \(a_i\) 影响的是 \(i\) 后面的一段序列。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<iomanip>
#include<ctime>
#include<stack>
using namespace std;
const int maxn=200005;
int n,a[maxn],dp[maxn];
int main()
{
    ios::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i];
		dp[n]=1;dp[n+1]=0;
		for(int i=n-1;i>=1;i--){
			if(i+a[i]<=n) dp[i]=min(dp[i+a[i]+1],dp[i+1]+1);
			else dp[i]=dp[i+1]+1;
		}
		cout<<dp[1]<<endl;
	}

    return 0;
}

F. Minimum Maximum Distance

类似于换根dp。

一开始我们设 \(f[u]\) 为 \(u\) 到以 \(u\) 为根的子树中标记点的最远距离。

那么 $f[u]=max{f[v]+1} $，即儿子节点的答案加上儿子节点到父亲的距离(1)。

然后需要进行换根操作（代码中直接延续了 \(f\) 数组，但是其意义变为在整张图的范围内 \(u\) 节点的答案），我们发现父亲节点的信息传递到某个儿子时，我们不知道父亲节点的答案是不是从这个儿子那里得到的。

所以说我们用 \(f[u][0/1]\) 分别记录最远距离、次远距离。

若 \(f[u][0]==f[v][0]+1\) 那么就用 \(f[u][1]+1\) 来传递给儿子信息，从而实现换根操作。

最后答案就是 \(min\{f[u][0]\}\)

赛场上能写出来我还是很满意的（

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<iomanip>
#include<ctime>
#include<stack>
using namespace std;
const int maxn=200005;
struct node{
	int v,next;
}e[maxn*2];
int cnt,p[maxn],a[maxn],ans,fa[maxn],f[maxn][2],son[maxn],vis[maxn],n,m;
void insert(int u,int v){
	cnt++;
	e[cnt].v=v;
	e[cnt].next=p[u];
	p[u]=cnt;
}
void dfs1(int u,int f){
	son[u]=0;
	fa[u]=f;
	for(int i=p[u];i!=-1;i=e[i].next){
		int v=e[i].v;
		if(v==f) continue;
		son[u]++;
		dfs1(v,u);
	}
}
void dfs2(int u){
	f[u][0]=f[u][1]=-1;
	if(vis[u]) f[u][0]=f[u][1]=0;
	for(int i=p[u];i!=-1;i=e[i].next){
		int v=e[i].v;
		if(v==fa[u]) continue;
		dfs2(v);
		if(f[v][0]==-1) continue;
		if(f[v][0]+1>f[u][0]) f[u][1]=f[u][0],f[u][0]=f[v][0]+1;
		else if(f[v][0]+1>f[u][1]) f[u][1]=f[v][0]+1;
	}
}
void gengxin(int u,int x){
	if(x==0) return;
	if(x>f[u][0]) f[u][1]=f[u][0],f[u][0]=x;
	else if(x>f[u][1]) f[u][1]=x;
}
void getans(int u){
	if(fa[u]!=-1){
		if(f[fa[u]][0]==f[u][0]+1) gengxin(u,f[fa[u]][1]+1);
		else gengxin(u,f[fa[u]][0]+1);
	}
	ans=min(ans,f[u][0]);
	for(int i=p[u];i!=-1;i=e[i].next){
		int v=e[i].v;
		if(v==fa[u]) continue;
		getans(v);
	}
}
int main()
{
    ios::sync_with_stdio(false);
    int T;
	cin>>T;
	while(T--){
		cnt=0;
		cin>>n>>m;
		for(int i=1;i<=n;i++) vis[i]=0,p[i]=-1;
		for(int i=1;i<=m;i++){
			int x;
			cin>>x;
			vis[x]=1;
		}
		for(int i=1;i<n;i++){
			int u,v;
			cin>>u>>v;
			insert(u,v);
			insert(v,u);
		}
		dfs1(1,-1);
		dfs2(1);
		ans=10000000;
		getans(1);
		cout<<ans<<endl;
	}
    return 0;
}

好，我是小丑。

看了一下题解，只需要找到距离最远的两个被标记的点，设距离为 \(d\)，答案就是 \(\lceil \frac{2}{d} \rceil\)

方法与找树的直径类似，从任意一个被标记的点出发跑一遍bfs找到距离最远的标记点 \(i\)，然后从 \(i\) 出发再跑一遍找到距离最远的标记点 \(j\)，\(ij\) 即为所求。

代码不放了。

G. Anya and the Mysterious String

好题。（赛后补的）

首先，因为题目问的是区间内有无回文串，所以我们只需要找到长度最短的回文串就行。

要么是形如 \(AA\) ，要么是形如 \(ABA\) 。

我们把前者和后者形式的回文串的首位置分别放在两个set中。

假如没有修改操作，那么每次询问的时候只需要分别在set里 lowerbound 一下第一个大于等于 l 的位置，看一看该回文串右端是否大于r即可。

加上区间加的修改操作怎么办呢？

我们发现如果回文串在这个区间内，那么是不影响答案的。

所以每次修改只会影响两端的位置的几个位置的回文情况。

区间修改完后单点查询两端位置的字符是什么，判断，分别更新两个set即可。

树状数组（或者线段树）都可以维护。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<iomanip>
#include<ctime>
#include<stack>
using namespace std;
const int maxn=200005;
int n,m,a[maxn],d[maxn]; 
set<int> a1,a2;
inline int lowbit(int x){
	return x&(-x);
}
void update(int x,int v){
	if(v<0) v+=(-v)/26*26;
	v=(v+26)%26;
	for(int i=x;i<=n;i+=lowbit(i)) d[i]+=v,d[i]%=26; 
}
int query(int x){
	int res=0;
	for(int i=x;i>0;i-=lowbit(i)) res+=d[i];
	return res%26;
}
void check(int x){
	if(x<=0) return;
	if(x<n){
		if(query(x)==query(x+1)) a1.insert(x);
		if(query(x)!=query(x+1)) a1.erase(x);
	}
	if(x<n-1){
		if(query(x)==query(x+2)) a2.insert(x);
		if(query(x)!=query(x+2)) a2.erase(x);
	}
}
int main()
{
    ios::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--){
		a1.clear();a2.clear();
		cin>>n>>m;
		char c;
		for(int i=0;i<=n+1;i++) d[i]=0;
		for(int i=1;i<=n;i++) cin>>c,a[i]=c-'a';
		for(int i=1;i<=n;i++) update(i,a[i]-a[i-1]);
		for(int i=1;i<n;i++) check(i);
		while(m--){
			int tp;
			cin>>tp;
			if(tp==1){
				int l,r,x;
				cin>>l>>r>>x;
				update(l,x);
				update(r+1,-x);
				check(l-2);
				check(l-1);
				check(r-1);
				check(r);
			}else{
				int l,r;
				cin>>l>>r;
				auto r1=a1.lower_bound(l);
				auto r2=a2.lower_bound(l);
				if(r1!=a1.end()&&(*r1)<=r-1){
					cout<<"NO\n";
					continue;
				}
				if(r2!=a2.end()&&(*r2)<=r-2){
					cout<<"NO\n";
					continue;
				}
				cout<<"YES\n";
			}
		}
	}
    return 0;
}

比赛总结

个人感觉比较满意，差一题AK。

不足之处就是F题没有找到最简单的方法，G题对于很多细节的处理也不恰当。

现在看来基本做题思路恢复差不多了，以后需要多做做难题了，不能一直在div3和ABC划水了。

标签：903,int,Codeforces,long,cin,maxn,Div,include,check
From： https://www.cnblogs.com/yinyuqin/p/17765600.html

相关文章

  • Codeforces Round 903 (Div. 3) F. Minimum Maximum Distance（图论）
    CodeforcesRound903(Div.3)F.MinimumMaximumDistance思路对标记点更新fg，从0开始进行bfs，更新d1为所有点到0的距离获得到0最远的标记点L，从L开始bfs，更新d2为所有点到L的距离获得距离L最远的标记点R，从R开始bfs，更新d3为所有点到R的距离遍历所有点，这个点与标记点的最大距......
  • CodeForces 1886E I Wanna be the Team Leader
    洛谷传送门CF传送门把题意抽象成，给你长为\(n\)的序列\(a\)和长为\(m\)的序列\(b\)，初始有\(m\)个空集合（可重集），\(a\)中的每个元素至多被分到\(m\)个集合中的一个。要求最后第\(i\)个集合\(T_i\)不为空，且\(\forallx\inT_i,x\ge\frac{b_i}{|T|}\)。要求构造......
  • Codeforces Round 671 (Div. 2) A. Digit Game
    \(R\)和\(B\)在玩一个数字游戏，给一个含有\(n\)位的正整数\(x\)。俩人轮流操作，\(R\)先行动。在每一步中，\(R\)可以选择\(x\)中一个未被标记的奇数位置并标记，\(B\)可以选择\(x\)中一个未被标记的偶数位置并标记。当最后只剩下一个未被标记的位置时，让这个数为\(m\)......
  • Codeforces Round 748 (Div. 3) B. Make it Divisible by 25
    给一个正整数\(n\)，在一步操作中可以移除\(n\)中的一个。当\(n\)只剩下一位时将不能再操作，如果过程中产生了前导\(0\)，则会被自动移除且不耗费操作次数。询问最少需要多少次操作可以使得\(n\)被\(25\)整除。显然一个正整数\(x\)若可以被\(25\)整除，只需要考虑最后......
  • Educational Codeforces Round 116 (Rated for Div. 2) A. AB Balance
    给一个长为\(n\)的字符串\(s\)，只包含\(0\)\(1\)两种字符。定义\(AB(s)\)是\(s\)中出现的\(01\)子串个数，\(BA(s)\)是\(s\)中出现的\(10\)子串个数。在一步操作中，可以选择一个字符进行异或。询问最小的操作次数使得\(AB(s)=BA(s)\)。显然连续的\(11\)或连......
  • Codeforces Round 903 (Div. 3) E. Block Sequence（DP）
    CodeforcesRound903(Div.3)E.BlockSequence思路：设dp[i]为当i~n为完美的最少删除次数dp[n]=1,dp[n+1]=0;从后至前对于dp[i]更新若直接删除当前点，则为dp[i+1]+1若不删除则为min（dp[i+a[i]+1],dp[i]）;i+a[i]+1为a[i]不能覆盖的位置#defineintlonglong#define......
  • Codeforces Round 903 (Div. 3)
    D题被hack了哭了第一题简单的只用把字符串重复的同时尝试匹配，然后判断就好了，只是需要一点代码能力第二题，也很简单最多剪断3次，就先从小到大排序，然后用最小的，看看大的是他的几倍，如果不是几倍的关系就不可能完成，如果是就算要几次就好了第三题，也很简单，很明显，对于一个格子，在它旋转9......
  • Codeforces Round 674 (Div. 3) B. Symmetric Matrix
    有\(n\)块\(2\times2\)的瓷砖，瓷砖上的每个方格包含一个数字，每种瓷砖都有无数种。现在需要用所给瓷砖构造一个\(m\timesm\)的方形矩阵\(a\)满足：每块瓷砖都在方形矩阵内瓷砖之间不能存在覆盖\(a_{i,j}=a_{j,i}\)。输出是否存在这种构造。一：显然合法的\(m\)......
  • Codeforces Round 903 (Div. 3)
    D.DivideandEqualize思路：1.某个数除以x，某个数再乘以x，可发现数组总的乘积没有变化2.也就是说，要使数组中的每一个元素相同，它们总的质因子应该满足：某个质因子的数量%n==0E.BlockSequence简单的dpdp[i]，表示删除这个数字后的最小删除次数可以正的枚举，也可以倒着来转移方程......
  • Codeforces Global Round 11 A. Avoiding Zero
    给一个大小为\(n\)的数组\(a_1,a_2,\cdots,a_n\)。你需要构造一个大小为\(n\)的数组\(b\)且满足以下条件：数组\(b\)是数组\(a\)的冲排列对于\(\forallk=1,2,\cdots,n\)，\(\sum_{i=1}^{k}b_i\neq0\)。输出任意一组构造，或者回答不可能。若\(\sum_{i......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99