T1 签到题

解题思路

每个点的度数对于 \(c\) 取 \(\bmod\) 有余数答案的贡献就加一。

证明太难，略。。。。

code

#include <bits/stdc++.h>
#define int long long 
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=1e6+10,INF=1e18;
int n,m,ed,c,ans,sum[N];
signed main()
{
	freopen("qiandao.in","r",stdin); freopen("qiandao.out","w",stdout);
	n=read(); m=read(); ed=read(); c=read();
	for(int i=1,x,y;i<=ed;i++)
	{
		x=read(); y=read()+n;
		sum[x]++; sum[y]++;
	}
	for(int i=1;i<=n+m;i++) ans+=(sum[i]%c!=0);
	cout<<ans;
	return 0;
}

T2 M 弟娃

解题思路

线段树维护每一个点成为祭坛的贡献。

对于新加入的一条链 \((x,y)\) 分为一下几种情况处理

• \(x=y\) 或者 \(x,y\) 相邻，直接给整棵树加 1

• \(x,y\) 都不是 LCA ,直接给以 \(x,y\) 为根的两颗子树区间加 1

• 有一者是 LCA ，假设 \(x\) 是，就给整棵树加 1 ，给 \(x\) 的子节点中子树包含 \(y\) 的节点为根的子树减 1 ，最后给 \(y\) 为根的子树加 1 。

对于第三种情况中的那个节点可以倍增找出来。

code

