首页 > 其他分享 >Atcoder 选做

Atcoder 选做

时间：2023-05-23 10:58:30浏览次数：38  
标签：Atcoder 选做 const int siz 操作 return mod

[ARC103F] Distance Sums (构造，重心)

首先显然 \(D_i\) 的最小值被重心取到，不妨以重心为根。

对于一条边连接的两个点 \(x,y\) ，不妨设这条边 \(x\) 侧的点数为 \(siz_x\) ，\(y\) 侧为 \(siz_y\) 。
那么 \(D_y=D_x+siz_x-siz_y=D_x+siz_x-(n-siz_x)=D_x+2\times siz_x -n\) 。

那么我们就可以知道以重心为根的时候，从 \(fa_x\) 转移到 \(x\) 的时候，\(2\times siz_x \leq n\)，因此沿着叶向，\(D_i\) 递减。

那我们可以直接剥叶子，把 \(D_i\) 从大到小排序，然后依次确定父亲。

最后检查跟合不合法就好了。

using namespace std;
typedef long long LL;
map<LL,int> node;
int n;
const int N = 1e5+7;
LL D[N];
int siz[N],fa[N],dep[N];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&D[i]);
		node[D[i]]=i;
	}
	sort(D+1,D+n+1);
	for(int i=n;i>=2;i--)
	{
		int x=node[D[i]];
		siz[x]++;
		fa[x]=node[D[i]+2ll*siz[x]-n];
		if(!fa[x]||fa[fa[x]])
		{
			cout<<-1;
			return 0;
		}
		siz[fa[x]]+=siz[x];
	}
	LL S=0;
	for(int i=2;i<=n;i++)
	{
		int x=node[D[i]];
		dep[x]=dep[fa[x]]+1;
		S+=dep[x];
	}
	if(S!=D[1])
	{
		cout<<-1;
		return 0;
	}
	for(int i=2;i<=n;i++)
	{
		int x=node[D[i]];
		printf("%d %d\n",x,fa[x]);
	}
	return 0;
}

[ARC102F] Revenge of BBuBBBlesort!

如果在 \(i\) 位置做过交换，则称 \(i\) 为一个中心点。

性质1：若 \(i\) 为中心点，则在原始排列 \(p\) 中 \(p_i = i\)

\(\texttt{proof:}\)

对 \(i\) 进行过操作后 , 有 \(p_{i-1}<p_i<p_{i+1}\)，不妨设现在\(p_{i}<i\)，那么一定会在 \(p_{i-1}\) 进行一次交换。

也就是说，我们需要使得 \(p_{i-2}>p_{i-1}>p_i\)，这需要在 \(p_{i-2}\) 进行一次交换，也就是说交换完变成 \(p_{i-3}<p_i<p_{i-2}<p_{i-1}\)，那就无法操作了。

另一侧同理。

设 \(a_i=[p_i=i]\)，那么我们只会对 \(a_i=1\) 的位置进行操作。

我们可以发现，如果 \(a_i=1,a_{i+1}=1\)，那么在 \(i,i+1\) 都不会进行操作。

那么 我们可以把 \(a\) 换分成若干段，使得每个段内没有连续相同的\(a\)。

那么各个段是独立的。

合法的条件：

  • [l,r] 内的数恰好覆盖 [l,r]

  • 把\(a_i=0\)的单独拿出来，如果这个序列中有长度大于2的下降子序列则不合法。

\(\texttt{proof:}\)

不妨设 \(p_i>p_j>p_k,i<j<k\)。

如果我们现在先交换 \(p_i,p_j\)，那么一定存在 \(a_x=1,i<x<j,p_j<p_x<p_i\)

然后再交换 \(p_i,p_k\)，那么一定存在 \(a_y=1,j<y<k,p_k<p_y<p_i\)。

现在我们要交换\(p_j,p_k\)，但是因为 现在 \(p_j<p_x\)，因此比不可能交换。

其他方案同理。

