第八届中国大学生程序设计竞赛总决赛（CCPC Final 2022）

Preface

真是坐坐又牢牢啊，2h40min 过了 A 后就开始发呆，剩下的题一个也做不来

但好在会的几个题全部一遍过，最后罚时尚可还能混进 Au 区

A. Graph Partitioning

考虑一条连接 \(x,y(x

因此构建一个二分图，左边是 \(2n-2\) 条边对应的点，右边是两棵树中 \(2n-2\) 个需要确定父亲节点的点，左边的每个点都会连接右边的两个点

不难发现有解的充要条件是这张图存在完美匹配，而稍做分析会发现由于这个二分图的点数等于边数，因此有完美匹配的充要条件为每个连通块都是基环树

而基环树的完美匹配方案一定为 \(2\)（环上某条边的匹配确定后，剩下的都唯一确定，一共有两个方向），因此最后方案数就是 \(2\) 的连通块幂次

#include

#include

#define RI register int

#define CI const int&

using namespace std;

const int N=2000005,mod=998244353;

int n,x,y,fa[N],num[N],sz[N];

inline int getfa(CI x)

{

return fa[x]!=x?fa[x]=getfa(fa[x]):x;

}

inline void Link(CI x,CI y)

{

fa[getfa(x)]=getfa(y);

}

int main()

{

scanf("%d",&n);

if (n==1) return puts("1"),0;

for (RI i=1;i<=4*n-4;++i) fa[i]=i;

for (RI i=1;i<=2*n-2;++i)

{

scanf("%d%d",&x,&y);

if (x==y) return puts("0"),0;

if (x>y) swap(x,y);

Link(i,2*n-2+y-1); Link(i,3*n-3+x);

}

for (RI i=1;i<=4*n-4;++i) ++sz[getfa(i)];

for (RI i=1;i<=2*n-2;++i) num[getfa(i)]+=2;

// for (RI i=1;i<=4*n-4;++i) printf("%d%c",sz[i]," \n"[i==4*n-4]);

// for (RI i=1;i<=4*n-4;++i) printf("%d%c",num[i]," \n"[i==4*n-4]);

int cnt=0;

for (RI i=1;i<=4*n-4;++i)

{

if (getfa(i)!=i) continue;

if (num[i]!=sz[i]) return puts("0"),0; else ++cnt;

}

int ans=1;

for (RI i=1;i<=cnt;++i) ans=2LL*ans%mod;

return printf("%d",ans),0;

}

C. DFS Order 3

这题之前在 2023 合肥区域赛的热身赛上做过，这次就直接秒了

#include

void work() {

int n; std::cin >> n;

std::vector> d(n, std::vector(n));

for(auto &d: d) for(auto &d: d) std::cin >> d, d--;

std::vector> ans;

std::vector vis(n, false);

vis[0] = true;

for(int i = 1; i < n; ++i) {

int cur = d[0][i];

for(int j = 0; j < n; ++j) if(vis[d[cur][j]]) {

ans.push_back({cur, d[cur][j]});

break;

}

vis[cur] = true;

}

for(auto [f, t]: ans) std::cout << f + 1 << " " << t + 1 << char(10);

return ;

}

int main() {

std::ios::sync_with_stdio(false);

int T; std::cin >> T; while(T--) work();

return 0;

}

E. CCPC String

枚举中心的 \(P\) 所在的位置，显然两边最长能延申的距离是可以二分的

#include

#include

#include

#define int long long

#define RI register int

#define CI const int&

using namespace std;

const int N=1e6+5;

int t,pfx[N]; char s[N];

signed main()

{

for (scanf("%lld",&t);t;--t)

{

scanf("%s",s+1); int n=strlen(s+1),ans=0;

for (RI i=1;i<=n;++i) pfx[i]=pfx[i-1]+(s[i]!='p'?1:0);

for (RI i=1;i<=n;++i)

{

if (s[i]=='c') continue;

int l=1,r=min((i-1)/2,n-i),ret=0;

auto check=[&](CI l,CI r)

{

return pfx[r]-pfx[l-1]==r-l+1;

};

while (l<=r)

{

int mid=l+r>>1;

if (check(i-mid*2,i-1)&&check(i+1,i+mid)) ret=mid,l=mid+1; else r=mid-1;

}

ans+=ret;

}

printf("%lld\n",ans);

}

return 0;

}

F. Chase Game 3

如果存在某个 \(i,i+1\)，使得它们在排列上的距离 \(\ge 3\)，此时后手一定不能获胜

因为此时 \(i,i+1\) 两个点在排列上的邻居一定不同，先手只要在 \(i,i+1\) 之间反复走到与后手当前位置不相邻的点即可

#include

using namespace std;

const int N = 4e5+5;

int pos[N];

bool solve() {

int n; cin >> n;

for (int i=1; i<=n; ++i) {

int a; cin >> a;

pos[a] = i;

}

for (int i=1; i

if (abs(pos[i]-pos[i+1]) > 2) return false;

}

return true;

}

signed main() {

ios::sync_with_stdio(0); cin.tie(0);

int T; cin >> T; while (T--) cout << (solve() ? "Yes\n" : "No\n");

return 0;

}

J. Best Carry Player 3

考虑找到 \(k\) 二进制下的最高位 \(t\)，显然异或操作只会改变后 \(t\) 位

因此最优的策略大致为：先用异或操作将最后 \(t\) 为变为全 \(1\)，再通过 \(+1\) 把前面的部分增加

但具体实现时需要注意各种 Corner Case，比如 \(k=2^t-1\) 时可以两步变换，否则至少要三步；还有一些边界情况的处理

#include

#include

#define int long long

#define RI register int

#define CI const int&

using namespace std;

int t,x,y,k;

signed main()

{

for (scanf("%lld",&t);t;--t)

{

scanf("%lld%lld%lld",&x,&y,&k);

if (x>y) swap(x,y);

if (x==y) { puts("0"); continue; }

if (k<=1) { printf("%lld\n",y-x); continue; }

int hb=1; while (hb<=k) hb<<=1;

int xf=x/hb,xb=x%hb,yf=y/hb,yb=y%hb,ans=0;

auto calc=[&](CI x,CI y)

{

if (x==y) return 0;

return ((x^y)<=k||y-x<=1)?1:2;

};

if (xf==yf)

{

printf("%lld\n",calc(xb,yb));

continue;

}

if (xb==(hb-1)) ans+=1; else

if (((hb-1)^xb)<=k) ans+=2; else ans+=3;

++xf; xb=0;

if (xf!=yf) ans+=(yf-xf)*(k==hb-1?2:3),xf=yf;

ans+=calc(xb,yb);

printf("%lld\n",ans);

}

return 0;

}

L. Completely Multiplicative Function

徐神在我的疯狂质疑下还是秒了这题，令人感慨

首先假设所有位置初始时都是 \(1\)，现在考虑要将若干位置变成 \(-1\)

不难发现 \([\frac{n}{2},n]\) 内的所有素数的值都可以任意改变，这就给了我们一个调整的余量

而对于 \([1,\frac{n}{2}]\) 内的素数显然先修改小的能改变的位置数更多，我们直接爆搜，在有余量调整的情况下跑的飞快

#include

using llsi = long long signed int;

constexpr bool check = false;

bool is_not_prime[1000005];

std::vector prime;

void init(int n) {

is_not_prime[0] = is_not_prime[1] = 1;

for(int i = 2; i <= n; ++i) if(!is_not_prime[i]) {

prime.push_back(i);

for(llsi j = llsi(i) * i; j <= n; j += i) is_not_prime[j] = 1;

}

return ;

}

void work(int n, int k) {

if(n % 2 != k % 2) return std::cout << "-1\n", void(0);

k = (n - k) / 2;

std::vector _b(n + 1, 0);

const std::vector &b = _b;

int cur = 0;

auto upd = [&](int pos, bool newVal) {

cur -= _b[pos];

cur += _b[pos] = newVal;

};

int hkr = 0;

for(int i = (n + 2) / 2; i <= n; ++i) if(!is_not_prime[i]) hkr++;

if(hkr < k) for(auto pr: prime) {

if(pr >= (n + 2) / 2) return void(std::cerr << "FUCK\n"), void(std::cout << "-1\n");

for(llsi P = pr; P <= n; P *= pr)

for(llsi i = 1; i <= n / P; ++i)

upd(i * P, b[i * P] ^ 1);

if(cur > k) {

for(llsi P = pr; P <= n; P *= pr)

for(llsi i = 1; i <= n / P; ++i)

upd(i * P, b[i * P] ^ 1);

} else

if(cur + hkr >= k) {

break;

}

}

// std::cerr << "cur = " << cur << char(10);

for(int i = (n + 2) / 2; cur < k && i <= n; ++i)

if(!is_not_prime[i]) upd(i, b[i] ^ 1);

if constexpr (check) {

for(int i = 1; i <= n; ++i) for(int j = 1; i * j <= n; ++j) {

if((b[i] ^ b[j]) != b[i * j]) {

std::cerr << "n, k = " << n << ", " << k << " failed at " << i << " * " << j << char(10);

goto __break__;

}

}

__break__:;

}

for(int i = 1; i <= n; ++i) std::cout << (b[i] ? "-1" : "1") << char(i == n ? 10 : 32);

return ;

}

int main() {

std::ios::sync_with_stdio(false);

init(1000000);

// for(int i = 0; i <= 1000; ++i) for(int k = (i & 1); k <= i; k += 2) work(i, k);

// return 0;

int T; std::cin >> T; while(T--) {

int n, k;

std::cin >> n >> k;

work(n, k);

}

return 0;

}

Postscript

唉沟槽的 Final，感觉下个月要在场上狠狠罚坐了