# DDJ Regular Contest Round#2 Toturial
---
## A. 果然我的高一平凡生活搞錯了。
`tag`：`Math, DP`
本題兩種想法：
- $DP$
那麼這邊就是實作巴斯卡三角形的 DP 法：
$Base$ $Case$：`c[n][0] = c[n][n] = 1`
`c[n][i] = c[n - 1][i] + c[n - 1][i - 1]`，$0 < i < n$。
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
int main() {
cin.tie(nullptr); ios_base::sync_with_stdio(false);
int T, n;
unsigned LL ans[63][63];
memset(ans, 0, sizeof(ans));
for (int x = 1; x <= 62; x++) ans[x][0] = 1;
ans[1][1] = 1;
for (int x = 2; x <= 62; x++) {
for (int y = 1; y <= x; y++) {
ans[x][y] = ans[x - 1][y - 1] + ans[x - 1][y];
}
}
cin >> T;
while (T--) {
cin >> n;
for (int x = 0; x <= n; x++) cout << ans[n][x] << ' ';
cout << '\n';
}
return 0;
}
```
:::
- 題目其實寫得很清楚：對於每個 $n$，依序輸出 $C^n_i$
且 $C^n_i$ = $C^n_{i - 1}\times \frac{n - i + 1}{i}$
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
int main() {
cin.tie(nullptr); ios_base::sync_with_stdio(false);
int T, n;
unsigned LL ans[63][63];
for (int x = 1; x < 63; x++)
for (int y = 0; y < 63; y++) ans[x][y] = 1;
for (int x = 1; x <= 62; x++) {
for (int y = 1; y <= x; y++) {
ans[x][y] = ans[x][y - 1] * (x - y + 1) / y;
}
}
cin >> T;
while (T--) {
cin >> n;
for (int x = 0; x <= n; x++) cout << ans[n][x] << ' ';
cout << '\n';
}
return 0;
}
```
:::
## B. 果然我的高一平凡生活搞錯了。續
`tag`：`Math, Modulo inverse`
本題因為與 $A.$ 相比，
$n$ 明顯大得多，可以看出剛剛 $DP$ 空間複雜度是是 $O(\frac{{n_{max}} ^2}{2})$，
這題顯然不能這樣做，因為 $n_{max} = 2\times 10^4$。
當然這複雜度可以壓成 $O(2n_{max})$，不過如此時間複雜度將變為 $O(TN^2)$，這樣太慢。
因此這裡只剩下剛剛 $A.$ 的 $C^n_i$，因為還要 $mod$ $10^9 + 7$，所以需要用到模逆元。
又 $10^9 + 7$ 為質數，所以模逆元求法適用費馬小定理證明：
對於任一小於質數 $p$ 的數 $n$，$n$ 對 $p$ 的模逆元為：$n^{p - 2}$ $mod$ $p$，
那次方的部分可以用快速冪優化。
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
constexpr int m = 1e9 + 7;
LL power(int n) {
LL ret = 1, tmp = n;
for (int k = m - 2; k; tmp = tmp * tmp % m, k >>= 1)
if (k & 1) ret = ret * tmp % m;
return ret;
}
int main() {
cin.tie(nullptr); ios_base::sync_with_stdio(false);
int n, T;
cin >> T;
LL pow[20000];
for (int x = 0; x < 20000; x++) pow[x] = power(x + 1);
while (T--) {
LL ans = 1;
cin >> n;
cout << ans << ' ';
for (int x = n; x; x--) {
ans = ans * x % m, ans = ans * pow[n - x] % m;
cout << ans << ' ';
}
cout << '\n';
}
return 0;
}
```
:::
## C. The Greedy Mouse
`tag`: `DP`、`Knapsack`
可以想到是 $DP[N][C]$，
而且是對 $prefix$ 做 $DP$。
只要想到這個，
轉移式就很直觀了。
$$DP[i][j]=max(DP[i-1][k-c[i-1][j]]+prefix[i-1][j], DP[i][k], DP[i-1][k])$$
$i$ 代表 $N$ 的變量，由 $1$ 到 $N$
$j$ 代表 $M$ 的變量，由 $1$ 到 $M$
$k$ 代表 $C$ 的變量，由 $C$ 到 $0$
:::spoiler `Solution`
```cpp=
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
const int mxC = 2500, mxN = 50;
int dp[mxN+1][mxC+1];
void solve() {
int N, M, C;
cin >> N >> M >> C;
vector<vector<int>> v, c;
for(int i = 0; i < N; ++i) {
int sum = 0;
v.push_back(vector<int>(0)), c.push_back(vector<int>(0));
for(int j = 0; j < M; ++j) {
int t;
cin >> t;
sum += t;
v[i].push_back(sum), c[i].push_back(j+1);
}
}
memset(dp, 0, sizeof(dp));
for(int i = 0; i < N; ++i) {
for(int j = 0; j < M; ++j) {
for(int k = C; k-c[i][j] >= 0; --k)
dp[i+1][k] = max({dp[i][k-c[i][j]]+v[i][j], dp[i+1][k], dp[i][k]});
}
}
cout << dp[N][C] << '\n';
}
int main() {
cin.tie(0), ios_base::sync_with_stdio(0);
int t;
cin >> t;
while(t--)
solve();
}
```
:::
## D. "Country" Road (Easy Version)
`tag`: `MST`
本題不是 `Shortest Path`，
仔細想想，
這題可以被轉為找到直徑最小的樹，
`Shortest Path` 出來的樹不會符合。
`MST` 會符合的原因可以這樣想，
任取兩點相鄰的距離皆為最小，
那即可推到所有點的最大距離為最小。
:::spoiler `Solution`
```cpp=
#include <bits/stdc++.h>
using namespace std;
template<class T, unsigned int N>
using ar = array<T, N>;
using ll = long long;
#define F first
#define S second
using node = pair<ll, int>;
const int mxN = 1e5;
int n, m;
vector<node> adj[mxN];
vector<int> graph[mxN];
void make_graph() {
priority_queue<ar<ll,3>, vector<ar<ll,3>>, greater<ar<ll,3>>> pq; //[w, u, v]
vector<bool> htop(n, 0);
pq.push({0, 0, 0});
while(!pq.empty()) {
auto t = pq.top(); pq.pop();
if(htop[t[2]]) continue;
htop[t[2]] = 1;
graph[t[1]].push_back(t[2]);
for(auto& nd : adj[t[2]]) {
if(!htop[nd.S])
pq.push({nd.F, t[2], nd.S});
}
}
for(int i = 0; i < n; ++i) {
cout << i+1 << ' ';
for(auto& nd : graph[i]) {
if(nd != i)
cout << nd+1 << ' ';
}
cout << '\n';
}
}
int main() {
cin.tie(0), ios_base::sync_with_stdio(0);
cin >> n >> m;
ll u, v, w;
for(int i = 0; i < m; ++i) {
cin >> u >> v >> w, --u, --v;
adj[u].push_back({w, v});
adj[v].push_back({w, u});
}
make_graph();
}
```
:::
## E. "Country" Road (Hard Version)
`tag`: `LCA Euler Tour Technique`
本題是用 `pD` 畫出來的圖做詢問，
仔細的想一下是對子樹做詢問，
那就是`樹壓平 LCA Euler Tour Technique` 啦!
樹壓平的資料結構維護的是一個區間除法修改、區間加法查詢的資料，
但因為有小數點，
所以不用擔心不精準所產生的誤差。
至於要判是不是上級機關，就用 `LCA` 的 `isanc(u, v)`，
因為下級必是上級的子樹節點之一。
```cpp=
bool isanc(int u, int v) {
return dfi[u] <= dfi[v] && dfo[v] <= dfo[u];
}
```
至於實作的方法有很多種，
這裡提供兩個。
:::spoiler `Solution revcoding`
```cpp=
#include <bits/stdc++.h>
using namespace std;
template<class T, unsigned int N>
using ar = array<T, N>;
using ll = long long;
using ld = long double;
#define F first
#define S second
using node = pair<ll, int>;
#define mid ((l+r)/2)
#define lc (id<<1)
#define rc (id<<1|1)
const int mxN = 1e5;
int n, m, h[mxN], dfi[mxN<<1], dfo[mxN<<1], tag[mxN<<3], cnt = 1;
vector<node> adj[mxN];
vector<int> graph[mxN];
unordered_map<int, int> pos;
ld seg[mxN<<3];
void make_graph() {
priority_queue<ar<ll,3>, vector<ar<ll,3>>, greater<ar<ll,3>>> pq; //[w, u, v]
vector<bool> htop(n, 0);
pq.push({0, 0, 0});
while(!pq.empty()) {
auto t = pq.top(); pq.pop();
if(htop[t[2]]) continue;
htop[t[2]] = 1;
graph[t[1]].push_back(t[2]);
for(auto& nd : adj[t[2]]) {
if(!htop[nd.S])
pq.push({nd.F, t[2], nd.S});
}
}
}
void dfs(int node) {
int real = node-n;
dfi[node] = cnt;
dfi[real] = cnt, dfo[real] = cnt++;
for(auto& nd : graph[real]) {
if(nd != real) {
dfs(n+nd);
}
}
dfo[node] = cnt++;
}
void pull(int id, int l, int r) {
if(l != r)
seg[id] = seg[lc] + seg[rc];
}
void push(int id, int l, int r) {
if(tag[id]) {
if(l != r) {
tag[lc] += tag[id];
tag[rc] += tag[id];
seg[lc] /= (1ll<<min(60, tag[id]));
seg[rc] /= (1ll<<min(60, tag[id]));
tag[id] = 0;
}
}
}
void build(int id, int l, int r) {
if(l == r) {
if(pos.find(l) != pos.end())
seg[id] = h[pos[l]];
return;
}
build(lc, l, mid), build(rc, mid+1, r);
pull(id, l, r);
}
void upd(int id, int l, int r, int ql, int qr, bool v) {
push(id, l, r);
if(ql <= l && r <= qr) {
if(v) {
seg[id] /= 2;
++tag[id];
}
return;
}
if(l > qr || ql > r)
return;
upd(lc, l, mid, ql, qr, v), upd(rc, mid+1, r, ql, qr, v);
pull(id, l, r);
}
ld qry(int id, int l, int r, int ql, int qr) {
push(id, l, r);
if(ql <= l && r <= qr)
return seg[id];
if(l > qr || ql > r)
return 0;
return qry(lc, l, mid, ql, qr) + qry(rc, mid+1, r, ql, qr);
}
bool isanc(int u, int v) {
return dfi[u] <= dfi[v] && dfo[v] <= dfo[u];
}
void statics() {
for(int i = 0; i < n; ++i)
cin >> h[i];
dfs(n);
--cnt;
for(int i = 0; i < n; ++i)
pos[dfo[i]] = i;
build(1, 1, cnt);
int q;
cin >> q;
while(q--) {
int u, v;
cin >> u >> v, --u, --v;
u += n, v += n;
if(isanc(u, v)) {
upd(1, 1, cnt, dfi[v], dfo[v], 1);
}
else if(isanc(v, u)) {
upd(1, 1, cnt, dfi[u], dfo[u], 1);
} else {
upd(1, 1, cnt, dfi[v], dfo[v], 1);
upd(1, 1, cnt, dfi[u], dfo[u], 1);
}
cout << qry(1, 1, cnt, dfi[u], dfo[u]) << ' ';
cout << qry(1, 1, cnt, dfi[v], dfo[v]) << '\n';
}
}
int main() {
cin.tie(0), ios_base::sync_with_stdio(0);
cin >> n >> m;
ll u, v, w;
for(int i = 0; i < m; ++i) {
cin >> u >> v >> w, --u, --v;
adj[u].push_back({w, v});
adj[v].push_back({w, u});
}
cout << fixed << setprecision(9);
make_graph();
statics();
}
```
:::
:::spoiler `Solution jakao`
```cpp=
#include<bits/stdc++.h>
#define MXN 100005
#define ll long long
#define endl '\n'
#define EPS
#define cl(x) (x<<1)
#define cr(x) (x<<1|1)
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
using ld = long double;
int n,m,ti;
int num[MXN],tin[MXN],tout[MXN];
ll pow2[62];
pair<int,int> rng[MXN];
vector<int> edge[MXN];
vector<pair<int,ll>> ori[MXN];
bool v[MXN];
priority_queue<pair<ll,pair<int,int>>,vector<pair<ll,pair<int,int>>>,greater<pair<ll,pair<int,int>>>> pq;
struct seg_tree{
ld a[MXN<<1],val[MXN<<3];
int tag[MXN<<3],NO_TAG=0;
void push(int i,int l,int r){
if(tag[i] != NO_TAG){
val[i]/=pow2[min(tag[i],60)];
if(l!=r){
tag[cl(i)]+=tag[i];
tag[cr(i)]+=tag[i];
}
tag[i]=NO_TAG;
} }
void pull(int i,int l,int r){
int mid=(l+r)>>1;
push(cl(i),l,mid);push(cr(i),mid+1,r);
val[i]=val[cl(i)]+val[cr(i)];
}
void build(int i,int l,int r){
if(l==r){
val[i]=a[l];
return;
}
int mid=(l+r)>>1;
build(cl(i),l,mid);build(cr(i),mid+1,r);
pull(i,l,r);
}
void update(int i,int l,int r,int ql,int qr){
push(i,l,r);
if(ql<=l&&r<=qr){
tag[i]++;
return;
}
int mid=(l+r)>>1;
if(ql<=mid) update(cl(i),l,mid,ql,qr);
if(qr>mid) update(cr(i),mid+1,r,ql,qr);
pull(i,l,r);
}
ld query(int i,int l,int r,int ql,int qr){
push(i,l,r);
if(ql<=l&&r<=qr)
return val[i];
int mid=(l+r)>>1;
double ret=0;
if(ql<=mid) ret+=query(cl(i),l,mid,ql,qr);
if(qr>mid) ret+=query(cr(i),mid+1,r,ql,qr);
return ret;
}
}tree;
void prim(){
pq.push(make_pair(0,make_pair(0,0)));
while(!pq.empty()){
auto u=pq.top();pq.pop();
if(v[u.second.second]) continue;
v[u.second.second]=1;
if(u.second.first != u.second.second){
edge[u.second.first].push_back(u.second.second);
}
for(auto i:ori[u.second.second]){
if(!v[i.first]){
pq.push(make_pair(i.second,make_pair(u.second.second,i.first)));
}
}
}
}
int dfs(int x){
tree.a[ti] = num[x];
tin[x] = rng[x].first = rng[x].second = ti++;
for(auto i:edge[x]){
rng[x].second = dfs(i);
}
tout[x] = ti++;
return rng[x].second;
}
bool isanc(int x,int y){
return tin[x]<=tin[y] && tout[x]>=tout[y];
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cout<<fixed<<setprecision(9);
pow2[0]=1;
for(int i=1;i<=60;i++){
pow2[i]=pow2[i-1]*2LL;
}
cin>>n>>m;
for(int i=0;i<m;i++){
ll u,v,w;
cin>>u>>v>>w;
--u,--v;
ori[u].push_back(make_pair(v,w));
ori[v].push_back(make_pair(u,w));
}
prim();
for(int i=0;i<n;i++) cin>>num[i];
dfs(0);
tree.build(1,0,ti-1);
int q;cin>>q;
for(int a,b;q--;){
cin>>a>>b;
--a,--b;
if(isanc(a,b)){
tree.update(1,0,ti-1,rng[b].first,rng[b].second);
cout<<tree.query(1,0,ti-1,rng[a].first,rng[a].second)<<" "<<tree.query(1,0,ti-1,rng[b].first,rng[b].second)<<endl;
}
else if(isanc(b,a)){
tree.update(1,0,ti-1,rng[a].first,rng[a].second);
cout<<tree.query(1,0,ti-1,rng[a].first,rng[a].second)<<" "<<tree.query(1,0,ti-1,rng[b].first,rng[b].second)<<endl;
}
else{
tree.update(1,0,ti-1,rng[a].first,rng[a].second);
tree.update(1,0,ti-1,rng[b].first,rng[b].second);
cout<<tree.query(1,0,ti-1,rng[a].first,rng[a].second)<<" "<<tree.query(1,0,ti-1,rng[b].first,rng[b].second)<<endl;
}
}
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet