Educational Codeforces Round 63 (Rated for Div. 2)

佚名 6年前 (2019-04-23) 随笔 1769人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题意：给一字符串，把一个区间的字符串倒置要求倒置后字典序严格变小

只要看这个字符串有没有逆序对就好了有的话输出

Educational Codeforces Round 63 (Rated for Div. 2) 随笔第1张

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

const int maxn = 3e5 + 10;
char s[maxn];
int temp[26];
vector<int> G[26];

int main() {
    int len;
    scanf("%d%s", &len, s);
    bool ans = false;
    int l = 0, r = 0;
    for (int i = 0; i < len; i++) {
        int id = s[i] - 'a';
        temp[id]++;
        G[id].push_back(i);
        for (int j = id + 1; j < 26; j++) {
            if (temp[j]) {
                ans = true;
                l = G[j][0];
                r = i;
                break;
            }
        }
        if (ans) break;
    }  
    if (ans) {
        printf("YES\n%d %d\n", l + 1, r + 1);
    } else puts("NO");
    return 0;
}

View Code

B. Game with Telephone Numbers

题意：给一长度为n（n为奇数）的字符串两人轮流删去一个字符问先手那人无论另一个人怎么删是否能获胜获胜条件：长度为11时第一个字符是8

看起来策略很多其实两个人的最优策略分别是：先手那人从前往后擦掉非8的字符后手从前往后擦掉8 模拟即可

Educational Codeforces Round 63 (Rated for Div. 2) 随笔第3张

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

const int maxn = 1e5 + 10;
char s[maxn];
vector<int> pos;
bool vis[maxn];
char ans[maxn];

int main() {
    int len;
    scanf("%d%s", &len, s + 1);
    int cnt8 = 0;
    for (int i = 1; i <= len; i++) {
        if (s[i] == '8') cnt8++, pos.push_back(i);  
    }
    int cnt2 = len - 11;
    cnt2 /= 2;
    if (cnt8 == 0 || cnt2 >= cnt8) {
        puts("NO");
        return 0;
    }
    for (int i = 0; i < cnt2; i++) vis[pos[i]] = 1;
    int cnt = 0;
    for (int i = 1; i <= len && cnt < cnt2; i++) {
        if (s[i] != '8') vis[i] = 1, cnt++;
    }
    cnt = 0;
    for (int i = 1; i <= len; i++) {
        if (!vis[i]) ans[cnt++] = s[i];
    }
    if (ans[0] == '8') puts("YES");
    else puts("NO");
    return 0;
}

View Code

这个想法其实等价于前n-10个字符里面的cnt8与(n-11)/2的关系

比赛的时候本来想着直接推的但是写的太乱了...WA了一发就直接上模拟了...

C. Alarm Clocks Everywhere

题意：给n个时间xi，m个可用的时间间隔pi，设一个闹钟作为开始时间，一个时间间隔，问是否存在一个时间间隔pi，让n个时间都有闹钟响（在其他时间响没有关系）

开始时间就肯定是x1 然后差分一下这些时间，求n-1个差值的gcd 看看有没有pi是这个gcd的因子

Educational Codeforces Round 63 (Rated for Div. 2) 随笔第5张

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

const int maxn = 3e5 + 10;
ll x[maxn];
ll p[maxn];
ll d[maxn];

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

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%I64d", &x[i]);
    for (int i = 1; i <= m; i++) scanf("%I64d", &p[i]);
    for (int i = 1; i <= n - 1; i++) d[i] = x[i + 1] - x[i];
    ll g = d[1];
    for (int i = 2; i < n; i++) g = gcd(g, d[i]);
    int ans = 0;
    for (int i = 1; i <= m; i++) {
        if (g % p[i] == 0) {
            ans = i;
            break;
        }
    }
    if (ans) {
        puts("YES");
        printf("%I64d %d\n", x[1], ans);
    } else puts("NO");
    return 0;
}

View Code

D. Beautiful Array

题意：n个数字还有一个x 至多一次操作：给一个区间上的数都乘上x 然后求最大子段和

比赛的时候受到最大子段和和最小子段和的影响...写的过程中想到了会WA的情况（下面说）...但我仍想侥幸地交一遍（好煞笔啊）

我地思路是求一遍最大子段和M1和最小子段和M2 比较 M1 和 M1*x 和 M2*x 的大小

M1最大直接输出 M1*x 或 M2*x 就在这个子段的 l，r 两头去再跑一遍最大子段和

看起来没问题但是如果有很多个情况相等的话就不是最优解了

比如

5 -1

-1 1 -1 1 -1

M1是1 M1*x是-1 M2*x是+1

这样直接就输出1了

然鹅答案是3

即使我把条件改成

M1严格大于另外两个才能输出

这样M2*x是+1

第一个数就是了

两头去找的答案就是2 还是不符合结果

找到那个最大的之后还得去原数组看看是不是有很多相等的子段和

因为每个字段两端的数据有可能不同所以得到的很有可能不是答案

可能还有更多的WA点

赛后一打开群就有大佬贴代码

dp[i][0,1,2]表示到i的最大子段和 0到i为止还没有乘x、1第i个要乘x、2已经乘过x了从第i个开始后面都不能乘x了

转移方程

dp[i][0] = max(0, dp[i-1][0]) + a[i]

dp[i][1] = max(dp[i-1][0], dp[i-1][1],0) + a[i] * x

dpi][2] = max(dp[i-1][1], dp[i-1][2], 0) + a[i]

Educational Codeforces Round 63 (Rated for Div. 2) 随笔第7张

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

const int maxn = 3e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll a[maxn];
ll dp[maxn][3];

int main() {
    int n;
    ll x;
    scanf("%d%I64d", &n, &x);
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%I64d", &a[i]);
        dp[i][0] = max(0LL, dp[i-1][0]) + a[i];
        dp[i][1] = max(max(dp[i-1][0], dp[i-1][1]), 0LL) + a[i] * x;
        dp[i][2] = max(dp[i-1][1], dp[i-1][2]) + a[i];
        ans = max(ans, max(dp[i][0], max(dp[i][1], dp[i][2]))); 
    }    
    printf("%I64d", ans); 
    return 0;
}