2022CCPC威海：A、C、E、G、J
目前这5题让我觉着，威海这场思路倒不是多难，但是代码我觉着很难写，比如c和j。
Problem - A - Codeforces
问题解析
题目很怪，看了好多次。
题目说有个比赛，先给你n行，每行5个人，这五个人的顺序是他们比赛的位置（1~5），这n行是之前比赛的冠军，再给你m个人，每个人有对应的位置，问你最多能组成多少队伍参加比赛，每个队伍里都至少要有一个冠军，每个人的位置不能变。
一开始想的能组多少不同的队伍，这样就是每个位置的不同人数和冠军的数量来算，但是显然样例1就不对劲。后来发现是能组成的队伍数，不是不同的队伍数。
- 那就计算每个位置的人数，如果不考虑冠军的因素，能组成的最多队伍数就等于这五个位置里人数最少的数量（比如1到4位置都有10人，但位置5只有1人，那就只能组成1个队伍，木桶原理）。
- 如果要考虑冠军因素，那贪心的来想，就是每个队伍一个冠军，那能组成的队伍数就是冠军的数量。
答案就是两者中的最小值。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e6 + 50, MOD = 1e9 + 7;
void solve()
{
int n, m, x;
string s;
unordered_map<int, int>mymap, champion;
unordered_map<string, int>st;
cin >> n;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= 5; j++)
{
cin >> s;
st[s] = 1;
}
}
cin >> m;
for (int i = 1; i <= m; i++)
{
cin >> s >> x;
mymap[x]++;
if (st.count(s))
{
champion[x]++;
}
}
int mn = 1e9, ans = 0;
for (int i = 1; i <= 5; i++)mn = min(mn, mymap[i]);
for (int i = 1; i <= 5; i++)
{
ans += champion[i];
}
cout << min(mn,ans);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
//cin >> t;
while (t--)
{
solve();
}
return 0;
}
Problem - C - Codeforces
问题解析
题目说给你n个点，问你能不能找到五个点ABCDE，让线段AB、AC、AD、AE之间不发生交叉。
很显然，要是给的点不够5个，就直接输出NO。
我们也可以想出，只要BCDE四个点不是都和A共线的，就能有结果，哪怕BCDE四个点都是共线。
也就说重点不在BCDE上，而是在点A上。
对于给的n个点，我们之间把前四个点记录下来，然后从剩下的点里面找第五个点。每次我们假设这五个点是答案送去判断，如果能组成答案就输出，不能我们就找下一个点当作第五个点，以此类推，要是找完了还没能出结果，说明没有答案，输出NO。
至于判断五个点是不是答案，我们枚举每个点当作是A，剩下的当作BCDE，然后看他们和A的共线情况。
这里我是判断他们和A的斜率：**（y2-y1）/（x2-x1）**是否相同。如果都不相同，说明当前枚举的点A就可以是一个合格的答案。
如果有两个斜率相同，说明这两个点和A共线，那么，当且仅当A是在这俩点中间时，才是正确的，比如：
而如果A不在两点之间，显然答案不对的，比如：
至于判断A是否在BC之间，只要看AB+AC是否等于BC即可。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e6 + 50, MOD = 1e9 + 7;
int gcd(int a, int b)
{
return a == 0 ? b : gcd(b % a, a);
}
bool check(vector<PII>& ans)
{
for (int i = 0; i < 5; i++)
{
//记录下每个斜率的点
unordered_map<double, vector<PII>>res;
bool flag = true;
for (int j = 0; j < 5; j++)
{
if (i == j)continue;
//计算斜率：（y2-y1）/（x2-x1）
double b = (ans[j].second - ans[i].second), a = (ans[j].first - ans[i].first);
double c = b / a;
//如果已经有两个点与A共线，那这第三个点显然不对
if (res[c].size() >= 2)
{
flag = false;
break;
}
//如果已经有一个点与A共线，那看A在不在这两个点之间
else if (res[c].size() == 1)
{
int x = abs(ans[i].first - res[c][0].first) + abs(ans[i].second - res[c][0].second);
int y = abs(ans[i].first - ans[j].first) + abs(ans[i].second - ans[j].second);
int z = abs(ans[j].first - res[c][0].first) + abs(ans[j].second - res[c][0].second);
if (x + y == z)
{
res[c].push_back(ans[j]);
}
else
{
flag = false;
break;
}
}
else res[c].push_back(ans[j]);
}
if (flag)
{
cout << "YES" << endl;
cout << ans[i].first << " " << ans[i].second << endl;
for (int j = 0; j < 5; j++)
{
if (i == j)continue;
cout << ans[j].first << " " << ans[j].second << endl;
}
return true;
}
}
return false;
}
void solve()
{
int n;
cin >> n;
unordered_map<double, int>mymap;
vector<PII>v(n + 1), ans;
for (int i = 1; i <= n; i++)
{
cin >> v[i].first >> v[i].second;
if (ans.size() < 4)
{
//固定前四个点
ans.push_back(v[i]);
}
}
if (n < 5)
{
cout << "NO" << endl;
return;
}
for (int i = 5; i <= n; i++)
{
//找第五个点
ans.push_back(v[i]);
if (check( ans ))
{
return;
}
ans.pop_back();
}
cout << "NO" << endl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
Problem - E - Codeforces
问题解析
题目是说给你一个长度为n的数组和一个数k，要你找到第一个小于k的数的位置，如果数组没有，那你可以扩展数组:ai=a(i-1)*2-a(i-2);
直到找到小于k的数位置，如果永远也找不到，输出永远也找不到。
没啥想法，就想着先把数组扩展到1e6个数，如果找到了就输出位置，找不到就输出永远也找不到。
然后就过了，笑死。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e6 + 50, MOD = 1e9 + 7;
int a[N];
void solve()
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (a[i] < k)
{
cout << "Python 3." << i << " will be faster than C++" << endl;
return;
}
}
for (int i = n + 1; i <= 1000000; i++)
{
a[i] = max((int)0, 2 * a[i - 1] - a[i - 2]);
if (a[i] < k)
{
cout << "Python 3." << i << " will be faster than C++" << endl;
return;
}
}
cout << "Python will never be faster than C++";
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
//cin >> t;
while (t--)
{
solve();
}
return 0;
}
Problem - G - Codeforces
问题解析
题目说给你一个数x和m次询问，每次询问给一个区间l~r，问你l到r里有几个数k能够满足gcd((k*x ^ x),x)=1.
找规律题，对于数字x，它的答案其实是有一个长度为2^(log2(x)）的循环节（循环节长度就是第一个大于x的2的次幂）。
因为x最大也就1e6，我们可以先把循环节的答案给算出来，一个循环节的k的个数我们记作cnt，然后每次询问，根据区间的长度能分成三部分：
- 最左边的部分，这一部分不是一个完整的循环节。
- 中间的部分，包含了复数个循环节。
- 最右边的部分，这一部分也不是一个完整的循环节。
中间的部分，我们可以通过计算出循环节的个数*cnt得到结果。
至于左边和右边的部分，一开始我用for循环一个个找，然后t了，想了想最坏的情况每次询问我们都要搜1e6左右的长度，复杂度就变成n^2了，慢死。
我们在计算循环节的时候，顺便准备一个前缀和数组sum,sum[i]表示0到i有多少个结果。这样左边和右边的部分我们就能通过前缀和数组算出结果了。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e6 + 50, MOD = 1e9 + 7;
//mymap[i]表示循环节内i是不是正确的答案。
//sum是前缀和数组
int mymap[N], sum[N];
int gcd(int a, int b)
{
return a == 0 ? b : gcd(b % a, a);
}
void solve()
{
int x, n, y = 1, cnt = 0;
cin >> x >> n;
//求出循环节的长度
while (y < x)
{
y *= 2;
}
//求出循环节内的答案数
for (int i = 0; i < y; i++)
{
if (gcd((i * x)^x, x) == 1)
{
mymap[i] = 1;
cnt++;
}
if (i == 0)sum[i] = mymap[i];
else sum[i] = sum[i - 1] + mymap[i];
}
while (n--)
{
int l, r;
cin >> l >> r;
//l2是区间内第一个循环节的开头，r2是区间内最后一个循环节的结尾
int l2 = ceil((double)l / y), r2 = r / y;
int res = 0;
if (l2 * y <= r2 * y)
{
res = (r2 - l2) * cnt;
res += sum[r % y];
}
res += sum[min(l2 * y - 1, r) % y] - sum[(l - 1) % y];
cout << res << endl;
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
//cin >> t;
while (t--)
{
solve();
}
return 0;
}
Problem - J - Codeforces
问题解析
题目是说给你n个数，以及m个限制，每个限制有两个数x和y，表示数x最多只能同时出现y个，每次两个玩家会选一个数-1，最先做不出操作的就输了。
一开始看见博弈吓得很，但是看了题目发现他们每轮的操作并没有多花哨，根据奇偶性就能求出结果。
按照限制中，y=0的地方分割数，如果x最多出现次数为0，说明比他大的数都只能停在x+1上了，不能更小。
然后剩下的数则能删多小删多小。
但是可能会出现x出现次数为0，x+1出现次数为1的限制。
（个人感觉思路不难，但是代码有点麻烦，文字不好说，看代码注释罢）
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e6 + 50, MOD = 1e9 + 7;
void solve()
{
int n, m, x, y;
cin >> n >> m;
//lim只记录y=0的情况
vector<int>v(n), lim;
//mymap记录每个数的限制，cnt记录操作之后每个数出现了几次
unordered_map<int, int>mymap, cnt;
for (int i = 0; i < n; i++)cin >> v[i];
for (int i = 0; i < m; i++)
{
cin >> x >> y;
mymap[x] = y;
//如果y=0，则把当前x存入数组lim中
if (y == 0)
{
lim.push_back(x);
}
}
//为了方便，lim额外存上x=-1和x=(任意一个很大的数)的情况
mymap[-1] = 0;
lim.push_back(-1);
mymap[1e18] = 0;
lim.push_back(1e18);
sort(v.begin(), v.end());
sort(lim.begin(), lim.end());
//res记录结果，ans记录当前能减小到的最小值，idx表示我们当前要减小的是哪个数，l表示当前是第几个限制。
int res = 0, ans = 0, idx = 0, l = 0, len = lim.size();
while (idx < n)
{
//lim[l]当作上界，要保证当前要减小的数小于lim[l]（所以要加一个很大的数
//如果当前进行操作的数大于lim[l]，则l后移，并更新ans
while (l < len && v[idx] > lim[l])
{
//既然lim[l]出现次数为0，那么大家能减小到的最小值就为ans
ans = lim[l] + 1;
l++;
}
while (idx < n && v[idx] < lim[l])
{
//如果ans的出现次数也有限制，那么当减小到ans的数到限制后，ans要++。
while (mymap.count(ans) && cnt[ans] == mymap[ans])
{
ans++;
}
//计算能减小的次数
res += v[idx] - ans;
cnt[ans]++;
idx++;
}
}
//根据奇偶性判断输赢
if (res % 2 == 1)cout << "Pico" << endl;
else cout << "FuuFuu" << endl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
