img

广州大学第十七届ACM大学生程序设计竞赛（同步赛）

写完这篇博客就学工分，不然挂科危了(别急，你没挂----来自遥远的未来对你的宽慰)

A

这里就是有一个小结论，贡献看取余部分

如果取余部分都相同就不用操作2

如果有不同的就需要找出最长的相同的一段，把其他用操作2都变成相同的

image-20240321100335339 
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
//有趣的第一题
//这种区间减为0的问题实际上只需要看取余的贡献就好了
//取余后都相等就不需要操作2了
//不然就算相等最长的一段
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using ll = long long;
using namespace std;
const int N=2e5+100;
ll s[N];
int n,k;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        
        rep(i,0,k-1)
        {
            s[i]=0;
        }
        cin>>n>>k;
        rep(i,1,n)
{
    int x;
    cin>>x;
    s[i%k]+=x;
}
sort(s,s+k);
ll cnt=1;
ll maxn=0;
rep(i,0,k-1)
{
if(s[i]==s[i+1])
{
    cnt++;
}
else
{    
    cnt=1;
}
maxn=max(maxn,cnt);
}
cout<<k-maxn<<'\n';
    }

}

C

建图为重点

就从要得到的物品为起点，不断往后加就可以了

image-20240321100355698 
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
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using ll = long long;
using namespace std;
const int N = 1e5 + 7;
vector<pair<ll, ll>> edge[N];
ll v[N];
ll d[N];
const int mod=1e9+7;
int main()
{
    ll n, m, k;
    cin >> n >> m >> k;
    rep(i,1,n)
    {
        edge[i].clear();
        v[i] = 0;
        d[i] = 0;
    }
    rep(i,1,k)
    {
        ll a, b;
        cin >> a >> b;
        v[a] += b;
    }
    rep(i,1,m)
    {
        ll x, y, c;
        cin >> x >> y >> c;
        edge[y].push_back({x, c});
        d[x]++;
    }
    queue<ll> q;
    for (int i = 1; i <= n; i++)
    {
        if (d[i] == 0)
        {
            q.push(i);
        }
    }
    ll ans = 0;
    while (!q.empty())
    {
        //cout<<q.front()<<'\n';
        ll x = q.front();
        q.pop();
        ans += v[x];
       // cout<<ans<<'\n';
        ans %= mod;
        for (auto y : edge[x])
        {
            d[y.first]--;
            if (d[y.first] == 0)
            {
                q.push(y.first);
            }
            v[y.first] += v[x] * y.second;
            v[y.first] %= mod;
        }
    }
    cout << ans <<'\n';
}

E

这个按题意模拟就好

每天记得更新，把今天施加的魔法后移

image-20240321100411488 
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
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using ll = long long;
using namespace std;
const int N = 2e5 + 100;
int d[20];
int n,m,k,h[N];
void update()
{
    frep(i,k,1)
    {
        if((d[i]))
        {
            h[d[i]]++;
        }
        d[i]=d[i-1];
        //整体向后移动，表示过了一天
    }
}
void add(int x)
{
    d[1]=x;
    rep(i,2,k)
    {
        if(d[i]==x)
        {
            d[i]=0;
            //清除之前的魔法
        }
    }
}
void del(int x)
{
    rep(i,1,k)
    {
        if(d[i]==x)
        {
            d[i]=0;
        }
    }
}
void solve()
{
    cin>>n>>m>>k;
    rep(i,1,m)
    {
        int op,x;
        cin>>op>>x;
        if(op==1)
        {
            add(x);
        }
        else if(op==2)
        {
            del(x);
        }
        else
        {
            cout<<h[x]+i-1<<'\n';
        }
        update();
    }
}
int main()
{
    int t=1;
    while(t--)
    {
        solve();
    }
}

F

签到

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
    cout << R"(                     ,----,        ,--,                                                  ____
  ,----..          .'   .`|      ,--.'|                 ,---,         ,----..          ,'  , `.
 /   /   \      .'   .'   ;   ,--,  | :         ,--,   '  .' \       /   /   \      ,-+-,.' _ |
|   :     :   ,---, '    .',---.'|  : '       ,'_ /|  /  ;    '.    |   :     :  ,-+-. ;   , ||
.   |  ;. /   |   :     ./ |   | : _' |  .--. |  | : :  :       \   .   |  ;. / ,--.'|'   |  ;|
.   ; /--`    ;   | .'  /  :   : |.'  |,'_ /| :  . | :  |   /\   \  .   ; /--` |   |  ,', |  ':
;   | ;  __   `---' /  ;   |   ' '  ; :|  ' | |  . . |  :  ' ;.   : ;   | ;    |   | /  | |  ||
|   : |.' .'    /  ;  /    '   |  .'. ||  | ' |  | | |  |  ;/  \   \|   : |    '   | :  | :  |,
.   | '_.' :   ;  /  /--,  |   | :  | ':  | | :  ' ; '  :  | \  \ ,'.   | '___ ;   . |  ; |--'
'   ; : \  |  /  /  / .`|  '   : |  : ;|  ; ' |  | ' |  |  '  '--'  '   ; : .'||   : |  | ,
'   | '/  .'./__;       :  |   | '  ,/ :  | : ;  ; | |  :  :        '   | '/  :|   : '  |/
|   :    /  |   :     .'   ;   : ;--'  '  :  `--'   \|  | ,'        |   :    / ;   | |`-'
 \   \ .'   ;   |  .'      |   ,/      :  ,      .-./`--''           \   \ .'  |   ;/
  `---`     `---'          '---'        `--`----'                     `---`    '---')";
}

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

