2024北京航空航天大学程序设计竞赛 决赛¶
2025-05-08
link: https://codeforces.com/gym/105629
前几天打的，还没补题，先把写了的题给记一下吧。
由于是晚上打的，所以没有办法打满四小时，但是也差不多了感觉。
A¶
B¶
找到最小的可以满足的数字，然后比它大的都可以，比它小的都不行。求个区间和就行了。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int mod = 998244353;
ll ksm(ll a, ll b)
{
ll res = 1;
while(b){
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int x, y;
cin >> x >> y;
ll L = 0;
for(int i = 1; i <= min(x - 1, y - 1); i++)
L = (L * 10 + 4) % mod;
L = (L * 10 + 5) % mod;
for(int i = 1; i <= x - y; i++)
L = L * 10 % mod;
// cout << L << '\n';
ll R = (ksm(10, x) - 1 + mod) % mod;
ll ans = (L + R) * (R - L + 1) % mod * ksm(2, mod - 2) % mod;
ans = (ans + mod) % mod;
cout << ans << '\n';
return 0;
}
C¶
过的人非常多的一道题，但是我们后面才想到。
\(n\) 为偶数的话，显然全负数就行。然后 \(n\) 为奇数，本以为不行的，在 WA 麻了之后突然发现，只需要整一个 \(2\) 就行，其他全 \(-1\)。
for _ in range(int(input())):
n = int(input())
print("YES")
if n & 1:
for i in range(2 * n):
print(-1, end = " ")
print(2)
else:
for i in range(2 * n + 1):
print(-1, end = " ")
print()
D¶
也是签到题。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int n, k;
cin >> n >> k;
vector<ll> a(k + 1), t(n + 1), c(n + 1);
for(int i = 1; i <= k; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> t[i] >> c[i];
// for(int i = 1; i <= n; i++) cin >> c[i];
auto check = [&](int T){
vector<ll> need(a);
for(int i = 1; i <= T; i++){
need[t[i]] -= c[i];
}
vector<ll> stk1, stk2;
for(int i = 1; i <= k; i++){
if(need[i] < 0) stk1.push_back(-need[i]);
else if(need[i] > 0) stk2.push_back(need[i]);
}
while(stk1.size() && stk2.size()){
auto x = stk1.back(), y = stk2.back();
// cerr << x << " " << y << '\n';
stk1.pop_back(), stk2.pop_back();
if(3 * x > y){
stk1.push_back(x - y / 3);
}else{
y -= 3 * x;
if(y >= 3) stk2.push_back(y);
}
}
return stk1.empty();
};
int lo = 0, hi = n + 1;
while(lo < hi - 1){
int mid = (lo + hi) >> 1;
if(check(mid)) lo = mid;
else hi = mid;
}
// cerr << check(5) << '\n';
cout << lo << '\n';
return 0;
}
E¶
感觉是这一场我们写出来的唯一稍微复杂点的题目。
题意是给一个有向图，每个节点有一种属性，我们需要对这个图，每次只能删除入度为 \(0\) 的点，如果删除了一种类型的点，就必须连着把这种类型的点删完。需要输出一种可行的顺序，若不行则输出 \(-1\)。
那么这个过程很显然就是在进行拓扑排序，只是多了一点限制条件，需要记录一下就行，记录一下每种类型的点有没有其他类型的点连过来。感觉还是稍微有一点细节的，但难度不高。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int n, m;
cin >> n >> m;
vector<int> a(n + 1), cnt(n + 1), ru(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
vector<vector<int>> g(n + 1, vector<int>());
vector<vector<int>> g1(n + 1, vector<int>());
// for(int i = 1; i <= n; i++)
// g1[a[i]].push_back(i);
for(int i = 1; i <= m; i++){
int x, y;
cin >> x >> y;
g[x].push_back(y);
ru[y]++;
if(a[x] != a[y]){
cnt[a[y]]++;
}
}
// queue<int> q;
// vector<bool> vis(n + 1);
// set<int> st;
// auto cmp = [&](int x, int y){
// return a[x] < a[y];
// };
// priority_queue<int, vector<int>, decltype(cmp)>pq(cmp);
set<int> color;
vector<queue<int>>q(n + 1);
{
vector<int> tmp;
for(int i = 1; i <= n; i++){
// cerr << ru[i] << " " << cnt[a[i]] << '\n';
if(ru[i] == 0 && cnt[a[i]] == 0){
// q.push(i);
// tmp.push_back(i);
// pq.push(i);
color.insert(a[i]);
}
if(ru[i] == 0)
q[a[i]].push(i);
}
// sort(tmp.begin(), tmp.end(), [&](int x, int y){
// return a[x] < a[y];
// });
// for(auto x : tmp)
// q.push(x);
}
vector<int> ans;
while(color.size()){
int x = *color.begin();
color.erase(color.begin());
while(!q[x].empty()){
int u = q[x].front();
q[x].pop();
ans.push_back(u);
for(auto v : g[u]){
ru[v]--;
if(a[v] == x){
if(ru[v] == 0)
q[x].push(v);
}else{
cnt[a[v]]--;
if(ru[v] == 0)
q[a[v]].push(v);
if(cnt[a[v]] == 0)
color.insert(a[v]);
}
}
}
}
// while(pq.size()){
// // queue<int> q1;
// {
// int u = pq.top();
// // q.pop();
// pq.pop();
// // if(vis[u]) continue;
// // q1.push(u);
// // vis[a[u]] = true;
// // cerr << u << '\n';
// // vis[u] = true;
// ans.push_back(u);
// for(auto v : g[u]){
// if(v == 5){
// cerr << cnt[a[5]] << '\n';
// }
// ru[v]--;
// if(a[v] == a[u]){
// if(ru[v] == 0)
// pq.push(v);
// }else{
// cnt[a[v]]--;
// if(ru[v] == 0)
// g1[a[v]].push_back(v);
// if(cnt[a[v]] == 0){
// for(auto x : g1[a[v]])
// pq.push(x);
// }
// }
// }
// }
// // while(!q1.empty()){
// // auto u = q1.front();
// // cerr << u << '\n';
// // q1.pop();
// // vis[u] = true;
// // ans.push_back(u);
// // for(auto v : g[u]){
// // ru[v]--;
// // if(a[v] == a[u]){
// // if(ru[v] == 0)
// // q1.push(v);
// // }else{
// // cnt[a[v]]--;
// // if(ru[v] == 0)
// // g1[a[v]].push_back(v);
// // if(cnt[a[v]] == 0){
// // for(auto x : g1[a[v]])
// // q.push(x);
// // }
// // }
// // }
// // }
// }
if(ans.size() != n){
cout << "-1\n";
return;
}
for(auto x : ans)
cout << x << ' ';
cout << '\n';
}
int main()
{
// freopen("1.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T;
cin >> T;
while(T--)
solve();
return 0;
}
summary¶
这场我们写出来的题感觉难度还是比较低的，还有点题能补的，但最近没空，以后看到再来吧。