Codeforces Round #754 (Div. 2) A-E

题目地址：链接

A. A.M. Deviation(贪心)

每次操作可以使得a+c-2*b +3或者-3 。那么答案只需要%3即可，如果%后结果为2，就让他再减去3等到|-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
//#pragma comment(linker, "/STACK:10240000000000,10240000000000")
#include<bits/stdc++.h>
#define pii pair<int,int>
#define pdd pair<double,double>
using namespace std;
typedef long long ll;

const int MAXN = 1e6+10;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9+7;

ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}

ll lcm(ll a,ll b)
{
    return a*(b/gcd(a,b));
}

//int a[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin>>T;
    while(T--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        int d = a+c-2*b;
        if(abs(d)%3==0) cout<<0<<endl;
        else cout<<1<<endl;
    }
    return 0;
}

/*
    ios::sync_with_stdio(false);
    cin.tie(0);
*/

B. Reverse Sort(双指针，贪心)

最多一次操作，两个指针i,j, i从左到右选择1，j从右到左选择0，使得两者选择的长度相同，并且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
56
57
58
59
60
61
//#pragma comment(linker, "/STACK:10240000000000,10240000000000")
#include<bits/stdc++.h>
#define pii pair<int,int>
#define pdd pair<double,double>
using namespace std;
typedef long long ll;

const int MAXN = 1e6+10;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9+7;



int a[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        string s;
        cin>>s;
        vector<int>ans,ans0;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='1') ans.push_back(i+1);
        }
        for(int i=0;i<n;i++) if(s[i]=='0') ans0.push_back(i+1);
        int sz = ans.size();
        if(sz==0) cout<<0<<endl;
        else if(sz==(ans[sz-1]-ans[0]+1)&&ans[sz-1]==n) cout<<0<<endl;
        else
        {
            cout<<1<<endl;
            int l = 0,r=ans0.size()-1;
            while(l<sz&&r>=0)
            {
                if(ans[l]>ans0[r]) break;
                l++;
                r--;
            }
            l--;
            r++;
            cout<<l+1+ans0.size()-1-r+1<<" ";
            for(int i=0;i<=l;i++) cout<<ans[i]<<" ";
            for(int i=r;i<=ans0.size()-1;i++) cout<<ans0[i]<<" ";
            cout<<endl;
        }
    }
    return 0;
}

/*
    ios::sync_with_stdio(false);
    cin.tie(0);
*/

C. Dominant Character（贪心，暴力）

有连续两个a,那么答案直接输出2即可。

如果没有的话考虑 长度小于7的暴力即可，因为accabba/abbacca是你能够造出最长的符合要求的序列了。

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
//#pragma comment(linker, "/STACK:10240000000000,10240000000000")
#include<bits/stdc++.h>
#define pii pair<int,int>
#define pdd pair<double,double>
using namespace std;
typedef long long ll;

const int MAXN = 1e6+10;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9+7;



int prea[MAXN],preb[MAXN],prec[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        string s;
        cin>>s;
        for(int i=0;i<n;i++)
        {
            prea[i+1] = prea[i];
            preb[i+1] = preb[i];
            prec[i+1] = prec[i];
            if(s[i]=='a') prea[i+1]++;
            else if(s[i]=='c') prec[i+1]++;
            else preb[i+1]++;
        }
        int minn = INF;
        bool ok = false;
        for(int len=2;len<10;len++)
        {
            for(int i=0;i+len-1<n;i++)
            {
                int cnta = prea[i+len-1+1] - prea[i];
                int cntb = preb[i+len-1+1] - preb[i];
                int cntc = prec[i+len-1+1] - prec[i];
                if(cnta>cntb&&cnta>cntc)
                {
                    ok = true;
                    minn = min(minn,len);
                    break;
                }
            }
        }
        if(ok) cout<<minn<<endl;
        else cout<<-1<<endl;


    }
    return 0;
}

/*
    ios::sync_with_stdio(false);
    cin.tie(0);
*/

D. Treelabeling（构造，二进制，博弈）

表面看起来是个树博弈，但是这个题的本质是希望你赋值出一棵树，使得在任何点都无法走向其他点。因此这个题变成了一个构造题。

如何构造上述的树呢？

img

首先我们发现1 , 23 , 4567 , 789….15 , 16….31 , ..每组都是可以相互联通的值，因此我们要让他们在树同一层，使得他们无法相连。

首先对树分层涂色，然后计算两种颜色的数量，如上图数量少的是蓝色，为3。 转换成2进制：11 也就是1 + 2，正好可以用 1 和 23这两组赋值。可是任何的数量都可以用几个组进行赋值吗？答案是肯定的，我们只需要对数量少的进行二进制表示，然后从1 , 23 , 4567 , 789….15 , 16….31 , ..这些组种选几组来赋值即可，剩下得随便放。

二进制拆分的好处就是选择完这组后就要把这组的数全拿走，可为什么非要选择这组就要把这组的数全拿走赋值呢？不可以只用一部分呢？

比如 对于组4567你只用了456，剩下了7，而我们这种做法种红色节点是可以随便放的，这会导致你可能在红色节点上放了7，而456可能是相邻的蓝色节点，这就无法保证每个点孤立了。

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
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN = 2e5+7;
const ll mod =  998244353;

