程序员经验分享-hwhale

Atcoder AGC005 题解

2023-05-16

A - STring

用类似括号匹配的方法搞一下即可…

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int N=200005;
char s[N];int len,js=0,ans;
int main()
{
	scanf("%s",s+1);
	len=strlen(s+1);
	for(RI i=1;i<=len;++i)
		if(s[i]=='S') ++js;
		else {
			if(js) --js;
			else ++ans;
		}
	printf("%d\n",ans+js);
	return 0;
}

B - Minimum Sum

额，用单调栈找到每个元素左右第一个比它小的元素，就能知道左端点在哪个区间取右端点在哪个区间取，这个元素会是最小值，然后处理每个元素的贡献即可。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
	int q=0;char ch=' ';
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
	return q;
}
typedef long long LL;
const int N=200005;
int n,top,L[N],R[N],a[N],st[N];LL ans;
int main()
{
	n=read();
	for(RI i=1;i<=n;++i) a[i]=read();
	for(RI i=1;i<=n;++i) {
		while(top&&a[st[top]]>a[i]) --top;
		L[i]=(top?st[top]+1:1),st[++top]=i;
	}
	top=0;
	for(RI i=n;i>=1;--i) {
		while(top&&a[st[top]]>a[i]) --top;
		R[i]=(top?st[top]-1:n),st[++top]=i;
	}
	for(RI i=1;i<=n;++i) ans+=1LL*(i-L[i]+1)*(R[i]-i+1)*a[i];
	printf("%lld\n",ans);
	return 0;
}

C - Tree Restoring

我们知道，树上一个点的最远点，一定是直径的两个端点之一。所以首先我们找出直径的长度 L L L。

如果 L L L是偶数，那么 a i = L 2 a_i=\frac{L}{2} ai​=2L​的点只能有一个， L 2 &lt; a i ≤ L \frac{L}{2} &lt;a_i \leq L 2L​<ai​≤L的点至少要有两个，如果有更多，则可以通过连接直径上 a j = a i − 1 a_j=a_i-1 aj​=ai​−1的点 j j j来达成目标。而 a i &lt; L 2 a_i&lt; \frac{L}{2} ai​<2L​的点不能存在。

如果 L L L是奇数，那么 a i = ⌈ L 2 ⌉ a_i=\lceil \frac{L}{2} \rceil ai​=⌈2L​⌉的点只能有两个， ⌈ L 2 ⌉ &lt; a i ≤ L \lceil \frac{L}{2} \rceil &lt;a_i \leq L ⌈2L​⌉<ai​≤L至少有两个， a i &lt; ⌈ L 2 ⌉ a_i&lt;\lceil \frac{L}{2} \rceil ai​<⌈2L​⌉不能存在。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int N=105;
int a[N],b[N],n,mx;
int main()
{
	scanf("%d",&n);
	for(RI i=1;i<=n;++i) scanf("%d",&a[i]),mx=max(mx,a[i]),++b[a[i]];
	if(mx&1) {
		for(RI i=mx;i>=(mx+1)/2;--i)
			if(b[i]<2) {puts("Impossible");return 0;}
		for(RI i=1;i<(mx+1)/2;++i)
			if(b[i]) {puts("Impossible");return 0;}
		if(b[(mx+1)/2]>2) {puts("Impossible");return 0;}
	}
	else {
		for(RI i=mx;i>mx/2;--i)
			if(b[i]<2) {puts("Impossible");return 0;}
		for(RI i=1;i<mx/2;++i)
			if(b[i]) {puts("Impossible");return 0;}
		if(b[mx/2]!=1) {puts("Impossible");return 0;}
	}
	puts("Possible");
	return 0;
}

D - ~K Perm Counting

考虑容斥，令 g i g_i gi​表示钦定 i i i个点不合法，其他点随便的方案数。

答案就是 ∑ i = 0 n ( − 1 ) i + 1 g i ( n − i ) ! \sum_{i=0}^n (-1)^{i+1}g_i(n-i)! ∑i=0n​(−1)i+1gi​(n−i)!

