首页 > 其他分享 >231030校内赛

231030校内赛

时间:2023-10-30 19:44:37浏览次数:42  
标签:校内 int mid 原树 231030 端点 ans 直径

T1 新的阶乘

有三种做法,第一种也就是我写的这种容易被评测机波动坑,复杂度玄学

考虑处理出每个数的质因数,然后就暴力除每个数的质因数的种类次

非常的简单,也容易被卡

第二种是与第一种差距不大,就是在线性筛中处理出质因数之后,再对每个数除以线筛中处理的质因数,将它的答案加到除数和商的答案里,质数本身不用处理

最后遍历每一个质数输出答案就行了

第三种是推式子,就是有点难想,我就不详说了

#include<bits/stdc++.h>
#define N 10000010
#define ll long long
using namespace std;
int n,p[N],is[N],cnt;
ll ans[N];
inline void pre(){
	is[0] = is[1] = 1;
	for(int i = 2;i<=n;++i){
		if(!is[i]) p[++cnt] = i,is[i] = i;
		for(int j = 1;j<=cnt&&i*p[j]<=n;++j){
			is[i*p[j]] = max(is[i*p[j]],p[j]);
			if(!(i%p[j])) break;
		}
	}
}
int main(){
	freopen("factorial.in","r",stdin);
	freopen("factorial.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	pre();
	for(int i = 2;i<=n;++i){
		int x = i;
		while(x>1){
			ans[is[x]]+=n-i+1;
			x/=is[x];
		}
	}
	cout<<"f("<<n<<")=";
	for(int i = 1;i<=cnt;++i){
		if(i!=1)cout<<"*";
		cout<<p[i];
		if(ans[p[i]]!=1) cout<<"^"<<ans[p[i]];
	}
	return 0;
}

T2 博弈树

一道需要推性质的题,你全输出 \(Alice\) 都有 \(70\) 分

我们考虑先手的位置如果在直径端点的话一定是先手必胜的,否则先手一定不能将点移动到直径端点

于是我们考虑删除了原树所有直径端点的树,如果初始点在这棵树上为直径端点那么也一定是先手必胜的

因为先手可以将点移动到另一个直径端点,这样后手就一定会将点移动到原树的直径端点上,并且移动的长度一定小于原树直径,这样先手就可以将点移动到原树的另一个直径端点取得胜利

所以这样我们可以将树的叶子一层一层的删下去,如果最后删剩下一个点那么在这个点是后手必胜的 ,因为先手无论如何都会将这个点移动到某一层的直径端点

否则根据我们之前的证明先手一定可以通过不断将点移动到下一层的直径端点取得胜利

直接实现是 \(\mathcal O(n^2)\) 的,不过我们注意到原树的直径中点一定是删一层后树的直径中点, 于是直接判断原树直径长度即可

如果不明白上述过程的话,其实可以自己求一下 \(SG\) 函数打个表就很容易发现规律了

#include<bits/stdc++.h>
#define N 100010
using namespace std;
struct edge{
	int v,ne;
}e[N<<1];
int cnt,h[N],dep[N],rt,lf,n,q,f[N];
void add(int u,int v){
	e[++cnt].v = v;
	e[cnt].ne = h[u];
	h[u] = cnt;
}
int dfs(int x,int fa){
	f[x] = x;dep[x] = dep[fa]+1;
	for(int i = h[x];i;i = e[i].ne){
		int v = e[i].v;
		if(v!=fa){
			int tmp = dfs(v,x);
			if(dep[tmp]>dep[f[x]]) f[x] = tmp;
		}
	}
	return f[x];
}
int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i = 1;i<n;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);add(v,u);
	}
	rt = dfs(1,0);
	lf = dfs(rt,0);
	for(int i = 1;i<=q;i++){
		int x;cin>>x;
		if((dep[lf]&1)&&f[x]==lf&&dep[x]==(dep[lf]+1)/2) cout<<"Bob\n";
		else cout<<"Alice\n";
	}
	return 0;
}

T3 划分

对于部分分的前 \(k\) 位没有 \(1\) 那么最优解一定是在第一个 \(1\) 之前分段,使用组合数计算

否则最优解一定会使自身尽量长,那么就是每回选出 \(n-k+1\) 的长度的一段,剩下的都是单独一段

考虑每个数的位权,每个方案对应的 \(n-k+1\) 长度的那一段的前 \(n-k\) 位一定相同

所以可以二分找到最大划分点,判断有多少划分点的前 \(n-k\) 位相同即可

需特判 \(n==k\)