int color[MAXN];
vector<int>g[MAXN];
void dfs(int u,int last=0)
{
    color[u] = color[last] ^ 1;
    for(auto v:g[u])
    {
        if(v!=last) dfs(v,u);
    }
}
int cnt[2];
int vis[MAXN];
int c0[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin>>T;
    while(T--)
    {
       cnt[0] = cnt[1] = 0;
       int n;
       cin>>n;
       for(int i=0;i<=n;i++) {vis[i] = 0;g[i].clear();}

       for(int i=1;i<=n-1;i++)
       {
           int x,y;
           cin>>x>>y;
           g[x].push_back(y);
           g[y].push_back(x);
       }
       dfs(1);
       for(int i=1;i<=n;i++) cnt[color[i]]++;
       if(cnt[0]>cnt[1])
       {
           swap(cnt[0],cnt[1]);
           for(int i=1;i<=n;i++) color[i] ^=1;
       }
       int pp = 0;
       for(int i=0;i<=22;i++)
       {
           if((cnt[0]>>i)&1)
           {
               for(int j=(1<<i);j<=(1<<(i+1))-1;j++)
               {
                   c0[++pp]=j;
                   vis[j]=1;
               }
           }
       }

       int p1=1;
       for(int i=1;i<=n;i++)
       {
           if(color[i]==0)
           {
               cout<<c0[pp--]<<" ";
           }
           else
           {
               while(vis[p1]) ++p1;
               cout<<p1<<" ";
               p1++;
           }
       }
       cout<<endl;
    }
    return 0;
}

E. Array Equalizer(前缀和，绝对值维护，二分)

这是一个挺有意思的题目

首先考虑如何让数组a变为数组b：

首先$a_1$需要减去 $a_1-b_1$

随后$a_2$需要减去 $a_2’-b_2 = a_2-(a_1-b_1) - b_2$

$a_3$需要减去$a_3’ - b_3 = a_3 - (a_1-b_1)-b_3$

$a_4$需要减去$a_4’-b_4 = a_4-(a_1-b_1)-(a_2-(a_1-b_1)-b_2)-b_4$

通过以上不难发现,我们从$a_1$开始操作到$a_n$，只需要考虑$a_i$的$i$的因子有哪儿些即可，只有$i$的因子会对$a_i$做贡献。

接下来考虑如何应对b1的变化，我们要求的式子是：

$f(b_1) = |a_1-b_1|+|a_2-(a_1-b_1) - b_2|+|a_3 - (a_1-b_1)-b_3|+|a_4-(a_1-b_1)-(a_2-(a_1-b_1)-b_2)-b_4|$

这是一个关于$b_1$的函数，其他都是定值，这里难处理的问题在于如何解决绝对值的问题，考虑将所有绝对值表示为$|kb_1+c|$的形式，保证k>0。

式子转化为:

考虑如何去掉绝对值呢？ $k_ib_1+c_i>=0$也就是$b_1>-c_i/k_i$时即可直接去掉，否则需要加一个负号再去掉。

由于有q(q<=1e5)个询问，我们可以按照$-c_i/k_i$进行排序，然后对于每个查询q，我们只需要二分排序后$-c_i/k_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
//#pragma comment(linker, "/STACK:10240000000000,10240000000000")
#include<bits/stdc++.h>
#define pii pair<long long,long long>
#define pdd pair<double,double>
using namespace std;
typedef long long ll;

const int MAXN = 1e6+10;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9+7;

ll a[MAXN],b[MAXN];
pii kc[MAXN];
pii prez[MAXN],suff[MAXN];
vector<double>c;
bool cmp(pii x,pii y)
{
    return -1.0*x.second/(1.0*x.first)<-1.0*y.second/(1.0*y.first);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    b[1] = 0;
    for(int i=1;i<=n;i++)
    {
        kc[i].second += a[i] - b[i];
        for(int j=i+i;j<=n;j+=i)
        {
            kc[j].second -= kc[i].second;
        }
    }
    kc[1].first = -1;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+i;j<=n;j+=i)
        {
            kc[j].first -= kc[i].first;
        }
    }
//    for(int i=1;i<=6;i++) cout<<kc[i].first<<" ";
//    cout<<endl;
//    for(int i=1;i<=6;i++) cout<<kc[i].second<<" ";
//    cout<<endl;
    vector<pii>coef;
    ll lef = 0;
    for(int i=1;i<=n;i++)
    {
        if(kc[i].first==0) lef+=abs(kc[i].second);
        else
        {
            if(kc[i].first<0) coef.push_back({-kc[i].first,-kc[i].second});
            else coef.push_back(kc[i]);
        }
    }
    //cout<<lef<<endl;
    sort(coef.begin(),coef.end(),cmp);
    //for(int i=0;i<coef.size();i++) cout<<coef[i].first<<" "<<coef[i].second<<endl;
    for(int i=0;i<coef.size();i++) c.push_back(-1.0*coef[i].second/(1.0*coef[i].first));
    for(int i=0;i<coef.size();i++)
    {
        if(i==0) {prez[i].first = coef[i].first;prez[i].second = coef[i].second;}
        else {prez[i].first = prez[i-1].first + coef[i].first;prez[i].second = prez[i-1].second + coef[i].second;}
    }
    for(int i=coef.size()-1;i>=0;i--)
    {
        suff[i] = {suff[i+1].first+coef[i].first, suff[i+1].second+coef[i].second};
    }

    int q;
    cin>>q;
    while(q--)
    {
        ll x;
        cin>>x;
        int idx = upper_bound(c.begin(),c.end(),1.0*x) - c.begin();
        ll ans = prez[idx-1].first*x+prez[idx-1].second;
        ans+=-suff[idx].first*x-suff[idx].second;
        ans+=lef;
        cout<<ans<<endl;
    }

    return 0;
}

/*
    ios::sync_with_stdio(false);
    cin.tie(0);
*/
ACM-Codeforces

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！