2022 China Collegiate Programming Contest (CCPC) Weihai Site
目录
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;
}
- Programming Collegiate Contest EAJGCI Weihaiprogramming collegiate contest eajgci programming collegiate contest weihai programming collegiate provincial contest programming collegiate jiangsu contest international programming collegiate contest programming collegiate mianyang contest programming collegiate contest guilin programming collegiate shanghai contest programming collegiate shenzhen contest programming collegiate contest harbin