#include <bits/stdc++.h>
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
#define ls x<<1
#define rs x<<1|1
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=3e5+10;
int n,m,f[N][25];
int tot=1,head[N],ver[N<<1],nxt[N<<1];
int tim,dfn[N],id[N],siz[N],dep[N],fa[N],son[N],topp[N];
struct Segment_Tree
{
	struct Node{int laz,dat;}tre[N<<2];
	void push_up(int x){tre[x].dat=max(tre[ls].dat,tre[rs].dat);}
	void push_down(int x)
	{
		if(!tre[x].laz) return ;
		tre[ls].dat+=tre[x].laz; tre[rs].dat+=tre[x].laz;
		tre[ls].laz+=tre[x].laz; tre[rs].laz+=tre[x].laz;
		tre[x].laz=0;
	}
	void insert(int x,int l,int r,int L,int R,int val)
	{
		if(L<=l&&r<=R) return tre[x].dat+=val,tre[x].laz+=val,void();
		int mid=(l+r)>>1; push_down(x);
		if(L<=mid) insert(ls,l,mid,L,R,val);
		if(R>mid) insert(rs,mid+1,r,L,R,val);
		push_up(x);
	}
}T;
void add_edge(int x,int y)
{
	ver[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
void dfs1(int x)
{
	siz[x]=1;
	for(int j=0;f[x][j];j++)
		f[x][j+1]=f[f[x][j]][j];
	for(int i=head[x];i;i=nxt[i])
	{
		int to=ver[i]; if(siz[to]) continue;
		dep[to]=dep[x]+1; fa[to]=f[to][0]=x;
		dfs1(to); siz[x]+=siz[to];
		if(siz[to]>siz[son[x]]) son[x]=to;
	}
}
void dfs2(int x,int tp)
{
	topp[x]=tp; dfn[x]=++tim; id[tim]=x;
	if(son[x]) dfs2(son[x],tp);
	for(int i=head[x];i;i=nxt[i])
		if(!dfn[ver[i]])
			dfs2(ver[i],ver[i]);
}
int LCA(int x,int y)
{
	if(!x||!y) return 0;
	while(topp[x]^topp[y])
	{
		if(dep[topp[x]]<dep[topp[y]]) swap(x,y);
		x=fa[topp[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	return x;
}
void solve()
{
	int x,y,lca; x=read(); y=read(); lca=LCA(x,y);
	if(dep[x]>dep[y]) swap(x,y);
	if(x==y) return T.insert(1,1,tim,1,tim,1),void();
	if(lca==x)
	{
		T.insert(1,1,tim,1,tim,1);
		if(dep[y]-dep[x]==1) return ;
		T.insert(1,1,tim,dfn[y],dfn[y]+siz[y]-1,1);
		int pos=y;
		for(int i=20;i>=0;i--)
			if(f[pos][i]&&dep[f[pos][i]]>=dep[x]+1)
				pos=f[pos][i];
		T.insert(1,1,tim,dfn[pos],dfn[pos]+siz[pos]-1,-1);
		return ;
	}
	T.insert(1,1,tim,dfn[x],dfn[x]+siz[x]-1,1);
	T.insert(1,1,tim,dfn[y],dfn[y]+siz[y]-1,1);
}
signed main()
{
	freopen("magic.in","r",stdin); freopen("magic.out","w",stdout);
	n=read(); m=read();
	for(int i=1,x,y;i<n;i++) x=read(),y=read(),add_edge(x,y),add_edge(y,x);
	dfs1(1); dfs2(1,1);
	while(m--) solve(),printf("%d\n",T.tre[1].dat);
	return 0;
}

T3 变异大老鼠

解题思路

不难发现跑完最短路之后保留下来的边就是一颗树，直接树上背包转移概率即可。

code

#include <bits/stdc++.h>
#define int long long 
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=3e2+10,M=3e4+10;
int n,m,cnt,dis[N],pre[N],s[N];
int tot=1,head[N],ver[M<<1],nxt[M<<1],edge[M<<1];
bool vis[N];
double ans,p[N][N],f[N][N],g[N];
vector<int> v[N];
priority_queue<pair<int,int> > q;
void add_edge(int x,int y,int val)
{
	ver[++tot]=y;
	nxt[tot]=head[x];
	edge[tot]=val;
	head[x]=tot;
}
void Dij()
{
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0; q.push(make_pair(0,1));
	while(!q.empty())
	{
		int x=q.top().second; q.pop();
		if(vis[x]) continue; vis[x]=true;
		for(int i=head[x];i;i=nxt[i])
		{
			int to=ver[i],val=edge[i];
			if(dis[to]<=dis[x]+val) continue;
			dis[to]=dis[x]+val; pre[to]=x;
			q.push(make_pair(-dis[to],to));
		}
	}
}
void dfs(int x)
{
	double base=1.0/(1.0*v[x].size());
	for(int i=0;i<v[x].size();i++)
	{
		int to=v[x][i]; dfs(v[x][i]);
		for(int j=cnt;~j;j--)
			for(int k=cnt-j;~k;k--)
				f[x][j+k]=max(f[x][j+k],f[x][j]+f[to][k]*base);
	}
	for(int i=cnt;~i;i--)
		for(int j=cnt-i;~j;j--)
			f[x][i+j]=max(f[x][i+j],f[x][i]*(1.0-p[x][j])+p[x][j]);
}
signed main()
{
	freopen("arrest.in","r",stdin); freopen("arrest.out","w",stdout);
	n=read(); m=read(); cnt=read();
	for(int i=1,x,y,val;i<=m;i++)
		x=read(),y=read(),val=read(),
		add_edge(x,y,val),add_edge(y,x,val);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=cnt;j++)
			scanf("%lf",&p[i][j]);
	Dij();
	for(int i=2;i<=n;i++) v[pre[i]].push_back(i);
	dfs(1);
	printf("%.6lf",f[1][cnt]);
	return 0;
}

T4 朝鲜时蔬

解题思路

反复琢磨题目名字的含义，就是菜。。

只能怪我语文素养低下了。。

题面的意思就是在一个包含 \([1,n]\) 所有数字的集合中选出 \(m\) 个数字来。

对于每一个方案再从其中选出 \(k\) 个数字，相对于 \(m\) 满足 集合数字之和 \(Sum(S_k)|Sum(S_m)\) 的所有集合中，设 \(mx_m=\max\{Sum(S_k)\}\) 求出 \(Sum(S_k)=mx_m\) 的个数。

学到了一个小技巧:

\(\sum\limits_{i=l}^r[2|i]=\frac{r}{2}-\frac{l+1}{2}+1\)

\(\sum\limits_{i=l}^r[3|i]=\frac{r}{3}-\frac{l+2}{3}+1\)

详细证明见 官方题解

code

#include <bits/stdc++.h>
#define int long long 
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=1e6+10,mod=1e9+7;
const int inv2=500000004,inv6=166666668,inv24=41666667;
int n,m,k,ans;
int d42[11]={0,0,0,0,1,1,1,3,6,9,10};
int power(int x,int y,int p=mod)
{
	int temp=1;
	while(y)
	{
		if(y&1) temp=temp*x%mod;
		x=x*x%mod; y>>=1;
	}
	return temp;
}
void solve1_1(){ans=n%mod;}
void solve2_1(){for(int l=1,r;l<=n;l=r+1) r=min(n,n/(n/l)),ans=(ans+(r-l+1)%mod*(n/l-1))%mod;}
void solve2_2(){n%=mod;ans=n*(n-1)%mod*inv2%mod;}
void solve3_1(){ans=n/3%mod;}
void solve3_2()
{
	for(int l=1,r,len;l<=n;l=r+1)
	{
		r=min(n,n/(n/l)); len=r-l+1;
		ans=(ans+(n/l)%mod*((l+r)%mod*(len%mod)%mod*inv2%mod-len%mod-(len/2)%mod-((l&1)^1)*(len&1)+2*mod)%mod)%mod;
	}
	ans=ans*inv2%mod;
}
void solve3_3(){n%=mod;ans=n*(n-1)%mod*(n-2)%mod*inv6%mod;}
void solve4_1(){ans=(n==4||n==5)?1ll:(n/6+n/9+n/10+n/12+n/15+n/21)%mod;}
void solve4_2(){ans=n<11?d42[n]:(n/11+n/29)%mod;}
int g(int x){return x%=mod,x*(x+1)%mod*(2*x+1)%mod*inv6%mod;}
void solve4_3()
{
	if(n==4) return ans=1,void();
	if(n==5) return ans=5,void();
	for(int l=1,r,len;l<=n;l=r+1)
	{
		r=min(n,n/(n/l)); len=(r-l+1)%mod;
		ans=(ans+(n/l)%mod*(5*len+(g(r)-g(l-1)+mod)%mod-6*(l+r)%mod*len%mod*inv2%mod+3*(r/2-(l+1)/2+1+mod)%mod+4*(r/3-(l+2)/3+1+mod)%mod+mod) )%mod;
	}
	ans=ans*inv2%mod*inv6%mod;
}
void solve4_4(){n%=mod;ans=n*(n-1)%mod*(n-2)%mod*(n-3)%mod*inv24%mod;}
signed main()
{
	freopen("vegetable.in","r",stdin); freopen("vegetable.out","w",stdout);
	n=read(); m=read(); k=read();
	if(m==1&&k==1) solve1_1();
	if(m==2&&k==1) solve2_1();
	if(m==2&&k==2) solve2_2();
	if(m==3&&k==1) solve3_1();
	if(m==3&&k==2) solve3_2();
	if(m==3&&k==3) solve3_3();
	if(m==4&&k==1) solve4_1();
	if(m==4&&k==2) solve4_2();
	if(m==4&&k==3) solve4_3();
	if(m==4&&k==4) solve4_4();
	printf("%lld",ans); return 0;
}