2020 高階競程 Contest #5 - 題解

小明的數學題

• Task Provider: CF 1038 B
• Task Setter: raiso

首殺 team20_23 (00:09)

解法說明

分成兩組：

$\sum _{i=1}^{n-1}i\Rightarrow \frac{(n)(n-1)}{2}$

$\sum _{i=n}^{n}i\Rightarrow n$
如果

$n$ 為偶數

$gcd=\frac{n}{2}$
如果

$n$ 為奇數

$gcd=n$

標準程式

#include <iostream>
using namespace std;
 
int main() {
        int n;
        cin >> n;
        if(n > 2) {
                cout << "Yes" << endl;
                cout << "1 " << n-1 << endl << n << endl;
                for(int i = 1; i < n; i++) cout << (i == 1? "":" ") << i;
                cout << endl;
        }
        else cout << "No" << endl;
        return 0;
}

欠債5億日圓頻道

• Task Provider: Miohitokiri5474
• Task Setter: Miohitokiri5474

首殺 team20_33 (00:22)

解法說明

裸最短路尋找負環
拿 Bellman-Ford or SPFA 等演算法，假設有任意節點被更新超過

$V-1$ 次即存在負環

標準程式

Bellman-Ford

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Edge {
    int u, v, w;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<Edge> E(m);
    vector<int> s(n + 1, 1e9);
s[n-1] = 0;
    
    for (Edge& e : E) {
        cin >> e.u >> e.v >> e.w;
    }
    for (int i = 0; i < n-1; i++) {
        for (const Edge& e : E) {
            s[e.v] = min(s[e.v], s[e.u] + e.w);
        }
    }
    bool ok = false;
    for (const Edge& e : E) {
        if (s[e.v] > s[e.u] + e.w) {
            ok = true;
            break;
        }
    }
    cout << (ok ? "Yes" : "No") << '\n';
    return 0;
}

SPFA（有加入優化）

#include<bits/stdc++.h>

using namespace std;

#define maxN 50005
#define INF 0x3f3f3f3f

typedef pair < int, int > pii;
#define pb push_back
#define F first
#define S second

vector < pii > edges[maxN];
int dis[maxN], cnt2[maxN], cnt[maxN];
bool inQ[maxN], ans;

int main(){
	ios::sync_with_stdio ( false );
	cin.tie ( 0 );
	cout.tie ( 0 );

	int n, m, u, v, now;
	deque < int > q;
	int w, front = maxN, end = maxN;
	cin >> n >> m;
	while ( m-- ){
		cin >> u >> v >> w;
		edges[u].pb ( pii ( v, w ) );
	}

	memset ( dis, INF, sizeof dis );
	for ( int j = 0 ; j < n ; j++ ){
		if ( dis[j] != INF )
			continue;
		dis[j] = 0;
		inQ[j] = true;
		q.push_back ( j );
		while ( !q.empty() ){
			inQ[now = q.front()] = false;
			q.pop_front();
			for ( auto i: edges[now] ){
				if ( dis[now] + i.S < dis[i.F] ){
					dis[i.F] = dis[now] + i.S;
					cnt[i.F]++;
					if ( !inQ[i.F] ){
						if ( cnt2[i.F] >= 2 )
							q.push_front ( i.F );
						else{
							q.push_back ( i.F );
							cnt2[i.F]++;
						}
						inQ[i.F] = true;
					}
				}

				if ( cnt[i.F] >= n ){
					cout << "Yes\n";
					return 0;
				}
			}
		}
	}

	cout << "No\n";
}

城鎮賽車比賽

• Task Provider: ys
• Task Setter: ys

首殺 team20_18 (00:28)

解法說明

解法 1

題目中提到賽車的路線是起點與終點相同的迴路，也就是說他是個環

如果城鎮就只是一個環的話，那麼只須找到環中成本最小的那路段就行了；
反過來思考，也可以將路段從大到小一個個排除，最後那段路段就是要求的。

同理，城鎮若是複雜的連通圖，將所有路段從大到小一個個選出，但若當前選出的路段與已選出的路段形成環，就表示當前選出的路段要設監視器，因為他是環中最小成本的路段。

其實上述的過程就是在找一個連通圖中的最大生成樹

解法 2

題目中輸入的邊權重 (

$c\le 1000$) 非常小，
於是基於 Counting sort 的概念，不需對邊做排序，從最大成本到最小成本使用邊即可。

標準程式

解法 1

#include<bits/stdc++.h>
using namespace std;

int const maxn = 1e4 + 10;

struct edge { int u, v, w; };
vector<edge> E;
int n, m, group[maxn];

int Find(int v) {
  if (v == group[v]) return v;
  return group[v] = Find(group[v]); // Path Compression
}

void Union(int u, int v)
  { group[Find(u)] = Find(v); }

