首页 > 其他分享 >2024暑假集训测试29

2024暑假集训测试29

时间:2024-08-20 21:37:59浏览次数:12  
标签:int void 29 Tp 2024 read inline 集训 define

前言

image

今上午在家打的,下午回的学校,话说啥时候改成 \(7\) 点开始了?

T1 是板子但是没打过标记永久化,想了一段时间想起树状数组维护区间求和操作于是用主席树实现了这个,赛时 T1 不给大样例所以调了挺长时间才放心;T2 想了一会儿没想出来就先打 T3 了,T3 想了一会儿胡了个 \(n^2\) DP 回来也没时间打了,因为时间少了半小时,刚把 T4 样例交上去就结束了。

T1 可持久化线段树

做法一

正常的标记永久化主席树,时空复杂度均为 \(O(n\log n)\)。

点击查看代码
#include<bits/stdc++.h>
#define ll long long 
#define endl '\n'
#define sort stable_sort
#define l(p) t[p].l
#define r(p) t[p].r
#define val(p) t[p].val
#define add(p) t[p].add
using namespace std;
const int N=1e5+10,M=3e6+10,P=998244353;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
	for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,m,tot,tim,a[N],rt[N];
struct aa {int l,r; ll val,add;}t[M];
void build(int &p,int l,int r)
{
	p=++tot;
	if(l==r) {val(p)=a[l]; return ;}
	int mid=(l+r)>>1;
	build(l(p),l,mid),build(r(p),mid+1,r);
	val(p)=(val(l(p))+val(r(p)))%P;
}
void change(int &now,int last,int l,int r,int vl,int vr,int d)
{
	now=++tot;
	t[now]=t[last],(val(now)+=1ll*(min(r,vr)-max(l,vl)+1)*d%P)%=P;
	if(vl<=l&&vr>=r) {(add(now)+=d)%=P; return ;}
	int mid=(l+r)>>1;
	if(vl<=mid) change(l(now),l(last),l,mid,vl,vr,d);
	if(vr>mid) change(r(now),r(last),mid+1,r,vl,vr,d);
}
ll ask(int p,int l,int r,int vl,int vr)
{
	if(vl<=l&&vr>=r) return val(p);
	int mid=(l+r)>>1,ans=0;
	if(vl<=mid) (ans+=ask(l(p),l,mid,vl,vr))%=P;
	if(vr>mid) (ans+=ask(r(p),mid+1,r,vl,vr))%=P;
	return (ans+1ll*add(p)*(min(r,vr)-max(l,vl)+1)%P)%P;
}
signed main()
{
	read(n,m);
	for(int i=1;i<=n;i++) read(a[i]);
	build(rt[0],1,n);
	for(int i=1,op,l,r,x;i<=m;i++)
	{
		read(op);
		if(op==1) 
		{
			read(l,r,x),tim++;
			change(rt[tim],rt[tim-1],1,n,l,r,x);
		}
		if(op==2)
		{
			read(l,r);
			write(ask(rt[tim],1,n,l,r)),puts("");
		}
		if(op==3) read(x),tim-=x;
	}
}     

做法二

  • 树状数组区间求和详见:oi-wiki

考虑树状数组的区间求和操作,将其转化为前缀和的可差分信息,从而单点修改单点查询,用主席树实现这个即可,时空复杂度均为 \(O(n\log n)\)。

点击查看代码
#include<bits/stdc++.h>
#define ll long long 
#define endl '\n'
#define sort stable_sort
#define l(p) t[p].l
#define r(p) t[p].r
#define val(p) t[p].val
using namespace std;
const int N=1e5+10,M=5e6+10,P=998244353;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
	for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,m,tim,tot,rt1[N],rt2[N];
