你最愿意做的哪件事，才是你的天赋所在

0%

Codeforces692Div.2

发表于 Valine：

C

思路

给出一个n*n的矩阵和m个点，现在需要移动到主对角线上，问需要多少次的移动成功，并且不存在两个点在相同的行和相同的列。
根据my，然后如果链成环贡献就+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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
inline bool isprime(ll num)
{if(num==2||num==3)return true;
    if(num%6!=1&&num%6!=5)return false;
    for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
    return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int N = 1e5+10;
int x[N],y[N];
vector<int>g[N];
int ans = 0;
bool vis[N];
void dfs(int u,int fa){
    if(vis[u]){
        if(u==fa)ans++;
        return;
    }
    vis[u]=1;
    if(g[u].empty())return ;
    ans++;
    dfs(g[u][0],fa);
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        ans = 0;
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)vis[i]=1,g[i].clear();
        for(int i=1;i<=m;i++){
            scanf("%d%d",&x[i],&y[i]);
            vis[x[i]]=0;
            if(x[i]!=y[i])g[x[i]].push_back(y[i]);

        }
        for(int i=1;i<=n;i++){
            if(!vis[i])dfs(i,i);
        }
        printf("%d\n",ans);
    }
}

D

思路

先证明一个结论，即两个相邻的?填01或者10都不会影响区间外的答案，很显然的，只对问号区间内的贡献有影响。
然后还需要证明一个结论即x>y的情况下相邻的两个?填10会比01好。此证明再codeforces上有。

image-20201222172156651现在考虑有sum个问号，此时有n个0和y个1的情况下，假设为010110011,那么根据上面的证明，我们需要对此进行修改，将所有相邻的01都变成10
第一次 : 101010101
第二次 : 110101010
第三次 : ………
最终 : 111110000
发现最后是1在前面，如果x<y的时候则是0在前面，所以我们只需要枚举0的个数即可找到最优的序列

代码实现

因为是最小值，所以不需要判断x,y大小，都做一遍即可。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
inline bool isprime(ll num)
{if(num==2||num==3)return true;
    if(num%6!=1&&num%6!=5)return false;
    for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
    return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int main(){
    string s;
    cin>>s;
    ll x,y;
    cin>>x>>y;
    ll ans = LONG_LONG_MAX;
    int pre0,pre1,suf0,suf1;
    pre0=pre1=suf0=suf1=0;
    ll tmpans = 0;
    ll tmpans1 = 0;
    //from zero to one
    for(int i=0;i<s.size();i++){
        if(s[i]=='0'){
            tmpans += pre1*y;
            pre0++;
            suf0++;
        }
        else {
            tmpans+=pre0*x;
            pre1++;
            suf1++;
        }
    }
    ans = min(ans,tmpans);
    ll tmp = 0;
    pre0 = 0;
    pre1 = 0;
    int tsuf0 = suf0;
    int tsuf1 = suf1;
    for(int i=0;i<s.size();i++){
        if(s[i]=='0'){
            tmp+=pre1*y;
            pre0++;
            tsuf0--;
        }else if(s[i]=='1'){
            tmp+=pre0*x;
            pre1++;
            tsuf1--;
        }else{
            // 1 to 0
            tsuf1--;
            tmpans += pre1*y - pre0*x - y*tsuf0 + tsuf1*x;
            tmp += pre1*y;
            pre0++;
            suf0++;
            suf1--;
        }
        ans = min(ans,tmpans);
    }
    ans = min(ans,tmp);
    pre0=0;
    pre1=0;
    tmpans = 0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='0'){
            pre0++;
            suf0--;
        }else if(s[i]=='1'){
            pre1++;
            suf1--;
        }else{
            // 0 to 1
            suf0--;
            tmp+=pre0*x - pre1*y - x*suf1 + y*suf0;
            pre1++;
        }
        ans = min(ans,tmp);
    }
    printf("%lld\n",ans);
}

-------------你最愿意做的哪件事才是你的天赋所在-------------