当前位置：首页 > news >正文

2024 ICPC National Invitational Collegiate Programming Contest, Wuhan Site 2024 ICPC 邀请赛武汉

news 2026/6/22 21:59:21

I. Cyclic Apple Strings

找第一个 \(1\) 的位置，后面的每个连续是 \(0\) 的段，每个都可以用一次交换解决

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;void solve(){string s;cin>>s;int n=s.size();s=" "+s;int ans=0,pos=-1;vector<int> stk;for(int i=1;i<=n;i++){if(i==1 || (s[i]-'0')!=stk.back()){stk.push_back(s[i]-'0');}}for(int i=0;i<stk.size();i++){if(stk[i]==1){pos=i;break;}}if(pos==-1){cout<<0;return;}for(int i=pos+1;i<stk.size();i++){if(stk[i]==0) ans++;}cout<<ans;}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}
}

K. Party Games

手玩一下样例，大胆 guess

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;void solve(){int n;cin>>n;n%=4;if(n==1 || n==0){cout<<"Fluttershy\n";}else{cout<<"Pinkie Pie\n";}
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;cin>>ct;while(ct--){solve();}
}

B. Countless Me

最多 \(n\) 次操作，所以等价于，把 \(sum\) 随意分给 \(n\) 个数

从高位到低位考虑，如果当前位能是 \(0\) 就是 \(0\)，否则全部置为 \(1\)，这样一定最优

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;void solve(){int n;cin>>n;int sum=0;vector<int> a(n+1);for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];a[i]=0;}for(int j=32;j>=0;j--){if(n*((1ll<<j)-1) < sum){int val=1ll<<j;for(int i=1;i<=n;i++){if(sum>=val){sum-=val;a[i]|=val;}}}}int ans=0;for(int i=1;i<=n;i++){ans|=a[i];}cout<<ans;}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}
}

F. Custom-Made Clothes

去二分答案

对于一个 \(x\)，从第一列到最后一列，第一个小于 \(x\) 的位置的行数，一定是越来越小的，所以 \(check\) 的复杂度就是 \(O(n)\) 扫一遍

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;int q(int i,int j,int x){cout<<"? "<<i<<" "<<j<<" "<<x<<endl;int ans;cin>>ans;return ans;
}void solve(){int n,k;cin>>n>>k;// 有多少个值是 <=x 的auto sum=[&](int x)-> int {int ans=0;int pos=n;for(int i=1;i<=n;i++){while(pos>=1 && q(pos,i,x)==0) pos--;ans+=pos; }return ans;};int l=1,r=n*n;while(l<r){int mid=(l+r)/2;if(sum(mid)<=n*n-k) l=mid+1;else r=mid;}cout<<"! "<<l<<endl;}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}
}

D. ICPC

可以先处理出来，不反转的结果

然后再处理反转一次的结果。反转多次一定不优

DP 的过程可以优化，最后复杂度 \(O(n^2)\)

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;int f[5010][10010][2];void solve(){int n;cin>>n;vector<int> a(n+1),pre(n+1);for(int i=1;i<=n;i++){cin>>a[i];pre[i]=a[i]+pre[i-1];}auto sum=[&](int l,int r)->int {l=max(1ll,l);r=min(n,r);return pre[r]-pre[l-1];};for(int i=1;i<=n;i++){for(int j=1;j<=2*n;j++){f[i][j][0]=sum(i-j,i);f[i][j][1]=sum(i,i+j);}}for(int i=1;i<=n;i++){for(int j=1;j<=2*n;j++){f[i][j][1]=max(f[i-1][j-1][1],f[i][j][1]);}}for(int i=n;i>=1;i--){for(int j=1;j<=2*n;j++){f[i][j][0]=max(f[i+1][j-1][0],f[i][j][0]);}}int ans=0;for(int i=1;i<=n;i++){int now=0;for(int j=1;j<=2*n;j++){now^=j*max(f[i][j][0],f[i][j][1]);}now+=i;ans^=now;}cout<<ans;}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}
}

E. Boomerang

首先，对于每个 \(t:[1,2*n]\) 处理出来一个直径长度。

