首页 > 其他分享 >NOIP 模拟 16

NOIP 模拟 16

时间:2024-11-25 20:46:42浏览次数:6  
标签:NOIP g1 16 int g0 必败 fa num 模拟

A 图

直接上 std::bitset

B 序列

首先赋值在加法前,加法在乘法后,一个有效的赋值可以看做一个加法,乘法的顺序无所谓,直接加最大,考虑把加法转化成乘法,那就看加的数在原数的占比,需要考虑加法的顺序,一定是先加大的,所以直接排序后转化成乘法就好了。

C 树

究极换根 DP 好题。
先看 \(D=1\),我们可以直接换根求出每个点做起点的情况以及这个点对根的影响,然后直接暴力统计即可。
正解就是在 \(D=1\) 的基础上处理一些更多的信息,或者说把 \(D=1\) 的步骤普适化。
求答案实际上需要的是连的树的必败点和必胜点方案数,以及对根有影响的节点数。先不考虑连第一棵树,这样每棵树都可以任意起点,设 \(f_{i,0/1}\) 表示连接了 \(i\) 棵数,当前树上必败/必胜点的方案数。发现只有连必败点才有可能改变信息,设 \(n_{0/1}\) 表示给 \(i\) 连一个必败点后整棵树上的必败/胜点数量,\(num_{0/1}\) 表示原有的必败/胜点数量,所以转移就是:

\[\begin{aligned} &f_{i,0}=\sum_{i=1}^{n}num_{i,0}\times f_{i-1,0}+n\times num_0\times f_{i,1}\\ &f_{i,1}=\sum_{i=1}^{n}num_{i,1}\times f_{i-1,0}+n\times num_1\times f_{i,1} \end{aligned} \]

这个东西可以轻易矩阵加速,所以现在只需要考虑如何处理出来 \(num\) 和 \(n_{0/1}\),\(n_{0/1}\) 就是换根的时候记一下即可,\(num\) 的处理比较困难。
首先,\(num_i\) 很难处理,因为会有很多连接关系的影响,并且这些影响要连续起来,考虑处理一个 \(f_{i,0/1}\) 表示连接一个必败点使得 \(i\) 节点为必败/胜的点的数量。不难发现 \(\sum_{i=1}^nnum_i=\sum_{i=1}^nf_i\),然后考虑如何换根。
换根需要拆贡献,博弈论通常把记一下 \(fn_i\) 表示 \(i\) 的子节点中必败点的数量。首先需要处理出子树情况的各种信息,考虑一个点是否对父亲有影响就可以处理出来 \(f\),然后换根也是需要考虑影响关系,如果父亲有 \(0\) 个或者大于两个必败点,那么直接换根即可,否则影响关系会变,如果儿子同时是必败点,那么就需要重新处理父亲的信息,封装一个转移函数就好写了,具体看代码吧。

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii std::pair<int,int>
#define eb emplace_back
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
std::mt19937 myrand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int R(int n){return myrand()%n+1;}
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=2e5+10,mod=1e9+7,inf=1e9;
inline void Min(int &x,int y){if(x>y)x=y;}
inline void Max(int &x,int y){if(x<y)x=y;}
inline void W(int &x,int y){x=(x+y)%mod;}
int n,num[2],D,n0,n1;
std::vector<int> e[N];
struct NODE{int num,f,g0,g1;}a[N],r[N],zc[N];
inline void Pass(int x,int fa){
	a[x]={0,0,0,0};
	for(int v:e[x]){
		if(v==fa)continue;
		a[x].f|=!a[v].f;a[x].num+=!a[v].f;
	}
	a[x].g1++;
	for(int v:e[x]){
		if(v==fa)continue;
		if(a[x].num>1)W(a[x].g1,a[v].g0+a[v].g1);
		if(a[x].num==1){
			if(a[v].f)W(a[x].g1,a[v].g0+a[v].g1);
			else W(a[x].g0,a[v].g1),W(a[x].g1,a[v].g0);
		}if(!a[x].num)W(a[x].g1,a[v].g0),W(a[x].g0,a[v].g1);
	}
}
inline void dfs(int x,int fa){for(int v:e[x])if(v^fa)dfs(v,x);Pass(x,fa);zc[x]=a[x];}
inline void change(int x,int fa){
	if(x==1)r[x]=a[x];
	else{
		if(!a[x].f){
			if(a[fa].num<=2)Pass(fa,x);
			else a[fa].num--,a[fa].g1-=a[x].g0+a[x].g1;
		}else{
			if(a[fa].f)a[fa].g1-=a[x].g0+a[x].g1;
			else a[fa].g1-=a[x].g0,a[fa].g0-=a[x].g1;
		}
		Pass(x,0);r[x]=a[x];
	}
	for(int v:e[x])if(v^fa)change(v,x),a[x]=r[x];a[x]=zc[x];
}
struct MAT{
	int a[2][2];
	inline MAT(){memset(a,0,sizeof(a));}
	inline MAT operator*(const MAT&B)const{
		MAT res;int r;for(int i=0;i<2;++i)
		for(int k=0;k<2;++k){
			r=a[i][k];for(int j=0;j<2;++j)W(res.a[i][j],r*B.a[k][j]);
		}return res;
	}
}base,ans;
inline void work(){
	for(int i=1;i<=n;++i)num[r[i].f]++,W(n0,r[i].g0),W(n1,r[i].g1);
	ans.a[0][0]=num[0],ans.a[0][1]=num[1];
	base.a[0][0]=n0,base.a[1][0]=n*num[0]%mod,base.a[0][1]=n1,base.a[1][1]=n*num[1]%mod;
	for(;D;D>>=1,base=base*base)if(D&1)ans=ans*base;int ANS=r[1].g1*ans.a[0][0]+n*ans.a[0][1]*r[1].f;
	std::cout<<(ANS%mod+mod)%mod<<'\n';
}
signed main(){
    freopen("c.in","r",stdin);freopen("c.out","w",stdout);
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    n=read();D=read()-1;for(int i=1;i<n;++i){int u=read(),v=read();e[u].eb(v);e[v].eb(u);}
    dfs(1,0);change(1,0);work();
}

