2020 高階競程 Contest #7 - 題解

Digital Firends 3

• Task Provider: raiso
• Task Setter: raiso

首殺 team20_23 (00:06)

解法說明

這題就是一棵樹去遍歷，以

$k$ 開始當作樹根，找到每個節點的父節點，就結束了。

這題的考點還有一個就是會使用輸入輸出加速，這樣你就成功了！

標準程式

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

const int maxn = 3e5 + 1;

int vis[maxn];
set<int> lk[maxn];
queue< pair<int, int> > Q;



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, q, k;
	cin >> n >> m >> q >> k;
	
	for(int i = 0; i <= n; i++) vis[i] = -1;
	
	for(int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		lk[a].insert(b);
		lk[b].insert(a);
	}
	
	Q.push(make_pair(k, k));
	//(pre, tar)
	while(!Q.empty()) {
		auto nw = Q.front(); Q.pop();
		int tar = nw.second;
		int pre = nw.first;
		if(vis[tar] != -1) continue;
		vis[tar] = pre;
		for(auto i: lk[tar]) if(vis[i] == -1) Q.push(make_pair(tar, i));
	}

	for(int nw,i = 0; i < q; i++) {
		cin >> nw;
		cout << (i==0? "": " ") << vis[nw];
	}
	cout << endl;
	return 0;
}

藍的競程之旅–欸可是 our

• Task Provider: Ian
• Task Setter: Ian

首殺 team20_18 (00:07)

解法說明

簡單來說是做前綴和，在提示中有提到 xor 其實是在數某個 bit 的 1 到底出現過奇數次還是偶數次，也就是說 xor 運算有各種有的沒的交換結合率，並且

$(a\oplus b\oplus c\oplus d)\oplus (a\oplus b)=c\oplus d$ 也就是說可以透過再 xor 運算一次逆運算出

$c\oplus d$ 的結果

定義

$a\oplus \oplus b=X_a\oplus X_{a+1}\oplus ...\oplus X_b$

$(0\oplus \oplus b)\oplus (0\oplus \oplus a-1)$ 其實就等於

$a\oplus \oplus b$ 也就是消去掉

$0\oplus \oplus a-1$ 的部分

標準程式

#include <bits/stdc++.h>
using namespace std;
int data[100010];
int quian[100010];
int main() {
    int n, m, i, j, k;

    quian[0] = 0;
    cin >> n >> m;
    for (i = 0; i < n; i++) {
        cin >> data[i];
    }
    for (i = 1; i <= n; i++) {
        quian[i] = quian[i - 1] ^ data[i - 1];
    }
    int a, b;
    while (m--) {
        cin >> a >> b;
        cout << (quian[b] ^ quian[a - 1]) << endl;
    }

    return 0;
}

次小生成樹

• Task Provider: MiohitoKiri5474
• Task Setter: MiohitoKiri5474

首殺 team20_23 (01:24)

解法說明

次小，代表權重和為第二小
所以觀察一下剩下還沒有用到的邊，檢查這個邊加進去現有的 MST 中，所形成的環拿掉最小的邊的權重和，是否為除了 MST 以外、最小的生成樹

所以步驟會像是這樣：

1. 做 MST
2. 對 MST 做倍增（或剖分，反正能用來找 LCA 的東西皆可）
3. 查詢沒有用到的點鐘，
   $w_i-LCA(u_i,v_i)$ 的最小值

另外

$LCA(u_i,v_i)$ 是代表在 MST 上，

$u_i,v_i$ 的路徑上所經過的邊的最大值
dp 表單的 first 就是存標準倍增法的節點
而 second 是存點

$i$ 到第

$2^{k-1}$ 個祖先之間，以及

$2^{k-1}$ 的祖先到

$2^k$ 之間，最大的邊
所以倍增轉移式如下

$$dp[i][k].first=dp[dp[i][k-1].first][k-1].first$$

$$dp[i][k].second=max(dp[i][k-1].second,dp[dp[i][k-1].first][k-1].second)$$

標準程式

// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define INF 0x3f3f3f3f
#define maxN 200005
#define maxLog 20
typedef pair < int, int > pii;
#define F first
#define S second

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

