2022年中国大学生程序设计竞赛女生专场
概况
因为女生赛，要给女队找找题，我又试了下2022女生赛，题目很多小细节需要注意，不然会wa很多发，前 \(3\) 题都要注意下小细节。I 的写法假了，但好在扣了常数扣过去了
A - 减肥计划
- 若 \(k \leq n\)，模拟即可
- 输出第 \(n + 1\) 轮后的队首
我忘记开 1e6 的数组了，而 TLE 两发
const int N = 1e6 + 10;
int n, k, a[N];
void solve()
{
cin>>n>>k;
deque<pair<int, int>> q;
for(int i = 1; i <= n; i++)
{
cin>>a[i];
q.push_back({i, a[i]});
}
int who = 1, win = 0;
while(win <= 2000000)
{
auto t1 = q.front(); q.pop_front();
auto t2 = q.front(); q.pop_front();
if(t1.second >= t2.second)
{
who = t1.first;
win++;
q.push_front(t1);
q.push_back(t2);
}
else
{
win = 0;
who = t2.first;
win++;
q.push_front(t2);
q.push_back(t1);
}
if(win >= k)
{
cout<<who<<'\n';
return;
}
}
cout<<q.front().first<<'\n';
return;
}
C - 测量学
注意题目可以顺时针或逆时针走，注意这个，我忽略而 WA 了两发
其他就是高中数学，唯一的难点就是将弧度转化成角度
double pi = acos(-1);
int n;
double R, a;
void solve()
{
// cin>>n>>r>>a;
scanf("%d%lf%lf", &n, &R, &a);
double c = a * 180.0 / pi / 360.0;
a = 2 * pi - a;
double c1 = a * 180.0 / pi / 360.0;
double res = 2.0 * R * pi * c;
res = min(2.0 * R * pi * c1, res);
for(int i = 1; i <= n; i++)
{
double r; scanf("%lf", &r);
double ans = 2.0 * (R - r) + 2.0 * r * pi * c;
res = min(ans, res);
ans = 2.0 * (R - r) + 2.0 * r * pi * c1;
res = min(ans, res);
}
printf("%.9lf\n", res);
return;
}
E - 睡觉
- 如果听完一整首歌的疲惫值是下降的，在无限长的时间内，答案是YES
- 一首歌内可以入睡，答案是YES
- 入睡的时刻可能出现两首歌之间，或多首歌，看3首歌的清醒度\(\leq k\) 的最长时间是否大于 $ > 2 n$，我们开倍长数组，模拟判断即可
- NO
第一次交没有判断2的情况
const int N = 1e6 + 10;
int x, t, k, n, d, a[N];
void solve()
{
int s = 0;
cin>>x>>t>>k>>n>>d;
for(int i = 1; i <= n; i++)
{
cin>>a[i];
a[i + n] = a[i];
a[i + 2 * n] = a[i];
a[i + 3 * n] = a[i];
a[i + 4 * n] = a[i];
a[i + 5 * n] = a[i];
a[i + 6 * n] = a[i];
a[i + 7 * n] = a[i];
a[i + 8 * n] = a[i];
a[i + 9 * n] = a[i];
if(a[i] <= d)
s++;
else s--;
}
if(s >= 1)
{
cout<<"YES\n";
return;
}
s = x;
int last = 0;
for(int i = 1; i <= 10 * n; i++)
{
if(a[i] <= d)
s--;
else s++;
if(s <= k)
last++;
else last = 0;
if(last >= t)
{
cout<<"YES\n";
return;
}
}
if(last >= 3 * n)
{
cout<<"YES\n";
return;
}
else
cout<<"NO\n";
return;
}
G - 排队打卡
直接模拟这个过程即可
ll t, m;
ll n, k;
pair<ll, ll> a[N];
void solve()
{
cin>>t>>m;
cin>>n>>k;
for(int i = 1; i <= n; i++)
cin>>a[i].first>>a[i].second;
n++;
a[n] = {t, 0};
sort(a + 1, a + 1 + n);
ll people = 0, s = 0;
ll r1 = 2e18, r2 = 2e18;
for(int i = 1; i <= n; i++)
{
ll gap = a[i].first - s - 1;
s = a[i].first;
people = people - gap * k;;
people = max(people, 0ll);
people = people + a[i].second;
if(a[i].second == 0 && people != m)
{
cout<<"Wrong Record\n";
return;
}
if(a[i].second != 0 && a[i].first >= t)
{
ll t = (people + 1) / k + ((people + 1) % k != 0);
if(t <= r2)
r1 = a[i].first, r2 = t;
}
people = max(people - k, 0ll);
}
cout<<r1<<" "<<r2<<'\n';
return;
}
H - 提瓦特之旅
当时一看用 \(k\) 条边到 \(t\) 号结点，这不是bellman-ford吗？直接往这方面想，发现复杂度是 \(O(NM)\) 是可以预处理出来的，查询的时候预处理\(w_1, w_2, \dots,w_{n-1}\)的前缀和，那么查询的时间复杂度是 \(O(QN)\)
const int N = 5e2 + 10;
const int M = 2e5 + 10;
ll f[N][N], g[N][N], cnt;
ll n, m, k, dist[N], backup[N];
struct EDGES
{
ll a, b, w;
}edge[M];
void bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
memset(f, 0x3f, sizeof f);
dist[1] = 0;
for(int i = 1; i < n; i++)
{
memcpy(backup, dist, sizeof dist);
// cout<<backup[0]<<'\n';
for(int j = 0; j < 2 * m; j++)
{
auto e = edge[j];
if(backup[e.a] <= 1e10)
dist[e.b] = min(dist[e.b], backup[e.a] + e.w);
}
for(int j = 1; j <= n; j++)
f[i][j] = min(dist[j], f[i - 1][j]);
// for(int j = 1; j <= n; j++)
// cout<<"round : "<<i<<" v : "<<j<<" "<<f[i][j]<<'\n';
}
}
void solve()
{
cin >> n >> m;
for(int i = 0; i < m; i++)
{
ll u, v, w;
cin >> u >> v >> w;
edge[cnt++] = {u, v, w};
edge[cnt++] = {v, u, w};
}
bellman_ford();
// for(int i = 1; i <= n; i++)
// {
// for(int j = 1; j <= n; j++)
// cout<<f[i][j]<<" ";
// cout<<'\n';
// }
int q; cin>>q;
for(int i = 1; i <= q; i++)
{
int t; cin>>t;
vector<ll> s(n + 1);
for(int i = 1; i <= n - 1; i++)
{
cin>>s[i];
s[i] += s[i - 1];
}
ll res = 1e18;
for(int i = 1; i <= n - 1; i++)
if(f[i][t] != 0)
res = min(f[i][t] + s[i], res);
cout<<res<<'\n';
}
return;
}
I - 宠物对战
很神奇，是一个简单dp，最开始TLE，怎么也过不去，扣了下常数就过了
\(f_{i,0/1}\) 代表第 \(i\) 位字符，最后一个字符串属于A类或B类
我的做法时间复杂度 \(O(\sum|a_i| + \sum|b_i| + N|S| + M|S|)\)
但看别人代码发现，存一下预处理的哈希值，每次转移看有没有哈希值等于\(S_{l, \dots, r}\) 的哈希值就可以了
这样是 \(O(\sum|a_i| + \sum|b_i| + |S|^2\log N)\)
\[f_{i,0} = \min f_{i - |a_i|} + 1
\\
f_{i,1} = \min f_{i - |b_i|} + 1
\]
const int N = 1e5 + 10;
typedef pair<long long, long long> pll;
struct DoubleStringHash
{
vector<long long> h1, h2, w1, w2;
long long base1 = 131, base2 = 13331;
long long p1 = 1e9 + 7, p2 = 1e9 + 9;
void init(string s) {
int len = s.size();
s = " " + s;
h1.resize(len + 1), w1.resize(len + 1);
h2.resize(len + 1), w2.resize(len + 1);
h1[0] = 0, w1[0] = 1;
h2[0] = 0, w2[0] = 1;
for(int i = 1; i <= len; i++) {
h1[i] = (h1[i - 1] * base1 + s[i]) % p1, w1[i] = w1[i - 1] * base1 % p1;
h2[i] = (h2[i - 1] * base2 + s[i]) % p2, w2[i] = w2[i - 1] * base2 % p2;
}
}
inline pll get(int l, int r) {
return {(h1[r] - h1[l - 1] * w1[r - l + 1] % p1 + p1) % p1, (h2[r] - h2[l - 1] * w2[r - l + 1] % p2 + p2) % p2};
}
}ha[N], hb[N], hs;
int n, m, f[N][2], len1[N], len2[N];
string s[N], ss[N];
pll sa[N], sb[N];
bool cmp(string a, string b)
{
return a.size() < b.size();
}
void solve()
{
cin>>n;
for(int i = 1; i <= n; i++)
cin>>s[i];
cin>>m;
for(int i = 1; i <= m; i++)
cin>>ss[i];
sort(s + 1, s + 1 + n, cmp);
sort(ss + 1, ss + 1 + m, cmp);
for(int i = 1; i <= n; i++)
{
len1[i] = s[i].size();
ha[i].init(s[i]);
sa[i] = ha[i].get(1, len1[i]);
}
for(int i = 1; i <= m; i++)
{
len2[i] = ss[i].size();
hb[i].init(ss[i]);
sb[i] = hb[i].get(1, len2[i]);
}
memset(f, 0x3f, sizeof f);
f[0][0] = f[0][1] = 0;
string op; cin>>op; int len = op.size();
hs.init(op);
for(int i = 1; i <= len; i++)
{
for(int j = 1; j <= n; j++)
{
if(i - len1[j] < 0)
break;
if(f[i - len1[j]][0] + 1 >= f[i][1]) continue;
auto t1 = hs.get(i - len1[j] + 1, i);
if(sa[j].first == t1.first && sa[j].second == t1.second)
f[i][1] = min(f[i - len1[j]][0] + 1, f[i][1]);
}
for(int j = 1; j <= m; j++)
{
if(i - len2[j] < 0)
break;
if(f[i - len2[j]][1] + 1 >= f[i][0]) continue;
auto t1 = hs.get(i - len2[j] + 1, i);
if(sb[j].first == t1.first && sb[j].second == t1.second)
f[i][0] = min(f[i - len2[j]][1] + 1, f[i][0]);
}
}
if(f[len][0] > 5000 && f[len][1] > 5000)
cout<<-1<<'\n';
else
cout<<min(f[len][0], f[len][1])<<'\n';
return;
}
L - 彩色的树
很典的树上启发式合并，改一改add，query，del函数就没了
const int N = 1e5 + 10;
int n, k;
vector<int> e[N];
int l[N], r[N], id[N], sz[N], hs[N], dep[N], tot;
int col[N], c[N], now;
vector<int> del_c[N * 2];
int res[N];
inline void add(int u)
{
if(c[col[u]] == 0) now++;
c[col[u]]++;
del_c[dep[u]].push_back(col[u]);
}
inline void del(int depth)
{
for(auto it : del_c[depth])
{
c[it]--;
if(c[it] == 0) now--;
}
del_c[depth].clear();
}
inline void query(int u)
{
res[u] = now;
}
void dfs_init(int u,int f) {
dep[u] = dep[f] + 1;
l[u] = ++tot;
id[tot] = u;
sz[u] = 1;
hs[u] = -1;
for (auto v : e[u]) {
if (v == f) continue;
dfs_init(v, u);
sz[u] += sz[v];
if (hs[u] == -1 || sz[v] > sz[hs[u]])
hs[u] = v;
}
r[u] = tot;
}
void dfs_solve(int u, int f, bool keep) {
// cout<<u<<" "<<f<<" "<<keep<<'\n';
for (auto v : e[u]) {
if (v != f && v != hs[u]) {
dfs_solve(v, u, false);
}
}
if (hs[u] != -1) {
dfs_solve(hs[u], u, true);
}
for (auto v : e[u]) {
if (v != f && v != hs[u]) {
// for (int x = l[v]; x <= r[v]; x++)
// query(id[x]);
for (int x = l[v]; x <= r[v]; x++)
if(dep[u] + k >= dep[id[x]])
add(id[x]);
}
}
add(u);
del(dep[u] + k + 1);
query(u);
if (!keep) {
for(int x = l[u]; x <= r[u]; x++)
del(dep[id[x]]);
}
}
void solve()
{
cin>>n>>k;
for(int i = 1; i <= n; i++)
cin>>col[i];
for (int i = 1; i < n; i++) {
int u, v; cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs_init(1, 0);
dfs_solve(1, 0, false);
int q; cin>>q;
for(int i = 1; i <= q; i++)
{
int u; cin>>u;
cout<<res[u]<<'\n';
}
}