首页 > 其他分享 >Codeforces Round #594 (Div. 2) 题解

Codeforces Round #594 (Div. 2) 题解

时间：2023-05-31 10:03:44浏览次数：47  
标签：rp 594 int 题解 ret lp ans Div mx


题目链接:https://codeforces.com/contest/1248

 

A - Integer Points

水题

#include<bits/stdc++.h>
using namespace std;
const int mx = 1e5+5;
typedef long long ll;
int a[mx],b[mx]; 
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n,m;
		scanf("%d",&n);
		ll c[2] = {0,0};
		ll d[2] = {0,0};
		for (int i=1;i<=n;i++) {
			scanf("%d",a+i);
			c[a[i]%2]++;
		}
		scanf("%d",&m);
		for (int i=1;i<=m;i++) {
			scanf("%d",b+i);
			d[b[i]%2]++;
		}
		printf("%lld\n",c[0]*d[0]+c[1]*d[1]);
	}
	return 0;
}

B - Grow The Tree

意思就是一半的和做一边，另一半的和做另一边，平方的话让一边越大越好就行了

#include<bits/stdc++.h>
using namespace std;
const int mx = 1e5+5;
typedef long long ll;
int a[mx],b[mx]; 
int main(){
	int n;
	scanf("%d",&n);
	int sum = 0;
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		sum += a[i];
	}
	sort(a+1,a+1+n);
	int beg = n / 2,ret = 0;
	for (int i=1;i<=beg;i++)
		ret += a[i];
	printf("%lld\n",1ll*ret*ret+1ll*(sum-ret)*(sum-ret));
	return 0;
}

C - Ivan the Fool and the Probability Theory

不难证明除了黑白交替的方块意外，其他的方块数都是取决于第一行的摆放方案，后面跟随第一行都摆放都是固定的。然后一行的dp方案只要记最后是连续两个一样的还是不一样的方案数就可以，另外行数对黑白交替的方案数的影响其实是一样的。

#include<bits/stdc++.h>
using namespace std;
const int mx = 1e5+5;
const int mod = 1e9 + 7; 
typedef long long ll;
ll dp[mx][2];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	if (m > n) swap(n,m);
	dp[1][0] = 1;
	for (int i=2;i<=n;i++) {
		dp[i][0] = (dp[i-1][0]+dp[i-1][1])%mod;
		dp[i][1] = dp[i-1][0];
	}
	ll ans = (dp[n][0] + dp[n][1] - 1)*2 + (dp[m][0] + dp[m][1])*2;
	ans %= mod;
	printf("%lld\n",ans);
	return 0;
}

D2 - The World Is Just a Programming Task (Hard Version)