复杂度 \(O(n)\)

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+7;
int n,p[N],a[N];
void badending()
{
	printf("No\n");
	exit(0);
}
int mx[N];
void check(int l,int r)
{

	int Max=0,SMax=0;
	for(int i=l;i<=r;i++)
	{
		if(p[i]<l||p[i]>r)badending();	
		if(a[i]==0)
		{
			mx[i]=Max;
			Max=max(Max,p[i]);
		}
	}
	int Min=1e9;
	for(int i=r;i>=l;i--)
	{
		if(a[i]==0)
		{
			if(mx[i]>p[i]&&p[i]>Min)badending();
			Min=min(Min,p[i]);
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&p[i]);
		a[i]=(p[i]==i);
	}
	for(int i=1;i+2<=n;i++)
	if(a[i]==0&&a[i+1]==0&&a[i+2]==0)badending();
	for(int i=1;i<=n;i++)
	{
		int j=i;
		while(j+1<=n&&a[j]!=a[j+1])j++;
		check(i,j);
		i=j;
	}
	printf("Yes\n");
	return 0;
}

[ARC111F] Do you like query problems?

首先为了方便，转成期望。
根据期望的线性性，答案等于每个位置的贡献之和。
记 \(a_{t,i}\) 为 \(t\) 次操作后 \(i\) 位置的数，总的操作种类数 \(S=\frac{n(n+1)}{2}\times (m+m+1)\)，\(Q(i)=\frac{i(n-i+1)}{S}\)为一个当前操作是一个询问操作且包含了位置 \(i\)的概率，那么答案为：

\[\sum_{i=1}^nQ(i)\sum_{t=0}^{q-1}E(a_{t,i}) \]

根据整数概率公式，\(E(a_{t,i})=\sum_{w=1}P(a_{t,i}\ge w)\) 。
对于每个 \(w\) 独立计算，把大于等于 \(v\) 的数看成1，小于的看成0，那么最终就是 \(a_{t,i}=1\) 的概率。
设可能会导致 \(a_i\) 改变的操作为关键操作，那么就有两种，一种是 \(v\geq w\) 的取 \(\max\) 操作，一种是\(v<w\) 的取 $\min $ 操作，概率记为\(p1(i)=\frac{i(n-i+1)(m-w)}{S},p2(i)=\frac{i(n-i+1)w}{S}\)。
那么 \(t\) 次操作后 \(a_i=1\) 就是要求至少有一个关键操作且最后一次操作是 \(p1(i)\)，这个概率 \(p_{t,i,w}=\frac{p1(i)}{p1(i)+p2(i)}(1-(1-p1(i)-p2(i))^t)\) 。
记 \(s_{t,i}=\sum\limits_{w=1}^{m-1}p_{t,i,w}=\sum\limits_{w=1}^{m-1}\frac{m-w}{m}(1-(1-\frac{i(n-i+1)m}{S})^t)=\frac{m-1}{2}(1-(1-\frac{i(n-i+1)m}{S})^t)\)
枚举 \(i\)，后面就是一个等比数列求和，复杂度\(O(n\log n)\)

#include<bits/stdc++.h>
using namespace std;
const int N = 1000;
const int mod = 998244353;
const int inv2=(mod+1)/2;
int Pow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}
int n,m,q;
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline int inv(int a){return Pow(a,mod-2);}
int Sum(int a,int b)
{
	if(a==1) return b;
	return mul((Pow(a,b)-1+mod)%mod,inv(a-1));
}
int main()
{
	cin>>n>>m>>q;
	int S=mul(n,mul(n+1,mul(inv2,m+m+1)));
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int Q=mul(mul(i,n-i+1),inv(S));
		int P=mul(m-1,inv2);
		int A=mul(mul(i,n-i+1),mul(m,inv(S)));
		int W=Sum((1-A+mod)%mod,q);
		ans=(ans+mul(P,mul(Q,(q-W+mod)%mod)))%mod;
	}
	cout<<mul(ans,Pow(S,q));
	return 0;
}

[ARC131F] ARC Stamp

考虑倒序操作，将被操作过的位置设为 \(?\) ，那么可以被操作的有如下几种：\(\texttt{ARC,AR?,?RC,A?C,A??,?R?,??C}\) 。

考虑将序列划分成若干段，每段是上述的一种，那么每段是独立的，把所有被操作过的段的方案数。

因为每一段是否被选择和他前后两端都有关系，因此不妨每三个计算一次贡献。

考虑 \(dp\) ，\(f_{i,x,y}\) 表示前 \(i\) 段，第 \(i-1\) 段的状态是 \(x\)，第 \(i\) 段的状态是 \(y\) 的方案数，转移时枚举下一段的状态。

