cf--全球最大的在线对战平台,1亿鼠标的枪战梦想,你还在等什么,快来加入吧,滑稽。
作为一只很久没打cf的1400分弱鸡,只能打打div3这个样子维持一下生活。
每次打cf都不容易,时断时续卡卡的网络疯狂劝退,特此纪念。

入了ACM的坑

A. Divisibility Problem

已知:$(a+x)\%b=0,\quad 1\leq a,b\leq10^9$。
求:$x$的最小非负整数值,共$t(1\leq t \leq 10^4)$次询问。
解:$x=(b-a\%b)\%b$。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 4e5 + 117;

int t;
int a, b;
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &a, &b);
        printf("%d\n", (b - a % b) % b);
    }
    return 0;
}

B. K-th Beautiful String

已知:长度为$n(3\leq n\leq 10^5)$的字符串由$n-2$个'a'和2个'b'构成。
求:字典序第$k$小的字符串,共$t(1\leq t \leq 10^4)$次询问。
解:前缀和+二分。
分块

  • 如上图所示,将所有字符串按最左边一个'b'所在的位置分块。
  • 设$s[i]$表示第$i$个块有的字符串个数,显然$s[i]=i$。
  • 二分求出第$k$小的字符串在哪个块,并计算右边的'b'所在的位置。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e5 + 117;
const int MAXM = 4e5 + 117;

int t;
int n, block, endid;
LL k, cnt[MAXN];
int main() {
    for(int i = 1; i < MAXN; i++) cnt[i] = cnt[i - 1] + i;
    scanf("%d", &t);
    while(t--) {
        scanf("%d%lld", &n, &k);
        block = lower_bound(cnt, cnt + n, k) - cnt;
        endid = cnt[block] - k;
        for(int i = 0; i < n; i++) {
            if(i == n - 1 - block) putchar('b');
            else if(i == n - block + endid) putchar('b');
            else putchar('a');
        }
        putchar(10);
    }
    return 0;
}

C. Ternary XOR

已知:一个长度为$n(1\leq n \leq 5\cdot10^4)$的三进制数$c$,第一个数一定为2,$a\bigodot b=c$。
求:没有前导0的$a$和$b$满足$max(a,b)$尽可能的小,共$t(1\leq t \leq 10^4)$次询问。
解:贪心+构造。

  • 考虑所有可能的情况

    • $0=0+0$或$0=1+2$或$0=2+1$。
    • $1=0+1$或$1=1+0$。
    • $2=1+1$或$2=0+2$或$2=2+0$。
  • 无论怎么样,$0=0+0$始终选用。
  • 没有1的时候$a=b$,贪心$a$和$b$都尽可能的小,选用$2=1+1$。
  • 存在1的时候假设$a>b$,贪心$a$尽可能的小。

    • 出现1之前,选用$2=1+1$。
    • 第一次出现1,选用$1=1+0$。
    • 出现1之后,选用$1=0+1$和$2=0+2$。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e5 + 117;
const int MAXM = 4e5 + 117;

int t;
int n;
char a[MAXN], b[MAXN], c[MAXN];
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%s", &n, c);
        bool flag = false;
        for(int i = 0; i < n; i++) {
            if(c[i] == '0') a[i] = b[i] = '0';
            else if(c[i] == '1') {
                if(flag) a[i] = '0', b[i] = '1';
                else a[i] = '1', b[i] = '0', flag = true;
            } else {
                if(flag) a[i] = '0', b[i] = '2';
                else a[i] = b[i] = '1';
            }
        }
        a[n] = b[n] = '\0';
        puts(a);
        puts(b);
    }
    return 0;
}

D. Carousel

已知:$n(3\leq n \leq 2 \cdot 10^5)$个数字围成一个圈,对每个数字涂上一种颜色,满足不存在两个不同的数字相邻且颜色相同。
求:任意一种合法的涂色方案,共$t(1\leq t \leq 10^4)$次询问。
解:构造。

  • 如果所有数字都相同,全部使用同一种颜色即可。
  • $n$是偶数,颜色1和颜色2交替使用即可。
  • $n$是奇数:

    • 如果$a[0]=a[n-1]$,则颜色1和颜色2交替使用即可。
    • 否则在序列中寻找一处$a[i-1]=a[i]$,前$i-1$项颜色1和颜色2交替使用,第$i$项跳一次继续交替,例如:1212122121或121212112121。如果不存在$i$满足条件,则最后一项必须使用颜色3。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 4e5 + 117;

int t;
int n, a[MAXN];
int f() {
    for(int i = 1; i < n; i++)
        if(a[i] == a[i - 1]) return i;
    return -1;
}
int main() {
    scanf("%d", &t);
    while(t--) {
        bool all = true;
        scanf("%d", &n);
        for(int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            if(i && a[i] != a[i - 1]) all = false;
        }
        if(all) {
            puts("1");
            for(int i = 0; i < n; i++) printf("1 ");
        } else if(n % 2 == 0 || a[0] == a[n - 1]) {
            puts("2");
            for(int i = 0; i < n; i++) printf("%d ", i % 2 + 1);
        } else {
            int id = f();
            if(id == -1) {
                puts("3");
                for(int i = 0; i < n - 1; i++) printf("%d ", i % 2 + 1);
                printf("3");
            } else {
                puts("2");
                for(int i = 0; i < n; i++) {
                    if(i < id) printf("%d ", i % 2 + 1);
                    else printf("%d ", (i + 1) % 2 + 1);
                }
            }
        }
        putchar(10);
    }
    return 0;
}

