The 2021 China Collegiate Programming Contest (Harbin)
目录
VP概况
队友不应该写签到,签到应该我来写,以至于多了 \(2\) 罚时,后面的题放心交给队友就好。
J - Local Minimum
问矩阵中有多少个元素 \(A_{i,j}\) 同时是第 \(r\) 行,第 \(c\) 列上的最小元素
\(n = 1000\) 直接暴力
const int N = 1e3 + 10;
ll a[N][N], n, m, res, r[N], c[N];
void solve()
{
cin>>n>>m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin>>a[i][j];
memset(r, 0x3f, sizeof r);
memset(c, 0x3f, sizeof c);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
r[i] = min(a[i][j], r[i]);
for(int j = 1; j <= m; j++)
for(int i = 1; i <= n; i++)
c[j] = min(a[i][j], c[j]);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(a[i][j] == r[i] && a[i][j] == c[j])
res++;
cout<<res<<'\n';
}
B - Magical Subsequence
问子序列第 \(2 \times i\) 元素和 第\(2 \times i - 1\) 位元素的和为 \(X\) 时,子序列的最大长度是?
定义状态 \(f_{i,j}\) ,表示第 \(i\) 位,元素和为 \(j\) 的子序列最大长度
预处理 \(suf_{i,j}\) 表示第 \(i\) 位,后缀中值为 \(k\) 的元素位置
转移方程:
\[f_{suf_{i,j-a_i},j} = f_{i-1,j} + 2
\]
const int N = 1e5 + 10;
int f[N][210];
int a[N], suf[N][110];
void solve()
{
ll n;
cin>>n;
for(int i = 1; i <= n; i++)
cin>>a[i];
memset(suf, -1, sizeof suf);
for(int i = n; i >= 1; i--)
{
for(int j = 1; j <= 100; j++)
suf[i][j] = suf[i + 1][j];
if(i + 1 <= n)
suf[i][a[i + 1]] = i + 1;
}
int res = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= 200; j++)
f[i][j] = max(f[i - 1][j], f[i][j]);
for(int j = a[i] + 1; j <= 200; j++)
{
if(j - a[i] > 100) break;
int k = j - a[i];
if(suf[i][k] == -1) continue;
f[suf[i][k]][j] = max(f[i - 1][j] + 2, f[suf[i][k]][j]);
res = max(f[suf[i][k]][j], res);
}
}
cout<<res<<'\n';
}
E - Power and Modulo
考虑到 \(a_i \leq 10^9\),那么对于取模来说,在 \(n\) 足够大的情况下,一定存在
\(2^{i - 2} \% m= 2^{i - 2}\)
\(2^{i - 1} \% m= a_i\)
const int N = 1e5 + 10;
ll a[N], n;
ll bmi[N];
void solve()
{
cin>>n;
for(int i = 1; i <= n; i++)
cin>>a[i];
bmi[1] = 1;
for(int i = 2; i <= 60; i++)
bmi[i] = bmi[i - 1] * 2;
ll m = -1;
for(int i = 1; i <= n; i++)
{
// cout<<a[i]<<" "<<bmi[i]<<'\n';
if(a[i] == bmi[i])
continue;
else
{
m = bmi[i] - a[i];
break;
}
}
// cout<<m<<" ";
if(m == -1)
{
cout<<-1<<'\n';
return;
}
bool ok = true;
ll base = 1 % m;
for(int i = 1; i <= n; i++)
{
if(base != a[i])
ok = false;
base *= 2;
base %= m;
}
if(ok)
cout<<m<<'\n';
else
cout<<-1<<'\n';
}
I - Power and Zero
发现各个二进制位的有多少个,若满足 \(cnt_0 \geq cnt_1 \geq \dots \geq cnt_{32}\) ,则答案最优,不断去调整即可
const int N = 2e5 + 10;
int cnt[40];
void solve()
{
memset(cnt, 0, sizeof cnt);
int n; cin>>n;
for(int i = 1; i <= n; i++)
{
int x; cin>>x;
int t = 0;
while(x)
{
cnt[t++] += (x % 2);
x /= 2;
}
}
while(1)
{
bool ok = false;
for(int i = 1; i <= 32; i++)
{
if(cnt[i] > cnt[i - 1])
{
ok = true;
cnt[i]--;
cnt[i - 1] += 2;
break;
}
}
if(!ok)
break;
}
cout<<cnt[0]<<'\n';
return;
}
D - Math master
用二进制数 \(S\) 表示分子剩余部分,我们从低位去检查分母即可
#define int __int128
#define ll __int128
using namespace std;
inline __int128 read(){__int128 x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
inline void write(__int128 x){if (x < 0){putchar('-');x = -x;}if (x > 9) write(x / 10);putchar(x % 10 + '0');}
ll a[50], b[50], c[50];
void solve()
{
ll p, q;
// cin>>p>>q;
p = read(), q = read();
int n = 0, m = 0;
__int128 t = p;
while(t) a[n++] = t % 10, t /= 10;
t = q;
while(t) b[m++] = t % 10, t /= 10;
for(int S = 0; S < (1 << n); S++)
{
ll tp = 0, cnt = 0, d[11];
memset(d, 0, sizeof d);
for(int i = n - 1; i >= 0; i--)
if((S >> i) & 1)
cnt++, tp = tp * 10 + a[i];
else d[a[i]]--;
__int128 tq =(__int128)tp * q;
if(tq % p != 0 || tp == 0) continue;
tq /= p;
t = tq;
int j = 0;
for(int i = 0; i < m; i++)
if(b[i] == t % 10)
j++, t /= 10;
else
d[b[i]]++;
bool ok = true;
for(int i = 0; i <= 9; i++)
if(d[i] != 0) ok = false;
if(ok && t == 0 && tq != 0 && tp != 0)
q = min(q, (ll)tq), p = min(p, (ll)tp);
}
write(p); cout<<" "; write(q);
cout<<'\n';
return;
}
G - Damaged Bicycle
\(P_S\) 记录集合内单车都是坏的
官方题解:
\(f_{i,S}\) 为访问 \(S\) 集合内的单车,最终停在 \(i\) 号点的最小期望时间,访问 \(i\) 之前就找到了好单车、\(i\) 是第一辆好 单车、\(i\) 还是坏的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int t, r;
int n, m;
vector<pair<int, int>> e[N];
int k;
int pos[N];
bool vis[N];
double p[20];
int d[20][N];
void dij(int id, int start)
{
priority_queue<pair<int,int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
memset(vis, false, sizeof vis);
for(int i = 1; i <= n; i++)
d[id][i] = 1e9;
d[id][start] = 0;
q.push({0, start});
while(q.size() >= 1)
{
auto t = q.top(); q.pop();
int u = t.second;
if(vis[u]) continue;
vis[u] = true;
for(auto [v, w] : e[u])
{
if(d[id][v] > d[id][u] + w)
{
d[id][v] = d[id][u] + w;
q.push({d[id][v], v});
}
}
}
}
double f[20][1 << 20];
double P[1 << 20];
void solve()
{
cin>>t>>r;
cin>>n>>m;
for(int i = 1; i <= m; i++)
{
int u, v, w;
cin>>u>>v>>w;
e[u].push_back({v, w});
e[v].push_back({u, w});
}
cin>>k;
p[0] = 1.0;
pos[0] = 1;
for(int i = 1; i <= k; i++)
{
cin>>pos[i]>>p[i];
p[i] = p[i] / 100;
if(pos[i] == 1)
{
p[0] = p[i];
i--, k--;
}
}
for(int i = 0; i <= k; i++)
dij(i, pos[i]);
if(d[0][n] >= 1e9)
{
cout<<-1<<'\n';
return;
}
double res = p[0] * d[0][n] / t + (1.0 - p[0]) * d[0][n] / r;
for(int S = 1; S < (1 << k); S++)
{
P[S] = p[0];
for(int j = 0; j < k; j++)
f[j][S] = 1e15;
for(int j = 0; j < k; j++)
if((S >> j) & 1)
P[S] *= p[j + 1];
}
for(int j = 0; j < k; j++)
{
f[j][1 << j] = p[0] * d[0][pos[j + 1]] / t;
f[j][1 << j] += (1 - p[0]) * d[0][n] / r;
f[j][1 << j] += p[0] * (1 - p[j + 1]) * d[j + 1][n] / r;
res = min(f[j][1 << j] + P[1 << j] * d[j + 1][n] / t, res);
}
for(int S = 1; S < (1 << k); S++)
{
for(int i = 0; i < k; i++)
{
if(((S >> i) & 1) == 0) continue;
for(int j = 0; j < k; j++)
{
if(((S >> j) & 1) == 0 || i == j) continue;
f[i][S] = min(f[j][S ^ (1 << i)] + P[S ^ (1 << i)] * d[j + 1][pos[i + 1]] / t, f[i][S]);
}
f[i][S] += P[S ^ (1 << i)] * (1 - p[i + 1]) * d[i + 1][n] / r;
res = min(f[i][S] + P[S] * d[i + 1][n] / t, res);
}
}
cout<<fixed << setprecision(10) <<res<<'\n';
// printf("%.10lf\n", res);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
}
- Programming Collegiate Contest Harbin JBEIDGprogramming collegiate contest harbin programming collegiate provincial contest programming collegiate jiangsu contest international programming collegiate contest programming collegiate mianyang contest programming collegiate contest guilin programming collegiate shenzhen contest programming collegiate shanghai contest programming collegiate codeforces contest programming collegiate contest weihai