GX/GZOI2019 day2 解题报告
题目链接
t1 逼死强迫症
显然地，记 \(f(i)\) 为长度为 \(i\) 的木板的答案，可得： \(\\\)
\[f(i)=\begin{cases}
0 \quad ······························ \quad (i \in [0,2]) \\
f(i-1)+f(i-2)+2 \times pre(i-3) \quad ·· \quad ( i \in [3,+\infty]))
\end{cases}\]
0 \quad ······························ \quad (i \in [0,2]) \\
f(i-1)+f(i-2)+2 \times pre(i-3) \quad ·· \quad ( i \in [3,+\infty]))
\end{cases}\]
其中 \(pre(n)=\Sigma_{i=0}^n fib(i)\);
然后矩阵快速幂就行了，复杂度 \(O(T \times 5^3 \times log_2n)\)。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
int in() {
int x=0;char c=getchar();bool f=false;
while(c<'0'||c>'9') f|=c=='-', c=getchar();
while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48), c=getchar();
return f?-x:x;
}
const int mod = 1e9+7;
inline void add(int &x, int y) { x+=y; if(x>=mod) x-=mod; }
inline void sub(int &x, int y) { x-=y; if(x<0) x+=mod; }
struct matrix {
int a[5][5];
matrix(int x=0) {
memset(a, 0, sizeof(a));
if(x) for(int i=0;i<5;++i) a[i][i]=x;
}
inline int * operator [] (const int x) {
return a[x];
}
inline matrix operator * (matrix b) const {
matrix ret;
for(int i=0;i<5;++i)
for(int j=0;j<5;++j)
for(int k=0;k<5;++k)
add(ret[i][j], (ll)a[i][k]*b[k][j]%mod);
return ret;
}
};
matrix qpow(matrix base, int b) {
matrix ret(1);
for(;b;b>>=1, base=base*base)
if(b&1) ret=ret*base;
return ret;
}
int main() {
//freopen("obsession.in", "r", stdin);
//freopen("obsession.out", "w", stdout);
int T=in(), n;
while(T--) {
n=in();
if(n<=2) {
puts("0");
continue;
}
matrix a, b;
a[0][0]=2, a[0][1]=0, a[0][2]=2, a[0][3]=1, a[0][4]=1;
b[0][0]=1, b[0][1]=1;
b[1][0]=1;
b[2][0]=2, b[2][2]=1;
b[3][2]=1, b[3][3]=1, b[3][4]=1;
b[4][2]=1, b[4][3]=1;
a=a*qpow(b, n-3);
printf("%d\n", a[0][0]);
}
return 0;
}
t2 旅行者
可以正向/反向建边，跑两遍 \(dijkstra\)，染色（颜色为 \(k\) 个节点的编号），只有两边的颜色不同才造成贡献。这里没有写
有一种比较暴力的想法：
新建两个节点 \(S,T\)，将 \(k\) 个点分成两组，\(S\) 向一组连边，另一组向 \(T\) 连边，边权都为 \(0\)，跑最短路即可；
不难想到按二进制分组：枚举 \(k\) 的每一个二进制位，分成两组，做 \(log_2k\) 次。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
typedef long long ll;
typedef std::pair<ll, int> pli;
int in() {
int x=0;char c=getchar();bool f=false;
while(c<'0'||c>'9') f|=c=='-', c=getchar();
while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48), c=getchar();
return f?-x:x;
}
template<typename T>inline void chk_min(T &_, T __) { _=_<__?_:__; }
const int N = 1e5+5;
struct edge {
int next, to, w;
}e[N*6];
int cnt, head[N];
int a[N];
ll d[N];
bool vis[N];
inline void jb(const int u, const int v, const int w) {
e[++cnt]=(edge){head[u], v, w}, head[u]=cnt;
}
std::priority_queue <pli> q;
ll dijkstra(const int s, const int t) {
memset(d, 0x3f, sizeof(d));
memset(vis, 0, sizeof(vis));
q.push(pli(0, s));
d[s]=0;
while(!q.empty()) {
int u=q.top().second; q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=e[i].next) {
int v=e[i].to, w=e[i].w;
if(d[u]+w<d[v]) {
d[v]=d[u]+w;
q.push(pli(-d[v], v));
}
}
}
return d[t];
}
ll spfa_(const int s, const int t) {
memset(d, 0x3f, sizeof(d));
q.push(pli(0, s));
d[s]=0, vis[s]=1;
while(!q.empty()) {
int u=q.top().second; q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].next) {
int v=e[i].to, w=e[i].w;
if(d[u]+w<d[v]) {
d[v]=d[u]+w;
if(!vis[v])
q.push(pli(-d[v], v)), vis[v]=true;
}
}
}
return d[t];
}
std::deque <int> Q;
ll spfa(const int s, const int t) {
memset(d, 0x3f, sizeof(d));
Q.push_back(s);
d[s]=0, vis[s]=1;
while(!Q.empty()) {
int u=Q.front(); Q.pop_front();
vis[u]=0;
for(int i=head[u];i;i=e[i].next) {
int v=e[i].to, w=e[i].w;
if(d[u]+w<d[v]) {
d[v]=d[u]+w;
if(!vis[v]) {
if(Q.empty()) Q.push_back(v);
else if(d[Q.front()]<d[v]) Q.push_back(v);
else Q.push_front(v);
vis[v]=true;
}
}
}
}
return d[t];
}
inline void init() {
cnt=1;
memset(head, 0, sizeof(head));
}
int main() {
//freopen("tourist.in", "r", stdin);
//freopen("tourist.out", "w", stdout);
int T=in();
while(T--) {
int n=in(), m=in(), k=in();
init();
for(int i=1, x, y, z;i<=m;++i) {
x=in(), y=in(), z=in();
jb(x, y, z);
}
for(int i=1;i<=k;++i) a[i]=in();
int s=0, t=n+1;
ll res=1ll<<60ll;
for(int l=1;l<=k;l<<=1) {
for(int i=1;i<=k;++i)
if(i&l) jb(s, a[i], 0);
else jb(a[i], t, 0);
chk_min(res, spfa(s, t));
for(int i=1;i<=k;++i)
if(i&l) head[s]=e[head[s]].next, --cnt;
else head[a[i]]=e[head[a[i]]].next, --cnt;
for(int i=1;i<=k;++i)
if(!(i&l)) jb(s, a[i], 0);
else jb(a[i], t, 0);
chk_min(res, spfa(s, t));
for(int i=1;i<=k;++i)
if(!(i&l)) head[s]=e[head[s]].next, --cnt;
else head[a[i]]=e[head[a[i]]].next, --cnt;
}
printf("%lld\n", res);
}
return 0;
}
t3 旧词
先考虑 \(k=1\) 的做法；
显然地，要离线处理，按 \(x\) 排好序，每一次把 \(1\)~\(x\) 的贡献维护好；
主要思想：对于深度为 \(d\) 的节点 \(u\)，把 \(d\) 均摊到 \(1\)~\(u\) 这条链上，查询 \(y\) 时计算 \(1\)~\(y\) 的和即可。
如果 \(k=1\)，则每次修改只需把 \(1\)~\(x\) 的权值每次加 \(1\)。
同样地，当 \(k \ne 1\) 时，不难发现，给每个节点一个权值(设点为 \(u\)) \((dep_u)^k-(dep_u-1)^k\)，每次修改只需要加一次这个权值就行了。
树剖维护即可。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
int in() {
int x=0;char c=getchar();bool f=false;
while(c<'0'||c>'9') f|=c=='-', c=getchar();
while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48), c=getchar();
return f?-x:x;
}
const int N = 5e4+5, mod = 998244353;
struct edge {
int next, to;
}e[N];
int cnt=1, head[N], dep[N], fro[N], siz[N], hson[N], dfn[N], pos[N], fa[N];
int n, m, k;
//heavy-light decomposition begin
void dfs_h(const int u) {
siz[u]=1;
for(int i=head[u];i;i=e[i].next) {
int v=e[i].to;
dep[v]=dep[u]+1;
fa[v]=u;
dfs_h(v);
siz[u]+=siz[v];
if(siz[v]>siz[hson[u]]) hson[u]=v;
}
}
void dfs_f(const int u, const int tp) {
fro[u]=tp, dfn[u]=++dfn[0], pos[dfn[u]]=u;
if(hson[u]) dfs_f(hson[u], tp);
for(int i=head[u];i;i=e[i].next)
if(e[i].to!=hson[u])
dfs_f(e[i].to, e[i].to);
}
inline void prep() {
dep[1]=1;
dfs_h(1);
dfs_f(1, 1);
}
//heavy-light decomposition end
//segment_tree begin
inline void add(int &_, int __) { _+=__; if(_>=mod) _-=mod; }
int qpow(int base, int b) {
int ret=1;
for(;b;b>>=1, base=(ll)base*base%mod)
if(b&1) ret=(ll)ret*base%mod;
return ret;
}
struct segment_tree {
#define lson tl, mid, p<<1
#define rson mid+1, tr, p<<1|1
int t[N<<2], base[N<<2], lazy[N<<2];
inline void push_up(const int p) {
t[p]=t[p<<1]+t[p<<1|1];
if(t[p]>=mod) t[p]-=mod;
}
inline void spread(const int p) {
add(t[p<<1], (ll)base[p<<1]*lazy[p]%mod);
add(t[p<<1|1], (ll)base[p<<1|1]*lazy[p]%mod);
add(lazy[p<<1], lazy[p]), add(lazy[p<<1|1], lazy[p]);
lazy[p]=0;
}
void build(const int tl, const int tr, const int p) {
if(tl==tr) {
base[p]=qpow(dep[pos[tl]], k)-qpow(dep[pos[tl]]-1, k);
if(base[p]<0) base[p]+=mod;
return ;
}
int mid=(tl+tr)>>1;
build(lson), build(rson);
base[p]=base[p<<1]+base[p<<1|1];
if(base[p]>=mod) base[p]-=mod;
}
void update(const int l, const int r, const int tl, const int tr, const int p) {
if(l<=tl&&tr<=r)
return (void)(add(t[p], base[p]), add(lazy[p], 1));
int mid=(tl+tr)>>1;
if(lazy[p]) spread(p);
if(mid>=l) update(l, r, lson);
if(mid<r) update(l, r, rson);
push_up(p);
}
int query(const int l, const int r, const int tl, const int tr, const int p) {
if(l<=tl&&tr<=r) return t[p];
int mid=(tl+tr)>>1, ret=0;
if(lazy[p]) spread(p);
if(mid>=l) ret=query(l, r, lson);
if(mid<r) add(ret, query(l, r, rson));
return ret;
}
#undef lson
#undef rson
}T;
//segment_tree end
struct ask {
int x, y, id;
}q[N];
int res[N];
inline bool cmpx(const ask &a, const ask &b) {
return a.x < b.x;
}
void update(int u, int v) {
while(fro[u]!=fro[v]) {
if(dep[fro[u]]>dep[fro[v]]) std::swap(u, v);
T.update(dfn[fro[v]], dfn[v], 1, n, 1);
v=fa[fro[v]];
}
if(dep[u]>dep[v]) std::swap(u, v);
T.update(dfn[u], dfn[v], 1, n, 1);
}
int query(int u, int v) {
int ret=0;
while(fro[u]!=fro[v]) {
if(dep[fro[u]]>dep[fro[v]]) std::swap(u, v);
add(ret, T.query(dfn[fro[v]], dfn[v], 1, n, 1));
v=fa[fro[v]];
}
if(dep[u]>dep[v]) std::swap(u, v);
add(ret, T.query(dfn[u], dfn[v], 1, n, 1));
return ret;
}
int main() {
//freopen("poetry.in", "r", stdin);
//freopen("poetry.out", "w", stdout);
n=in(), m=in(), k=in();
for(int i=2;i<=n;++i) {
int f=in();
e[++cnt]=(edge){head[f], i};
head[f]=cnt;
}
prep();
T.build(1, n, 1);
for(int i=1;i<=m;++i) q[i]=(ask){in(), in(), i};
std::sort(q+1, q+1+m, cmpx);
for(int i=1, now=0;i<=m;++i) {
while(now<q[i].x) {
++now;
update(1, now);
}
res[q[i].id]=query(1, q[i].y);
}
for(int i=1;i<=m;++i) printf("%d\n", res[i]);
return 0;
}