@Dmaxiya 2018-08-17T10:14:03.000000Z 字数 6315 阅读 928

Codeforces Round #482 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #482 (Div. 2)
过题数：2
排名：843/10089

A. Pizza, Pizza, Pizza!!!

题意

用最少的线将一个圆平分成 $n+1$ 块。

输入

输入只包含一个整数 $n~(0\leq n\leq10^{18})$ 。

输出

输出需要的线的数量。

样例

输入
3
输出
2

输入
4
输出
5

题解

如果 $n$ 为奇数，就要平分成偶数块，就需要 $\frac{n+1}{2}$ 条线，如果 $n$ 为偶数，就需要平分成奇数块，每条线必须从圆心往外，需要 $n+1$ 条线，注意 $n$ 为 $0$ 就不需要线。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
using namespace std;
#define LL long long
LL int n;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("10.out", "w", stdout);
    #endif // LOCAL
    while(scanf("%I64d", &n) != EOF) {
        if(n == 0) {
            printf("0\n");
            continue;
        }
        ++n;
        if(n % 2 == 0) {
            printf("%I64d\n", n / 2);
        } else {
            printf("%I64d\n", n);
        }
    }
    return 0;
}

B. Treasure Hunt

题意

$Kuro$ 、 $Shiro$ 和 $Katie$ 三人都有一个长度相同的字符串，每个字符串都只包含小写字母和大写字母，三个人都有 $n$ 次对自己的字符串进行操作的机会，每次操作可以选择一个字符并将这个字符修改成另一个字符。一个字符串的价值定义为这个字符串中所有子串出现的最大次数，他们三人经过 $n$ 轮操作后，在采取最优策略下，谁的字符串价值将会最大。

输入

第一行为一个整数 $n~(0\leq n\leq10^9)$ ，接下去三行为三个字符串，分别为 $Kuro,Shiro$ 和 $Katie$ 的初始字符串，字符串的长度不超过 $10^5$ ，字符串只包含小写字母和大写字母。

输出

输出三人都采取最优策略下，字符串价值最大的人，如果存在两个或两个以上最大价值，输出 $Draw$ 。

样例

输入
3 `Kuroo` `Shiro` `Katie`
输出
Kuro
提示
$3$ 轮之后， $Kuro$ 可以将自己的字符串修改为 `ooooo`，价值为 $5$ ，而另外两个人最多只能得到价值为 $4$ 的字符串。

输入
7 `treasurehunt` `threefriends` `hiCodeforces`
输出
Shiro

输入
1 `abcabc` `cbabac` `ababca`
输出
Katie

输入
15 `foPaErcvJ` `mZaxowpbt` `mkuOlaHRE`
输出
Draw
提示
每个人都可以将自己的字符串修改成 $9$ 个相同的字符，因此三人平局。

题解

如果某个长度大于 $1$ 的子串是字符串中出现次数最多的子串，那么这个子串中的字符一定也是出现最多的子串，因此只要处理所有字符即可，对于每个人都计算出可能的最大价值再进行比较就能知道赢家。如果某个字符串的字符完全相等且 $n$ 等于 $1$ ，那么这个符串的价值只能等于 $|s|-1$ ，如果 $Max+n\leq|s|$ （其中 $Max$ 为字符出现的最大次数），那么最大价值就是 $Max+n$ ，否则字符串的价值就可以达到 $|s|$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int n;
char str[3][maxn];
int score[3];
map<char, int> mp[3];
int len[3];
map<int, int> mpp;
map<int, int>::iterator it;
int getscore(int Index, char ch) {
    int tmp = n - (len[Index] - mp[Index][ch]);
    if(tmp >= 0) {
        if(mp[Index][ch] == len[Index] && tmp == 1) {
            return len[Index] - 1;
        }
        return len[Index];
    }
    return n + mp[Index][ch];
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("10.out", "w", stdout);
    #endif // LOCAL
    while(scanf("%d", &n) != EOF) {
        mpp.clear();
        memset(score, 0, sizeof(score));
        for(int i = 0; i < 3; ++i) {
            mp[i].clear();
            scanf("%s", str[i]);
            len[i] = strlen(str[i]);
            for(int j = 0; str[i][j]; ++j) {
                ++mp[i][str[i][j]];
            }
        }
        for(char ch = 'a'; ch <= 'z'; ++ch) {
            for(int i = 0; i < 3; ++i) {
                score[i] = max(score[i], getscore(i, ch));
            }
        }
        for(char ch = 'A'; ch <= 'Z'; ++ch) {
            for(int i = 0; i < 3; ++i) {
                score[i] = max(score[i], getscore(i, ch));
            }
        }
        int Max = 0;
        for(int i = 0; i < 3; ++i) {
            Max = max(Max, score[i]);
            ++mpp[score[i]];
        }
        int cnt = 0;
        int ans = 0;
        for(int i = 0; i < 3; ++i) {
            if(score[i] == Max) {
                ++cnt;
                ans = i;
            }
        }
        if(cnt >= 2) {
            printf("Draw\n");
        } else {
            switch(ans) {
                case 0: printf("Kuro\n"); break;
                case 1: printf("Shiro\n"); break;
                case 2: printf("Katie\n"); break;
            }
        }
    }
    return 0;
}