复杂度 \(O(n^2)\)

#include<bits/stdc++.h>
using namespace std;
int n,k;
const int N = 5040;
char S[N];
int a[N],b[N];
#define PII pair<int,int>
#define mk(x,y) make_pair(x,y)
PII range[N];
int m=0;
int dp[N][N][2][2];
int bef[N][N];
const int mod = 998244353;
int w[N];
int calc(int i,int x,int y,int z)
{
    if(!i)return 1;
    int A=range[i-1].second,B=range[i].first;
    int C=range[i].second,D=range[i+1].first;
    bool must1=0;
    bool must0=0;
    if(x==1&&bef[A][B]==2)must1=1;
    if(z==1&&bef[C][D]==1)must1=1;
    if(x==0&&bef[A][B]==1)must0=1;
    if(z==0&&bef[C][D]==2)must0=1;
    if(must0&&must1)return 0;
    if(must0) return y==0;
    if(must1) return (y==1)*w[i];
    if(y==0) return 1;
    return w[i]-1;
}
int main()
{
    scanf("%s",S+1);
    n=strlen(S+1);
    cin>>k;k=min(k,n);
    for(int i=1;i<=n;i++)
    if(S[i]=='A')a[i]=1;
    else if(S[i]=='R')a[i]=2;
    else a[i]=3;
    for(int i=1;i<=n;i++)b[i]=a[i];
    while(1)
    {
        bool flag=0;
        for(int i=1;i+2<=n;i++)
        {
            if(b[i]==1&&b[i+1]==2&&b[i+2]==3)
            {
                range[++m]=mk(i,i+2);
                b[i]=b[i+1]=b[i+2]=0;
                flag=1;
                continue;
            }
            if(b[i]==0&&b[i+1]==2&&b[i+2]==3)
            {
                range[++m]=mk(i+1,i+2);
                bef[i][i+1]=1;
                b[i]=b[i+1]=b[i+2]=0;
                flag=1;
                continue;
            }
            if(b[i]==1&&b[i+1]==2&&b[i+2]==0)
            {
                range[++m]=mk(i,i+1);
                bef[i+1][i+2]=2;
                b[i]=b[i+1]=b[i+2]=0;
                flag=1;
                continue;
            }
            if(b[i]==1&&b[i+1]==0&&b[i+2]==0)
            {
                range[++m]=mk(i,i);
                bef[i][i+1]=2;
                b[i]=b[i+1]=b[i+2]=0;
                flag=1;
                continue;
            }
            if(b[i]==0&&b[i+1]==2&&b[i+2]==0)
            {
                bef[i][i+1]=1;
                bef[i+1][i+2]=2;
                range[++m]=mk(i+1,i+1);
                b[i]=b[i+1]=b[i+2]=0;
                flag=1;
                continue;
            }
            if(b[i]==0&&b[i+1]==0&&b[i+2]==3)
            {
                bef[i+1][i+2]=1;
                range[++m]=mk(i+2,i+2);
                b[i]=b[i+1]=b[i+2]=0;
                flag=1;
                continue;
            }
        }
        if(!flag)break;
    }
    sort(range+1,range+m+1);
    for(int i=1;i<=m;i++)
    {
        w[i]=1;
        for(int u=range[i].first;u<=range[i].second;u++)w[i]=w[i]*3;
    }
    dp[0][0][0][0]=1;
    for(int i=1;i<=m;i++)
    for(int j=0;j<=min(i-1,k);j++)
    for(int x=0;x<=1;x++)
    for(int y=0;y<=1;y++)
    if(dp[i-1][j][x][y])
    {
        for(int z=0;z<=1;z++)
        {
            dp[i][j+z][y][z]=(dp[i][j+z][y][z]+1ll*dp[i-1][j][x][y]*calc(i-1,x,y,z)%mod)%mod;
        }
    }
    int res=0;
    for(int i=0;i<=k;i++)
    for(int c=0;c<=1;c++)
    for(int d=0;d<=1;d++)
    res=(res+1ll*dp[m][i][c][d]*calc(m,c,d,0)%mod)%mod;
    cout<<res;
    return 0;
}

[ARC085F] NRE

