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

Codeforces Round 936 (Div. 2)

时间：2024-03-27 19:24:11浏览次数：21  
标签：typedef int CI Codeforces long Div include 936 define

Preface

懒狗闪总开完组会不打CF直接滚去睡觉了可海星，感觉我好像退化成我们队训练最少的人了

赛后补了下发现这场题竟然都会做，不过F不知道是我实现有问题常数大得一批加了读优才惊险卡过

A. Median of an Array

签到，找到中位数后面与它相同的数的个数即可

#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,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		int ans=1; for (sort(a+1,a+n+1),i=(n+1)/2+1;i<=n;++i)
		if (a[i]==a[(n+1)/2]) ++ans; else break;
		printf("%d\n",ans);
	}
	return 0;
}

B. Maximum Sum

找出最大子段和\(S\)后，显然每次就是把\(S\)插入到能和原来的最大子段和一起统计的位置

最后答案就是\((2^k-1)\times S+\sum_{i=1}^n 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 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,mod=1e9+7;
int t,n,k,a[N];
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d",&n,&k),i=1;i<=n;++i) scanf("%d",&a[i]);
		LL cur=0,mx=0,sum=0; for (i=1;i<=n;++i) cur=max(cur+a[i],0LL),mx=max(mx,cur),sum+=a[i];
		printf("%d\n",(1LL*(quick_pow(2,k)-1)*(mx%mod)%mod+sum%mod+mod)%mod);
	}
	return 0;
}

C. Tree Cutting

最小值最大一眼二分答案\(x\)，考虑如何check

不妨选择任意一个点为根把树变成有根树，考虑从叶子往上贪心，如果存在某个点子树大小\(\ge x\)就直接砍掉它和父亲的边

不难发现这样一定是最优的，最后检验下是否砍掉了\(k\)条边以及最后顶上留下的部分大小是否\(\ge x\)即可

同时显然这个贪心过程对于任意点为根都能跑出正确的策略，因此可以随便选

#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,k,x,y,cnt,all,sz[N]; vector <int> v[N];
inline void DFS(CI lim,CI now=1,CI fa=0)
{
	if (cnt==k) return; sz[now]=1;
	for (auto to:v[now]) if (to!=fa)
	{
		DFS(lim,to,now); sz[now]+=sz[to];
		if (cnt==k) return;
	}
	if (fa==0) return; if (sz[now]>=lim) ++cnt,all-=sz[now],sz[now]=0;
	if (cnt==k) return;
}
inline bool check(CI x)
{
	all=n; cnt=0; DFS(x); return cnt==k&&all>=x;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d",&n,&k),i=1;i<=n;++i) v[i].clear();
		for (i=1;i<n;++i) scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
		int l=1,r=n/(k+1),mid,ret; while (l<=r)
		if (check(mid=l+r>>1)) ret=mid,l=mid+1; else r=mid-1;
		printf("%d\n",ret);
	}
	return 0;
}

D. Birthday Gift

经典二进制操作，上来先考虑从高到低依次处理

不难发现对于某个二进制位\(2^p\)，若序列中这一位为\(1\)的数有奇数个，则不管怎么划分最后这一位上一定为\(1\)

否则如果这一位为\(1\)的数有偶数个，只要把这些数偶数个分为一组即可，由于这题要求划分数量最多，因此显而易见的把相邻的两两合并即可

注意到在任意一个时刻，如果我们凑出了\(<x\)的数那么直接退出统计答案一定最优，否则如果前缀相等则还需要往后讨论后面的位带来的影响

