2018 Multi-University Training Contest 7 Solution

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

A - Age of Moyu

题意：给出一张图，从1走到n，如果相邻两次走的边的权值不同，花费+1，否则花费相同，求最小花费

思路：用set记录有当前点的最小花费有多少种方案到达，然后最短路

#include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + ; struct Edge{
int to, nxt, val;
Edge(){}
Edge(int to, int nxt, int val):to(to), nxt(nxt), val(val){};
}edge[maxn << ]; set<int>s[maxn];
int head[maxn], tot; void Init(int n)
{
for(int i = ; i <= n; ++i) head[i] = -, s[i].clear();
tot = ;
} void addedge(int u, int v,int val)
{
edge[tot] = Edge(v, head[u], val);head[u] = tot++;
} struct qnode{
int v, c;
int pre;
int fa;
qnode(){}
qnode(int v, int c, int pre, int fa) :v(v), c(c), pre(pre), fa(fa){}
bool operator < (const qnode &r) const
{
return c > r.c;
}
}; int n, m;
int dist[maxn]; void BFS(int st)
{
for(int i = ; i <= n; ++i) dist[i] = INF;
priority_queue<qnode>q;
dist[st] = ;
q.push(qnode(st, , , ));
while(!q.empty())
{
qnode tmp = q.top();
q.pop();
int u = tmp.v;
if(tmp.c > dist[u]) continue;
else if(tmp.c == dist[u])
{
if(s[u].find(tmp.pre) != s[u].end()) continue;
s[u].insert(tmp.pre);
}
else
{
dist[u] = tmp.c;
s[u].clear();
s[u].insert(tmp.pre);
}
for(int i = head[u]; ~i; i = edge[i].nxt)
{
int v = edge[i].to;
int cost = edge[i].val;
if(v == tmp.fa) continue;
if(dist[u] + (cost != tmp.pre) <= dist[v])
{
dist[v] = dist[u] + (cost != tmp.pre);
if(v != n)
{
q.push(qnode(v, dist[v], cost, u));
}
}
}
}
} int main()
{
int t;
while(scanf("%d %d", &n, &m) != EOF)
{
Init(n);
for(int i = ; i <= m; ++i)
{
int u, v, w;
scanf("%d %d %d", &u, &v ,&w);
addedge(u, v, w);
addedge(v, u, w);
}
BFS();
if(dist[n] == INF) dist[n] = -;
printf("%d\n", dist[n]);
}
return ;
}

B - AraBellaC

留坑。

C - YJJ’s Stack

留坑。

D - Go to school

留坑。

E - GuGuFishtion

留坑。

F - Lord Li's problem

留坑。

G - Reverse Game

留坑。

H - Traffic Network in Numazu

题意：两种操作，第一种是更改一条边权的值，第二种是查询x-y的最短路径，给出的是一颗树加一条边