简单题，设 \(dp_{i,j}\) 表示前 \(i\) 个位置，覆盖最远的区间覆盖到 \(j\) 的最小代价，转移是简单的。
那么只需要线段树优化 \(dp\) 即可。

// LUOGU_RID: 111038731
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
typedef long long LL;
void ckmax(int &x,int v){x=max(x,v);}
int tag[N*4],mn[N*4],upd[N*4];
const int INF = 1e8;
void pushtag(int k,int v)
{
	mn[k]+=v;
	tag[k]+=v;
	upd[k]+=v;
}
void pushmin(int k,int v)
{
	mn[k]=min(mn[k],v);
	upd[k]=min(upd[k],v);
}
void pushdown(int k)
{
	if(tag[k])
	{
		pushtag(k<<1,tag[k]);
		pushtag(k<<1|1,tag[k]);
		tag[k]=0;
	}
	if(upd[k]<=INF)
	{
		pushmin(k<<1,upd[k]);
		pushmin(k<<1|1,upd[k]);
		upd[k]=INF;
	}
}
void pushup(int k)
{
	mn[k]=min(mn[k<<1],mn[k<<1|1]);
}
void Add(int k,int l,int r,int L,int R,int v)
{
	if(L<=l&&r<=R)
	{
		pushtag(k,v);
		return;
	}	
	pushdown(k);
	int mid=(l+r)>>1;
	if(L<=mid)Add(k<<1,l,mid,L,R,v);
	if(R>mid)Add(k<<1|1,mid+1,r,L,R,v);
	pushup(k);
}
void Min(int k,int l,int r,int L,int R,int v)
{
	if(L<=l&&r<=R)
	{
		pushmin(k,v);
		return;
	}	
	pushdown(k);
	int mid=(l+r)>>1;
	if(L<=mid)Min(k<<1,l,mid,L,R,v);
	if(R>mid)Min(k<<1|1,mid+1,r,L,R,v);
	pushup(k);
}
int Qry(int k,int l,int r,int L,int R)
{
	if(L<=l&&r<=R)return mn[k];
	pushdown(k);
	int res=INF;
	int mid=(l+r)>>1;
	if(L<=mid)res=min(res,Qry(k<<1,l,mid,L,R));
	if(R>mid)res=min(res,Qry(k<<1|1,mid+1,r,L,R));
	return res;
}
void Build(int k,int l,int r)
{
	mn[k]=INF;
	upd[k]=INF;
	tag[k]=0;
	if(l==r)return;
	int mid=(l+r)>>1;
	Build(k<<1,l,mid);
	Build(k<<1|1,mid+1,r);
}
int n,w[N],m,dp[N];
void ADD(int l,int r,int v)
{
	Add(1,0,n,l,r,v);
}
void MIN(int l,int r,int v)
{
	Min(1,0,n,l,r,v);
}
int QRY(int l,int r)
{
	return Qry(1,0,n,l,r);
}
vector<int> G[N];
int main()
{
//	freopen("a.in","r",stdin);
//	freopen("a.ans","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int l,r;
		scanf("%d %d",&l,&r);
		G[l].push_back(r);
	}
	Build(1,0,n);
	MIN(0,0,0);
	for(int i=1;i<=n;i++)
	{
		for(auto x:G[i])MIN(x,x,QRY(0,x-1));
		//a[i]=0
		if(w[i]==1)ADD(0,i-1,1);
		//a[i]=1
		if(w[i]==0)ADD(i,n,1);
	}
	cout<<QRY(0,n);
	return 0;
}

[ARC094F] Normalization

