CF531 div3 1102

Author Avatar
Axell 1月 29, 2019
  • 在其它设备中阅读本文章

goto

A Integer Sequence Dividing

大水题，直接判断所有整数的和％2的余数即为答案

#include <bits/stdc++.h>
using namespace std;

int n;
long long tmp;

int main(){
    cin>>n;
    tmp=(long long)n*(n+1)/2;
    cout<<(tmp&1)<<endl;
    return 0;
}

B Array K-Coloring

先按元素大小排序，然后换着颜色染过去，遇到同一值染了相同元素或元素个数少于颜色个数，均不能完成染色

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> p;
map <p,bool> ma;
struct node{
    int v,id,c;
}a[5005];

int n,k;

bool cmp(node x,node y){
    return x.v<y.v;
}
bool cmp2(node x,node y){
    return x.id<y.id;
}
int main(){
    cin>>n>>k;
    for (int i=1;i<=n;++i) scanf("%d",&a[i].v),a[i].id=i;
    sort(a+1,a+n+1,cmp);

    if (n<k){
        cout<<"NO"<<endl;
        return 0;
    }
    int nowk=1;
    for (int i=1;i<=n;++i,++nowk){
        if (nowk>k) nowk=1;
        a[i].c=nowk;
    }
    for (int i=1;i<=n;++i){
        if (ma[{a[i].v,a[i].c}]){
            cout<<"NO"<<endl;
            return 0;
        }
        ma[{a[i].v,a[i].c}]=1;
    }
    sort(a+1,a+n+1,cmp2);
    cout<<"YES"<<endl;
    for (int i=1;i<=n;++i) printf("%d ",a[i].c);
    return 0;
}

C Doors Breaking and Repairing

由于游戏时间很长，所以只要打破速度>修复速度，必然能把门全部打破
如果x<=y，则需要尽快打破耐久值<=x的门，统计出<=x的总数，能打破的数量为(n+1)/2

#include <bits/stdc++.h>
using namespace std;

int n,x,y,tmp,ans;

int main(){
    scanf("%d %d %d",&n,&x,&y);
    for (int i=1;i<=n;++i){
        scanf("%d",&tmp);
        if (tmp<=x) ans++;
    }
    if (x>y) printf("%d\n",n);
    else printf("%d",(ans+1)>>1);
    return 0;
}

D Balanced Ternary String

简单的贪心，按照以下的方式执行
如果2的个数少于需要值，默认从后向前替换
如果0的个数少于需要值，默认从前向后替换
如果1的个数小于所需值，先从前向后将多余的2替换成1，再从后向前将多余的0替换成1

#include <bits/stdc++.h>
using namespace std;

int n,a[3],ans;
char s[300005];

int main(){
    cin>>n;
    scanf("%s",s+1);
    for (int i=1;i<=n;++i) a[s[i]-'0']++;
    for (int i=n;i>=1;--i){
        if (a[2]>=n/3) break;
        int tmp=s[i]-'0';
        if (tmp!=2 && a[tmp]>n/3){
            a[tmp]--;
            a[2]++;
            s[i]='2';
            ans++;
        }
    }
    for (int i=1;i<=n;++i){
        if (a[0]>=n/3) break;
        int tmp=s[i]-'0';
        if (tmp!=0 && a[tmp]>n/3){
            a[tmp]--;
            a[0]++;
            s[i]='0';
            ans++;
        }
    }
    for (int i=1;i<=n;++i){
        if (a[1]>=n/3) break;
        int tmp=s[i]-'0';
        if (tmp==2 && a[2]>n/3){
            a[2]--;
            a[1]++;
            s[i]='1';
            ans++;
        }
    }
    for (int i=n;i>=1;--i){
        if (a[1]>=n/3) break;
        int tmp=s[i]-'0';
        if (tmp==0 && a[0]>n/3){
            a[0]--;
            a[1]++;
            s[i]='1';
            ans++;
        }
    }
    printf("%s",s+1);
    return 0;
}

E Monotonic Renumeration

两个相同的元素中间的构造方案是确定的，只需要统计有独立的几段即可，用前缀和和差分

#include <bits/stdc++.h>
using namespace std;

int n,sum[200005];
long long p=998244353;
struct node{
    int v,id;
}a[200005];

bool cmp(node x,node y){
    return x.v<y.v||x.v==y.v&&x.id<y.id;
}

