首页 > 其他分享 >Codeforces Round #819 (Div. 1 + Div. 2)

Codeforces Round #819 (Div. 1 + Div. 2)

时间：2022-09-07 20:45:11浏览次数：77  
标签：int rep Codeforces 819 MAXN Div MOD dp define

\(\texttt{Unrated}\)

好像是印度老哥又一次放了 F 原题，悲。

A

考虑保留头尾的数，\(3\) 种情况的分讨，即保留 \(a_1\)，保留 \(a_n\)，或者都保留。

My Code 
#include<bits/stdc++.h>
#define ll long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define siz(a) (int)a.size()
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pt(a) cerr<<#a<<' '<<a<<' '
#define pts(a) cerr<<#a<<' '<<a<<'\n'
//#define int long long
using namespace std;
const int MAXN=2e3+10;
int a[MAXN];
void solve(){
	int n;cin>>n;
	rep(i,1,n) cin>>a[i];
	if(n==1){cout<<0<<'\n';return;}
	int mx=0,mn=1000;
	rep(i,1,n-1) mn=min(mn,a[i]);
	int ans=a[n]-mn;
	rep(i,2,n) mx=max(mx,a[i]);
	ans=max(ans,mx-a[1]);
	rep(i,2,n) ans=max(ans,a[i-1]-a[i]);
	cout<<ans<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;for(cin>>T;T--;)
		solve();
	return 0;
}

B

一堆特判就行了。

首先判断 \(n>m\) 无解。然后是如果 \(m\%n=0\)，则每个位置平均分就行。

接下来按照 \(1,1,\cdots,m-n+1\) 的方式构造。如果 \(n\) 是奇数，则一定可以。如果是偶数，则判断 \(m\) 是否是奇数，如果是，则无解，否则可以按 \(1,1,\cdots,\dfrac{m-n+2}{2},\dfrac{m-n+2}{2}\) 的方式构造。

My Code 
#include<bits/stdc++.h>
#define ll long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define siz(a) (int)a.size()
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pt(a) cerr<<#a<<' '<<a<<' '
#define pts(a) cerr<<#a<<' '<<a<<'\n'
#define int long long
using namespace std;