可以发现如果把 \(a,b,c\) 设为 \(0,1,2\)，那么操作不会改变字符串中数字总和 \(\%3\) 意义下的数。
首先特判掉 \(S\) 都是一个字符以及 \(|S|<=3\) 的情况。
那么一个串 \(T\) 可以被得到的必要条件是： \(T\) 中存在一对相邻且相等的位置，且两个序列 \(\%3\) 相等。
猜一下这个也是充分的，事实也确实如此。
因此直接 \(dp\) 就好了。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
const int mod = 998244353;
char s[N];
int n;
int dp[N][3][2][3];
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	bool flag=1,flag2=0;
	for(int i=1;i<n;i++)
	{
		flag&=(s[i]==s[i+1]);
		flag2|=(s[i]==s[i+1]);
	}
	if(flag)
	{
		printf("1\n");
		return 0;
	}
	if(n==2)
	{
		cout<<2;
		return 0;
	}
	if(n==3)
	{
		if(s[1]!=s[2]&&s[2]!=s[3]&&s[1]!=s[3])cout<<3;
		else if(s[1]==s[2])cout<<6;
		else if(s[2]==s[3])cout<<6;
		else cout<<7;
		return 0;
	}
	for(int c=0;c<=2;c++)dp[1][c][0][c]=1;
	int w=0;
	for(int i=1;i<=n;i++)w=(w+s[i]-'a')%3; 
	for(int i=2;i<=n;i++)
	{
		for(int v=0;v<=2;v++)
		for(int c=0;c<=1;c++)
		for(int a=0;a<=2;a++)
		if(dp[i-1][v][c][a])
		{
			for(int b=0;b<=2;b++)
			dp[i][(v+b)%3][c|(a==b)][b]=(dp[i][(v+b)%3][c|(a==b)][b]+dp[i-1][v][c][a])%mod;
		}
	}
	int ans=0;
	for(int c=0;c<=2;c++)ans=(ans+dp[n][w][1][c])%mod;
	cout<<(ans+1-flag2)%mod;
	return 0;
}

[ARC082F] Sandglass

设 \(f_{a}(t)\) 为初始值为 \(a\) 的情况下，时间 \(t\) 时的值。
那么整个图像就是一条折线，碰到 \(y=0\) 和 \(y=X\) 就会顶着，而遇到 \(x=r_i\) 就会改变斜率。
容易发现对于 \(0\leq a\leq b\leq X,t\in Z,f_a(t)\leq f_b(t)\) 。
同时，如果在某一时刻 \(t\)，\(f_a(t)=f_0(t)\) 或者 \(f_a(t)=f_X(t)\)，那么之后，\(f_a(t)\) 就会一直和 \(f_0(t)\) 或 \(f_X(t)\) 相等，而如果从来没有，那么说明\(f_a(t)\)一直没有触碰上下界，因此当前位置可以直接求出，设为 \(x\)。
那么如果 \(x<f_0(t)\)，最终就是 \(f_0(t)\)，如果 \(>f_X(t)\)，最终就是 \(f_X(t)\)，否则就是 \(x\) 。
复杂度 \(O(n+m)\)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
typedef long long LL;
LL X,O,n,q,fo,fx,f,p[N];
int main()
{
	scanf("%lld",&X);
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%lld",&p[i]);
	fo=O;fx=X;f=0;
	int now=0;
	cin>>q;
	while(q--)
	{
		LL t,a;
		scanf("%lld %lld",&t,&a);
		while(now+1<=n&&p[now+1]<=t)
		{
			if(now&1)
			{
				fx=min(X,fx+p[now+1]-p[now]);
				fo=min(X,fo+p[now+1]-p[now]);
				f+=p[now+1]-p[now];
			}
			else 
			{
				fx=max(O,fx-p[now+1]+p[now]);
				fo=max(O,fo-p[now+1]+p[now]);
				f-=p[now+1]-p[now];
			}
			now++;
		}
		LL Fx=0,Fo=0,Fa=0;
		if(now&1)
		{
			Fx=min(X,fx+t-p[now]);
			Fo=min(X,fo+t-p[now]);
			Fa=f+t-p[now];
		}
		else 
		{
			Fx=max(O,fx-t+p[now]);
			Fo=max(O,fo-t+p[now]);
			Fa=f-t+p[now];
		}
		Fa+=a;
		Fa=min(Fa,Fx);
		Fa=max(Fa,Fo);
		printf("%lld\n",Fa); 
	}
	return 0;
}

标签：Atcoder,选做,const,int,siz,操作,return,mod
From： https://www.cnblogs.com/jesoyizexry/p/17315243.html

