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

The 2024 ICPC Asia Shanghai Regional Contest

Preface

马上要 25 年 Regional 了才猛然发现去年的 IC Regional 还有上海和杭州两场没 VP 过,最近找机会补了

这场前期我和祁神在签到题 C 上坐牢一小时,本来以为要崩了,结果中期题做的还都挺顺

最后 4h 的时候过了 7 题,剩下的计数 F 是做不来一点,遂让祁神去写几何

赛后发现这题做法全对但精度卡的飞起,赛场上无人通过可还行


B. Basic Graph Algorithm

徐神在我对着 C 红温的时候写的,我题都没看

#include <bits/stdc++.h>constexpr int $n = 300005;int n, m;
std::set<int> out[$n];
bool vis[$n];
int p[$n], p_cur = 0;int ans = 0;
std::vector<std::pair<int, int>> hkr;void dfs() {int cur = p[p_cur];vis[cur] = 1;while(out[cur].size() > 0) {if(p_cur == n) return ;int nxt = p[p_cur + 1];if(out[cur].count(nxt)) {out[cur].erase(nxt);p_cur += 1;dfs();} else {auto it = out[cur].begin();while(it != out[cur].end() && vis[*it]) out[cur].erase(it++);if(it == out[cur].end()) return ;ans += 1;p_cur += 1;hkr.emplace_back(cur, p[p_cur]);dfs();}}return ;
}int main() {std::ios::sync_with_stdio(false);std::cin >> n >> m;for(int i = 0, u, v; i < m; ++i) {std::cin >> u >> v;out[u].insert(v);out[v].insert(u);}for(int i = 1; i <= n; ++i) std::cin >> p[i];while(p_cur < n) ++p_cur, dfs();std::cout << ans << char(10);for(auto [u, v]: hkr) std::cout << u << " " << v << char(10);return 0;
}

C. Conquer the Multiples

考虑两人都可以使用同样的贪心策略:

  • 当前 \(x\) 为奇数,则优先取 \(2x\),若不存在这样的数取 \(x\)
  • 当前 \(x\) 为偶数,则优先取 \(x\),若 \(x\) 已经被取了就该取 \(2x\)

分析一波会发现第一个遇到区间内的奇数 \(k\),且 \(2k\) 在区间内的人一定可以获胜,因为它可以决定操作次数的奇偶性

如果不存在这样的数只用判区间长度的奇偶性即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,l,r;
int main()
{for (scanf("%d",&t);t;--t){scanf("%d%d",&l,&r);int odd=l;if (odd%2==0) ++odd;if (odd>r||2*odd>r) puts((r-l)%2?"Bob":"Alice");else puts((odd-l)%2?"Bob":"Alice");}return 0;
}

D. Decrease and Swap

又是队友秒的题,我题目都没看

#include <bits/stdc++.h>bool work() {int n; std::cin >> n;std::string s; std::cin >> s;int l = 0, c1 = 1;while(l < n && s[l] == '0') l += 1;if(l == n) return true;int r = l + 1;for(;;) {while(r < n && s[r] == '0') r += 1;if(r == n) break;if(r - l <= c1 * 2) c1 += 1;else l = r, c1 = 1;r += 1;}return l <= n - 4 || l == n - 3 && c1 == 1;
}int main() {std::ios::sync_with_stdio(false);int T; std::cin >> T; while(T--) std::cout << (work() ? "Yes\n" : "No\n");return 0;
}

E. Equal Measure

最遥控的一集,我题都没看队友就告诉我结论,然后我上去写写写就一遍过了

首先对图进行点双缩点,对于每个点双,其可能的形态只有:

  • 孤点或两点一边:这种 Case 里不存在环可以直接忽略;
  • 简单环:记录下环长即可;
  • “西瓜”(徐神给这类图起的名字):存在两个度数大于 \(2\) 的点,它们之间存在若干条等长的简单路径;