暴力处理分组过程，复杂度\(O(n\log 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 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,ans;
inline void solve(vector <int> a,CI p=30)
{
	if (p<0) return (void)(ans=max(ans,(int)a.size()));
	RI i,j; vector <int> pos;
	for (i=0;i<a.size();++i) if ((a[i]>>p)&1) pos.push_back(i);
	if (pos.size()%2==1&&((x>>p)&1)==0) return;
	if (pos.size()%2==1&&((x>>p)&1)==1) return solve(a,p-1);
	vector <int> rmv(a.size()); vector <int> b,c=a;
	for (i=0;i<pos.size();i+=2)
	for (j=pos[i]+1;j<=pos[i+1];++j)
	rmv[j]=1,c[pos[i]]^=c[j];
	for (i=0;i<c.size();++i) if (!rmv[i]) b.push_back(c[i]);
	if (((x>>p)&1)==0) return solve(b,p-1);
	ans=max(ans,(int)b.size()); return solve(a,p-1);
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%d%d",&n,&x); vector <int> a(n);
		for (i=0;i<n;++i) scanf("%d",&a[i]);
		ans=-1; solve(a); printf("%d\n",ans);
	}
	return 0;
}

E. Girl Permutation

感觉算是我最近见到的最简单的计数题了，一眼秒的那种

首先如果前缀最大最后的位置和后缀最大第一个位置的值不同，则显然无解，同时还有些trivial的无解情况也一起顺手判掉

否则我们可以确定最大数\(n\)所在的位置\(x\)，首先需要一个把剩下的\(n-1\)个数分到两边的方案数，就是\(C_{n-1}^{x-1}\)

然后此时每一边的问题独立，以前缀这一段为例

我们从后往前枚举前缀最大值的位置，显然当前最大的数的位置唯一确定了，但该位置到\(x\)这一段中间的数方法是任意的

刚开始傻逼了这里乘了个组合数上去，后面过不了样例才发现原来是还得乘一个随便放顺序的排列数

后缀的处理同理，最后把每部分的方案数乘起来即可

#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=200005,mod=1e9+7;
int t,n,m1,m2,fact[N],ifac[N];
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
	RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
	for (ifac[n]=quick_pow(fact[n]),i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
inline int C(CI n,CI m)
{
	if (n<0||m<0||n<m) return 0;
	return 1LL*fact[n]*ifac[m]%mod*ifac[n-m]%mod;
}
inline int A(CI n,CI m)
{
	if (n<0||m<0||n<m) return 0;
	return 1LL*fact[n]*ifac[n-m]%mod;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t),init(2e5);t;--t)
	{
		RI i; scanf("%d%d%d",&n,&m1,&m2); vector <int> pre(m1),suf(m2);
		for (i=0;i<m1;++i) scanf("%d",&pre[i]);
		for (i=0;i<m2;++i) scanf("%d",&suf[i]);
		if (pre[0]!=1||suf[m2-1]!=n) { puts("0"); continue; }
		if (pre[m1-1]!=suf[0]) { puts("0"); continue; }
		int ans=C(n-1,suf[0]-1),cur;
		for (cur=suf[0]-1,i=m1-2;i>=0;--i)
		ans=1LL*ans*A(cur-1,pre[i+1]-pre[i]-1)%mod,cur-=pre[i+1]-pre[i];
		for (cur=n-suf[0],i=1;i<m2;++i)
		ans=1LL*ans*A(cur-1,suf[i]-suf[i-1]-1)%mod,cur-=suf[i]-suf[i-1];
		printf("%d\n",ans);
	}
	return 0;
}

F. Nobody is needed

很套路的一个题

首先对于只选一个数的情况特别考虑，然后我们发现对于某个固定的右端点，其合法的左端点选法是$\log $级别的

因此如果我们把以\(l\)为开头，\(r\)为结尾的选法的方案数统计出来，最后就是个询问\([L,R]\)包含的所有子区间的贡献和，这个是个经典的扫描线问题

现在的问题是如何计算\(l,r\)的贡献，这个也很好办，我们对于每个\(r\)按照\(l\)降序DP一下即可