E. Tree Queries

已知:$n(2 \leq n \leq 2 \cdot10^5)$个点的树,1为根节点
求:给定$k(1 \leq k \leq n)$个点,问是否存在点$u$,使$k$个点都在根节点到$u$的路径上或距离为1,共$t(1\leq t \leq 2 \cdot 10^4)$次询问。
赛中思路:把$k$个点按深度排序,从下往上合并,若不能合并则说明路径不存在。
TLE:判断$u$是否是$v$的祖先效率太慢。
赛后优化:dfs一遍,进入的时候标记左端点,离开的时候标记右端点。若$u$是$v$的祖先,则一定满足$l[u]<l[v]<r[v]<r[u]$,总体时间复杂度$O(n+m)$。
举个例子:如下图所示:
dfs

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 4e5 + 117;

int n, m, k, t;
int deep[MAXN], root[MAXN];
int l[MAXN], r[MAXN];
int point[MAXN];
struct Edge {
    int to, ne;
} edge[MAXM];
int head[MAXN], tot;
void init() {
    t = tot = 0;
    memset(head, -1, sizeof(head));
    memset(deep, 0, sizeof(deep));
    memset(root, 0, sizeof(root));
}
void addedge(int u, int v) {
    edge[tot].to = v;
    edge[tot].ne = head[u];
    head[u] = tot++;
}
void dfs(int id, int num) {
    l[id] = t++;
    deep[id] = num;
    for(int i = head[id]; i != -1; i = edge[i].ne) {
        if(deep[edge[i].to]) continue;
        root[edge[i].to] = id;
        dfs(edge[i].to, num + 1);
    }
    r[id] = t++;
}
bool check(int u, int v) {
    if(l[u] <= l[v] && r[v] <= r[u]) return true;
    return false;
}
int main() {
    init();
    scanf("%d%d", &n, &m);
    for(int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    dfs(1, 1);
    while(m--) {
        scanf("%d", &k);
        int maxid = 0;
        for(int i = 0; i < k; i++) {
            scanf("%d", &point[i]);
            if(deep[point[i]] > deep[point[maxid]]) maxid = i;
        }
        bool pr = true;
        for(int i = 0; i < k; i++) {
            if(!pr) break;
            if(i != maxid && point[i] != 1) {
                point[i] = root[point[i]];
                if(!check(point[i], point[maxid])) pr = false;
            }
        }
        if(pr) puts("YES");
        else puts("NO");
    }
    return 0;
}

F. Make k Equal

把$n$个数排序后,设$f(i)$为得到$k$个$a[i]$所需要的操作次数,$l(i)$为$a[i]$最左边的位置,$r(i)$为$a[i]$最右边的位置,$pre(i)$表示前$i$项的和,$suf(i)$表示后$i$项的和,$dx(i)=r(i)-l(i)+1-k$,则可分为以下四种情况:

  • 若$dx(i) \leq 0$,则$f(i)=0$。
  • 若只由左边的数通过+1操作得到,设$lcost(i)=(l(i)-1)*(a[i]-1)-pre(l(i)-1)$表示左边的数全部变成$a[i]-1$所需要的操作数,则$f(i)=lcost(i)+dx(i)$。
  • 若只由右边的数通过-1操作得到,设$rcost(i)=suf(r(i)+1)-(n-r(i))*(a[i]+1)$表示右边的数全部变成$a[i]+1$所需要的操作数,则$f(i)=rcost(i)+dx(i)$。
  • 由左边的数和右边的数共同得到,则$f(i)=lcost(i)+rcost(i)+dx(i)$。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 2e5 + 117;

int n, k;
LL a[MAXN];
LL pre[MAXN], suf[MAXN];
map<int, int>l, r;
void build() {
    for(int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + a[i];
        if(l[a[i]] == 0) l[a[i]] = i;
    }
    for(int i = n; i > 0; i--) {
        suf[i] = suf[i + 1] + a[i];
        if(r[a[i]] == 0) r[a[i]] = i;
    }
}
int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    sort(a + 1, a + n + 1);
    build();
    LL ans = 1e15;
    for(int i = 1; i <= n; i++) {
        int dx = k - (r[a[i]] - l[a[i]] + 1);//还需要dx个数
        if(dx <= 0) {
            ans = 0;
            break;
        }
        LL lcost = (l[a[i]] - 1) * (a[i] - 1) - pre[l[a[i]] - 1];//左边的数全部变成a[i]-1所需要的操作次数
        LL rcost = suf[r[a[i]] + 1] - (n - r[a[i]]) * (a[i] + 1);//右边的数全部变成a[i]+1所需要的操作次数
        if(i >= k) ans = min(ans, lcost + dx);
        if(n - i + 1 >= k) ans = min(ans, rcost + dx);
        ans = min(ans, lcost + rcost + dx);
    }
    printf("%lld\n", ans);
    return 0;
}

一次愉快的cf体验,赛中有点紧张,思路不够清晰,码代码也不够快,从来没有四题的弱鸡快哭了。赛后把不好看的代码全部重构提交了一遍,希望能早日上到1600+愉快的玩耍。
入了ACM的坑

Last modification:March 30th, 2020 at 08:28 pm
如果觉得我的文章对你有用,请随意赞赏