那么怎么求 g i g_i gi​呢？

假设有一张二分图，左边是每一个值，右边是每一个位子，每一个不合法的匹配，我们连一条边。我们发现这张图长得十分优美：

灵魂画手litble

是若干条链。我们把所有的链都拉直了进行DP，设 f ( i , j , 0 / 1 ) f(i,j,0/1) f(i,j,0/1)表示前 i i i个点里选了 j j j个不合法匹配，且第 i i i个点和第 i + 1 i+1 i+1个点之间的匹配边是否选择的方案数，那么有：

f ( i + 1 , j , 0 ) = f ( i , j , 0 ) + f ( i , j , 1 ) , f ( i + 1 , j + 1 , 1 ) = f ( i , j , 0 ) f(i+1,j,0)=f(i,j,0)+f(i,j,1),f(i+1,j+1,1)=f(i,j,0) f(i+1,j,0)=f(i,j,0)+f(i,j,1),f(i+1,j+1,1)=f(i,j,0)

当然，如果一个点是某一条链的结尾，那么就要强制跳 f ( i + 1 , j + 1 , 1 ) = f ( i , j , 0 ) f(i+1,j+1,1)=f(i,j,0) f(i+1,j+1,1)=f(i,j,0)这个转移。

然后令 g ( i ) = f ( n , i , 0 ) + f ( n , i , 1 ) g(i)=f(n,i,0)+f(n,i,1) g(i)=f(n,i,0)+f(n,i,1)即可算出答案。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int mod=924844033,N=4005;
int vis[N][2],ed[N],f[N][N][2],fac[N],js,n,K,ans;
int qm(int x) {return x>=mod?x-mod:x;}
int main()
{
	scanf("%d%d",&n,&K);
	for(RI i=1;i<=n;++i)
		for(RI j=0;j<=1;++j) {
			if(vis[i][j]) continue;
			for(RI x=i,y=j;x<=n;x+=K,y^=1) ++js,vis[x][y]=1;
			ed[js]=1;
		}
	f[1][0][0]=1;
	for(RI i=1;i<=js;++i)
		for(RI j=0;j<=n;++j) {
			f[i+1][j][0]=qm(f[i][j][0]+f[i][j][1]);
			if(!ed[i]) f[i+1][j+1][1]=f[i][j][0];
		}
	fac[0]=1;for(RI i=1;i<=n;++i) fac[i]=1LL*fac[i-1]*i%mod;
	for(RI i=0,fh=1;i<=n;++i,fh=-fh)
		ans=qm(ans+qm(1LL*fh*qm(f[js][i][0]+f[js][i][1])%mod*fac[n-i]%mod+mod));
	printf("%d\n",ans);
	return 0;
}

E - Sugigma: The Showdown

若有红树上有一条边，它的两个端点在蓝树上的距离大于2，则如果先手到达了这两个端点，就必胜。

建出蓝树，以后手起点为根，算出所有点深度。然后建出红树，删掉满足以上条件的边（也就是建的时候就不加）

然后看先手能到那些点。