具体实现看代码，复杂度\(O(n\log^2 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 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=1e6+5;
int t,n,q,a[N],pos[N],ans[N],l,r; vector <int> frac[N]; vector <pi> evt[N];
#define Tp template <typename T>
class FileInputOutput
{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
        #define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=Fout)++=ch))
        char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[30];
    public:
        inline FileInputOutput(void) { Ftop=Fout; Fend=Fout+S; }
        Tp inline void read(T& x)
        {
            x=0; char ch; while (!isdigit(ch=tc()));
            while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
        }
        Tp inline void write(T x,const char ch='\n')
        {
        	if (x<0) x=-x,pc('-');
            RI ptop=0; while (pt[++ptop]=x%10,x/=10);
            while (ptop) pc(pt[ptop--]+48); pc(ch);
        }
        inline void flush(void)
        {
            fwrite(Fout,1,Ftop-Fout,stdout);
        }
        #undef tc
        #undef pc
}F;
inline void init(CI n)
{
	for (RI i=1;i<=n;++i) for (RI j=i;j<=n;j+=i) frac[j].push_back(i);
}
class Tree_Array
{
	private:
		int bit[N];
	public:
		#define lowbit(x) (x&(-x))
		inline void init(CI n)
		{
			for (RI i=1;i<=n;++i) bit[i]=0;
		}
		inline void add(RI x,CI y)
		{
			for (;x;x-=lowbit(x)) bit[x]+=y;
		}
		inline int get(RI x,int ret=0)
		{
			for (;x<=n;x+=lowbit(x)) ret+=bit[x]; return ret;
		}
		#undef lowbit
}BIT;
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (F.read(t),init(1e6);t;--t)
	{
		RI i,j,k; for (F.read(n),F.read(q),i=1;i<=n;++i)
		F.read(a[i]),pos[a[i]]=i,evt[i].clear();
		for (i=1;i<=n;++i)
		{
			vector <int> lpos;
			for (auto x:frac[a[i]])
			if (pos[x]<i) lpos.push_back(pos[x]);
			vector <int> dp(lpos.size());
			sort(lpos.begin(),lpos.end());
			for (j=(int)lpos.size()-1;j>=0;--j)
			for (dp[j]=1,k=j+1;k<lpos.size();++k)
			if (a[lpos[k]]%a[lpos[j]]==0) dp[j]+=dp[k];
			for (j=0;j<lpos.size();++j)
			evt[i].push_back({lpos[j],dp[j]});
		}
		for (i=1;i<=q;++i) F.read(l),F.read(r),ans[i]=r-l+1,evt[r].push_back({l,-i});
		for (BIT.init(n),i=1;i<=n;++i)
		for (auto [x,y]:evt[i]) if (y>0) BIT.add(x,y); else ans[-y]+=BIT.get(x);
		for (i=1;i<=q;++i) F.write(ans[i]," \n"[i==q]);
	}
	return F.flush(),0;
}

Postscript

接下来几天要忙CCPC Final的事情，估计没啥时间写题了的说

标签：typedef,int,CI,Codeforces,long,Div,include,936,define
From： https://www.cnblogs.com/cjjsb/p/18100024

相关文章

  • Codeforces Round 915 (Div. 2) D
    CyclicMEX题面翻译对于一个长为\(n\)的排列\(p\)，定义其权值为\(\sum_{i=1}^n\operatorname{mex}_{j=1}^ip_j\)，也就是\(p_1\simp_i\)中没有出现过的最小自然数的和。然后你可以对这个排列进行移位操作，问最大权值。题目描述Foranarray$a$,defineitscostas$......
  • CodeForces 1936E Yet Yet Another Permutation Problem
    洛谷传送门CF传送门首先设\(a_i=\max\limits_{j=1}^ip_j\)，\(b_i=\max\limits_{j=1}^iq_j\)。直接容斥，钦定有多少值不同的\(a_i\)使得\(a_i=b_i\)。然后再把钦定的每种值转化成每种值第一次使得\(a_i=b_i\)的位置\(i\)。也就是说我们现在要钦定一些位置，......
  • Div4 VP总结
    CodeforcesRound799(Div.4)E（最长子区间）基本思路求满足s的最长子区间。错误思路分析想用双指针左右贪心模拟题目要求删前或后的数（但在面对前后两个相等的时候，删前删后没有无后效性）简单暴力枚举子区间长度（显然在n=1e5的时候t了）正确思路虽然也是暴力枚举子区间，但有做......
  • css实现弹出的div显示在屏幕中间
    主要代码如下：.info{width:90vw;height:102vw;display:block;position:fixed;z-index:999;top:50%;left:50%;transform:translate(-50%,-50%);border-radius:14px;}.info-header{......
  • Windows Packet Divert（WinDivert）是一个适用于Windows 10、Windows 11和Windows Server
    WindowsPacketDivert（WinDivert）是一个适用于Windows10、Windows11和WindowsServer的用户模式数据包捕获和重定向工具。WinDivert允许用户模式应用程序捕获/修改/丢弃发送到/从Windows网络堆栈的网络数据包。总之，WinDivert可以：捕获网络数据包过滤/丢弃网络数据包嗅探......
  • Codeforces Round 936 (Div. 2) E
    SofiaandStrings题面翻译\(t\)组数据。每一次测试，有长度为\(n\)的序列\(s\)，长度为\(m\)的序列\(t\)。你可以对\(s\)进行两种操作：删除\(s_i,1\lei\le|s|\)（\(s\)从\(1\)开始标号）.将\(s_l,s_{l+1},\dots,s_r\)排序（\(1\lel\ler\le|s|\)）。上面\(|s|......
  • CF1935 Codeforces Round 932 (Div. 2)
    C.MessengerinMAC给两个数组a,b和一个整数L.寻找一个关于a,b下标的序列p,使得\(\suma_{p_i}+\sum|b_{p_i}-b_{p_{i+1}}|\leqL\)SolutionKey1:按照b从小到大排序一定是最优的.Key2:固定\(b_l\),\(b_r\),那么\(\sum^r_l|b_{p_i}-b_{p_{i+1}}|=b_r-b_l......
  • codeforces div3 935
    Problem-E-Codeforces题解：一道二分糖题首先我们先在原序列跑一遍题目给的二分，然后跑出最后的l点我们稍微思考一下，这个l这个点一定小于或者等于x为什么呢一个在这个二分里，如果最后的点是大于x的那么必定被r拿走，因为判断上l只能接收比x小的地点所以我们知道l以后，要么就是l=......
  • cfEduRound163div2--D题解
    D-TandemRepeats?题意:做法：因为字符串长度较少，可以考虑枚举。or--动态规划voidsolve(){//D枚举//枚举！！！！！！！！！！stringstr;cin>>str;intn=str.size(),ans=0;for(inti=1;i<=n/2;i++){//枚举一半!!!intcnt=0;for(intj=0;......
  • SMU Winter 2024 div2 ptlks的周报Week 6（3.18-3.24）
    不难想到，要求环的期望，只需求出所有可能的环的长度总和和不相邻点对的组数。而边数确定，则只需求环的总长。对于两个不相邻的点x，y，所形成的环的长度等于两点深度之差加一，\(\vertdp[x]-dp[y]\vert+1\)，不妨令x为根节点，则只需求所有节点的深度之和，再减去相邻的点，最后对树进行换根dp，输出......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99