首页 > 其他分享 >Codeforces Round 969 (Div. 1)

Codeforces Round 969 (Div. 1)

时间：2024-09-04 19:15:02浏览次数：9  
标签：typedef now int 969 long Codeforces Div include define

Preface

暑假最后几天疑似有点摆过头了，训练也没咋训，CF 也没咋打

这周末就是网络赛了，虽然名额早就满了，但还是得写写题找下手感不然要被学弟暴打了

这场由于是 Div.1/2 分场，补题就只写 Div.1 的题了

A. Iris and Game on the Tree

首先考虑快速计算一个 01 串的贡献，不难发现一段相同的连续段和带个字符等价，因此每个 01 串都和一个 01 交错的串等价

手玩一下会发现贡献仅和这个串开头和结尾的元素有关，因此不难想到如下策略：

若根节点的值确定，则两人的操作一定是先把叶子赋成相应的值，这种情况很 trivial

否则若根节点的值确定，此时统计下值为 \(0\) 的叶子以及值为 \(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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
int t,n,x,y,c[3],token; char s[N]; vector <int> v[N];
inline void DFS(CI now=1,CI fa=0)
{
	bool is_leaf=1;
	for (auto to:v[now]) if (to!=fa) DFS(to,now),is_leaf=0;
	if (now!=1&&!is_leaf&&s[now]=='?') ++token;
	if (is_leaf)
	{
		if (s[now]=='?') ++c[2]; else ++c[s[now]-'0'];
	}
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d",&n); c[0]=c[1]=c[2]=token=0;
		for (RI i=1;i<=n;++i) v[i].clear();
		for (RI i=1;i<n;++i)
		scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
		scanf("%s",s+1); DFS();
		if (s[1]!='?') { printf("%d\n",c[(s[1]-'0')^1]+(c[2]+1)/2); continue; }
		if (c[0]!=c[1]) printf("%d\n",max(c[0],c[1])+c[2]/2);
		else printf("%d\n",c[0]+(token%2?(c[2]+1)/2:c[2]/2));
	}
	return 0;
}

B. Iris and the Tree

经典 DFS 序性质题，想到了就很简单

考虑一条 \(x\to y\) 的边会在哪些点的 \(\operatorname{dist}(i,i\bmod n+1)\) 上，手玩下会发现只有 \(i=y-1\) 和 \(i=R(y)\) 两个点，其中 \(R(y)\) 为 \(y\) 子树内 DFS 序最大的点

同时对于一条路径，如果上面所有的边都确定了，那么它的贡献就是确定的；否则它的贡献为 \(w\) 减去这条路径之外的已经确定的值

