桂林电子科技大学 ACM 暑假课 | 7 月 25 日 ACM 期中考试题解

这次比赛简直绝了，A 到 E 五道题一道不会，就最后的 F 题打牌会，呜呜呜，还是多刷刷算法题吧。

A: 奇数和数组

题目描述：

给你一个由 n 个整数组成的数组 a。
在一次移动中，您可以选择两个下标 (1 \leq i, j \leq n)，且 (i \neq j)，并且设置 (a_i := a_j)。
您可以执行这样的移动任意次数（可能是零次）。您可以在不同的操作中选择不同的下标。
操作 := 是赋值的操作（即选择 i 和 j 并用 (a_j) 替换 (a_i)）。
你的任务是判断是否有可能得到一个元素之和为奇数（不能被 2 整除）的数组。

输入：

第一行包含一个整数 t（(1 \leq t \leq 2000)）——测试用例的数量。
接下来的 2t 行描述了测试用例。
测试用例的第一行包含一个整数 n（(1 \leq n \leq 2000)）——数组中元素的数量。
测试用例的第二行包含 n 个整数 (a_1, a_2, \dots, a_n)（(1 \leq a_i \leq 2000)），保证所有测试用例的 n 之和不超过 2000（(\sum n \leq 2000)）。

输出：

对于每个测试用例，如果能得到一个奇数元素和的数组，输出 "YES"（不加引号），否则输出 "NO"。

样例输入：

样例输出：

YES
NO
YES
NO
NO

B: 暗箱操作

题目描述：

有两个英语菜鸡 lzh 和 xzy，每个人所能解决的问题都不一样。每个学期的英语考试到了，对于每一个英语题目都有一个相应的分数且每道题的相应分数 (p_i) 不能小于 1。
所有题目的分数总和最低的人就获得挂科重修再来一次，作为 lzh 好朋友的你，为了让 lzh 的英语考试分数比 xzy 高，你需要偷偷操控每题的分数 (p_i)。
但是如果 (p_i) 太大，lzh 就会因为作弊被抓住，所以你要做的就是最小化所有英语题目中的最大分数 (p_i)。

输入：

第一行包含一个整数 n（(1 \leq n \leq 100)），代表英语题目的数量。
第二行有 n 个整数 (r_1, r_2, \dots, r_n)（0 ≤ (r_i) ≤ 1），(r_i = 1) 意味着 lzh 会第 i 题，(r_i = 0) 意味着不会。
第三行有 n 个整数 (b_1, b_2, \dots, b_n)（0 ≤ (b_i) ≤ 1），(b_i = 1) 意味着 xzy 会第 i 题，(b_i = 0) 意味着不会。

输出：

如果不能通过任何手段让 lzh 的分数大于 xzy 就输出 -1。
否则输出你在所有项目中修改分数的最大值。

样例输入：

1
2
3

5
1 1 1 0 0
0 1 1 1 1

样例输出：

提示：

对于样例来说，你只需要把第一道题的分数改为 3，第二道题的分数改为 1，第三道题的分数改为 3，第四道题的分数改为 1，第五题的分数改为 1。
那么 lzh 的得分就是 3+1+3=7，而 xzy 的得分是 1+3+1+1=6，lzh 的分数就比 xzy 的高了。

C: 简简单单 A+B

题目描述：

给出三个整数 A, B, N； (1 < A, B, N < 10^9)。
我们可以进行如下操作：

操作 1：让 (A = A + B)。
操作 2：让 (B = A + B)。

问最少需要多少次操作，可以使 (\max(A, B)) 严格大于 N。
(\max(a,b)) 为 (A,B) 中较大的那个。

输入：

第一行一个整数 T 代表测试组数（(1 < T < 100)）。
接下来 T 行，每行三个整数 A, B, N。

输出：

输出 T 行，每行一个整数，代表所需要的最少操作次数。

样例输入：

1
2
3

2
1 2 3
5 4 100

样例输出：

1
2

2
7

D: 淘淘的暗号

题目描述：

淘淘的暗号为一串由 n 个小写字母组成的字符串 b，原文 a 生成 b 的方法为 a 中从左到右将每个长度为 2 的子串加入到 b 中，例如 a 串为 “abcd”，那么子串从左到右的顺序为 “ab”, “bc”, “cd”，则 b 为 “abbccd”。

输入：

输入长度为 n（(3 \leq n \leq 100000)）的暗号 b。

输出：

输出原文 a。

样例输入：

abbaac

样例输出：

abac

参考程序：

#include <string.h>
#include <iostream>
using namespace std;

int main() {
    int n;
    char s[100001];
    gets(s);
    n = strlen(s);
    int i = 0;
    while(i <= n - 1) {
        cout << s[i];
        i += 2;
    }
    cout << s[n - 1];
    return 0;
}

E: 淘淘的序列

题目描述：

对于一个长为 n 的数字序列中的每个数字 $a_i$ ，若当 $i$ 为奇数时 $a_i$ 也为奇数，则称它为淘淘序列。
同时，淘淘每次可以将序列中两个任意数字交换位置，求出淘淘需要多少次交换能将一个序列变为淘淘序列。

注意： $i$ 从 0 开始。

输入:

第一行输入一个整数 n(1<=n<=100000)，第二行输入 n 个整数 $a_i$ (0<=i<=n-1)

输出:

输出一个整数，代表淘淘最小需要做多少次交换操作能将给定序列变为淘淘序列，若不能变成淘淘序列输出-1

样例输入:

1
2

4
3 2 7 6

样例输出:

F: 打牌

题目描述：

sys 和 llf 在打牌，他们觉得现有的玩法太简单，所以他们玩起了摸牌游戏
规则如下：

有 N 张牌
两个人轮流摸牌每次摸牌的数量只能是 2 的幂次比如 1，2，4，8，16 ……
当轮到某人摸牌，此人若无牌可摸，败
llf 先手摸牌
他们两人都会采取最优策略去摸牌

输入:

第一行一个数 T 代表测试组数

下面 N 行每行一个数 N 意义如题所示

输出:

输出 T 行

若先手赢输出 llfnb

否则输出 sysnb

样例输入:

样例输出:

llfnb
sysnb
llfnb
sysnb

参考程序：

#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
int main(){
    int t,i,ans=1;
    long long l;
    cin>>t;
    while(t--){
        ans=1;
        cin>>l;
            if(l%3==0)
                ans=0;
            if(ans==0)
            cout<<"sysnb"<<endl;
            else
            cout<<"llfnb"<<endl;
        }
            return 0;
    }