由于红树上任意一条边连接的两点在蓝树上的距离小于等于2，所以如果一个点到先手起点的距离大于等于到后手起点的距离，先手走这点就一定会被后手抓，所以不能走。这样如果它能到必胜点，就输出-1，否则选择在蓝树上深度最大的那个点，待在那里坐以待毙。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
	int q=0;char ch=' ';
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
	return q;
}
const int N=200005;
int n,s1,s2,tim,ans;
int win[N],dep[N],in[N],out[N],fa[N],vis[N],dis[N],que[N];
struct edge{int x,y;}e1[N];
struct tree{
	int h[N],ne[N<<1],to[N<<1],tot;
	void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
}T1,T2;
void dfs(int x,int las) {
	dep[x]=dep[las]+1,in[x]=++tim,fa[x]=las;
	for(RI i=T2.h[x];i;i=T2.ne[i])
		if(T2.to[i]!=las) dfs(T2.to[i],x);
	out[x]=tim;
}
int check(int x,int y) {
	if(in[x]>in[y]) swap(x,y);
	if(in[x]<=in[y]&&out[x]>=in[y]) return dep[y]-dep[x]>2;
	if(fa[x]==fa[y]) return 0;
	return 1;
}
void bfs() {
	int he=1,ta=1;
	vis[s1]=1,dis[s1]=0,que[1]=s1;
	while(he<=ta) {
		int x=que[he];++he;
		for(RI i=T1.h[x];i;i=T1.ne[i])
			if(dis[x]+1<dep[T1.to[i]]&&!vis[T1.to[i]])
				vis[T1.to[i]]=1,dis[T1.to[i]]=dis[x]+1,que[++ta]=T1.to[i];
	}
}
int main()
{
	int x,y;
	n=read(),s1=read(),s2=read();
	if(s1==s2) {puts("0");return 0;}
	for(RI i=1;i<n;++i) e1[i].x=read(),e1[i].y=read();
	for(RI i=1;i<n;++i) x=read(),y=read(),T2.add(x,y),T2.add(y,x);
	dep[0]=-1,dfs(s2,0);
	for(RI i=1;i<n;++i) {
		if(check(e1[i].x,e1[i].y)) win[e1[i].x]=win[e1[i].y]=1;
		else T1.add(e1[i].x,e1[i].y),T1.add(e1[i].y,e1[i].x);
	}
	bfs();
	for(RI i=1;i<=n;++i)
		if(win[i]&&vis[i]) {puts("-1");return 0;}
		else if(vis[i]) ans=max(ans,dep[i]+dep[i]);
	printf("%d\n",ans);
	return 0;
}

F - Many Easy Problems

容斥。

考虑每一个点对答案的贡献，发现如果一个选点集合的f中，x这个点没有参与贡献，则所有集合中的点都在删掉x的那些连通块中，也就是说，x对k意义下的答案的贡献为：
C n k − ∑ C a i k C_n^k-\sum C_{a_i}^k Cnk​−∑Cai​k​

其中 a i a_i ai​为删掉点 x x x的那些连通块的大小。

我们发现对于任意一个 k k k，一个指定的 C i k C_i^k Cik​的系数是不变的，预处理这个系数，设为 p i p_i pi​。

则：

a n s k = ∑ i = k n C i k p i = 1 k ! ∑ i = k n p i i ! ( i − k ) ! ans_k=\sum_{i=k}^n C_i^kp_i=\frac{1}{k!}\sum_{i=k}^n \frac{p_ii!}{(i-k)!} ansk​=i=k∑n​Cik​pi​=k!1​i=k∑n​(i−k)!pi​i!​

我们发现，构造一个 a i = p i i ! a_i=p_ii! ai​=pi​i!和一个 b n − i = 1 i ! b_{n-i}=\frac{1}{i!} bn−i​=i!1​，则 a a a与 b b b的卷积的第 i + k i+k i+k项就是 k k k意义下的答案。