G

这个题就是从x里面选出n+1的数

比如n是5

x是6

显然只有一种选法，就是1 6

如果x是7，那就是有7种选法了，

1 6，还有3个数字不能有2 7同时出现

2 7 还有3个数字不能有1 6同时出现

经过计算就是7

image-20240321100444985 
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>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using ll = long long;
using namespace std;
const int N = 5005;
ll c[N+2][N+2];
//预处理组合数
int mod=1e9+7;
void init()
{
    rep(i,0,N)
{
    c[i][0]=1;
rep(j,1,i)
{
    c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
}
}
void solve()
{
ll n,x;
cin>>n>>x;
if(x<n+1)
{
    cout<<-1<<'\n';
}
else
{
    cout<<c[x][n+1]<<'\n';
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
init();
while (t--)
{
    solve();
    }
}

K

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
#include <bits/stdc++.h>
using namespace std;
#define N 1000005
#define INF 0x3f3f3f3f
int t[N<<2],lazy[N<<2],pl[N<<2],pr[N<<2];
void pushup(int k){
    t[k]=t[k<<1]+t[k<<1|1];pl[k]=pl[k<<1];pr[k]=pr[k<<1|1];
}
void build(int k,int l,int r){
    if(l==r)t[k]=0,pl[k]=l,pr[k]=r;
    else{
        int m=l+((r-l)>>1);
        build(k<<1,l,m);
        build(k<<1|1,m+1,r);
        pushup(k);
    }
}
void pushdown(int k){
    if(lazy[k]){
        lazy[k<<1]+=lazy[k];
        lazy[k<<1|1]+=lazy[k];
        t[k<<1]+=lazy[k]*(pr[k<<1]-pl[k<<1]+1);
        t[k<<1|1]+=lazy[k]*(pr[k<<1|1]-pl[k<<1|1]+1);
        lazy[k]=0;
    }
}
int query(int L,int R,int l,int r,int k){
    if(L<=l&&r<=R)return t[k];
    else{
        pushdown(k);
        int res=0;
        int m=l+((r-l)>>1);
        if(L<=m)res+=query(L,R,l,m,k<<1);
        if(R>=m+1)res+=query(L,R,m+1,r,k<<1|1);
        return res;
    }
}
void updateqj(int L,int R,int v,int l,int r,int k){
    if(L<=l&&r<=R){
        lazy[k]+=v;
        t[k]+=v*(pr[k]-pl[k]+1);
    }
    else{
        pushdown(k);
        int m=l+((r-l)>>1);
        if(L<=m)updateqj(L,R,v,l,m,k<<1);
        if(R>=m+1)updateqj(L,R,v,m+1,r,k<<1|1);
        pushup(k);
    }
}
void solve(void)
{
    int n,q;cin>>n>>q;
    int a1,a2,a3,a4;cin>>a1>>a2>>a3>>a4;
    string ch;cin>>ch;
    build(1,1,n);
    for(int i=1;i<=q;i++){
        int op,l,r;cin>>op>>l>>r;
        if(op==1){
            updateqj(l,r,1,1,n,1);
        }else{
            int x=query(r,r,1,n,1);
            if((x&1)){
                    if(ch[r-1]=='1'){
                        cout<<"HoloPsychon"<<"\n";
                    }
                else cout<<"Magical Splash Flare"<<"\n";
                }
            else{
                    if(ch[r-1]=='1'){
                        cout<<"Magical Splash Flare"<<"\n";
                    }else cout<<"HoloPsychon"<<"\n";
                }
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // int t;cin>>t;
    // while(t--)
    solve();
    return 0;
}

I

这里最小值显然就是从大到小排序

这样子肯定保证了正确性

最大值就0 m 1 m-1

自己证吧（拿纸写个样例你就知道了）

image-20240321100504562 
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>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using ll = long long;
using namespace std;
const int N = 1e5+100;
ll v[N];
void solve()
{
int n;
cin>>n;
rep(i,1,n)
{
int x;
cin>>x;
v[i]=1<<x;
}
sort(v+1,v+1+n);
ll ans=0;
ll res=0;
rep(i,1,n)
{
    if(i>(n+1)/2)
    {
        ans+=v[i]*2;
    }
    res+=v[i];
}
if(n&1)
{
    ans+=v[(n+1)/2];
}
cout<<res<<" "<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
}
img