然后让每个 \(k\) 去找到一个最合适的 \(t\) 即可

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;struct HLD {int n, root;vector<vector<int>> adj;  // 邻接表vector<int> sz, dep, fa, son;      // 子树大小、深度、父节点、重儿子vector<int> top, id, rev, seq, w;  // 链顶、DFN编号、逆向映射、权值线性化数组、原权值int timer;// 构造函数，传入节点数HLD(int _n = 0) : n(_n) {adj.assign(n+1, {});sz.assign(n+1, 0);dep.assign(n+1, 0);fa.assign(n+1, 0);son.assign(n+1, 0);top.assign(n+1, 0);id.assign(n+1, 0);rev.assign(n+1, 0);seq.assign(n+1, 0);w.assign(n+1, 0);timer = 0;}// 添加一条无向边 u-vvoid addEdge(int u, int v){adj[u].push_back(v);adj[v].push_back(u);}// 设置节点 u 的初始权值void setWeight(int u, int v){ w[u] = v; }/*** dfs1：计算每个节点的子树大小和重儿子* u：当前节点，p：父节点*/void dfs1(int u, int p){fa[u] = p;dep[u] = dep[p] + 1;sz[u] = 1;son[u] = 0;for (int v : adj[u]) if (v != p) {dfs1(v, u);sz[u] += sz[v];// 选出最大的子树作为重儿子if (!son[u] || sz[v] > sz[son[u]]) son[u] = v;}}/*** dfs2：沿重链深入，分配 DF* u：当前节点，t：当前链顶节点*/void dfs2(int u, int t){top[u] = t;id[u] = ++timer;rev[timer] = u;seq[timer] = w[u];// 先遍历重儿子，保持链上连续if (son[u]) dfs2(son[u], t);// 再遍历其他轻儿子，各自开新链for (int v : adj[u]) if (v != fa[u] && v != son[u]) {dfs2(v, v);}}/*** lca：计算 u 和 v 的最近公共祖先*/int lca(int u, int v){while (top[u] != top[v]){if (dep[top[u]] > dep[top[v]]) u = fa[top[u]];else v = fa[top[v]];}return dep[u] < dep[v] ? u : v;}/*** dist：计算 u 和 v 之间的树上距离（边权为 1）*/int dist(int u, int v){return dep[u] + dep[v] - 2 * dep[lca(u, v)];}};void solve(){int n,r,t0;cin>>n;HLD hld(n);for(int i=1;i<n;i++){int u,v;cin>>u>>v;hld.addEdge(u,v);}cin>>r>>t0;hld.dfs1(r,0);hld.dfs2(r,r);vector<vector<int>> dep(n+1);for(int u=1;u<=n;u++){dep[hld.dep[u]-1].push_back(u);}int u1=r,u2=r,now=0;vector<int> len(2*n+1);for(int t=1;t<=2*n;t++){if(t<=n){for(auto v:dep[t]){int d1=hld.dist(u1,v);int d2=hld.dist(u2,v);if(d1>now){u2=v;now=d1;}else if(d2>now){u1=v;now=d2;}}}len[t]=now;}vector<int> ans(n+1);int t=2*n;for(int k=1;k<=n;k++){while(t-1>=t0 && k*(t-1-t0)>=(len[t-1]+1)/2){t--;}   ans[k]=t;}for(int i=1;i<=n;i++){cout<<ans[i]<<" ";}}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}
}

首先，因为偶数 + 奇数 = 奇数

所以所有偶数最多会被处理一次

从大到小处理所有偶数，想办法去凑一个 \(x+1\) 或 \(x-1\) 出来即可

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;void solve(){int n;cin>>n;map<int,int> mp;vector<int> a(n+1);for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]]++;}sort(a.begin()+1,a.end(),greater<int>());auto f=[&](int x)->bool {vector<int> t;auto check=[&](auto check,int x)-> bool {if(mp[x]>0){mp[x]--;t.push_back(x);return 1;}if(x&1){return (check(check,x/2) && check(check,(x+1)/2));}return 0;};if(check(check,x)==0){for(auto val:t){mp[val]++;}return 0;}return 1;};for(int i=1;i<=n;i++){if(a[i]%2==0){if(mp[a[i]]==0) continue;mp[a[i]]--;//1. 尝试找 a[i]+1if(f(a[i]+1)){mp[a[i]*2+1]++;}else if(f(a[i]-1)){mp[a[i]*2-1]++;}else mp[a[i]]++;}}vector<int> ans;for(auto [val,cnt]:mp){for(int i=cnt;i>=1;i--){ans.push_back(val);}}cout<<ans.size()<<endl;for(auto val:ans){cout<<val<<" ";}
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}
}

查看全文

http://www.jsqmd.com/news/594109/