首页 > 其他分享 >Codeforces Round 911 (Div. 2)

Codeforces Round 911 (Div. 2)

时间：2023-12-03 20:35:47浏览次数：30  
标签：typedef now int Codeforces long Div include 911 define

Preface

忙里偷闲补一下之前欠下的一些CF

这场前5个题都极其一眼，然而F瞪了好久愣是屁都不会

感觉现在水平有有点到瓶颈了，以前是Div2D写完卡现在是Div2E写完卡，但至少还是在进步的

A. Cover in Water

如果存在某个空地块的长度大于\(2\)则可以用两个块造出无限水，否则答案就是所有空位的个数

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=105;
int t,n; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; int lst,sum=0,flag=0;
		for (scanf("%d%s",&n,s+1),i=1;i<=n;++i)
		{
			if ((i==1||s[i-1]=='#')&&s[i]=='.') lst=i;
			if (s[i]=='.'&&(i==n||s[i+1]=='#'))
			{
				int len=i-lst+1; if (len>2) flag=1; sum+=len;
			}
		}
		printf("%d\n",flag?2:sum);
	}
	return 0;
}

B. Laura and Operations

能变成某一个数的充要条件是，另外两个数的奇偶性相同

构造一组解的话也很简单，首先把另外两个数中的一个用到\(0\)，这样多余的那个个数一定是偶数

不妨设要变成\(1\)，现在\(2\)还有偶数个，\(3\)已经用完了，我们重复若干次\((1,2)\to 3,(2,3)\to 1\)即可，每次操作可以消去\(2\)个\(2\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=105;
int t,a[3];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (i=0;i<3;++i) scanf("%d",&a[i]);
		for (i=0;i<3;++i) putchar(a[(i+1)%3]%2==a[(i+2)%3]%2?'1':'0'),putchar(" \n"[i==2]);
	}
	return 0;
}

C. Anji's Binary Tree

直接在数上DP一下即可，设\(f_x\)表示走到\(x\)后要走到某个叶子节点最少所需修改次数

转移的话非常显然，注意当字符为L/R时走对应一边时不需要额外的修改代价，否则要带上\(1\)的修改代价

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=300005,INF=1e9;
int t,n,ls[N],rs[N],f[N]; char s[N];
inline void DFS(CI now=1)
{
	if (ls[now]==0&&rs[now]==0) return (void)(f[now]=0); f[now]=INF;
	if (ls[now]) DFS(ls[now]); if (rs[now]) DFS(rs[now]);
	if (s[now]=='U') f[now]=min(f[now],min(f[ls[now]],f[rs[now]])+1);
	if (s[now]=='L') f[now]=min(f[now],min(f[ls[now]],f[rs[now]]+1));
	if (s[now]=='R') f[now]=min(f[now],min(f[ls[now]]+1,f[rs[now]]));
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%s",&n,s+1),i=1;i<=n;++i) scanf("%d%d",&ls[i],&rs[i]);
		f[0]=INF; DFS(); printf("%d\n",f[1]);
	}
	return 0;
}

D. Small GCD

很经典的约数容斥，看完题目就能想到

首先考虑将所有数从小到大排序，则此时相当于要计算：

\[\sum_{i=1}^n \sum_{j=i+1}^n \gcd(a_i,a_j)\times (n-j) \]

乍一看不好计算，但有关\(\gcd\)的东西我们要么想到反演，要么就是约数容斥，这里显然是后者

我们枚举某个约数\(d\)，将序列中满足\(d|a_i\)的位置\(i\)按顺序拿出来，此时整个式子中除了\(\gcd(a_i,a_j)\)外的贡献很容易统计