思路：将形成环的边单独拿出来考虑，那么考虑是否经过这条边使得答案更优，修改操作用线段树或者树状数组维护

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + ;
const int DEG = ; struct EDGE{
int u, v, w;
}EDGE[maxn], TEMP; struct Edge{
int to, nxt, val;
Edge(){}
Edge(int to, int nxt, int val) :to(to), nxt(nxt), val(val){}
}edge[maxn << ]; int head[maxn], tot, cnt;
int father[maxn]; void Init(int n)
{
for(int i = ; i <= n; ++i) head[i] = -, father[i] = i;
tot = cnt = ;
} int find(int x)
{
return x == father[x] ? father[x] : father[x] = find(father[x]);
} void mix(int x,int y)
{
x = find(x), y = find(y);
if(x != y) father[x] = y;
} bool same(int x,int y)
{
return find(x) == find(y);
} void addedge(int u, int v, int val)
{
edge[tot] = Edge(v, head[u], val); head[u] = tot++;
} int dro[maxn];
int ord[maxn], son[maxn];
int fa[maxn][DEG];
int deg[maxn]; void DFS(int u, int pre)
{
ord[u] = ++cnt;
dro[cnt] = u;
for(int i = ; i < DEG; ++i) fa[u][i] = fa[fa[u][i - ]][i - ];
for(int i = head[u]; ~i; i = edge[i].nxt)
{
int v = edge[i].to;
if(v == pre) continue;
fa[v][] = u;
deg[v] = deg[u] + ;
DFS(v, u);
}
son[u] = cnt;
} int LCA(int u, int v)
{
if(deg[u] > deg[v]) swap(u, v);
int hu = deg[u], hv = deg[v];
int tu = u, tv = v;
for(int det = hv - hu, i = ; det; det >>= , ++i)
{
if(det & )
{
tv = fa[tv][i];
}
}
if(tu == tv) return tu;
for(int i = DEG - ; i >= ; --i)
{
if(fa[tu][i] == fa[tv][i]) continue;
tu = fa[tu][i];
tv = fa[tv][i];
}
return fa[tu][];
} struct node{
int l, r;
ll val, lazy;
node(){}
node(int l,int r, ll val, ll lazy) :l(l), r(r), val(val), lazy(lazy){}
}tree[maxn << ]; void pushup(int id)
{
tree[id].val = tree[id << ].val + tree[id << | ].val;
} void pushdown(int id)
{
if(tree[id].lazy)
{
ll lazy = tree[id].lazy;
tree[id << ].val += lazy;
tree[id << | ].val += lazy;
tree[id << ].lazy += lazy;
tree[id << | ].lazy += lazy;
tree[id].lazy = ;
}
} void build(int id, int l, int r)
{
tree[id] = node(l, r, , );
if(l == r) return ;
int mid = (l + r) >> ;
build(id << , l, mid);
build(id << | , mid + , r);
} void update(int id, int l, int r, ll val)
{
if(l <= tree[id].l && r >= tree[id].r)
{
tree[id].val += val;
tree[id].lazy += val;
return ;
}
pushdown(id);
int mid = (tree[id].l + tree[id].r) >> ;
if(mid >= l) update(id << , l, r, val);
if(r > mid) update(id << | , l, r, val);
pushup(id);
} ll query(int id, int pos)
{
if(tree[id].l == pos && tree[id].r == pos)
{
return tree[id].val;
}
pushdown(id);
int mid = (tree[id].l + tree[id].r) >> ;
if(pos <= mid) return query(id << , pos);
if(pos > mid) return query(id << | , pos);
pushup(id);
} ll getdis(int u,int v)
{
int root = LCA(u, v);
return query(, ord[u]) + query(, ord[v]) - * query(, ord[root]);
} int n, q; int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &n, &q);
Init(n);
for(int i = ; i <= n; ++i)
{
scanf("%d %d %d", &EDGE[i].u, &EDGE[i].v, &EDGE[i].w);
int u = EDGE[i].u, v = EDGE[i].v, w = EDGE[i].w;
if(same(u, v))
{
TEMP = EDGE[i];
continue;
}
mix(u, v);
addedge(u, v, w);
addedge(v, u, w);
}
fa[][] = ;
deg[] = ;
DFS(, -);
build(, , n);
for(int i = ; i <= n; ++i)
{
int u = EDGE[i].u, v = EDGE[i].v, w = EDGE[i].w;
if(u == TEMP.u && v == TEMP.v) continue;
if(fa[u][] == v)
{
update(, ord[u], son[u], w);
}
else if(fa[v][] == u);
{
update(, ord[v], son[v], w);
}
}
// for(int i = 1; i <= n; ++i) cout << ord[i] << endl;
// for(int i = 1; i <= n; ++i) cout << i << " " << query(1, ord[i]) << endl;
while(q--)
{
int op, x, y;
scanf("%d %d %d", &op, &x ,&y);
if(op == )
{
int u = EDGE[x].u, v = EDGE[x].v, w = EDGE[x].w;
if(u == TEMP.u && v == TEMP.v)
{
EDGE[x].w = y;
TEMP.w = y;
}
if(fa[u][] == v)
{
update(, ord[u], son[u], y - w);
}
else if(fa[v][] == u)
{
update(, ord[v], son[v], y - w);
}
EDGE[x].w = y;
}
else if(op == )
{
ll ans = getdis(x, y);
ans = min(ans, getdis(x, TEMP.u) + TEMP.w + getdis(y, TEMP.v));
ans = min(ans, getdis(y, TEMP.u) + TEMP.w + getdis(x, TEMP.v)); printf("%lld\n", ans);
}
}
}
return ;
}

I - Tree

题意：一棵树种，每个点有一个权值，表示可以向上跳几步，两种操作，一种是修改某点权值，还有一种是询问某个点需要跳几次跳出

思路：DFS序分块，弹飞绵阳升级版，注意更新的时候，维护一个$In[u]$ 表示最远跳到块内是第几块，这样就不用多一个log

