[编程题]二进制计数-研发
小A刚学了二进制,他十分激动。为了确定他的确掌握了二进制,你给他出了这样一道题目:给定N个非负整数,将这N个数字按照二进制下1的个数分类,二进制下1的个数相同的数字属于同一类。求最后一共有几类数字?
输入描述:
输入的第一行是一个正整数T(0<T<=10),表示样例个数。对于每一个样例,第一行是一个正整数N(0<N<=100),表示有多少个数字。接下来一行是N个由空格分隔的非负整数,大小不超过2^31
– 1。,
输出描述:
对于每一组样例,输出一个正整数,表示输入的数字一共有几类。
输入例子1:
1
5
8 3 5 7 2
输出例子1:
3
#include <bits/stdc++.h>using namespace std;int main() {int t;cin >> t;for (int i = 0; i < t; i++) {int n;cin >> n;set<int> res;for (int j = 0; j < n; j++) {int tmp;cin >> tmp;int count = 0;while (tmp) {tmp = tmp & (tmp - 1);count++;}res.insert(count);}cout << res.size() << endl;}return 0;}
[编程题]水平线-研发
伞屉国是一个以太阳能为主要发电手段的国家,因此他们国家中有着非常多的太阳能基站,链接着的基站会组合成一个发电集群。但是不幸的是伞屉国不时会遭遇滔天的洪水,当洪水淹没基站时,基站只能停止发电,同时被迫断开与相邻基站的链接。你作为伞屉国的洪水观察员,有着这样的任务:在洪水到来时,计算出发电集群被洪水淹没后被拆分成了多少个集群。
由于远古的宇宙战争的原因,伞屉文明是一个二维世界里的文明,所以你可以这样理解发电基站的位置与他们的链接关系:给你一个一维数组a,长度为n,表示了n个基站的位置高度信息。数组的第i个元素a[i]表示第i个基站的海拔高度是a[i],而下标相邻的基站才相邻并且建立链接,即x号基站与x-1号基站、x+1号基站相邻。特别的,1号基站仅与2号相邻,而n号基站仅与n-1号基站相邻。当一场海拔高度为y的洪水到来时,海拔高度小于等于y的基站都会被认为需要停止发电,同时断开与相邻基站的链接。
输入描述:
每个输入数据包含一个测试点。
第一行为一个正整数n,表示发电基站的个数 (0 < n <= 200000)
接下来一行有n个空格隔开的数字,表示n个基站的海拔高度,第i个数字a[i]即为第i个基站的海拔高度,对于任意的i(1<=i<=n),有(0
<= a[i] < 2^31-1)
接下来一行有一个正整数q(0 < q <= 200000),表示接下来有q场洪水
接下来一行有q个整数,第j个整数y[j]表示第j场洪水的海拔为y[j],对于任意的j(1<=j<=n),有(-2^31 < y[j] <
2^31-1)
输出描述:
输出q行,每行一个整数,第j行的整数ans表示在第j场洪水中,发电基站会被分割成ans个集群。标准答案保证最后一个整数后也有换行。
输入例子1:
10
6 12 20 14 15 15 7 19 18 13
6
15 23 19 1 17 24
输出例子1:
2
0
1
1
2
0
40%
需要先把所有数据都读进来,排序后再做比较,然后输出才能100%
#include <bits/stdc++.h>using namespace std;int main() {int n, q;cin >> n;vector<int> tmp;int max = -1;for (int i = 0; i < n; i++) {int a;cin >> a;max = a > max ? a : max;tmp.push_back(a);}cin >> q;for (int i = 0; i < q; i++) {int h;cin >> h;if (h < 0) cout << 1 << endl;else if (max <= h) cout << 0 << endl;else{int count = 0;int pre = -1, now = -1;for (int j = 0; j < n; j++) {if (tmp[j] > h) {if (pre == -1) pre = j, count++;else if (j - pre != 1)count++;pre = j;}}cout << count << endl;}}return 0;}
[编程题]游泳池-研发
小明作为一个游泳池管理员,以玩弄给水管和排水管为乐,也因此产生了很多数学题考验小朋友。
现在小明想把这个行动升级,考验一下程序员,做了一个自动装置来控制给水管和排水管。在开始时,给水管和排水管都是打开状态的,并且游泳池里没有水。在自动装置的作用下,每经过t1分钟,给水管的状态都会改变,即从打开状态变为关闭状态或从关闭状态变为打开状态,而同时每经过t2分钟,排水管的状态也会改变。当给水管打开时,给水管每分钟会向游泳池里注入m1升水;当排水管打开时,排水管每分钟会把游泳池里水排走m2升;当给水管和排水管同时打开时,游泳池的水量变化为每分钟(m1-m2)升。当然泳池的水量不能变为负数,同时泳池也有个最大容量m,水量不能超过m升。那么经过t分钟后,游泳池里有多少升水?
输入描述:
输入第一行为一个正整数T,表示有T组数据。
每组数据的为一行包含六个整数,分别表示m, t, m1, t1, m2, t2。
数据范围:
对于所有数据,满足1<=T<=10, 1<=m<=100000, 1<=t<=86400, 1<=m1,m2<=100,
1<=t1,t2<=10。
输出描述:
对于每一个数据,输出一行,包括一个整数,为在t分钟后游泳池中的水量。
输入例子1:
5
10 2 1 5 2 5
10 2 10 5 2 5
10 2 3 5 2 5
100 100 3 4 4 3
10000 1000 10 5 5 3
输出例子1:
0
10
2
3
2495
#include <bits/stdc++.h>using namespace std;int main() {int T;cin >> T;for (int i = 0; i < T; i++) {int m, t, m1, t1, m2, t2;cin >> m >> t >> m1 >> t1 >> m2 >> t2;int sum = 0;bool m1_flag = true;bool m2_flag = true;for (int j = 0; j < t; j++) {m1_flag = (j / t1) % 2 == 0 ? true : false;m2_flag = (j / t2) % 2 == 0 ? true : false;sum += m1 * (int)m1_flag - m2 * (int)m2_flag;if (sum < 0) sum = 0; if (sum > m) sum = m;}cout << sum << endl;}return 0;}
[编程题]幸运N串-研发
小A很喜欢字母N,他认为连续的N串是他的幸运串。有一天小A看到了一个全部由大写字母组成的字符串,他被允许改变最多2个大写字母(也允许不改变或者只改变1个大写字母),使得字符串中所包含的最长的连续的N串的长度最长。你能帮助他吗?
输入描述:
输入的第一行是一个正整数T(0 < T <= 20),表示有T组测试数据。对于每一个测试数据包含一行大写字符串S(0 < |S| <=
50000,|S|表示字符串长度)。
数据范围:
20%的数据中,字符串长度不超过100;
70%的数据中,字符串长度不超过1000;
100%的数据中,字符串长度不超过50000。
输出描述:
对于每一组测试样例,输出一个整数,表示操作后包含的最长的连续N串的长度。
输入例子1:
3
NNTN
NNNNGGNNNN
NGNNNNGNNNNNNNNSNNNN
输出例子1:
4
10
18
#include <bits/stdc++.h>using namespace std;int main() {int T;cin >> T;for (int i = 0; i < T; i++) {string str;cin >> str;vector<int> res;int max = -1;for (int j = 0; j < str.size(); j++) {if (str[j] != 'N') res.push_back(j);}if (res.size() <= 2) cout << str.size() << endl;else{max = res[2];for (int k = 3; k < res.size(); k++) {max = (res[k] - res[k - 3] - 1) > max ? res[k] - res[k - 3] - 1 : max;}max = str.size() - res[res.size() - 3] - 1 > max ? str.size() - res[res.size() - 3] - 1 : max;cout << max << endl;}}return 0;}