Codeforces Round #461 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #461 (Div. 2)
过题数：4
排名：230/11398

A. Cloning Toys

题意

有一个可以克隆玩具的机器，如果放入一个原始玩具，则会获得一个额外的原始玩具和一个克隆玩具，如果放入一个克隆玩具，则会获得两个额外的克隆玩具，$Imp$ 最初有 $1$ 个原始玩具，他想要获得 $x$ 个克隆玩具和 $y$ 个原始玩具，问他能否通过这个机器得到。

输入

输入包含两个整数 $x$ 和 $y~(0\leq x,y\leq10^9)$。

输出

如果可以，则输出 $Yes$，否则输出 $No$，大小写任意。

样例

题解

原始玩具的个数至少为 $1$，且如果原始玩具的个数为 $1$，则他不可能有克隆玩具，如果他有克隆玩具，则克隆玩具的个数至少为 $y-1$，除了通过原始玩具得到的 $y-1$ 个克隆玩具，剩下的所有克隆玩具个数应该为偶数。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
int x,  y;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &x, &y) != EOF) {
        if(x < y - 1 || y < 1) {
            printf("No\n");
            continue;
        }
        if(y == 1 && x != 0) {
            printf("No\n");
            continue;
        }
        x -= y - 1;
        if(x % 2 == 0) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}

B. Magic Forest

题意

给定数字 $n$，问有多少个整数对 $(a,b,c)$ 满足下面的条件：

1. $1\leq a\leq b\leq c\leq n$；
2. $a\bigoplus b\bigoplus c=0$；
3. 以 $a,b,c$ 为三边可以构成一个非退化的三角形。

输入

输入包含一个整数 $n~(1\leq n\leq2500)$。

输出

输出满足条件的整数对的个数。

样例

题解

暴力从 $1$ 到 $n$ 枚举 $a$ 和 $b$ 的值，用异或得到 $c$ 的值进行判断。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
int n;
LL ans;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        ans = 0;
        for(int i = 1; i <= n; ++i) {
            for(int j = i; j <= n; ++j) {
                int k = i ^ j;
                if(k >= j && k <= n && i + j > k) {
                    ++ans;
                }
            }
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

C. Cave Painting

题意

给定整数 $n$ 和 $k$，问对于所有的 $i\in[1,k]$，是否 $n\%i$ 的值都不相同。

输入

输入包含两个整数 $n,k~(1\leq n,k\leq10^{18})$。

输出

如果 $n$ 和 $k$ 满足条件，则输出 $Yes$，否则输出 $No$，大小写任意。

样例

题解

从 $1$ 开始，$n\%1$ 的值一定为 $0$，对 $2$ 取模的值要不等于 $n\%1$，则只能 $n\%2=1$，以此类推，对 $x$ 取模的值必须等于 $x-1$，因此可以建立一个同余方程，可以发现要满足对 $[1,k]$ 内所有的数取模都等于 $x-1$，$n$ 的解是呈阶乘增长的，因此只要暴力从 $1$ 到 $k$ 进行判断，一旦不满足条件就跳出循环，实际需要判断的次数是很少的，远远达不到 $100$。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
LL n, k;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%I64d%I64d", &n, &k) != EOF) {
        bool flag = true;
        for(LL i = 1; i <= k; ++i) {
            if(n % i != i - 1) {
                flag = false;
                break;
            }
        }
        if(flag) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}

D. Robot Vacuum Cleaner

题意

定义一个只包含 $s$ 和 $h$ 的字符串的权值为字符串中 $sh$ 子序列的个数，现在给定 $n$ 个字符串 $t_1,t_2,\cdots,t_n$，问将这些字符串按任意顺序连接起来能够得到的最大的权值。

输入

第一行为一个整数 $n$，接下去 $n$ 行每行一个字符串 $t_i$，每一个字符串都只包含字符 $s$ 和 $h$。

输出

输出将所有字符串按任意顺序连接起来之后得到的最大的权值。

样例

题解

首先统计每个字符串中 $s$ 和 $h$ 的数量 $cnt_s$ 和 $cnt_h$，然后贪心将所有字符串进行排序，排序的规则为：

1. 如果字符串 $t_i$ 排在 $t_j$ 之前，可以得到 $x=s_i\times h_j$ 个 $sh$ 子序列，反之亦然，记为 $y$；
2. 如果 $x=y$，则将 $cnt_s$ 值大的放在前面，否则将 $x$ 和 $y$ 中值大的放在前面。

最后扫一遍排序后的字符串统计 $sh$ 子序列的个数。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
struct Node {
    int Index;
    LL cnts, cnth;
};
bool operator<(const Node &a, const Node &b) {
    LL aa = a.cnts * b.cnth;
    LL bb = b.cnts * a.cnth;
    if(aa == bb) {
        return a.cnts > b.cnts;
    }
    return aa > bb;
}
int n;
string str[maxn];
Node node[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(cin >> n) {
        for(int i = 0; i < n; ++i) {
            cin >> str[i];
            node[i].Index = i;
            node[i].cnts = node[i].cnth = 0;
            for(int j = 0; str[i][j]; ++j) {
                if(str[i][j] == 's') {
                    ++node[i].cnts;
                } else {
                    ++node[i].cnth;
                }
            }
        }
        sort(node, node + n);
        LL cnt = 0, ans = 0;
        for(int i = 0; i < n; ++i) {
            int ii = node[i].Index;
            for(int j = 0; str[ii][j]; ++j) {
                if(str[ii][j] == 's') {
                    ++cnt;
                } else {
                    ans += cnt;
                }
            }
        }
        printf("%I64d\n", ans);
    }
    return 0;
}