CCPC 2024 吉林

I. The Easiest Problem

输出小写字母个数

 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


#include <bits/stdc++.h>
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
const int N=2e5+7,M=1e6,mod=998244353;

void solve()
{
    printf("21");
    
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    // cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

L. Recharge

用一定数量的 2 和 1 来填 k 。

优先用 2，再用 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


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

int n,x,y;

void solve(){
    cin>>n>>x>>y;
    if(n==1){
        cout<<x+y<<endl;
        return;
    }
    if(n%2==0){
        cout<<(x+y*2)/n<<endl;
        return;
    }
    ll ans=0;
    int t=n/2;
    int mn=min(y/t,x);
    ans+=mn;
    if(y/t>x)ans+=(y-mn*t)*2/(n+1);
    else ans+=((y-mn*t)*2+x-mn)/n;
    cout<<ans<<endl;
}

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

G. Platform Game

平台从高到低排序，遍历是否接触即可

 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


#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=2e5+7, mod=1e9+7;

struct Node{
    int l,r,y;
}a[N];

int n;

bool cmp(Node a,Node b){
    return a.y>b.y;
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].l>>a[i].r>>a[i].y;
    }
    sort(a+1,a+1+n,cmp);
    int x,y;
    cin>>x>>y;
    for(int i=1;i<=n;i++){
        if(x>=a[i].r||x<=a[i].l||a[i].y>y)continue;
        y=a[i].y;
        x=a[i].r;
    }
    cout<<x<<endl;
}

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

E. Connected Components

首先易观察到偏序关系，按其中一项偏序排序后，这里取左侧的偏序，即 $a_i-i<a_j-j$，再通过单调栈判断联通情况即可

 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


#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=1e6+7, mod=1e9+7;

struct Node{
    int id,a,b;
}a[N];

bool cmp(Node a,Node b){
    if(a.a==b.a)return a.b<b.b;
    return a.a<b.a;
}

int n;

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].a>>a[i].b;
        a[i].id=i;
        a[i].a-=i;
        a[i].b=i-a[i].b;
    }
    sort(a+1,a+1+n,cmp);
    deque<int>q;
    for(int i=1;i<=n;i++){
        int t=-1e9-7,flag=0;
        if(q.size())t=q.front();
        while(!q.empty() && a[i].b>=q.front()){
            q.pop_front();
            flag=1;
        } 
        if(flag)q.push_front(t);
        else q.push_front(a[i].b);
    }
    cout<<q.size()<<endl;
}

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

D. Parallel Lines

观察到时限 3s，n 仅为 1e4，可以大胆 $n^2$ 方向思考。

题目明确，所有点都位于 k 条斜率确定的平行线上，可以固定一点遍历其他点找到所有可能的斜率，再固定斜率找到 $y=ax+b$ 中不同的 b 来确定平行线的数量。

 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


#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=1e4+7, mod=1e9+7;

int n,k;
pair<int,int>d[N];

void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>d[i].first>>d[i].second;
    }
    for(int i=2;i<=n;i++){
        int dx=d[i].first-d[1].first,dy=d[i].second-d[1].second;
        map<int,vector<int>>mp;
        for(int j=1;j<=n;j++){
            int b=d[j].second*dx-d[j].first*dy;
            mp[b].push_back(j);
            if(mp.size()>k)break;
        }
        if(mp.size()==k){
            bool flag=0;
            for(auto [x,y]:mp){
                if(y.size()==1){
                    flag=1;
                    break;
                }
            }
            if(!flag){
                for(auto [x,y]:mp){
                    cout<<y.size()<<" ";
                    for(auto a:y){
                        cout<<a<<" ";
                    }
                    cout<<endl;
                }
                return;
            }
        }
    }
}

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

B.DfsOrder0.5

显然进行树上 DP，设 $DP_{i,0}$ 为子树内偶数 dfs 序权值最大和，$DP_{i,1}$ 为子树内奇数 dfs 序权值最大和。

考虑转移过程，找到当前所有子树，按大小奇偶分开，然后如果全是偶大小的，按当前奇偶取所有子树对应值；

如果有奇大小的，偶大小的子树全取最大值，奇的一半取 0，一半取 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


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

int n,a[N],f[N][2],siz[N];
vector<int>e[N];

void dfs(int now, int fa){
    vector<int>even,odd;
    for(auto x:e[now]){
        if(x==fa)continue;
        dfs(x,now);
        siz[now]+=siz[x];
        if(siz[x]&1)odd.push_back(x);
        else even.push_back(x);
    }
    vector<pair<int,int>>tmp;

    for(auto x:odd){
        tmp.push_back({f[x][0]-f[x][1],x});
    }
    
    sort(tmp.begin(),tmp.end());
    for(int t=0;t<2;t++){
        if(odd.size()==0){
            f[now][t]=t*a[now];
            for(auto x:even){
                f[now][t]+=f[x][t^1];
            }
        }
        else{
            f[now][t]=t*a[now];
            
            for(auto x:even){
                f[now][t]+=max(f[x][0],f[x][1]);
            }
            
            int mid = (int)odd.size() / 2;
            if ((odd.size() & 1) && (t ^ 1)) ++mid;

            for(int i=0;i<mid;i++){
                f[now][t]+=f[tmp[i].second][1];
            }
            for(int i=mid;i<tmp.size();i++){
                f[now][t]+=f[tmp[i].second][0];
            }
        }
    }
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        siz[i]=1;
        e[i].clear(); 
        f[i][0] = f[i][1] = 0; 
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    cout<<f[1][0]<<endl;
}

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