ll a[N];
struct aa {int l,r; ll val;}t[M];
void change(int &now,int last,int l,int r,int x,ll d)
{
	now=++tot;
	t[now]=t[last],(val(now)+=d)%=P;
	if(l==r) return ;
	int mid=(l+r)>>1;
	if(x<=mid) change(l(now),l(last),l,mid,x,d);
	else change(r(now),r(last),mid+1,r,x,d);
}
ll ask(int p,int l,int r,int x)
{
	if(l==r) return val(p);
	int mid=(l+r)>>1;
	if(x<=mid) return ask(l(p),l,mid,x);
	else return (ask(r(p),mid+1,r,x)+val(l(p)))%P;
}
ll ask(int x)
{
	return (a[x]+ask(rt1[tim],1,n,x)*(x+1)%P-ask(rt2[tim],1,n,x)+P)%P;
}
signed main()
{
	read(n,m);
	for(int i=1;i<=n;i++) read(a[i]),(a[i]+=a[i-1])%=P;
	for(int i=1,op,l,r;i<=m;i++)
	{
		read(op); ll x;
		if(op==1) 
		{
			read(l,r,x),tim++;
			rt1[tim]=rt1[tim-1],rt2[tim]=rt2[tim-1];
			change(rt1[tim],rt1[tim],1,n,l,x);
			change(rt1[tim],rt1[tim],1,n,r+1,(-x+P)%P);
			change(rt2[tim],rt2[tim],1,n,l,x*l%P);
			change(rt2[tim],rt2[tim],1,n,r+1,(-x*(r+1)%P+P)%P);
		}
		if(op==2)
		{
			read(l,r);
			write((ask(r)-ask(l-1)+P)%P),puts("");
		}
		if(op==3) read(x),tim-=x;
	}
}

做法三

因为他只是撤销,所以每个操作最多进行一遍再撤销一遍,所以树状数组暴力撤销即可,空间复杂度可以达到 \(O(n)\),时间还是 \(O(n\log n)\),因为树状数组常熟小所以跑得巨快。

点击查看代码
#include<bits/stdc++.h>
#define ll long long 
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=5e5+10,P=998244353;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
	for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,m,t,a[N],c1[N],c2[N];
struct aa {int l,r,x;}e[N];
int mod(int x,int y) {ll res=x+y; return res>=P?res-P:res;}
int lowbit(int x) {return x&-x;}
void add(int x,int d)
{
	for(int i=x;i<=n;i+=lowbit(i)) 
		c1[i]=mod(c1[i],d),c2[i]=mod(c2[i],1ll*x*d%P);
}
int ask(int x)
{
	int ans1=0,ans2=0;
	for(int i=x;i;i-=lowbit(i)) ans1=mod(ans1,c1[i]);
	for(int i=x;i;i-=lowbit(i)) ans2=mod(ans2,c2[i]);
	return mod(1ll*ans1*(x+1)%P,P-ans2);
}
signed main()
{
	read(n,m);
	for(int i=1;i<=n;i++) read(a[i]),a[i]=mod(a[i],a[i-1]);
	for(int i=1,op,l,r,x;i<=m;i++)
	{
		read(op);
		switch (op)
		{
			case 1: 
				read(l,r,x),e[++t]={l,r,x};
				add(l,x),add(r+1,P-x);
				break;
			case 2:
				read(l,r);
				write(mod(mod(a[r],P-a[l-1]),mod(ask(r),P-ask(l-1)))),puts("");
				break;
			case 3:
				read(x);
				while(x--)
				{
					int l=e[t].l,r=e[t].r,x=e[t].x;
					add(l,P-x),add(r+1,x);
					t--;
				}
				break;
		}
	}
}

T2 Little Busters !

转化题面,所剩所有 lun 边均在双连通分量里,所有 qie 边用来连接这些双连通分量,且最终图联通。

由此先只连接 lun 边跑 tarjan 保留合法的边,之后加入 qie 边并查集维护图连通即可。

  • 根据 Shadow 的论述,双连通分量本质是有向图的环,由此直接在无向图上跑强连通分量就是双连通分量。
点击查看代码
#include<bits/stdc++.h>
#define ll long long 
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e5+10;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
	for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,m,tot,cnt,f[N],dfn[N],low[N],belong[N];
bool ins[N];
stack<int>s;
vector<int>e[N];
vector<pair<int,int> >lun,qie,ans;
int find(int x) {return x==f[x]?x:f[x]=find(f[x]);}
void tarjan(int x,int fa)
{
	dfn[x]=low[x]=++tot,ins[x]=1,s.push(x);
	for(int y:e[x]) if(y!=fa)
	{
		if(dfn[y]==0) tarjan(y,x),low[x]=min(low[x],low[y]);
		else if(ins[y]==1) low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x])
	{
		int k=0; cnt++;
		while(x!=k) k=s.top(),s.pop(),ins[k]=0,belong[k]=cnt;
	}
}
signed main()
{
	read(n,m); char op[4];
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1,x,y;i<=m;i++)
	{
		read(x,y); scanf("%s",op);
		if(op[0]=='L') 
		{
			e[x].push_back(y),e[y].push_back(x);
			lun.push_back(make_pair(x,y));
		}
		else qie.push_back(make_pair(x,y));
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
	for(auto pos:lun) if(belong[pos.first]==belong[pos.second]) 
		ans.push_back(pos);
	for(auto pos:qie)
	{
		int x=find(belong[pos.first]),y=find(belong[pos.second]);
		if(x!=y) f[y]=x,cnt--,ans.push_back(pos);
	}
	if(cnt==1) 
	{
		puts("YES"),write(ans.size()),puts("");
		for(auto pos:ans) write(pos.first,pos.second),puts("");
	}
	else puts("NO");
} 