利用栈的原理如果括号最后不完全匹配，那么肯定是会是这样情况))))((((,那么要想有解必须左括号数量等于右括号数量。

不难发现我们能操作的空间只有...)..)...(...(...也就是最多两个不匹配的括号

1、将原来匹配的括号互换(()) ==> )()(

2、将两个不匹配的变成0个，))(( ==> ()()

3、减少一个不匹配，)( ==>()

4、变换一个不匹配的位置 ())(== > )()(

#include<bits/stdc++.h>
using namespace std;
const int mx = 3e5+5;
const int mod = 1e9 + 7; 
typedef long long ll;
int n;
int sum[mx];
char s[mx];
int lp[mx],rp[mx],psiz;
int cnt[mx],lc[mx],rc[mx];
bool vis[mx],mark[mx];
int fa[mx];
bool get_pos() {
	stack <int> s1;
	int j = 0;
	for (int i=1;i<=n;i++) {
		if (s[i] == '(') {
			s1.push(i);
		} else {
			if (s1.empty()) {
				lp[psiz++] = i;
				mark[i] = 1;
				continue;
			}
			int now = s1.top();
			lc[now] = i, rc[i] = now;
			s1.pop();
		} 
	}
	if (s1.size() != psiz) return 0;
	reverse(lp,lp+psiz);
	while (!s1.empty()) {
		rp[j++] = s1.top();
		mark[rp[j-1]] = 1;
		s1.pop();
	}
	reverse(rp,rp+psiz);
	return 1;
}
inline int get_int(int l,int r) {
	return sum[r] - sum[l];
}
void get_val() {
	stack <int> s1;
	for (int i=1;i<=n;i++) {
		if (mark[i]) continue;
		if (s[i]=='(') {
			s1.push(i);
		} else {
			int now = s1.top();
			s1.pop();
			if (!s1.empty()) {
				cnt[s1.top()]++;
				fa[now] = s1.top();
			}
			else {
				sum[now]++;
				vis[now] = 1;
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	scanf("%s",s+1);
	int ans,l,r;
	if(!get_pos()) return 0*puts("0\n1 1");
	get_val();
	for (int i=1;i<=n;i++) sum[i] += sum[i-1];
	rp[psiz] = n + 1;
	lp[psiz] = 0;
	sum[n+1] = sum[n];
	ans = get_int(lp[0],rp[0]) + (psiz > 0);
	l = 1,r = 1;
	for (int i=lp[0]+1;i<rp[0];i++) {
		if (s[i]=='(') {
			if (vis[i]){
				if (cnt[i] + 1 > ans) {
					ans = cnt[i] + 1;
					l = i, r = lc[i];
				}
			} else if (vis[fa[i]]){
				int ret = get_int(lp[0],rp[0]) + cnt[i] + 1 + (psiz > 0);
				if (ret > ans) {
					ans = ret;
					l = i, r = lc[i];
				}
			} 
		} 
	}
	if (psiz) {
		int ret = get_int(lp[1],rp[1]) - get_int(lp[0],rp[0])  + (psiz>1) + 1;
		if (ret > ans) {
			ans = ret;
			l = lp[0], r = rp[0];
		}
		if (psiz > 1) {
			ret = get_int(lp[2],rp[2]) + 2;
			ret -= get_int(lp[1],lp[0]) + get_int(rp[0],rp[1]);
			ret += (psiz > 2);
			if (ret > ans) {
				ans = ret;
				l = lp[1],r = rp[1];
			}
		}
		int L = lp[0];
		while (L != lp[1]) {
			if (vis[L]) {
				ret = get_int(lp[0],rp[0]) + 2;
				ret += cnt[L];
				if (ret > ans) {
					ans = ret;
					l = L, r = lc[L];
				}
			}
			L--;
		}
		int R = rp[0];
		while (R != rp[1]) {
			if (vis[R]) {
				ret = get_int(lp[0],rp[0]) + 2;
				ret += cnt[R];
				if (ret > ans) {
					ans = ret;
					l = R, r = lc[R];
				}
			}
			R++;
		}
	}
	printf("%d\n%d %d\n",ans,l,r);
	return 0;
}

E - Queue in the Train

用三个队列维护:

1、优先队列维护可以去泡面的时间

2、在机子前排队的队列

3、可以取泡面但是由于前面的人不在而还没去的优先队列

#include<bits/stdc++.h>
#define x first
#define y second 
using namespace std;
const int mx = 1e5+5;
const int mod = 1e9 + 7; 
typedef long long ll;
typedef pair <int,int> pa;
int n,m;
pa s[mx];
ll ret[mx];
int sum[mx];
priority_queue <int,vector<int>,greater<int>> sq;
queue <int> nq;
void add(int x,int v) {
	for (;x<=n;x+=x&(-x))
		sum[x] += v;
} 
int get_sum(int x) {
	int ans = 0;
	while (x) {
		ans += sum[x];
		x -= x&(-x);
	}
	return ans;
}
void to_queue (int& j,ll times) {
	while (j <= n && s[j].x <= times) {
		if (get_sum(s[j].y) == s[j].y) {
			nq.push(s[j].y);
			add(s[j].y,-1); 
		} else {
			sq.push(s[j].y);
		}
		j++;
	}	
}
int main(){
	scanf("%d%d",&n,&m);
	int u;
	for (int i=1;i<=n;i++) {
		scanf("%d",&u);
		s[i] = pa(u,i);
		add(i,1);
	}
	ll times = 0;
	sort(s+1,s+1+n);
	for (int i=1,j=1;i<=n;i++) {
		if (nq.size() == 0 && s[j].x > times) 
			times = s[j].x;
		to_queue(j, times);
		int id = nq.front(); nq.pop();
		times += m, ret[id] = times;
		to_queue(j, times);
		add(id,1);
		if (!sq.empty() && get_sum(sq.top()) == sq.top()) {
			int now = sq.top();
			nq.push(now); add(now,-1);
			sq.pop(); 
		} 
	}
	for (int i=1;i<=n;i++)
		printf("%lld ",ret[i]);
	return 0;
}

F - Catowice City

一个结论就是人和猫的编号一定是互补的，这个由第i个人肯定和第i只猫有连边推出

然后就是建边找出度为0的强连通分量

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int mx = 2e6 + 10;
int n,m;
bool vis[mx];
int sta[mx],siz,is;
int dfn[mx],id[mx];
int be[mx],ty;
vector <int> g[mx];
void tarjan(int u) {
	dfn[u] = id[u] = ++is;
	sta[++siz] = u;
	vis[u] = 1;
	for (int v:g[u]) {
		if (!dfn[v]) {
			tarjan(v);
			id[u] = min(id[u],id[v]);
		} else if (vis[v])
			id[u] = min(id[u],dfn[v]);
	}
	if (id[u]==dfn[u]) {
		ty++;
		while (sta[siz] != u) {
			be[sta[siz]] = ty;
			vis[sta[siz]] = 0;
			siz--;
		}
		be[u] = ty,vis[u] = 0,siz--;
	}
}
int cnt_one() {
	int cnt = 0;
	for (int i=1;i<=n;i++)
		if (be[i]==1) cnt++;
	return cnt;
}
int main() {
	int t;
	scanf("%d",&t);
	while (t--) {
		scanf("%d%d",&n,&m);
		for (int i=1;i<=2*n;i++) 
			g[i].clear();
		ty = is = siz = 0;
		for (int i=1;i<=2*n;i++)
			dfn[i] = vis[i] = 0;
		for (int i=0,u,v;i<m;i++) {
			scanf("%d%d",&u,&v);
			if (u==v) g[v+n].push_back(u);
			else g[u].push_back(v+n);
		}
		if (n == 1) {
			puts("No");
			continue;
		}
		for (int i=1;i<=n;i++) if(!dfn[i])
			tarjan(i);
		int cnt = cnt_one();
		if (cnt == n) puts("No");
		else {
			//cout << cnt  << endl;
			puts("Yes");
			printf("%d %d\n",cnt,n-cnt);
			for (int i=1;i<=n;i++) if (be[i]==1)
				printf("%d ",i);
			puts("");
			for (int i=1;i<=n;i++) if (be[i]!=1)
				printf("%d ",i);
			puts("");
		}
	}
    return 0;
}

 

标签：rp,594,int,题解,ret,lp,ans,Div,mx
From： https://blog.51cto.com/u_12468613/6384514

相关文章

  • Codeforces Round #599 (Div. 2) 题解
    题目链接:https://codeforces.com/contest/1243 A-MaximumSquare水题不说了#include<bits/stdc++.h>usingnamespacestd;constintmx=1e5+50;typedeflonglongll;intn;inta[mx];intmain(){ intt; scanf("%d",&t); while(t--){ scan......
  • Codeforces #564 (Div. 2) C. Nauuo and Cards[贪心]
    题目链接:http://codeforces.com/contest/1173/problem/C 解题思路:很明显总的抽卡次数是不会超过2*n的。然后我们再将情况分成两种:1.编号1的卡片已经在里面了，并且最底部已经形成了一个1~x的连续的卡片，而且之后x+1,x+2都可以来得及补上，在这种情况下抽卡次数肯定就不会超过n了。2.......
  • Codeforces #564 (Div. 2) D. Nauuo and Circle[树形DP]
    题目链接:http://codeforces.com/contest/1173/problem/D 解题思路:首先得知道按照圆周顺序的话，那么一颗子树必须存放在连续的一段区间里面，现在我们假设根节点是1，那么一颗为u做根节点的子树他的方案数就是各个儿子的方案数的乘积最后再乘以儿子个数+1(u节点本身)的排列方案数。所......
  • 题解 AT_nikkei2019ex_e【コラッツ問題】
    啥玩意，诈骗题还能这么诈骗。\(f(X)\)就是角谷猜想（冰雹猜想）所需的步数。根据角谷猜想，定义函数\(g\)：\[g(X)=\begin{cases}\frac{X}{2},&2\midX\\3X+1,&2\nmidX\end{cases}\]则显然有\(f(g(X))=f(X)-1\)。样例二已经给出了\(f(X)=1000\)的解\(X=1789997546303\)，而\(P......
  • Educational Codeforces Round 149 (Rated for Div. 2)
    A.GrasshopperonaLine#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvoidsolve(){intx,k;cin>>x>>k;if(x%k==0){cout<<"2\n"<<x-1<<"&......
  • P9376 题解
    首先考虑怎么暴力。考虑把每个数进行\(B\)进制分解，然后我们惊奇的发现这两个操作就是把最低位去掉和往最低位后面插入一个数。然后我们顺藤摸瓜，把每个数的分解扔到Trie树上，我们发现我们要找到一个节点，使得所有单词节点到其的距离之和最短，答案就是这个最短距离。这里直接考......
  • CODE FESTIVAL 2016 qual B E 题解
    以下\(\Sigma\)为字符集。首先单次询问\(O(|\Sigma||S|)\)的暴力是显然的：建出trie树，然后每次把对应的字符串在上边扫，加上对应位置比它小的子树的大小。然后接下来有两种方法。正解首先在线大概是没什么前途的，考虑离线，建出trie树之后在上边dfs，处理挂在每个节点上的询......
  • leetcode 728. Self Dividing Numbers
    Aself-dividingnumberisanumberthatisdivisiblebyeverydigititcontains.Forexample,128isaself-dividingnumberbecause128%1==0,128%2==0,and128%8==0.Also,aself-dividingnumberisnotallowedtocontainthedigitzero.Givenal......
  • leetcode 594. Longest Harmonious Subsequence
    Wedefineaharmoniousarrayisanarraywherethedifferencebetweenitsmaximumvalueanditsminimumvalueisexactly1.Now,givenanintegerarray,youneedtofindthelengthofitslongestharmonioussubsequenceamongallitspossiblesubsequences.E......
  • CF1398E Two Types of Spells 题解 set
    题目链接：https://codeforces.com/problemset/problem/1398/E题目大意你有一个集合，初始为空。有两种类型的元素，一种是普通元素，一种是强化元素，两种元素都有一个数值。有\(n\)次操作，每次操作会往集合中加入一个元素或者删除一个元素。每次操作后，你都需要确定集合中元素的一个......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99