2022 China Collegiate Programming Contest (CCPC) Weihai Site
目录- 2022 China Collegiate Programming Contest (CCPC) Weihai Site
- VP概况
- E - Python Will be Faster than C++
- A - Dunai
- J - Eat, Sleep, Repeat
- G - Grade 2
- C - Grass
- I - Dragon Bloodline
VP概况
这场我一年之前做过，然后就没有去补题，今年重新和新队友们做做这场，开局还算顺利地过了两个签到，然后就是三道铜牌题，曾经一度卡题一个半小时，然后我做出了J，队友做出了数学和计算几何，在正赛算是可以拼手速拿到铜，但还不够，还要多多补题，其实VP的时候C可以写出来的，下蛋就真的不会了
E - Python Will be Faster than C++
模拟，存在 \(a_{n - 1} \geq a_n\) 无解，其余模拟即可
const int N = 1e7 + 20;
int a[N];
void solve()
{
int n, k; cin>>n>>k;
int i;
for(i = 1; i <= n; i++)
cin>>a[i];
int cnt = 0;
i = n;
while(++cnt <= 1e7 && a[n - 1] >= a[n])
{
i++;
a[i] = max(0, 2 * a[i - 1] - a[i - 2]);
if(a[i] < k)
{
cout<<"Python 3."<<i<<" will be faster than C++\n";
return;
}
}
cout<<"Python will never be faster than C++\n";
return;
}
A - Dunai
记录每个位置有多少人，然后算出能组成多少支队伍，再和冠军选手取个min即可，赛时画了柱状图去理解
int n, m, c[10], b[10];
void solve()
{
cin>>n;
set<string> S;
for(int i = 1; i <= n * 5; i++)
{
string s; cin>>s;
S.insert(s);
}
cin>>m;
for(int i = 1; i <= m; i++)
{
string s; cin>>s;
int a; cin>>a;
if(S.count(s))
c[a]++;
b[a]++;
}
int miv = min({b[1], b[2], b[3], b[4], b[5]});
miv = min({miv, c[1] + c[2] + c[3] + c[4] + c[5]});
cout<<miv<<'\n';
return;
}
J - Eat, Sleep, Repeat
博弈，但是答案是求最多的操作次数的奇偶性相关
我的做法是对限制为0进行分段，这样就可以确定 \(a_i\) 最终会出现在哪一段内，对 a 排序，双指针去模拟这个过程
const int N = 3e5 + 20;
int a[N];
int n, k;
map<int, int> mp;
vector<int> vx;
set<int> S;
void solve()
{
mp.clear();
vx.clear();
S.clear();
cin>>n>>k;
for(int i = 1; i <= n; i++)
cin>>a[i];
mp[-1] = 0;
vx.push_back(-1);
S.insert(-1);
mp[1000000002] = 0;
vx.push_back(1000000002);
S.insert(1000000002);
for(int i = 1; i <= k; i++)
{
int x, y; cin>>x>>y;
mp[x] = y;
if(y == 0)
{
S.insert(x);
vx.push_back(x);
}
}
sort(a + 1, a + 1 + n);
sort(vx.begin(), vx.end());
int m = vx.size();
queue<int> q[m + 2];
for(auto it : vx)
{
int p = it + 1;
for(int l = p; ; l++)
{
if(S.count(l)) break;
if(mp.count(l) == 0)
{
mp[l] = n;
break;
}
}
}
for(int i = 1; i <= n; i++)
{
int pos = lower_bound(vx.begin(), vx.end(), a[i]) - vx.begin() - 1;
q[pos].push(a[i]);
}
ll res = 0;
for(int i = 0; i < m; i++)
{
int p = vx[i] + 1;
for(int l = p; ; l++)
{
while(mp[l] != 0 && !q[i].empty() && q[i].front() >= l)
{
mp[l]--;
res += (q[i].front() - l);
q[i].pop();
}
if(q[i].empty())
break;
}
}
if(res % 2 == 1)
{
cout<<"Pico\n";
}
else
cout<<"FuuFuu\n";
return;
}
G - Grade 2
打表可以知道答案有循环节，求出这个循环节区间
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e6 + 10;
ll mi = 1, s[N];
void init()
{
ll x; cin>>x;
for(; mi <= x; mi *= 2);
for(int i = 1; i <= mi; i++)
s[i] = s[i - 1] + (__gcd(i * x ^ x, x) == 1);
}
void solve()
{
ll l, r; cin>>l>>r;
l--;
ll res = r / mi * s[mi] + s[r % mi] - l / mi * s[mi] - s[l % mi];
cout<<res<<'\n';
return;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int TC = 1;
init();
cin >> TC;
for(int tc = 1; tc <= TC; tc++)
{
//cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
C - Grass
手玩数据可以知道，只要 5 个点不在一条直线上，那么答案一定存在，枚举这 5 个点谁做A点即可
证明看 官方题解
int n;
void solve()
{
cin>>n;
vector<array<int, 2>> d;
for(int i = 1; i <= min(n, 4); i++)
{
int x, y; cin>>x>>y;
d.push_back({x, y});
}
bool ok = false;
if(n > 4)
{
for(int i = 5; i <= n; i++)
{
int x, y; cin>>x>>y;
d.push_back({x, y});
for(int j = 0; j < 5; j++)
{
set<array<int, 2>> S, a;
for(int k = 0; k < 5; k++)
{
if(j == k) continue;
int tx = d[k][0] - d[j][0];
int ty = d[k][1] - d[j][1];
int g = __gcd(abs(tx), abs(ty));
tx /= g, ty /= g;
S.insert({tx, ty});
}
if(S.size() == 4 && ok == false)
{
cout<<"YES\n";
cout<<d[j][0]<<" "<<d[j][1]<<'\n';
for(int k = 0; k < 5; k++)
if(j != k)
cout<<d[k][0]<<" "<<d[k][1]<<'\n';
ok = true;
}
}
d.pop_back();
}
}
if(!ok)
cout<<"NO\n";
return;
}
I - Dragon Bloodline
VP时没思路，认为是dp或者贪心，看了题解发现是贪心，也明白了贪心的正确性，对于每次贪心需要最多的元素，放生产效率最高的工具龙去生产
const int N = 2e5 + 10;
int n, k;
ll a[N], b[N], c[N], sb[N];
bool check(ll mid)
{
priority_queue<ll, vector<ll>, less<ll>> q;
for(int i = 1; i <= n; i++)
q.push(a[i] * mid);
for(int i = 0; i < k; i++)
c[i] = b[i];
int i = k - 1;
while(q.size() >= 1)
{
ll t = q.top(); q.pop();
if(i == -1) return false;
ll need = max({1ll, t / (1 << i)});
need = min(c[i], need);
t = t - need * (1 << i);
c[i] = c[i] - need;
if(t >= 1)
q.push(t);
if(c[i] == 0)
i--;
}
return true;
}
void solve()
{
cin>>n>>k;
ll l = 0, r = 0, t = 0;
for(int i = 1; i <= n; i++)
{
cin>>a[i];
t += a[i];
}
for(int i = 0; i < k; i++)
{
cin>>b[i];
sb[i] = b[i] * (1 << i);
r += sb[i];
}
r /= t;
while(l < r)
{
ll mid = (l + r + 1) >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout<<l<<'\n';
return;
}