Preface
久违地线下训练，没想到前年的比赛还有没打过的漏网之鱼
这场由于一个中期题 G 被看出来是去年暑假前集训做过的原，导致题目难度跨度有点大
最后一共出了 8 题，J 几何的思路其实出的大差不差了，赛后改了改就过了
A. Modulo Ruins the Legend
首先转化下题意，令 \(A=n,B=\frac{n\times (n+1)}{2},C=\sum_{i=1}^n a_i\)，则题目要求一组 \(x,y\) 使得 \((Ax+By+C)\bmod m\) 的值最小
然后把这个问题扔给徐神，徐神自然而然地就解决了，真是太神奇了
#include <bits/stdc++.h>
using llsi = long long signed int;
llsi n, m;
std::tuple<llsi, llsi, llsi> exgcd(llsi a, llsi b) {
if(b == 0) return { a, 1, 0 };
auto [gcd, y, x] = exgcd(b, a % b);
y -= a / b * x;
return { gcd, x, y };
}
int main() {
std::ios::sync_with_stdio(false);
std::cin >> n >> m;
llsi A = n, B = (n + 1) * n / 2 % m, C = 0;
if(B == 0) B = m;
for(int i = 0, a; i < n; ++i) std::cin >> a, C += a;
C %= m;
auto [gAm , x1, z1] = exgcd(A, m);
auto [gBm , y2, z2] = exgcd(B, m);
auto [gAll, xz, yz] = exgcd(gAm, gBm);
assert(xz * x1 * A + yz * y2 * B + (z1 * xz + z2 * yz) * m == gAll);
llsi k = C + (m - C) / gAll * gAll;
if(k < m) k += gAll;
k -= m;
std::cout << k << char(10);
llsi x = x1 % m * (xz % m) % m;
llsi y = y2 % m * (yz % m) % m;
assert((x * A + y * B - gAll) % m == 0);
x = x * (k - C) / gAll % m;
y = y * (k - C) / gAll % m;
assert((A * x + B * y - (k - C)) % m == 0);
if(x < 0) x += m;
if(y < 0) y += m;
std::cout << x << ' ' << y << char(10);
return 0;
}
C. No Bug No Game
首先如果 \(\sum_{i=1}^n p_i\le k\)，则答案就是 \(\sum_{i=1}^n w_{i,p_i}\)，否则一定存在某个数作为部分 Buff 进行贡献
考虑直接枚举哪个数 \(i\) 作为部分贡献，然后枚举它贡献的值 \(t\in[0,\min(p_i,k)]\)，则此时要在剩余的数中选出一个 \(\sum p_i=k-t\)，且 \(\sum w_{i,p_i}\) 最大的集合
每次重新跑个背包复杂度肯定会寄，但由于只是少了一个物品，因此可以用经典的前后缀套路来优化
求出前缀/后缀物品对应的背包数组，合并时由于只要知道某个体积的贡献，复杂度是 \(O(k)\) 的，最后总复杂度就是 \(O(nkp)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=3005,INF=1e9;
int n,k,p[N],w[N][15],pre[N][N],suf[N][N];
int main()
{
scanf("%d%d",&n,&k); int sum=0,all=0;
for (RI i=1;i<=n;++i)
{
scanf("%d",&p[i]);
for (RI j=1;j<=p[i];++j)
scanf("%d",&w[i][j]);
sum+=p[i]; all+=w[i][p[i]];
}
if (sum<=k) return printf("%d",all),0;
for (RI j=1;j<=k;++j) pre[0][j]=suf[n+1][j]=-INF;
for (RI i=1;i<=n;++i)
{
for (RI j=0;j<=k;++j) pre[i][j]=pre[i-1][j];
for (RI j=p[i];j<=k;++j) pre[i][j]=max(pre[i][j],pre[i-1][j-p[i]]+w[i][p[i]]);
}
for (RI i=n;i>=1;--i)
{
for (RI j=0;j<=k;++j) suf[i][j]=suf[i+1][j];
for (RI j=p[i];j<=k;++j) suf[i][j]=max(suf[i][j],suf[i+1][j-p[i]]+w[i][p[i]]);
}
int ans=0;
for (RI i=1;i<=n;++i)
{
for (RI t=0;t<=min(p[i],k);++t)
for (RI j=0;j<=k-t;++j)
ans=max(ans,pre[i-1][j]+suf[i+1][k-t-j]+w[i][t]);
}
return printf("%d",ans),0;
}
D. Money Game
令 \(S=\sum_{i=1}^n a_i\)不难发现最后的稳定状态一定为 \(a_1=\frac{2S}{n+1},a_2=a_3=\dots=a_n=\frac{S}{n+1}\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,a[N];
int main()
{
scanf("%d",&n); long long sum=0;
for (RI i=1;i<=n;++i) scanf("%d",&a[i]),sum+=a[i];
printf("%.8lf ",2.0*sum/(n+1));
for (RI i=2;i<=n;++i) printf("%.8lf ",1.0*sum/(n+1));
return 0;
}
F. Da Mi Lao Shi Ai Kan De
签到，按题意模拟即可
#include<cstdio>
#include<iostream>
#include<set>
#include<string>
#define RI register int
#define CI const int&
using namespace std;
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
int n; cin>>n; set <string> ext;
for (RI i=1;i<=n;++i)
{
int m; cin>>m; bool ocr=0;
for (RI j=1;j<=m;++j)
{
string s; cin>>s; bool flag=0;
for (RI k=0;k+2<s.size();++k)
if (s[k]=='b'&&s[k+1]=='i'&&s[k+2]=='e') { flag=1; break; }
if (flag&&!ext.count(s)) ext.insert(s),ocr=1,cout<<s<<'\n';
}
if (!ocr) cout<<"Time to play Genshin Impact, Teacher Rice!\n";
}
return 0;
}
G. Subgraph Isomorphism
这题在 去年暑假前集训图论专题 里出现过，这次就直接 CV 代码了
#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
typedef vector <int> VI;
const int N=100005;
int T,n,m,x,y,pre[N],s,t,hsh[N],idx; VI v[N],C;
bool vis[N],cycle[N]; map <VI,int> rst;
inline bool find_cycle(CI now=1,CI lst=0)
{
for (int to:v[now]) if (to!=lst&&vis[to])
return s=to,t=now,1; else if (!vis[to])
{
vis[to]=1; pre[to]=now;
if (find_cycle(to,now)) return 1; vis[to]=0;
}
return 0;
}
inline void get_hash(CI now,CI fa=0)
{
VI tmp; for (int to:v[now]) if (to!=fa&&!cycle[to])
get_hash(to,now),tmp.push_back(hsh[to]);
sort(tmp.begin(),tmp.end());
if (!rst[tmp]) rst[tmp]=++idx; hsh[now]=rst[tmp];
}
int main()
{
for (scanf("%d",&T);T;--T)
{
RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) vis[i]=cycle[i]=0,v[i].clear();
for (i=1;i<=m;++i) scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
if (m==n-1) { puts("YES"); continue; }
if (m>n) { puts("NO"); continue; }
vis[1]=1; find_cycle(); cycle[s]=1; C.clear(); C.push_back(s);
for (idx=0,rst.clear();t!=s;t=pre[t]) cycle[t]=1,C.push_back(t);
for (int x:C) get_hash(x); bool flag=1;
for (i=1;i<C.size()&&flag;++i) if (hsh[C[i]]!=hsh[C[0]]) flag=0;
if (flag) { puts("YES"); continue; }
if (C.size()%2==1) { puts("NO"); continue; }
for (flag=1,i=2;i<C.size()&&flag;++i) if (hsh[C[i]]!=hsh[C[i&1]]) flag=0;
puts(flag?"YES":"NO");
}
return 0;
}
I. Guess Cycle Length
很有意思的一个交互，把随机和 BSGS 两种做法合起来才能通过
首先有个很自然的 BSGS 思想的做法，设一个阈值 \(S\)，然后进行如下过程：
- 先进行 \(S\) 次
walk 1操作； - 再进行 \(S\) 次
walk S操作；
但这样的话只能用 \(2S\) 次操作得到 \(S^2\) 级别的环，没法直接通过
因此在此之前我们需要进行一些神秘的随机操作，在本题中，直接先随机 \(3000\) 次，每次步长在 \([1,10^9]\) 中随机挑选，同时记录下这个过程中遇到的编号最大的点 \(M\)
考虑 \(N-M\le 10^7\) 的概率，由于 \(10^7\) 是 \(10^9\) 的 \(\frac{1}{100}\)，因此这个概率为 \(1-(\frac{99}{100})^{3000}\)，可以认为不可能出错
然后由于 \(3200^2\ge 10^7\)，因此我们可以编出如下做法：
- 进行 \(3000\) 次随机操作，记录下遇到的点编号的最大值；
- 进行 \(3200\) 次
walk 1操作； - 进行 \(1\) 次
walk M操作； - 进行 \(3200\) 次
walk 3200操作；
注意到进行第三次操作后相当于回退了 \(N-M\) 步，因此我们只需要用那个 BSGS 的做法确定 \(N-M\) 的值即可
#include<cstdio>
#include<iostream>
#include<random>
#include<map>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
bool debug=0;
int n,cur,p[10000000];
map <int,int> mp;
mt19937 rng(0x0d000721);
inline int randint(CI l, CI r)
{
return uniform_int_distribution{l, r}(rng);
}
inline int ask(int x)
{
if (x==0) x=randint(1,1000000000);
if (debug)
{
(cur+=x)%=n; return p[cur];
} else
{
printf("walk %d\n",x); fflush(stdout);
int res; scanf("%d",&res); return res;
}
}
inline void answer(CI x)
{
printf("guess %d\n",x); fflush(stdout);
}
int main()
{
if (debug)
{
scanf("%d",&n); cur=0;
for (RI i=0;i<n;++i) p[i]=i;
shuffle(p,p+n,rng);
}
int M=0;
for (RI i=1;i<=3000;++i) M=max(M,ask(0));
for (RI i=1;i<=3200;++i)
{
int pos=ask(1);
if (mp.count(pos)) return answer(i-mp[pos]),0;
mp[pos]=i;
}
int pos=ask(M);
if (mp.count(pos)) return answer(M+3200-mp[pos]),0;
for (RI i=1;i<=3200;++i)
{
int pos=ask(3200);
if (mp.count(pos)) return answer(3200*i+M+3200-mp[pos]),0;
}
return 0;
}
J. Painting
徐神秒切的几何，但好像细节有点多
大致思路就是非显示地维护凸包，令挡住某条线段 \(p\) 的线段为 \(q\)，则建一颗树，\(q\) 就是 \(p\) 的父亲
询问时先求出在两边墙上距离当前线段最近的两条线段 \(u,v\)，则 \(u,v\) 在树上的路径构成了一个凸壳，在上面二分找交点即可
用倍增实现树上操作，总复杂度 \(O(n\log n)\)
#include<bits/stdc++.h>
using namespace std;
#define int __int128
#define ft first
#define sd second
int gcd(int a, int b) {return 0==b ? a : gcd(b, a%b);}
struct Frac{
__int128 up, dn;
bool operator<(const Frac &b) {
return up*b.dn < dn*b.up;
}
pair<long long, long long> divd() {
int g = gcd(up, dn);
// printf("g=%d up=%d dn=%d\n", (signed)g, (signed)up, (signed)dn);
return {up/g, dn/g};
}
};
struct Pt {
int x, y;
Pt operator-(const Pt &b)const {return Pt{x-b.x, y-b.y};}
int crs(const Pt &b) const {return x*b.y - y*b.x;}
int check(pair<Frac, Frac> p, Pt ppp) {
int res = x*(p.sd.up - ppp.y*p.sd.dn) - y*(p.ft.up - ppp.x*p.ft.dn);
return (0==res ? 0 : (res>0 ? 1 : -1));
}
};
pair<Frac, Frac> ins(Pt p1, Pt v1, Pt p2, Pt v2) {
Frac x, y;
int res1 = v1.crs(v2), res2 = v2.crs(p1-p2);
x.dn = y.dn = res1;
x.up = p1.x*res1 + v1.x*res2;
y.up = p1.y*res1 + v1.y*res2;
if (res1<0) {
x.dn = -x.dn; y.dn = -y.dn;
x.up = -x.up; y.up = -y.up;
}
// printf("p1(%d %d) p2(%d %d) v1(%d %d) v2(%d %d)\n", (signed)p1.x, (signed)p1.y, (signed)p2.x, (signed)p2.y, (signed)v1.x, (signed)v1.y, (signed)v2.x, (signed)v2.y);
// printf("x.up=%d x.dn=%d res1=%d res2=%d\n", (signed)x.up, (signed)x.dn, (signed)res1, (signed)res2);
return {x, y};
}
const int INF = (int)1e6+5;
const int N = 3e5+5;
const int B = 21;
signed n, W;
int fa[B][N], dep[N];
Pt seg[N][2];
pair<Frac, Frac> insp[N];
set<pair<int, int>> st;
int LCA(int x, int y) {
if (dep[x]<dep[y]) swap(x, y);
for (int j=B-1; j>=0; --j) if (dep[fa[j][x]]>=dep[y]) x=fa[j][x];
if (y==x) return x;
for (int j=B-1; j>=0; --j) if (fa[j][x]!=fa[j][y]) x=fa[j][x], y=fa[j][y];
return fa[0][x];
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> W;
fa[0][0] = 0; dep[0] = 0;
fa[0][n+1] = fa[0][n+2] = 0; dep[n+1] = dep[n+2] = 1;
insp[n+1] = {{W,1}, {INF, 1}};
insp[n+2] = {{W,1}, {-INF, 1}};
st.insert({INF, n+1}); st.insert({-INF, n+2});
for (int i=1; i<=n; ++i) {
signed a, b, c; cin >> a >> b >> c;
seg[0][0] = {W, INF}; seg[0][1] = {W, -INF};
seg[i][0] = {0, a}; seg[i][1] = {W, b};
auto it2 = st.lower_bound({a, -1});
auto it1 = it2; --it2;
// printf("11111\n");
Pt v = Pt{W, b} - Pt{0, a};
int lca = LCA(it1->sd, it2->sd);
auto getFa = [&](int cur1, Pt ppp, int sg) {
if (v.check(insp[cur1], ppp)*sg < 0) return cur1;
for (int j=B-1; j>=0; --j) if (fa[j][cur1] && dep[fa[j][cur1]]>dep[lca]){
if (v.check(insp[fa[j][cur1]], ppp)*sg > 0) cur1 = fa[j][cur1];
}
cur1 = fa[0][cur1];
if (dep[cur1] <= dep[lca]) return (__int128)-1;
return cur1;
};
int cur;
int cur1 = getFa(it1->sd, seg[i][0], 1);
int cur2 = getFa(it2->sd, seg[i][0], -1);
// printf("i=%d cur1=%d\n", (signed)i, (signed)cur1);
// printf("i=%d cur2=%d\n", (signed)i, (signed)cur2);
if (-1==cur1 && -1==cur2) {
cur = lca;
insp[i] = ins(seg[i][0], seg[i][1]-seg[i][0], seg[lca][0], seg[lca][1]-seg[lca][0]);
} else {
Frac x1, y1, x2, y2;
if (-1==cur1) x1 = {INF, 1}, y1 = {INF, 1};
else {
auto pii = ins(seg[i][0], seg[i][1]-seg[i][0], seg[cur1][0], seg[cur1][1]-seg[cur1][0]);
x1 = pii.ft, y1 = pii.sd;
}
if (-1==cur2) x2 = {INF, 1}, y2 = {INF, 1};
else {
auto pii = ins(seg[i][0], seg[i][1]-seg[i][0], seg[cur2][0], seg[cur2][1]-seg[cur2][0]);
x2 = pii.ft, y2 = pii.sd;
}
if (x1 < x2) insp[i] = {x1, y1}, cur=cur1;
else insp[i] = {x2, y2}, cur=cur2;
}
auto [x1, y1] = insp[i];
auto [xup, xdn] = x1.divd();
auto [yup, ydn] = y1.divd();
cout << "(" << xup << "/" << xdn << "," << yup << "/" << ydn <<")\n";
// printf("i=%d cur=%d\n", (signed)i, (signed)cur);
if (c>0) {
st.insert({a, i});
fa[0][i] = cur;
dep[i] = dep[cur]+1;
for (int j=1; j<B; ++j) fa[j][i] = fa[j-1][fa[j-1][i]];
}
}
return 0;
}
K. Master of Both
徐神开场就秒了，我题意都没看
#include <bits/stdc++.h>
constexpr int $n = 500005;
constexpr int $ss = 1000006;
int n, q;
int64_t ctr[26][26], pans = 0;
int go[$ss][26], sum[$ss], O = 0;
int main() {
std::ios::sync_with_stdio(false);
std::cin >> n >> q;
for(int i = 0; i < n; ++i) {
std::string s; std::cin >> s;
int cur = 0;
for(auto ch: s) {
int u = ch - 'a';
for(int j = 0; j < 26; ++j) if(j != u && go[cur][j])
ctr[j][u] += sum[go[cur][j]];
if(!go[cur][u]) go[cur][u] = ++O;
cur = go[cur][u];
sum[cur]++;
}
for(int i = 0; i < 26; ++i) if(go[cur][i]) pans += sum[go[cur][i]];
}
// for(int i = 0; i < 26; ++i) for(int j = 0; j < 26; ++j)
// std::cerr << ctr[i][j] << char(j == 25 ? 10 : 32);
while(q--) {
std::string s; std::cin >> s;
int rk[26];
for(int i = 0; i < 26; ++i) rk[s[i] - 'a'] = i;
int64_t ans = pans;
for(int i = 0; i < 26; ++i) for(int j = 0; j < 26; ++j) if(rk[i] > rk[j] && ctr[i][j])
// std::cerr << "ctr[" << i << "][" << j << "] = " << ctr[i][j] << char(10),
ans += ctr[i][j];
std::cout << ans << char(10);
}
return 0;
}
M. Please Save Pigeland
注意到如果选择在某个点 \(x\) 修医院，则我们求出 \(x\) 到所有关键点的距离，记为 \(l_1,l_2,\dots,l_k\)，则它的贡献就是 \(2\times \frac{\sum_{i=1}^k l_i}{\gcd_{i=1}^k l_i}\)
考虑切换 \(x\) 时用换根 DP 维护这两个值，分子显然是很基础的加减模型，但分母无法直接维护，因为涉及经过一条边后的全体数加上一个值
但徐神神之一手发现可以令一个二元组 \((v,g)\) 来表示子树信息，\(v\) 表示一条到当前点的路径长度，\(g\) 表示剩下路径与 \(v\) 的差值的 \(\gcd\)
这样集体加 \(w\) 就有 \((v,g)\to (v+w,g)\)；同时合并两个子树有 \((v_1,g_1)+(v_2,g_2)\to (v_1,\gcd(g_1,g_2,|v_1-v_2|))\)，然后就也可以套换根 DP 模型了
实现的时候注意各种奇奇怪怪的细节，尤其是子树内没有关键点的状态需要单独设
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=500005,INF=1e18;
int n,k,x,y,z,key[N],ans,sum[N],sz[N]; vector <pi> v[N];
struct ifo
{
int v,g;
inline ifo(CI V=-1,CI G=-1)
{
v=V; g=G;
}
inline void add(CI x) { v+=x; }
friend inline ifo operator + (const ifo& A,const ifo& B)
{
if (A.v==-1) return B; if (B.v==-1) return A;
return ifo(A.v,__gcd(__gcd(A.g,B.g),abs(A.v-B.v)));
}
}f[N]; vector <ifo> pre[N],suf[N];
inline void DFS1(CI now=1,CI fa=0)
{
sz[now]=key[now]; sum[now]=0; if (key[now]) f[now]=ifo(0,0);
vector <pi> sons;
for (auto [to,w]:v[now]) if (to!=fa) sons.push_back({to,w});
v[now]=sons;
for (auto [to,w]:v[now])
{
DFS1(to,now); sz[now]+=sz[to];
sum[now]+=sum[to]+w*sz[to];
pre[now].push_back(f[to]+pre[to].back());
if (sz[to]) pre[now].back().add(w);
suf[now].push_back(f[to]+pre[to].back());
if (sz[to]) suf[now].back().add(w);
}
if (pre[now].empty()) pre[now].push_back(ifo());
if (suf[now].empty()) suf[now].push_back(ifo());
for (RI i=1;i<(int)pre[now].size();++i) pre[now][i]=pre[now][i-1]+pre[now][i];
for (RI i=(int)suf[now].size()-2;i>=0;--i) suf[now][i]=suf[now][i+1]+suf[now][i];
}
inline void DFS2(CI now=1,CI fa=0,CI out_sz=0,CI out_sum=0,const ifo& out_f=ifo())
{
int cur_sum=sum[now]+out_sum;
ifo cur_f=f[now]+pre[now].back()+out_f;
int cur_gcd=__gcd(cur_f.v,cur_f.g);
// printf("now = %lld, sum = %lld, gcd = %lld\n",now,cur_sum,cur_gcd);
if (cur_gcd!=0) ans=min(ans,cur_sum/cur_gcd); else ans=0;
for (RI i=0;i<v[now].size();++i)
{
auto [to,w]=v[now][i];
ifo tmp_f=f[now]+(i-1>=0?pre[now][i-1]:ifo())+(i+1<v[now].size()?suf[now][i+1]:ifo())+out_f;
if (out_sz+sz[now]-sz[to]) tmp_f.add(w);
DFS2(to,now,out_sz+sz[now]-sz[to],out_sum+sum[now]-(sum[to]+w*sz[to])+(out_sz+sz[now]-sz[to])*w,tmp_f);
}
}
signed main()
{
scanf("%lld%lld",&n,&k); ans=INF;
for (RI i=1;i<=k;++i) scanf("%d",&x),key[x]=1;
for (RI i=1;i<n;++i)
{
scanf("%lld%lld%lld",&x,&y,&z);
v[x].push_back({y,z}); v[y].push_back({x,z});
}
DFS1(); DFS2(); printf("%lld",2LL*ans);
return 0;
}
Postscript
接下来的几天大家好像都有考试啥的，感觉不太抽得出时间来训了
下周开始就要连战三战了，希望能打个令人满意的成绩吧
标签：include,cur,Contest,int,sum,Regional,Programming,seg,now From： https://www.cnblogs.com/cjjsb/p/18536975