inline bool cmp ( bri a, bri b ){
    return a.w < b.w;
}

vector < bri > edges;
vector < pii > mst[maxN];
int ma, dis[maxN], n, D[maxN];
pii dp[maxN][maxLog];
vector < int > LOG;

inline void Init ( void ){
    for ( int i = 0 ; i < maxN ; i++ )
        dis[i] = i;
}

inline int find ( int d ){
    return dis[d] == d ? d : dis[d] = find ( dis[d] );
}

inline void Union ( int a, int b ){
    dis[find ( a )] = find ( b );
}

inline bool same ( int a, int b ){
    return find ( a ) == find ( b );
}

inline void dfs ( int d, int p, int dep ){
    D[d] = dep++;
    dp[d][0].F = p;
    for ( auto i: mst[d] ){
        if ( i.F == p )
            continue;
        dp[i.F][0] = pii ( d, i.S );
        dfs ( i.F, d, dep );
    }
}

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

inline void 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].F != -1 && D[dp[x][i].F] >= D[y] ){
            ma = max ( ma, dp[x][i].S );
            x = dp[x][i].F;
        }
    }

    if ( x == y )
        return;

    for ( int i = maxLog - 1 ; i >= 0 ; i-- ){
        if ( dp[x][i].F != dp[y][i].F ){
            ma = max ( ma, max ( dp[x][i].S, dp[y][i].S ) );
            x = dp[x][i].F, y = dp[y][i].F;
        }
    }

    ma = max ( ma, max ( dp[x][0].S, dp[y][0].S ) );
}

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

    int m, t = 1, ans, swp = 0, u, v, w;
    vector < int > unUsed;
    for ( int i = 0 ; i < maxLog ; i++ ){
        LOG.pb ( t );
        t <<= 1;
    }
    t = 1;
    cin >> n >> m;
    Init();
    ans = INF;
    ma = -1;

    for ( int i = 0 ; i < m ; i++ ){
        cin >> u >> v >> w;
        edges.pb ( bri { u, v, w } );
    }

    sort ( edges.begin(), edges.end(), cmp );
    for ( int i = 0 ; i < m ; i++ ){
        if ( same ( edges[i].u, edges[i].v ) ){
            unUsed.pb ( i );
            continue;
        }
        Union ( edges[i].u, edges[i].v );
        mst[edges[i].u].pb ( pii ( edges[i].v, edges[i].w ) );
        mst[edges[i].v].pb ( pii ( edges[i].u, edges[i].w ) );
        swp += edges[i].w;
    }

    buildLCA();
    for ( auto i: unUsed ){
        ma = -1;
        findLCA ( edges[i].u, edges[i].v );
        ans = min ( ans, edges[i].w - ma );
    }

    cout << ans + swp << '\n';
}

丸亀製麺買一送一

• Task Provider: ys
• Task Setter: ys

首殺 team20_05 (00:16)

解法說明

• 令
  $x$ 為
  $m$ 個人過來前，桌子上目前佔最多人的人數
• 令
  $k$ 為題目要求的最多人的那桌的最小解

若先去坐

$x$ 人的那個桌子，

$k$ 會變大，所以

$m$ 個人應先分配到其他桌子上
於是求除了

$x$ 人的桌子外，還剩下多少位置(rem)

for (int i = 0; i < N; i++) rem += x-a[i];

若

$m\le \text{rem}$ 則顯然

$k=x$
若

$m>\text{rem}$ 就將部份人分配到剩下的位置中(此時桌子人數都為

$x$)，
接著將剩餘的人

$(m-\text{rem})$ 平均分配到每張桌子上，

$k=x+\lceil \frac{m-\text{rem}}{N}\rceil$

標準程式

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

int const maxN = 110;

int N, m, a[maxN];

int main() {
  scanf("%d%d", &N, &m);
  for(int i = 0; i < N; i++) scanf("%d", &a[i]);

  int x = *max_element(a, a+N), rem = 0; // remainder
  for(int i = 0; i < N; i++) rem += x-a[i];

  if(m > rem) printf("%d", x + (m-rem)/N + !!((m-rem)%N));
  else printf("%d", x);

  return 0;
}