C. Kuro and Walking Route

题意

在一棵 $n$ 个节点的树上， $(u,v)~(u\neq v)$ 表示从节点 $u$ 到节点 $v$ 的一条路径，其中 $(u,v)$ 与 $(v,u)$ 被认为是不同的路径，问有多少条路径不会先经过节点 $x$ 再经过节点 $y$ 。

输入

第一行包含三个整数 $n,x,y~(1\leq n\leq3\times10^5,1\leq x,y\leq n,x\neq y)$ ，接下去 $n-1$ 行每行两个整数 $a,b~(1\leq a,b\leq n,a\neq b)$ ，表示节点 $a$ 和节点 $b$ 之间有一条边，数据保证给出的边集能构成一棵树。

输出

输出合法的路径数量。

样例

输入
3 1 3 1 2 2 3
输出
5

输入
3 1 3 1 2 1 3
输出
4

题解

将所有路径数 $A_n^2$ 减去不合法的路径数就是答案，不合法路径就是先经过 $x$ 再经过 $y$ 的路径，先以 $x$ 为根 $dfs$ 统计 $y$ 的子树节点数 $son_y$ ，再以 $y$ 为根 $dfs$ 统计 $x$ 的子树节点数量 $son_x$ ，不合法路径数就是 $son_x\times son_y$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 300000 + 100;
LL n;
int x, y, u, v;
vector<int> G[maxn];
int sum[maxn];
void dfs(int f, int x) {
    sum[x] = 1;
    int len = G[x].size();
    for(int i = 0; i < len; ++i) {
        int pos = G[x][i];
        if(pos != f) {
            dfs(x, pos);
            sum[x] += sum[pos];
        }
    }
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("10.out", "w", stdout);
    #endif // LOCAL
    while(scanf("%I64d%d%d", &n, &x, &y) != EOF) {
        for(int i = 1; i <= n; ++i) {
            G[i].clear();
        }
        for(int i = 1; i < n; ++i) {
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(x, x);
        LL ans = sum[y];
        dfs(y, y);
        ans *= sum[x];
        printf("%I64d\n", n * (n - 1) - ans);
    }
    return 0;
}

D. Kuro and GCD and XOR and SUM

题意

初始有一个空的集合，有 $q$ 次操作，每次操作有两种选择：

给定 $u_i$ ，表示将 $u_i$ 加入到集合中；

给定 $x_i,k_i,s_i$ ，从集合中找到一个整数 $v$ ，要求 $v$ 满足条件 $k_i|\gcd(x_i,v),x_i+v\leq s_i$ 且 $x_i\oplus v$ 的值最大。

输入

第一行为一个整数 $q~(2\leq q\leq10^5)$ ，接下去 $q$ 行，每行可以是以下两种格式：

第一个数字为 $1$ ，后面跟着一个整数 $u_i~(1\leq u_i\leq10^5)$ ，表示第一种操作；

第一个数字为 $2$ ，后面跟着三个整数 $x_i,k_i.s_i$ ，表示操作 $2$ 。

输出

对于每次操作 $2$ ，如果可以找到合法的 $v$ ，则输出 $v$ 的值，否则输出 $-1$ 。

样例

输入
5 1 1 1 2 2 1 1 3 2 1 1 2 2 1 1 1
输出
2 1 -1
提示
1.向集合中加入数字 $1$ ，则集合为 $\{1\}$ ； 2.向集合中加入数字 $2$ ，则集合为 $\{1,2\}$ ； 3. $1\|\gcd(1,1),1+1\leq2,1\oplus1=0;1\|\gcd(1,2),1+2\leq3,1\oplus2=3$ 因此答案为 $2$ ； 4.只有 $1$ 满足前两个条件，因此答案为 $1$ ； 5.无法找到满足条件的数字，因此答案为 $-1$ 。

输入
10 1 9 2 9 9 22 2 3 3 18 1 25 2 9 9 20 2 25 25 14 1 20 2 26 26 3 1 14 2 20 20 9
输出
9 9 9 -1 -1 -1

题解

若 $k_i$ 不能整除 $x_i$ ，直接输出 $-1$ ，如果可以整除，答案就在 $k_i$ 的所有倍数中查找，建立 $10^5$ 棵字典树，第 $i$ 棵字典树存的是集合中 $i$ 的所有倍数，这样每加入一个数字 $u_i$ ，就将 $u_i$ 加入到他的所有约数的字典树中，对于每次 $2$ 操作，直接在第 $k$ 棵字典树上查找满足条件的答案即可，需要 $O(n\ln n)$ 地预处理所有约数。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
vector<vector<int> > tree;
vector<int> Min;
int cnt;
bool vis[maxn];
struct Trie {
    int root;
    int creat(int x) {
        int ret = cnt;
        ++cnt;
        tree.push_back(vector<int>(2, -1));
        Min.push_back(x);
        return ret;
    }
    void Init() {
        root = creat(1000000000);
    }
    int id(int x, int Index) {
        return ((x >> (20 - Index)) & 1);
    }
    void add(int x) {
        int pos = root;
        Min[pos] = min(Min[pos], x);
        for(int i = 0; i <= 20; ++i) {
            int w = id(x, i);
            if(tree[pos][w] == -1) {
                tree[pos][w] = creat(x);
            }
            pos = tree[pos][w];
            Min[pos] = min(Min[pos], x);
        }
    }
    int query(int x, int s) {
        int ret = 0;
        int num = 0;
        int pos = root;
        for(int i = 0; i <= 20; ++i) {
            int w = !id(x, i);
            if(tree[pos][w] == -1 || Min[tree[pos][w]] > s) {
                w = !w;
            } else {
                ret |= (1 << (20 - i));
            }
            if(tree[pos][w] == -1 || Min[tree[pos][w]] > s) {
                return -1;
            }
            num |= (w << (20 - i));
            pos = tree[pos][w];
        }
        return num;
    }
};
int q, command, x, k, s;
Trie t[maxn];
vector<int> fac[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("10.out", "w", stdout);
    #endif // LOCAL
    for(int i = 1; i < maxn; ++i) {
        t[i].Init();
        for(int j = i; j < maxn; j += i) {
            fac[j].push_back(i);
        }
    }
    scanf("%d", &q);
    for(int i = 0; i < q; ++i) {
        scanf("%d", &command);
        if(command == 1) {
            scanf("%d", &x);
            if(vis[x]) {
                continue;
            }
            vis[x] = true;
            int len = fac[x].size();
            for(int j = 0; j < len; ++j) {
                int num = fac[x][j];
                t[num].add(x);
            }
        } else {
            scanf("%d%d%d", &x, &k, &s);
            if(x % k != 0 || s <= x) {
                printf("-1\n");
            } else {
                printf("%d\n", t[k].query(x, s - x));
            }
        }
    }
    return 0;
}

Codeforces Round #482 (Div. 2)

A. Pizza, Pizza, Pizza!!!

题意

输入

输出

样例

题解

过题代码

B. Treasure Hunt

题意

输入

输出

样例

题解

过题代码

C. Kuro and Walking Route

题意

输入

输出

样例

题解

过题代码

D. Kuro and GCD and XOR and SUM

题意

输入

输出

样例

题解

过题代码

内容目录