Preface
这场打的时候出现了各种突发情况，比如中途和教练在机房讨论了若干问题，徐神 J 题写一半临时有事走了之类的
再加上有人犯病了魔改欧拉回路板子导致 E 题完全对的思路最后没过，直接 9 题变 7 题了
我再也不乱改板子了.jpg
A. Problem Setting
队友开场写的签
#include<bits/stdc++.h>
using namespace std;
#define int long longusing pii = pair<int, int>;
#define ft first
#define sd second
const int N = 105;
const int INF = (int)1e9+5;
int n, q, A[N];
pii pi[N];pii ins(const pii &a, const pii &b) {if (a.ft > b.sd || b.ft > a.sd) return pii{-1, -1};return pii{max(a.ft, b.ft), min(a.sd, b.sd)};
}int solve() {cin >> n >> q;for (int i=1; i<=n; ++i) cin >> A[i], pi[i].ft = 0, pi[i].sd = INF;bool flag = true;for (int i=1; i<=q; ++i) {int p, l, r; cin >> p >> l >> r;pi[p] = ins(pi[p], pii{l, r});if (-1 == pi[p].ft) flag = false; }if (!flag) return -1;// for (int i=1; i<=n; ++i) printf("i=%lld (%lld %lld)\n", i, pi[i].ft, pi[i].sd);int ans = 0;for (int i=1; i<=n; ++i) {if (A[i] < pi[i].ft) ans += (pi[i].ft - A[i]);else if (A[i] > pi[i].sd) ans += (A[i] - pi[i].sd);}return ans;
}signed main() {ios::sync_with_stdio(0); cin.tie(0);int T; cin >> T; while (T--) cout << solve() << '\n';return 0;
}
C. One Must Imagine Sisyphus Happy
思路不难但细节比较多，如果实现不好的话可能会写的很繁琐
将一棵草在向右走的时候被拔掉记为 \(R\)，向左走的时候被拔掉记为 \(L\)，则一共有以下三种情况：
- \(R,R,R,R,\dots\)
- \(R,L,L,L,\dots\)
- \(R,L,R,L,\dots\)
不难发现除了第三种情况，前面两种情况拔草的时间都可以写成某个周期函数的形式
而第三种情况可能会有两个不同的间隔，会出现形如 \(+2,+3,+2,+3,\dots\) 这样的情况
不过我们很容易将这种情况拆成两个周期函数的形式，并且简单分析后会发现这种两个间隔的情形下二者之差为 \(1\)，因此并不会使得最后总状态的数量级增加
最后把所有本质相同的状态合并到一起，暴力维护贡献，复杂度是调和级数的
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5;
int t,n,m,a[N],ans[N];
vector <pair <int,int>> vec[N];
inline void set(CI s,CI d)
{if (s>m) return;if (d>=m) return (void)(++ans[s]);for (auto& [x,y]:vec[d])if (x==s) return (void)(++y);vec[d].push_back({s,1});
}
int main()
{for (scanf("%d",&t);t;--t){scanf("%d%d",&n,&m);for (RI i=1;i<=m;++i) ans[i]=0,vec[i].clear();for (RI i=1;i<=n;++i) scanf("%d",&a[i]),++a[i];for (RI i=1;i<=n;++i){int T=a[i]/(2*n-1),rem=a[i]-T*(2*n-1);int L=2*(i-1),R=2*(n-i)-1;if (rem==0) { set(1,T); continue; }if (rem<=2*(n-i)){if (rem<=2*(i-1)+1) set(1,T+T+1),set(1+T,T+T+1);else ++ans[1],set(1+T,T+1);} else set(1,T+1);}for (RI d=1;d<m;++d){for (auto [s,v]:vec[d])for (RI i=s;i<=m;i+=d) ans[i]+=v;}for (RI i=1;i<=m;++i)printf("%d%c",ans[i]," \n"[i==m]);}return 0;
}
E. Colorful Graph
思路全对，过程也全对，结果板子抄不对，也是神人了
由于答案的下界为 \(\sum \lceil\frac{deg_i}{2}\rceil\)，因此考虑下列能构造出该下界的方案
每次找出一个环，将环上的边染为一种颜色，直到最后找不出环为止
对于原图中度数为奇数的点，两两之间加上一条虚拟边后，图就变成了欧拉图
直接找欧拉回路即可轻松构造答案
#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<stack>
#include<assert.h>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=400005;
int t,n,m,ans[N],used[N],vis[N],idx; vector <pi> v[N]; vector <int> path;
inline void Euler(CI now)
{while (!v[now].empty()){auto [to,id]=v[now].back();v[now].pop_back();if (used[id]) continue;used[id]=1; Euler(to);}path.push_back(now);
}
int main()
{for (scanf("%d",&t);t;--t){scanf("%d%d",&n,&m);map <pi,int> rst;for (RI i=1;i<=n;++i) v[i].clear();for (RI i=1;i<=m;++i){int x,y; scanf("%d%d",&x,&y);v[x].push_back({y,i});v[y].push_back({x,i});rst[{x,y}]=rst[{y,x}]=i;used[i]=ans[i]=0;}vector <int> odd;for (RI i=1;i<=n;++i)if ((int)v[i].size()%2==1) odd.push_back(i);for (RI i=0;i+1<odd.size();i+=2){int x=odd[i],y=odd[i+1];v[x].push_back({y,m+i/2+1});v[y].push_back({x,m+i/2+1});used[m+i/2+1]=0;}idx=0; for (RI i=1;i<=n;++i) vis[i]=0;for (RI i=1;i<=n;++i){if (v[i].empty()) continue;path.clear(); Euler(i);// for (auto x:path) printf("%d ",x); putchar('\n');stack <int> stk;for (auto x:path){ if (vis[x]){int lst=x; ++idx;while (stk.top()!=x){// printf("(%d,%d)\n",lst,stk.top());if (rst.count({lst,stk.top()})) ans[rst[{lst,stk.top()}]]=idx;vis[stk.top()]=0; lst=stk.top();stk.pop();}if (rst.count({lst,x})) ans[rst[{lst,x}]]=idx;vis[x]=1;} else stk.push(x),vis[x]=1;}for (auto x:path) vis[x]=0;}for (RI i=1;i<=m;++i)assert(1<=ans[i]&&ans[i]<=m);assert(idx<=m);for (RI i=1;i<=m;++i)printf("%d%c",ans[i]," \n"[i==m]);}return 0;
}
F. Knapsack
考虑贪心，将物品从大到小排序，我们的策略是每次将物品放到总体积最小的包里
不过由于包和物品的数量很多，实现时通过维护答案以及总缺口量
因为物品的体积粒度越来越小，因此去填坑总是能填上的，故不需要维护缺口的具体形态
由于这题的数量级比较大，实现时可以维护当前缺口需要多少个当前物品才能不足，并可以通过设阈值的方法避免高精度
#include <bits/stdc++.h>using llsi = long long signed int;
constexpr llsi THRESHOLD = 1ll << 50;constexpr llsi mod = 998244353;constexpr llsi ksm(llsi a, llsi b) {llsi c = 1;while(b) {if(b & 1) c = c * a % mod;a = a * a % mod;b >>= 1;}return c;
}// void add(std::set<int> &s, int b) {
// while(s.find(b) != s.end()) s.erase(b++);
// s.insert(b);
// return ;
// }// void add(std::set<int> &s, int a, int b) {
// while(a) {
// if(a & 1) add(s, b);
// b += 1;
// a >>= 1;
// }
// return ;
// }// llsi to_mod(std::set<int> &s) {
// llsi res = 0;
// for(auto c: s) res = (res + ksm(2, c)) % mod;
// return res;
// }llsi work() {int n, m; std::cin >> n >> m;std::vector<std::pair<int, int>> hkr(n);for(auto &[b, a]: hkr) std::cin >> a >> b;std::sort(hkr.begin(), hkr.end(), std::greater<std::pair<int, int>>());llsi res = 0, res_b = -1;llsi ans = 0;for(auto [b, a]: hkr) {if(res_b > b && res == 0) res_b = b;while(res_b > b) {res_b--;res *= 2;if(res >= THRESHOLD) return ans;}llsi take = std::min(llsi(a), res);a -= take;res -= take;if(a == 0) continue;// add(ans, a / m, b);(ans+=1LL*(a/m)%mod*ksm(2,b)%mod)%=mod;res_b = b;a %= m;if(a) {// add(ans, b);(ans+=ksm(2,b))%=mod;res = (m - a);} else {res = 0;}}return ans;
}int main() {std::ios::sync_with_stdio(false);int T; std::cin >> T; while(T--) std::cout << work() << char(10);return 0;
}
G. Path Summing Problem
很经典的一个题啊，连我这种计数苦手都能看一眼就编出做法
考虑枚举每个位置，钦定只有它是一条路径经过的同类数字的第一个时才计算贡献，这样显然是不重不漏的
现在要对每个位置求出走到它且不经过与它值相同的路径条数，显然有两种做法：
- 直接 \(O(nm)\) 递推，在之前遇到和它值相同的位置就清空；
- 大力容斥，设之前有 \(k\) 个值相同的数，复杂度是 \(O(k^2)\) 的；
很容易发现根号分治，对于出现次数大于 \(\sqrt{nm}\) 的数用第一种方法，否则用第二种方法，总复杂度是 \(O(nm\sqrt{nm})\) 的
#include<cstdio>
#include<iostream>
#include<vector>
#include<cmath>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=100005,mod=998244353;
int t,n,m,fact[N<<1],ifac[N<<1]; vector <int> a[N],g[N],sp[N]; vector <pi> pos[N];
inline void inc(int& x,CI y)
{if ((x+=y)>=mod) x-=mod;
}
inline void dec(int& x,CI y)
{if ((x-=y)<0) x+=mod;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{fact[0]=1;for (RI i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;ifac[n]=quick_pow(fact[n]);for (RI i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
inline int C(CI n,CI m)
{if (n<0||m<0||n<m) return 0;return 1LL*fact[n]*ifac[m]%mod*ifac[n-m]%mod;
}
inline int calc(const pi& A,const pi& B)
{int dx=B.first-A.first,dy=B.second-A.second;if (dx<0||dy<0) return 0;return C(dx+dy,dx);
}
int main()
{for (init(200000),scanf("%d",&t);t;--t){scanf("%d%d",&n,&m);for (RI i=0;i<=n;++i) a[i].resize(m+1),g[i].resize(m+1),sp[i].resize(m+1);for (RI i=1;i<=n*m;++i) pos[i].clear();for (RI i=1;i<=n;++i)for (RI j=1;j<=m;++j){scanf("%d",&a[i][j]);pos[a[i][j]].push_back({i,j});}int S=(int)sqrt(n*m),ans=0;for (RI k=1;k<=n*m;++k){if ((int)pos[k].size()<=S){vector <int> f(pos[k].size(),0);for (RI i=0;i<(int)pos[k].size();++i){f[i]=calc({1,1},pos[k][i]);for(RI j=0;j<i;++j)dec(f[i],1LL*f[j]*calc(pos[k][j],pos[k][i])%mod);inc(ans,1LL*f[i]*calc(pos[k][i],{n,m})%mod);}} else{for (RI i=0;i<=n;++i)for (RI j=0;j<=m;++j)g[i][j]=sp[i][j]=0;for (auto [x,y]:pos[k])sp[x][y]=1;g[1][1]=1;for (RI i=1;i<=n;++i)for (RI j=1;j<=m;++j){inc(g[i][j],g[i-1][j]); inc(g[i][j],g[i][j-1]);if (sp[i][j]) inc(ans,1LL*g[i][j]*calc({i,j},{n,m})%mod),g[i][j]=0;}}}printf("%d\n",ans);}return 0;
}
I. Bingo 3
签到，但有人开局看错题了我不说是谁
把 \(k\) 放在 \((1,1)\)，然后找 \(n-1\) 个小于 \(k\) 的数放在第一行，再找 \(n-1\) 个大于 \(k\) 的数放在剩下的主对角线位置即可
#include<cstdio>
#include<iostream>
#include<assert.h>
#define RI register int
#define CI const int&
using namespace std;
const int N=55;
int t,n,k,a[N][N],used[N*N];
int main()
{for (scanf("%d",&t);t;--t){scanf("%d%d",&n,&k);if (k<n||n*n-k<n-1) { puts("No"); continue; }puts("Yes"); int idx=k;for (RI i=1;i<=n;++i)for (RI j=1;j<=n;++j)a[i][j]=0;for (RI i=1;i<=n*n;++i) used[i]=0;for (RI i=1;i<=n;++i) used[idx]=1,a[1][i]=idx--;idx=k+1;for (RI i=2;i<=n;++i) used[idx]=1,a[i][i]=idx++;idx=1;for (RI i=1;i<=n;++i)for (RI j=1;j<=n;++j){if (a[i][j]) continue;while (used[idx]) ++idx;a[i][j]=idx++;}// int res=-1;// for (RI s=1;s<=n*n;++s)// {// bool flag=0;// for (RI i=1;i<=n;++i)// {// int cnt=0;// for (RI j=1;j<=n;++j)// cnt+=a[i][j]<=s;// if (cnt==n) { flag=1; }// }// if (!flag) continue;// flag=0;// for (RI j=1;j<=n;++j)// {// int cnt=0;// for (RI i=1;i<=n;++i)// cnt+=a[i][j]<=s;// if (cnt==n) { flag=1; }// }// if (!flag) continue;// res=s; break;// }// assert(res==k);for (RI i=1;i<=n;++i)for (RI j=1;j<=n;++j)printf("%d%c",a[i][j]," \n"[j==n]);}return 0;
}
J. Dictionary
赛时 SAM 板都抄好了还写了一大半了，结果唯一会 string 的徐神一走留下剩下两条字符串苦手，索性直接开摆
徐神宣布对此题负责.jpg
L. Subsequence
不难发现给序列排序不影响答案
枚举最小最大两个数，可以很容易计算出合法的中位数所在的区间
在区间里选一个尽可能靠近中心的位置即可，注意奇偶长度区间的区别
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
#define RI register int
#define CI const int&
using namespace std;
const int N=3005;
int t,n,a[N];
int main()
{for (scanf("%d",&t);t;--t){scanf("%d",&n);for (RI i=1;i<=n;++i) scanf("%d",&a[i]);sort(a+1,a+n+1);map <int,int> L,R;for (RI i=1;i<=n;++i) R[a[i]]=i;for (RI i=n;i>=1;--i) L[a[i]]=i;int ans=1;for (RI i=1;i<=n;++i)for (RI j=i+1;j<=n;++j){if ((a[i]+a[j])%2==1) continue;int M=(a[i]+a[j])/2;if (!L.count(M)) continue;int l=L[M],r=R[M];auto upt=[&](CI p){int res=2*min(p-i,j-p)+1;if (p-i<j-p) ++res;ans=max(ans,res);return;};if ((j-i)%2==0){int p=i+j>>1;if (l<=p&&p<=r) upt(p);upt(l); upt(r);} else{int p=i+j>>1;if (l<=p&&p<=r) upt(p);if (l<=p+1&&p+1<=r) upt(p+1);upt(l); upt(r);}}printf("%d\n",ans);}return 0;
}
M. Flight Tracker
神秘的立体几何，但无所谓我们队有几何大手子
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define LD long doubleconst LD PI = acosl(-1.0L);struct Pt {int x, y, z;int dot(const Pt &b) const {return x*b.x + y*b.y + z*b.z;}Pt crs(const Pt &b) const {return Pt {y*b.z-z*b.y, z*b.x-x*b.z, x*b.y-y*b.x};}int len2() const {return x*x+y*y+z*z;}
};LD cosv(const Pt &a, const Pt &b) {return 1.0L * a.dot(b) / sqrtl(a.len2()*b.len2());}LD solve() {int r; cin >> r;Pt p; cin >> p.x >> p.y >> p.z;Pt a; cin >> a.x >> a.y >> a.z;Pt b; cin >> b.x >> b.y >> b.z;Pt c = a.crs(b);int s1 = (cosv(c.crs(a), p) >= 0);int s2 = (cosv(p, b.crs(c)) >= 0);if (s1 && s2) {LD thi = acos(cosv(c, p));if (thi < PI/2) thi = PI/2 - thi;else thi = thi - PI/2;// puts("11111");return thi*r;} else {// puts("22222");return r*min(acos(cosv(p, a)), acos(cosv(p, b)));}
}signed main() {ios::sync_with_stdio(0); cin.tie(0);cout << setiosflags(ios::fixed) << setprecision(18);int T; cin >> T; while (T--) cout << solve() << '\n';return 0;
}
Postscript
fun fact：有人在有中文题面的时候读错题意的次数比英文题面多得多，我不说是谁