A. Left-handers, Right-handers and Ambidexters
题意: 有 l 个人擅长用左手, 有 r 个人擅长用右手, 有 a 个人可以选择用左手或右手现在需要构建一个含偶数人的队伍, 其中用左手和右手的人数相等, 求队伍人数?
思路: 简单题
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- int main()
- {
- int l, r, a;
- scanf("%d%d%d", &l, &r, &a);
- int Min = min(l, r) + a,Max=max(l,r);
- int ans;
- if (Min <= Max) ans = 2 * Min;
- else ans = 2 * Max + 2*((Min - Max) / 2);
- printf("%d\n", ans);
- return 0;
- }
- View Code
- B. Intercepted Message
题意: 有两条信息, 包含相同的文件 (大小一样排列顺序一样), 每个文件分成若干包按照顺序在网上传送已知每个包的大小, 求文件可能的最大数目?
思路: 从头到尾遍历, 当和相同时数目 + 1
- #include < iostream > #include < cstdio > using namespace std;
- const int maxn = 100010;
- int a[maxn],
- b[maxn];
- int main() {
- int n,
- m;
- scanf("%d%d", &n, &m);
- for (int i = 0; i < n; i++) scanf("%d", a + i);
- for (int i = 0; i < m; i++) scanf("%d", b + i);
- int ans = 0,
- tmpa = 0,
- tmpb = 0,
- i = 0,
- j = 0;
- while (i < n || j < m) {
- if (tmpa == tmpb && tmpa == 0) tmpa += a[i++],
- tmpb += b[j++];
- else {
- if (tmpa < tmpb) tmpa += a[i++];
- else if (tmpb < tmpa) tmpb += b[j++];
- }
- if (tmpa == tmpb) ans++,
- tmpa = tmpb = 0;
- }
- printf("%d\n", ans);
- return 0;
- }
- View Code C.Zebras
题意: 有一个 01 串, 现在问能否分成 k 个子串 (子串中 0 和 1 不一定在原串中连续), 每个子串以 0 作为开始和结尾, 0 和 1 在串中交替给出任意一种可行方案
思路: 用 vector 模拟子串当当前字符为 0 时, 如果有串为 1 结尾, 0 必须放在其后面, 否则可以自成新串的开头; 如果当前为 1, 则只能放在 0 结尾的子串后面
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #include<vector>
- using namespace std;
- const int maxn = 200010;
- char str[maxn];
- int num0=0, num1=0;
- vector<int>List[maxn];
- int main()
- {
- scanf("%s", str + 1);
- int len = strlen(str + 1);
- for (int i = 1; i <= len; i++) if (str[i] == 0) num0++;
- num1 = len - num0;
- if (num1 >= num0 || str[1] == 1||str[len]==1) printf("-1\n");
- else
- {
- int curnum = 0,onenum=0;// 前者表示 List[0]~List[curnum-1] 都是以 0 作为结尾的子串, 后者表示 List[curnum]~List[curnum+onenum-1] 为 1 作为结尾的子串
- for (int i = 1; i <= len; i++)
- {
- if (str[i] == 0)
- {
- List[curnum++].push_back(i);
- if (onenum) onenum--;
- }
- else List[--curnum].push_back(i), onenum++;
- if (curnum < 0) break;
- }
- if (onenum != 0) printf("-1\n");
- else
- {
- printf("%d\n", curnum);
- for (int i = 0; i < curnum; i++)
- {
- int sz = List[i].size();
- printf("%d", sz);
- for (int j=0; j < sz; j++) printf("%d", List[i][j]);
- printf("\n");
- }
- }
- }
- return 0;
- }
- View Code
- D. A Leapfrog in the Array
题意: 有 n 个数, 第 i 个数放在 (i+1)/2 的位置每次选取位置最大的数, 将其挪至其左侧与其最近的空位置, 直至所有数字都在前 n 个位置现在有 q 个询问, 问所有操作过后, 第 qi 个位置是哪个数字?
思路: 手动模拟一边可知, 所有奇数位置不变, 所有偶数位置按照 + bias,bias/2(init:bias=n-index/2) 知道加至 bias 为奇数为止
- #include<iostream>
- #include<cstdio>
- using namespace std;
- typedef long long LL;
- int main()
- {
- LL n;
- int q;
- scanf("%I64d%d", &n, &q);
- for (int i = 1; i <= q; i++)
- {
- LL index;
- scanf("%I64d", &index);
- if (index % 2 == 1) printf("%I64d\n", (index + 1) / 2);
- else
- {
- LL init = n - index / 2;
- while (init % 2 == 0) index += init, init /= 2;
- index = (index + init + 1) / 2;
- printf("%I64d\n", index);
- }
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2521984.html