@2368860385 2020-11-07T03:09:55.000000Z 字数 5883 阅读 181

1038—— Codeforces Round #508 (Div. 2)

codeforces

https://codeforces.com/contest/1038
http://codeforces.com/blog/entry/61692

2018.9.19晚模拟参加
2018.9.20整理

比赛经过

B题想了乱搞，最后最不去，之后想到一个正确的算法，然后A的时候50多分钟了。

A

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
char s[100005];
int cnt[100];
int main() {
    int n = read(), k = read();
    scanf("%s",s+1);
    for (int i=1; i<=n; ++i) cnt[s[i] - 'A' + 1] ++;
    int Ans = n;
    for (int i=1; i<=k; ++i) {
        Ans = min(Ans, cnt[i]);
    }
    cout << Ans * k;
    return 0;
}

B

题意:
1~n的所有数，分成两个集合，使gcd(sum1,sum2)>1，无解输出No，有解输出集合的划分。

首先gcd一定是质数，然后筛出1~n的质数，判断。
一个质数p如果可行的话，一定是这样的
.....p.....2p.....3p
称中间的...为一段，那么p分成了很多段。
每段中的每个数%p后，分别123...(p-1)。
如果有偶数个段，那么就可以让1+(p-1),2+(p-2)...然后p就是合法。
如果有p个段，也是可行的。
所以判断是否p将n分成偶数个，或者p的倍数个完整的段。

正解：<=2的输出No，其他的都有？

一开始猜结论，以为gcd只会是2，交上去不过，算了算3也行，于是加了3的，还是不过，最后想到这个做法，才过。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
int cnt[100005], n;
int pri[100005], tot;
bool nopri[100005];
void init() {
    int T = 45000;
    nopri[1] = true;
    for (int i=2; i<=T; ++i) {
        if (!nopri[i]) pri[++tot] = i;
        for (int j=1; j<=tot&&i*pri[j]<=T; ++i) {
            nopri[i * pri[j]] = true;
            if (i % pri[j] == 0) break;
        }
    }
}
bool solve(int a) { 
    int t = n % a;
    if (t != 0 && t != a - 1) return false;
    int c = (n - 1) / a + 1;
    if (c % 2 == 0 || c % a == 0) {
        cout << "Yes\n" << n / a << " ";
        for (int i=1; i<=n; ++i) 
            if (i % a == 0) cout << i << " ";
        cout << "\n" << n - n / a << " ";
        for (int i=1; i<=n; ++i) 
            if (i % a == 0) ;
            else cout << i << " ";
        return true;
    }
    return false;
}
int main() {
    init();
    cin >> n;   
    for (int i=1; i<=tot; ++i) {
//      cout << pri[i] << " ";
        if (solve(pri[i])) return 0;
    }
    cout << "No";
    return 0;
    int ji = (n + 1) / 2;
//  if (ji & 1) {
//      cout << "No"; return 0;
//  }
//  
    if (ji % 2 == 0) {
        cout << "Yes\n";
        cout << n - ji << " ";
        for (int i=1; i<=n; ++i) {
            if (!(i & 1)) cout << i << " ";
        }
        cout << "\n";
        cout << ji << " ";
        for (int i=1; i<=n; ++i) {
            if (i & 1) cout << i << " ";
        }
        return 0;
    }
    if (solve(3)) {
        cout << "Yes\n";
        cout << n / 3 << " ";
        for (int i=1; i<=n; ++i) 
            if (i % 3 == 0) cout << i << " ";
        cout << "\n" << n - n / 3 << " ";
        for (int i=1; i<=n; ++i) 
            if (i % 3 == 1 || i % 3 == 2) cout << i << " ";
        return 0;
    }
    cout << "No";
    return 0;
}

C

两个人各有一个长度为n的序列。
进行2n次操作，轮流操作。
每次操作可以，删掉对方一个数，或者加上自己的一个数（加上后删除）
每个人采取最优策略，使得分更大，求第一个人的得分-第二个人的得分。

一看以为对抗搜索，但是数据范围有点大。于是发现一个结论，排序后，一个一个的比较。具体见代码。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
int a[100005], b[100005];
bool cmp(int a,int b) {
    return a > b;
}
int main() {
    int n = read();
    for (int i=1; i<=n; ++i) {
        a[i] = read();
    }   
    for (int i=1; i<=n; ++i) {
        b[i] = read();
    }
    sort(a + 1, a + n + 1, cmp);
    sort(b + 1, b + n + 1, cmp);
    LL sum1 = 0, sum2 = 0;
    int p1 = 1, p2 = 1;
    a[n + 1] = -1e9, b[n + 1] = -1e9;
    for (int i=1; i<=n+n; ++i) {
        if (i & 1) {
            if (a[p1] > b[p2]) sum1 += a[p1 ++];
            else p2 ++;
        }
        else {
            if (b[p2] > a[p1]) sum2 += b[p2 ++];
            else p1 ++;
        }
    }
    cout << sum1 - sum2;
    return 0;
}