#include<bits/stdc++.h>
#define mod 998244353
#define N 2000010
using namespace std;
int n,k,fac[N],inv[N],a[N],h[N],pw[N];
char s[N];
int ksm(int x,int y){
	int res = 1;
	while(y){
		if(y&1) res = 1ll*res*x%mod;
		x = 1ll*x*x%mod;
		y>>=1;
	}
	return res;
}
int C(int x,int y){
	if(x<y) return 0;
	return 1ll*fac[x]*inv[y]%mod*1ll*inv[x-y]%mod;
}
int hsh(int l,int r){
	return (h[r]-1ll*h[l-1]*pw[r-l+1]%mod+mod)%mod;
}
int main(){
	freopen("divide.in","r",stdin);
	freopen("divide.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>k>>s+1;
	fac[0] = pw[0] = 1;
	for(int i = 1;i<=n;i++){
		fac[i] = 1ll*fac[i-1]*i%mod;
		pw[i] = 2*pw[i-1]%mod;
		h[i] = (h[i-1]*2+s[i]-'0')%mod;
	}
	inv[n] = ksm(fac[n],mod-2);
	for(int i = n-1;i>=0;i--)
		inv[i] = 1ll*inv[i+1]*(i+1)%mod;
	int p = n;
	for(int i = 1;i<=n;i++)
		if(s[i]=='1'){
			p = i-1;
			break;
		}
	if(p>=k-1){
		int val = 0,ans = 0;
		for(int i = p;i<=n;i++)
			val = (val*2+(s[i]-'0'))%mod;
		if(p==n) p--;
		for(int i = k-1;i<=p;i++)
			ans = (ans+C(p,i))%mod;
		cout<<val<<" "<<ans;
		return 0;
	}
	int mx = 1;
	for(int i = 2;i<=k;i++){
		int l = 1,r = n-k+1,ans = -1;
		while(l<=r){
			int mid = (l+r)>>1;
			if(hsh(i,i+mid-1)!=hsh(mx,mx+mid-1)){
				r = mid-1;ans = mid;
			}else l = mid+1;
		}
		if(ans!=-1&&s[i+ans-1]>s[mx+ans-1]) mx = i;
	}
	int ans = 0;
	for(int i = 1;i<mx;i++)
		ans+=(s[i]=='1');
	for(int i = mx+(n-k+1);i<=n;i++)
		ans+=(s[i]=='1');
	ans = (ans+hsh(mx,mx+n-k))%mod;
	int cnt = 0;
	for(int i = 1;i<=k;i++)
		if(hsh(i,i+n-k-1)==hsh(mx,mx+n-k-1))
			cnt++;
	cout<<ans<<" "<<(n==k?1:cnt);
	return 0;
}

标签:校内,int,mid,原树,231030,端点,ans,直径
From: https://www.cnblogs.com/cztq/p/17798625.html

相关文章

  • test20231030
    rp大爆发(别一次用完就行了)。来晚了,差点没赶上考试。先看T1,看上去很像一个三维偏序问题,一看数据范围\(n\le3\times10^7\),不行,再看一眼题目,发现一句话请选手仔细观察给出的数据生成器,数据生成方式与解题强相关。阿这,原来是一道分析代码题。看他数据生成器:typedefunsig......
  • 231023校内赛
    T1区间题解很容易想到的一点是如果\(k\)足够大,那么把区间单独放到一个组里总比多个区间在一个组优对于多个区间来说,区间之间如果两两不包含的话这道题会是比较好做的就可以注意到如果一个大区间包含了一个小区间,那么大区间要么单独一组,要么和小区间同一组,这样会是比较优的......
  • 231019校内赛
    T1机器人题解傻逼题,但是有人\(90\)分一开始十分想直接暴力\(2^n\)判断每一步选不选求出所有可能性但是会发现它有制约关系有些步走了之后,有些就必须走了所以需要用一个数组记录当前位置走没走过,或者是不是障碍注意走没走过不能直接赋值\(1,0\)因为回溯时会直接将前......
  • 231019校内赛
    T1购买饮料题解简单且傻逼的题目有人更傻逼没做出来很容易就会想去拿最后能喝多少瓶去做未知量来求然后就有一个严重的问题,它会赊账非常明显这样算是不得行的那么考虑换个思路以能喝多少套饮料为未知量,先除去第一套,免得一套都买不起时赊账买了饮料然后将剩余的钱除以\(......
  • [校内]此方(konata)
    2023-10-14题目LittleBrother题目描述难度&重要性(1~10):7题目来源CQYC题目算法几何,二分解题思路Sol我们知道,对于两个圆,我们无非就只有三种情况:相离,相切,相交。而这道题目是不允许其他圆相交,而两个圆不相交只有两种情况:包含,不包含。根据垂径定理得知,过线段两端的圆的......
  • 231011校内赛
    T1树上的数题解比上一次好一些的第一题不过我还是没做出来一眼树形\(dp\)不过状态设计和转移不是很好列容易想到对于子树枚举,记录\(f_{i,j}\)表示\(i\)的子树空出了\(j\)个点时的方案数对于每一个节点的初始状态都是\(f_{i,0}=n-dep_i\\\f_{i,1}=1\)为......
  • 231009校内赛
    T1里群题解阴间第一题题目中有一个很明显的建图方法就是对于第\(i\)天入群的人在第\(j\)天退群那么就在\(i,j\)之间连一条边首先有一个结论,管理员个数不大于\(3\)对于这个结论,证明如下:首先第一次删除出现后就一定需要两个管理员了如果某次删除只删掉了某一个管理......
  • 231007校内赛
    T1karma题解首先从贪心的思路出发把所有零多的字符串放在前面,但如下一组数据便可以卡掉201100接着我们可以来思考对于贪心的更改多举几组不同的可以卡掉的样例后可以发现如下规律先将所有字符串按\(0\)的数量排一遍序对于每一个字符串的\(0\)和\(1\)的数量我......
  • 231004校内赛
    T1水管题解很简单的一道题,别想复杂了只要一边\(dfs\)即可先将当前点的所有水量给出去,如果缺水就给出去负数那么等到最后一个节点如果不是刚好合适,那么就把剩余水量回溯回来,无论正负再如此给下一个连边的点如果最后一个点刚好合适那么给下一个点的就是\(0\)实现很简单......
  • 231002校内赛
    T1数独题解十分简单的一道模拟题有sb少打了一个换行挂50分#include<bits/stdc++.h>#defineN15usingnamespacestd;structnode{ inta[N][N],be;}t[N*10];intT,n=9,q;intferror(intcnt,intx,inty,intk){ for(inti=1;i<=n;i++) if(t[cnt].a[x][i]==k)......