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$。
  code

  ​​​​#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_i^n$
  且
  $C_i^n$ =
  $C_{i-1}^n\times \frac{n-i+1}{i}$
  code

  ​​​​#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(T{N}^2)$，這樣太慢。

因此這裡只剩下剛剛

$A.$ 的

$C_i^n$，因為還要

$mod$

${10}^9+7$，所以需要用到模逆元。
又

${10}^9+7$ 為質數，所以模逆元求法適用費馬小定理證明：
對於任一小於質數

$p$ 的數

$n$，

$n$ 對

$p$ 的模逆元為：

$n^{p-2}$

$mod$

$p$，
那次方的部分可以用快速冪優化。

code

#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$

Solution

#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 會符合的原因可以這樣想，
任取兩點相鄰的距離皆為最小，
那即可推到所有點的最大距離為最小。

Solution

#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)，
因為下級必是上級的子樹節點之一。

bool isanc(int u, int v) {
	return dfi[u] <= dfi[v] && dfo[v] <= dfo[u];
}

至於實作的方法有很多種，
這裡提供兩個。

Solution revcoding

#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();
}

Solution jakao

#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;
}