Preface
北京市赛（×），小 WF（确信）
感觉这场题总体都挺难的，除了前 1h 出了两个题后，后面基本上都是 1h 出一题
然后最后 1h 发生了经典的我和徐神 B,F 双开双会，最后开始抢机时，最后经典的一个没写出来
赛后发现 F 赛时代码改个初值就能过了，而徐神多花了半小时也是成功把 B 过了
只能说还是经典前期写题太慢，导致后期机时不足，还得多练练的说
B. 组合数
不难发现刨除掉 \(v=0/1\) 的情况后有用的值很少，同时 \(m>20\) 的很多情况也显然无解
所以这题最后本质就是个没啥意思的暴力题，具体实现看徐神代码
#include <bits/stdc++.h>
using llsi = long long signed int;
constexpr llsi threshold = 1'000'000'000;
__int128_t _C[500000][18];
__int128_t C(llsi u, llsi v) {
if(_C[u][v]) return _C[u][v];
__int128_t res = 1;
for(llsi i = u - v + 1; i <= u; ++i) res *= i;
for(llsi i = 2; i <= v; ++i) res /= i;
return _C[u][v] = res;
}
llsi query(llsi a, llsi b, int n, int m) {
if(n < 2 * b) return 0;
if(b > m) return 0;
if(b <= 8) {
__int128_t l = -1, r = 100000, mid;
while(l < r) {
mid = (l + r + 1) >> 1;
if(C(b + b + mid, b) <= a) l = mid;
else r = mid - 1;
}
return std::min(l + 1, __int128_t(n) - 2 * b + 1);
} else {
llsi i;
for(i = 0; C(b + b + i, b) <= a; ++i);
return std::min(i, n - 2 * b + 1);
}
}
std::vector<llsi> hkr[18];
std::map<llsi, std::vector<std::pair<int, int>>> mp;
std::vector< std::pair<int, std::vector< std::pair<int, int> > > > cor;
int main() {
std::ios::sync_with_stdio(false);
for(int i = 2; i < 18; ++i) {
for(int j = 0; ; ++j) {
llsi P = C(i + i + j, i);
if(P > threshold) break;
hkr[i].emplace_back(P);
mp[P].push_back({i + i + j, i});
}
// std::cerr << hkr[i].size() << char(10);
}
for(auto [k, v]: mp) if(v.size() > 1)
cor.emplace_back(k, v);
int q; std::cin >> q;
while(q--) {
int l, r, n, m, ans = 0; std::cin >> l >> r >> n >> m;
if(m == 0) {
std::cout << (l == 1) << char(10);
continue;
}
if(l <= n) ans += std::min(r, n) - l + 1, l = n + 1;
if(l > r) {
std::cout << ans << char(10);
continue;
}
for(int i = 2; i <= 16; ++i) {
ans += query(r, i, n, m) - query(l - 1, i, n, m);
}
for(auto [c, v]: cor) {
if(c > r || c < l) continue;
int tt = 0;
for(auto [a, b]: v) {
if(a > n || b > m) continue;
tt += 1;
}
if(tt >= 2) ans -= tt - 1;
}
std::cout << ans << char(10);
}
return 0;
}
D. 树
手玩发现一个点是否需要删掉仅和与其相连的两个点有关，因此直接判断某个点 \(c\) 是否在另外两点 \(a,b\) 间的路径上即可
实现的话求出 \(\operatorname{LCA}(a,b)=f\) ，检验 \(c\) 和 \(f\) 的深度关系；如果合法就把 \(a,b\) 跳到与 \(c\) 同深度的位置判断是否相同即可
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,m,q,x,y,b[N],dep[N],anc[N][20],ans; vector <int> v[N];
inline void DFS(CI now=1,CI fa=0)
{
dep[now]=dep[fa]+1; anc[now][0]=fa;
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) DFS(to,now);
}
inline int getLCA(int x,int y)
{
if (dep[x]<dep[y]) swap(x,y);
for (RI i=19;i>=0;--i)
if (dep[anc[x][i]]>=dep[y]) x=anc[x][i];
if (x==y) return x;
for (RI i=19;i>=0;--i)
if (anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
return anc[x][0];
}
inline bool onpath(int x,CI tar)
{
for (RI i=19;i>=0;--i)
if (dep[anc[x][i]]>=dep[tar]) x=anc[x][i];
return x==tar;
}
inline bool check(CI x)
{
if (x==1||x==m) return 1;
int u=b[x-1],v=b[x+1],w=b[x],fa=getLCA(u,v);
if (dep[w]<dep[fa]) return 1;
return !(onpath(u,w)||onpath(v,w));
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for (RI i=1;i<n;++i)
scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
DFS();
for (RI i=1;i<=m;++i) scanf("%d",&b[i]);
for (RI i=1;i<=m;++i) ans+=check(i);
for (RI i=1;i<=q;++i)
{
scanf("%d%d",&x,&y);
if (x-1>=1) ans-=check(x-1);
if (x+1<=m) ans-=check(x+1);
ans-=check(x); b[x]=y;
if (x-1>=1) ans+=check(x-1);
if (x+1<=m) ans+=check(x+1);
ans+=check(x);
printf("%d\n",ans);
}
return 0;
}
E. 骰子
神秘卷积题，想到分治这个思路了就不难
考虑分治求解，根据经典套路我们仅需要考虑跨过区间中点的情况
如果分别求出 \([i,mid]\) 这段后缀以及 \([mid+1,j]\) 这段前缀的信息然后合并的话，复杂度不免会来到 \(O(n^2m^2)\)，因此要考虑优化掉一维
考虑枚举 \(i,j\) 的部分不可省略，而最后计算答案假设 \([i,mid]\) 中选了和为 \(k\) 的方案，那么 \([mid+1,r]\) 中可以选 \(l\le m-k\) 的方案，这个可以前缀和优化掉
具体地，令 \(f_{i,j}\) 表示处理了从中点到 \(i\) 的这段后缀/前缀，总和为 \(j\) 的概率；\(dp_{i,j,k}\) 表示在 \([mid+1,i]\) 中，左侧区间选了和为 \(j\) 的方案，右侧区间选了和为 \(k\) 的方案的期望，最后把 \(dp_{i,j,k}\) 的最后一维做一个前缀和即可
具体转移实现看代码，复杂度 \(O(n^2m+nm^2)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1505,M=205,mod=1e9+7;
int n,m,q,p[N][M],b[M],f[N][M],ans[N][N],dp[N][M][M];
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
inline void solve(CI l,CI r)
{
if (l==r)
{
for (RI i=0;i<=m;++i) inc(ans[l][l],1LL*p[l][i]*b[i]%mod);
return;
}
int mid=l+r>>1; solve(l,mid); solve(mid+1,r);
for (RI i=0;i<=m;++i) f[mid][i]=p[mid][i],f[mid+1][i]=p[mid+1][i];
for (RI i=mid-1;i>=l;--i)
{
for (RI j=0;j<=m;++j) f[i][j]=0;
for (RI j=0;j<=m;++j) for (RI k=0;j+k<=m;++k)
inc(f[i][j+k],1LL*f[i+1][j]*p[i][k]%mod);
}
for (RI i=mid+2;i<=r;++i)
{
for (RI j=0;j<=m;++j) f[i][j]=0;
for (RI j=0;j<=m;++j) for (RI k=0;j+k<=m;++k)
inc(f[i][j+k],1LL*f[i-1][j]*p[i][k]%mod);
}
for (RI i=mid+1;i<=r;++i)
{
for (RI j=0;j<=m;++j) for (RI k=0;j+k<=m;++k)
dp[i][j][k]=1LL*f[i][k]*b[j+k]%mod;
for (RI j=0;j<=m;++j) for (RI k=1;j+k<=m;++k)
inc(dp[i][j][k],dp[i][j][k-1]);
}
for (RI i=l;i<=mid;++i) for (RI j=mid+1;j<=r;++j)
for (RI k=0;k<=m;++k) inc(ans[i][j],1LL*f[i][k]*dp[j][k][m-k]%mod);
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for (RI i=0;i<=m;++i) scanf("%d",&b[i]);
for (RI i=1;i<=n;++i) for (RI j=0;j<=m;++j)
scanf("%d",&p[i][j]),p[i][j]%=mod;
for (solve(1,n);q;--q)
{
int l,r; scanf("%d%d",&l,&r);
printf("%d\n",ans[l][r]);
}
return 0;
}
F. 保区间最小值一次回归问题
感觉很公式化的一个题，很多地方都是经典套路，不过实现的时候有一些细节
不妨先令 \(\{b\}=\{a\}\)，考虑按照 \(v_i\) 的值从大到小对序列进行 fix
不难发现不同的 \(v_i\) 之间不会有影响，因为我们总是找出区间内最小的数并将其变为当前的 \(v_i\)，如果这个值之前被操作过则说明无解
因此不难发现一个位置只会被一个 \(v_i\) 的值操作过，可以用经典的并查集来维护所有没被操作过的位置
将所有 \(v_i\) 相同的三元组一起考虑，并找出此时所有没被操作过的位置，不难发现此时问题变为一个经典的模型
即要在一个序列上选择若干个位置，每个位置有不同的选择代价，要求所有给出的区间内要有至少一个选中的位置
这是个经典的 DP 模型，令 \(f_i\) 表示钦定 \(i\) 被选的最小代价，对于一个右端点 \(i\) 考虑哪些点 \(j\) 是合法的左端点
一个充要条件是 \([j+1,i-1]\) 不包含任意一个完整的区间，因此很容易求出能转移到每个 \(i\) 的合法区间，用线段树维护下即可
总复杂度 \(O((n+m)\log n)\)
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=500005,INF=1e18;
struct ifo
{
int l,r,v;
friend inline bool operator < (const ifo& A,const ifo& B)
{
return A.v>B.v;
}
}O[N]; int t,n,m,tl,tr,a[N],fa[N],mxp[N];
inline int getfa(CI x)
{
return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
class Segment_Tree
{
private:
int mn[N<<2];
public:
#define TN CI now=1,CI l=tl,CI r=tr
#define LS now<<1,l,mid
#define RS now<<1|1,mid+1,r
inline void build(TN)
{
if (l==r) return (void)(mn[now]=INF);
int mid=(l+r)/2; build(LS); build(RS);
}
inline int query(CI beg,CI end,TN)
{
if (beg>end) return INF;
if (beg<=l&&r<=end) return mn[now]; int mid=(l+r)/2,ret=INF;
if (beg<=mid) ret=min(ret,query(beg,end,LS));
if (end>mid) ret=min(ret,query(beg,end,RS));
return ret;
}
inline void update(CI pos,CI mv,TN)
{
if (l==r) return (void)(mn[now]=mv); int mid=(l+r)/2;
if (pos<=mid) update(pos,mv,LS); else update(pos,mv,RS);
mn[now]=min(mn[now<<1],mn[now<<1|1]);
}
#undef TN
#undef LS
#undef RS
}SEG;
inline int solve(CI l,CI r,CI v)
{
vector <int> vec;
for (RI i=l;i<=r;++i)
{
int x=getfa(O[i].l);
while (x<=O[i].r)
{
vec.push_back(x);
fa[x]=x+1; x=getfa(x);
}
}
sort(vec.begin(),vec.end());
for (RI i=0;i<vec.size();++i) mxp[i]=-1;
for (RI i=l;i<=r;++i)
{
int L=lower_bound(vec.begin(),vec.end(),O[i].l)-vec.begin();
int R=upper_bound(vec.begin(),vec.end(),O[i].r)-vec.begin()-1;
if (L>R) return -1; else mxp[R]=max(mxp[R],L);
}
tl=0; tr=vec.size(); SEG.build(); SEG.update(0,0);
int lst=-1;
for (RI i=0;i<vec.size();++i)
{
if (i-1>=0) lst=max(lst,mxp[i-1]);
int tmp=SEG.query(lst+1,i)+abs(a[vec[i]]-v);
SEG.update(i+1,tmp);
if (a[vec[i]]<=v) lst=i;
}
lst=max(lst,mxp[vec.size()-1]);
return SEG.query(lst+1,vec.size());
}
signed main()
{
//freopen("F.in","r",stdin);
for (scanf("%lld",&t);t;--t)
{
scanf("%lld%lld",&n,&m);
for (RI i=1;i<=n;++i) scanf("%lld",&a[i]);
for (RI i=1;i<=n+1;++i) fa[i]=i;
for (RI i=1;i<=m;++i) scanf("%lld%lld%lld",&O[i].l,&O[i].r,&O[i].v);
sort(O+1,O+m+1); bool flag=1; int ans=0;
for (RI i=1;i<=m;)
{
int j=i;
while (j+1<=m&&O[j+1].v==O[i].v) ++j;
int tmp=solve(i,j,O[i].v);
if (tmp==-1) { flag=0; break; }
ans+=tmp; i=j+1;
}
if (!flag) puts("-1"); else printf("%lld\n",ans);
}
return 0;
}
G. 后继
中间我写题的时候徐神 solo 出来的，我对做法一无所知
#include <bits/stdc++.h>
int a[400005], ch[12000005][2], dfn[12000005], dfr[12000005], tag[12000005], itag[400005], O = 1, frk[30], x;
int query(int p) {
std::cout << "? " << p << std::endl;
int res; std::cin >> res;
if(res == -2) exit(1);
return res;
}
void dfs(int cur, int dep) {
static int T = 1;
dfn[cur] = T++;
if(ch[cur][0]) dfs(ch[cur][0], dep - 1);
if(ch[cur][1]) dfs(ch[cur][1], dep - 1);
if(ch[cur][0] && ch[cur][1]) frk[dep] = cur;
dfr[cur] = T;
}
int pick_largest(int cur, int dep) {
if(dep == -1) return cur;
if(ch[cur][0] && !ch[cur][1]) return pick_largest(ch[cur][0], dep - 1);
if(ch[cur][1] && !ch[cur][0]) return pick_largest(ch[cur][1], dep - 1);
return pick_largest(ch[cur][(x >> dep & 1) ^ 1], dep - 1);
}
int main() {
std::ios::sync_with_stdio(false);
memset(frk, -1, sizeof frk);
int n, m; std::cin >> n >> m;
for(int i = 1; i <= n; ++i) std::cin >> a[i];
for(int i = 1; i <= n; ++i) {
int t = a[i], cur = 1;
for(int j = 29; ~j; --j) {
int u = t >> j & 1;
if(!ch[cur][u]) ch[cur][u] = ++O;
cur = ch[cur][u];
}
tag[cur] = i;
itag[i] = cur;
}
dfs(1, 29);
while(m--) {
x = 0;
for(int k = 0; k < 30; ++k) {
if(frk[k] == -1) continue;
int largest = tag[pick_largest(frk[k], k)];
int next = query(largest);
if(next < 0) continue;
next = itag[next];
if(dfn[frk[k]] <= dfn[next] && dfn[next] <= dfr[frk[k]])
x |= 1 << k;
}
std::cout << "! " << x << std::endl;
}
return 0;
}
H. BFS 序 0
刚开始徐神想写一个神秘的在虚树上操作的做法，后面我发现了种更好写的做法就把徐神赶下来在他代码上写了
首先判掉一些显然无解的情况后，不难发现只有相邻的同层点之间会有 bound
考虑建立一张新的有向图，边 \(u\to v\) 的含义就是 \(u\) 要在 \(v\) 之前访问，显然如果新图是个 DAG 则有解，否则一定无解
直观的想法是对于相邻的同层点 \(x,y\) ，\(x\to y,fa(x)\to fa(y),fa(fa(x))\to fa(fa(y)),\dots\) 这些边都要连，直到两个点跳父亲到达其 \(\operatorname{LCA}\) 为止
但这样边数显然会爆，不过我们手玩一下会发现只连最上层的边即可，即将两个点跳到它们 \(\operatorname{LCA}\) 的儿子处连边，最后跑一个拓扑排序即可
#include <bits/stdc++.h>
std::vector <int> G[300005];
int deg[300005];
void work() {
int n; std::cin >> n;
std::vector<int> pa(n, 0);
std::vector<std::vector<int>> ch(n), loop(n);
std::vector<int> dfn(n), dep(n);
for(int i = 1; i < n; ++i) std::cin >> pa[i], pa[i]--, ch[pa[i]].emplace_back(i);
int O = 0;
auto dfs = [&](auto dfs, int cur) -> void {
dfn[cur] = O++;
loop[cur].emplace_back(pa[cur]);
while(loop[cur].back() != 0) {
if(loop[loop[cur].back()].size() < loop[cur].size()) break;
loop[cur].emplace_back(loop[loop[cur].back()][loop[cur].size() - 1]);
}
for(auto ch: ch[cur]) dep[ch] = dep[cur] + 1, dfs(dfs, ch);
};
auto lca = [&](int a, int b) -> int {
if(dep[a] < dep[b]) std::swap(a, b);
for(int i = 20; ~i; --i) if((dep[a] - dep[b]) & (1 << i)) a = loop[a][i];
if(a == b) return a;
for(int i = 20; ~i; --i) if(loop[a].size() > i && loop[a][i] != loop[b][i])
a = loop[a][i], b = loop[b][i];
return loop[a][0];
};
auto jump = [&](int &x, int step) {
assert(dep[x] >= step);
for (int i=20;i>=0;--i) if ((step>>i)&1) x=loop[x][i];
};
dep[0] = 0;
dfs(dfs, 0);
// std::cerr << loop[9][0] << " " << loop[9][1] << char(10);
// std::cerr << lca(10, 9) << char(10);
// return ;
int q; std::cin >> q;
auto query = [&]() -> bool {
int m; std::cin >> m;
std::vector<int> b(m);
for(auto &b: b) std::cin >> b, b--;
std::vector <int> ext;
for (int i=0;i+1<m;++i)
if (dep[b[i+1]]<dep[b[i]]||b[i]==b[i+1]) return false;
for (int i=0;i+1<m;++i)
{
int x=b[i],y=b[i+1];
if (dep[x]!=dep[y]) continue;
int z=lca(x,y);
// printf("(%d %d %d)\n",x,y,z);
jump(x,dep[x]-dep[z]-1); jump(y,dep[y]-dep[z]-1);
ext.push_back(x); ext.push_back(y);
G[x].push_back(y); ++deg[y];
}
std::sort(ext.begin(),ext.end());
ext.erase(std::unique(ext.begin(),ext.end()),ext.end());
std::queue <int> Q; int cnt=0;
for (auto x:ext) if (!deg[x]) Q.push(x),++cnt;
while (!Q.empty())
{
int now=Q.front(); Q.pop();
for (auto to:G[now])
if (!--deg[to]) Q.push(to),++cnt;
}
for (auto x:ext) G[x].clear(),deg[x]=0;
return cnt==(int)ext.size();
};
while(q--) std::cout << (query() ? "Yes\n" : "No\n");
return ;
}
int main() {
// freopen("H.in","r",stdin);
std::ios::sync_with_stdio(false);
int T = 1; while(T--) work();
return 0;
}
K. 乘二
首先将所有数按照二进制下最高位分类放入桶中，每个桶内元素从小到大排序
首先从最高位小的桶开始模拟，直到 \(k\) 为 \(0\) 或者所有数都在一个桶中，后者可以直接快速算出每个数被乘的次数
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,mod=1e9+7;
int n,k; vector <int> vec[35];
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;
}
int main()
{
scanf("%d%d",&n,&k);
for (RI i=1;i<=n;++i)
{
int x; scanf("%d",&x);
auto highbit=[&](int x)
{
int k=0; while (x>0) ++k,x>>=1;
return k;
};
vec[highbit(x)].push_back(x);
}
for (RI i=0;i<31;++i)
{
sort(vec[i].begin(),vec[i].end());
if ((int)vec[i].size()==n)
{
int d=k/n,r=k%n,sum=0;
for (RI j=0;j<r;++j)
(sum+=1LL*vec[i][j]%mod*quick_pow(2,d+1)%mod)%=mod;
for (RI j=r;j<n;++j)
(sum+=1LL*vec[i][j]%mod*quick_pow(2,d)%mod)%=mod;
return printf("%d",sum),0;
}
for (auto &x:vec[i])
{
if (k==0)
{
int sum=0;
for (RI j=0;j<31;++j)
for (auto x:vec[j]) (sum+=x%mod)%=mod;
return printf("%d",sum),0;
}
--k; vec[i+1].push_back(x<<1); x=0;
}
vec[i].clear();
}
return 0;
}
Postscript
感觉这场好可惜，如果中期想题写题快一点的话是有机会 7 题的，还是太菜太菜
标签：std,竞赛,return,cur,int,2024,dep,ch,程序设计 From： https://www.cnblogs.com/cjjsb/p/18442941