AtCoder Beginner Contest 263（ABC263）A-F 题解

当出现刚好两次的数字只有一个，且出现刚好三次的数字只有一个时为 Yes。

#include
#define Max(a,b) ((ab)&&(a=b))
using namespace std;
 
 
 
inline int read()
{
	int x=0,f=1;static char ch;
	while(ch=getchar(),ch<48)if(ch==45)f=0;
	do x=(x<<1)+(x<<3)+(ch^48);
	while(ch=getchar(),ch>=48);
	return f?x:-x;
}
 
int cnt[15],_2,_3;
 
int main()
{
	for(int i=1,x;i<=5;i++)
		x=read(),cnt[x]++;
	for(int i=1;i<=13;i++)
	{
		if(cnt[i]==2)_2++;
		if(cnt[i]==3)_3++;
	}
	if(_2==1&&_3==1)printf("Yes");
	else printf("No");
	
	return 0;
}

连边，直接以 1 1 1 为根 dfs，求得 n n n 的深度即可。

#include
#define Max(a,b) ((ab)&&(a=b))
using namespace std;

const int M=55;

inline int read()
{
	int x=0,f=1;static char ch;
	while(ch=getchar(),ch<48)if(ch==45)f=0;
	do x=(x<<1)+(x<<3)+(ch^48);
	while(ch=getchar(),ch>=48);
	return f?x:-x;
}

int n,dep[M];
vector E[M];

void dfs(int x)
{
	for(int v:E[x])
	{
		dep[v]=dep[x]+1;
		dfs(v);
	}
}

int main()
{
	n=read();
	for(int i=2,fa;i<=n;i++)
	{
		fa=read();
		E[fa].push_back(i);
	}
	dfs(1);
	printf("%d",dep[n]);
	
	return 0;
}

类似全排列的形式，直接爆搜即可。

#include
#define Max(a,b) ((ab)&&(a=b))
using namespace std;

inline int read()
{
	int x=0,f=1;static char ch;
	while(ch=getchar(),ch<48)if(ch==45)f=0;
	do x=(x<<1)+(x<<3)+(ch^48);
	while(ch=getchar(),ch>=48);
	return f?x:-x;
}

int n,m,a[15];

void dfs(int x)
{
	if(x>n)
	{
		for(int i=1;i<=n;i++)
			printf("%d ",a[i]);
		printf("n");
		return;
	}
	for(int i=a[x-1]+1;i<=m;i++)
		a[x]=i,dfs(x+1),a[x]=0;
}

int main()
{
	n=read(),m=read();
	dfs(1);
	
	return 0;
}

设 p r e ( i , 0 / 1 ) pre(i,0/1) pre(i,0/1) 表示处理完 1 ∼ i 1sim i 1∼i，其中 已不用刷子/正在用刷子 时的最小值。那么

p r e ( i , 0 ) = min ⁡ ( p r e ( i − 1 , 0 ) , p r e ( i − 1 , 1 ) ) + a i pre(i,0)=minleft(pre(i-1,0),pre(i-1,1)right)+a_i pre(i,0)=min(pre(i−1,0),pre(i−1,1))+ai​

p r e ( i , 1 ) = p r e ( i − 1 , 1 ) + L pre(i,1)=pre(i-1,1)+L pre(i,1)=pre(i−1,1)+L

同理设 s u f ( i , 0 / 1 ) suf(i,0/1) suf(i,0/1)，转移类似。

那么枚举划分点 i i i，那么当前为前缀最小值和后缀最小值之和。对这个值取最小值即可。

注意前缀和后缀可以为空。

#include
#define Max(a,b) ((ab)&&(a=b))
using namespace std;

typedef long long ll;
const int M=2e5+5;

inline int read()
{
	int x=0,f=1;static char ch;
	while(ch=getchar(),ch<48)if(ch==45)f=0;
	do x=(x<<1)+(x<<3)+(ch^48);
	while(ch=getchar(),ch>=48);
	return f?x:-x;
}

int n,L,R,a[M];
ll pre[M][2],suf[M][2],ans=1e18;

