9.16 近期比赛总结

26 CSP 七连测 day3 | 正睿 OI 题目 #3642 | 正睿 OI 这题用的是 DP，感觉更好想一点。。。 先考虑不是一个环，设 $dp_{i,1/0}$ 表示当前这个位置是点亮还是熄灭，$dp$ 到最后时在用概率把链连成环需要的贡献减去即可。这个贡献的计算考虑每次遇到不确定状态的位置时，我们都会新增一条分支，需要减去的贡献也会乘以 $2$，最后还需要根据头和尾的状态进行分类讨论。 代码： C++#include using namespace std; typedef long long ll; const int N=2e6+5; const int mod=998244353; int T,n; string s; ll dp[N][2],p2; ll qpow(ll x,int y){ ll res=1; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y=1; } return res; } void solve(){ int sum0=0; scanf("%d",&n); cins; dp[0][0]=0,dp[0][1]=(s[0]!='0'); sum0+=(s[0]=='0'); ll p=1+(s[0]=='?'); for(int i=1;i#include using namespace std; typedef long long ll; const int N=2e6+5; const int mod=998244353; int T,n; string s; ll dp[N][2],p2; ll qpow(ll x,int y){ ll res=1; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y=1; } return res; } void solve(){ int sum0=0; scanf("%d",&n); cins; dp[0][0]=0,dp[0][1]=(s[0]!='0'); sum0+=(s[0]=='0'); ll p=1+(s[0]=='?'); for(int i=1;in;i++){ sum0+=(s[i]=='0'); dp[i][0]=dp[i][1]=0; if(s[i]!='1') (dp[i][0]+=dp[i-1][0]+dp[i-1][1])%=mod; if(s[i]!='0'){ (dp[i][1]+=dp[i-1][0]+dp[i-1][1])%=mod; if(s[i-1]=='?') (dp[i][1]+=(p*p2%mod))%=mod; if(s[i-1]=='0') (dp[i][1]+=p)%=mod; } if(s[i]=='?') (p*=2)%=mod; } if(s[n-1]=='?'){ if(s[0]=='?') (dp[n-1][1]+=mod-((p*p2)%mod*p2%mod))%=mod; if(s[0]=='1') (dp[n-1][1]+=mod-(p*p2%mod))%=mod; dp[n-1][1]=(dp[n-1][1]%mod+mod)%mod; } if(s[n-1]=='1'){ if(s[0]=='?') (dp[n-1][1]+=mod-(p*p2%mod))%=mod; if(s[0]=='1') (dp[n-1][1]+=mod-p)%=mod; dp[n-1][1]=(dp[n-1][1]%mod+mod)%mod; } printf("%d\n",(dp[n-1][0]+dp[n-1][1]+!sum0)%mod); } signed main(){ freopen("light.in","r",stdin); freopen("light.out","w",stdout); scanf("%d",&T); p2=qpow(2,mod-2); while(T--) solve(); return 0; } 题目 #3643 | 正睿 OI 计数题。 我们考虑最后剩下的颜色一共有 $i$ 种，我们考虑最终得到的颜色序列（将一个长度为 $2$ 的块合并成一个块）一定是一个序列，会发现一个性质，那就是这个序列（在左右两边补两个 $0$）的一个峰一定长度为 $2$，因为作为峰，它一定涂色得比相邻的两个晚，则不可能长度为 $1$。 设 $dp_{i,j}$ 表示满足有 $i$ 个数和 $j$ 个峰的排列的个数，有： $$ dp_{i,j}=2j\cdot dp_{i,j-1}+(n-2j+2)\cdot dp_{i-1,j-1} $$ 统计答案有： $$ ans=\sum_{i=1}^{min(n-1,m)} {m-1 \choose i-1} \sum_{j=1}^{\frac{i}{2}+1}{i-j \choose n-i-j} dp_{i,j} $$ 代码： C++#include using namespace std; #define int long long const int N=4005; const int mod=998244353; int n,m,ans; int cm[N],c[N][N],dp[N][N]; int qpow(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y=1; } return res; } void init(){ c[0][0]=1; for(int i=1;inm; cm[0]=1,dp[1][1]=1; init(); for(int i=1;i#include using namespace std; #define int long long const int N=4005; const int mod=998244353; int n,m,ans; int cm[N],c[N][N],dp[N][N]; int qpow(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y=1; } return res; } void init(){ c[0][0]=1; for(int i=1;in;i++) for(int j=0;ji;j++){ c[i][j]=c[i-1][j]; if(j) (c[i][j]+=c[i-1][j-1])%=mod; } } signed main(){ cinnm; cm[0]=1,dp[1][1]=1; init(); for(int i=1;imin(n-1,m);i++){ cm[i]=cm[i-1]*(m-i)%mod*qpow(i,mod-2)%mod; int sum=0; for(int j=1;ji/2+1;j++){ if(i!=1) dp[i][j]=((2*j*dp[i-1][j])%mod+((i-2*j+2)*dp[i-1][j-1]%mod))%mod; sum=(sum+dp[i][j]*c[i-j][n-i-j]%mod)%mod; } ans=(ans+sum*cm[i-1]%mod)%mod; } coutans; return 0; } 26 NOIP 十连测 day2 | 正睿 OI 题目 #3646 | 正睿 OI 考虑原图是一颗树，我们按照从叶子到根节点的顺序操作，如果当前点连接它所有儿子的边的数量为偶数，那就一一配对，如果为奇数，那就把连接当前点和它父亲的点的那一条边也放进来计算即可。 如果不是一棵树，我们考虑把返祖边也放入边集即可。 代码： C++#include using namespace std; const int N=2e5+5; int T,n,m; int tag[N],vis[N]; vector ans,g[N]; bool dfs(int u,int f,int fu){ vector e; for(auto[v,w]:g[u]){ if(tag[w]||v==f) continue; if(vis[v]) e.push_back(w); else{ vis[v]=1; int res=dfs(v,u,w); if(res) e.push_back(w); } } for(int i=1;inm; ans.clear(); for(int i=1;iuv; g[u].push_back({v,i}); g[v].push_back({u,i}); } vis[1]=1; dfs(1,0,0); for(auto[x,y]:ans) coutT; while(T--) solve(); return 0; }#include using namespace std; const int N=2e5+5; int T,n,m; int tag[N],vis[N]; vectorpairint,int ans,g[N]; bool dfs(int u,int f,int fu){ vectorint e; for(auto[v,w]:g[u]){ if(tag[w]||v==f) continue; if(vis[v]) e.push_back(w); else{ vis[v]=1; int res=dfs(v,u,w); if(res) e.push_back(w); } } for(int i=1;ie.size();i+=2) ans.push_back({e[i-1],e[i]}),tag[e[i-1]]=tag[e[i]]=1; if(e.size()&1) return ans.push_back({e.back(),fu}),tag[e.back()]=tag[fu]=1,0; return 1; } void solve(){ cinnm; ans.clear(); for(int i=1;in;i++) vis[i]=0,g[i].clear(); for(int i=1;im;i++) tag[i]=0; for(int i=1,u,v;im;i++){ cinuv; g[u].push_back({v,i}); g[v].push_back({u,i}); } vis[1]=1; dfs(1,0,0); for(auto[x,y]:ans) coutx" "y"\n"; } signed main(){ cinT; while(T--) solve(); return 0; } 题目 #3647 | 正睿 OI 不难发现，对于当前处理的二元组 $(a_i,b_i)$，$S$ 中这一段区间必须是空的。虑转换一下思考方式，对于一段空区间 $[l,r]$，我们计算期望新增的二元对数量，设 $C(l,r)$ 表示被区间完全包围的二元对数量，有： $$ \mathbb{E} = 1 + \frac{1}{|C(l, r)|} \sum_{i \in C(l, r)} \Big( E(l, a_i - 1) + E(a_i + 1, r) \Big) $$ 按照遍历顺序优化一下即可。 代码： C++#include using namespace std; #define int long long const int N=6005,mod=998244353; int n,m; int inv[N],dp[N][N],lr[N],la[N],rl[N],ra[N],cnt[N],h[N]; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cinn; m=2*n; inv[1]=1; for(int i=2;iuv; int l=min(u,v),r=max(u,v); lr[l]=r,la[l]=u,rl[r]=l,ra[r]=u; } for(int l=m;l=1;l--){ int id=lr[l]; if(id){ int ai=la[l]; for(int r=id;r=l){ int ai=ra[r]; int t=(l#include using namespace std; #define int long long const int N=6005,mod=998244353; int n,m; int inv[N],dp[N][N],lr[N],la[N],rl[N],ra[N],cnt[N],h[N]; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cinn; m=2*n; inv[1]=1; for(int i=2;im;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; for(int i=1;in;i++){ int u,v; cinuv; int l=min(u,v),r=max(u,v); lr[l]=r,la[l]=u,rl[r]=l,ra[r]=u; } for(int l=m;l=1;l--){ int id=lr[l]; if(id){ int ai=la[l]; for(int r=id;rm;r++){ cnt[r]++; int t=(ai+1r?dp[ai+1][r]:0); h[r]=(h[r]+t)%mod; } } int sum=0; for(int r=l;rm;r++){ if(rl[r]=l){ int ai=ra[r]; int t=(lai-1?dp[l][ai-1]:0); sum=(sum+t)%mod; } if(!cnt[r]) dp[l][r]=0; else dp[l][r]=(1+(sum+h[r])%mod*inv[cnt[r]])%mod; } } coutdp[1][m]"\n"; return 0; } 题目 #3648 | 正睿 OI 神了。 不难发现 $10^{18} 考虑 DP 预处理最优策略。设 $f[l][r]$ 表示最坏情况下猜出答案的最少询问次数，$g[l][r]$ 记录最优决策。枚举分界点 $k \in (l, 60 - r)$ 询问 $2^k$：若返回商则确定最高 $60 - k$ 位，转移到 $(l, 60 - k)$；若返回余数则确定最低 $k$ 位，转移到 $(k, r)$。有转移 $f[l][r] = \min_k { \max(f[k][r], f[l][60 - k]) + 1 }$。 考虑两种可以在 $1$ 步内直接收尾的边界情况。第一种是 $len = 1$，此时只剩第 $l$ 位未知，答案仅可能为 $ans$ 或 $ans + 2^l$。直接询问 $ans + 2^l$，若返回余数为 $0$ 或商为 $1$ 说明为 $ans + 2^l$，否则为 $ans$。 第二种是 $len 因此在 init() 中按长度 $len$ 从小到大预处理，满足上述边界时置 $f[l][r] = 1$，其余情况枚举 $k$ 转移，最坏只需 $4$ 步；在 solve() 中若命中两类边界则一步收尾，否则查表询问 $2^k$ 迭代状态即可。 代码： C++#include"guess.h" #include #define int long long using namespace std; int f[110][110],g[110][110]; int init(){ memset(f,0x3f,sizeof f); for(int len=1;lenlen){ f[l][r]=1; continue; } for(int k=l+1;k#include"guess.h" #include #define int long long using namespace std; int f[110][110],g[110][110]; int init(){ memset(f,0x3f,sizeof f); for(int len=1;len60;len++) for(int l=0;l+len60;l++){ int r=60-len-l; if(len==1||llen){ f[l][r]=1; continue; } for(int k=l+1;k60-r;k++){ int v=max(f[k][r],f[l][60-k])+1; if(vf[l][r]) f[l][r]=v,g[l][r]=k; } } return 1e18; } int solve(){ int l=0,r=0; int ans=0; while(1){ int len=60-l-r; if(len==1){ auto [op,y]=query(ans+(1lll)); if(op=='%') return y==0?ans+(1lll):ans; return y==1?ans+(1lll):ans; } if(lenl){ int val=(1lll)-1; auto [op,y]=query(val); if(op=='%') return ans+=(y-ans%val+val)%vall; else return y*val+((ans&val)-y*val%(1lll)+(1lll))%(1lll); } int k=g[l][r]; auto [op,y]=query(1llk); if(op=='/'){ ans|=(yk); r=60-k; } else{ ans|=y; l=k; } } }