【潤羽るしあ】新衣装と新ゲーム【ホロライブ】

• Task Provider: leo900807
• Task Setter: leo900807

首殺 – (-:-)

解法說明

Subtask 1

$P_n^m$

暴力匹配，每架飛機都匹配一個機場，看是否能降落，共

$P_n^m$ 種可能，最後取

$max$ 。

Subtask 2

$O(NM)$

將每架飛機與機場，視為二分圖兩邊的點，對於每架飛機，將其與其航程內所有機場連邊，最後對這張圖做最大匹配即可。

標準程式

#include <iostream>
#include <utility>
#include <bitset>
#include <vector>
#define x first
#define y second
using namespace std;

pair<int, int> p[1001], a[1001];

vector<int> v[1001];

bitset<1001> vis;

int mp[1001], mq[1001];

bool matching(int u){
    vis[u] = 1;
    for(int i : v[u])
        if(!mq[i] || !vis[mq[i]] && matching(mq[i]))
            return mq[mp[u] = i] = u, 1;
    return 0;
}

int dis2(pair<int, int> a, pair<int, int> b){
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

int main() {
    int n, m, d[1001], cnt = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> p[i].x >> p[i].y >> d[i];
    for(int i = 1; i <= m; i++)
        cin >> a[i].x >> a[i].y;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(dis2(p[i], a[j]) <= d[i] * d[i])
                v[i].push_back(j);
    for(int i = 1; i <= n; i++)
        if(vis.reset(), matching(i))
            cnt++;
    cout << cnt << "\n";
    for(int i = 1; i <= n; i++)
        if(mp[i])
            cout << i << " " << mp[i] << "\n";
}

快晴

• Task Provider: ys
• Task Setter: ys

首殺 team20_12 (02:17)

解法說明

顯然這是一種找最短路徑的問題，當

$K=1$ 時，直接用 BFS 算出起點到終點的最短路徑。
而

$K>1$ 時，一個位置

$(a,b)$ 可在

$1$ 秒內飛到

$j\le K$ 遠的位置

$(na,nb)$：

while(q.size()) {
  auto [a, b] = q.front(); q.pop();

  for(int i = 0; i < 4; i++) // 方向 i
    for(int j = 1; j <= K; j++) {
      int na = a + j*da[i], nb = b + j*db[i]; // j 單位遠的下個位置

      if(maze[na][nb] != '.') break; // 該方向中途遇到障礙物
      if(vis[na][nb]) continue;

      q.push({na, nb});
      t[na][nb] = t[a][b] + 1; // 原位置秒數加 1 秒
      vis[na][nb] = true;
    }
}

這樣複雜度為

$O(N\cdot M\cdot K)$，若飛行途中都沒遇到障礙物，則會 TLE

仔細觀察同個方向飛行時無障礙物的狀況，
若下個位置

$(na,nb)$ 到達時間較小，那麼從

$(na,nb)$ 開始飛會比較省時，
於是同個方向的搜尋可提早結束：

if(t[na][nb] < t[a][b] + 1) break;

複雜度為

$O(N\cdot M)$

標準程式

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

int const maxN = 1e3 + 10;
int da[] = {1, -1, 0, 0}; // direction
int db[] = {0, 0, -1, 1};

int N, M, K, a0, b0, a1, b1, t[maxN][maxN]; // t := time
char maze[maxN][maxN];
bool vis[maxN][maxN]; // vis := visited

int main()
{
  scanf("%d%d%d", &N, &M, &K);
  for(int i = 1; i <= N; i++)
    for(int j = 1; j <= M; j++) cin >> maze[i][j];
  scanf("%d%d%d%d", &a0, &b0, &a1, &b1);


  queue<pair<int, int>> q;
  q.push({a0, b0});
  memset(t, 0x3f, sizeof t); // 初始無限大
  memset(vis, false, sizeof vis);
  t[a0][b0] = 0;
  vis[a0][b0] = true;

  while(q.size()) {
    auto [a, b] = q.front(); q.pop();

    for(int i = 0; i < 4; i++)
      for(int j = 1; j <= K; j++) {
        int na = a + j*da[i], nb = b + j*db[i];

        if(maze[na][nb] != '.') break;
        if(t[na][nb] < t[a][b] + 1) break;
        if(vis[na][nb]) continue;

        q.push({na, nb});
        t[na][nb] = t[a][b] + 1;
        vis[na][nb] = true;
      }
  }

  printf("%d\n", vis[a1][b1]? t[a1][b1] : -1);

  return 0;
}

增殖序列

• Task Provider: TIOJ 2005
• Task Setter: leo900807

首殺 – (-:-)

解法說明

Subtask 1

$O(n)$

不會超出 long long 範圍，直接做就好。

Subtask 2

$O(n)$

由題目敘述可以導出遞迴式

$a_n=\begin{array}{r}\{\begin{array}{ll}1& ,\text{ if }n=1\\ a_{n-1}\times {10}^{\lfloor {\log }_{10}n\rfloor +1}+n& ,\text{ if }n>1\end{array}\end{array}$

那就直接

$O(n)$ 做，要記得

$\mathrm{mod}m$。

Subtask 3

$O(lgN)$

這種線性遞迴的題目，就會想到可以用矩陣快速冪來優化，但是

${10}^{\lfloor {\log }_{10}n\rfloor +1}$ 該如何處理呢？
不妨將其拆成

$0\sim 9,10\sim 99,100\sim 999,\cdots$ 並分開進行矩陣快速冪，就能將

${10}^{\lfloor {\log }_{10}n\rfloor +1}$ 視為常數，而矩陣的形式如下：

$$A=\left[\begin{array}{ccc}{10}^{\lfloor {\log }_{10}n\rfloor [phone]\mathrm{}}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\end{array}\right],B=\left[\begin{array}{c}{a}_n\\ n\\ 1\end{array}\right]$$

那麼

$$AB=\left[\begin{array}{c}{a}_{n+1}\\ n+1\\ 1\end{array}\right]$$

因此一開始若將

$B$ 設為

$\left[\begin{array}{c}0\\ 1\\ 1\end{array}\right]$ ，那麼

$a_n=A^{n}B$

接著只要用上述的方法分段快速冪就可以得到答案了，要記得過程中都要

$\mathrm{mod}m$

標準程式

看起來很亂，其實主要都是矩陣運算，實際上程式碼不長

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    long long t, n, m, lim, a[3][3], b[3], tmp[3][3], x;
    cin >> t;
    while(t--){
        cin >> n >> m;
        x = log10(n) + 1;
        lim = 1;
        while(x--)
            lim *= 10;
        b[0] = 0, b[1] = 1, b[2] = 1;
        for(long long mul = 10; mul <= lim; mul *= 10){
            a[0][0] = mul, a[0][1] = 1, a[0][2] = 0;
            a[1][0] = 0, a[1][1] = 1, a[1][2] = 1;
            a[2][0] = 0, a[2][1] = 0, a[2][2] = 1;
            x = min(mul - 1, n) - mul / 10 + 1;
            while(x){
                if(x & 1){
                    for(int i = 0; i < 3; i++)
                        for(int j = 0; j < 3; j++){
                            tmp[i][j] = 0;
                            for(int k = 0; k < 3; k++)
                                tmp[i][j] = (tmp[i][j] + a[i][k] * b[k] % m) % m;
                        }
                    for(int i = 0; i < 3; i++)
                            b[i] = tmp[i][0];
                }
                for(int i = 0; i < 3; i++)
                    for(int j = 0; j < 3; j++){
                        tmp[i][j] = 0;
                        for(int k = 0; k < 3; k++)
                            tmp[i][j] = (tmp[i][j] + a[i][k] * a[k][j] % m) % m;
                    }
                for(int i = 0; i < 3; i++)
                    for(int j = 0; j < 3; j++)
                        a[i][j] = tmp[i][j];
                x >>= 1;
            }
        }
        cout << b[0] << "\n";
    }
}