要验证一个点双分量是不是上述几种情况十分容易,直接分讨即可

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<set>
#define RI register int
#define CI const int&
using namespace std;
const int N=500005,INF=1e9;
int t,n,m,x[N],y[N],dfn[N],low[N],idx,stk[N],deg[N],dis[N],top,len,vcccnt;
vector <int> v[N],nv[N],vcc[N],edges[N]; set <int> bel[N];
inline void Tarjan(CI now,CI fa=0)
{low[now]=dfn[now]=++idx;stk[++top]=now; int son=0;for (auto to:v[now])if (!dfn[to]){++son; Tarjan(to,now);low[now]=min(low[now],low[to]);if (low[to]>=dfn[now]){vcc[++vcccnt].push_back(now);bel[now].insert(vcccnt);do{vcc[vcccnt].push_back(stk[top]);bel[stk[top]].insert(vcccnt);} while (stk[top--]!=to);}} else if (to!=fa) low[now]=min(low[now],dfn[to]);if (fa==0&&son==0) vcc[++vcccnt].push_back(now);
}
int main()
{for (scanf("%d",&t);t;--t){scanf("%d%d",&n,&m);for (RI i=1;i<=n;++i){dfn[i]=deg[i]=0; v[i].clear(); bel[i].clear();nv[i].clear(); vcc[i].clear(); edges[i].clear();}for (RI i=1;i<=m;++i){scanf("%d%d",&x[i],&y[i]);v[x[i]].push_back(y[i]);v[y[i]].push_back(x[i]);}idx=top=vcccnt=0; len=-1;for (RI i=1;i<=n;++i)if (!dfn[i]) Tarjan(i,0);for (RI i=1;i<=m;++i){int u=x[i],v=y[i];if ((int)bel[u].size()>(int)bel[v].size()) swap(u,v);for (auto id:bel[u])if (bel[v].count(id)){edges[id].push_back(i);break;}}// for (RI k=1;k<=vcccnt;++k)// {//     printf("vcc(%d):\n",k);//     printf("vertices: ");//     for (auto x:vcc[k]) printf("%d ",x); putchar('\n');//     printf("egdes: ");//     for (auto id:edges[k]) printf("(%d,%d) ",x[id],y[id]); putchar('\n');// }bool flag=1;auto upt=[&](CI mv){if (len==-1) len=mv;else if (len!=mv) flag=0;};for (RI k=1;k<=vcccnt&&flag;++k){for (auto id:edges[k]){++deg[x[id]]; ++deg[y[id]];nv[x[id]].push_back(y[id]);nv[y[id]].push_back(x[id]);}int cnt[4]={0,0,0,0};for (auto x:vcc[k])if (deg[x]<=2) ++cnt[deg[x]]; else ++cnt[3];if (cnt[0]==1&&cnt[1]==0&&cnt[2]==0&&cnt[3]==0){//single vertex} elseif (cnt[0]==0&&cnt[1]==2&&cnt[2]==0&&cnt[3]==0){//two vertices, single edge} elseif (cnt[0]==0&&cnt[1]==0&&cnt[2]==(int)vcc[k].size()&&cnt[3]==0){// printf("single cycle %d\n",k);upt(cnt[2]); // single cycle} elseif (cnt[0]==0&&cnt[1]==0&&cnt[2]==(int)vcc[k].size()-2&&cnt[3]==2){// printf("watermelon %d\n",k);vector <int> key;for (auto x:vcc[k])if (deg[x]>2) key.push_back(x);queue <int> q;for (auto x:vcc[k]) dis[x]=INF;dis[key[0]]=0; q.push(key[0]);while (!q.empty()){int now=q.front(); q.pop();for (auto to:nv[now]){if (dis[to]==INF){dis[to]=dis[now]+1;q.push(to);}if (to==key[1]&&dis[to]!=dis[now]+1) flag=0;}}upt(2*dis[key[1]]); //watermelon} else flag=0;for (auto id:edges[k])--deg[x[id]],--deg[y[id]];for (auto x:vcc[k]) nv[x].clear();}puts(flag?"Yes":"No");}return 0;
}

G. Geometry Task

看到中位数就想到套路二分,放在这题上就是要检验是否能找出若干个纵坐标大于某个值的交点

把斜线按照斜率正负分为两类,考虑 \(x=c\) 的直线排序后一定存在一个分界点,使得前半部分和斜率为负的匹配,后半部分和斜率为正的匹配

\(a_i<0\) 的直线为例,它能匹配的符合要求的 \(x=c\) 的直线一定是一段前缀区间,因此可以排序后贪心;\(a_i>0\) 的情况同理

注意特判 \(a_i=0\) 的直线;同时二分边界要设为 \(\pm 2\times 10^{18}\)

#include<bits/stdc++.h>
using namespace std;
#define int long longconst int N=100005;int n, a[N], c[N], b[N], pre[N], suf[N];
vector<int> L, R;const long double EPS=1e-12;int check(int yc) {int cnt = 0;for (int i=1; i<=n; ++i) {if (a[i] < 0) L.push_back(floor(1.0L*(yc-b[i])/a[i]+EPS));else if (a[i] > 0) R.push_back(ceil(1.0L*(yc-b[i])/a[i]-EPS));else if (b[i] >= yc) ++cnt;}// if (yc==9)// {//     printf("c = \n");//     for (int i=1;i<=n;++i) printf("%lld%c",c[i]," \n"[i==n]);//     printf("L = \n");//     for (auto x:L) printf("%lld ",x); putchar('\n');//     printf("R = \n");//     for (auto x:R) printf("%lld ",x); putchar('\n');// }sort(L.begin(),L.end(),greater <int>());pre[0]=0;for (int i=1;i<=n;++i){pre[i]=pre[i-1];while (!L.empty()&&L.back()<c[i]) L.pop_back();if (!L.empty()) ++pre[i],L.pop_back();}sort(R.begin(),R.end());suf[n+1]=0;for (int i=n;i>=1;--i){suf[i]=suf[i+1];while (!R.empty()&&R.back()>c[i]) R.pop_back();if (!R.empty()) ++suf[i],R.pop_back();}int ans=0;for (int i=0;i<=n;++i)ans=max(ans,pre[i]+suf[i+1]);return ans+cnt;
}void solve() {cin >> n;for (int i=1; i<=n; ++i) cin >> a[i];for (int i=1; i<=n; ++i) cin >> b[i];for (int i=1; i<=n; ++i) cin >> c[i];sort(c+1,c+n+1);// printf("chk(20) = %d\n",check(20));// printf("chk(25) = %d\n",check(25));int L=-4e18,R=4e18,res;while (L<=R){int mid=(L+R)/2;if (check(mid)>=(n+1)/2) res=mid,L=mid+1; else R=mid-1; }cout<<res<<'\n';
}signed main() {ios::sync_with_stdio(0); cin.tie(0);int T; cin >> T; while (T--) solve();return 0;
}

I. In Search of the Ultimate Artifact

队友开局写的签,我题目都没看

#include <bits/stdc++.h>using llsi = long long signed int;
constexpr llsi mod = 998244353;llsi work() {int n, k;std::cin >> n >> k;std::vector<llsi> a(n);for(auto &a: a) std::cin >> a;std::sort(a.begin(), a.end(), std::greater<llsi>());while(a.size() && a.back() == 0) a.pop_back();if(a.empty()) return 0;if(a.size() < k) return a[0] % mod;llsi ans = 1;int i = 0;for(i = 0; i < k; ++i) ans = ans * a[i] % mod;while(i + (k - 1) <= a.size()) {for(int r = i + (k - 1); i < r; ++i)ans = ans * a[i] % mod;}return ans;
}int main() {std::ios::sync_with_stdio(false);int T; std::cin >> T;while(T--) std::cout << work() << char(10);return 0;
}

J. Just-in-Time Render Analysis

经典二合一,但无所谓反正我们队中后期没题写的时候就会让我去赤这种大分题的史

这题前半部分就是把给出的矩形信息建成一棵树,这个说实话有点过于经典了,直接扫描线+线段树搞一搞就完事

在树上需要维护单点翻转权值(可以转化为树上到根路径加),以及询问某个深度的点中,有多少个点权值为正

考虑用树剖维护路径修改,同时对每个深度维护一个答案

把一个点 \(x\) 的权值从 \(0\to 1\) 时,只会对路径上权值为 \(0\) 的点对应的深度的答案产生影响

因为这种修改操作存在性质,即一个点的点权小于等于其父亲,因此我们可以在树上倍增找到权值为 \(0\) 的一段,即可快速统计贡献

\(1\to 0\) 的情况同理,理清楚之后每个部分都很套路

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=500005;
struct sweep_line
{int x,yl,yr,id; //id > 0 -> in; id < 0 -> outfriend inline bool operator < (const sweep_line& A,const sweep_line& B){return A.x<B.x;}
}l[N<<1]; int n,m,q,fa[N]; vector <int> v[N];
class Segment_Tree
{private:int val[N<<3],tag[N<<3];inline void apply(CI now,CI mv){tag[now]=mv; val[now]=mv;}inline void pushdown(CI now){if (tag[now]!=-1) apply(now<<1,tag[now]),apply(now<<1|1,tag[now]),tag[now]=-1;}public:#define TN CI now=1,CI l=1,CI r=m#define LS now<<1,l,mid#define RS now<<1|1,mid+1,rinline void build(TN){tag[now]=-1; val[now]=n+1;if (l==r) return; int mid=l+r>>1;build(LS); build(RS);}inline void modify(CI beg,CI end,CI mv,TN){if (beg<=l&&r<=end) return apply(now,mv);int mid=l+r>>1; pushdown(now);if (beg<=mid) modify(beg,end,mv,LS);if (end>mid) modify(beg,end,mv,RS);}inline int query(CI pos,TN){if (l==r) return val[now];int mid=l+r>>1; pushdown(now);if (pos<=mid) return query(pos,LS); else return query(pos,RS);}#undef TN#undef LS#undef RS
}SEG;
int anc[N][20],dep[N],a[N];
inline void DFS1(CI now)
{anc[now][0]=fa[now];for (RI i=0;i<19;++i)if (anc[now][i]) anc[now][i+1]=anc[anc[now][i]][i]; else break;for (auto to:v[now]){if (to==fa[now]) continue;dep[to]=dep[now]+1; DFS1(to);}
}
class Tree_Array
{private:int bit[N];public:#define lowbit(x) (x&-x)inline int get(RI x,int res=0){for (;x;x-=lowbit(x)) res+=bit[x]; return res;}inline void add(RI x,CI y){for (;x<=n+3;x+=lowbit(x)) bit[x]+=y;}inline void modify(int l,int r,CI mv){if (l>r) return; add(l,mv); add(r+1,-mv);}#undef lowbit
}VAL,ANS;
namespace Heavy_Light_Division
{int sz[N],dfn[N],son[N],top[N],idx;inline void DFS2(CI now){sz[now]=1;for (auto to:v[now]){if (to==fa[now]) continue;DFS2(to); sz[now]+=sz[to];if (sz[to]>sz[son[now]]) son[now]=to;}}inline void DFS3(CI now,CI tf){dfn[now]=++idx; top[now]=tf;if (son[now]) DFS3(son[now],tf);for (auto to:v[now]){if (to==fa[now]||to==son[now]) continue;DFS3(to,to);}}inline void modify_path(int x,CI mv){while (top[x]!=n+1){// printf("(VAL) l = %d, r = %d, mv = %d\n",dfn[top[x]],dfn[x],mv);VAL.modify(dfn[top[x]],dfn[x],mv);x=fa[top[x]];}// printf("(VAL) l = %d, r = %d, mv = %d\n",dfn[n+1],dfn[x],mv);VAL.modify(dfn[n+1],dfn[x],mv);}
};
using namespace Heavy_Light_Division;
int main()
{scanf("%d%d",&n,&q);vector <int> rst;for (RI i=1;i<=n;++i){int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);l[i*2-1]=(sweep_line){a,b,d,i};l[i*2]=(sweep_line){c,b,d,-i};rst.push_back(b); rst.push_back(d);}sort(rst.begin(),rst.end());rst.erase(unique(rst.begin(),rst.end()),rst.end());sort(l+1,l+2*n+1); m=(int)rst.size(); SEG.build();for (RI i=1;i<=2*n;++i){auto find=[&](CI x){return lower_bound(rst.begin(),rst.end(),x)-rst.begin()+1;};l[i].yl=find(l[i].yl); l[i].yr=find(l[i].yr);if (l[i].id>0){fa[l[i].id]=SEG.query(l[i].yl);SEG.modify(l[i].yl,l[i].yr,l[i].id);} else SEG.modify(l[i].yl,l[i].yr,fa[-l[i].id]);}for (RI i=1;i<=n;++i){v[fa[i]].push_back(i);// printf("%d -> %d\n",fa[i],i);}dep[n+1]=-1; DFS1(n+1); DFS2(n+1); DFS3(n+1,n+1);// printf("dfn: "); for (RI i=1;i<=n+1;++i) printf("%d%c",dfn[i]," \n"[i==n+1]);while (q--){char opt[5]; int x;scanf("%s%d",opt,&x);if (opt[0]=='^'){if (a[x]==0) // 0 -> 1{// printf("val(%d) = %d\n",x,VAL.get(dfn[x]));if (VAL.get(dfn[x])==0){int y=x;for (RI i=19;i>=0;--i)if (anc[y][i]&&VAL.get(dfn[anc[y][i]])==0) y=anc[y][i];// printf("(ANS) l = %d, r = %d, mv = %d\n",dep[y]+2,dep[x]+2,1);ANS.modify(dep[y]+2,dep[x]+2,1);}modify_path(x,1);} else // 1 -> 0{if (VAL.get(dfn[x])==1){int y=x;for (RI i=19;i>=0;--i)if (anc[y][i]&&VAL.get(dfn[anc[y][i]])==1) y=anc[y][i];// printf("(ANS) l = %d, r = %d, mv = %d\n",dep[y]+2,dep[x]+2,-1);ANS.modify(dep[y]+2,dep[x]+2,-1);}modify_path(x,-1);}a[x]^=1;} else printf("%d\n",ANS.get(x+2));}return 0;
}

M. Machine Learning with Penguins

欧耶,几几的何,因为出题人出的神秘数据极其卡精度,导致这题还处于未完工状态


Postscript

感觉去年的 IC Regional 除了我们队选的两站,其它站 VP 了都能摄金啊,只能说是选站策略大失败

http://www.hskmm.com/?act=detail&tid=29434

相关文章:

  • 英语_阅读_Fireflies_待读
  • 1.基础
  • 深入解析:RoadCLIP 笔记 针对自动驾驶优化的 CLIP 变体 vlm
  • ASP.NET Razor VB 变量 - 实践
  • dos命令和命令提示符
  • 20232401 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • for 循环 range
  • 在AI技术唾手可得的时代,挖掘新需求成为核心竞争力——某知名离线转录工具需求洞察
  • JavaScript async/await 基础使用
  • 27. 移除元素 暴力+快慢指针+相向双指针
  • ST表学习笔记
  • 谈一类易实现的非四毛子线性 RMQ
  • 我们学会在具体情境中做出恰当判断
  • 编译安装nginx
  • AutoGCL——AutoGCL: automated graph contrastive learning via learnable view generators
  • 【教程】无需第三方应用,Windows自带邮箱如何绑定QQ邮箱等第三方邮箱
  • 2025婚纱摄影影楼权威推荐榜:专业团队与创意拍摄打造梦幻婚礼
  • 为什么40岁后的快乐消失了
  • 分布式结构化存储系统-HBase访问方式
  • 【Azure APIM】自建网关(self-host gateway)收集请求的Header和Body内容到日志中的办法
  • [JAVA]JDK多版本设置
  • Google Veo3生成跳舞视频
  • 【PolarCTF】stackof
  • 新生赛 F,H,J 题解
  • pycharm跑python项目易出错的困难
  • 双端队列的0-1BFS
  • Python psycopg2 类库使用学习总结
  • [GenAI] RAG架构演进
  • 24NOIP游记——彼时彼刻
  • 嵌入式-C++面经1