2022 International Collegiate Programming Contest, Jinan Site
VP概况
没有罚时的情况下拿下签到,E因为打的表太小,猜错了结论,后面让队友读完大模拟来写,也很顺利,看榜发现后面的题不可做,补题的时候发现也不是1小时可以写出来的,下次比赛按照打满的思路来
M - Best Carry Player
推导得知运算顺序不影响答案,直接模拟
int n;
void solve()
{
cin>>n;
vector<int> a, b, res;
int x; cin>>x;
int ans = 0;
while(x)
{
a.push_back(x % 10);
x /= 10;
}
for(int i = 2; i <= n; i++)
{
cin>>x;
b.clear();
res.clear();
while(x)
{
b.push_back(x % 10);
x /= 10;
}
int len1 = a.size(), len2 = b.size();
int add = 0;
for(int j = 0; j < max(len1, len2); j++)
{
int t1 = 0, t2 = 0;
if(j < len1)
t1 = a[j];
if(j < len2)
t2 = b[j];
int s = t1 + t2 + add;
// cout<<s<<'\n';
res.push_back(s % 10);
// cout<<i<<" "<<j<<" "<<add<<'\n';
add = s / 10;
if(add == 1)
ans++;
}
if(add)
res.push_back(add);
swap(a, res);
// a = res;
}
cout<<ans<<'\n';
}
K - Stack Sort
看有多少个相邻段在数值上和数组下标上是连续的
const int N = 5e5 + 10;
int n, a[N], pos[N];
void solve()
{
cin>>n;
int res = 0;
for(int i = 1; i <= n; i++)
{
cin>>a[i];
pos[a[i]] = i;
}
for(int i = n; i >= 1; i--)
{
int j = i;
while(j >= 2 && pos[j - 1] >= pos[j])
j--;
res++;
i = j;
}
cout<<res<<'\n';
return;
}
A - Tower
如果所有数字都要变成 \(x\) ,那么就是一个中位数问题了,其区别在于除 \(2\) 的操作,除 \(2\) 代表可以有更多的中位数选择,那么可能得中位数数量有 \(O(N \log V)\) 种,然后去判断每个数到达 \(x\) 的最小操作次数,总共时间复杂度 \(N^2 \log V \times (\log V + \log N)\) ,这里包括排序的复杂度
int n, m, a[510];
vector<int> b;
ll check(int x)
{
ll ans = 0;
vector<int> c;
// cout<<"X : ";
for(int i = 1; i <= n; i++)
{
if(a[i] <= x)
{
c.push_back(x - a[i]);
// cout<<x - a[i]<<" ";
continue;
}
int y = a[i];
int cost = a[i] - x;
int t = 0;
while(y)
{
cost = min(abs(y - x) + t, cost);
y /= 2;
t++;
}
c.push_back(cost);
}
sort(c.begin(), c.end());
reverse(c.begin(), c.end());
for(int i = m; i < n; i++)
ans += c[i];
return ans;
}
void solve()
{
b.clear();
cin>>n>>m;
for(int i = 1; i <= n; i++)
{
cin>>a[i];
int x = a[i];
while(x)
{
b.push_back(x);
x /= 2;
}
}
b.push_back(0);
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
ll res = 1e18;
for(auto it : b)
res = min(check(it), res);
cout<<res<<'\n';
}
E - Identical Parity
我是打表找规律做的,队内的两位数学手没做出来,我先打表打出来了
规律如下,表中 \(1\) 代表 YES
在 \(k\) 为奇数的时候,YES 情况成等差数列分布
\(k = 1, 10\)
\(k = 3, 111010\)
\(k = 5, 11111011100010\)
\(\dots\)
\(1\) 和 \(0\)的数量分部刚好等于 \(k + 1\) ,就很好的去做这个规律了
k: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
n : 1 1
n : 2 0 1
n : 3 0 1 1
n : 4 0 1 1 1
n : 5 0 1 1 1 1
n : 6 0 1 0 1 1 1
n : 7 0 1 1 1 1 1 1
n : 8 0 1 0 1 1 1 1 1
n : 9 0 1 0 1 1 1 1 1 1
n : 10 0 1 0 1 0 1 1 1 1 1
n : 11 0 1 0 1 1 1 1 1 1 1 1
n : 12 0 1 0 1 1 1 1 1 1 1 1 1
n : 13 0 1 0 1 1 1 1 1 1 1 1 1 1
n : 14 0 1 0 1 0 1 0 1 1 1 1 1 1 1
n : 15 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1
n : 16 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1
n : 17 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
n : 18 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1
n : 19 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
n : 20 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
n : 21 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
n : 22 0 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
n : 23 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
n : 24 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
n : 25 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
打表代码(丢失了)
AC代码:
typedef long long ll;
void solve()
{
ll n, k;
cin>>n>>k;
if(n == 1)
{
cout<<"YES\n";
return;
}
if(k == 1)
{
cout<<"NO\n";
return;
}
if(k % 2 == 0)
{
cout<<"YES\n";
return;
}
ll m = (n + 1) / 2;
ll x = k;
ll t = (n - (k - 1)) / (x + 1), r = (n - (k - 1)) % (x + 1);
if(r != 0) t++;
if(r == 0) r = x + 1;
ll d = 1ll + (t - 1) * 2;
// cout<<"t: "<<t<<" m: "<<m<<" r: "<<r<<" d: "<<d<<"\n";
if(t <= m && r <= x + 1 - d)
cout<<"YES\n";
else
cout<<"NO\n";
}
D - Frozen Scoreboard
大模拟
对于要求的总时间先减去已经确定的时间,即是封榜前AC的题的罚时,再枚举 \(S\) 其二进制下第 \(i\) 位为 \(1\) 代表通过第 \(i - 1\) 题,对于状态 \(S\) 封榜后通过的题,总时间减去\(240\) 的基础时间,再用罚时消耗总时间,剩下的时间再用封榜后的60min消耗
并不难,细节多而已,代码的注释更清楚
array<int, 3> a[15];
array<int, 4> res[15];
int n, m;
void solve()
{
int ac, time; cin>>ac>>time;
for(int i = 0; i < m; i++)
{
char opt; cin>>opt;
if(opt == '.')
{
res[i] = {0, 0, 0, 0};
a[i] = {0, 0, 0};
}
else if(opt == '+')
{
int x, y; cin>>x>>opt>>y;
time -= ((x - 1) * 20 + y);
a[i] = {1, x, y};
res[i] = {1, x, y, 0};
}
else if(opt == '?')
{
int x, y; cin>>x>>y;
a[i] = {2, x, y};
res[i] = {2, 0, 0, 0};
}
else if(opt == '-')
{
int x; cin>>x;
a[i] = {3, 0, x};
res[i] = {3, 0, x, 0};
}
}
// cout<<time<<'\n';
for(int S = 0; S < (1 << m); S++)
{
bool ok = true;
int cnt = 0;
for(int i = 0; i < m; i++)
{
if((a[i][0] == 0 || a[i][0] == 3) && ((S >> i) & 1) == 0)
ok = false;
if(a[i][0] == 1 && ((S >> i) & 1) == 0)
ok = false;
}
for(int i = 0; i < m; i++)
{
if(a[i][0] == 1) cnt++;
else if(a[i][0] == 2 && ((S >> i) & 1) == 1) cnt++;
}
if(!ok || ac != cnt) continue;
int T = time;
// 过题时间 罚时次数
for(int i = 0; i < m; i++)
if(((S >> i) & 1) && a[i][0] == 2)
{
T -= 240;
T -= (a[i][2] - a[i][1]) * 20;
}
if(T < 0) continue;
// T 基础罚时
// 优先消耗封榜的罚时 20 倍数
// cout<<T<<'\n';
for(int i = 0; i < m; i++)
if(((S >> i) & 1) && a[i][0] == 2)
{
int c = min(a[i][1] - 1, T / 20);
T -= c * 20;
}
// 消耗罚时时间
for(int i = 0; i < m; i++)
if(((S >> i) & 1) && a[i][0] == 2)
T -= min(59, T);
if(T == 0) //输出答案
{
T = time;
for(int i = 0; i < m; i++)
if(((S >> i) & 1) && a[i][0] == 2)
{
T -= 240;
T -= (a[i][2] - a[i][1]) * 20;
}
// T 基础罚时
// 优先消耗封榜的罚时 20 倍数
for(int i = 0; i < m; i++)
if(((S >> i) & 1) && a[i][0] == 2)
{
int c = min(a[i][1] - 1, T / 20);
T -= c * 20;
res[i] = {1, a[i][2] - a[i][1] + c + 1, 240, 0};
// 封榜前次数 封榜后的第几次
}
// 消耗罚时时间
for(int i = 0; i < m; i++)
if(((S >> i) & 1) && a[i][0] == 2)
{
res[i][0] = 1;
res[i][2] += min(59, T);
T -= min(59, T);
}
cout<<"Yes\n";
for(int i = 0; i < m; i++)
{
if(a[i][0] == 0)
cout<<".\n";
else if(a[i][0] == 1)
cout<<"+ "<<res[i][1]<<"/"<<res[i][2]<<'\n';
else if(a[i][0] == 2 && ((S >> i) & 1) == 1)
cout<<"+ "<<res[i][1]<<"/"<<res[i][2]<<'\n';
else if(a[i][0] == 2 && ((S >> i) & 1) == 0)
cout<<"- "<<a[i][2]<<"\n";
else
cout<<"- "<<a[i][2]<<"\n";
}
return;
}
}
cout<<"No\n";
}
G - Quick Sort
因为递归次数只有 \(\log n\) 次,则交换次数最多 \(n \log n\) 次,所以可以直接做
每个数字只会出现 \(1\) 次,用数据结构维护区间最大值,区间最小值即可
细节要注意的地方:par函数内,找到的下标不在范围内,那么我们就要找更大或更小的,为什么呢?因为 \(pivot\) swap了,导致 \(\geq\) 或 \(\leq\) \(pivot\)不在范围内
const int N = 5e5 + 10;
int n, a[N], res;
struct segtree
{
int w1, w2;
}seg[N * 4];
void update(int id)
{
seg[id].w1 = max(seg[id * 2].w1, seg[id * 2 + 1].w1);
seg[id].w2 = min(seg[id * 2].w2, seg[id * 2 + 1].w2);
}
void build(int id, int l, int r)
{
seg[id] = {0, 0};
if(l == r)
{
seg[id] = {a[l], a[l]};
return;
}
int mid = (l + r) >> 1;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
update(id);
}
void change(int id, int l, int r, int pos)
{
if(l == r)
{
seg[id] = {a[l], a[l]};
return;
}
int mid = (l + r) >> 1;
if(pos <= mid)
change(id * 2, l, mid, pos);
else
change(id * 2 + 1, mid + 1, r, pos);
update(id);
}
int query1(int id, int l, int r, int val)
{
if(l == r)
return l;
int mid = (l + r) >> 1;
if(seg[id * 2].w1 >= val)
return query1(id * 2, l, mid, val);
else
return query1(id * 2 + 1, mid + 1, r, val);
}
int query2(int id, int l, int r, int val)
{
if(l == r)
return l;
int mid = (l + r) >> 1;
if(seg[id * 2 + 1].w2 <= val)
return query2(id * 2 + 1, mid + 1, r, val);
else
return query2(id * 2, l, mid, val);
}
int par(int l, int r)
{
int tl = l - 1, tr = r + 1;
int val = a[(l + r) / 2];
while(1)
{
int p1 = query1(1, 1, n, val);
if(p1 <= tl) p1 = query1(1, 1, n, val + 1);
int p2 = query2(1, 1, n, val);
if(p2 >= tr) p2 = query2(1, 1, n, val - 1);
if(p1 >= p2)
return p2;
swap(a[p1], a[p2]);
change(1, 1, n, p1); change(1, 1, n, p2);
res++;
tl = p1, tr = p2;
}
}
void quicksort(int l, int r)
{
if(l >= r || l < 0 || r < 0) return;
int p = par(l, r);
quicksort(l, p);
quicksort(p + 1, r);
}
void solve()
{
cin>>n;
for(int i = 1; i <= n; i++)
cin>>a[i];
res = 0;
build(1, 1, n);
quicksort(1, n);
cout<<res<<'\n';
return;
}
C - DFS Order 2
回退背包,第一次见耶
2022 ICPC 济南站 C (回退背包) - 严格鸽的文章 - 知乎
typedef long long ll;
const int mod = 998244353;
const int N = 500 + 10;
ll qmi(ll a, ll b, ll mod)
{
ll ans = 1 % mod;
while(b)
{
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
vector<int> e[N];
int n;
ll son[N], sz[N], fac[N];
ll f[N][N], g[N][N], h[N];
ll dfs1(int u, int from)
{
son[u] = 0;
sz[u] = 1;
ll res = 1;
for(auto v : e[u])
{
if(v == from) continue;
res = (res * dfs1(v, u)) % mod;
sz[u] += sz[v];
son[u]++;
}
res = (res * fac[son[u]]) % mod;
return res;
}
void dfs(int u, int from)
{
memset(g, 0, sizeof g);
g[0][0] = 1;
for(auto v : e[u])
{
if(v == from) continue;
for(int i = son[u]; i >= 1; i--)
for(int j = sz[u]; j >= sz[v]; j--)
g[i][j] = (g[i][j] + g[i - 1][j - sz[v]]) % mod;
}
for(auto v : e[u])
{
if(v == from) continue;
for(int i = 1; i <= son[u]; i++)
for(int j = sz[v]; j <= sz[u]; j++)
g[i][j] = (g[i][j] - g[i - 1][j - sz[v]] + mod) % mod;
memset(h, 0, sizeof h);
for(int i = 0; i <= son[u] - 1; i++)
for(int k = 0; k <= sz[u]; k++)
h[k + 1] = (h[k + 1] + (fac[i] * fac[son[u] - 1 - i] % mod) * g[i][k]) % mod;
for(int i = 1; i <= n; i++)
for(int k = 1; k <= n; k++)
if(i + k <= n)
f[v][i + k] = (f[v][i + k] + f[u][i] * h[k]) % mod;
for(int i = son[u]; i >= 1; i--)
for(int j = sz[u]; j >= sz[v]; j--)
g[i][j] = (g[i][j] + g[i - 1][j - sz[v]]) % mod;
}
for(auto v : e[u])
{
if(v == from) continue;
dfs(v, u);
}
}
void solve()
{
cin>>n;
fac[0] = 1;
for(int i = 1; i < N; i++) fac[i] = (fac[i - 1] * i) % mod;
for(int i = 1; i <= n - 1; i++)
{
int u, v; cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
f[1][1] = dfs1(1, 0);
dfs(1, 0);
for(int i = 1; i <= n; i++)
{
ll sum = 0;
for(int k = 1; k <= n; k++) sum += f[i][k];
sum %= mod;
ll inv = qmi(sum, mod - 2, mod);
for(int k = 1; k <= n; k++)
cout<<(f[i][k] * f[1][1] % mod) * inv % mod<<" ";
cout<<'\n';
}
return;
}
- International Programming Collegiate Contest MKAEDGCinternational programming collegiate contest programming collegiate provincial contest programming collegiate jiangsu contest programming collegiate mianyang contest programming collegiate contest guilin programming collegiate shenzhen contest programming collegiate shanghai contest programming collegiate contest harbin programming collegiate codeforces contest programming collegiate contest weihai