A.扭蛋
思维。
考虑最坏情况，一定是每次都获得数量最多的那个扭蛋，那除掉一个之后多余的数可以拿来换数量少的扭蛋，若当前 \(a_i - 1\) 加上之前存的多余的扭蛋数大于等于了 \(i-1\) ，说明后面的扭蛋都可以换。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define endl '\n'
const int N=3e5+10, mod=998244353;
const int B=32;int n,k;
int a[N],b[N];
vector<PII>q,ans,a1;void solve() {cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];b[i]=0;}sort(a+1,a+1+n);int s=0,p=0;for(int i=n;i>=1;i--){if((p+a[i]-1)/k>=i-1){cout<<s+1+max(0ll,((i-1)*k-p))<<endl;return;}else{p+=a[i]-1;s+=a[i];}}}signed main() {
// freopen("in.txt", "r", stdin);ios::sync_with_stdio(false), cin.tie(0);int t=1;cin>>t;while (t--){solve();}
}
B. 精神胜利
最短路。
因为边的朝向是独立的，且 \(50\%\) 概率，所以当点数越多的时候，两个点之间的距离期望肯定不会很大，所以最短路松弛的过程大于一定长度后就不必继续了，为了限制边的松弛复杂度，这里对每个点最多松弛 \(5\times 10^4\) 次即可。
点击查看代码
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define endl '\n'
#define LL long long
const int N=5e3+4;
int n,Q;
int dist[N][N];
vector<int>g[N];
void solve() {cin >> n >> Q;memset(dist, 0x3f, sizeof dist);for (int i = 1; i <= n; ++i) {for (int j = i + 1; j <= n; ++j) {char x;cin >> x;if (x == '1') {g[i].push_back(j);} else g[j].push_back(i);}}for (int st = 1; st <= n; ++st) {int cnt = 0;queue<int> q;q.push(st);dist[st][st] = 0;while (q.size()) {auto u = q.front();q.pop();if (cnt >= 5000 * 10)break;if (dist[st][u] > 10)continue;for (auto v: g[u]) {cnt++;if (cnt >= 5000 * 10)break;if (dist[st][u] + 1 < dist[st][v]) {dist[st][v] = dist[st][u] + 1;q.push(v);}}}}while (Q--){int x,y;cin>>x>>y;if(dist[x][y]>=11){cout<<"-1\n";}else{cout<<dist[x][y]-1<<endl;}}
}signed main() {ios::sync_with_stdio(false), cin.tie(0);int t=1;
// cin>>t;while (t--){solve();}
}
C. 虫洞
双指针，线段树。
将多个区间分组，要使得分成的每组内的区间不产生交集，有个结论是，将这些区间进行差分后做个前缀和，前缀最大值就是至少能分成的组数。
所以可以使用双指针维护区间长度，使用线段树动态维护区间差分，区间加区间取 \(Max\)，判断是否小于等于 \(k\) 即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define LL long long
#define PII pair<int,int>
#define endl '\n'
const int N=3e5+10, mod=998244353,INF=1e9;
const int B=32;int w[N],n,m;
struct adt {int l,r;int ma,add,cover;
}tr[N << 2];
// 左子树
inline int ls(int p) {return p<<1; }
// 右子树
inline int rs(int p) {return p<<1|1; }
// 向上更新
void pushup(int u) {tr[u].ma = max(tr[ls(u)].ma, tr[rs(u)].ma);
}void coverdown(int u) {auto &root = tr[u], &right = tr[rs(u)], &left = tr[ls(u)];if(root.cover != -INF) {left.add = right.add = 0;left.ma = right.ma = root.cover;left.cover = right.cover = root.cover;root.cover = -INF;}
}
void sumdown(int u) {auto &root = tr[u], &right = tr[rs(u)], &left = tr[ls(u)];if(root.add) {coverdown(u);left.ma += root.add; right.ma += root.add;left.add += root.add; right.add += root.add;root.add = 0;}
}
void pushdown(int u) {coverdown(u); sumdown(u);
}
// 建树
void build(int u, int l, int r) {if(l == r) tr[u] = {l, r, w[r], 0, -INF};else {tr[u] = {l,r, 0, 0, -INF}; // 容易忘int mid = l + r >> 1;build(ls(u), l, mid), build(rs(u), mid + 1, r);pushup(u);}
}
// 修改
void modify_add(int u, int l, int r, int d) {if(tr[u].l >= l && tr[u].r <= r) {coverdown(u);tr[u].ma += d;tr[u].add += d;}else {pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify_add(ls(u), l ,r, d);if(r > mid) modify_add(rs(u), l, r, d);pushup(u);}
}
void modify_cover(int u, int l, int r, int d) {if(tr[u].l >= l && tr[u].r <= r) {tr[u].add = 0;tr[u].ma = d;tr[u].cover = d;} else {pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify_cover(ls(u), l, r, d);if(r > mid) modify_cover(rs(u), l, r, d);pushup(u);}
}
// 查询
LL query(int u, int l, int r) {if(tr[u].l >= l && tr[u].r <= r) {return tr[u].ma;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;LL res = -INF;if(l <= mid) res = query(ls(u), l, r);if(r > mid ) res =max(res, query(rs(u), l, r));return res;
}int k;
PII a[N],b[N];
vector<PII>q,ans,a1;void solve() {cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i].first>>a[i].second;}int ans=1;int r=1;build(1,1,n);int s=1;modify_add(1,a[1].first,a[1].second,1);for(int l=1;l<=n;l++){while(r+1<=n&&s<=k){modify_add(1,a[r+1].first,a[r+1].second,1);s=query(1,1,n);r++;}if(s>k){modify_add(1,a[r].first,a[r].second,-1);r--;}ans=max(ans,r-l+1);modify_add(1,a[l].first,a[l].second,-1);s=query(1,1,n);}cout<<ans<<endl;
}signed main() {
// freopen("in.txt", "r", stdin);ios::sync_with_stdio(false), cin.tie(0);int t=1;cin>>t;while (t--){solve();}
}
D. 挑战图同构
期望，最短路。
神秘猜猜题。
Vp 时猜的，大概就是当进行有限次最短路后，后面的最短路都趋于相同了，所以只要枚举一定点数进行最短路比较后即可得出答案。
点击查看代码
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define endl '\n'
#define LL long long
const int N=1e5+4;
int n,m1,m2;
int dist1[N],dist2[N];
int vis1[N];
int vis2[N];
vector<array<int,2>>g1[N],g2[N];
const int INF=1e9+3;
void solve() {cin >> n >> m1 >> m2;for (int i = 1; i <= n; ++i) {g1[i].clear();g2[i].clear();dist1[i] = INF, dist2[i] = INF;vis1[i] = 0;vis2[i] = 0;}for (int i = 0; i < m1; ++i) {int x, y, w;cin >> x >> y >> w;g1[x].push_back({y, w});g1[y].push_back({x, w});}for (int i = 0; i <m2 ; ++i) {int x, y, w;cin >> x >> y >> w;g2[x].push_back({y, w});g2[y].push_back({x, w});}for (int st = 1; st <= min(n, 30); ++st) {for (int i = 1; i <= n; ++i) {dist1[i] = INF;dist2[i] = INF;vis1[i] = 0;vis2[i] = 0;}dist1[st] = 0;dist2[st] = 0;priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> q;q.push({0, st});while (q.size()) {auto [w, u] = q.top();q.pop();if (vis1[u])continue;vis1[u] = 0;for (auto [v, w1]: g1[u]) {int nw = max(w, w1);if (dist1[v] > nw) {dist1[v] = nw;q.push({nw, v});}}}q.push({0, st});while (q.size()) {auto [w, u] = q.top();q.pop();if (vis2[u])continue;vis2[u] = 0;for (auto [v, w1]: g2[u]) {int nw = max(w, w1);if (dist2[v] > nw) {dist2[v] = nw;q.push({nw, v});}}}int vis=1;for (int i = 1; i <=n ; ++i) {if(dist1[i]!=dist2[i]){vis=0;break;}}if(!vis){cout<<"NO\n";return;}}cout<<"YES\n";}signed main() {ios::sync_with_stdio(false), cin.tie(0);int t=1;cin>>t;while (t--){solve();}
}
E. 魔法阵
队友写的。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define LL long long
const int mod=998244353;void solve() {int n, k;cin >> n >> k;vector<int> c(n + 1);vector<int> a(n + 1);vector<int> mp[k + 3];for (int i = 1; i <= n; ++i) {cin >> c[i];mp[c[i]].push_back(i);}for (int i = 1; i <= n; ++i) {cin >> a[i];}int ans=0;for (int i = 1; i <= k; ++i) {for (int j = 1; j <= k; ++j) {if (i == j)continue;auto ai = mp[i];auto aj = mp[j];vector<array<int, 2>> Q;std::reverse(aj.begin(), aj.end());std::reverse(ai.begin(), ai.end());while (ai.size() and aj.size()) {if (ai.back() < aj.back()) {Q.push_back({ai.back(), 0});ai.pop_back();} else {Q.push_back({aj.back(), 1});aj.pop_back();}}while (ai.size()){Q.push_back({ai.back(), 0});ai.pop_back();}while (aj.size()){Q.push_back({aj.back(), 1});aj.pop_back();}vector<int> f(4);//A AB ABA ABAB;for (auto [idx, op]: Q) {
// cout<<idx<<' '<<op<<endl;int w = a[idx];
// cout<<idx<<' '<<w<<' '<<op<<' '<<f[0]<<' '<<f[1]<<' '<<f[2]<<' '<<f[3]<<endl;if (op == 0) {f[0] += w;f[2] += f[1] * w % mod;f[0] %= mod;f[2] %= mod;} else {f[1] += f[0] * w % mod;f[1] %= mod;f[3] += f[2] * w % mod;f[3] %= mod;}}
// cout<<endl;ans+=f[3];ans%=mod;}}cout<<ans<<endl;
}signed main() {ios::sync_with_stdio(false), cin.tie(0);int t=1;
// cin>>t;while (t--){solve();}
}
G. 玻璃碎晶
思维。
尽量分成 \(3\)，如果模 \(3\) 之后为 \(2\)，可以分配给一个 \(3\) 凑成 \(5\) 即可，如果为 \(1\)，需要看是否有两个 \(3\) 来凑成 \(7\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
//#define int unsigned long long
#define endl '\n'
#define int long longvoid solve() {int n;cin>>n;if(n==2){cout<<"-1\n";return;}int cnt=n/3;int yu=n%3;if(yu==0 or yu==2){cout<<cnt<<endl;}else{if(cnt>=2){cout<<cnt-1<<endl;}else{cout<<"-1\n";}}}signed main() {ios::sync_with_stdio(false), cin.tie(0);int t=1;cin>>t;while (t--){solve();}
}
H. 珍珠链
队友写的，看起来是数据结构。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
//#define int unsigned long long
#define endl '\n'
//#define int long long
#define int long long
#define N 500010
#define LD (o<<1)
#define RD (o<<1|1)
#define INF 0x7fffffff
struct Node{int l,r;int maxv,add;
};
int n,b,k;
int pre[200005];
struct Tree{Node t[N<<2];int a[N];inline void pushup(Node &o,Node &ld,Node &rd){o.maxv=min(ld.maxv,rd.maxv);}inline void pushdown(Node &o,Node &ld,Node &rd){ld.add+=o.add;ld.maxv+=o.add;rd.add+=o.add;rd.maxv+=o.add;o.add=0;}void build(int o,int l,int r){t[o].l=l;t[o].r=r;t[o].add=0;if(l==r){t[o].maxv=a[l];return;}int mid=(l+r)>>1;build(LD,l,mid);build(RD,mid+1,r);pushup(t[o],t[LD],t[RD]);}void update(int o,int l,int r,int v){if(l<=t[o].l&&t[o].r<=r){t[o].add+=v;t[o].maxv+=v;return;}pushdown(t[o],t[LD],t[RD]);int mid=(t[o].l+t[o].r)>>1;if(mid>=l)update(LD,l,r,v);if(mid<r)update(RD,l,r,v);pushup(t[o],t[LD],t[RD]);}int query(int o,int l,int r){if(l<=t[o].l&&t[o].r<=r)return t[o].maxv;pushdown(t[o],t[LD],t[RD]);int ans=LLONG_MAX,mid=(t[o].l+t[o].r)>>1;if(mid>=l)ans=min(ans,query(LD,l,r));if(mid<r)ans=min(ans,query(RD,l,r));pushup(t[o],t[LD],t[RD]);return ans;}
}A;
void solve() {cin >> n;int vis=0;for (int i = 1; i <= n; ++i) {int x;cin >> x;A.a[i] = x - i;
// cout<<A.a[i]<<' ';if(A.a[i]<0){vis=1;}}
// cout<<endl;if(vis){cout<<"-1\n";return;}A.build(1, 1, n);int ans = 0;int idx = 0;for (int i = 1; i <= n; ++i) {idx++;
// cout<<i<<' '<<A.query(1,i,i)<<endl;if (A.query(1, i, i) == 0) {continue;}int mi = A.query(1, i, n);A.update(1, i, n, -mi);idx += mi;int sy = A.query(1, i, i);ans -= mi;ans = max(0ll, ans);ans += sy;}
// cout<<ans<<' '<<idx<<endl;ans+=idx;cout<<ans<<endl;
}signed main() {ios::sync_with_stdio(false), cin.tie(0);int t=1;cin>>t;while (t--){solve();}
}
K. 不许偷吃
贪心。
首先可以想到，一个 \(3\) 可以后面跟一个 \(1\)，一个 \(2\) 后面可以跟两个 \(1\)，在此基础上肯定是能放 \(1\) 就尽量这样放。
其次当 \(1\) 放完后对于 \(3\) 来说，就不能放超过三个 \(3\)，这样会在第三个 \(3\) 后面形成 \(1\)，所以需要 \(3,3,2,3,3,2...\) 这样放。
即当 \(1\) 放完后，需要满足 \(\frac{cnt_3}{2} - 1 > cnt_2\)，减 \(1\) 是因为结尾两个 \(3\) 可以不必配 \(2\)。
点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;void solve() {int n;cin >> n;vector<int> a(n + 1);vector cnt(4, vector<int>());for (int i = 1; i <= n; i += 1) {cin >> a[i];cnt[a[i] % 4].push_back(i);}int ok = 2 * (int)cnt[2].size() + (int)cnt[3].size();if ((int)cnt[1].size() > ok) {cout << "-1\n";return ;}int now = 0;vector<int> ans;for (int i : {3, 2}) {while (cnt[i].size()) {if (cnt[1].empty() && i == 3) {now += 1;}if (cnt[1].empty() && i == 3) {if (cnt[3].size() / 2 > cnt[2].size() + 1) {cout << "-1\n";return;}}ans.push_back(cnt[i].back());cnt[i].pop_back();int k = 4 - i;while (cnt[1].size() && k) {k -= 1;ans.push_back(cnt[1].back());cnt[1].pop_back();}if (now && now % 2 == 0 && i == 3 && cnt[2].size()) {ans.push_back(cnt[2].back());cnt[2].pop_back();}}}for(int x : ans){cout << x << " ";}while (cnt[0].size()) {cout << cnt[0].back() << " ";cnt[0].pop_back();}cout << "\n";
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}
L. 羽球比赛
模拟。
点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int a, b;cin >> a >> b;if (a >= 21 && a - b >= 2 || a == 30) {cout << "Alice\n";}else if (b == 30 || b >= 21 && b - a >= 2) {cout << "Bob\n";}else {cout << "Underway\n";}return 0;
}