DTOJ 2023.02.11 测试 题解
2023 省选模拟 Round #12
\(100+8+50=158\)
还行 T2 想到了，但是没写，我觉得写了也不一定写得出来，挺妙的
T1
题意
http://59.61.75.5:18018/p/5455
铃是一个爱玩游戏的女孩子。
她在游戏中想要炼制一种稀有合金 —— 这需要 \(n\) 种金属来合成。
她准备好矿石后建造了 \(k\) 个不同的熔炉，当熔炉启动时，会随机炼出这 \(n\) 种金属中的一些（也可能什么都没有）。
如果把每个熔炉炼出的金属收集起来，有了全部 \(n\) 种金属，就能造出合金了。澪对此很好奇，对铃说：「我考考你，有多少种情况可以炼出合金呢？」这个简单的问题铃很快就会做了，你能求出结果吗？
答案可能很大，请对 \(998244353\) 取模（即除以 \(998244353\) 的余数）后输出。
题解
水题 不知道为什么放测试里了
可以独立考虑每种金属，每种都不能是空集，所以是 \((2^k-1)^n\)
听说有人在容斥和二项式反演。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 998244353;
int n,k;
int qpow(int a, int b)
{
int r=1;
for(; b; b>>=1,a=(ll)a*a%P) if(b&1) r=(ll)a*r%P;
return r;
}
int main()
{
scanf("%d%d",&n,&k);
printf("%d\n",qpow(qpow(2,k)-1,n));
return 0;
}
T2
题意
http://59.61.75.5:18018/p/5456
给定一个 \(n\) 个点的有向无环图，点编号为 \(1 \sim n\)。有 \(m\) 条边，每条边被染上黑色或白色。保证从 \(1\) 号点出发能到达任意点。
给定 \(q\) 个询问，第 \(i\) 次询问给定 \(a_i, b_i, x_i\)。将所有黑色边的权值设为 \(a_i\)，所有白色边的权值设为 \(b_i\) 后，求从 \(1\) 号点到 \(x\) 号点的最短路长度。
对于所有数据，满足 \(1 \le n, q \le 5 \times 10 ^ 4\)，\(1 \le m \le 10 ^ 5\)，\(1 \le u_i < v_i \le n\)，\(v_i - u_i \le 1000\)，\(c_i \in \{0, 1\}\)，\(1 \le a_i, b_i \le 10 ^ 4\)，\(1 \le x_i \le n\)。保证从 \(1\) 号点出发能到达任意点。
题解
暴力拓扑很好想，注意拓扑序一定是 \(1\sim n\)，直接 \(O(qm)\)
注意 DAG 上的最短路可以拓扑排序
正解也很好想
注意到你可以带着 \(a,b\) 一起求最短路，回答询问时把 \(a,b\) 带进去即可
这样子每一个点的最短路一定是 \(\min(xa+yb)\) 的形式
容易发现这时候 \((x,y)\) 形成一个凸包，因为 \(xa+yb=t\) 是一系列平行线，如果一个 \((x,y)\) 在凸包里，那一定不会对任意的 \((a,b)\) 产生贡献（可以自己画画图理解一下）
于是你维护凸包，一遍拓扑排序一遍回答，\(v_i-u_i\leq 1000\) 还让你空间不超限
这看着太对了吧，分析一下复杂度 \(x\in (1,n)\) 凸包大小是 \(O(n)\) 的啊，所以时间复杂度是 \(O(nm)\) 的
于是我选择写暴力（
事实上有一个很厉害的结论，竟然是论文题，结论是这样的：
\(1\leq x,y\leq n\) 有一个右下严格凸包，凸包上点是整点，则凸包点数 \(O(n^{2/3})\)
证明也不难，我觉得还挺妙的
于是你的复杂度就是 \(O(n^{2/3}m)\)，可以通过本题
具体怎么合并凸包：使用类似归并排序的东西，详细看代码
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e4+5, M = 1e5+5, Rl = 1005, N23 = 1500, inf = 1e9;
int n,m,q;
struct edge { int v,c; };
vector<edge> g[N];
struct pnt
{
int x,y;
friend bool operator< (const pnt &A, const pnt &B) { return A.x<B.x or (A.x==B.x and A.y<B.y); }
friend pnt operator- (const pnt &A, const pnt &B) { return {A.x-B.x,A.y-B.y}; }
friend ll operator* (const pnt &A, const pnt &B) { return (ll)A.x*B.y-(ll)A.y*B.x; }
} tb[Rl+5][N23];
int sz[Rl+5];
struct Misaka { int a,b,x,ans,id; } Q[N];
pnt w[N23];
int nw;
void psh(const pnt &p)
{
while(nw>1 and (w[nw]-w[nw-1])*(p-w[nw])<=0) nw--;
if(nw and w[nw].x==p.x) w[nw]=min(w[nw],p);
else if(!nw or w[nw].y>p.y) w[++nw]=p;
}
void update(int v, int u, int col)
{
nw=0;
int umod=u%Rl,vmod=v%Rl;
for(int cv=1,cu=1; cv<=sz[vmod] or cu<=sz[umod]; )
{
auto tu=tb[umod][cu],tv=tb[vmod][cv];
if(col) tu.y++; else tu.x++;
if(cv>sz[vmod]) psh(tu),cu++;
else if(cu>sz[umod]) psh(tv),cv++;
else
{
if(tu.x<tv.x) psh(tu),cu++;
else psh(tv),cv++;
}
}
sz[vmod]=nw;
for(int i=1; i<=sz[vmod]; i++) tb[vmod][i]=w[i];
}
int main()
{
scanf("%d%d",&n,&m); for(int i=1,u,v,c; i<=m; i++) scanf("%d%d%d",&u,&v,&c),g[u].push_back({v,c});
scanf("%d",&q); for(int i=1; i<=q; i++) scanf("%d%d%d",&Q[i].a,&Q[i].b,&Q[i].x), Q[i].ans=inf,Q[i].id=i;
sort(Q+1,Q+q+1, [&] (const Misaka &A, const Misaka &B) { return A.x<B.x or (A.x==B.x and A.a*B.b>B.a*A.b); });
int Qc=1; tb[1][++sz[1]]={0,0};
for(int i=1; i<=n; i++)
{
while(Q[Qc].x<i) Qc++;
for(auto e:g[i]) update(e.v,i,e.c);
int imod=i%Rl;
/*printf("i=%d: ",i);
for(int j=1; j<=sz[imod]; j++) printf("(%d %d) ",tb[imod][j].x,tb[imod][j].y);
puts("");*/
int tc=1;
while(Qc<=q and Q[Qc].x==i)
{
while(tc<sz[imod] and (tb[imod][tc+1]-tb[imod][tc])*(pnt){Q[Qc].b,-Q[Qc].a}>=0) tc++;
// printf("qa=%d qb=%d qx=%d\n",Q[Qc].a,Q[Qc].b,Q[Qc].x);
// printf("tc=%d tx=%d ty=%d\n",tc,tb[imod][tc].x,tb[imod][tc].y);
Q[Qc].ans=min(Q[Qc].ans,Q[Qc].a*tb[imod][tc].x+Q[Qc].b*tb[imod][tc].y); Qc++;
}
sz[imod]=0;
}
sort(Q+1,Q+q+1, [&] (const Misaka &A, const Misaka &B) { return A.id<B.id; });
for(int i=1; i<=q; i++) printf("%d\n",Q[i].ans);
return 0;
}