把贡献的式子写出来，由于确定一条边只会改变两个点对应的贡献，因此可以很容易维护，简单预处理每个 \(\operatorname{dist}(i,i\bmod n+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 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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,w,anc[N][20],dep[N],len[N],R[N],x,y; vector <int> v[N];
inline void DFS(CI now=1)
{
	R[now]=now; for (auto to:v[now]) DFS(to),R[now]=max(R[now],R[to]);
}
inline int LCA(int x,int y)
{
	if (dep[x]<dep[y]) swap(x,y);
	for (RI i=19;i>=0;--i)
	if (dep[anc[x][i]]>=dep[y]) x=anc[x][i];
	if (x==y) return x;
	for (RI i=19;i>=0;--i)
	if (anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
	return anc[x][0];
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		scanf("%lld%lld",&n,&w); dep[1]=1;
		for (RI i=1;i<=n;++i) v[i].clear();
		for (RI i=2;i<=n;++i)
		{
			scanf("%lld",&anc[i][0]); dep[i]=dep[anc[i][0]]+1;
			v[anc[i][0]].push_back(i);
			for (RI j=0;j<19;++j)
			if (anc[i][j]) anc[i][j+1]=anc[anc[i][j]][j]; else break;
		}
		for (RI i=1;i<=n;++i)
		{
			int x=i,y=i%n+1;
			len[i]=dep[x]+dep[y]-2LL*dep[LCA(x,y)];
		}
		int ans=0,sum=0,unfilled=n; DFS();
		static int cnt[N],val[N];
		auto calc=[&](CI x)
		{
			if (cnt[x]==len[x]) return val[x];
			return w-(sum-val[x]);
		};
		for (RI i=1;i<=n;++i) cnt[i]=val[i]=0,ans+=calc(i);
		for (RI i=1;i<n;++i)
		{
			scanf("%lld%lld",&x,&y);
			ans-=calc(x-1)+calc(R[x]);
			if (++cnt[x-1]==len[x-1]) --unfilled; val[x-1]+=y;
			if (++cnt[R[x]]==len[R[x]]) --unfilled; val[R[x]]+=y;
			sum+=y; ans-=y*(unfilled-(cnt[x-1]!=len[x-1])-(cnt[R[x]]!=len[R[x]]));
			ans+=calc(x-1)+calc(R[x]);
			printf("%lld%c",ans," \n"[i==n-1]);
		}
		for (RI i=1;i<=n;++i) for (RI j=0;j<20;++j)
		if (anc[i][j]) anc[i][j]=0; else break;
	}
	return 0;
}

C. Eri and Expanded Sets

这题由于之前看队群聊天已经知道结论了，因此写的就很快

先考虑找一个有序数组合法的充要条件，我们注意到当两个数之差为偶数时才可以操作

从差分的角度看问题，我们最终的目标是让差分数组的每个值都为 \(1\)

同时一次操作相当于将原来的某个数除以 \(2\)，或者将差分数组中的两个位置作差

后者其实就等价于辗转相减法，因此合法的充要条件是差分数组的 \(\gcd\) 为 \(0\) 或者 \(2\) 的幂次

而且可以用归纳法证明，这个性质对于无序数组亦然成立，因此我们直接在原数组上处理即可

考虑固定右端点 \(r\) 时，找到最靠右的合法的左端点 \(l\)，显然 \([1,l]\) 都是合法的左端点取值

直接在线段树上二分，总复杂度 \(O(n\log n)\)

#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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=400005;
int t,n,a[N],pre[N],dlt[N],ret;
class Segment_Tree
{
	private:
		int val[N<<2];
	public:
		#define TN CI now=1,CI l=1,CI r=n-1
		#define LS now<<1,l,mid
		#define RS now<<1|1,mid+1,r
		inline void build(TN)
		{
			if (l==r) return (void)(val[now]=dlt[l]);
			int mid=l+r>>1; build(LS); build(RS);
			val[now]=__gcd(val[now<<1],val[now<<1|1]);
		}
		inline int query(CI beg,CI end,TN)
		{
			if (end<l||beg>r) return -1;
			if (beg<=l&&r<=end)
			{
				int tmp=__gcd(ret,val[now]);
				if ((tmp&-tmp)!=tmp)
				{
					ret=tmp; return -1;
				}
			}
			if (l==r) return l;
			int mid=l+r>>1,pos=query(beg,end,RS);
			if (pos!=-1) return pos;
			return query(beg,end,LS);
		}
		#undef TN
		#undef LS
		#undef RS
}SEG;
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d",&n); pre[1]=1;
		for (RI i=1;i<=n;++i) scanf("%d",&a[i]);
		for (RI i=2;i<=n;++i) pre[i]=(a[i]==a[i-1]?pre[i-1]:i);
		for (RI i=1;i<n;++i) dlt[i]=abs(a[i]-a[i+1]);
		if (n==1) { puts("1"); continue; }
		SEG.build(); LL ans=0;
		for (RI i=1;i<=n;++i)
		{
			ans+=i-pre[i]+1; ret=0;
			int pos=(1<=pre[i]-1?SEG.query(1,pre[i]-1):-1);
			if (pos!=-1) ans+=pos;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

D. Iris and Adjacent Products

首先不难发现修改总是将最大的数改为 \(1\)，假设现在已经完成的所有修改操作，怎样重排是最优的

手玩发现按照形如“最大、最小、次大、次小……”的方式交错排布一定最优

此时等价于将所有数从小到大排列为 \(a_1,a_2,\dots,a_m\)，对于 \(\forall i\in[1,m],a_i\times a_{m-i+1}\le k\)，不过要注意当数有奇数个时中间的那个数不需要考虑

考虑将这个条件等价转换，我们令 \(c(l,r)\) 表示在 \([l,r]\) 范围内数的数量，则上述条件等价于 \(\forall i\in[1,\sqrt k],c(1,i)\ge c(\lfloor\frac{k}{i+1}\rfloor+1,k)\)，为了处理上面奇数的 Corner Case，我们将两边的值都向 \(\lfloor\frac{n}{2}\rfloor\) 取 \(\min\) 即可

因此其实有用的值只有 \(\sqrt k\) 级别个，同时一次修改想到与将上式左侧所有数 \(+1\)，右侧所有数 \(-1\)

因此枚举每个 \(i\in[1,\sqrt k]\)，计算其对应位置需要修改的次数，取最大值即可

通过离线枚举+前缀和，可以做到 \(O((n+q)\times \sqrt k)\) 的时间，\(O(n+q)\) 的空间

#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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
int t,n,q,k,ans[N],l[N],r[N],b[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d%d",&n,&q,&k);
		for (RI i=1;i<=n;++i) scanf("%d",&b[i]);
		for (RI i=1;i<=q;++i) scanf("%d%d",&l[i],&r[i]),ans[i]=0;
		for (RI i=1;i*i<=k;++i)
		{
			static int c1[N],c2[N]; c1[0]=c2[0]=0;
			for (RI j=1;j<=n;++j)
			c1[j]=c1[j-1]+(b[j]<=i),c2[j]=c2[j-1]+(b[j]>k/(i+1));
			for (RI j=1;j<=q;++j)
			{
				int a=c1[r[j]]-c1[l[j]-1],b=c2[r[j]]-c2[l[j]-1],len=r[j]-l[j]+1;
				ans[j]=max(ans[j],min((b-a+1)/2,len/2-a));
			}
		}
		for (RI i=1;i<=q;++i) printf("%d%c",ans[i]," \n"[i==q]);
	}
	return 0;
}

Postscript

明后天争取再补一两场 CF，不然到时候网络赛怕是要唐得飞起

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

相关文章

  • Codeforces Round 971 (Div. 4) E 题解析
    #E题Klee'sSUPERDUPERLARGEArray!!!题目描述思路：对于这道题，首先观察到题目求的是最小可能值，而且数据的范围是1e9范围，所以首先可以考虑的方法就是O(logn)的方法，而适合求最值的方法无疑就是二分搜索，可以通过二分来不断缩小答案的区间......
  • Codeforces Round 969 (Div. 1 + 2)
    A将序列转化为\(01\)串，奇数为\(1\)，偶数为\(0\)。容易发现两个\(0\)不能分在同一组，于是答案的上限取决于奇数的个数，并且容易构造方案达到这个上界，随便做做就行。B将序列排序后，发现不管怎么加，大小顺序不变，记录下最大值按题意模拟。C根据基本数论知识可得，操作等价于加上......
  • Codeforces Round 971 (Div. 4)
    A-Minimize!inlinevoidsolve(){ inta,b; cin>>a>>b; cout<<b-a<<'\n';}B-osu!maniainlinevoidsolve(){ intn; cin>>n; vector<string>a(n); for(auto&x:a){ cin>>x......
  • Codeforces Round 971 (Div. 4) A-G1
    Ab-a#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;mt19937rnd(time(0));#defineintlonglongtypedeftuple<int,int,int>tp;#definexfirst#defineysecondtypedefpair<int,int>pii;typedefpair<double,double......
  • Educational Codeforces Round 169（A-D）
    A.ClosestPoint        给你一组点。你必须在这个集合中加入一个整数的点，使它与集合中现有的每一个点不同，并且它成为与集合中每一个点**最近的点。这可能吗？（输入yesorno）    一道思路题，简单思考可以发现，如果数字超过两个，那么这题答案就是NO。当两个数字的......
  • Codeforces Round 966 (Div. 3)
    ab略...C:map嵌套水过去的，复杂度\(nlog^2n\),感觉不如正解#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#definepiipair<int,int>#definemkpmake_pair#definefirfirst#definesecsecond#definepbpush_backconstintmaxn=2e5+100;......
  • Codeforces Round 970 (Div. 3)（VP）
    A.Sakurako'sExam总结：一看n<=20,直接暴力+剪枝即可inlinevoidsolve(){ inta,b; cin>>a>>b; vector<int>d; d.reserve(a+b); while(a--){ d.push_back(1); } while(b--){ d.push_back(2); } autodfs=[&](auto&......
  • Codeforces Round 968 (Div. 2)
    vp的，老规矩跳过abC:根据题意我们知道三个不一样的字母连续放一定可以，然后观察样例发现好像把两个不同的字母轮流放也可以。进一步猜测（瞎猜的)发现这个好像只要把不同的挨个放进去就行了（本来以为可能要按数量排序但是似乎根本不用），最后剩下的全放一起也没事。然后就过了。#includ......
  • Codeforces Round 970 div3
    CodeforcesRound970div3错过的一场比赛,第二天早晨VP,题目的通过率还挺奇怪A.Sakurako'sExamhttps://codeforces.com/contest/2008/problem/A题意:有a个1和b个2的数组,在1和2前面增添加减号,判断是否能让结果为0思路:1个2需要2个1进行填补,不如先让2自己进行消去,如......
  • Codeforces Round 969 Div.2+Div.1
    A.Dora'sSet注意到任意两个偶数的\(\gcd\)都大于\(1\)，因此选择的三个数中至多一个偶数，而注意到相邻的奇数一定互质，因此每次选两个奇数一个偶数，答案=奇数的个数÷2点击查看代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineullunsigned......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99