题解:
https://files.cnblogs.com/files/clrs97/2022Hong_Kong_Tutorial.pdf
Code:
A. TreeScript
#include <bits/stdc++.h> using namespace std; using LL = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; for (cin >> t; t; t -= 1) { int n; cin >> n; vector<int> p(n + 1); vector<vector<int>> g(n + 1); vector<int> dp(n + 1); for (int i = 1; i <= n; i += 1) cin >> p[i]; for (int i = n; i >= 1; i -= 1) { if (g[i].empty()) dp[i] = 1; else if (g[i].size() == 1) dp[i] = g[i][0]; else { sort(g[i].begin(), g[i].end(), greater<int>()); dp[i] = max(g[i][0], g[i][1] + 1); } g[p[i]].push_back(dp[i]); } cout << dp[1] << "\n"; } return 0; }
B. Big Picture
#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL mod=998244353; const LL N=1200; LL a[N][N],b[N][N],n,m,e1[N][N]; void upd(LL &x,LL y){x=(x+y)%mod;} int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m; for (LL i=1;i<=n;++i){ for (LL j=1;j<=m;++j){ cin>>a[i][j]; upd(a[i][j],a[i][j-1]); } } for (LL i=1;i<=n;++i){ for (LL j=1;j<=m;++j){ cin>>b[i][j]; upd(b[i][j],b[i-1][j]); } } LL E=0,V=0,S=0; // E: [out edge] // V: [node] // S: [inside edge] - [fake face] auto pr=[&](LL i,LL j)->LL { if (i==0||j==0) return 1; return 1-a[i][j-1]*b[i-1][j]%mod; }; for (LL i=1;i<=n;++i){ for (LL j=1;j<=m;++j){ upd(V,pr(i,j)); // cerr<<i<<' '<<j<<' '<<pr(i,j)<<'\n'; } } for (LL i=1;i<=n;++i){ for (LL j=1;j<=m;++j){ if (j>1){// edge([i,j-1],[i,j]) LL p=0; upd(p,1-pr(i,j-1)); upd(p,1-pr(i,j)); upd(p,-(a[i][j-2]*b[i-1][j-1]%mod*b[i-1][j])); upd(E,1-p); e1[i][j]=1-p; } if (i>1){// edge([i-1,j],[i,j]) LL p=0; upd(p,1-pr(i-1,j)); upd(p,1-pr(i,j)); upd(p,-(b[i-2][j]*a[i-1][j-1]%mod*a[i][j-1])); upd(E,1-p); } } } for (LL i=2;i<=n;++i){ for (LL j=2;j<=m;++j){ {//square LL p1=(1-a[i][j-1])*e1[i-1][j]%mod; LL p2=(a[i][j-1]-a[i][j-2])*(1-b[i-1][j])%mod*pr(i-1,j-1)%mod; LL p3=a[i][j-2]*(1-b[i-1][j])%mod*(1-b[i-1][j-1])%mod; upd(S,-(p1+p2+p3)); } {//diag LL p=a[i-1][j-2]*b[i-2][j-1]%mod*(a[i][j-1]-a[i][j-2])%mod*(b[i-1][j]-b[i-2][j])%mod; upd(S,p); } } } // cerr<<E<<' '<<V<<' '<<S<<'\n'; LL ans=(1+1+1+E-V+S)%mod; cout<<(ans+mod)%mod<<'\n'; }
C. Painting Grid
#include<bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); int T; cin>>T; while(T--) { int n,m; cin>>n>>m; int ok=1; if(m<=10 and (1<<m)<n)ok=0; if(n<=10 and (1<<n)<m)ok=0; if(not ok or n*m%2==1)cout<<"NO\n"; else { cout<<"YES\n"; int sw=0; if(m%2!=0)sw=1,swap(n,m); vector<vector<int>> ans(n+5,vector<int>(m+5)); int mx; for(int i=1;i<=m/2;i++)ans[1][i]=1,mx=1; set<vector<int>> s; vector<vector<int>> tmp; { auto rev=ans[1]; for(int i=1;i<=m;i++)rev[i]^=1; tmp.push_back(rev); s.insert(rev);s.insert(ans[1]); } for(int b=0;(1<<b)<m/2;b++) { // cerr<<"go "<<b<<endl; for(int i=0;i<m/2;i++) { ans[b+2][i+1]=(i>>b)&1; ans[b+2][i+m/2+1]=((i>>b)&1)^1; } auto rev=ans[b+2]; for(int i=1;i<=m;i++)rev[i]^=1; tmp.push_back(rev); s.insert(rev);s.insert(ans[b+2]); mx=max(mx,b+2); } vector<int> now(m+5); // auto chk=[&](){int ret=0;for(int i=1;i<=m;i++)ret+=now[i];return ret;}; auto nxt=[&](){for(int i=m;i>=1;i--)if(now[i]==1)now[i]=0;else {now[i]=1;return true;}return false;}; mx++; while(mx+1<=n) { if(s.count(now)) { if(nxt()) continue; else break; } auto rnow=now; for(int i=1;i<=m;i++)rnow[i]^=1; ans[mx]=now; ans[mx+1]=rnow; s.insert(now); s.insert(rnow); mx+=2; nxt(); } while(mx<=n) { ans[mx]=tmp.back(); tmp.pop_back(); mx++; } if(sw) { for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) cout<<ans[j][i]; cout<<"\n"; } } else { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) cout<<ans[i][j]; cout<<"\n"; } } } } return 0; }
D. Shortest Path Query
#include<cstdio> #include<vector> #include<algorithm> using namespace std; const int N=50005,Q=50005,MASK=1023,inf=~0U>>1; int n,m,q,cnt,i,j,k,x,y,z,e[Q][2],ans[Q]; vector<int>g[N][2],h[N]; struct P{int x,y;P(){}P(int _x,int _y){x=_x,y=_y;}}hull[N*2]; vector<P>f[MASK+2],cur; inline void up(int&a,int b){a>b?(a=b):0;} inline void ext(const P&p,int dx,int dy){ if(cnt){ if(hull[cnt].y<=p.y+dy)return; if(hull[cnt].x==p.x+dx)cnt--; } while(cnt>1&&1LL*(hull[cnt].y-hull[cnt-1].y)*(p.x+dx-hull[cnt].x)>=1LL*(p.y+dy-hull[cnt].y)*(hull[cnt].x-hull[cnt-1].x))cnt--; hull[++cnt]=P(p.x+dx,p.y+dy); } inline void merge(const vector<P>&v,int dx,int dy){ cnt=0; int i=0,j=0; while(i<cur.size()&&j<v.size()){ if(cur[i].x<v[j].x+dx)ext(cur[i++],0,0); else ext(v[j++],dx,dy); } while(i<cur.size())ext(cur[i++],0,0); while(j<v.size())ext(v[j++],dx,dy); cur.resize(cnt); for(i=0;i<cnt;i++)cur[i]=hull[i+1]; } int main(){ scanf("%d%d",&n,&m); while(m--){ scanf("%d%d%d",&x,&y,&z); g[y][z].push_back(x); } scanf("%d",&q); for(i=1;i<=q;i++){ scanf("%d%d%d",&x,&y,&z); e[i][0]=x; e[i][1]=y; h[z].push_back(i); } for(i=1;i<=n;i++){ cur.clear(); if(i==1)cur.push_back(P(0,0)); for(j=0;j<g[i][0].size();j++)merge(f[g[i][0][j]&MASK],1,0); for(j=0;j<g[i][1].size();j++)merge(f[g[i][1][j]&MASK],0,1); for(j=0;j<h[i].size();j++){ z=h[i][j]; x=e[z][0]; y=e[z][1]; int tmp=inf; for(k=0;k<cur.size();k++)up(tmp,x*cur[k].x+y*cur[k].y); ans[z]=tmp; } swap(cur,f[i&MASK]); } for(i=1;i<=q;i++)printf("%d\n",ans[i]); }
E. Goose, Goose, DUCK?
#include<bits/stdc++.h> using namespace std; const int N=1e6+1e3+7,L=1e6; int n,k,a[N]; vector<int>pos[N]; struct T{ int l,r,ls,rs; int mx,cnt; int tag; }t[N*2+1]; int cnt; void add(int x,int v) { t[x].tag+=v; t[x].mx+=v; } void pushdown(int x) { if(t[x].tag) { add(t[x].ls,t[x].tag); add(t[x].rs,t[x].tag); t[x].tag=0; } } void update(int x) { t[x].mx=max(t[t[x].ls].mx,t[t[x].rs].mx); t[x].cnt=(t[x].mx==t[t[x].ls].mx)*t[t[x].ls].cnt+(t[x].mx==t[t[x].rs].mx)*t[t[x].rs].cnt; } int build(int l,int r) { int x=++cnt; t[x].l=l,t[x].r=r; if(l==r) { t[x].cnt=1; return x; } int mid=(l+r)>>1; t[x].ls=build(l,mid); t[x].rs=build(mid+1,r); update(x); return x; } void change(int x,int l,int r,int v) { if(l<=t[x].l&&t[x].r<=r) { add(x,v); return; } pushdown(x); int mid=(t[x].l+t[x].r)>>1; if(l<=mid) change(t[x].ls,l,r,v); if(r>mid) change(t[x].rs,l,r,v); update(x); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; long long ans=0; build(1,n); for(int i=1;i<=n;i++) { change(1,i,i,L); if(pos[a[i]].size()>=k) { int r=pos[a[i]][pos[a[i]].size()-k],l=pos[a[i]].size()==k?1:pos[a[i]][pos[a[i]].size()-k-1]+1; change(1,l,r,1); } pos[a[i]].push_back(i); if(pos[a[i]].size()>=k) { int r=pos[a[i]][pos[a[i]].size()-k],l=pos[a[i]].size()==k?1:pos[a[i]][pos[a[i]].size()-k-1]+1; change(1,l,r,-1); } if(t[1].mx==L) ans+=t[1].cnt; } cout<<ans<<"\n"; }
F. Sum of Numbers
#include <bits/stdc++.h> using namespace std; constexpr int base = 10; struct Dec{ vector<int> d; Dec(vector<int> d = {0}): d(d) { assert(not d.empty()); } bool is_zero() const { return d.size() == 1 and d[0] == 0; } Dec& operator += (const Dec& dec) { int carry = 0; int msize = max(d.size(), dec.d.size()); d.resize(msize); for (int i = 0; i < msize; i += 1) { if (i < dec.d.size()) d[i] += dec.d[i]; d[i] += carry; if (d[i] >= base) { carry = 1; d[i] -= base; } else { carry = 0; } } if (carry) d.push_back(carry); return *this; } bool operator < (const Dec& dec) const { if (d.size() != dec.d.size()) return d.size() < dec.d.size(); for (int i = d.size() - 1; i >= 0; i -= 1) if (d[i] != dec.d[i]) return d[i] < dec.d[i]; return false; } }; ostream& operator << (ostream& out, const Dec& dec) { for (int i = dec.d.size() - 1; i >= 0; i -= 1) out << dec.d[i]; return out; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; map<int, map<int, vector<vector<int>>>> mp; for (cin >> t; t; t -= 1) { int n, k; string sr; cin >> n >> k >> sr; vector<int> p(n); for (int i = 0; i < n; i += 1) { p[i] = sr[n - i - 1] - '0'; } auto f = [&](int L, int R) -> Dec { return Dec(vector<int>(p.begin() + (n - 1 - R), p.begin() + (n - L))); }; if (not mp.count(k)) { vector<int> a(k); function<void(int)> DFS = [&](int u) { if (u == k) { vector<int> s(k); for (int i = 0; i < k; i += 1) { if (i) s[i] = s[i - 1]; s[i] += a[i]; } int ss = 0; for (int si : s) ss += si; mp[k][(ss % (k + 1) + k + 1) % (k + 1)].push_back(s); return; } for (int i : {0, -1, 1}) { a[u] = i; DFS(u + 1); } }; DFS(0); } Dec ans; for (auto s : mp[k][n % (k + 1)]) { int ss = 0; for (int si : s) ss += si; int x = (n - ss) / (k + 1); int ok = x > 0; for (int si : s) ok &= x + si > 0; if (not ok) continue; Dec pans = f(0, x - 1); int L = x; for (int si : s) { si += x; if (not ans.is_zero() and si > ans.d.size()) { ok = 0; break; } pans += f(L, L + si - 1); if (not ans.is_zero() and ans < pans) { ok = 0; break; } L += si; } if (not ok) continue; if (ans.is_zero() or pans < ans) ans = pans; } cout << ans << "\n"; } return 0; }
G. Paddle Star
#include<bits/stdc++.h> using namespace std; const double pi=acos(-1); int T; double l1,l2,alp,bet; double trans(double deg) { return deg/180*pi; } double fix(double x) { return min(max(x,-1.0),1.0); } int main() { int Case=0; scanf("%d",&T); while(T--) { scanf("%lf%lf%lf%lf",&l1,&l2,&alp,&bet); alp=trans(alp); bet=trans(bet); double ans=(l1+l2)*(l1+l2)*alp+l2*l2*bet; if(bet<=pi/2) { printf("%.15lf\n",ans); continue; } else { double rc=pi-bet; double A=l1,B=l2; double C=sqrt(max(A*A+B*B-2*A*B*cos(rc),0.0)); double rb=asin(fix(B*sin(rc)/C)); double ra=pi-rb-rc; if(ra>=pi/2) { double t=min(rb,alp*2); double S=0.5*A*B*sin(rc); double rcc=pi-ra-(rb-t); double AA=C/sin(rcc)*sin(ra); S-=0.5*C*AA*sin(rb-t); S-=C*C*t*0.5; ans+=S*2; } else { double S=0.5*A*B*sin(rc); double H=S*2/B; double rL=acos(fix(H/C)); S-=0.5*C*H*sin(rL); double rR=rb-rL; double t=min(rR,alp*2); S-=H*H*t*0.5; S-=0.5*H*H*tan(rR-t); ans+=S*2; } printf("%.15lf\n",ans); } } }
H. Another Goose Goose Duck Problem
#include<bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define data dataa #define rep(i,n) for(int i=1;i<=n;i++) typedef long long LL; int main() { int l,r,b,k; scanf("%d%d%d%d",&l,&r,&b,&k); printf("%lld\n",(LL)((l-1)/b+1)*b*k); return 0; }
I. Range Closest Pair of Points Query
#include<cstdio> #include<vector> using namespace std; typedef unsigned int U; typedef long long ll; const int N=250005,Q=250005,BLK=9,M=(N>>BLK)+5,K=28,Base=(1<<21)-1; const ll inf=1LL<<60; int n,m,i,j,x,y,g[N],v[Q],nxt[Q]; int cb;ll val[N],mi[M],ans[Q]; struct P{int x,y;}a[N]; inline ll dis(const P&a,const P&b){return 1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y);} inline void up(ll&a,ll b){a>b?(a=b):0;} inline void modify(int x,ll p){up(val[x],p);up(mi[x>>BLK],p);} inline ll query(int x){ ll ret=inf; int X=x>>BLK; for(int i=x;(i>>BLK)==X&&i<=n;i++)up(ret,val[i]); for(int i=X+1;i<=cb;i++)up(ret,mi[i]); return ret; } struct Layer{ int g[Base+2],vx[N],vy[N],nxt[N],ed; int rad; vector<int>pool[N]; int st[N],size[N]; int head; int ask(int x,int y){ if(x<0||y<0)return 0; U val=((((U)x)<<8)^y)&Base; for(int i=g[val];i;i=nxt[i])if(vx[i]==x&&vy[i]==y)return i; return 0; } int ins(int x,int y){ U val=((((U)x)<<8)^y)&Base; for(int i=g[val];i;i=nxt[i])if(vx[i]==x&&vy[i]==y)return i; vx[++ed]=x; vy[ed]=y; nxt[ed]=g[val]; g[val]=ed; return ed; } void insert(int o){pool[ins(a[o].x>>rad,a[o].y>>rad)].push_back(o);} void init(){ for(int i=1;i<=ed;i++)st[i]=pool[i].size()-1; head=1; } void search(int o){ int A=a[o].x>>rad,B=a[o].y>>rad; for(int X=A-1;X<=A+1;X++)for(int Y=B-1;Y<=B+1;Y++){ int O=ask(X,Y); if(!O)continue; int i=st[O]; while(i>=0&&pool[O][i]<head)i--; for(st[O]=i;i>=0;i--){ int who=pool[O][i]; if(who>=o)break; ll now=dis(a[o],a[who]); if(now>>(rad*2))continue; if(!(now>>((rad-1)*2))){ if(head<=who)head=who+1; continue; } modify(who,now); } } } }layer[K]; int main(){ scanf("%d%d",&n,&m); for(i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y); for(i=1;i<=m;i++){ scanf("%d%d",&x,&y); v[i]=x; nxt[i]=g[y]; g[y]=i; } cb=n>>BLK; for(i=0;i<=cb;i++)mi[i]=inf; for(i=1;i<=n;i++)val[i]=inf; for(i=0;i<K;i++)layer[i].rad=i+1; for(i=n;i;i--)for(j=0;j<K;j++)layer[j].insert(i); for(i=0;i<K;i++)layer[i].init(); for(i=1;i<=n;i++){ for(j=0;j<K;j++){ if(j&&layer[j-1].head>layer[j].head)layer[j].head=layer[j-1].head; layer[j].search(i); } for(j=g[i];j;j=nxt[j]){ x=v[j]; if(x<layer[0].head)ans[j]=0;else ans[j]=query(x); } } for(i=1;i<=m;i++)printf("%lld\n",ans[i]); }
J. Dice Game
#include<bits/stdc++.h> using namespace std; #define int long long const int P=998244353; typedef pair<int,int> pii; #define fs first #define sd second #define mp make_pair int qpow(int a,int b) { int ret=1; while(b) { if(b&1) ret=ret*a%P; b>>=1; a=a*a%P; } return ret; } int n; int val[31],L,R; pii operator +(const pii &a,const pii &b) { return {max(a.fs,b.fs),min(a.sd,b.sd)}; } pii f[2][2][31]; int vis[2][2][31]; pii dp(int p,int up,int dw) { if(p==-1) return mp(0,0); if(vis[up][dw][p]) return f[up][dw][p]; vis[up][dw][p]=1; pii ret(-1e18,1e18); for(int i=dw?L>>p&1:0;i<=(up?R>>p&1:1);i++) { auto nxt=dp(p-1,up&&i==(R>>p&1),dw&&i==(L>>p&1)); nxt.first+=(i?-val[p]:val[p]); nxt.second+=(i?-val[p]:val[p]); ret=ret+nxt; } return f[up][dw][p]=ret; } int c1(int N,int i) { return N/(1<<i+1)*(1<<i)+max(0ll,N%(1<<i+1)-(1<<i)); } pii getv(int l,int r) { memset(vis,0,sizeof(vis)); L=l,R=r; return dp(30,1,1); } int sgn(int x) { return x>=0?1:-1; } int ans=0,ivn; void solve(int l,int r) { pii res=getv(l,r); if(sgn(res.fs)==sgn(res.sd)) { if(sgn(res.fs)>=0) { int sum=0; for(int i=30;i>=0;i--) { int x1=val[i]/(1<<i),x0=(n-x1),y1=c1(r+1,i)-c1(l,i),y0=r-l+1-y1; sum=(sum+(x1*y0%P+x0*y1%P)*(1<<i))%P; } ans=(ans+sum*ivn)%P; } else ans=(ans+(l+r)*(r-l+1)/2)%P; return; } int mid=(l+r)>>1; solve(l,mid); solve(mid+1,r); } signed main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin>>T; while(T--) { cin>>n; ivn=qpow(n,P-2); for(int i=0;i<=30;i++) val[i]=c1(n,i)*(1<<i); ans=0; solve(0,n-1); ans=ans*ivn%P; cout<<ans<<"\n"; } }
K. Maximum GCD
#include<bits/stdc++.h> using namespace std; const int N=1e6+1e3+7; set<int>s; int n; int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n; for(int i=1;i<=n;i++) { int x; cin>>x; s.insert(x); } int ans=s.size()==1?*s.begin():(*s.begin())/2; if(s.size()>1) { if((*next(s.begin()))/2>=*s.begin()) ans=*s.begin(); } cout<<ans<<endl; }
L. Permutation Compression
#include<bits/stdc++.h> using namespace std; const int N=2e5+1e3+7; int T,n,m,k,p[N],q[N],l[N],pos[N],del[N]; int c[N]; void add(int x,int v) { while(x<=n) { c[x]+=v; x+=x&-x; } } int qry(int x) { int ret=0; while(x) { ret+=c[x]; x-=x&-x; } return ret; } int main() { scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) scanf("%d",&p[i]),pos[p[i]]=i,del[i]=1,c[i]=0; for(int i=1;i<=m;i++) scanf("%d",&q[i]),del[q[i]]=0; for(int i=1;i<=k;i++) scanf("%d",&l[i]); bool ok=1; for(int i=1;i<m;i++) if(pos[q[i]]>pos[q[i+1]]) ok=0; if(!ok) { puts("NO"); continue; } set<int>s; vector<int>nd; for(int i=n;i>=1;i--) { int x=pos[i]; if(!del[i]) s.insert(x); else { auto it=s.lower_bound(x); int r=it==s.end()?n:*it-1; int l=it==s.begin()?1:*prev(it)+1; nd.push_back((r-l+1)-(qry(r)-qry(l-1))); add(x,1); } } sort(nd.begin(),nd.end()); sort(l+1,l+k+1); int p=k; while(nd.size()) { int x=nd.back(); nd.pop_back(); while(p>0&&l[p]>x) p--; if(!p) { ok=0; break; } p--; } puts(ok?"YES":"NO"); } }
- Hong Kong Programming The Universalhong kong programming the qingdao programming the universal guilin programming collegiate universal universal stage the 2nd universal qingdao stage the the universal binjiang contest qingdao the universal acm-icpc the universal acm-icpc regional universal stage hefei the universal shenyang stage the