void solve(){
	int n,m;cin>>n>>m;
	if(n>m){cout<<"No"<<'\n';return;}
	if(m%n==0){
		cout<<"Yes\n";
		rep(i,1,n) cout<<m/n<<' ';cout<<'\n';
		return;
	}else{
		if(n&1){
			cout<<"Yes\n";
			rep(i,1,n-1) cout<<1<<' ';
			cout<<m-(n-1)<<' '<<'\n';
			return;
		}else{
			if(m&1) cout<<"No\n";
			else{
				cout<<"Yes\n";
				rep(i,1,n-2) cout<<1<<' ';
				rep(i,1,2) cout<<(m-(n-2))/2<<' ';
				return;
			}
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;for(cin>>T;T--;)
		solve();
	return 0;
}

C

比较显然的做法是一个 )( 那么这两个位置在同一个联通块里，匹配的两个也在同一个联通块里。这样用并查集数一下就行了。

更快的做法就是考虑 (( 会出现两个联通块分开，所以答案就是 (( 的个数加一。

My Code 
#include<bits/stdc++.h>
#define ll long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define siz(a) (int)a.size()
#define pb emplace_back
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pt(a) cerr<<#a<<' '<<a<<' '
#define pts(a) cerr<<#a<<' '<<a<<'\n'
//#define int long long
using namespace std;
const int MAXN=2e5+10;
int f[MAXN];
int find(int x){
	while(f[x]^x) x=f[x]=f[f[x]];
	return x;
}
void solve(){
	int n;string s;cin>>n>>s;
	iota(f+1,f+1+2*n,1);
	s=' '+s;
	vector<int> cur;
	rep(i,1,2*n){
		if(s[i]=='('){
			cur.pb(i);
			if(i!=1&&s[i-1]==')') f[find(i-1)]=find(i);
		}
		else{
			f[find(cur.back())]=find(i);
			cur.pop_back();
		}
	}
	int ans=0;
	rep(i,1,2*n) ans+=(find(i)==i);
	cout<<ans<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;for(cin>>T;T--;)
		solve();
	return 0;
}

D

贪心地想，每条边最多使得联通块个数减一，所以我们只要两张图都不成环就行了。具体做法有很多，比较简单的就是先随便找一棵生成树，然后判断剩下的边是否成环，如果成环就任取一条环上的边，并取这条边深度较大的节点，用这个点在生成树上的父亲边替换选取的环上的边。

My Code 
#include<bits/stdc++.h>
#define ll long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define siz(a) (int)a.size()
#define pb emplace_back
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pt(a) cerr<<#a<<' '<<a<<' '
#define pts(a) cerr<<#a<<' '<<a<<'\n'
//#define int long long
using namespace std;
const int MAXN=2e5+10;
int u[MAXN],v[MAXN],f[MAXN];
int find(int x){
	while(x^f[x]) x=f[x]=f[f[x]];
	return x;
}
vector<int> e[MAXN];
int fa[MAXN],dep[MAXN];
void dfs(int x){
	for(int s:e[x]){
		if(s==fa[x]) continue;
		fa[s]=x;dep[s]=dep[x]+1;
		dfs(s);
	}
}
int ans[MAXN],ban[MAXN];
void solve(){
	int n,m;cin>>n>>m;
	iota(f+1,f+1+n,1);
	rep(i,1,m) ans[i]=0;
	rep(i,1,n) ban[i]=0,e[i].clear(),fa[i]=dep[i]=0;
	rep(i,1,m){
		cin>>u[i]>>v[i];
		if(find(u[i])==find(v[i])) continue;
		f[find(u[i])]=find(v[i]);
		ans[i]=1;
		e[u[i]].pb(v[i]);
		e[v[i]].pb(u[i]);
	}
	if(m==n+2){
		int id;
		rep(i,1,m){
			if(ans[i]) continue;
			id=i;
			ban[u[i]]=ban[v[i]]=1;
		}
		int cnt=0;
		rep(i,1,n) cnt+=(ban[i]>0);
		if(cnt==3){
			dfs(1);
			if(dep[u[id]]<dep[v[id]]) swap(u[id],v[id]);
			rep(j,1,m){
				if(u[j]==u[id]&&v[j]==fa[u[id]])
					swap(ans[id],ans[j]);
				else if(v[j]==u[id]&&u[j]==fa[u[id]])
					swap(ans[id],ans[j]);
			}
		}
	}
	rep(i,1,m) cout<<ans[i];cout<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;for(cin>>T;T--;)
		solve();
	return 0;
}

E

考虑一个置换群什么时候能满足题目的条件。首先如果大小小于等于 \(2\) 的置换群，则一定可行。如果大小为 \(4\)，则有 \(3,4,2,1\) 或者 \(4,3,1,2\) 两种情况满足，且要求前两个相邻，后两个相邻。大胆猜测没有别的情况了。

所以问题就转化成，对于 \(n\) 个数，要求按如下方式分组的数目：

  1. 一个数一组；
  2. 任意两个数一组；
  3. 相邻的数和另一相邻的数一组，共 \(4\) 个数，且权重为 \(2\)。

考虑到方式 \(3\) 比较困难，所以先看只考虑前两种方式的方案计数，不难发现就是个简单的 \(dp\)。即令 \(dp_{i,0/1}\) 表示 \(i\) 个数，最后一个数是单独一组或者和前面某一个数一组的方案数，不难得到：

\[\begin{cases} dp_{i,0}=dp_{i-1,0}+dp_{i-1,1}\\ dp_{i,1}=(dp_{i-2,0}+dp_{i-2,1})\times (i-1) \end{cases} \]

然后考虑方式 \(3\)，我们可以枚举一个 \(m\) 表示相邻的数的组数，保证 \(m\) 为偶数。那么我们只需要知道，这 \(m\) 个数两两配对的方案数（可以简单 dp，不再赘述）和在 \(n\) 个数中选出这两两相邻的 \(m\) 组的方案数（利用组合数，就是 \(n-m\choose m\)）。

那最后直接统计答案就行了。

My Code 
#include<bits/stdc++.h>
#define ll long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define siz(a) (int)a.size()
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pt(a) cerr<<#a<<' '<<a<<' '
#define pts(a) cerr<<#a<<' '<<a<<'\n'
#define int long long
using namespace std;
const int MOD=998244353;
const int MAXN=3e5+10;
int ksm(int a,int p){
	int ret=1;while(p){
		if(p&1) ret=ret*a%MOD;
		a=a*a%MOD; p>>=1;
	}return ret;
}
int inv(int x){return ksm(x,MOD-2);}
int fac[MAXN],ifac[MAXN];
void init(){
	fac[0]=ifac[0]=1;
	rep(i,1,MAXN-10) fac[i]=fac[i-1]*i%MOD;
	ifac[MAXN-10]=inv(fac[MAXN-10]);
	per(i,MAXN-11,1) ifac[i]=ifac[i+1]*(i+1)%MOD;
}
int C(int n,int m){return fac[n]*ifac[m]%MOD*ifac[n-m]%MOD;}
int dp[MAXN][2],f[MAXN];
void solve(){
	int n;cin>>n;
	int ans=0;
	for(int m=0;m<=n;m+=2){
		if(n-m>=m){
			ans=(ans+C(n-m,m)*f[m]%MOD*(dp[n-2*m][0]+dp[n-2*m][1])%MOD*ksm(2,m/2)%MOD)%MOD;
		}
	}
	cout<<ans<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	init();f[0]=1;
	for(int i=2;i<=MAXN-10;i+=2)
		f[i]=f[i-2]*(i-1)%MOD;
	dp[0][0]=1;
	rep(i,1,MAXN-10){
		dp[i][0]=(dp[i-1][0]+dp[i-1][1])%MOD;
		if(i>1) dp[i][1]=(dp[i-2][0]+dp[i-2][1])%MOD*(i-1)%MOD;
	}
	int T;for(cin>>T;T--;)
		solve();
	return 0;
}

标签：int,rep,Codeforces,819,MAXN,Div,MOD,dp,define
From： https://www.cnblogs.com/ZCETHAN/p/16667192.html

相关文章

  • Codeforces Round #816 (Div. 2)
    Preface早上7：20起来早自习，结果不知道背什么遂刷了好久知乎……下午只有一个思修课，一边划水一遍写题，堪堪做了ABCD晚上据说有C语言的程序设计？又可以摸鱼了好耶A.Crossm......
  • Educational Codeforces Round 40 (Rated for Div. 2) 补题
    E.WaterTaps题意：每个水龙头有一个流量限制\(a_i\)，温度\(t_i\)，现在让你控制每个水龙头的出水量\(x_i\)，使得最终的水温为\(T\)，水温的公式为$\frac{\sum\limits_{i=1}^{......
  • CodeForces 限时随机挑战
    挑战规则就是初始难度*2400，积分为\(0\)，每次在该难度随机一道题做，每题时限\(35\)分钟，如果没有AC就-1，否则+1，如果积分\(>6\)，那么难度\(+100\)，积分清零，如果积分\(<......
  • 拿到tr循环里的td下的div里的文案
    Elements里的结构如下，需要拿到text文案，首先要拿到tr的循环列表，然后取出每一个tr里的第二个td，再去定位文案   //先定位到tr的上一步WebElementname=driver.fi......
  • Codeforces Round #819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022
    这场打的稀烂。。。A.MainakandArray题意：将数组中某段子序列翻转一次，求a[n]-a[1]最大的值。思路：有三种情况：第一种，将最小的数翻转到第一位，然后用原来的a[n]减去反......
  • python中divmod是什么意思？
    python中divmod()是一个内置函数。pythondivmod()函数把除数和余数运算结果结合起来，返回一个包含商和余数的元组(a//b,a%b)。在python2.3版本之前不允许处理复数......
  • [Editorial] Codeforces Contest 1726
    A.MainakandArray显然如果\([l,r]\)不包括两端那么就不会对答案有影响，那么直接枚举包括两端的情况即可。/*author:Geminidate:September6th,2022url:htt......
  • 9/6 学了一点线性规划，打了一把cf div2被薄纱
    9/6日23:18才参加完cf的一场div2比赛，真难，我只会A题，后面再读题也不会了。希望下一次参赛能会更多。下午学习了数学建模的线性规划部分，深刻的感觉到自己的不足的数学功底，......
  • Educational Codeforces Round 134 D
    D.MaximumAND可以很轻松通过^和&两个操作看出我们要求的两个序列每一位上的1加起来必须等于n才行多一个少一个都不行然后1加起来等于n0自然加起来也等于n0和1的数......
  • Codeforces Round #815 (Div. 2)
    Preface休假强续了一天？刚好找一场题目少的Div.2做一下感觉今天状态不是很好啊，各种傻逼题秒不掉想各种奇怪东西……A.BurenkaPlayswithFractions首先不难发现答案......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99