CCPC2024jinan

前言

又是差罚时能偷银，唉，还是实力不够，这场感觉可写的不少，和之前 vp 南京那场差不多

A. The Fool

刚开始一眼以为找 QWQ 差点交了，还好考虑了一下，实际是一堆相同的串，里面会有一个串与其他串不同，输出那个串的位置

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    string s[n+1];
    map<string,vector<pair<int,int>>>mp;
    for(int i=1;i<=n;i++)cin>>s[i];
    for(int i=1;i<=n;i++){
        int cnt=1;
        for(int j=0;j<(int)s[i].size();j+=k){
            string tmp=s[i].substr(j,k);
            mp[tmp].push_back({i,cnt});
            cnt++;
        }
    }
    for(int i=1;i<=n;i++){
        int cnt=1;
        for(int j=0;j<(int)s[i].size();j+=k){
            string tmp=s[i].substr(j,k);
            if(mp[tmp].size()==1){
                cout<<i<<" "<<cnt<<endl;
                return 0;
            }
            cnt++;
        }
    }
}

J. Temperance

被题意哈住了，实际上先删值小的并不会影响到后面的，因为如果他和后面值更大的在同一行或列，他也是那个大值，而不是这个小的值

所以只需要统计小于 $i$ 的值有多少个即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+7;

int a[N],b[N],c[N];
int n;

void solve(){
    map<int,int>x,y,z;
    vector<int>s;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i];
        x[a[i]]++;
        y[b[i]]++;
        z[c[i]]++;
    }
    for(int i=1;i<=n;i++){
        int tmp=-1;
        tmp=max({x[a[i]]-1,y[b[i]]-1,z[c[i]]-1});
        s.push_back(tmp);
    }
    sort(s.begin(),s.end());
    s.push_back(N+50);
    int cnt=0;
    for(int i=0;i<n;i++){
        while(s[cnt]<i&&cnt<(int)s.size())cnt++;
        cout<<cnt<<" ";
    }
    cout<<"\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

B. The Magician

一共 $52$ 张牌，每种牌最多 $13$ 张，最多剩下 $3$ 张，即一共最多剩下 $12$ 张，要求的其实就是用这 $12$ 张能再拼出几个同花顺

队长大模拟两发过

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92


#include <bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int cnt[5],id[1000],flag[5],num=0;
bool vis[5];
bool sol()
{
    int sum=0,now[5],tmp=num,ff[5];
    for(int i=1;i<=4;++i) {
        if(!vis[i])  sum+=cnt[i];
        now[i]=cnt[i];
        ff[i]=flag[i];
    }
    for(int i=1;i<=4;++i) {
        if(!vis[i])  continue;
        if(ff[i]){
            int x=min(3,5-now[i]);
            now[i]+=x;
            sum-=x;
            ff[i]=0;
        }
        if(now[i]==5)  continue;
        int x=min(tmp,5-now[i]);
        now[i]+=x;
        tmp-=x;sum-=x;
        if(now[i]==5)  continue;
        else  return 0;
    }
    return 1;
}
bool dfs(int k)
{
    if(k==0) {
        return  sol();
    }
    for(int i=1;i<=4;++i) {
        if(vis[i])  continue;
        vis[i]=1;
        bool x=dfs(k-1);
        if(x)  return 1;
        vis[i]=0;
    }
    return 0;
}
void solve()
{
    num=0;
    for(int i=1;i<=4;++i)  cnt[i]=flag[i]=0,vis[i]=0;
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;++i) {
        string s;
        cin>>s;
        ++cnt[id[s[1]]];
    }
    for(int i=1;i<=4;++i) {
        ans+=cnt[i]/5;
        cnt[i]%=5;
    }
    for(int i=1;i<=4;++i)  cin>>flag[i];
    for(int i=1;i<=2;++i) {
        int x;
        cin>>x;
        num+=x;
    }
    int tot=0;
    for(int i=1;i<=4;++i) {
        tot+=cnt[i];
    }
    for(int i=tot/5;i>=1;--i) {
        bool x=dfs(i);
        if(x) {
            ans+=i;
            break;
        }
    }
    printf("%d\n",ans);
    
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    id['D']=1;id['C']=2;id['H']=3;id['S']=4;
    int T=1;
    cin>>T;
    
    while(T--) {
        solve();
    }
    return 0;
}

F. The Hermit

加的思路

开始我想的是统计每种数可能被删的次数，最后在所有的答案中减去这部分

但是想错了一点就是只考虑了删前几位，没有考虑倍增时，前面的几个都能删

队长想的是按长度分开，前面的部分是倍增关系需要删的，后面部分是留下的，加到答案上的

前面的片段的长度只可能为 $O(\log n)$，同时确定前面片段的最大值之后，后面的片段只需要按组合数计算得出数量即可

每次加前面片段的种类数量乘以后面片段的种类数量即可

