Codeforces 每日一练 1067A+1267L+1217B

1067A Array Without Local Maximums

传送门
题意：给定一个数列，其中-1代表不确定，替换所有的-1，使得任意一项小于两侧的最大值，输出方案数。
一道1e5的三维dp，首先考虑dp的过程中需要表示哪些量——位置，当前位置的值，和前一个的关系。假设0/1/2分别代表大于/等于/小于，不难得出下列转移方程：$$dp[i][j][1]=dp[i-1][j][1]+dp[i-1][j][2]+dp[i-1][j][0]$$ $$dp[i][j][0]=\sum_{m=1}^{j-1}(dp[i-1][m][1]+dp[i-1][m][2]+dp[i-1][m][0])$$ $$dp[i][j][0]=\sum_{m=j+1}^{200}(dp[i-1][m][1]+dp[i-1][m][2])$$ 关于初始化，我们只需要假设第0位是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
45
46
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100005
#define il inline
#define mod 998244353
#define int long long
int a[maxn],dp[maxn][210][3];
signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    for (int i = 1; i <=n ; ++i) {
        cin>>a[i];
    }
    for (int i = 1; i <=200 ; ++i) {
        if(a[1]==-1||a[1]==i){
            dp[1][i][0]=1;
        }
    }
    for (int i = 2; i <=n ; ++i) {
        int sum=0;
        for (int j = 1; j <=200 ; ++j) {
            if(a[i]==-1||a[i]==j){
                dp[i][j][0]=sum;
                dp[i][j][1]=(dp[i-1][j][1]+dp[i-1][j][2]+dp[i-1][j][0])%mod;
            }
            sum=(sum+dp[i-1][j][1]+dp[i-1][j][2]+dp[i-1][j][0])%mod;
        }
        sum=0;
        for (int j = 200; j >=1 ; --j) {

            if(a[i]==-1||a[i]==j){
                dp[i][j][2]=sum;
            }sum=(sum+dp[i-1][j][1]+dp[i-1][j][2])%mod;
        }
    }
    ll sum=0;
    for (int i = 1; i <=200 ; ++i) {
        if(a[n]==-1||a[n]==i){
            sum=(sum+dp[n][i][1]+dp[n][i][2])%mod;
        }
    }
    cout<<sum;
    return 0;
}

1267L Lexicography

传送门
题意：一个长度n*l的字符串，将他分割成n个长度l字符串，使得按字典序从小到大排列时，第k个字符串的字典序尽可能小。
显然我们只需要考虑前k个就好，排序之后，第一次我们可以依次放进k个字符串，假设有m个和第k个相同，那么第二次放入字母时只需要考虑这m个就好，因为前k-m个肯定比第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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 1005
char ans[maxn][maxn];
int pos[maxn],cnt=1;int n, l, k;char s[maxn*maxn];
#define il inline
il void insert(int x,int a){
    memset(pos,0, sizeof(pos));
    for (int i = a; i <=k ; ++i) {
        if(!pos[s[cnt]]){
            pos[s[cnt]]=i;
        }
        ans[i][x]=s[cnt++];
    }
    if(x==l)return;
    insert(x+1,pos[ans[k][x]]);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> l >> k;
    cin >> (s + 1);
    s[0] = 1;
    sort(s + 1, s + 1 + n * l);
    insert(1,1);
    for (int i = 1; i <=n ; ++i) {
        for (int j = 1; j <=l ; ++j) {
            if(!ans[i][j])cout<<s[cnt++];
            else cout<<ans[i][j];
        }
        cout<<"\n";
    }
    return 0;
}

1217B Zmei Gorynich

传送门
题意：n个法术和一只x头龙，第i个可以使魔龙掉d[i]个头，长h[i]个头，询问最少多少次可以把龙打败。
贪心水题了，如果可以秒了巨龙就秒，如果秒不掉，输入时记录伤害的最大值和d,h差的最大值，如果差的最大值<=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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100005
#define il inline
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        ll n,x;
        cin>>n>>x;
        int fl=0;
        ll a=0,b=-10000000000;
        for (int i = 0; i <n ; ++i) {
            ll d,h;
            cin>>d>>h;
            a=max(a,d);
            b=max(b,d-h);
            if(b>=0&&d>=x)fl=1;
            if(d>=x)fl=1;
        }
        if(fl)cout<<1<<endl;
        else{
            if(b<=0)cout<<-1<<endl;
            else{
                x-=a;
                ll tmp;
                if(x%b==0){
                    tmp=1+x/b;
                }else{
                    tmp=2+x/b;
                }
                cout<<tmp<<endl;
            }
        }
    }
    return 0;
}