首页 > 其他分享 >ABC295(D~G)

ABC295(D~G)

时间:2023-04-02 20:55:31浏览次数:55  
标签:return 环上 int fa ans include ABC295

Tasks - AtCoder Beginner Contest 295

这篇是超级抽象的简要tj,看不懂不要骂我这个蒟蒻QWQ

D - Three Days Ago (atcoder.jp)

\(f_i\)表示\([1,i]\)的所有数的奇偶情况,如果\(b\)有奇数个,那么\(f_i|=2^b\),特别的,\(f_0=0\),答案就是\(\sum\limits_{i=1}^n \sum\limits_{j=0}^{i-1} [f_j=f_i]\)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+5;
int n,f[N];
char s[N];
map<int,int> mp;
ll ans;
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	++mp[0];
	for(int i=1;i<=n;++i) f[i]=f[i-1],f[i]^=(1<<(int)(s[i]-'0'));
	for(int i=1;i<=n;++i) ans+=mp[f[i]],++mp[f[i]];
	printf("%lld\n",ans);


	return 0;
}

E - Kth Number (atcoder.jp)

最后的答案为\(\sum\limits_{i=1}^m i*\{i作为A_k的概率\}\),就相当于求\(\sum\limits_{i=1}^m \{A_k\geq i的概率\}\)

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5,MOD=998244353;
int n,m,k,a[N],C[N][N],ans,p[N],q[N]; 
void Init(){
	for(int i=0;i<=n;++i){
		C[i][0]=1;
		for(int j=1;j<=i;++j) C[i][j]=(1ll*C[i-1][j]+1ll*C[i-1][j-1])%MOD;
	}
}
int power(int x,int y){
	int ans=1;
	for(;y;y>>=1,x=1ll*x*x%MOD) if(y&1) ans=1ll*ans*x%MOD;
	return ans;
}
int main(){
	scanf("%d%d%d",&n,&m,&k),Init();
	for(int i=1;i<=n;++i) scanf("%d",&a[i]); 
	for(int i=1;i<=m;++i){
		int nd=n+1-k,cnt=0;
		for(int j=1;j<=n;++j) nd-=(a[j]>=i),cnt+=(!a[j]);
		if(nd<0||nd>cnt){
			if(nd<0) ans=(ans+1ll)%MOD;
			continue;
		}
		int pp=1ll*(m-i+1)*power(m,MOD-2)%MOD,qq=(MOD+1-pp)%MOD;
		p[0]=q[0]=1;
		for(int j=1;j<=cnt;++j) p[j]=1ll*p[j-1]*pp%MOD,q[j]=1ll*q[j-1]*qq%MOD;
		for(int j=nd;j<=cnt;++j) ans=(1ll*ans+1ll*C[cnt][j]*p[j]%MOD*q[cnt-j]%MOD)%MOD;
	}
	printf("%d",ans);
	return 0;
}

F - substr = S (atcoder.jp)

答案肯定是\(ask(r)-ask(l-1)\)

枚举\(S\)处于当前数字的位置,如果现在给一个排名\(k\),那么我们就可以根据这个排名得出当前数字应该是多少

所以考虑\(S\)所处的位置下的最大排名,也就是最大个数,最后答案就是所有位置下的个数的和

#include<bits/stdc++.h>
#define int long long
using namespace std;
string s;
int l,r,pw[20];
int ask(int i,int k,string s){
	int a=s.size(),b=k-a+1;
	if(b<0) return -1;
	--i;
	if(s[0]=='0') i+=pw[b];
	int x=i/pw[b],y=i%pw[b];
	return x*pw[k+1]+stoll(s)*pw[b]+y;
}
int ans;
int solve(int x,string s){
	ans=0;
	for(int k=0;k<=15;++k){
		int t=ask(1,k,s);
		if(t==-1||t>x) continue;
		int l=0,r=pw[16-s.size()],mid;
		while(l<r){
			mid=l+r+1>>1;
			if(ask(mid,k,s)>x) r=mid-1;
			else l=mid;
		}
		ans+=r;
	}
	return ans;
}
signed main(){
	int T; scanf("%lld",&T);
	pw[0]=1; for(int i=1;i<=17;++i) pw[i]=pw[i-1]*10;
	while(T--){
		cin>>s>>l>>r;
		printf("%lld\n",solve(r,s)-solve(l-1,s));	
	}
	return 0;
}

