Preface
最唐氏的一集，这场现场打的时候中间出现了“消失的 150min”
很难相信在 93min 过了 D 之后下一次过题要等到 241min 过 E，虽然后面全力追赶最后也是出了 9 题，但罚时也是突破天际，险些拿下同题数罚时倒一
后面分析了下最大的原因就是我比赛的时候想不出 E 导致心态崩了没法正常想题，祁神 J 的实现相比于正解又有些繁琐了导致花费了大量机时调试以及写对拍
但好在有徐神中流砥柱，一眼秒了 E 后又单切了 I，把节奏拉了回来，只能说这就是我们的绝对核心啊
后面补题的时候发现 A 和赛时想的大差不差，但需要繁琐的讨论就没补了；F 算是个经典多合一，赛后补了一下发现也不难写
抛开开场的幽默网络问题，这场题目本身还是挺友好的，比去年的 CCPC 网络赛的罚坐大赛舒服了不少
A. 军训 I
正如官方题解所说，本题很容易发现答案的上界为 \(13\)
赛时和队友讨论了一些情况后发现有些 Case 的解构造不出来（比如 \(8,12\) 这些），由于不确定是真的无解还是单纯的没找到方法因此就没敢冲
后面想到其实完全可以爆搜一下的，\(5\times 5\) 的范围如果都找不出解那么其它情况大概率也是无解的，只可惜机时不够了
看了题解后代码实现不难，不过 \(k=5\) 的情况赛时还是考虑欠缺了，看来这题的超高 dirt 率也是合情合理
B. 军训 II
签到，不难发现最优方案一定是有序的，计算方案数时只要求出每个数的数量，然后阶乘相乘即可
注意特判只有一种数的情况，此时方案数不乘 \(2\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5,mod=998244353,INF=1e9;
int n,a[N],c[N],fact[N];
inline void init(CI n)
{
fact[0]=1; for (RI i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
}
int main()
{
scanf("%d",&n); init(n);
for (RI i=1;i<=n;++i) scanf("%d",&a[i]),++c[a[i]];
sort(a+1,a+n+1); long long ans=0;
for (RI i=1;i<=n;++i)
{
int mn=INF,mx=-INF;
for (RI j=i;j<=n;++j)
{
mn=min(mn,a[j]); mx=max(mx,a[j]);
ans+=mx-mn;
}
}
int cnt=1,tp=0;
for (RI i=1;i<=1000000;++i)
if (c[i]!=0) cnt=1LL*cnt*fact[c[i]]%mod,++tp;
if (tp!=1) cnt=2LL*cnt%mod;
return printf("%lld %d",ans,cnt),0;
}
C. 种树
感觉想到了就很简单的一个题，赛时可能榜有点歪
考虑选大小为 \(3\) 的连通块，且里面必须要有关键点，换句话说一次操作最多将 \(2\) 个非关键点变为关键点
不难发现我们只要安排一种非关键点间的配对关系，总存在一个合法的构造方案能将其全部变为关键点，因此不需要考虑顺序问题
限制是匹配的点对间距离不能超过 \(2\)，因此其实只有三种情况：兄弟间配对、父子间配对、祖父和孙子节点配对
考虑如下贪心策略，任选一个关键点为根，从叶子往上贪心；优先两两合并某个点的所有非关键点儿子，若有多余的儿子节点则尝试和该点合并，仍有多余则尝试和该点的父节点合并
实现非常简单，复杂度 \(O(n)\)
#include <bits/stdc++.h>
constexpr int $n = 100005;
int n, m, ans, a, qu[$n], fa[$n];
std::vector<int> out[$n], ch[$n];
bool hkr[$n];
void work() {
std::cin >> n >> m;
for(int i = 1; i <= n; ++i) out[i].clear(), ch[i].clear(), hkr[i] = false;
for(int i = 1; i <= m; ++i) std::cin >> a, hkr[a] = true;
ans = 0;
for(int i = 1, u, v; i < n; ++i) {
std::cin >> u >> v;
out[u].push_back(v);
out[v].push_back(u);
}
int l = 1, r = 1; qu[l] = a; fa[a] = 0;
while(l <= r) {
int hd = qu[l++];
for(auto out: out[hd]) if(out != fa[hd]) {
fa[out] = hd; ch[hd].push_back(out);
qu[++r] = out;
}
}
for(int _i = n; _i > 0; --_i) {
int i = qu[_i];
while(ch[i].size()) {
int a = -1, b = -1;
while(ch[i].size() && hkr[ch[i].back()]) ch[i].pop_back();
if(ch[i].size()) a = ch[i].back(), ch[i].pop_back();
while(ch[i].size() && hkr[ch[i].back()]) ch[i].pop_back();
if(ch[i].size()) b = ch[i].back(), ch[i].pop_back();
// std::cout << a << " " << b << char(10);
if(a < 0) break;
if(b < 0 && !hkr[i]) b = i;
if(b < 0 && !hkr[fa[i]]) b = fa[i];
hkr[a] = true;
if(b >= 0) hkr[b] = true;
ans += 1;
}
}
// for(int i = 1; i <= n; ++i) std::cout << std::boolalpha << hkr[i] << char(i == n ? 10 : 32);
std::cout << ans << char(10);
}
int main() {
std::ios::sync_with_stdio(false);
int T; std::cin >> T; while(T--) work();
return 0;
}
D. 编码器-解码器
小清新 DP 题
不难想到设状态 \(f_{k,l,r}\) 表示 \(T[l,r]\) 在 \(S'_k\) 中出现的次数
转移类似于区间 DP，枚举某个 \(T[i]=S[k]\)，分成两边两个子状态即可；注意不匹配的情况也要统计
总复杂度 \(O(|S|\times |T|^3)\)
#include <bits/stdc++.h>
constexpr int mod = 998244353;
int n, m, f[105][105][105];
std::string s, t;
inline void add(int &a, const int &b) {
if((a += b) >= mod) a -= mod;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin >> s >> t;
n = s.size(); m = t.size();
for(int l = 0; l < m; ++l) f[0][l][l] = (s[0] == t[l]);
for(int i = 1; i < n; ++i) for(int l = 0; l < m; ++l) for(int r = l; r < m; ++r) {
if(l == r) f[i][l][r] = (s[i] == t[l]);
else for(int y = l; y <= r; ++y) if(s[i] == t[y]) {
if(y == l) add(f[i][l][r], f[i - 1][y + 1][r]); else
if(y == r) add(f[i][l][r], f[i - 1][l][y - 1]); else
add(f[i][l][r], int64_t(f[i - 1][l][y - 1]) * f[i - 1][y + 1][r] % mod);
}
add(f[i][l][r], f[i - 1][l][r]); add(f[i][l][r], f[i - 1][l][r]);
for(int y = l; y < r; ++y) add(f[i][l][r], int64_t(f[i - 1][l][y]) * f[i - 1][y + 1][r] % mod);
// std::cout << "f[" << i << "][" << l << "][" << r << "] = " << f[i][l][r] << char(10);
}
std::cout << f[n - 1][0][m - 1] << char(10);
return 0;
}
E. 随机过程
想到了就究极弱智的一个题，但有人被腐乳了我不说是谁
首先最大值很好统计，每层的节点数最多为 \(26^i\)，因此最优情况下答案为 \(\sum_{i=0}^m \min(n,26^i)\)
考虑计算期望，还是分层考虑，对于第 \(i\) 层共 \(26^i\) 个点，显然它们出现的概率都是相同的
计算一个点出现的概率，正难则反，逆过来考虑会发现这个概率就是 \(1-(1-\frac{1}{26^i})^n\)
因此最后的总期望就是 \(\sum_{i=0}^m [1-(1-\frac{1}{26^i})^n]\times 26^i\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,mod=998244353;
int n,m,f[N][26],fact[N],ifac[N];
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
fact[0]=1; for (RI i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
ifac[n]=quick_pow(fact[n]); for (RI i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
inline int C(CI n,CI m)
{
if (n<0||m<0||n<m) return 0;
return 1LL*fact[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
scanf("%d%d",&n,&m);
int mx=1,sum=0;
if (m>=1) inc(mx,min(26,n));
if (m>=2) inc(mx,min(26*26,n));
if (m>=3) inc(mx,min(26*26*26,n));
if (m>=4) inc(mx,1LL*n*(m-3)%mod);
for (RI i=0;i<=m;++i)
{
int c=quick_pow(26,i);
inc(sum,1LL*c*(1-quick_pow((1-quick_pow(c)+mod)%mod,n)+mod)%mod);
}
return printf("%d %d",mx,sum),0;
}
F. 包子鸡蛋 III
超级多合一，每一部分单拿出来感觉都不难，但合在一起就感觉特别麻烦
首先字符只有 e,g 比较有用，记其概率分别为 \(P_e,P_g\)，剩下的字符出现概率统一记为 \(P_o\)
如果我们钦定字符只能填 e,g，且强制开头一定为 e，结尾一定为 g，则好的字符串方案可以 DP 出来
正着大力 DP 需要记录长度、egg 的数量、eg 的数量、e 的数量，复杂度是 \(O(m^4)\) 的，无法通过
因此不妨考虑倒着填，令 \(f_{i,j,k}\) 表示填了长为 \(i\) 的串，此时 egg 的数量为 \(j\)，且 g 出现了 \(k\) 次的方案数
转移枚举下一个数填什么即可，这个 DP 乍一看是 \(O(m^3)\) 的，但由于 egg 的数量随 g 的数量平方增长，因此其实是 \(O(m^{2.5})\) 的，有了这个我们可以求出长为 \(i\) 的合法串出现的概率 \(g_i\)
接下来考虑往这个串中填入其它字符，设插之前的字符串长度为 \(x\)，插入的字符数量为 \(y\)，由经典插板法得到此时的贡献为：
\[F(x+y)=\sum C_{x+y-2}^{x-2}\times g_x\times P_o^y \]不难发现上面式子展开来就是个卷积的形式，大力 NTT 即可；最后为了不重不漏的统计还要加上一段前后缀的情况
设原来串长为 \(p\)，前缀（不包含 e）长为 \(q\)，后缀（不包含 g）长为 \(l\)，则最后的贡献为：
这个式子还是个卷积，继续大力 NTT 即可；最后得到了每种长度为 \(i\) 的好串的贡献 \(G(i)\)，则最后的答案就是 \(\sum G(i)\times (n-i+1)\)
总复杂度 \(O(m^{2.5}+n\log n)\)，需要注意一下常数
#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=1<<21,M=1600,mod=998244353;
int n,m,fact[N],ifac[N],Pe,Pg,Po,pwe[N],pwg[N],f[2][M][65],g[N],A[N],B[N],C[N];
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
inline int sum(CI x,CI y)
{
return x+y>=mod?x+y-mod:x+y;
}
inline int sub(CI x,CI y)
{
return x-y<0?x-y+mod:x-y;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
fact[0]=1; for (RI i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
ifac[n]=quick_pow(fact[n]); for (RI i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
namespace Poly
{
int rev[N],lim,p;
inline void init(int n)
{
for (lim=1,p=0;lim<=n;lim<<=1,++p);
for (RI i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<p-1);
}
inline void NTT(int *f,CI opt)
{
RI i; for (i=0;i<lim;++i) if (i<rev[i]) swap(f[i],f[rev[i]]);
for (i=1;i<lim;i<<=1)
{
int m=i<<1,D=quick_pow(3,opt==1?(mod-1)/m:mod-1-(mod-1)/m);
for (RI j=0;j<lim;j+=m)
{
int W=1; for (RI k=0;k<i;++k,W=1LL*W*D%mod)
{
int x=f[j+k],y=1LL*f[i+j+k]*W%mod;
f[j+k]=sum(x,y); f[i+j+k]=sub(x,y);
}
}
}
if (!~opt)
{
int Inv=quick_pow(lim); for (i=0;i<lim;++i) f[i]=1LL*f[i]*Inv%mod;
}
}
};
int main()
{
scanf("%d%d",&n,&m); init(n);
for (RI i=0;i<26;++i)
{
int p; scanf("%d",&p);
if (i==4) Pe=p; else
if (i==6) Pg=p; else inc(Po,p);
}
pwe[0]=pwg[0]=1;
for (RI i=1;i<=n;++i) pwe[i]=1LL*pwe[i-1]*Pe%mod;
for (RI i=1;i<=n;++i) pwg[i]=1LL*pwg[i-1]*Pg%mod;
f[1][0][1]=1;
for (RI i=1;i<=min(n,m+60);++i)
{
memset(f[(i&1)^1],0,sizeof(f[(i&1)^1]));
for (RI j=0;j<=m;++j) for (RI k=0;k<60;++k)
{
if (!f[i&1][j][k]) continue;
auto C2=[&](CI x)
{
return x*(x-1)/2;
};
if (j+C2(k)<=m) inc(f[(i&1)^1][j+C2(k)][k],f[i&1][j][k]);
if (j+C2(k)==m) inc(g[i+1],1LL*f[i&1][j][k]*pwe[i+1-k]%mod*pwg[k]%mod);
inc(f[(i&1)^1][j][k+1],f[i&1][j][k]);
}
}
for (RI i=min(n,m+60)+1;i<=n;++i) g[i]=1LL*g[i-1]*Pe%mod;
//for (RI i=1;i<=n;++i) printf("g[%d] = %d\n",i,g[i]);
for (RI i=3;i<=n;++i) A[i]=1LL*g[i]*ifac[i-2]%mod;
B[0]=1; for (RI i=1;i<=n;++i) B[i]=1LL*B[i-1]*Po%mod;
for (RI i=1;i<=n;++i) B[i]=1LL*B[i]*ifac[i]%mod;
Poly::init(n*2); Poly::NTT(A,1); Poly::NTT(B,1);
for (RI i=0;i<Poly::lim;++i) A[i]=1LL*A[i]*B[i]%mod;
Poly::NTT(A,-1); memset(B,0,sizeof(B));
for (RI i=2;i<=n;++i) A[i]=1LL*A[i]*fact[i-2]%mod;
for (RI i=n+1;i<Poly::lim;++i) A[i]=0;
B[0]=C[0]=1;
for (RI i=1;i<=n;++i) B[i]=1LL*B[i-1]*(1-Pe+mod)%mod;
for (RI i=1;i<=n;++i) C[i]=1LL*C[i-1]*(1-Pg+mod)%mod;
Poly::init(n*3); Poly::NTT(A,1); Poly::NTT(B,1); Poly::NTT(C,1);
for (RI i=0;i<Poly::lim;++i) A[i]=1LL*A[i]*B[i]%mod*C[i]%mod;
Poly::NTT(A,-1); int ans=0;
for (RI i=1;i<=n;++i) inc(ans,1LL*A[i]*(n-i+1)%mod);
return printf("%d",ans),0;
}
G. 疯狂星期六
很经典的一个题，如果没有第一个人花钱超过其它人的限制就是个很典的网络流模型
现在加上这一要求后其实也很简单，首先要尽可能多的让第一个人花钱，因此可以先以该点为源点跑一个最大流，求出第一个人的最大开销 \(lim\)
不难发现对于其它的人 \(i\in[2,n]\)，其开销的上界为 \(\min(a_i,lim-1)\)，以此将边的容量定下后在参量网络上跑最大流，最后看每个物品对应的边是否流满即可
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005,INF=1e9;
int n,m,a[N],v[N],x,y,w;
namespace Network_Flow
{
const int NN=2005,MM=5e6;
struct edge
{
int to,nxt,v;
}e[MM<<1]; int cnt=1,head[NN],cur[NN],dep[NN],s,t;
inline void addedge(CI x,CI y,CI z)
{
//printf("%d -> %d (%d)\n",x,y,z);
e[++cnt]=(edge){y,head[x],z}; head[x]=cnt;
e[++cnt]=(edge){x,head[y],0}; head[y]=cnt;
}
#define to e[i].to
inline bool BFS(void)
{
memset(dep,0,(s+1)*sizeof(int));
dep[s]=1; queue <int> q; q.push(s);
while (!q.empty())
{
int now=q.front(); q.pop();
for (RI i=head[now];i;i=e[i].nxt)
if (e[i].v&&!dep[to]) dep[to]=dep[now]+1,q.push(to);
}
return dep[t];
}
inline int DFS(CI now,CI tar,int dis)
{
if (now==tar) return dis; int ret=0;
for (RI& i=cur[now];i&&dis;i=e[i].nxt)
if (e[i].v&&dep[to]==dep[now]+1)
{
int dist=DFS(to,tar,min(dis,e[i].v));
if (!dist) dep[to]=INF;
dis-=dist; ret+=dist;
e[i].v-=dist; e[i^1].v+=dist;
if (!dis) return ret;
}
if (!ret) dep[now]=INF; return ret;
}
#undef to
inline int Dinic(int ret=0)
{
while (BFS()) memcpy(cur,head,(s+1)*sizeof(int)),ret+=DFS(s,t,INF); return ret;
}
};
using namespace Network_Flow;
int main()
{
scanf("%d%d",&n,&m); t=n+m+1;
for (RI i=1;i<=n;++i) scanf("%d%d",&a[i],&v[i]);
for (RI i=1;i<=m;++i)
{
scanf("%d%d%d",&x,&y,&w);
if (x==y) v[x]+=w; else
{
addedge(n+i,t,w);
addedge(x,n+i,INF);
addedge(y,n+i,INF);
}
}
for (RI i=1;i<=n;++i) if (v[i]>a[i]) return puts("NO"),0;
s=n+m+2; addedge(s,1,a[1]-v[1]);
Dinic(); int lim;
for (RI i=head[s];i;i=e[i].nxt) lim=v[1]+e[i^1].v;
s=n+m+3;
for (RI i=2;i<=n;++i)
{
int bd=min(a[i],lim-1);
if (v[i]>bd) return puts("NO"),0;
addedge(s,i,bd-v[i]);
}
Dinic();
for (RI i=n+1;i<=n+m;++i)
{
for (RI j=head[i];j;j=e[j].nxt)
if (e[j].to==t)
{
if (e[j].v!=0) return puts("NO"),0;
}
}
return puts("YES"),0;
}
H. 另一个游戏
防 AK 数据结构题，鉴定为弃疗
I. 找行李
被徐神 solo 了，ORZ
这类问题一眼考虑容斥，令 \(g_x\) 表示答案至少为 \(x\) 的方案数，最后相邻的项作差即可得到答案恰好为 \(x\) 的方案数
计算 \(g_x\) 也很简单，首先将人和行李排序，那么一个人 \(i\) 能选的行李一定是一段前缀；且第 \(i+1\) 个人能选的行李一定包含了第 \(i\) 个人的，因此很好计算方案数
单次 DP 的复杂度为 \(O(n^2)\)，总复杂度 \(O(n^3)\)
#include <bits/stdc++.h>
using llsi = long long signed int;
constexpr int mod = 998244353;
int ksm(int a, int b) {
int c = 1;
while(b) {
if(b & 1) c = llsi(c) * a % mod;
a = llsi(a) * a % mod;
b >>= 1;
}
return c;
}
int fac[502], facinv[502];
void init(int n) {
fac[0] = 1;
for(int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * llsi(i) % mod;
facinv[n] = ksm(fac[n], mod - 2);
for(int i = n; i >= 1; --i) facinv[i - 1] = facinv[i] * llsi(i) % mod;
return;
}
int C(int a, int b) {
return llsi(fac[a]) * facinv[b] % mod * facinv[a - b] % mod;
}
int w[502];
int dp[502][502];
inline void add(int &a, const int &b) {
if((a += b) >= mod) a -= mod;
}
int get_dp(int n) {
// for(int i = 1; i <= n; ++i) std::cerr << w[i] << char(i == n ? 10 : 32);
dp[0][0] = 1; w[0] = 0;
for(int i = 0; i < n; ++i) {
memset(dp[i + 1], 0, sizeof(dp[i + 1]));
for(int j = 0; j <= w[i]; ++j) {
add(dp[i + 1][j], dp[i][j]);
if(j + 1 <= w[i + 1])
add(dp[i + 1][j + 1], llsi(dp[i][j]) * llsi(w[i + 1] - j) % mod);
}
}
int ans = mod - 1;
for(int i = 0; i <= w[n]; ++i) add(ans, dp[n][i]);
return ans;
}
int n, m, a[502], b[502], hkr[502];
int main() {
std::ios::sync_with_stdio(false);
int n, m; std::cin >> n >> m;
for(int i = 1; i <= n; ++i) std::cin >> a[i];
for(int j = 1; j <= m; ++j) std::cin >> b[j];
std::sort(a + 1, a + n + 1);
std::sort(b + 1, b + m + 1);
for(int x = 1; x <= 500; ++x) {
for(int i = 1; i <= m; ++i) {
w[i] = 0;
while(w[i] < n && b[i] - x >= a[w[i] + 1]) w[i]++;
}
hkr[x] = get_dp(m);
// if(x <= 5) std::cout << hkr[x] << char(10);
}
int ans = 0;
for(int x = 1; x <= 500; ++x) add(ans, llsi(mod + hkr[x] - hkr[x + 1]) * x % mod);
std::cout << ans << char(10);
return 0;
}
J. 找最小
唉沟槽的线性基还在追杀我，但无所谓我有队友
考虑先求出两个序列的异或和 \(A,B\)，同时令 \(c_i=a_i\oplus b_i\)，则修改位置 \(i\) 相当于让 \(A,B\) 同时异或上 \(c_i\)
考虑将所有 \(c_i\) 加入线性基中，然后进行一个按位贪心即可；题解的实现较为简单，以下代码是祁神赛时实现的，由于写了对拍可读性较差
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int R = 35;
struct Linebase{
int p[R];
void init() {
for (int i=R-1; i>=0; --i) p[i]=0;
}
inline void insert(int x) {
for (int i=R-1; i>=0; --i) if ((x>>i)&1){
if (!p[i]) return (void)(p[i]=x); x^=p[i];
}
}
bool check(int x, int pos){
for (int i=R-1; i>=pos; --i) if ((x>>i)&1){
if (0==p[i] && ((x>>i)&1)) return false;
x^=p[i];
}
return true;
}
}base;
const int INF = (int)1e18+5;
const int N = 1e6+5;
int n, A[N], B[N], C[N], xorA, xorB;
int bf(){
int ans=INF;
for (int i=0; i<(1LL<<n); ++i){
int resA=0, resB=0;
for (int j=0; j<n; ++j){
if ((i>>j)&1) resA^=A[j+1], resB^=B[j+1];
else resA^=B[j+1], resB^=A[j+1];
}
ans = min(ans, max(resA, resB));
}
return ans;
}
void makedata(int n_){
n = n_;
const int AA = 4;
for (int i=1; i<=n; ++i) A[i] = rand()%AA, B[i] = rand()%AA;
}
void readd(){
cin >> n;
for (int i=1; i<=n; ++i) cin >> A[i];
for (int i=1; i<=n; ++i) cin >> B[i];
}
bool solve(){
readd();
// makedata(4);
int bfans = bf();
base.init();
xorA = xorB = 0;
for (int i=1; i<=n; ++i) xorA^=A[i], xorB^=B[i];
for (int i=1; i<=n; ++i) C[i] = (A[i]^B[i]), base.insert(C[i]);
// printf("xorA=%lld xorB=%lld\n", xorA, xorB);
// printf("base:\n");
// for (int i=0; i<4; ++i) {
// printf("i=%lld : %lld\n", i, base.p[i]);
// }
int cur=0, pos=-1;
int xxx = xorA^xorB;
for (int i=R-1; i>=0; --i){
if ((xxx>>i)&1) {pos=i; break;}
bool ok0 = base.check(cur, i);
bool ok1 = base.check(cur|(1LL<<i), i);
if (ok0 && ok1){
if ((xorA>>i)&1) cur |= (1LL<<i);
}else if (ok1) cur |= (1LL<<i);
}
// printf("cur=%lld pos=%lld\n", cur, pos);
int resA = xorA^cur, resB = xorB^cur;
int ans = INF;
// printf("cur=%lld resA=%lld resB=%lld\n", cur, resA, resB);
if (pos<0) ans = max(xorA^cur, xorB^cur);
else {
for (int h=0; h<2; ++h){
cur &= (1LL<<R) - (1LL<<pos);
cur ^= (1LL<<pos);
resA = xorA^cur, resB = xorB^cur;
// printf("cur=%lld resA=%lld resB=%lld\n", cur, resA, resB);
// printf("base.check(%lld, %lld)=%lld\n", cur, pos, base.check(cur, pos));
if (!base.check(cur, pos)) continue;
for (int i=pos-1; i>=0; --i){
bool ok0 = base.check(cur, i);
bool ok1 = base.check(cur|(1LL<<i), i);
// printf("i=%lld ok0=%d ok1=%d\n", i, ok0, ok1);
if (ok0 && ok1){
// printf("(%lld %lld)(%lld %lld)\n", resA, resB, resA^(1LL<<i), resB^(1LL<<i) );
if (max(resA, resB) > max(resA^(1LL<<i), resB^(1LL<<i))) cur |= (1LL<<i);
}else if (ok1) cur |= (1LL<<i);
resA = xorA^cur, resB = xorB^cur;
// printf("cur=%lld resA=%lld resB=%lld\n", cur, resA, resB);
}
// printf("resA=%lld %lld\n", resA, resB);
ans = min(ans, max(resA, resB));
}
}
cout << ans << '\n';
// if (ans!=bfans){
// // printf("n=%lld\n", n);
// for (int i=1; i<=n; ++i) printf("%lld ", A[i]);
// for (int i=1; i<=n; ++i) printf("%lld ", B[i]);
// // printf("ans=%lld bfans=%lld\n", ans, bfans);
// return false;
// }else printf("ans=%lld bfans=%lld\n", ans, bfans);
return true;
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) solve();
// while (solve()) {break;}
return 0;
}
K. 取沙子游戏
祁神开场一眼秒了，我题意都不知道
#include<bits/stdc++.h>
using namespace std;
int n, k;
int lb(int x){return x&(-x);}
void solve(){
cin >> n >> k;
if (lb(n) <= k) cout << "Alice\n";
else cout << "Bob\n";
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t; while (t--) solve();
return 0;
}
L. 网络预选赛
签到，枚举即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=505;
int n,m; char s[N][N];
int main()
{
scanf("%d%d",&n,&m); int ans=0;
for (RI i=1;i<=n;++i) scanf("%s",s[i]+1);
for (RI i=1;i+1<=n;++i) for (RI j=1;j+1<=m;++j)
if (s[i][j]=='c'&&s[i][j+1]=='c'&&s[i+1][j]=='p'&&s[i+1][j+1]=='c') ++ans;
return printf("%d",ans),0;
}
Postscript
这场打的实在是有点唐，被同届的一堆队伍吊着打，还差点被 Div2 的队暴打了，还好最后小赢一手罚时保住颜面
这周的 ICPC 网络赛还要打名额，只能说希望别再犯病了的说
标签：CI,return,Contest,int,CCPC,2024,const,include,mod From： https://www.cnblogs.com/cjjsb/p/18410962