题目给出的模数的原根是5，可以NTT。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
	int q=0;char ch=' ';
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
	return q;
}
const int N=200005,LIM=524288,mod=924844033,G=5;
int n,tot;
int h[N],ne[N<<1],to[N<<1],sz[N],p[LIM],tmp[LIM],rev[LIM],fac[N],ni[N];
int qm(int x) {return x>=mod?x-mod:x;}
void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
void pre_dfs(int x,int las) {
	sz[x]=1;p[n]=qm(p[n]+1);
	for(RI i=h[x];i;i=ne[i]) {
		if(to[i]==las) continue;
		pre_dfs(to[i],x),sz[x]+=sz[to[i]];
		p[sz[to[i]]]=qm(p[sz[to[i]]]-1+mod);
	}
	if(n-sz[x]) p[n-sz[x]]=qm(p[n-sz[x]]-1+mod);
}
int ksm(int x,int y) {
	int re=1;
	for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
	return re;
}
void NTT(int *a,int n,int x) {
	for(RI i=0;i<n;++i) if(rev[i]>i) swap(a[i],a[rev[i]]);
	for(RI i=1;i<n;i<<=1) {
		int gn=ksm(G,(mod-1)/(i<<1));
		for(RI j=0;j<n;j+=(i<<1)) {
			int t1,t2,g=1;
			for(RI k=0;k<i;++k,g=1LL*g*gn%mod) {
				t1=a[j+k],t2=1LL*g*a[j+i+k]%mod;
				a[j+k]=qm(t1+t2),a[j+i+k]=qm(t1-t2+mod);
			}
		}
	}
	if(x==1) return;
	int inv=ksm(n,mod-2);reverse(a+1,a+n);
	for(RI i=0;i<n;++i) a[i]=1LL*a[i]*inv%mod;
}
int main()
{
	int x,y,kn=1,len=0;
	n=read();
	for(RI i=1;i<n;++i) x=read(),y=read(),add(x,y),add(y,x);
	pre_dfs(1,0);fac[0]=1;
	for(RI i=1;i<=n;++i)
		fac[i]=1LL*fac[i-1]*i%mod,p[i]=1LL*p[i]*fac[i]%mod;
	ni[n]=ksm(fac[n],mod-2);
	for(RI i=n-1;i>=0;--i) ni[i]=1LL*(i+1)*ni[i+1]%mod;
	for(RI i=0;i<=n;++i) tmp[n-i]=ni[i];
	while(kn<=n+n) kn<<=1,++len;
	for(RI i=1;i<kn;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));
	NTT(p,kn,1),NTT(tmp,kn,1);
	for(RI i=0;i<kn;++i) tmp[i]=1LL*tmp[i]*p[i]%mod;
	NTT(tmp,kn,-1);
	for(RI i=1;i<=n;++i) printf("%lld\n",1LL*tmp[n+i]*ni[i]%mod);
	return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

AtCoder

AGC005

Atcoder AGC005 题解 的相关文章