G - Minimum Reachable City (atcoder.jp)

可以发现,连了一条边过后会构成一个环,环上的点在一条链上,并且环上所有点的答案都跟新为这个环上深度最浅的点的答案

所以自然而然就想到并查集,也就是将环上所有点都连向最浅的点,因为环上的点一定在一条链上,所以如果下次构成的环经过了这个环的点,那么就可以直接跳过这些点,跳到这个环上所有的点的指向的点\(x\)上去,此时,要么下次构成的环的最高的点\(y\)也指向\(x\),这个就不用管;要么就是\(x\)指向\(y\)。

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2e5+5;
int n;
vector<int> edge[N];
int ans[N],fa[N],fr[N];
void dfs(int u){
	ans[u]=u,fa[u]=u;
	for(auto v:edge[u]){
		dfs(v);
		ans[u]=min(ans[u],ans[v]);
	}
}
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
int main(){
	scanf("%d",&n);
	for(int i=2,u,v;i<=n;++i) scanf("%d",&fr[i]),edge[fr[i]].pb(i);
	dfs(1);
	int q,op,u,v; scanf("%d",&q);
	while(q--){
		scanf("%d%d",&op,&u);
		if(op==1){
			scanf("%d",&v),v=find(v);
			while(u!=v){
				u=find(u);
				if(u==v) continue;
				fa[u]=v,u=fr[u];
			}
		}else printf("%d\n",ans[find(u)]);
	}

	return 0;
}

标签:return,环上,int,fa,ans,include,ABC295
From: https://www.cnblogs.com/LuoyuSitfitw/p/17281333.html

相关文章

  • ABC295 E
    ABC295E给你一个长度为\(N\)的序列\(A\)满足\(\foralli\in[1,N],A_i\in[0,M]\),其中\(M\)是一个给定的常数执行以下两种操作不断把序列中的一个\(0\)换成在\([1,M]\)中均匀随机的一个数,直到序列中没有\(0\)对整个序列升序排序求序列第\(K\)个数的期望值,对......
  • abc295-G
    题目链接:https://atcoder.jp/contests/abc295/tasks/abc295_g题目意思:给你一颗以1为根的有向树,询问有两种情况:    第一种询问是在u,v中加一条边,保证v是可以到u的。......
  • abc295-E
    题目链接:https://atcoder.jp/contests/abc295/tasks/abc295_e一道数学好题,做完后深受启发。思路:设\(A_k\)处的值为\(x\),则答案为:\(E(x)=\Sigma_1^mi*p(x=i)=1*p(x......
  • 【题解】Atcoder ABC295 A-G
    A.ProbablyEnglish题目分析:直接每一个单词判一下就好了。代码:点击查看代码#include<bits/stdc++.h>usingnamespacestd;intmain(){ intn;scanf("%d",&n); bo......
  • [ABC295Ex] E or m 题解
    状压dp,2hd4me/ng。题意开始你有一个全\(0\)矩阵,你可以随意执行如下操作:选择任意一行,将其从最左端开始的连续一段染成\(1\)。选择任意一列,将其从最上端开始的连......
  • AT_abc295_d 题解
    一、题目描述:给你一个由数字0~9组成的字符串,长度为N(1<=N<=500000)。求出满足1<=l<=r<=N且在l~r区间内所有数字都出现了偶数次的整数对l,r有多少对。......
  • ABC295 D题 题解
    题意简述给定一个长度不超过\(5\times10^5\)的,仅有数字构成的字符串,问存在多少段子串,使得子串内字符重新排序后,前半段与后半段相同?做法分析重组后前后两部分相同,其实也......
  • ABC295 A~C题解
    A-ProbablyEnglish共有\(n\)个单词,如果出现过and,not,that,the,you其中一个单词至少一次,输出\(Yes\),否则,输出\(No\)。(输入的单词均为小写)按题意模拟即可:#include<......