写在前面
时间复杂度与数据范围的关系
计算机 1 秒大约能执行 5e8 次计算，假设时间限制为 1 秒，时间复杂度和数据范围对应如下：
O(n) 的算法能解决的数据范围在 n <= 1e8
O(nlogn) 的算法能解决的数据范围在 n <= 1e6
O(n^2) 的算法能解决的数据范围在 n <= 5e3
O(n^3) 的算法能解决的数据范围在 n <= 3e2
O(2^n) 的算法能解决的数据范围在 n <= 25
O(n!) 的算法能解决的数据范围在 n <= 11
题解
Problem A 毒奶
题意
TI 比赛有 n 只冠军队伍，每个队伍由五个选手组成，每个 选手分别打 1-5 号位中的一个，一个选手永远只打一个位置，不会打其他位置。有 m 名选手组队，问最多能组多少队，满足每个队内至少有一名冠军选手。
代码
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
unordered_map<string, int> name;
int pos[10], cham[10];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= 5; j++)
{
string s;
cin >> s;
name[s] = 1;
}
}
int m;
cin >> m;
for(int i = 1; i <= m; i++)
{
string s;
int x;
cin >> s >> x;
pos[x]++;
if(name.count(s) != 0)
{
cham[x]++;
}
}
int pos_min_num = INT_MAX, cham_num = 0;
for(int i = 1; i <= 5; i++)
{
pos_min_num = min(pos_min_num, pos[i]);
cham_num += cham[i];
}
cout << min(pos_min_num, cham_num);
return 0;
}
Problem C 草
题意
给定平面上 n 个点，要求选出其中 5 个不同的点，并选定 1 个中心点 A 向其他 4 个点 B, C, D, E 连出 4 条线段，要求这四条线段任意两条的交点都仅有中心点 A。
代码
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 25005;
int x[N], y[N];
int n;
bool check()
{
if(n < 5)
{
return false;
}
set<pair<int, int>> s;
for(int i = 2; i <= n; i++)
{
int dx = x[i] - x[1];
int dy = y[i] - y[1];
int t = abs(__gcd(dx, dy));
if(dx < 0)
{
dx = -dx;
dy = -dy;
}
s.insert({dx / t, dy / t});
}
if(s.size() == 1)
{
return false;
}
return true;
}
bool valid_point(int o)
{
set<pair<int, int>> s;
for(int i = 1; i <= 4; i++)
{
int dx = x[i] - x[o];
int dy = y[i] - y[o];
int t = abs(__gcd(dx, dy));
if(dx < 0)
{
dx = -dx;
dy = -dy;
}
s.insert({dx / t, dy / t});
}
if(s.size() == 1)
{
return false;
}
return true;
}
bool valid_permulation(int o)
{
set<pair<int, int>> s;
for(int i = 1; i <= 4; i++)
{
int dx = x[i] - x[o];
int dy = y[i] - y[o];
int t = abs(__gcd(dx, dy));
if(dx < 0)
{
dx = -dx;
dy = -dy;
}
s.insert({dx / t, dy / t});
}
if(s.size() == 1)
{
return false;
}
return true;
}
bool valid_permulation(vector<int>& v)
{
set<pair<int, int>> s;
for(int i = 1; i < 5; i++)
{
int dx = x[v[i]] - x[v[0]];
int dy = y[v[i]] - y[v[0]];
int t = abs(__gcd(dx, dy));
s.insert({dx / t, dy / t});
}
if(s.size() != 4)
{
return false;
}
return true;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T;
cin >> T;
while(T--)
{
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> x[i] >> y[i];
}
if(check() == false)
{
cout << "NO" << endl;
continue;
}
vector<int> v = {1, 2, 3, 4};
for(int i = 5; i <= n; i++)
{
if(valid_point(i))
{
v.emplace_back(i);
break;
}
}
while(next_permutation(v.begin(), v.end()))
{
if(valid_permulation(v))
{
cout << "YES" << endl;
for(auto i : v)
{
cout << x[i] << " " << y[i] << endl;
}
break;
}
}
}
return 0;
}
Problem D 中国跳棋
题意
给定六边形棋盘每个格子的分数，询问若干初始的棋子摆放方式，问按照规则移除棋子最多得多少分。
移除棋子有两种方式，一种是直接移除一个棋子，不得分； 另一种是用一个棋子跳过其相邻棋子，移除被跳过的棋子并且得分增加被移除棋子所在的格子的分数。
代码
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 19;
int w[N];
int dp[1 << N], vis[1 << N];
vector<pair<int, int>> v[N];
void add(int mid, int a, int b)
{
v[mid].push_back({a, b});
v[mid].push_back({b, a});
}
void init()
{
memset(dp, -0x3f, sizeof dp);
dp[0] = 0, vis[0] = 1;
add(1, 0, 2);
add(3, 0, 7);
add(4, 0, 9), add(4, 1, 8), add(4, 3, 5);
add(5, 1, 10), add(5, 2, 9), add(5, 4, 6);
add(6, 2, 11);
add(8, 3, 13), add(8, 4, 12), add(8, 7, 9);
add(9, 4, 14), add(9, 5, 13), add(9, 8, 10);
add(10, 5, 15), add(10, 6, 14), add(10, 9, 11);
add(12, 7, 16);
add(13, 8, 17), add(13, 9, 16), add(13, 12, 14);
add(14, 9, 18), add(14, 10, 17), add(14, 13, 15);
add(15, 11, 18);
add(17, 16, 18);
}
int dfs(int state)
{
if(vis[state])
{
return dp[state];
}
for(int i = 0; i < N; i++)
{
if(((state >> i) & 1) == 0)
{
continue;
}
dp[state] = max(dp[state], dfs(state - (1 << i)));
}
for(int i = 0; i < N; i++)
{
if(((state >> i) & 1) == 0)
{
continue;
}
for(auto p : v[i])
{
int a = p.first, b = p.second;
if((((state >> a) & 1) == 0) || (((state >> b) & 1) == 1))
{
continue;
}
dp[state] = max(dp[state], dfs(state - (1 << i) - (1 << a) + (1 << b)) + w[i]);
}
}
vis[state] = 1;
return dp[state];
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
for(int i = 0; i < 19; i++)
{
cin >> w[i];
}
init();
int n;
cin >> n;
while(n--)
{
string s, t;
for(int i = 0; i < 5; i++)
{
cin >> t;
s += t;
}
int state = 0;
for(int i = 0; i < N; i++)
{
if(s[i] == '#')
{
state += (1 << i);
}
}
cout << dfs(state) << endl;
}
return 0;
}
Problem E Python将比c++更快
题意
给出 n 个 Python 版本的运行时间，依据最后两个版本的运行时间画出一次函数之后判断是否会在未来某个版本运行时 间超过 C++。
代码
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e6 + 5;
int a[N];
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
for(int i = n + 1; i <= 1e6; i++)
{
a[i] = max(0ll, 2ll * a[i - 1] - a[i - 2]);
if(a[i] < k)
{
cout << "Python 3." << i << " " << "will be faster than C++" << endl;
exit(0);
}
}
cout << "Python will never be faster than C++" << endl;
return 0;
}
Problem G 二年级
题意
求 多组询问。其中 ⊕ 为异或运算。
代码
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e6 + 5;
int pre[N];
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int x, n;
cin >> x >> n;
int c = 1;
while(c < x)
{
c *= 2;
}
for(int i = 1; i <= c; i++)
{
pre[i] = pre[i - 1] + (__gcd(i * x ^ x, x) == 1);
}
while(n--)
{
int l, r;
cin >> l >> r;
l--;
int res = 0;
res -= (l / c) * pre[c];
res -= pre[l % c];
res += (r / c) * pre[c];
res += pre[r % c];
cout << res << endl;
}
return 0;
}
Problem I 龙的血统
题意
合成一个龙蛋需要 n 种精华，其中第 i 种精华需要 ai 个单位。
有 k 种工具龙，第 j 种工具龙总共有 bj 条，且每单位时间 能产出 2^(j − 1) 单位的任意一种精华。
你需要将每条工具龙分配去生产某种精华，并最大化每单位 时间内能产生的龙蛋数量。
代码
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 5e4 + 5;
int a[N], b[25], bb[25];
int n, k;
int check(int x)
{
if(x == 0)
{
return 1;
}
for(int i = 1; i <= k; i++)
{
bb[i] = b[i];
}
priority_queue<int> q;
for(int i = 1; i <= n; i++)
{
q.push(a[i] * x);
}
int maxlevel = k;
while(!q.empty())
{
if(maxlevel == 0)
{
return 0;
}
int topq = q.top();
int numl = (1ll << (maxlevel - 1));
q.pop();
if(topq <= numl)
{
bb[maxlevel]--;
if(bb[maxlevel] == 0)
{
maxlevel--;
}
}
else
{
int cnt = min(topq / numl, bb[maxlevel]);
bb[maxlevel] -= cnt;
topq -= cnt * numl;
if(bb[maxlevel] == 0)
{
maxlevel--;
}
if(topq > 0)
{
q.push(topq);
}
}
}
return 1;
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T;
cin >> T;
while(T--)
{
cin >> n >> k;
int suma = 0, totb = 0;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
suma += a[i];
}
for(int i = 1; i <= k; i++)
{
cin >> b[i];
totb += (1ll << (i - 1)) * b[i];
}
int left = 0, right = totb / suma + 1;
while(left < right)
{
int mid = left + ((right - left) >> 1);
if(check(mid))
{
left = mid + 1;
}
else
{
right = mid;
}
}
cout << left - 1 << endl;
}
return 0;
}
Problem J 吃饭，睡觉，重复
题意
给定 n 个数 a1, a2..., an，以及 k 条限制，每条形如 limit[xi] = yi。两个人进行游戏，每次选一个大于 0 的数并减去 1，如果出现某个数 t 的出现次数 cnt[t] 大于上限 limit[t] 或者无法操作就输了，问谁赢。
代码
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e5 + 5;
int a[N];
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T;
cin >> T;
while(T--)
{
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
sort(a + 1, a + 1 + n);
map<int, int> mp;
set<int> s;
while(k--)
{
int x, y;
cin >> x >> y;
mp[x] = y;
if(y == 0)
{
s.insert(x);
}
}
s.insert(-1);
s.insert(1e18);
int ans = 0;
for(int i = 1; i <= n; i++)
{
int x = a[i];
auto p = lower_bound(s.begin(), s.end(), x);
p = prev(p);
ans += x - *p - 1;
if(mp.count(*p + 1))
{
mp[*p + 1]--;
if(mp[*p + 1] == 0)
{
s.insert(*p + 1);
}
}
}
cout << ((ans % 2 == 1) ? "Pico" : "FuuFuu") << endl;
}
return 0;
}