正题

题目链接:https://codeforces.com/gym/103960

B-Fun with Stones【博弈论,数位dp】

题目大意

三个堆的取石子游戏，第 \(i\) 个堆石子个数可能是 \([L_i,R_i]\)，求先手必胜的概率。

\(1\leq L_i\leq R_i\le 10^9\)

解题思路

状压一下三个堆数量是否到达上界，就可以数位\(dp\)出界都是\([1,R_i]\)的先手必胜方案数。

然后当个三维的容斥一下就好了。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#define ll long long
using namespace std;
const ll P=1e9+7;
const ll w[4]={0,3,5,6};
ll L1,R1,L2,R2,L3,R3,f[31][8];
ll read(){
	ll x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
void print(ll x)
{if(x>9)print(x/10);putchar(x%10+'0');return;}
ll power(ll x,ll b){
	ll ans=1;
	while(b){
		if(b&1)ans=ans*x%P;
		x=x*x%P;b>>=1;
	}
	return ans;
}
ll solve(ll n,ll m,ll k){
	memset(f,0,sizeof(f));f[30][7]=1;
	for(ll i=29;i>=0;i--){
		ll a=((n>>i)&1)+((m>>i)&1)*2+((k>>i)&1)*4;
		for(ll s=0;s<8;s++)
			for(ll z=0;z<4;z++)
				if(!((a^7)&s&w[z]))
					(f[i][s^(s&a&(w[z]^7))]+=f[i+1][s])%=P;
	}
	ll ans=0;
	for(ll s=0;s<8;s++)(ans+=f[0][s])%=P;
	return ans;
}
signed main()
{
	L1=read();R1=read();L2=read();R2=read();L3=read();R3=read();
	ll S=(R1-L1+1)*(R2-L2+1)%P*(R3-L3+1)%P,L=0;
	(L+=solve(R1,R2,R3))%=P;
	(L-=solve(L1-1,R2,R3))%=P;
	(L-=solve(R1,L2-1,R3))%=P;
	(L-=solve(R1,R2,L3-1))%=P;
	(L+=solve(L1-1,L2-1,R3))%=P;
	(L+=solve(L1-1,R2,L3-1))%=P;
	(L+=solve(R1,L2-1,L3-1))%=P;
	(L-=solve(L1-1,L2-1,L3-1))%=P;
	L=(L+P)%P;
	print((S-L+P)%P*power(S,P-2)%P);putchar('\n');
	return 0;
}

D-Displacing Particles【结论】

题目大意

开始有一个点在 \((2^{n-1},2^{n-1})\) ，然后你每次可以从 \((0,0),(0,2^n),(2^n,0),(2^n,2^n)\) 选择一个点让那个点变为他们的中点，求到达 \((x,y)\) 的最少次数。

\(1\leq n\leq 20,0<x,y<2^n\)

解题思路

相当于开始最高位有一个 \(1\) ，然后每次除以2再给最高位配一个数，所以求每个 \(x,y\) 的第一个 \(1\) 的位置然后取 \(max\) 就可以得到答案了。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,x,y,a,b;
int main()
{
	scanf("%d%d%d",&n,&x,&y);
	while(!(x&1))a++,x>>=1;
	while(!(y&1))b++,y>>=1;
	a=n-a;b=n-b;
	printf("%d",max(a,b)-1);
	return 0;
}

F-Multidimensional Hangman

题目大意

给出 \(n\) 个长度为 \(m\) 的小写字母字符串，其中都有一个字母不确定。

求一个字典序最小的能够匹配最多字符串的串。

\(1\leq n\leq 10^4,1\leq m\leq 12\)

解题思路

暴力枚举那个不确定的字母，然后压缩成long long用map存一下，遍历一遍就可以得到答案了。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define llu unsigned long long
using namespace std;
int n,m;
llu pw[20];char s[20];
map<llu,int> mp;
map<llu,int>::iterator it;
int main()
{
	scanf("%d%d",&n,&m);pw[0]=1;
	for(int i=1;i<=m;i++)pw[i]=pw[i-1]*26ull;
	for(int i=1;i<=n;i++){
		scanf("%s",s);int pos=0;
		llu h=0;
		for(int j=0;j<m;j++){
			h=h*26ull;
			if(s[j]=='*')pos=m-j;
			else h+=s[j]-'a';
		}
		for(int j=0;j<26;j++)
			mp[h+j*pw[pos-1]]++;
	}
	it=mp.begin();
	llu ans=0;int mx=0;
	while(it!=mp.end()){
		if((*it).second>mx)
			mx=(*it).second,ans=(*it).first;
		it++;
	}
	for(int i=m-1;i>=0;i--)
		putchar(ans/pw[i]%26+'a');
	putchar(' ');
	printf("%d\n",mx);
	return 0;
}

I-Intercepting Information

题目大意

输入 \(8\) 个数字，求是否有 \(9\)

解题思路

如题

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int x,flag;
int main()
{
	for(int i=1;i<=8;i++){
		scanf("%d",&x);
		if(x==9)flag=1;
	}
	if(flag)puts("F");
	else puts("S");
	return 0;

L-Listing Tedious Paths【根号分治,树上差分,LCA】

题目大意

给出 \(n\) 个点的一棵树，每个点有个颜色，求经过每一条边的，且首尾是相同颜色的路径数量。

\(2\leq n\leq 10^5\)

解题思路

根号分治一下，如果一种颜色数量超过 \(\sqrt n\) ，就整棵树 \(dp\) 一下更新答案，否则就暴力给每个点对的链加值。

给链加值的时候用树上差分，需要 \(O(1)\) 的 \(LCA\) 保证复杂度。

时间复杂度：\(O(n\sqrt n)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int N=2e5+10;
struct node{
	int to,next,w;
}a[N<<1];
int n,Q,tot,cnt,dfn[N],rfn[N],dep[N],lg[N];
int f[N][23],ls[N],pos[N],c[N],w[N];
long long ans[N],val[N];
vector<int> v[N];
void print(long long x)
{if(x>9)print(x/10);putchar(x%10+'0');return;}
void addl(int x,int y,int w){
	a[++tot].to=y;
	a[tot].next=ls[x];
	a[tot].w=w;
	ls[x]=tot;return;
}
void dfs(int x,int fa){
	dfn[++cnt]=x;rfn[x]=cnt;
	dep[x]=dep[fa]+1;
	for(int i=ls[x];i;i=a[i].next){
		int y=a[i].to;
		if(y==fa)continue;
		dfs(y,x);pos[y]=a[i].w;
		dfn[++cnt]=x;
	}
	return;
}
void init(){
	dfs(1,1);
	for(int i=1;i<=cnt;i++)f[i][0]=dfn[i];
	for(int i=2;i<=cnt;i++)lg[i]=lg[i/2]+1;
	for(int j=1;(1<<j)<=cnt;j++)
		for(int i=1;i+(1<<j)-1<=cnt;i++){
			int x=f[i][j-1],y=f[i+(1<<j-1)][j-1];
			f[i][j]=dep[x]<dep[y]?x:y;
		}
	return;
}
int LCA(int x,int y){
	int l=rfn[x],r=rfn[y];
	if(l>r)swap(l,r);
	int z=lg[r-l+1];
	x=f[l][z];y=f[r-(1<<z)+1][z];
	return dep[x]<dep[y]?x:y;
}
void solve(int x,int fa,int col){
	w[x]=(c[x]==col);
	for(int i=ls[x];i;i=a[i].next){
		int y=a[i].to;
		if(y==fa)continue;
		solve(y,x,col);w[x]+=w[y];
		ans[pos[y]]+=1ll*w[y]*(v[col].size()-w[y]);
	}
	return;
}
void calc(int x,int fa){
	for(int i=ls[x];i;i=a[i].next){
		int y=a[i].to;
		if(y==fa)continue;
		calc(y,x);val[x]+=val[y];
	}
	ans[pos[x]]+=val[x];
	return;
}
int main()
{
	scanf("%d",&n);Q=sqrt(n);
	for(int i=1;i<=n;i++){
		scanf("%d",&c[i]);
		v[c[i]].push_back(i);
	}
	for(int i=1,x,y;i<n;i++){
		scanf("%d%d",&x,&y);
		addl(x,y,i);addl(y,x,i);
	}
	init();
	for(int i=1;i<=n;i++){
		if(v[i].size()<=Q){
			for(int x=0;x<v[i].size();x++)
				for(int y=x+1;y<v[i].size();y++)
					val[v[i][x]]++,val[v[i][y]]++,
					val[LCA(v[i][x],v[i][y])]-=2;
		}
		else solve(1,0,i);
	}
	calc(1,0);
	for(int i=1;i<n;i++)print(ans[i]),putchar((i==n-1)?'\n':' ');
	return 0;
}

N-Numbers on both Sides【线段树】

题目大意

\(n\) 张牌排成一排，有正面反面的数值，选择首尾加起来 \(K\) 张牌取得正面的数值，然后在这些牌中选择 \(L\) 张取反面的数值，求最大数值和。

\(1\leq L\leq K\leq n\leq 10^5\)

解题思路

直接暴力枚举头选多少张尾选多少张，然后用线段树维护一下反面的数字，每次取前 \(L\) 大就好了。

时间复杂度：\(O(n\log E)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#define ll long long
using namespace std;
const ll N=1e5+10,M=N*40;
ll n,a[N],b[N],sum,ans,cnt,k,l,rt;
ll w[M],v[M],ls[M],rs[M];
ll read(){
	ll x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
ll print(ll x)
{if(x>9)print(x/10);putchar(x%10+'0');}
void Change(ll &x,ll L,ll R,ll pos,ll val){
	if(!x)x=++cnt;w[x]+=val;v[x]+=val*pos;
	if(L==R)return;ll mid=(L+R)>>1;
	if(pos<=mid)Change(ls[x],L,mid,pos,val);
	else Change(rs[x],mid+1,R,pos,val);
	return;
}
ll Ask(ll x,ll L,ll R,ll k){
	if(!x)return 0;
	if(L==R)return k*L;
	ll mid=(L+R)>>1;
	if(w[rs[x]]>=k)return Ask(rs[x],mid+1,R,k);
	return Ask(ls[x],L,mid,k-w[rs[x]])+v[rs[x]];
}
signed main()
{
	n=read();
	for(ll i=1;i<=n;i++)a[i]=read();
	for(ll i=1;i<=n;i++)b[i]=read();
	k=read();l=read();rt=cnt=1;
	for(ll i=n-k+1;i<=n;i++)Change(rt,1,1e9,b[i],1),sum+=a[i];
	ans=max(ans,sum+Ask(rt,1,1e9,l));
	for(ll i=1;i<=k;i++){
		Change(rt,1,1e9,b[n-k+i],-1);
		Change(rt,1,1e9,b[i],1);
		sum+=a[i];sum-=a[n-k+i];
		ans=max(ans,sum+Ask(rt,1,1e9,l));
	}
	print(ans);putchar('\n');
	return 0;
}