L1-4数学题？

分析

我们设进行$x$次操作，为了满足条件我们就可以列出不等式：
$$ A+xB \leq xDC $$
移项得到
$$ (CD-B)x \geq A $$
因为要求$x$的最小值，所以当$C*D \leq B$时无法得到答案。否则，答案就是$\lceil \frac{A}{CD-B} \rceil$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve(){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    if(b>=c*d){
        cout<<-1<<endl;
    }
    else{
        cout<<(a+d*c-b-1)/(d*c-b)<<endl;
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

L1-5别炸！

分析

模拟题，求每个主对角线的最小负数之和即可，这里有个小技巧，主对角线的坐标相减是个定值，所以我们在遍历的时候把每个点$i-j$的值记录下来（$1-n \leq i-j \leq n-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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve(){
    int n;
    cin>>n;
    vector<vector<int> >vt(n+1,vector<int>(n+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>vt[i][j];
        }
    }
    map<int,int>mp;
    for(int i=1-n;i<=n-1;i++){
        mp[i]=1e9;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            mp[i-j]=min(mp[i-j],vt[i][j]);
        }
    }
    int ans=0;
    for(auto [x,y]:mp){
        ans+=max(0,-y);
    }
    cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

L1-6Applied Energistics 2

分析

观察到任意一种操作只会影响奇数位或偶数位的值的大小，且奇数位或偶数位的总和不变，所以要让所有数相等就需要让奇数位和偶数位的平均数相等

代码

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<iostream>
#include<map>
#include<algorithm>
#include<vector>
#include<stack>
#include<set>
#include<math.h>
#include<string>
#include<deque>
#define ll long long
#define maxn 2000005
using namespace std;
int main() {
    int a;
    cin>>a;
    while(a--){
        ll b,js=0,jss=0,os=0,oss=0;
        cin>>b;
        for(int i=1;i<=b;i++){
            int y;
            cin>>y;
            if(i%2==0){
                os+=y;
                oss++;
            }
            else{
                js+=y;
                jss++;
            }
        }
        if(os%oss!=0 || js%jss!=0){
            cout<<"NO"<<endl;
        }
        else{
            if(js/jss==os/oss){
                cout<<"YES"<<endl;
            }
            else{
                cout<<"NO"<<endl;
            }
        }
    }
    return 0;
}

L1-7云岿山叶顺光，以此剑破妄

分析

可以发现能选择的并且会对整个数造成影响的数只有$2$和$3$(选$2$的话对答案的贡献为+2,选$3$的话对答案的贡献为6)，所以可以记录$2$和$3$出现的次数，我们设原数字各个数位之和为$S$，$2$和$3$出现的次数分别为$i$和$j$，我们要满足$(S+2i+6j) \equiv 0(mod 9)$，由于$2 \cdot 9 \equiv 0 (mod 9)$所以$2$最多出现9次不同的结果，同理$3 \cdot 6 \equiv 0(mod 9)$，$6$最多出现3次不同的结果，所以只要枚举$i \leq 9 和 j \leq 6$时的答案即可

代码

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve(){
    string s;
    cin>>s;
    int sum=0;
    int e=0,san=0;
    for(auto it:s){
        sum+=(it-'0');
        if(it=='2'){
            e++;
        }
        if(it=='3'){
            san++;
        }
    }

    for(int i=0;i<=min(e,9);i++){
        for(int j=0;j<=min(san,3);j++){
            if((sum+i*2+j*6)%9==0){
                cout<<"YES"<<endl;
                return;
            }
        }
    }
    cout<<"NO"<<endl;
    
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
}

L1-8别再来这么多猫娘了！

分析

**纯💩题**，数据范围很小，直接暴力即可，枚举每个违禁词，在原文中找到违禁词的位置并用换行符替换防止违禁词是<censored>陷入死循环，最后遍历一遍更改后的字符串，读到换行符时用<censored>替换即可。

代码

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
#include"bits/stdc++.h"
#define ll long long
#define maxn 200005
#define endl '\n'
using namespace std;
void solve() {
    int n;
    cin>>n;
    vector<string>s(n+1);
    for(int i=1;i<=n;i++){
        cin>>s[i];
    }
    int k;
    cin>>k;
    string fl="\n";
    getline(cin,fl);
    string t;
    getline(cin,t);
    int ans=0;
    for(int i=1;i<=n;i++){
        while(t.find(s[i])!=string::npos){
            int pos=t.find(s[i]);
            t=t.substr(0,pos)+"\n"+t.substr(pos+(int)s[i].length());
            ans++;
        }
    }
    if(ans>=k){
        cout<<ans<<endl;
        cout<<"He Xie Ni Quan Jia!"<<endl;
    }
    else{
        for(auto it:t){
            if(it=='\n'){
                cout<<"<censored>";
            }
            else{
                cout<<it;
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

PS:这是24年天梯赛真题

L2-1安睡吧，我的白鸽呀

分析

因为只要一关过不去就结束游戏，所以可以贪心的把每一关的属性$j$设为前$i$关的最大值，当某一关的总和比$x$大时即可退出。

代码

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve(){
    ll n,m,k;
    cin>>n>>m>>k;
    vector<vector<ll> >vt(n+1,vector<ll>(m+1)); 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>vt[i][j];
        }
    }
    int ans=0;
    ll res=k;
    vector<ll>dq(m+1,0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(res<0){
                break;
            }
            if(dq[j]<vt[i][j]){
                res-=vt[i][j]-dq[j];
                dq[j]=vt[i][j];
            }
        }
        if(res>=0){
            ans++;
        }
        else{
            break;
        }
    }
    cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

L2-2这是树？

分析

因为子节点的编号一定要大于父节点的编号，所以在一颗节点数为$n$的树，我们可以依次把编号$1,2,\dots,n$拿出来，换句话说节点数为$i$的树一定基于节点数为$i-1$的树。一开始节点为数为$1$的树只有一颗，编号为$2$的节点可以放两个地方，放上编号为$2$的节点之后能放的节点的位置增加了-1+2=1，也就是说每放一个节点，接下来的节点能放的位置就多一个，所以答案是$n!$，由于要对$p$取模，所以当$n \geq p$时，答案必定是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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve(){
    string s;
    cin>>s;
    int p;
    cin>>p;
    ll o=0;
    for(auto it:s){
        o=o*10+(it-'0');
        if(o>=p){
            cout<<0<<endl;
            return;
        }
    }
    ll ans=1;
    for(int i=1;i<=o;i++){
        ans=ans*i%p;
    }
    cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

PS：这题直接输出0也有11分pwq

L2-3故事之外，有谁还在

分析

正向寻找最大比较困难，我们可以反向建图，并从编号大的节点开始遍历，因为从大编号的节点遍历到的所有节点不可能再大了，所以当下一次遍历到之前遍历到过的节点时直接退出即可，时间复杂度O(n)

代码

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<int> >vt(n+1);
    vector<int>ans(n+1,-1);
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        vt[v].push_back(u);
    }
    for(int i=n;i>=1;i--){
        queue<int>qu;
        qu.push(i);
        if(ans[i]==-1){
            ans[i]=i;
        }
        while(!qu.empty()){
            int q=qu.front();
            qu.pop();
            for(auto it:vt[q]){
                if(ans[it]==-1){
                    ans[it]=i;
                    qu.push(it);
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<" \n"[i==n];
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

L2-4愿浪漫，永不离席

分析

先预处理前$n+m$个候选人应该在的岗位，并把因人满而分配到别的岗位的人记录下来，然后在求缺少第$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
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
110
111
112
113
114
115
116
117
118
119
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
#include<stack>
#include<set>
#include<math.h>
#include<string>
#include<deque>
#include<iomanip>
#include<string.h>
#include<queue>
#define ll long long
#define int ll
#define maxn 2000005
#define endl '\n'
using namespace std;
ll a[200005];
ll b[200005];
int flag[200005];
struct node{
    int z,id;
};
bool cmp(node a,node b){
    return a.z>b.z;
}
void solve() {
    int n,m;
    cin>>n>>m;
    vector<int>vta;
    vector<int>vtb;
    for(int i=1;i<=n+m+1;i++){
        cin>>a[i];
        flag[i]=0;
    }
    for(int i=1;i<=n+m+1;i++){
        cin>>b[i];
    }
    int u=0,v=0;
    int ans=0;
    
    for(int i=1;i<=n+m;i++){
        if(u<n && a[i]>b[i]){
            u++;
            ans+=a[i];
            flag[i]=1;
        }
        else if(v<m && a[i]<b[i]){
            v++;
            ans+=b[i];
            flag[i]=2;
        }
        else if(u>=n){
            v++;
            ans+=b[i];
            flag[i]=2;
            vta.push_back(i);
        }
        else{
            u++;
            ans+=a[i];
            flag[i]=1;
            vtb.push_back(i);
        }
        
    }
    for(int i=1;i<=n+m;i++){
        if(flag[i]==1 && a[i]>b[i]){
            if(vta.size()!=0){
                int xb=lower_bound(vta.begin(),vta.end(),i)-vta.begin();
                xb=vta[xb];
                int da=ans-b[xb]+a[xb];
                da+=b[n+m+1];
                da-=a[i];
                cout<<da<<" ";
            }
            else{
                int da=ans-a[i];
                da+=a[n+m+1];
                cout<<da<<" ";
            }
        }
        else if(flag[i]==2 && a[i]<b[i]){
            if(vtb.size()!=0){
                int xb=lower_bound(vtb.begin(),vtb.end(),i)-vtb.begin();
                xb=vtb[xb];
                int da=ans-a[xb]+b[xb];
                da+=a[n+m+1];
                da-=b[i];
                cout<<da<<" ";
            }
            else{
                int da=ans-b[i];
                da+=b[n+m+1];
                cout<<da<<" ";
            }
        }
        else if(flag[i]==1 && a[i]<b[i]){
            int da=ans-a[i];
            da+=a[n+m+1];
            cout<<da<<" ";
        }
        else if(flag[i]==2 && a[i]>b[i]){
            int da=ans-b[i];
            da+=b[n+m+1];
            cout<<da<<" ";
        }
    }
    cout<<ans<<endl;
}
signed main() {
   ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
   int a = 1;
   cin >> a;
   while (a--) {
       solve();
   }
   return 0;
}

L3-2史题来袭，ac力场全开

分析

首先我们考虑暴力的做法，设$dp_{i,j}$表示处理第$i$个数时令它为$j$能得到的最大结果，很容易得到转移方程$$dp_{i,j}=\max_{i-1 \leq k \leq j-1} (dp_{i-1,k})+v(i,j)$$。现在考虑优化，直接考虑$a_i$比较困难，因为$a_i$是递增的，所以我们令偏移量$b_i=a_i-i(0 \leq b_i \leq m-n)$，如果$a_i不是i的倍数$，那么$v(i,a_i)$的贡献是0，既然我们要求最大，那么直接枚举$i$的倍数即可，由于$b_i$是单调不减的，所以当我们令$a_i=j$时$b_{i-1}$就要满足$b_{i-1} \leq j-i$。现在我们设$dp_x$为当前偏移量不超过$x$时能获得的最大收益，对于第$i$个位置，我们枚举$i$的倍数$j$，可以得到转移方程$$dp_{j-i}=\max(dp_{j-i},\max_{0 \leq k \leq j-i} (dp_k+v(i,j)))$$。至于如何查询$\max_{0 \leq k \leq j-i} (dp_k+v(i,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
52
53
54
55
#include"bits/stdc++.h"
#define ll long long
#define maxn 200005
#define endl '\n'
using namespace std;
int dp[200005];    
int n,m;
int lowbit(int x){
    return (x&(-x));
}
void upd(int x,int v){
    x++;
    while(x<=m-n+1){
        dp[x]=max(dp[x],v);
        x+=lowbit(x);
    }
}
int ask(int x){
    int ans=0;
    x++;
    while(x>0){
        ans=max(ans,dp[x]);
        x-=lowbit(x);
    }
    return ans;
}
int v(int x,int b){
    int ans=0;
    while(b%x==0){
        ans++;
        b=b/x;
    }
    return ans;
}
void solve() {
    cin>>n>>m;
    for(int i=0;i<=m;i++){
        dp[i]=0;
    }
    for(int i=2;i<=n;i++){
        for(int j=(m-n+i)/i*i;j>=i;j-=i){
            upd(j-i,ask(j-i)+v(i,j));
        }
    }
    cout<<ask(m-n)<<endl;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}