T3 魔卡少女樱

  • 原题:[ABC276G] Count Sequences

  • 部分分 \(40pts\):\(O(n^3)\) DP。

  • 部分分 \(65pts\):\(O(n^2)\) DP,就是 \(n^3\) 的加个前缀和优化。

  • 正解:

    考虑 \(a_i\) 的差分数组 \(b_i\),\(b_i\) 可以表示为 \(3k_i+r_i\),有 \(r_1\in\{0,1,2\},r_i\in\{1,2\}\)。

    对于除了 \(r_1\) 以外的其他 \(n-1\) 个 \(r_i\),设其中 \(2\) 的个数为 \(cnt\),那么 \(\sum\limits_{i=1}^nr_i=r_1+cnt+n-1\)。

    不难发现 \(\sum\limits_{i=1}^nb_i\le m\),回去考虑 \(k_i\) 的贡献,只考虑除了 \(k_1\) 以外其他 \(n-1\) 个 \(k_i\),有 \(\sum\limits_{i=1}^n3k_i\le m-\sum\limits_{i=1}^nr_i\),所以 \(\sum\limits_{i=1}^nk_i\le \lfloor\frac{m-\sum\limits_{i=1}^nr_i}{3}\rfloor\),即 \(n-1\) 个位置去分配,可转化为隔板法问题解决。

    综上所述,答案为 \(\sum\limits_{r_1=0}^{2}\sum\limits_{i=0}^{n-1}C_{n-1}^{i}\sum\limits_{j=0}^{\lfloor\frac{m-(r_1+i+n-1)}{3}\rfloor}C_{n-1+j}^{n-1}\),后半部分可以前缀和优化,最终复杂度为线性。

    点击查看代码
    #include<bits/stdc++.h>
    #define ll long long 
    #define endl '\n'
    #define sort stable_sort
    using namespace std;
    const int N=1.4e7+10,M=4e6+10,P=998244353;
    template<typename Tp> inline void read(Tp&x)
    {
    	x=0;register bool z=true;
    	register char c=getchar();
    	for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    	for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    	x=(z?x:~x+1);
    }
    template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
    template<typename Tp> inline void wt(Tp x)
    {if(x>9)wt(x/10);putchar((x%10)+'0');}
    template<typename Tp> inline void write(Tp x)
    {if(x<0)putchar('-'),x=~x+1;wt(x);}
    template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
    int n,m,ans,jc[N],inv[N],s[M];
    int add(int x,int y) {ll res=x+y; return res>=P?res-P:res;}
    int mul(int x,int y) {return 1ll*x*y%P;}
    int qpow(int a,int b)
    {
    	int res=1;
    	for(;b;b>>=1)
    	{
    		if(b&1) res=mul(res,a);
    		a=mul(a,a);
    	}
    	return res;
    }
    int C(int n,int m)
    {
    	if(m>n) return 0;
    	if(m==0||m==n) return 1;
    	return mul(mul(jc[n],inv[n-m]),inv[m]);
    }
    signed main()
    {
    	read(n,m); int k=n+(m-n+1)/3;
    	jc[0]=inv[0]=s[0]=1;
    	for(int i=1;i<=k;i++) jc[i]=mul(jc[i-1],i);
    	inv[k]=qpow(jc[k],P-2);
    	for(int i=k-1;i>=1;i--) inv[i]=mul(inv[i+1],i+1);
    	for(int i=1;i<=(m-n+1)/3;i++) s[i]=add(s[i-1],C(i+n-1,n-1));
    	for(int i=0;i<=2;i++)
    		for(int j=0;j<=n-1&&j+n-1+i<=m;j++)
    			ans=add(ans,mul(C(n-1,j),s[(m-n+1-i-j)/3]));
    	write(ans);
    }
    