D

一个长度为n的序列，每个数可以吃掉另一个数，吃掉后，另一数消失，当前数为原来的权值-吃掉数的权值。
即a吃b的话，a变成a-b,b消失。
问最后剩下一个数的时候，这个数最大是多少。

负数的话，直接加上。
正数的话，用一个负数-所有的整数，然后再用一个数-这个数。所有正数就加上了，然后那个负数也加上了。
所有有正有负的情况下， $ans=\sum\limits_{i=1}^{n}abs(a[i])$

全是正数或者负数的情况下，那么可以让绝对值最小的减所有数。
全是正数的时候，还要用一个数减回来。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
int a[500005];
int main() {
    int n = read(); 
    if (n == 1) {
        cout << read();
        return 0;
    }
    LL sum = 0, mn = 1e18;
    bool f = true;
    for (int i=1; i<=n; ++i) {
        a[i] = read();
        mn = min(mn, abs(1ll*a[i]));
        sum += abs(a[i]);
        if (i >= 2 && 1ll * a[i] * a[i - 1] < 0) f = false;
    }
    if (f) {
        sum -= mn;
        sum -= mn;
        cout << sum;
    }
    else {
        cout << sum;
    }
    return 0;
}

E

有n个木棍，n<=100，每个木棍，形容这样[cor1 | val | cor2]如果两个木棍挨着的地方的颜色一样（木棍可以旋转），那么就可以合起来。比如[4|1|3] [2|1|3]就可以合起来变成[4|1|3][3|1|2]。
问一根木棍最大的价值。颜色数量<=4

当时想了一个奇怪的思路。将颜色看成点，一根木棍看成链接两个点的边。一共4个点，两点之间的很多边是可以一起走的，就是形成了环，可以绕很多圈。

当时的思路：从一个点到另一个点，计数条边的话，可以一次全走完，那么就可以合成一条，偶数条的话，拆成两条。然后dfs就好了，边数不多。
这样是错的，因为奇数条边变成了一条，那么它走过去，不能回来了。所以奇数可以拆成3条。
边数比较多，然后这样就超时了

正难则反，换个角度，反过来考虑。同样的，如果在两个点之间经过偶数条边，那么相当于不变，所以把偶数条边合起来，一起走。如果进过了x->y这样的一条边，可以直接把那些偶数条加进去。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 10;
const int INF = 1e9;
int e[N][N][101], cnt[N][N], f[N][N], vis[N];
LL Answer = 0;
void dfs(int x,LL sum) {
    for (int i=1; i<=4; ++i) 
        if (!vis[x] && !vis[i]) sum += f[x][i];
    ++vis[x];
    Answer = max(Answer, sum);
    for (int i=1; i<=4; ++i) {
        if (x != i && cnt[x][i]) {
            sum += e[x][i][cnt[x][i]];
            cnt[x][i] --; cnt[i][x] --; 
            dfs(i, sum);
            cnt[x][i] ++; cnt[i][x] ++;
            sum -= e[x][i][cnt[x][i]]; 
        }
    }
    --vis[x];
    for (int i=1; i<=4; ++i) 
        if (!vis[x] && !vis[i]) sum -= f[x][i];
}
int main() {
    int n = read();
    for (int i=1; i<=n; ++i) {
        int u = read(), w = read(), v = read();
        if (u > v) swap(u, v);
        e[u][v][++cnt[u][v]] = w;
    }
    for (int i=1; i<=4; ++i) {
        for (int k=1; k<=cnt[i][i]; ++k) f[i][i] += e[i][i][k];
        cnt[i][i] = 0;
        for (int j=i+1; j<=4; ++j) {
            int &k = cnt[i][j];
            sort(e[i][j] + 1, e[i][j] + k + 1);
            for (; k>2; k-=2) f[i][j] += e[i][j][k] + e[i][j][k - 1];
            f[j][i] = f[i][j]; 
            cnt[j][i] = cnt[i][j]; e[j][i][1] = e[i][j][1]; e[j][i][2] = e[i][j][2];
        }
    }
    for (int i=1; i<=4; ++i) dfs(i, 0);
    cout << Answer;
    return 0;
}

1038—— Codeforces Round #508 (Div. 2)

比赛经过

A

B

C

D

E

内容目录