Kickstart 2018
2018 Around A¶
1. Even Digits¶
8pts, 15pts
有一个计算器，上面有
+和-两个运算符号，给一个数，最少按多少次后可以将各位都变成偶数4 42 #1: 0 11 #2: 3 1 #3: 1 2018 #4: 2
思路
从左到右找到第一个不是偶数的数字k，然后离它最近的就是偶数有两种，一是 (k+1)000...0，二是(k-1)888...8，计算这两个哪个更近即可
例外在于如果k是9，那么要通过加让所有位数都是偶数，需要将k-1先变奇数再变偶，大于将k减为0的步骤数，所以直接计算减到(k-1)888...8的步数即可
#include <iostream>
using namespace std;
int T;
bool isEven(char c) {
return c == '0' || c == '2' || c == '4' || c == '6' || c == '8';
}
int main() {
cin >> T;
int caseRank = 0;
for (int caseRank = 1; caseRank <= T; caseRank ++) {
string N;
cin >> N;
int rank = 0;
while (rank < N.size()) {
if (!isEven(N[rank])) break;
rank ++;
}
if (rank == N.size()) {
cout << "Case #" << caseRank << ": 0\n";
continue;
}
string s1 = "0";
char a = N[rank] + 1;
if (a < '9') {
s1 = string(N.size() - rank, '0');
s1[0] = a;
}
string s2 = string(N.size() - rank, '0');
s2[0] = N[rank] - 1;
for (int j = 1; j < s2.size(); j ++) s2[j] = '8';
long long n = stoll(N.substr(rank));
long long n1 = stoll(s1), n2 = stoll(s2);
long long result = n1 > 0 ? min(n1 - n, n - n2) : n - n2;
cout << "Case #" << caseRank << ": " << result << '\n';
}
}
2. Lucky Dip¶
10pts, 19pts
一个包里有
N件货物，第i件货物价值为Vi，从中抽取一件，有K次放回再抽的机会，求一个最佳策略来获得最大价值，返回最大价值期望输入如下，输入
N和K，然后输入N个价值5 4 0 1 2 3 4 Case #1: 2.500000 3 1 1 10 1 Case #2: 6.000000 3 15 80000 80000 80000 Case #3: 80000.000000 1 1 10 Case #4: 10.000000 5 3 16 11 7 4 1 Case #5: 12.358400
思路
dp即可
- k=0，期望就是所有货物价值的平均值
- k=i时，从价值最大货物开始，抽到价值大于
k=i-1时期望值的货物时留下，小于时放回去
这样连续更新K轮后，得到的即是期望值
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
int T;
int main() {
cin >> T;
for (int caseRank = 1; caseRank <= T; caseRank ++) {
int N, K;
cin >> N >> K;
vector<unsigned int> items;
for (int i = 0; i < N; i ++) {
unsigned int v;
cin >> v;
items.push_back(v);
}
sort(items.begin(), items.end(), std::greater<unsigned int>());
double avg = 0;
for (int i = 0; i <= K; i ++) {
double temp = 0;
for (int j = 0; j < N; j ++) {
unsigned int value = items[j];
if (value > avg) temp += value;
else {
temp += avg * (N - j);
break;
}
}
avg = temp / N;
}
printf("Case #%d: %.6f\n", caseRank, avg);
}
}
3. Scrambled Words¶
18pts, 30pts
有一个词典，含L个单词，之后有一个N位长的字符串，求字符串中出现单词的次数，这里单词是除过首字母和尾字母，中间可以乱序，多次出现也只累积一次
第一行是T，指cases数量，第二行为L，之后是词典，再之后是用于生成字符串的数据
First we define ord© as the decimal value of a character c and char(n) as the character value of a decimal n. For example, ord('a') = 97 and char(97) = 'a'. You can refer to ASCII table for other conversions.
Now, define x1 = ord(S1), x2 = ord(S2). Then, use the recurrence below to generate xi for i = 3 to N: xi = ( A * xi-1 + B * xi-2 + C ) modulo D. We define Si = char(97 + ( xi modulo 26 )), for all i = 3 to N.
Input
1
5
axpaj apxaj dnrbt pjxdn abd
a a 50 1 1 1 30
这里生成字符串上抄错式子，一直WA调不好，应该仔细一些
原来把vector直接转成string来作为unordered_map的键，但会TIL，改成哈希成unsigned long long的键值，可以AC，不知道是不是用整数作为键值比字符串更快
然后按各长度来建立unordered_map，对单词各字符出现次数进行统计，因为多个单词会重复，值是重复次数
#include <cstdio>
#include <string>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <set>
using namespace std;
const int SEED = 13331;
unsigned long long getHash(char start, char end, vector<int>& v) {
unsigned long long ret = start*SEED + end;
for (int i = 0; i < 26; i++) {
ret = ret*SEED + v[i];
}
return ret;
}
unordered_map<int, unordered_map<unsigned long long, int>> dict;
vector<int> lengths;
int main() {
int T;
cin >> T;
for (int caseRank = 1; caseRank <= T; caseRank ++) {
dict.clear();
lengths.clear();
int L;
cin >> L;
for (int i = 0; i < L; i ++) {
string str;
cin >> str;
vector<int> cnt(26, 0);
for (char c : str) cnt[c - 'a'] ++;
int length = str.size();
if (!dict.count(length)) lengths.push_back(length);
dict[length][getHash(str[0], str[length - 1], cnt)] ++;
}
string S1, S2;
int N;
long long A, B, C, D;
cin >> S1 >> S2 >> N >> A >> B >> C >> D;
string sentence = S1 + S2;
long long v1 = S1[0], v2 = S2[0];
for (int i = 3; i <= N; i ++) {
int temp = v2;
long long x = (A * v2 + B * v1 + C) % D;
char c = 'a' + (x % 26);
v1 = v2; v2 = x;
sentence += c;
}
int result = 0;
for (int length : lengths) {
if (length > N) continue;
vector<int> cnt(26, 0);
for (int i = 0; i < length - 1; i ++) cnt[sentence[i] - 'a'] ++;
int head = 0, tail = length - 1;
while (tail < N) {
cnt[sentence[tail] - 'a'] ++;
unsigned long long hashKey = getHash(sentence[head], sentence[tail], cnt);
auto it = dict[length].find(hashKey);
if (it != dict[length].end()) {
result += it->second;
dict[length].erase(it);
}
cnt[sentence[head] - 'a'] --;
head ++; tail ++;
}
if (result == L) break;
}
printf("Case #%d: %d\n", caseRank, result);
}
}
2018 Round B¶
1. Not Nine¶
7pts, 13pts
T个cases，给1\le F\le L\le 10^{18}，求从F到L之间不被9整数也不包含9的整数个数，保证F和L都满足此条件
小数据集上限为10^6，大数据集上限为10^{18}
思路其实很简单，实现统计从1到N满足该条件的数，做减法即可，从最高位开始从左向右累加，因为第i位肯定不是9，之后有length-i-1位，这些数字可以随意填非9的数，所以可能性就是9^{length-i-1}，然后最后一位有8种取值范围
是8位的原因是末尾元素从0取到9，对应整个数模9的结果是从0到9，所以一定能是0-8都有，同时一个结果重复两遍，如果重复的不是0，同时需要除去末尾的9，如果重复的是0，那么一定是个位取0和9时模为0，也是去除两个，所以是8
注意，用double来存数，存在精度不足的问题，这里必须用long long
#include <iostream>
#include <cstdio>
using namespace std;
int T;
unsigned long long table[20];
unsigned long long count(string s) {
unsigned long long cnt = 0;
for (int i = 0; i < s.size() - 1; i ++)
cnt += (unsigned long long)(s[i] - '0') * table[s.size() - 2 - i] * 8;
long long n = stoll(s);
long long bgn = n - n % 10;
for (long long num = n - n % 10; num <= n; num ++)
if (num % 9 != 0) cnt ++;
return cnt;
}
int main() {
cin >> T;
unsigned long long pw = 1;
for (int i = 0; i < 20; i ++) {
table[i] = pw;
pw *= 9;
}
for (int caseRank = 1; caseRank <= T; caseRank ++) {
string s1, s2;
cin >> s1 >> s2;
unsigned long long result = count(s2) - count(s1) + 1;
printf("Case #%d: %llu\n", caseRank, result);
}
}
2. Sherlock and the Bit Strings¶
11pts, 26pts
长为
N的只包含0和1的字符串，需要满足K个限制条件，每个限制条件以[Ai, Bi, Ci]的形式给出，表示从Ai到Bi，恰好包含Ci个1input
2 3 1 2 2 2 1 4 3 1 1 2 1 2 3 1 3 4 1output
Case #1: 011 Case #2: 0101
- 1\le N \le 100
- 1\le K \le 100
- 1\le P \le 10^{18}
- 1 \le A_i \le B_i \le N
- B_i - A_i \le 15
- 0 \le C_i \le N
核心思路是因为B_i-A_i \le 15，所以对每个限制条件，只考虑包括这位在内的16个字母即可，2^{16}=65536，是可以接受的遍历长度，加上前缀和相减来求1的个数，时间复杂度和空间复杂度都可以接受
先用动归求出在某个前缀下，满足要求的字符串有K个，然后找到刚好大于等于P的那个前缀，继续向后找即可
- 一定要注意数据范围，以及溢出处理，这里dp过程中可能会远大于
P，因为其实是一个指数增长的过程，所以在超过P的上限后，只设置为上限即可 - 将
iostream改为scanf，去掉memset，会从TLE变为AC，以后OJ都用scanf来做
#include <cstdio>
#include <vector>
#include <string>
using namespace std;
int T;
unsigned long long dp[66000][101];
const long long MAXP = 1000000000000000000;
int num1s[66000][17];
string tobits(int i) {
string s = "";
for (int j = 0; j < 16; j ++) {
s += ('0' + ((i >> (15 - j)) & 1));
}
return s;
}
int main() {
scanf("%d", &T);
for (int i = 0; i < (1 << 16); i ++) {
int num = 0;
for (int j = 16; j >= 0; j --) {
if ((i >> j) & 1) num ++;
num1s[i][16 - j] = num;
}
}
for (int caseRank = 1; caseRank <= T; caseRank ++) {
int N, K, A, B, C;
long long P;
scanf("%d%d%lld", &N, &K, &P);
vector<vector<pair<int, int>>> constraints(101, vector<pair<int, int>>());
for (int i = 0; i < K; i ++) {
scanf("%d%d%d", &A, &B, &C);
constraints[B].push_back({A, C});
}
for (int i = N; i >= 1; i --) {
for (int j = 0; j < (1 << min(16, i)); j ++) {
bool succeed = true;
for (auto p : constraints[i]) {
int num = num1s[j][16] - num1s[j][16 - i - 1 + p.first];
if (num != p.second) {
succeed = false;
dp[j][i] = 0;
break;
}
}
if (!succeed) continue;
if (i == N) dp[j][i] = 1;
else {
int next = (j << 1);
next &= ((1 << 16) - 1);
dp[j][i] = dp[next][i + 1] + dp[next + 1][i + 1];
if (dp[j][i] > MAXP) dp[j][i] = MAXP;
}
}
}
string s = "";
long long prefix = 0;
long long rank = P;
for (int i = 1; i <= N; i ++) {
int limit = 1 << min(16, i);
for (int j = prefix; j < limit; j ++) {
if (dp[j][i] < rank) {
rank -= dp[j][i];
continue;
}
s += ('0' + (j & 1));
prefix = j;
prefix <<= 1;
prefix &= ((1 << 16) - 1);
break;
}
}
printf("Case #%d: %s\n", caseRank, s.c_str());
}
}
2018 Round C¶
1. Planet Distance¶
10pts, 15pts
并查集
一共N个星球，N条边，而且所有星球都互相可达，就是一棵树加了一条边，那这条边将两个本来就互相可达的点连在了一起，用并查集可以找到这条边
这时从u开始bfs来找这个环的所有点，直到v，bfs复杂度是O(N+E)，这里会很快结束
之后再bfs来设定距离即可
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int T, N;
int planets[1001];
int nums[1001];
int find(int num) {
while (planets[num] != num) num = planets[num];
return num;
}
void bfs(const vector<vector<int>>& edges, int begin, int end, deque<int>& que) {
vector<int> visited(N + 1, -1);
visited[begin] = begin;
deque<int> q = { begin };
while (!q.empty()) {
int u = q.front();
q.pop_front();
for (int v : edges.at(u)) {
if (visited[v] != -1) continue;
visited[v] = u;
q.push_back(v);
if (v == end) break;
}
if (visited[end] != -1) break;
}
int n = end;
while (n != begin) {
que.push_back(n);
nums[n] = 0;
n = visited[n];
}
que.push_back(begin);
nums[begin] = 0;
}
int main() {
scanf("%d", &T);
for (int caseRank = 1; caseRank <= T; caseRank ++) {
scanf("%d", &N);
memset(nums, -1, sizeof(nums));
for (int i = 1; i <= N; i ++) planets[i] = i;
vector<vector<int>> edges(N + 1, vector<int>());
deque<int> q;
for (int i = 0; i < N; i ++) {
int x, y;
scanf("%d%d", &x, &y);
if (find(x) == find(y)) {
vector<int> visited(N + 1, -1);
bfs(edges, x, y, q);
}
edges[x].push_back(y);
edges[y].push_back(x);
planets[find(x)] = find(y);
}
while (q.size() > 0) {
int node = q.front();
for (int v : edges[node]) {
if (nums[v] == -1) {
nums[v] = nums[node] + 1;
q.push_back(v);
}
}
q.pop_front();
}
printf("Case #%d:", caseRank);
for (int i = 1; i <= N; i ++) printf(" %d", nums[i]);
printf("\n");
}
}
拓扑排序
这里的思路是把图看成一个环，然后伸出去若干树枝，那么把所有度为1的点排除后，剩下的就是这个环
然后同样执行bfs设定距离即可
#include <iostream>
#include <vector>
#include <queue>
#define MAX_N 1001
using namespace std;
int main() {
ios::sync_with_stdio(false);
int tcase;
cin >> tcase;
for(int tc = 1; tc <= tcase; tc++) {
int N;
cin >> N;
// Constructs the graph.
vector<int> G[MAX_N];
for(int i = 0; i < N; i++) {
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
// Computes the degree for each node.
queue<int> q;
vector<int> degree(N + 1);
for(int i = 1; i <= N; i++) {
degree[i] = G[i].size();
if (G[i].size() == 1) {
q.push(i);
}
}
// Topological sort.
vector<int> dis(N + 1);
while(!q.empty()) {
int node = q.front();
q.pop();
dis[node] = -1;
for(int i = 0; i < G[node].size(); i++) {
int v = G[node][i];
degree[v]--;
if (degree[v] == 1) {
q.push(v);
}
}
}
// Adds in nodes in the cycle.
for(int i = 1; i <= N; i++) {
if (dis[i] == 0) {
q.push(i);
}
}
// BFS to compute the distances.
while(!q.empty()) {
int node = q.front();
q.pop();
for(int i = 0; i < G[node].size(); i++) {
int v = G[node][i];
if (dis[v] == -1) {
dis[v] = dis[node] + 1;
q.push(v);
}
}
}
cout << "Case #" << tc << ": ";
for(int i = 1; i <= N; i++) {
cout << dis[i] << " ";
}
cout << endl;
}
return 0;
}
2. Fairies and Witches¶
15pts, 21pts
N个点，其中若干点之间会有边相连，选其中若干不相连的边，构成一个凸多边形，求所有方案数
输入一个N，之后是一个N*N的对称矩阵，表明连接一些点的边，要求输出方案个数
N范围是[6, 15]
思路
判断若干边能否构成凸多边形，准则是所有边之和是否大于两倍的最长边
接下来就是罗列出所有的可能性，依次进行检查，这里其实可以直接用递归来做，关键是对问题的复杂度有清晰的判断
因为边不能相邻，所以其实是选取不同的顶点对，然后构成多边形，所以一个方案即是偶数个节点的组合，在给出N个偶数节点后，不同组合对数可以这样来求，从最小点开始选取，第一对有N-1中可能，接着再选剩下的最小点，然后有N-3中可能，因此一共是f(N)=(N-1)*(N-3)*...*1种可能
对于N，罗列所有可能性就是从0罗列所有偶数，共\sum f(m)\times C_N^m，对15来说，也只有10349536种可能，每种可能用递归来做，最多会递归N次，总可能是1.5 \times 10^8量级，可以短时间内完成
#include <cstdio>
#include <vector>
using namespace std;
int L[16][16];
int N, T;
bool isGoodPolygon(const vector<int>& edges) {
if(edges.size() < 3) return false;
int tot = 0;
int mx = 0;
for(int i = 0; i < edges.size(); i++) {
tot += edges[i];
mx = max(mx, edges[i]);
}
return tot - mx > mx;
}
int bit(int mask, int i) {
return (mask >> i) & 1;
}
int solve(int mask, vector<int>& edges) {
int res = 0;
if(mask + 1 == (1 << N)) {
res = isGoodPolygon(edges);
return res;
}
for(int i = 0; i < N; i++)
if(!bit(mask, i)) {
res += solve(mask | (1 << i), edges);
for(int j = i + 1; j < N; j++) {
if(!bit(mask, j) && L[i][j]) {
edges.push_back(L[i][j]);
res += solve(mask | (1 << i) | (1 << j), edges);
edges.pop_back();
}
}
break;
}
return res;
}
int main() {
scanf("%d", &T);
for (int caseRank = 1; caseRank <= T; caseRank ++) {
scanf("%d", &N);
for (int i = 0; i < N; i ++)
for (int j = 0; j < N; j ++)
scanf("%d", &L[i][j]);
vector<int> edges;
int res = solve(0, edges);
printf("Case #%d: %d\n", caseRank, res);
}
}
3. Kickstart Alarm¶
13pts, 26pts
#include <cstdio>
using namespace std;
int T;
long long K, N, x, y, C, D, E1, E2, F;
long long nums[1000010];
const int MAX = 1000000007;
long long pow(long long num, long long p) {
if (num == 1 || num == 0) return 1;
long long result = 1;
while (p) {
if (p & 1) result = (result * num) % MAX;
num = (num * num) % MAX;
p >>= 1;
}
return result;
}
int main() {
scanf("%d", &T);
for (int caseRank = 1; caseRank <= T; caseRank ++) {
scanf("%lld%lld%lld%lld%lld%lld%lld%lld%lld", &N, &K, &x, &y, &C, &D, &E1, &E2, &F);
nums[1] = (x + y) % F;
for (int i = 2; i <= N; i ++) {
long long newx = (x * C + y * D + E1) % F;
long long newy = (x * D + y * C + E2) % F;
nums[i] = (newx + newy) % F;
x = newx; y = newy;
}
long long prefixSum = 0;
long long result = 0;
for (int i = 1; i <= N; i ++) {
long long fct = 0;
if (i == 1) prefixSum += K;
else prefixSum += i * (pow(i, K) - 1) % MAX * pow(i - 1, MAX - 2) % MAX;
prefixSum %= MAX;
long long temp = prefixSum * (N - i + 1) % MAX;
result += (temp * nums[i] % MAX);
result %= MAX;
}
printf("Case #%d: %lld\n", caseRank, result);
}
}
2018 Round D¶
1. Candies¶
10pts, 15pts
有
N个糖果，每个糖果甜度为S，Supervin只能吃连续的糖果，并且最多只能吃O颗甜度为奇数的糖果，吃到的糖果甜度和要尽量大，但不能大于D，求所能吃到满足要求的最大甜度和第一行是T，表示T个testcases，每个testcase第一行是
N, O, D，第二行是X1, X2, A, B, C, M, L，用于迭代推导出所有甜度，公式如下X_i = (A \times X_{i - 1} + B \times X_{i - 2} + C) \% M, for i = 3 to N.
S_i = X_i + L
例子如下
输出5 6 1 1000000000000000 1 1 1 1 0 100 0 (1, 1, 2, 3, 5, 8) 6 1 -100 1 1 1 1 0 100 0 10 1 8 4 3 4 1 5 20 -10 (-6, -7, -9, 2, 4, 3, 1, -8, -6, -7) 10 2 8 4 3 4 1 5 20 -10 10 1 8 4 3 4 1 5 20 -19 (-15, -16, -18, -7, -5, -6, -8, -17, -15, -16)Case #1: 13 Case #2: IMPOSSIBLE Case #3: 7 Case #4: 8 Case #5: -5IMPOSSIBLE表示没有任何满足要求的糖果数据范围
- 1 ≤ T ≤ 100
- Time limit: 40 seconds per test set.
- Memory limit: 1 GB.
- 2 ≤ N ≤ 5 × 10^5
- 0 ≤ O ≤ N
- -10^{15} ≤ D ≤ 10^{15}
- 0 ≤ X_1, X_2, A, B, C ≤ 10^9
- 1 ≤ M ≤ 10^9
- Small dataset (Test set 1 - Visible) L = 0.
- Large dataset (Test set 2 - Hidden) -5 × 10^8 ≤ L ≤ 0
思路
首先可以想到用滑动窗口来保证最多O个奇数出现，然后对窗口做统计，但因为甜度会有负数，所以要计算出最大甜度，窗口还要向前滑动，对N个位置都计算最大值，复杂度是O(N^2)，不可行
可以在滑动窗口基础上，用平衡二叉树(例如multi_set)来计算每个范围的最大值，由此即可得到解
具体来说，左指针从1到N，右指针指向包含O个奇数甜度的最大范围，即右指针再向右一格就不满足该要求，超出N或者有O+1个奇数
同时，记录甜度数组前缀和S，则从L到R的甜度和就是S[R]-S[L-1]，维护二叉树，使其中元素为左指针到右指针的所有前缀和，然后查询不大于D+S[L-1]的最大值，即得到这个区间内最接近D的甜度，一共N个区间，维护和查询二叉树都是logN，总复杂度是NlogN
这里根据10^5的数据范围就该知道是用NlogN的算法，然后就该向二叉树/堆等方向去思考，加上容易想到的滑动窗口，将问题划分为N个子问题，要注意思考方式
代码注意
multi_set默认是从小到大，lower_bound(i)返回的是大于等于i的数，这里应该用
multi_set<long long, greater<long long>> s;
这样lower_bound返回的是小于等于的数
负奇数模2是-1，这里直接用num&1来判断是不是奇数即可
要特别注意双指针的滑动过程写法，这里写错导致TLE，换了种写法才过
#include <iostream>
#include <set>
using namespace std;
int T, N, O, X1, X2, A, B, C, M, L;
long long D;
long long X[500010]; // sweetness = X + L
long long XSum[500010];
int main() {
cin >> T;
for (int caseRank = 1; caseRank <= T; caseRank ++) {
cin >> N >> O >> D;
cin >> X[1] >> X[2] >> A >> B >> C >> M >> L;
for (int i = 3; i <= N; i ++)
X[i] = ((long long)A * X[i-1] + (long long)B * X[i-2] + C) % M;
XSum[0] = 0;
for (int i = 1; i <= N; i ++) {
X[i] += L;
XSum[i] = X[i] + XSum[i - 1];
}
int R = 1, oddSum = 0;
multiset<long long, greater<long long>> s;
long long ans = 0;
bool first = true;
for (int i = 1; i <= N; i ++) {
while (R <= N && oddSum + (X[R] & 1) <= O) {
s.insert(XSum[R]);
oddSum += (X[R ++] & 1);
}
if (R <= i) R = i + 1;
else {
multiset<long long>::iterator it = s.lower_bound(D + XSum[i-1]);
if (it != s.end()) {
if (first || *it - XSum[i-1] > ans)
ans = *it - XSum[i-1];
first = false;
}
s.erase(s.find(XSum[i]));
oddSum -= (X[i] & 1);
}
}
cout << "Case #" << caseRank << ": ";
if (first) cout << "IMPOSSIBLE\n";
else cout << ans << '\n';
}
}
2018 Round E¶
1. Yogurt¶
10pts, 10pts
Lucy很喜欢喝酸奶，每天可以喝
K盒酸奶，现在他买了N盒牛奶，每盒牛奶会有一个保质期，第i盒酸奶在A_i天内可以喝，从第0天开始算，到第A_i天不能喝，求他能喝到的最多盒数输入
T个case，每个case先输入N和K，然后输入A_i数据，输出最多盒数input
output4 2 1 1 1 5 1 3 2 3 2 3 2 2 1 1 6 2 1 1 1 7 7 7Case #1: 1 Case #2: 3 Case #3: 2 Case #4: 5
思路
可以对保质期进行排序，然后从头每次扫K盒，如果过期则跳过即可，复杂度是NlogN
不过可以在O(N)时间内求解，用cups[i]存储最晚在i天喝的酸奶盒数，这里注意因为一共有N盒酸奶，所以保质期超过N天的酸奶最晚会在第N-1天喝掉
然后从第N-1天起，将每天超过K的酸奶向前累加，同时记录可以喝掉的酸奶盒数，即可得到答案
#include <iostream>
#include <cstring>
using namespace std;
int T, K, N;
int cups[5010];
int main() {
cin >> T;
for (int caseRank = 1; caseRank <= T; caseRank ++) {
memset(cups, 0, sizeof(int) * 5010);
cin >> N >> K;
for (int i = 1; i <= N; i ++) {
int A; cin >> A;
cups[min(N, A) - 1] ++;
}
int result = 0;
for (int i = N - 1; i >= 0; i --) {
if (cups[i] > K && i > 0) cups[i - 1] += cups[i] - K;
result += min(K, cups[i]);
}
cout << "Case #" << caseRank << ": " << result << '\n';
}
}
2. Milk Tea¶
10pts, 10pts
奶茶有
P种配料，N人喝奶茶，每个人有不同要求，用P位的01串表示该要求，给所有人买同一种奶茶，每个人一个要求不满足会抱怨一次，求一种买的方案，使所有人抱怨次数最少。同时商店有M种搭配是不卖的input，第一行是
T个cases，接下来N行表示每个人要求，接下来M行表示禁止的搭配2 3 1 4 1100 1010 0000 1000 2 4 4 1111 1111 1111 0111 1011 1101output
Case #1: 4 Case #2: 2数据范围
- 1 ≤ N ≤ 100
- 1 ≤ M ≤ min(100, 2^P - 1)
- 1 ≤ P ≤ 100
思路
从第一种配料开始枚举所有搭配，因为最多禁止100种搭配，保存抱怨次数最小的101个搭配方式即可
#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>
#include <cstring>
using namespace std;
int T, N, M, P;
int main() {
cin >> T;
for (int caseRank = 1; caseRank <= T; caseRank ++) {
cin >> N >> M >> P;
vector<int> nums(110, 0);
for (int i = 0; i < N; i ++) {
string s;
cin >> s;
for (int j = 0; j < s.size(); j ++) nums[j] += (s[j] - '0');
}
unordered_set<string> forbidden;
for (int i = 0; i < M; i ++) {
string s;
cin >> s;
forbidden.insert(s);
}
set<pair<int, string>> teas;
teas.insert({0, ""});
for (int i = 0; i < P; i ++) {
vector<pair<int, string>> arr;
for (auto p : teas) {
arr.push_back({p.first + N - nums[i], p.second + '1'});
arr.push_back({p.first + nums[i], p.second + '0'});
}
teas.clear();
for (auto p : arr) {
teas.insert(p);
if (teas.size() > 101) teas.erase(teas.find(*teas.rbegin()));
}
}
for (auto p : teas) {
if (!forbidden.count(p.second)) {
cout << "Case #" << caseRank << ": " << p.first << '\n';
break;
}
}
}
}
3. Board Game¶
10pts, 10pts
2018 Round F¶
1. Common Anagrams¶
8pts, 10pts
给
A和B两个长度为L的字符串，求A中有多少个子串在B中能找到异构的子串，即字母一样排列不同input
6 3 ABB BAB 3 BAB ABB 6 CATYYY XXXTAC 9 SUBXXXXXX SUBBUSUSB 4 AAAA AAAA 19 PLEASEHELPIMTRAPPED INAKICKSTARTFACTORYoutput
Case #1: 5 Case #2: 6 Case #3: 6 Case #4: 6 Case #5: 10 Case #6: 9数据范围
- 1 \le T \le 100
- 1 \le L \le 50
思路
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
const int SEED = 13331;
unsigned long long toHash(string s) {
int* nums = new int[26]();
for (char c : s) nums[c - 'A'] ++;
unsigned long long result = 0;
for (int i = 0; i < 26; i ++) result = (result * SEED + nums[i]);
return result;
}
int T, L;
int main() {
cin >> T;
for (int caseRank = 1; caseRank <= T; caseRank ++) {
cin >> L;
string A, B;
cin >> A >> B;
int result = 0;
for (int i = 1; i <= L; i ++) {
unordered_set<unsigned long long> s;
for (int j = 0; j <= L - i; j ++) s.insert(toHash(B.substr(j, i)));
for (int j = 0; j <= L - i; j ++) {
unsigned long long key = toHash(A.substr(j, i));
if (s.count(key)) result ++;
}
}
cout << "Case #" << caseRank << ": " << result << '\n';
}
}
2. Specializing Villages¶
12pts, 18pts
2018 Round G¶
1. Product Triplets¶
5pts, 12pts
给
N个范围在[0,2\times 10^5]的整数，求里面有多少满足两个数之积等于第三个数的三元组
#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
const int MX = 200005;
int T, N;
int main() {
cin >> T;
for (int caseRank = 1; caseRank <= T; caseRank ++) {
cin >> N;
vector<long long> nums(200010, 0);
for (int i = 0; i < N; i ++) {
int num; cin >> num;
nums[num] ++;
}
long long result = 0;
for (int i = 2; i < MX - 1; i ++) {
if (i * i > MX) break;
if (nums[i] == 0) continue;
if (nums[i] > 1) result += nums[i] * (nums[i]-1) * nums[i*i] / 2;
for (int j = i + 1; j < MX; j ++) {
if (nums[j] == 0) continue;
if (i * j > MX) break;
long long product = nums[i] * nums[j] * nums[i * j];
result += product;
}
}
if (nums[0] >= 3) result += (nums[0] * (nums[0]-1) * (nums[0]-2)) / 6;
if (nums[1] >= 3) result += (nums[1] * (nums[1]-1) * (nums[1]-2)) / 6;
if (nums[0] > 1)result += nums[0] * (nums[0]-1) * (N-nums[0]) / 2;
if (nums[1] > 0) for (int i = 2; i <= MX; i ++) if (nums[i] > 1) result += nums[1] * nums[i] * (nums[i]-1) / 2;
cout << "Case #" << caseRank << ": " << result << '\n';
}
}
2018 Round H¶
1. Big Buttons¶
9pts, 13pts
#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;
class Node{
public:
bool end;
Node* left, *right;
Node() : end(false), left(nullptr), right(nullptr) {}
};
bool prefix(Node* node, string s) {
int i = 0;
while (node != nullptr && i < s.size()) {
if (node->end) return true;
if (s[i] == 'R') node = node->left;
else node = node->right;
i ++;
}
return false;
}
void insert(Node* node, string s) {
int i = 0;
Node* prev = node;
while (node != nullptr && i < s.size()) {
prev = node;
if (s[i] == 'R') node = node->left;
else node = node->right;
if (node != nullptr) i ++;
}
if (node == nullptr) {
while (i < s.size()) {
Node *temp = new Node();
if (s[i] == 'R') prev->left = temp;
else prev->right = temp;
prev = temp; i ++;
}
prev->end = true;
}
}
int T, N, P;
int main() {
ios::sync_with_stdio(false);
cin >> T;
for (int caseRank = 1; caseRank <= T; caseRank++) {
cin >> N >> P;
vector<string> V[51];
for (int i = 0; i < P; i++) {
string s;
cin >> s;
V[s.size()].push_back(s);
}
long long result = 1;
result <<= N;
Node* root = new Node();
for (int i = 1; i <= N; i ++) {
for (auto& s : V[i]) {
if (prefix(root, s)) continue;
long long temp = 1;
temp <<= (N - s.size());
result -= temp;
insert(root, s);
}
}
cout << "Case #" << caseRank << ": " << result << '\n';
}
}
2. Mural¶
14pts, 19pts
3. Let Me Count The Ways¶
20pts, 25pts
#include <cstdio>
int T, M, N;
const long long MOD = 1000000007;
long long pow(long long num, long long k) {
if (num == 1 || num == 0) return 1;
long long result = 1;
while (k) {
if (k & 1) result = result * num % MOD;
num = num * num % MOD;
k >>= 1;
}
return result;
}
int main() {
scanf("%d", &T);
long long perm[200001];
long long power[100001];
perm[0] = 1;
for (int i = 1; i <= 2 * 100000; i++) {
perm[i] = perm[i - 1] * i;
perm[i] %= MOD;
}
power[0] = 1;
for (int i = 1; i <= 100000; i++) {
power[i] = 2 * power[i - 1];
power[i] %= MOD;
}
for (int caseRank = 1; caseRank <= T; caseRank++) {
scanf("%d%d", &N, &M);
long long result = 0, comb = 1;
bool sign = true;
for (int i = 0; i <= M; i++) {
long long temp = comb * power[i] % MOD * perm[2 * N - i] % MOD;
if (sign) result += temp;
else result -= temp;
result %= MOD;
if (result < 0) result += MOD;
sign = !sign;
comb = comb * (M - i) % MOD * pow(i + 1, MOD - 2) % MOD;
}
printf("Case #%d: %lld\n", caseRank, result);
}
}