#include <bits/stdc++.h>
using namespace std; namespace FastIO
{
#define BUF_SIZE 10000005
bool IOerror = false;
inline char NC()
{
static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
if (p1 == pend)
{
p1 = buf;
pend = buf + fread(buf, , BUF_SIZE, stdin);
if (pend == p1)
{
IOerror = true;
return -;
}
}
return *p1++;
} inline bool blank(char ch)
{
return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
} template <typename T>
inline void read(T &x)
{
char ch;
while (blank(ch = NC()));
if (IOerror)
{
x = -;
return;
}
bool flag = false;
if (ch == '-')
{
flag = true;
ch = NC();
}
if (!isdigit(ch)) while (!isdigit(ch = NC()));
for (x = ch - ''; isdigit(ch = NC()); x = x * + ch - '');
if (flag) x *= -;
} void out(int x)
{
if (x / ) out(x / );
putchar(x % + '');
} inline void print(int x)
{
out(x);
puts("");
}
#undef BUF_SIZE
}using namespace FastIO; #define N 100010
#define DEG 20
#define block 400 int t, n, q;
int a[N], b[N], In[N], Out[N], fa[N][], deep[N], p[N], fp[N], cnt;
vector <int> G[N]; void Init()
{
for (int i = ; i <= n; ++i) G[i].clear();
cnt = ; fa[][] = ; deep[] = ;
} void DFS(int u)
{
p[u] = ++cnt;
fp[cnt] = u;
for (int i = ; i < DEG; ++i)
fa[u][i] = fa[fa[u][i - ]][i - ];
for (auto v : G[u]) if (v != fa[u][])
{
deep[v] = deep[u] + ;
DFS(v);
}
} int GetK(int x, int k)
{
bitset <> b; b = k;
for (int i = ; i >= ; --i) if (b[i])
x = fa[x][i];
return x;
} int query(int x)
{
int res = ;
x = p[x];
while (x)
{
res += b[x];
x = Out[x];
}
return res;
} void update(int x)
{
if (a[x] > deep[x])
{
b[p[x]] = ;
Out[p[x]] = ;
In[p[x]] = p[x];
}
else
{
int root = GetK(x, a[x]);
if ((p[root] - ) / block != (p[x] - ) / block)
{
b[p[x]] = ;
Out[p[x]] = p[root];
In[p[x]] = p[x];
}
else
{
b[p[x]] = b[p[root]] + ;
Out[p[x]] = Out[p[root]];
In[p[x]] = p[root];
}
}
x = p[x];
for (int i = x + ; i <= n && (i - ) / block == (x - ) / block; ++i)
{
if (In[i] != i)
{
b[i] = b[In[i]] + ;
Out[i] = Out[In[i]];
}
}
} void Run()
{
read(t);
while (t--)
{
read(n); Init();
for (int i = ; i <= n; ++i)
{
read(fa[i][]);
G[fa[i][]].push_back(i);
} DFS();
for (int i = ; i <= n; ++i) read(a[i]);
for (int i = ; i <= n; ++i)
{
int x = fp[i];
if (a[x] > deep[x])
{
b[i] = ;
Out[i] = ;
In[i] = i;
continue;
}
int root = GetK(x, a[x]);
if ((p[root] - ) / block != (i - ) / block)
{
b[i] = ;
Out[i] = p[root];
In[i] = i;
}
else
{
b[i] = b[p[root]] + ;
Out[i] = Out[p[root]];
In[i] = p[root];
}
}
read(q);
for (int i = , op, x, v; i <= q; ++i)
{
read(op); read(x);
if (op == ) print(query(x));
else
{
read(v);
a[x] = v;
update(x);
}
}
}
} int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run();
return ;
}

J - Sequence

题意：求$F_n = C * F_{n - 2} + D * F_{n - 1} + \lfloor{\frac {p}{n}}\rfloor$

思路：考虑最后一项最多有$\sqrt n 项按这个值分块矩阵快速幂即可$

#include <bits/stdc++.h>
using namespace std; #define ll long long const ll MOD = (ll)1e9 + ; int t, n;
ll A, B, C, D, P; ll Biner(ll x)
{
ll l = x, r = n, res = l;
x = P / x;
while (r - l >= )
{
ll mid = (l + r) >> ;
ll tmp = P / mid;
if (tmp >= x)
{
l = mid + ;
res = mid;
}
else
r = mid - ;
}
return res;
} struct node
{
ll a[][];
node ()
{
memset(a, , sizeof a);
}
node operator * (const node &r) const
{
node ans = node();
for (int i = ; i < ; ++i) for (int j = ; j < ; ++j) for (int k = ; k < ; ++k)
ans.a[i][j] = (ans.a[i][j] + a[i][k] * r.a[k][j] % MOD) % MOD;
return ans;
}
}base; node qmod(node base, int n)
{
node res = node();
res.a[][] = B, res.a[][] = A; res.a[][] = ;
while (n)
{
if (n & ) res = res * base;
base = base * base;
n >>= ;
}
return res;
} ll work()
{
if (n == ) return A;
if (n == ) return B;
int l = , r;
while (l <= n)
{
r = Biner(l);
base.a[][] = P / l;
node res = qmod(base, r - l + );
B = res.a[][], A = res.a[][];
l = r + ;
}
return B;
} int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%lld%lld%lld%lld%lld%d", &A, &B, &C, &D, &P, &n);
memset(base.a, , sizeof base.a);
base.a[][] = D, base.a[][] = C, base.a[][] = ; base.a[][] = ;
printf("%lld\n", work());
}
return ;
}