int main(){
    cin>>n;
    for (int i=1;i<=n;++i) scanf("%d",&a[i].v),a[i].id=i;
    sort(a+1,a+n+1,cmp);
    int now=1;
    while (now<=n){
        int last=now;
        while (a[now+1].v==a[last].v && now<n) now++;
        if (last!=now){
            sum[a[last].id]++;
            sum[a[now].id]--; 
        }
        now++;
    }
    long long ans=1;
    int tmp=0,tt=0;
    for (int i=1;i<=n;++i){
        tt+=sum[i-1];
        if (tt==0) tmp++;
    }
    tmp--;
    for (int i=1;i<=tmp;++i) ans=ans*2%p;
    cout<<ans<<endl;
    return 0;
}

F Elongated Matrix

预处理+最短哈密尔顿路径

首先，可以不考虑m（可以预处理出任意2行同列的元素之间的最小差异。以及i行的k列和j行的k+1列的元素之间的最小差异,这将用于当第i行作为最后一行、第j行作为第一行）
接下来，只需要考虑行之间的顺序。
一种可行的解法是：每次枚举第一行j和最后一行i，求出i-j之间的Hamiltonian路径，使其每条路径的最小值最大，求Hamiltonian路径的复杂度为2^n_n，外部循环复杂度为n_n，总复杂度为O(2^n*n^3),因为n=16，所以不会超时

#include <bits/stdc++.h>
using namespace std;

int n,m,a[17][10005],mn1[17][17],mn2[17][17],t[100000][17],ans;

int get(int mask,int st){
    if (t[mask][st]!=-1) return t[mask][st];
    t[mask][st]=0;
    for (int i=1;i<=n;++i){
        if (i!=st && mask&(1<<(i-1)))
            t[mask][st]=max(t[mask][st],min(mn1[i][st],get(mask^(1<<(st-1)),i)));
    }
    return t[mask][st];
}

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j) scanf("%d",&a[i][j]);
    }
    for (int i=1;i<=n;++i){
        for (int j=1;j<=n;++j){
            int tmp=0x3f3f3f3f;
            for (int k=1;k<=m;++k){
                tmp=min(tmp,abs(a[i][k]-a[j][k]));
            }
            mn1[i][j]=tmp;
            tmp=0x3f3f3f3f;
            for (int k=1;k<m;++k){
                tmp=min(tmp,abs(a[i][k]-a[j][k+1]));
            }
            mn2[i][j]=tmp;
        }
    }
    for (int i=1;i<=n;++i){
        memset(t,-1,sizeof(t));
        for (int j=1;j<=n;++j) if (i==j) t[1<<(j-1)][j]=0x3f3f3f3f; else t[1<<(j-1)][j]=0;
        for (int j=1;j<=n;++j) ans=max(ans,min(mn2[i][j],get((1<<n)-1,j)));
    }
    cout<<ans<<endl;
    return 0;
}

另一种可行的解法是二分答案+Hamiltonian路径存在性判断，预处理同第一种解法，且在边权均较小是更优，每次枚举答案后，取出所有大于该答案的边，再判断是否存在Hamiltonian路径即可，总复杂度为O(2^n_n^2_log MAXa[i])

#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;

const int N = 18;
const int M = 100 * 1000 + 13;
const int INF = 1e9;

int used[1 << N];char dp[1 << N];int g[1 << N];
int n, m;int a[N][M];int mn1[N][N], mn2[N][N];

bool calc(int mask){
    if (dp[mask] != -1)
        return dp[mask];
    used[mask] = 0;
    dp[mask] = 0;
    forn(i, n){
        if (!((mask >> i) & 1))
            continue;
        if (!calc(mask ^ (1 << i)))
            continue;
        if (!(used[mask ^ (1 << i)] & g[i])) //判断路径是否大于等于答案
            continue;
        used[mask] |= (1 << i);
        dp[mask] = 1;
    }
    return dp[mask];
}
bool check(int k){
    forn(i, n){
        g[i] = 0;
        forn(j, n)
            g[i] |= (1 << j) * (mn1[j][i] >= k);
    }
    forn(i, n){
        memset(dp, -1, sizeof(dp));
        forn(j, n){
            dp[1 << j] = (j == i);
            used[1 << j] = (1 << j);
        }
        calc((1 << n) - 1);
        forn(j, n) if (mn2[j][i] >= k && ((used[(1 << n) - 1] >> j) & 1))
            return true;
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &m);
    forn(i, n) forn(j, m)
        scanf("%d", &a[i][j]);

    forn(i, n) forn(j, n){
        int val = INF;
        forn(k, m)
            val = min(val, abs(a[i][k] - a[j][k]));
        mn1[i][j] = val;
        val = INF;
        forn(k, m - 1)
            val = min(val, abs(a[i][k] - a[j][k + 1]));
        mn2[i][j] = val;
    }//预处理

    int l = 0, r = INF;
    while (l < r - 1){
        int m = (l + r) / 2;
        if (check(m))
            l = m;
        else
            r = m;
    }

    printf("%d\n", check(r) ? r : l);
}

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/86/