ACM之7-25日中期比赛
1.A:奇数和数组
题目描述
给你一个由n个整数组成的数组a。 在一次移动中，您可以选择两个下标 1≤i，j≤n，i≠j并且设置ai:=aj。您可以执行这样的移动任意次数(可能是零次)。您可以在不同的操作中选择不同的下标。 操作:=是赋值的操作(即选择 i 和 j 并用 aj 替换 a i)。 你的任务是判断是否有可能得到一个元素之和为奇数(不能被2整除)的数组。
1.A:奇数和数组
题目描述
给你一个由n个整数组成的数组a。 在一次移动中，您可以选择两个下标 1≤i，j≤n，i≠j并且设置ai:=aj。您可以执行这样的移动任意次数(可能是零次)。您可以在不同的操作中选择不同的下标。 操作:=是赋值的操作(即选择 i 和 j 并用 aj 替换 a i)。 你的任务是判断是否有可能得到一个元素之和为奇数(不能被2整除)的数组。
输入
输入的第一行包含一个整数t(1≤t≤2000)——测试用例的数量。
接下来的2t行描述了测试用例。
测试用例的第一行包含一个整数n(1≤n≤2000)——a中的元素数。
测试用例的第二行包含n个整数a1，a2，…，an (1≤ai≤2000)，其中ai是a的第I个元素 保证所有测试用例的n之和不超过2000 (∑n≤2000)。
输出
对于每个测试用例，如果能得到一个奇数元素和的数组，输出“YES”(不加引号)，否则为“NO”。
样例输入
5
2
2 3
4
2 2 8 8
3
3 3 3
4
5 5 5 5
4
1 1 1 1样例输出
YES
NO
YES
NO
NO参考程序
2.B:暗箱操作
题目描述
有两个英语菜鸡lzh和xzy，每个人所能解决的问题都不一样，每个学期的英语考试到了，对于每一个英语题目都有一个相应的分数且每道题的相应分数p_i不能小于1，所有题目的分数总和最低的人就获得挂科重修再来一次，作为lzh好朋友的你，为了让lzh的英语考试分数比xzy高，你需要偷偷操控每题的分数p_i,但是如果p_i太大，lzh就会因为作弊被抓住，所以你要做的就是最小化所有英语题目中的最大分数p_i。
输入
第一行包含一个整数n（1<=n<=100）代表英语题目的数量
第二行有n个整数r1,r2 …,rn (0<=ri<=1).ri=1意味着lzh会i-题目,ri=0意味着它不会i- 题目
第三行有n个整数b1,b2, …,bn (0<=bi<=1).bi=1意味着xzy会i-题目,bi=0意味着它不会i- 题目
输出
如果你不能通过任何手段让lzh的分数大于xzy就输出-1 否则输出你在所有项目中修改分数的最大值
样例输入
5
1 1 1 0 0
0 1 1 1 1样例输出
3提示
对于样例来说，你只需要把第一道题的分数改为3，第二道题的分数改为1，第三道题的分数改为3，第四道题的分数改为1，第五题的分数改为1 那么lzh的得分就是3+1+3=7，而xzy的得分是1+3+1+1=6，lzh的分数就比xzy的高了
参考程序
3.C:简简单单A+B
题目描述
给出三个整数 A,B,N； 1<A,B,N<1e9
我们可以进行如下操作
操作 1：让A=A+B；
操作 2：让B=A+B；
问最少需要多少次操作 可以使max（A，B）严格大于N max（a,b)为（A,B中较大的那个）
输入
第一行一个整数T 代表测试组数
下面T行 1<T<100
每行三个整数 A,B,N 意义如题所示 1<A,B,N<1e9
输出
输出T行
每行一个整数 代表所需要的最少操作
样例输入
2
1 2 3
5 4 100样例输出
2
7参考程序
4.D:淘淘的暗号
题目描述
淘淘的暗号为一串由n个小写字母组成的字符串b,原文a生成b的方法为a中从左到右将每个长度为2的子串加入到b中，例如a串为’abcd’，那么子串从左到右的顺序为’ab’,’bc’,’cd’，则b为’abbccd’
输入
输入长为n(3<=n<=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;
} 5.E:淘淘的序列
题目描述
对于一个长为n的数字序列中的每个数字ai，若当i为奇数时ai也为奇数，则称它为淘淘序列。同时，淘淘每次可以将序列中两个任意数字交换位置，求出淘淘需要多少次交换能将一个序列变为淘淘序列
注意 ：i从0开始
输入
第一行输入一个整数n(1<=n<=100000)，第二行输入n个整数ai(0<=i<=n-1)
输出
输出一个整数，代表淘淘最小需要做多少次交换操作能将给定序列变为淘淘序列，若不能变成淘淘序列输出-1
样例输入
4
3 2 7 6样例输出
2参考程序
6.F:打牌
题目描述
sys和llf在打牌，他们觉得现有的玩法太简单，所以他们玩起了摸牌游戏 规则如下
有N张牌 两个人轮流摸牌 每次摸牌的数量只能是2的幂次 比如 1，2，4，8，16 …… 当轮到某人摸牌，此人若无牌可摸，败 llf先手摸牌 他们两人都会采取最优策略去摸牌
输入
第一行一个数T 代表测试组数
下面N行每行一个数N 意义如题所示
输出
输出T行
若先手赢 输出llfnb
否则输出sysnb
样例输入
4
1
3
4
12样例输出
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;
}题解
根据案例不难清楚当牌的数量为3的倍数时，都是先手输，所以可知，该问题被简化成倍数问题，在比赛中这样的规律可能不易发觉，要认真审题