然后套约数容斥的板子，把每个数的真实贡献算清楚即可，具体实现看代码，复杂度\(O(n\sqrt a_i)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
int t,n,m,a[N],f[N]; vector <int> v[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i,j; for (m=0,scanf("%lld",&n),i=1;i<=n;++i)
		scanf("%lld",&a[i]),m=max(m,a[i]);
		for (i=1;i<=m;++i) f[i]=0,v[i].clear();
		for (sort(a+1,a+n+1),i=1;i<=n;++i)
		for (j=1;j*j<=a[i];++j) if (a[i]%j==0)
		{
			v[j].push_back(i);
			if (j!=a[i]/j) v[a[i]/j].push_back(i);
		}
		int ans=0; for (i=m;i>=1;--i)
		{
			for (j=0;j<v[i].size();++j) f[i]+=j*(n-v[i][j]);
			for (j=2*i;j<=m;j+=i) f[i]-=f[j]; ans+=f[i]*i;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

E. Transitive Graph

这道更是傻逼题

有向图的传递闭包？那不就等价于跑个Tarjan缩点，在一个强连通分量里的所有点最后会变成一个团吗

然后又要求路径最长，那么显然一个强连通分量里的点最后都要选上

最后跑个拓扑排序，过程中维护下信息最优即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,m,a[N],x,y,dfn[N],low[N],stk[N],vis[N],col[N],tot,top,cnt,s[N],sz[N],deg[N];
pi f[N]; vector <int> v[N],nv[N];
inline void Tarjan(CI now)
{
	dfn[now]=low[now]=++tot; stk[++top]=now; vis[now]=1;
	for (int to:v[now]) if (!dfn[to]) Tarjan(to),low[now]=min(low[now],low[to]);
	else if (vis[to]) low[now]=min(low[now],dfn[to]);
	if (low[now]==dfn[now])
	{
		s[col[now]=++cnt]=-a[now]; sz[cnt]=1; vis[now]=0;
		while (stk[top]!=now) s[col[stk[top]]=cnt]-=a[stk[top]],++sz[cnt],vis[stk[top--]]=0; --top;
	}
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",&a[i]);
		for (i=1;i<=m;++i) scanf("%d%d",&x,&y),v[x].push_back(y);
		for (i=1;i<=n;++i) if (!dfn[i]) Tarjan(i);
		for (i=1;i<=n;++i) for (auto j:v[i])
		if (col[i]!=col[j]) nv[col[i]].push_back(col[j]),++deg[col[j]];
		for (i=1;i<=cnt;++i) if (!deg[i]) f[i]=pi(sz[i],s[i]); else f[i]=pi(0,0);
		queue <int> q; for (i=1;i<=cnt;++i) if (!deg[i]) q.push(i);
		while (!q.empty())
		{
			int now=q.front(); q.pop();
			for (auto to:nv[now])
			{
				f[to]=max(f[to],pi(f[now].fi+sz[to],f[now].se+s[to]));
				if (!--deg[to]) q.push(to);
			}
		}
		pi ans=pi(0,0); for (i=1;i<=cnt;++i) ans=max(ans,f[i]);
		printf("%lld %lld\n",ans.fi,-ans.se);
		for (i=1;i<=n;++i) v[i].clear(),dfn[i]=0;
		for (i=1;i<=cnt;++i) nv[i].clear(),deg[i]=0; tot=cnt=0;
	}
	return 0;
}

Postscript

评价是题出的很好，希望下次我现场打的时候也能出这么合我胃口的DE，我可以展示1h切5题光速下班

标签：typedef,now,int,Codeforces,long,Div,include,911,define
From： https://www.cnblogs.com/cjjsb/p/17873688.html

相关文章

  • Codeforces Round 881 (Div. 3)
    CodeforcesRound881(Div.3)A：ABCA.SashaandArrayColoring题意：求最大的着色成本（着色成本是指同一个颜色的最大值-最小值）思路：肯定不能是相同的，直接最大-最小就行#include<bits/stdc++.h>usingnamespacestd;inta[60];voidsolve(){intn;cin>>n;......
  • [Codeforces] CF1807E Interview
    题目翻译有\(n\)堆石头，其中\(n-1\)堆都只有重量为一克的石头，剩下一堆有则有一块有两克的石头和若干重量为一克的石头。你的任务是在\(30\)次询问内推理出那一堆有重量为两克的石头是第几堆。首先输入\(n\)，接下来输入\(n\)个数\(a_1,a_2\dotsa_n\)，其中\(a_i\)表示......
  • Codeforces Round 911 (Div. 2)
    CodeforcesRound911(Div.2)A-CoverinWaterintmain(){IOS;for(cin>>_;_;--_){cin>>n>>s+1;intans=0;boolf=0;for(inti=1,j=1;i<=n;i=++j)if(s[i]=='......
  • Codeforces Round 904 (Div. 2) C. Medium Design
    jly：开始的想法：首先枚举max的位置。包含它的一定是全加，剩下的一定都不加。然后求所有位置的最小值。初始全0，枚举max之后，因为是加区间，min一定在两端（最左或最右）。所以不需要枚举max，我们枚举min就好（因为加区间和初始全0，这个题的特殊性）。写法注意的点：下标从0开始，区间的左端点都-1，右端......
  • [Codeforces] CF1733C Parity Shuffle Sorting
    题面翻译给定一个长度为\(n\)的数组，你可以对它进行不超过\(n\)次操作。对于每次操作：选择两个下标\(l,r\)，满足\(1\leql<r\leqn\)；若\(a_l+a_r\)为奇数，将\(a_r\)赋值为\(a_l\)，否则将\(a_l\)赋值为\(a_r\)。求一种方案，使得操作后的数组单调不减（即\(a_1\leq......
  • Codeforces Round 912 (Div. 2)
    A.HalloumiBoxes题意：长度为n的数组，你可以逆转最多k长度，问你能不能是数组递增思路：如果k>=2那么每个数都可以两两交换，如果下表1的地方是1就一定可以，k=1的话单独讨论usingnamespacestd;voidsolve(){ intn,k; cin>>n>>k; vector<int>a(n+1); for(inti=1;i<=n;i++){ ......
  • Codeforces Round 908 (Div. 2)
    总结T1题目大意:A,B两人玩游戏，游戏规则如下：整场游戏有多轮，每轮游戏先胜\(X\)局的人获胜，每场游戏先胜\(Y\)局的人获胜。你在场边观看了比赛，但是你忘记了\(x\)和\(y\)，只记得总共比了\(1\len\le20\)局，和每局获胜的人，请判断谁获胜了。如果A获胜，输出A，如果B获胜，输......
  • CodeForces 1526F Median Queries
    洛谷传送门CF传送门首先，如果我们确定了\(1,2\)或\(n-1,n\)的位置，我们就能求出原排列。因为题目给了\(p_1<p_2\)，所以可以不考虑对称性。也就是说我们知道两个位置是\(1,2\)或\(n-1,n\)但不确定究竟是\(1,2\)还是\(n-1,n\)也可以。然后，如果我们确定......
  • Codeforces Round 878 (Div. 3)
    CodeforcesRound878(Div.3)A：ABCA.CipherShifer题意：在自身后面添加一个字母，但是不能添加自身思路：找到第二个与自身相符的就再找#include<bits/stdc++.h>usingnamespacestd;constintMAX=110;chara[MAX];voidsolve(){intn;cin>>n;for(......
  • [Codeforces] CF1627B Not Sitting
    题意Rahul和Tina在玩一个游戏。游戏在一个\(n\timesm\)的网格图上进行，记第\(r\)行第\(c\)列上的格子为\((r,c)\)。定义\((a,b)\)与\((c,d)\)之间的距离为\(\left|a-c\right|+\left|b-d\right|\)。游戏开始后，Tina会选择恰好\(k\)个格子，并将其涂成粉红色。涂......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99