Codeforces Round #726 (Div. 2) 题解

本场链接:Codeforces Round #726 (Div. 2)

A. Arithmetic Array

按题意模拟即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n,sum = 0;scanf("%d",&n);
        forn(i,1,n)
        {
            int x;scanf("%d",&x);
            sum += x;
        }
        if(sum == n)    puts("0");
        else if(sum < n)    puts("1");
        else printf("%d\n",sum - n);
    }
    return 0;
}

B. Bad Boy

不难猜想到四个角是不会变得更差的选择。枚举所有选择的情况即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
#define x first
#define y second

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        ll n,m,a,b;scanf("%lld%lld%lld%lld",&n,&m,&a,&b);
        pii qua[4] = {{1,1},{1,m},{n,1},{n,m}},op[2] = {{1,1},{1,1}};
        ll res = 0;
        forn(i,0,3) forn(j,0,3)
        {
            int x1 = qua[i].x,y1 = qua[i].y,x2 = qua[j].x,y2 = qua[j].y;
            ll dist = abs(a - x1) + abs(b - y1) + abs(x2 - x1) + abs(y2 - y1) + abs(a - x2) + abs(b - y2);
            if(dist > res)
            {
                res = dist;
                op[0] = qua[i];
                op[1] = qua[j];
            }
        }
        printf("%d %d %d %d\n",op[0].x,op[0].y,op[1].x,op[1].y);
    }
    return 0;
}

C. Challenging Cliffs

由于\(|h_1-h_n|\)最小是前提条件,所以优先满足。不妨对整个数组排序,那么可以快速找到:左边最小且之差最小的一对数。之后分配不难想到要使从第一个元素就开始得到贡献,应该从小到大依次填入没填的数,且第一个数比最左侧的大,剩下的继续按大小分配即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)

const int N = 2e5+7;
int a[N],ans[N];

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n;scanf("%d",&n);
        forn(i,1,n) scanf("%d",&a[i]);
        sort(a + 1,a + n + 1);
        int p = 1,cur = 2e9+100;
        forn(i,1,n - 1)
        {
            if(abs(a[i] - a[i + 1]) < cur)
            {
                p = i;
                cur = abs(a[i] - a[i + 1]);
            }
        }        
        int idx = 2;
        ans[1] = a[p];ans[n] = a[p + 1];
        forn(i,p + 2,n) ans[idx++] = a[i];
        forn(i,1,p - 1) ans[idx++] = a[i];
        forn(i,1,n) printf("%d ",ans[i]);
        puts("");
    }

    return 0;
}

D. Deleting Divisors

  • \(n\)是奇数,则删除一个因子一定会让\(n\)变成一个偶数(且不是\(2^k\))。
  • \(n\)是偶数但不是\(2^k\)则可以通过减去一个奇因子的办法使之变成一个奇数。如果先手\(n\)是偶数那么一定能让后手始终是一个奇数,最后要么走到\(1\)要么走到质数,显然两者都是必败态。所以\(n\)是偶数且不是\(2^k\)时先手必胜,奇数时必败。
  • \(n\)\(2^k\),若把\(n\)变成一个偶数但不是\(2^k\)显然必败,所以只能继续让他是一个\(2^k\),由于\(2^k-2^{k-1}=2^{k-1}\).所以当\(k\)是奇数时先手必败,反之先手必胜。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)


int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n;scanf("%d",&n);
        if(n % 2)
        {
            puts("Bob");
            continue;
        }
        int cnt = 0;
        while(n % 2 == 0)
        {
            ++cnt;
            n /= 2;
        }
        if(n > 1 || cnt % 2 == 0)   puts("Alice");
        else puts("Bob");
    }
    return 0;
}

E1. Erase and Extend (Easy Version)

不难想到答案一定是某个前缀重复若干次得到的,暴力枚举即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)


int main()
{
    Angel_Dust;
    int n,k;cin >> n >> k;
    string cur,s;cin >> s;
    string res;
    forn(i,0,n - 1)
    {
        cur += s[i];
        string nxt;
        forn(j,1,(k + i) / (i + 1))   nxt += cur;
        nxt.resize(k);
        if(res == "" || nxt < res)  res = nxt;
    }
    cout << res << endl;
    return 0;
}

E2. Erase and Extend (Hard Version)

copy来的牛逼做法:记\(prefix(x)\)表示前缀\([1,x]\)\(f_k(s)\)表示将\(s\)重复若干次直到其长度\(\geq k\)得到的串。

问题等价于求一个\(x\)使\(f_k(prefix(x))\)最小。

考虑枚举\(x\in[2,n]\)即当前答案\(pos=1\),每次尝试更新\(pos\):若\(f_k(prefix(pos))[x] > s[x]\)则换上\(x\)进入序列会更优,反之则不会变得更好,因为以后的所有前缀一定包含\(s[x]\),直接退出即可。如果相同则说明当前这一位无所谓,答案可能在后面继续做即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)

const int N = 5e5+7;
char s[N];

int main()
{
    int n,m;scanf("%d%d%s",&n,&m,s + 1);
    int k = min(n,m),pos = 1;
    forn(i,2,k)
    {
        if(s[i] < s[(i - 1) % pos + 1])   pos = i;
        else if(s[i] > s[(i - 1) % pos + 1])  break;
    }
    forn(i,1,m) printf("%c",s[(i - 1) % pos + 1]);
    return 0;	
}

F. Figure Fixing

首先考虑无解:若\(\sum v_i\)\(\sum t_i\)奇偶性不同,则一定无解。

如果\(m=n-1\)则是一个树,因为树一定是一个二分图,那么边上的操作等价于对两个集合同时加或减一个值,相当于白干。对树二染色若两个集合的\(\sum v_i - t_i\)值不同则无解,反之一定有解。如果不是二分图,则一定有两个点染色的时候会是同色的:这两个点可以随意调整集合的和,所以一定有解。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)

const int N = 2e5+7,M = 2 * N;
int edge[M],succ[M],ver[N],idx;
int v[N],t[N],col[N];
ll sum[2];

void add(int u,int v)
{
    edge[idx] = v;
    succ[idx] = ver[u];
    ver[u] = idx++;
}

bool dfs(int u,int c,int d)
{
    col[u] = c;
    sum[d] += v[u] - t[u];
    for(int i = ver[u];~i;i = succ[i])
    {
        int v = edge[i];
        if(!col[v])
        {
            if(!dfs(v,3 - c,d ^ 1)) return 0;
        }
        else if(col[v] == c)    return 0;
    }
    return 1;
}

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n,m;scanf("%d%d",&n,&m);
        forn(i,1,n) ver[i] = -1,col[i] = 0;idx = 0;
        sum[0] = 0;sum[1] = 0;
        forn(i,1,n) scanf("%d",&v[i]);
        forn(i,1,n) scanf("%d",&t[i]);
        forn(i,1,m)
        {
            int u,v;scanf("%d%d",&u,&v);
            add(u,v);add(v,u);
        }
        ll vsum = 0,tsum = 0;
        forn(i,1,n) vsum += v[i],tsum += t[i];
        if(abs(vsum) % 2 != abs(tsum) % 2)    puts("NO");
        else
        {
            if(!dfs(1,1,0) || sum[1] == sum[0]) puts("YES");
            else puts("NO");
        }
    }
    return 0;
}

Codeforces Round #726 (Div. 2) 题解

上一篇:lua委托


下一篇:记一次log4j日志导致线上OOM问题案例