D 字符串

简单手玩发现相邻的两个字母如果逆序一定会产生一个贡献,然后暴力线段树维护 \(k^2\) 中情况就做完了。

总结

打成傻逼了,T2 忘了特判挂了 60pts,T4 根本没去仔细观察,给自己设限了,傻卵。

标签:NOIP,g1,16,int,g0,必败,fa,num,模拟
From: https://www.cnblogs.com/Ishar-zdl/p/18568568

相关文章

  • NOIP 模拟 17
    A镜的绮想直接做,不过如果\(n=2e5\)咋做?B万物有灵倒着选一定最优,然后每\(K\)层是一个周期,为了避免分讨,使\(K\gets2K\),写完贡献的式子是等比数列,但是这题卡逆元,所以用矩阵加速或者倍增求和即可。C白石溪\(n^2\)DP容易想到,但是无论如何都需要石子数量的状态,整个是2D......
  • 2024.11.25 noip模拟赛
    赛时T1发现公差只有\(m/n\)个,可以枚举,对于每个数在一个公差下可以推出首项为几是它才不改变,我开\(map\)存了在这个公差,首相下有几个\(a\)可以不变。此时快九点。T2很快有了\(O(n^3)\)的做法,感觉很好写,就没有立即写,想着再想想,把后面的题想了一圈,受挫,回来老实码,码完不过......
  • jmeter之性能测试(16.1)
    一、性能测试介绍1、什么叫做性能测试?(1)通过某些工具或手段来检测软件的某些指标是否达到了要求,这就是性能测试(2)指通过自动化的测试工具模拟多种正常、峰值以及异常负载条件来对系统的各项性能指标进行测试2、性能测试的时间?在功能测试完成后才能进行性能测试3、为什么要做性......
  • 2024.11.25 NOIP2024模拟赛
    挂了若干分。赛时T1赛时开了\(T1\),最开始都没有往正解去想,当时想着$\Deltay$是可以枚举的范围,于是我就先枚举了公差,之后再把处于同一个系中的数绑一块,然后我加了个所谓的\(n^2\)优化,但其实根本没用,应为肯定会覆盖\([0,(m-1)/(n-1)]\),可以省掉一个\(n^2\)。然后(没删反......
  • The authenticity of host ‘worker1 (192.168.254.130)‘ can‘t be established.Are
    一、报错信息在两台CentOS7虚拟机之间传输文件时,出现下面错误,其中master和worker的主机名已经在本地hosts文件做过域名解析。Theauthenticityofhost'worker1(192.168.254.130)'can'tbeestablished.ECDSAkeyfingerprintisSHA256:RlL4yF3YVyjYWGrioHFYMMos4RL9......
  • [2024.11.25]NOIP全真模拟赛
    总榜rk6,但是发现只需要改3s的T1就可以拿到rk2,但是没有如果。赛时T1怎么像是原啊,算了反正不记得。总结关键词:斜率为非负整数,直线在某区间内的高度有限制。想了想,发现斜率最大值是\(m\overn\)级的,所以后面显然可以再乘上一个\(n\)。于是有思路:枚举斜率\(k\),对每个......
  • 国标GB28181软件LiteGBS国标GB28181公网平台海康设备是否支持GB28181-2016版本(海康IP
    随着视频技术的不断进步,视频监控、直播、执法记录仪等多种视频资源的应用场景愈发广泛且多样化。这些视频资源不仅在数量上快速增长,更在质量、格式及编码标准等方面展现出极高的多样性。因此,为了实现对这些资源的有效整合和统一管理输出,信息化项目中对于视频综合接入能力的需求愈......
  • 国标GB28181软件LiteGBS国标GB28181公网平台海康设备是否支持GB28181-2016版本(海康IP
    随着视频技术的不断进步,视频监控、直播、执法记录仪等多种视频资源的应用场景愈发广泛且多样化。这些视频资源不仅在数量上快速增长,更在质量、格式及编码标准等方面展现出极高的多样性。因此,为了实现对这些资源的有效整合和统一管理输出,信息化项目中对于视频综合接入能力的需求愈......
  • SpringBoot整合MQTT利用EMQX完成消息的发布与接收+Python模拟硬件测试通信
    教程说明本教程主要内容为使用SpringBoot整合MQTT利用EMQX代理服务完成MQTT的消息发送与接收,然后用Python模拟硬件与SpringBoot应用进行了MQTT消息的通信,教程详细,并在最后讲解了开发中的注意事项,本教程适用于物联网领域、JavaWeb领域的开发人员。前置所需已经搭建好了EMQX代......
  • Java:168 基于springboot+vue的游戏交易系统
    作者主页:舒克日记简介:Java领域优质创作者、Java项目、学习资料、技术互助文中获取源码项目介绍本系统一共管理员,用户两个角色。管理员登录进入本系统操作的功能包括对商品信息,订单投诉信息,商品评价信息,商品收藏信息,会员等级信息,商品订单信息等进行管理用户登录进入......