随机推荐

  • ＜context:component-scan/＞标签爆红

    lt xml version 61 34 1 0 34 encoding 61 34 UTF 8 34 gt lt beans xmlns 61 34 http www springframework org schema beans 34

  • iOS exit函数深入浅出

    1 exit函数 C C 43 43 函数exit用来终止当前程序 xff0c 函数定义如下 xff1a void exit int status 官方说明如下 xff1a Terminates the process normally p

  • 前端妹子如何在 sqlserver 2008 中如何用自定义函数 解析json数据

    导航 前言 xff1a 开始干活 xff1a 0 预告1 首先先建立一个 通用的json解析自定义函数 xff08 这个代码是网络上找到的成熟代码 xff09 2 重点讲解一下 函数 parseJSON 的用法3 学会了函数 parseJS

  • ECS架构的思考

    最近在整理Demo代码 xff0c 遇到一个设计问题 xff0c 这个问题是transform组件到底放到哪里比较合适 xff1f 我们都知道逻辑 xff0c 物理 xff0c 渲染模块都会用到transform组件 比如渲染模块会将tra

  • 外网如何访问内网/局域网网站【内网穿透】

    在本地内网 局域网环境下搭建的网站 xff0c 正常情况下只能在同个局域网下访问 xff0c 想要实现外网用户也能够正常访问 xff0c 可以通过内网穿透来实现 做内网穿透 xff0c 无需公网IP xff0c 也无需进入到路由器配置 xf

  • 禁用nouveau

    sudo vim etc modprobe d blacklist conf 在最后两行添加 xff1a blacklist nouveau options nouveau modeset 61 0 禁用nouveau第三方驱动 xff0c

  • 使用win10自带的微软远程桌面，远程控制不同局域网的电脑【无需公网IP、无需进入路由器】

    在Windows环境下 xff0c 要实现远程桌面控制 xff0c 首推系统自带的微软远程桌面mstsc xff0c 不需要另外去下载第三方远程软件 不管设备是否在同个网络下 xff0c 都可以使用mstsc来实现远程连接 在同个局域网内远

  • 推荐一款永久免费不限流量的内网穿透软件

    文章目录 前言1 安装cpolar内网穿透1 1 windows系统1 2 Linux系统 2 创建隧道穿透内网端口2 1 cpolar web ui2 2 命令行创建隧道 3 配置固定二级子域名3 1 保留二级子域名3 2 配置二级子域名

  • 群晖nas免费内网穿透，实现外网异地远程访问

    文章目录 1 安装cpolar群晖套件2 打开cpolar群晖套件3 登录cpolar Web UI管理界面4 创建新隧道映射5 获取公网地址6 配置固定二级子域名6 1 保留一个二级子域名6 2 配置二级子域名 7 使用固定二级子域名远程

  • 永久免费的内网端口映射工具推荐【无公网IP】

    搭建了个游戏服务器 xff0c 想要让在不同网段下的朋友也可以连接想要在家远程桌面公司电脑想要在外远程访问本地电脑的web服务器想要在外远程访问NAS 一切的一切 xff0c 都需要公网IP的支持 但是目前IPV4资源的稀缺 xff0c 很

  • 免费内网穿透教程【无公网IP】

    文章目录 前言1 安装cpolar内网穿透工具1 1 Windows系统1 2 Linux系统1 3 macOS系统 2 创建隧道映射内网端口3 获取公网地址4 配置固定二级子域名4 1 保留一个二级子域名4 2 配置二级子域名 5 公网测

  • 内网穿透SSH远程连接家里的树莓派

    随着科技的进步和信息技术的发展 xff0c 我们身边出现了各种新奇的科技产品 xff0c 其中既有轻便易用的消费类电子产品 xff0c 也有更轻更小的硬件设备 而树莓派作为计算机学习设备 xff0c 经过多年发展 xff0c 已经获得了不俗

  • 推荐10款简单好用的免费内网穿透工具

    前言 远程办公越来越普遍 xff0c 但是如何应对在外远程桌面控制公司电脑 远程公司内网办公系统 调阅公司文件资料 远程公司内网服务器是个问题 而解决方案其实很简单 xff0c 做内网穿透就可以突破局域网的限制 xff0c 轻松实现公网访问

  • Java支付宝沙箱环境支付，官方Demo远程调试【内网穿透】

    文章目录 1 下载当面付demo2 修改配置文件3 打包成web服务4 局域网测试5 内网穿透6 测试公网访问7 配置二级子域名8 测试使用固定二级子域名访问 在沙箱环境调试支付SDK的时候 xff0c 往往沙箱环境部署在本地 xff0c

  • opencv内存不足问题（OpenCV Error: Insufficient memory）

    最近在用opencv自带的函数haartraining训练分类器 xff0c 之前用的图片是20 20 xff0c 能训练出分类器 xff0c 后来换成了80 86 xff0c 就报错了 xff0c 报的错误是内存不足 xff0c 于是 x

  • ffmpeg 4.2.2 实现mp4转avi（修改官方remuxing例子）

    最近想把ffmpeg官方例子过一遍 xff0c 达到初步了解ffmpeg的目的 xff0c 本文只是给自己一个记录 xff0c 也是在网上没有找到一样的文章 xff0c 发出来供大家指点 直接使用官方demo xff0c 把mp4转换成av

  • 12.bss段的初始化

    12 bss段的初始化 在C代码 xff1a 有初始化全局的数据段 xff0c 局部的栈 xff0c malloc部分的堆 xff0c 未初始化的全局的bss段 从上面的编译的信息知道 xff1a Bss段的起始地址 xff1a 00010

  • pandas学习之df.rename()

    pandas学习之df rename df rename 用于更改行列的标签 xff0c 即行列的索引 可以传入一个字典或者一个函数 在数据预处理中 xff0c 比较常用 官方文档 xff1a DataFrame rename self m

  • java8操作两个集合List

    public static void main String args List lt String gt list1 61 new ArrayList lt String gt list1 add 34 1 34 list1 add 34

  • Atcoder AGC005 题解

    A STring 用类似括号匹配的方法搞一下即可 span class token macro property span class token directive keyword include span span class toke

热门标签