int main()
{
  scanf("%d%d", &n, &m);

  while (m--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    E.push_back({a, b, c});
  }

  for (int v = 1; v <= n; v++) group[v] = v;

  sort(E.begin(), E.end(), [&](edge x, edge y) { return x.w > y.w; });

  int cost = 0;
  for (edge e: E) {
    int a = Find(e.u), b = Find(e.v);
    if (a != b) Union(e.u, e.v);
    else cost += e.w;
  }

  printf("%d\n", cost);

  return 0;
}

解法 2

#include<bits/stdc++.h>
using namespace std;

int const maxn = 1e4 + 10;
int const maxc = 1e3 + 10;

struct edge { int u, v; };
vector<edge> E[maxc];
int n, m, group[maxn];

int Find(int v)
  { return (v == group[v])? v : group[v] = Find(group[v]); }

void Union(int u, int v)
  { group[Find(u)] = Find(v); }

int main()
{
  scanf("%d%d", &n, &m);

  while (m--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    E[c].push_back({a, b});
  }

  for (int v = 1; v <= n; v++) group[v] = v;

  int cost = 0;
  for(int c = maxc-1; c >= 1; c--) {
    for(edge e: E[c]) {
      int a = Find(e.u), b = Find(e.v);
      if (a != b) Union(e.u, e.v);
      else cost += c;
    }
  }

  printf("%d\n", cost);

  return 0;
}

藍的競程之旅–山姆機偶性

• Task Provider: CF 1352 B
• Task Setter: ian

首殺 team20_37 (00:38)

解法說明

我們的目標是把

$n$ 分成偶數或奇數，最簡單的作法就是分成

$1,1,1,...\mathrm{剩}\mathrm{下}\mathrm{的}$ 或

$2,2,2,...\mathrm{剩}\mathrm{下}\mathrm{的}$

$nk$ 可以分為幾種狀況

$n$ 偶

$k$ 奇：一定要用偶數構成

$n$ 偶

$k$ 偶：都可以，但用

$1,1,1,...$ 那組可以做出更多數

$n$ 奇

$k$ 奇：一定要用奇數構成

$n$ 奇

$k$ 偶：無法構成

另外當需要使用偶數構成，且

$n<2k$ 無法構成，當然，在任何情況下

$n<k$ 無法構成。
此外要注意使用 long long

標準程式

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n, m, i, j, k;
    cin >> m;
    while (m--) {
        cin >> n >> k;
        if (n < k) {
            cout << "NO" << endl;
            continue;
        }
        if (n % 2 && k % 2 == 0) {
            cout << "NO" << endl;
            continue;
        }
        if (n % 2 == 0 && k % 2) {
            if (n < k * 2) {
                cout << "NO" << endl;
                continue;
            }
            cout << "YES" << endl;
            while (k-- != 1) {
                cout << 2 << " ";
                n -= 2;
            }
            cout << n << endl;
        } else {
            cout << "YES" << endl;
            while (k-- != 1) {
                cout << 1 << " ";
                n -= 1;
            }
            cout << n << endl;
        }
    }

    return 0;
}

AB 的祖先

• Task Provider: Miohitokiri5474
• Task Setter: Miohitokiri5474

首殺 team20_38 (00:11)

解法說明

就是裸 LCA（我甚至沒有包裝欸，可以回去看進階圖論那週的課程）
作法有三種，倍增法、Tarjan、輕重鍊剖分
標程是用倍增法

標準程式

#include<bits/stdc++.h>

using namespace std;

#define maxN 100005
#define maxLog 20
#define pb push_back

vector < int > edges[maxN];
int dp[maxN][maxLog], D[maxN], n;

void dfs ( int d, int p, int dep ){
	D[d] = dep++;
	dp[d][0] = p;
	for ( auto i: edges[d] )
		if ( i != p )
			dfs ( i, d, dep );
}

inline void buildLCA ( void ){
	memset ( dp, -1, sizeof dp );
	dfs ( 0, -1, 0 );
	for ( int k = 1 ; k < maxLog ; k++ )
		for ( int i = 0 ; i < n ; i++ )
			if ( dp[i][k - 1] != -1 )
				dp[i][k] = dp[dp[i][k - 1]][k - 1];
}

inline int findLCA ( int x, int y ){
	if ( D[x] < D[y] )
		swap ( x, y );

	for ( int i = maxLog - 1 ; i >= 0 ; i-- )
		if ( dp[x][i] != -1 && D[dp[x][i]] >= D[y] )
			x = dp[x][i];

	if ( x == y )
		return x;

	for ( int i = maxLog - 1 ; i >= 0 ; i-- )
		if ( dp[x][i] != dp[y][i] )
			x = dp[x][i], y = dp[y][i];

	return dp[x][0];
}

int main(){
	ios::sync_with_stdio ( false );
	cin.tie ( 0 );
	cout.tie ( 0 );

	int q, u, v;
	cin >> n >> q;
	for ( int i = 1 ; i < n ; i++ ){
		cin >> u >> v;
		edges[u].pb ( v );
		edges[v].pb ( u );
	}

	buildLCA();

	while ( q-- ){
		cin >> u >> v;
		cout << findLCA ( u, v ) << '\n';
	}
}