Codeforces 每日一练 706C+575H+15C

706C Hard problem

传送门
镜像
题意：给定n个字符串，反转每个字符串有代价c[i]，求使得所有字符串按字典序排列所需的最小代价，如果不可能，输出-1；
看一眼数据范围和题意大概就猜出来是用二维了，0代表不反转，1代表反转，转移方程也很容易就可以写出来

1
2
dp[i][1]=min(dp[i-1][0]+c[i],dp[i-1][1]+c[i]);
dp[i][0]=min(dp[i-1][0],dp[i-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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100005
#define eps 1e-4
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#pragma GCC optimize(2)
#define lowbit(x) ((x)&-(x))
#define ull unsigned long long
#define db double
#define ld long double
#define mod 1000000007
string s[maxn],t[maxn];
ll c[maxn];
ll dp[maxn][2];
int vis[maxn][2];
signed main(){
    IOS
    int n;
    cin>>n;
    for (int i = 1; i <=n ; ++i) {
        cin>>c[i];
        dp[i][0]=dp[i][1]=9223372036854775800;
    }
    for (int i = 1; i <=n ; ++i) {
        cin>>s[i];
        reverse(s[i].begin(),s[i].end());
        t[i]=s[i];
        reverse(s[i].begin(),s[i].end());
    }
    dp[1][0]=0;
    dp[1][1]=c[1];
    vis[1][1]=1;
    vis[1][0]=1;
    for (int i = 2; i <=n ; ++i) {
        int fl=0;
        if(t[i]>=s[i-1]&&vis[i-1][0]==1){
            vis[i][1]=1;
            dp[i][1]=min(dp[i][1],dp[i-1][0]+c[i]);
            fl=1;
        }
        if(t[i]>=t[i-1]&&vis[i-1][1]==1){
            vis[i][1]=1;
            dp[i][1]=min(dp[i][1],dp[i-1][1]+c[i]);
            fl=1;
        }
        if(s[i]>=s[i-1]&&vis[i-1][0]==1){
            vis[i][0]=1;
            dp[i][0]=min(dp[i][0],dp[i-1][0]);
            fl=1;
        }
        if(s[i]>=t[i-1]&&vis[i-1][1]==1){
            vis[i][0]=1;
            dp[i][0]=min(dp[i][0],dp[i-1][1]);
            fl=1;
        }
        if(!fl){
            cout<<"-1";
            return 0;
        }
    }
    cout<<min(dp[n][1],dp[n][0]);
    return 0;
}

575H Bots

传送门
镜像
题意：两个机器人分别可以走0-n步，且分别会把走过的步数染成红色或蓝色，求所有的染色情况数。
想出答案并不难，明显答案应该是$$\sum_{i=0}^n\sum_{j=0}^nC_{i+j}^{i}$$，难点在化简求值，首先关于组合数有恒等式$$ C_{n+1}^{m+1}=C_{n}^{m+1}+C_{n}^{m}$$
根据这个恒等式可以将第一个求和化简为$C_{i+n+1}^{i+1}$，之后在化简第二个求和时，先加上$C_{n+2}^{1}$，就可以把答案化简为$C_{2n+2}^{n+1}+C_{n+1}^{1}$，之后减去$C_{n+2}^{1}$，则答案即为$C_{2n+2}^{n+1}-1$的值取模。
卢卡斯定理套个板子就OK

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
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long ll;
ll mulit(ll a,ll b,ll m){
    ll ans=0;
    while(b){
        if(b&1) ans=(ans+a)%m;
        a=(a<<1)%m;
        b>>=1;
    }
    return ans;
}
ll quick_mod(ll a,ll b,ll m){
    ll ans=1;
    while(b){
        if(b&1){
            ans=mulit(ans,a,m);
        }
        a=mulit(a,a,m);
        b>>=1;
    }
    return ans;
}
ll comp(ll a,ll b,ll m){
    if(a<b) return 0;
    if(a==b) return 1;
    if(b>a-b) b=a-b;
    ll ans=1,ca=1,cb=1;
    for(int i=0;i<b;i++){
        ca=ca*(a-i)%m;
        cb=cb*(b-i)%m;
    }
    ans=ca*quick_mod(cb,m-2,m)%m;
    return ans;
}
ll lucas(ll a,ll b,ll m){
    ll ans=1;
    while(a&&b){
        ans=(ans*comp(a%m,b%m,m))%m;
        a/=m;
        b/=m;
    }
    return ans;
}
int main()
{
    ll a,b,m,n;
    cin>>n;
    ll ans=lucas(2*n+2,n+1,mod)-1;
    ans%=mod;
    cout<<ans;
    return 0;
}

15C Industrial Nim

直接贴大佬的题解啦
写的比我好多了Orz
传送门