口胡得到这个应该是 $O(n \log n \log n)$ 的来着，实际交上去只跑了 $200$ 多 $ms$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+7,mod=998244353;
ll jc[N],inv[N],f[N][20],n,m,g[N][20],id[N];
ll qpow(ll x,ll k)
{
    ll ans=1,tmp=x;
    while(k) {
        if(k&1)  ans=ans*tmp%mod;
        tmp=tmp*tmp%mod;
        k>>=1;
    }
    return ans;
}
ll C(int x,int y)
{
    if(x<y)  return 0;
    return jc[x]*inv[y]%mod*inv[x-y]%mod;
}
ll calc(int x,int y)
{
    if(x<y)  return 0;
    if(y==0)  return 0;
    if(g[id[x]][n-y]!=-1)  return g[id[x]][n-y];
    ll sum=0;
    for(int i=1;i<=x;++i) {
        sum=(sum+C(x/i-1,y-1))%mod;
    }
    sum=(C(x,y)-sum+mod)%mod;
    g[id[x]][n-y]=sum;
    return sum;
}
void solve()
{
    memset(g,-1,sizeof(g));
    int tot=0;
    cin>>m>>n;
    inv[0]=jc[0]=1;
    for(int i=1;i<=m;++i) {
        jc[i]=jc[i-1]*i%mod;
        inv[i]=inv[i-1]*qpow(i,mod-2)%mod;
        if(!id[m/i])  id[m/i]=++tot;
    }
    ll ans=calc(m,n)*n%mod;
    for(int i=1;i<=m;++i) {
        f[i][1]=1;
        for(int j=1;j<=19&&j<=n;++j) {
            if(!f[i][j])  break;
            for(int k=i*2;k<=m;k+=i)  f[k][j+1]=(f[k][j+1]+f[i][j])%mod;
            ll x=calc(m/i,n-j);
            ans=(ans+f[i][j]*x%mod*(n-j)%mod)%mod;
        }
    }
    printf("%lld",ans);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T=1;
    // cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

减的思路

题解和我开始想那种有点类似，是减每个数能被删的次数

把队长那个和我想的结合下差不多

按题解的思路：

先固定一个元素 $x$，如果他能被删掉：
- 比他小的，构成了一个以 $x$ 结尾的倍数链
- 比他大的，都是 $x$ 的倍数
小的部分枚举倍数链，求得长度为 c，当前值为 x 的链的数量
大的部分直接组合数求

最后减去的总数为 $\sum_{1\leq c\leq n,1\leq x\leq m}f_{c,x}\cdot \begin{pmatrix} \lfloor m/x\rfloor-1 \ n-c \end{pmatrix}.$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75


#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=998244353;

int m,n;
ll ans,inv[N],inc[N];
ll f[25][N];

// 快速幂
ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

// inc存的是阶乘，inv存的是阶乘的逆元
void init(){
    inc[0]=1;
    for(int i=1;i<N;i++){
        inc[i]=inc[i-1]*i%mod;
    }
    inv[N-1]=qpow(inc[N-1],mod-2);
    for(int i=N-2;i>0;i--){
        inv[i]=inv[i+1]*(i+1)%mod;
    }
}

// 计算组合数
ll C(int a,int b){
    if(b==0||a==b)return 1;
    if(a<b)return 0;
    return inc[a]*inv[a-b]%mod*inv[b]%mod;
}

void solve(){
    cin>>m>>n;
    ans=C(m,n)*n%mod;
    for(int i=0;i<=m;i++)f[1][i]=1;
    for(int i=2;i<=20;i++){
        for(int j=1;j<=m;j++){
            for(int k=2;k*j<=m;k++){
                f[i][k*j]=(f[i][k*j]+f[i-1][j])%mod;
            }
        }
    }
    for(int i=1;i<=20;i++){
        for(int j=1;j<=m;j++){
            if(n-i>=0){
                ll k=C((m/j)-1,n-i);
                if((m/j)-1>=0)ans=(ans-(f[i][j]*C((m/j)-1,n-i))%mod+mod)%mod;
                else ans=(mod+ans-f[i][j])%mod;
            }
        }
    }
    cout<<ans<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    init();
    // cin>>t;
    while(t--)solve();
    return 0;
}

I. The Hanged Man

赛时想的是，固定以 1 为根，然后往下 dfs，优先连最小的环，看最后剩下的是否能成环即可

但是交上去 WA 了，讨论发现，如果 1 的子节点有奇数个，最后会有一个子节点的边无法连全

队长说可以拆树，把一个有奇数子节点的拆出去，其他的从 1 往下连，这个拆出去的就先把能连的连了，最后会剩下一条边，用这个边结合到 1 的子树中即可

写完调了半天，发现是没赋初值的问题。。。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+7,mod=998244353;
vector<int> nx[N];
int deg[N],fa[N],son[N],a[N],dep[N],n,siz[N];
vector<pair<int,int>> ans;
bool vis[N];
void dfs(int x,int FA)
{
    vis[x]=1;siz[x]=1;
    fa[x]=FA;dep[x]=dep[FA]+1;
    for(auto y:nx[x]) {
        if(y!=FA)  dfs(y,x),++son[x],siz[x]+=siz[y];
    }
}
void sol(int rt)
{
    deque<int> q;
    dfs(rt,0);
    for(int i=1;i<=n;++i)
        if(vis[i]&&son[i]==0&&i!=rt)  q.push_back(i);
    int sum=0;
    while(!q.empty()&&sum!=siz[rt]-1) {
        int x=q.front();
        q.pop_front();
        int now=x;
        while(now!=rt&&son[now]<=1)  now=fa[now];
        if(!a[now])  a[now]=x;
        else {
            int cnt=dep[x]+dep[a[now]]-2*dep[now];
            ans.push_back(make_pair(x,a[now]));
            a[now]=0;
            sum+=cnt;
            son[now]-=2;
            deg[now]-=2;
            if(deg[now]==1&&now!=rt)  q.push_back(now);
        }
    }
}
void solve()
{
    ans.clear();
    int rt=0;
    cin>>n;
    for(int i=1;i<=n;++i)  nx[i].clear(),vis[i]=0,siz[i]=dep[i]=deg[i]=son[i]=fa[i]=a[i]=0;
    for(int i=1;i<n;++i) {
        int x,y;
        cin>>x>>y;
        nx[x].push_back(y);
        nx[y].push_back(x);
        ++deg[x];++deg[y];
    }
    if(n==2) {
        printf("-1\n");
        for(int i=1;i<=n;++i)  nx[i].clear(),vis[i]=siz[i]=dep[i]=deg[i]=son[i]=fa[i]=a[i]=0;
        return;
    }
    for(int i=1;i<=n;++i) {
        if(!rt&&deg[i]%2==0)  rt=i;
    }
    if(!rt) {
        int flag=0;
        for(int i=1;i<=n;++i) {
            for(auto x:nx[i]) {
                if((deg[x]-1)%2==1) {
                    flag=x;
                    break;
                }
            }
            if(flag)  rt=i;
        }
        if(!flag) {
            printf("-1\n");
            for(int i=1;i<=n;++i)  nx[i].clear(),vis[i]=siz[i]=dep[i]=deg[i]=son[i]=fa[i]=a[i]=0;
            return;
        }
        nx[rt].erase(find(nx[rt].begin(),nx[rt].end(),flag));
        nx[flag].erase(find(nx[flag].begin(),nx[flag].end(),rt));
        --deg[rt];--deg[flag];
        sol(rt);sol(flag);
        ans.push_back(make_pair(rt,a[flag]));
        printf("%d\n",ans.size());
        for(auto x:ans)  printf("%d %d\n",x.first,x.second);
    } else {
        sol(rt);
        printf("%d\n",ans.size());
        for(auto x:ans)  printf("%d %d\n",x.first,x.second);
        
    }
    for(int i=1;i<=n;++i)  nx[i].clear(),vis[i]=siz[i]=dep[i]=deg[i]=son[i]=fa[i]=a[i]=0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

赛后看题解，这实现方法差的也太多了，我们那干了 100 行，这少了接近一半

可以发现：

如果一个节点他的子节点有偶数个，那就可以互相连
如果一个节点他的子节点有奇数个，那就任选一个不连，用不连的这个替换父节点在上一层树中的位置即可

只要找一个度数为偶数的节点为根，这个方案总能实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71


#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=3e5+7, mod=1e9+7;

int n;
vector<int> dep[N];
vector<pair<int,int>>ans;
bool vis[N];

int dfs(int now){
    vis[now]=1;
    deque<int>tmp;
    for(auto x:dep[now]){
        if(!vis[x]){
            int flag=dfs(x);
            if(!flag)tmp.push_back(x);
            else tmp.push_back(flag);
        }
    }
    if(tmp.size()==0)return 0;
    while(tmp.size()>=2){
        int x=tmp.front();
        tmp.pop_front();
        int y=tmp.front();
        tmp.pop_front();
        ans.push_back({x,y});
    }
    if(tmp.size())return *tmp.begin();
    else return 0;
}

void solve(){
    cin>>n;
    ans.clear();
    for(int i=1;i<=n;i++)dep[i].clear(),vis[i]=0;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        dep[u].push_back(v);
        dep[v].push_back(u);
    }
    bool flag=0;
    int pos=1;
    for(int i=1;i<=n;i++){
        if((int)(dep[i].size())%2==0){
            flag=1,pos=i;
            break;
        }
    }
    if(!flag){
        cout<<"-1\n";
        return;
    }
    dfs(pos);
    cout<<ans.size()<<endl;
    for(auto [x,y]:ans)cout<<x<<" "<<y<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}