网站建设与管理就业前景,高级网站开发工程师 证书,网站建设深圳,西安网站维护招聘A题#xff1a;Question Marks
题目#xff1a;
Tim正在做一个由 4n 个问题组成的测试#xff0c;每个问题都有 4 个选项#xff1a;“A”、“B”、“C”和“D”。对于每个选项#xff0c;有 n 个正确答案对应于该选项#xff0c;这意味着有 n 个问题的答案为“A”。 n…A题Question Marks
题目
Tim正在做一个由 4n 个问题组成的测试每个问题都有 4 个选项“A”、“B”、“C”和“D”。对于每个选项有 n 个正确答案对应于该选项这意味着有 n 个问题的答案为“A”。 n 个答案为“B”的问题 n 个答案为“C”的问题以及 n 个回答为“D”的问题。每道题蒂姆都把答案写在答题纸上。如果他想不出答案他就会留下一个问号。为了这个问题。您将获得 4n 个字符的答题卡。蒂姆最多能得到多少个正确答案 输入
第一行包含单个整数 t 1 t 1000 —测试用例的数量。
每个测试用例的第一行包含一个整数 n 1 n 100 。
每个测试用例的第二行包含 4n 个字符 si 属于{A, B, C, D, ?} 的字符串 s —Tim对问题的回答。
输出
对于每个测试用例打印一个整数—Tim可以达到的最大分数。
样例 注意
在第一个测试用例中每个答案“A”、“B”、“C”和“D”只有一个问题所以蒂姆有可能所有的答案都是正确的。在第二个测试案例中只有两个正确答案A这使得他在任何情况下都能得到2 分。在第三个测试用例中Tim最多可以得到 2 个选项A的正确答案和 2 个选项B的正确答案。例如如果答案是AACCBBDD他将得到 4 分。在第四个测试案例中他拒绝回答任何问题这使他获得 0 分。 解题思路
问题问的是他的最大得分例如第一个样例他的答案为ABCD,那么我们默认正确的答案为ABCD,所以能得到4分这种确认正确答案要建立在条件之上确保每个选项出现的次数是一样的当为5个问题时必然有四个答案为A,B,C,D还剩一个答案那就可以是任意一个因为是要得最大的分那么剩余那一个一定是答案出现两次的选项。当出现‘ ’时可视为他空着这个题没写答案必然不得分。 AC代码
#includeiostream
using namespace std;
const int N500;
int t,n;
char ch[N];
int main(){cint;while(t--){cinn;cinch;int suma0,sumb0,sumc0,sumd0;//记录四个选项出现次数for(int i0;i4*n;i){if(ch[i]A)suma;else if(ch[i]B)sumb;else if(ch[i]C)sumc;else if(ch[i]D)sumd;}//因为4*n个问题每个选项最多出现n次if(suman)suman;if(sumbn)sumbn;if(sumcn)sumcn;if(sumdn)sumdn;coutsumasumbsumcsumdendl;}return 0;
} B题Parity and Sum
题目
给定一个由n个正整数组成的数组 a 。
在一个操作中您可以选择任意一对索引 (i, j) 使 ai 和 aj 具有不同的奇偶校验然后用它们的和替换较小的一个。更正式地说
-如果ai aj 请将 ai 替换为 ai aj
-否则将 aj 替换为 ai aj 。
找出使数组的所有元素具有相同奇偶性所需的最小操作数。 输入
第一行包含单个整数 t ( 1 t 10^4 )—测试用例的数量。
每个测试用例的第一行包含一个整数 n ( 1 n 2*10^5 )。
第二行包含 n 整数 a1, a2, ..., an ( 1 ai 10^9 )—数组 a 的元素。
保证所有测试用例的 n 之和不超过 2*10^5 。
输出
对于每个测试用例输出一个整数——所需的最小操作数。
样例 注意
在第一个测试用例中所有整数都具有相同的奇偶性。因此不需要任何操作。
在第三个测试用例中我们可以执行两个操作 (1, 2) 和 (1, 3) 。数组 a 转换如下 a [2, 3, 4] - [5, 3, 4] - [5, 3, 9] 。
在第四个测试用例中最优操作序列的示例是 (1, 2) 、 (1, 3) 、 (1, 4) 和 (1, 4) 。数组 a 转换如下 a [3, 2, 2, 8] - [3, 5, 2, 8] - [3, 5, 5,8] - [11, 5, 5, 8] - [11, 5, 5, 19] 。 解题思路 通过上面图片我们知道了奇偶两两相加的特点由此我们可以得出只有oddevenodd是可行的我们是这个式子中较小的为偶数偶数与奇数相加为奇数这就把偶数变为奇数了当偶数奇数时通过这样的操作可以把这个奇数的值变得更大使得前面的条件偶数奇数变为偶数奇数,那么这样我们又可以通过操作一把偶数变为奇数。
那么我们的操作顺序是什么先哪个奇数跟哪个偶数先操作由题意知我们要最大程度满足偶数奇数这个条件因为只有这个条件操作才是对目标序列有贡献的。这样我们的奇数使其最大偶数使其最小既能把偶数变为奇数的情况下奇数的值也可能得到了更新。使偶数按照递增的顺序是最优的例如a{2348}开始奇数最大为3偶数递增为{248}第一次把2变为5此时奇数最大值为5第二次5与4操作变为9奇数最大值又得到更新变为9第三次操作9与8变为17结束。这样最优没有奇数偶数的情况。那么如果有奇数偶数的情况我们就让此时最大的奇数与最大的偶数进行一次操作这样得到的奇数足够大可以满足所有的偶数了例如a{126}开始最大奇数一个也不满足先让1与6进行一次操作1变为7这样7可以与2也可以与6进行操作了。如果1先于2进行操作1变为3在进行一次2变为556,最大奇数又小于偶数这样无非多一次操作。 AC代码
#includeiostream
#includequeue
using namespace std;
typedef long long ll;
const int N2e55;
ll a[N];//原数组
ll n,t;
priority_queuell,vectorll,greaterll q;//升序优先队列偶数
int main(){cint;while(t--){cinn;ll maxodd0,maxeven0;//最大奇数最大偶数ll sum0;//操作次数while(!q.empty()){//多次输入清空队列q.pop();}for(int i1;in;i){cina[i];if(a[i]%21){maxoddmax(maxodd,a[i]);//求奇数最大值}else{q.push(a[i]);maxevenmax(maxeven,a[i]);//求偶数最大值}}if(maxodd0||q.empty()){//都为奇数或偶数cout0endl;}else{ll lenq.size();ll sum10;//队内偶数操作次数while(1){if(q.top()maxodd){maxoddmaxoddmaxeven;}else{maxoddmaxoddq.top();q.pop();sum1;}sum;if(sum1len)break;}coutsumendl;}}return 0;
} C题Light Switches
题目
有一个由 n 个房间组成的公寓每个房间的灯最初都是关闭的。为了控制这些房间的灯光公寓的主人决定在房间里安装芯片这样每个房间只有一个芯片。并且在不同的时间安装芯片。具体来说这些时间由数组 a1, a2,..., an 表示其中 ai 是时间(以分钟为单位)芯片安装在第 i 个房间。一旦安装了芯片它就会每隔 k 分钟改变一次房间的灯光状态—它会打开灯光 k 分钟。然后在接下来的 k 分钟内将其关闭然后在接下来的 k 分钟内将其重新打开依此类推。换句话说芯片在分钟 ai 、ai k 、ai 2k 、ai 3k 改变灯的状态公寓里所有房间的灯最早什么时候打开 输入
第一行包含单个整数 t ( 1 t 10^4 )—测试用例的数量。
每个测试用例的第一行包含两个整数 n 和 k ( 1 k n 2*10^5 )—公寓中的房间数和芯片的周期。
第二行包含 n 不同的整数 a1, a2, ..., an ( 1 ai 10^9 )—安装芯片的时刻。
保证所有测试用例的 n 之和不超过 2*10^5 。
输出
对于每个测试用例打印一个整数—问题的答案(以分钟为单位)。如果不存在所有房间的灯都打开的时刻则改为打印 -1。
样例 注意
在第一个测试案例中所有的灯都会在 5 分钟内打开而不会被芯片关闭。答案是 5 。在第二个测试案例中由于第一个指示灯将在 2, 3, 4, 8, 9, 10, 14, ... 分钟时亮起。同时第 4 个指示灯将在 5, 6, 7, 11, 12, 13, 17, ... 分钟亮起。这两个序列没有任何相同的数字因此它们永远不会同时出现。在第三个测试案例中可以看到第一个灯和第二个灯将在 6 和 7 分钟关闭。但芯片将在 9 和 10 分钟时重新打开它们。第 3 和第 4 个灯也将在第 10 分钟亮起因此答案是 10 。 解题思路
灯亮的时刻
x→xk−1x2k→x3k−1x4k→x5k−1…
列表中的每个段(除了第一个)实际上是它前面的段移动了 2k 分钟。这也意味着如果我们除以 2k 并在每个线段的两端取余数则所有这些线段都变得相等。因此我们将第 i 个芯片的片段称为 (ai mod 2k,(aik−1) mod 2k) 。因此我们的问题被简化为找到最小整数 s 使得 maxa≤ s 出现在每个部分中 s mod 2k 属于其中的每个段之中 AC代码
#includebits/stdc.h
using namespace std;
int a[200001];
int main() {int t;cint;while(t--){int n,k;cin n k;for(int i 1; i n; i)cina[i];sort(a1,an1);for(int i1; in; i)a[i](a[n]k-1-a[i])/(k*2)*k*2;sort(a1,an1);if(a[n]-a[1]1k) cout-1endl;else couta[n]endl;}return 0;
}