int main()
{
	n=read(),L=read(),R=read();
	for(int i=1;i<=n;i++)a[i]=read();
	
	memset(pre,0x3f,sizeof(pre));
	memset(suf,0x3f,sizeof(suf));
	
	pre[0][0]=pre[0][1]=0;
	for(int i=1;i<=n;i++)
	{
		pre[i][0]=min(pre[i-1][0],pre[i-1][1])+a[i];
		pre[i][1]=pre[i-1][1]+L;
	}
	suf[n+1][0]=suf[n+1][1]=0;
	for(int i=n;i>0;i--)
	{
		suf[i][0]=min(suf[i+1][0],suf[i+1][1])+a[i];
		suf[i][1]=suf[i+1][1]+R;
	}
	for(int i=0;i<=n;i++)
		Min(ans,min(pre[i][0],pre[i][1])+min(suf[i+1][0],suf[i+1][1]));
	printf("%lld",ans);
	
	return 0;
}

期望 DP。逆序考虑，设 d p i dp_i dpi​ 表示从 i i i 到 N N N 的期望步数，那么：

d p i = ∑ j = i i + A i d p j + 1 A i + 1 dp_i=dfrac{sumlimits_{j=i}^{i+A_i}{dp_j+1}}{A_i+1} dpi​=Ai​+1j=i∑i+Ai​​dpj​+1​

等式两边都有 d p i dp_i dpi​，因此移项并化简后得到：

d p i = 1 + A i + ∑ j = i + 1 i + A i d p j A i dp_i=dfrac{1+A_i+sumlimits_{j=i+1}^{i+A_i}{dp_j}}{A_i} dpi​=Ai​1+Ai​+j=i+1∑i+Ai​​dpj​​

其中 ∑ sum ∑ 部分可以用后缀和求出。

#include
#define Max(a,b) ((ab)&&(a=b))
using namespace std;

typedef long long ll;
const ll P=998244353;
const int M=2e5+5;

inline int read()
{
	int x=0,f=1;static char ch;
	while(ch=getchar(),ch<48)if(ch==45)f=0;
	do x=(x<<1)+(x<<3)+(ch^48);
	while(ch=getchar(),ch>=48);
	return f?x:-x;
}

int n,a[M];

ll Inv[M],dp[M],s[M];

void ADD(ll &x,ll y){(x+=y)>=P?x-=P:x;}

ll ksm(ll a,ll b)
{
	ll res=1ll;
	while(b)
	{
		if(b&1ll)res=res*a%P;
		a=a*a%P,b>>=1ll;
	}
	return res;
}

void init()
{
	for(int i=1;i<=n;i++)
		Inv[i]=ksm(i,P-2);
}

int main()
{
	n=read();
	for(int i=1;i0;i--)
	{
		ll res=(s[i+1]-s[i+1+a[i]]+P)%P;
		dp[i]=(a[i]+1+res)%P*Inv[a[i]]%P;
		s[i]=(s[i+1]+dp[i])%P;
	}
	
	printf("%lld",dp[1]);
	
	return 0;
}

按照题意，我们可以先建出一棵 N + 1 N+1 N+1 层的满二叉树，其中最后一层从左往右依次为 1 ∼ 2 N 1sim 2^N 1∼2N。

那么从第一层开始往下搜索，枚举是左子树赢还是右子树赢，取 max ⁡ max max 就可以得到答案。我们再记录一个数 w i n win win，表示目前连胜的场数。那么当访问到最后一层时，我们就可以知道该叶子往上能赢多少场。

加个记忆化 d p ( p , w i n ) dp(p,win) dp(p,win) 表示到节点 p p p，连胜 w i n win win 场时的最大收益即可。

#include
#define Max(a,b) ((ab)&&(a=b))
#define ls p<<1
#define rs p<<1|1
using namespace std;

typedef long long ll;
const int M=(1<<17)+5;

inline int read()
{
	int x=0,f=1;static char ch;
	while(ch=getchar(),ch<48)if(ch==45)f=0;
	do x=(x<<1)+(x<<3)+(ch^48);
	while(ch=getchar(),ch>=48);
	return f?x:-x;
}

int n,c[M][18];
ll dp[M][18];

ll dfs(int p,int win)
{
	if(p>=(1<
	memset(dp,-1,sizeof(dp));
	
	n=read();
	for(int i=0;i<(1< 
 
G - Erasing Prime Pairs 
听说是网络流，但我不会。
 
 
Ex - Intersection 2 
我只知道有个二分，但我计算几何是白痴。