国庆集训 Test 1

T1

考虑把数组排序，每次对当前的 $b_i$ 找到一个小于等于他且最大的 $a_i$ 与之配对并删除。直接使用优先队列维护时间复杂度为 $\text{O}(n \log n)$ 。

考虑使用链表类的储存方式在数组上实现指针跳跃，时间复杂度可以降至 $\text{O}(n)$ 。

T2

仔细看发现是卡塔兰数的变种。但是由于有子序列的限制，我们考虑使用 dp 实现转移。

一个简单的观察是男生的贡献为 $1$ ，女生的贡献为 $-1$ ，那么使得前缀和非负，也是卡塔兰数的实际意义。

令 $dp_{i,j,k}$ 表示已经完成了第 $i$ 位，当前位置放 $-1/1$ 后的前缀和为 $j$ ，并已匹配到子序列的第 $k$ 位。

那么大力分类讨论：

当 $j$ 为正整数时我们可以放置女生，否则只能放置男生；
当前位置选择对子序列产生影响，或者选择对子序列无影响，但是一定需要考虑对后一位是否会有影响。

由于当前的枚举的 $k$ 使得 $a_k$ 的请款不同，得到转移方程大概有

dp_{i,j,k} = dp_{i-1,j-1,k} + dp_{i-1,j+1, k} + dp_{i-1,j+1, k-1} \\ dp_{i,j,k} = dp_{i-1,j-1,k} + dp_{i-1,j+1, k} + dp_{i-1,j-1, k-1}

具体的转移条件与讨论详见代码。

成绩出来发现只有 70 pts，错误的测试点输出了 0，发现有一个初始化类型的条件没有判。

#include<iostream>
#include<cstdio>
#include<cctype>
using namespace std;

template <typename T>
T read(){
    T x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
    while(isdigit(c)){x=x*10+(c^48);c=getchar();}
    return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=5e2+1e1,Mod=998244353;
const lint INF=1e18+1e9;

lint dp[MAXN][MAXN][2];
int a[MAXN],n,m;

int main(void){
    
    n=readint,m=readint,dp[0][0][0]=1;
    for(int i=m;i;i--) a[i]=readint;
    for(int i=1;i<=n+n;i++){
        for(int j=0;j<=i;j++){
            if((i+j)&1) continue;
            if(m && !a[1] && j>0) (dp[j][0][1]+=dp[j-1][0][0])%=Mod; // Here
            for(int k=1;k<=m;k++){
                if(!a[k]){
                    if(j>0 && k<m && !a[k+1]) (dp[j][k][1]+=dp[j-1][k][0])%=Mod;
                    if(k<m && a[k+1]) (dp[j][k][1]+=dp[j+1][k][0])%=Mod;
                    (dp[j][k][1]+=dp[j+1][k-1][0])%=Mod;
                }
                else{
                    if(j>0 && k<m && !a[k+1]) (dp[j][k][1]+=dp[j-1][k][0])%=Mod;
                    if(k<m && a[k+1]) (dp[j][k][1]+=dp[j+1][k][0])%=Mod;
                    if(j>0) (dp[j][k][1]+=dp[j-1][k-1][0])%=Mod;
                }
            }
            if(j>0) (dp[j][m][1]+=dp[j-1][m][0])%=Mod;
            (dp[j][m][1]+=dp[j+1][m][0])%=Mod;
        }
        for(int j=0;j<=n+n;j++) for(int k=0;k<=m;k++) dp[j][k][0]=dp[j][k][1];
        for(int j=0;j<=n+n;j++) for(int k=0;k<=m;k++) dp[j][k][1]=0;
    }
    printf("%lld\n",dp[0][m][0]);
    
    return 0;
}

T3

我们发现由于每个人都会向前或向左看齐，那么意味着这是一种类似于树形的形态与结构。

那么每次我们考虑钦定树的叶子结点一定保持正确的步伐，那么答案即是 $(1,1)$ 处的正确步伐。

对于每一个遍历时的结点，如果他是边界上的结点，那么我们强制他为正确的步伐，否则他一定是由其子结点按概率转移过来的。

注意到我们不能从根节点1直接向下遍历并每次记录答案，因为根节点的答案可能在沿途中传递下去而重复计算。

#include<iostream>
#include<cstdio>
#include<cctype>
using namespace std;

template <typename T>
T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=x*10+(c^48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=1e6+1e1,Mod=998244353;
const lint INF=1e18+1e9;

struct Edge{
	int nxt,to;
}e[MAXN<<1];
bool vis[MAXN],dot[MAXN];
lint dp[MAXN][2],p[MAXN][2],Ans0,Ans1,p100;
int head[MAXN],n,m,tot;

lint Abs(lint x){
	return (x<0 ? x%Mod+Mod : x)%Mod;
}

lint Qpow(lint A,int B){
	lint res=1;
	while(B>0){
		if(B&1) (res*=A)%=Mod;
		(A*=A)%=Mod,B>>=1;
	}
	return res;
}

void Addedge(int u,int v){
	e[++tot]=(Edge){head[u],v};
	head[u]=tot;
	return;
}

void Dfs(int u){
	vis[u]=true,dp[u][0]=dp[u][1]=1;
	if(dot[u]) dp[u][1]=0;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(vis[v]) continue;
		Dfs(v);
		(dp[u][0]*=Abs((dp[v][0]*p[v][0]%Mod)+(dp[v][1]*p[v][1]%Mod)))%=Mod;
		(dp[u][1]*=Abs((dp[v][0]*p[v][1]%Mod)+(dp[v][1]*p[v][0]%Mod)))%=Mod;
	}
	return;
}

int main(void){
	
	scanf("%d%d",&n,&m),dot[1]=true,Ans0=Ans1=1,p100=Qpow(100,Mod-2);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
		int op=readint,x=(i-1)*m+j-(!op ? m : 1);
		if((i-1)*m+j==1) continue;
		Addedge(x,(i-1)*m+j),Addedge((i-1)*m+j,x);
		if(i==1 || j==1 || i==n || j==m) dot[(i-1)*m+j]=true;
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
		p[(i-1)*m+j][1]=Abs(readlint*p100);
		p[(i-1)*m+j][0]=Abs(1-p[(i-1)*m+j][1]);
	}
	Dfs(1),printf("%lld\n",dp[1][0]);

	return 0;
}

国庆集训 Test 1

国庆集训 Test 1

T1

T2

T3

感谢您的支持，我会继续努力的!