T4 声之形

不会。

总结

T2 再给点时间或许能想出来?不确定但是确实应该想出来的,病刚好有点没劲儿,回学校看电脑屏幕好大啊,机械键盘都有点用不习惯了(在家用笔记本用的)。

标签:int,void,29,Tp,2024,read,inline,集训,define
From: https://www.cnblogs.com/Charlieljk/p/18370367

相关文章

  • CF293E Close Vertices
    对于这种树上路径统计问题,一个经典解法就是点分治。如果没有两个限制,还是很简单的,对于单个限制,使用树状数组来解决就行了。但是这道题目要求两个限制,有点像二维偏序,但不完全是。可以说是分成了几个段,每个段之间求二维偏序,而要求段内不能产生贡献。如果这么表述这个问题的话,那就......
  • 【SPIE 出版,最后5天!】第五届信号处理与计算机科学国际学术会议(SPCS 2024,8月24线上)
    第五届信号处理与计算机科学国际学术会议(SPCS2024)将于2024年8月23-25日在中国哈尔滨举行。会议主要围绕信号处理与计算机科学等研究领域展开讨论。会议旨在为从事信号处理与计算机科学研究的专家学者、工程技术人员、技术研发人员提供一个共享科研成果和前沿技术,了解......
  • 2024浙江省信息通信行业职业技能竞赛信息安全测试员竞赛CTF比赛
    浙江省信息通信行业职业技能竞赛信息安全测试员竞赛CTF比赛MISC部分Author:Ns100kUpFrom:极安云科-服务中心Data:2024/08/07Copyright:本内容版权归属极安云科,未经授权不得以任何形式复制、转载、摘编和使用。培训、环境、资料、考证公众号:Geek极安云科网络安全群:62403......
  • 暑假集训CSP提高模拟25
    赛时rank5,T1100,T285,T350,T45T2Tarjan意外挂了,在Tarjan里判割边会挂?T3\(O(nm^2)\)暴力能拿50?特判样例能拿60?可持久化线段树没啥好说的,主席树板子。点此查看代码#include<bits/stdc++.h>#include<bits/extc++.h>//usingnamespace__gnu_pbds;//usingnames......
  • 2024.8.20
    #include<stdio.h>#include<stdio.h>#include<sys/socket.h>#include<netinet/in.h>#include<arpa/inet.h>#include<sys/types.h>#include<string.h>#include<unistd.h>#include<stdlib.h>#include......
  • 【C++二分查找 前缀和 】1292. 元素和小于等于阈值的正方形的最大边长
    本文涉及的基础知识点C++二分查找C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频LeetCode1292.元素和小于等于阈值的正方形的最大边长给你一个大小为mxn的矩阵mat和一个整数阈值threshold。请你返回元素总和小于或等于阈值的正方形区......
  • 2024年“研究生科研素养提升”考试答案分享
    1、下列哪个数据库文献不包含在知网研学平台里面()。 A、期刊文献✓ B、标准 C、硕博文献 D、年鉴文献您的答案: B 参考答案: B 收藏答案解析:知网研学平台数据库文献主要包括期刊、硕博、年签、报纸、会议。2、下列选项中,不属于全文数据库的是() A、Springerlin......
  • 20240820(周二)AH股行情总结:A股三大指数收跌近1%,游戏传媒板块大涨,工行超中国移动成市值
    A股三大股指集体下挫,创业板指跌1.34%。国债期货收盘多数上涨,30年期主力合约涨0.22%。工商银行股价再创历史新高,盘中市值超过中国移动。“黑神话”概念股大涨,浙版传媒涨停,华谊兄弟涨超10%,新迅达20CM涨停。周二,A股三大指数均收跌近1%受《黑神话:悟空》大热带动,A股游戏、传媒板......
  • 2024牛客多校第10场
    10Bstd::pair(B)模拟题,没什么难度,就是有点恶心。题解提到的二叉树做法赛时也想过,但写着不太顺手就放弃了,转而写了个类似括号匹配的解法。for(inti=1;i<=n;i++){strings;cin>>c[i]>>s;mp[s]=i;}while(q--){......
  • 2024.8.20(playbook剧本安装nginx、roles)
    一、playbook 剧本安装nginx[root@m0~]#mkdir/etc/ansible/playbook[root@m0~]#vim/etc/ansible/playbook/nginx.yml----hosts:group02remote_user:roottasks:-name:卸载httpdyum:......