C. Fibonacci Sum

题目要求

$$ \boxed{\displaystyle \sum_{i=1}^{n} F\!\bigl(\text{popcount}(i)\bigr)\;\bmod 10^{9}+7} $$

我们将二进制字符串用 固定前缀+随机后缀 来表示

若当前已确定的前缀含 cnt 个 1，后缀长 k 位，则所有后缀随意填得到的贡献为 $\sum_{j=0}^{k}{\binom{k}{j}},F(cnt+j)$

有公式如下：

$$ \boxed{\displaystyle \sum_{j=0}^{k}\binom{k}{j}F(t+j)=F(t+2k)} \quad(t\ge 0,k\ge 0) $$

从头到尾遍历字符串即可

 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


#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=2e7+7, mod=1e9+7;

string s;
int f[N];

void solve(){
    cin>>s;
    int n=s.size();
    int l=2*n;
    f[0]=0;
    f[1]=1;
    for(int i=2;i<=l;i++){
        f[i]=(f[i-1]+f[i-2])%mod;
    }
    ll ans=0;
    int cnt=0;
    for(int i=0;i<n;i++){
        if(s[i]=='1'){
            int k=n-i-1;
            ans+=f[cnt+2*k];
            if(ans>=mod)ans-=mod;
            ++cnt;
        }
    }
    ans+=f[cnt];
    if(ans>=mod)ans-=mod;
    cout<<ans<<endl;
}

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

F. Best Player

首先明确想法，如果 i 是优胜者，那么他在所有比赛中都取走所有的 z，其他人的比赛都是均分（比赛双方总分尽量持平）。

遍历每个人，只修改当前对象的比赛，再判断是否最大即可。

  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
104
105
106
107
108
109


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

int n, m;
int a[N], b[N], x[N], y[N], z[N], tx[N], ty[N], tz[N];
vector<int> e[N];
multiset<int> s[N];

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        s[i].clear();
        e[i].clear();
    }
    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i] >> x[i] >> y[i] >> z[i];
        tx[i] = x[i];
        ty[i] = y[i];
        tz[i] = z[i];
        e[a[i]].push_back(i);
        e[b[i]].push_back(i);
        if (x[i] <= y[i]) {
            int cha = min(y[i] - x[i], z[i]);
            x[i] += cha;
            z[i] -= cha;
            if (z[i]) x[i] += z[i] / 2 + (z[i] % 2), y[i] += z[i] / 2;
            s[a[i]].insert(x[i]);
            s[b[i]].insert(y[i]);
        } else {
            int cha = min(x[i] - y[i], z[i]);
            y[i] += cha;
            z[i] -= cha;
            if (z[i]) x[i] += z[i] / 2 + (z[i] % 2), y[i] += z[i] / 2;
            s[a[i]].insert(x[i]);
            s[b[i]].insert(y[i]);
        }
    }
    multiset<int> t;
    for (int i = 1; i <= n; i++) t.insert(*s[i].rbegin());
    vector<int> ans;
    for (int i = 1; i <= n; i++) {
        vector<int> tmp;
        for (auto id : e[i]) {
            tmp.push_back(a[id]);
            tmp.push_back(b[id]);
        }
        sort(tmp.begin(), tmp.end());
        tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
        for (auto id : tmp) {
            t.erase(t.find(*s[id].rbegin()));
        }
        for (auto id : e[i]) {
            s[a[id]].erase(s[a[id]].find(x[id]));
            s[b[id]].erase(s[b[id]].find(y[id]));
        }
        for (auto id : e[i]) {
            if (a[id] == i) {
                int nx = tx[id] + tz[id], ny = ty[id];
                s[a[id]].insert(nx), s[b[id]].insert(ny);
            } else {
                int nx = tx[id], ny = ty[id] + tz[id];
                s[a[id]].insert(nx), s[b[id]].insert(ny);
            }
        }
        for (auto id : tmp) t.insert(*s[id].rbegin());
        auto mx = t.end();
        mx--;
        auto smx = mx;
        smx--;
        if (*mx == *s[i].rbegin() && *mx != *smx) ans.push_back(i);
        for (auto id : tmp) t.erase(t.find(*s[id].rbegin()));
        for (auto id : e[i]) {
            if (a[id] == i) {
                int nx = tx[id] + tz[id], ny = ty[id];
                s[a[id]].erase(s[a[id]].find(nx));
                s[b[id]].erase(s[b[id]].find(ny));
            } else {
                int nx = tx[id], ny = ty[id] + tz[id];
                s[a[id]].erase(s[a[id]].find(nx));
                s[b[id]].erase(s[b[id]].find(ny));
            }
        }
        for (auto id : e[i]) {
            s[a[id]].insert(x[id]);
            s[b[id]].insert(y[id]);
        }
        for (auto id : tmp) t.insert(*s[id].rbegin());
    }
    cout << ans.size() << endl;
    for (auto id : ans) cout << id << " ";
    cout << endl;
}

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