相关文章

  • Atcoder Grand Contest 060 D - Same Descent Set
    先推式子。设\(f(S)\)表示decent集合恰好为\(S\)的排列个数，\(g(S)\)表示\(S\)是\(p\)的decent集合的一个子集的排列\(p\)个数，\(g'(\{a_1,a_2,\cdots,a_k\})=\dfrac{n!}{a_1!(a_2-a_1)!(a_3-a_2)!\cdots(a_k-a_{k-1})!(n-a_k)!}\)，那么有：\[\begin{aligned}ans=&\......
  • Atcoder Beginner Contest ABC302 题解
    代码见此：https://atcoder.jp/contests/abc302/submissions?f.Task=&f.LanguageName=&f.Status=&f.User=frequenter。AAttackhttps://atcoder.jp/contests/abc302/tasks/abc302_a直接计算a/b，有余数的话答案加一。BFindSnukehttps://atcoder.jp/contests/abc302/tasks/abc......
  • AtCoder Regular Contest 132 D Between Two Binary Strings
    洛谷传送门AtCoder传送门提供一个dp思路。下文设串长为\(n\)，串中\(1\)个数为\(m\)。考虑如何求\(d(s,t)\)。设\(s\)的\(1\)位置分别为\(a_1,a_2,...,a_m\)，\(t\)的\(1\)位置分别为\(b_1,b_2,...,b_m\)。那么\(d(s,t)=\sum\limits_{i=1}^m|a_i-b......
  • AtCoder Beginner Contest 302 Ex Ball Collector
    洛谷传送门AtCoder传送门考虑如果只询问一次怎么做。连边\((a_i,b_i)\)，对于每个连通块分别考虑。这是ARC111B，如果一个连通块是树，肯定有一个点不能被选；否则有环，一定能构造一种方案，使得每个点都被选。那么现在对于每个点都要求，考虑dfs时合并当前的\((a_u,b_u)\)，并且使用......
  • 【题解】Atcoder ABC302 F,G,Ex
    完全不会G和Ex，这些套路还是要积累一下的。F.MergeSet题目描述：给定\(n\)个集合，每次可以合并两个有交的集合，问最少多少次合并可以让\(1\)和\(m\)位于同一个集合中。题目分析：一开始将题读成了将\([1,m]\)位于同一个集合中，然后就感觉这个题相当不可做。因为集合的元......
  • AtCoder Regular Contest 130 E Increasing Minimum
    这题太神仙了吧！感觉还不是很懂，但是尽力理一下思路。设\(t_x\)为最大的\(j\)使得\(i_j=x\)，不存在则\(t_x=0\)。设\(1\simn\)的数按照\(t\)从小到大排序后是\(p_1,p_2,...,p_n\)，设\(q_i\)为\(i\)在\(p\)中的排名，即\(q_{p_i}=i\)。发现正着不好考虑，......
  • AtCoder Beginner Contest 302
    A-Attack(abc302a)题目大意给定怪物的血量\(a\)和你每次攻击扣除的血量\(b\)，问打多少次怪物才会死。解题思路答案即为\(\lceil\frac{a}{b}\rceil=\lfloor\frac{a+b-1}{b}\rfloor\)神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=long......
  • AtCoder Regular Contest 130 C Digit Sum Minimization
    洛谷传送门AtCoder传送门分类讨论，但是写起来挺答辩的。首先发现我们要使进位尽量多。特判怎么重排都没有进位的情况（\(a_i+b_i<10\)）。然后枚举个位选的两个数字，并且要求它们和\(\ge10\)。如果当前位两个位都有数字，那么从小到大枚举数位的和\(\in[9,18]\)；如果有数字......
  • AtCoder Regular Contest 133 E Cyclic Medians
    洛谷传送门AtCoder传送门其实是套路题，但是为什么做不出来啊第一步就是经典套路。枚举\(k\)，统计中位数\(>k\)的方案数，加起来就是中位数的总和。那么现在\(x_{1\simn},y_{1\simm}\)就变成了\(0/1\)序列，考虑一次操作，如果\((x,y)=(0,0)\)，那么\(a\)会变成\(0\)......
  • AtCoder Regular Contest 124 F Chance Meeting
    洛谷传送门AtCoder传送门感觉挺高妙的……为了方便，不妨把横纵坐标都整体减\(1\)。如果单独考虑上下移动，方案数是\(\binom{2n}{n}\)。发现两个人上下总共移动\(n\)次后一定会在同一行，设这行编号为\(x\)，那么最后带个\(\binom{n}{x}^2\)的系数，并且除掉上下移动后方案本质......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99