2019 ICPC NCPU 簡易講評
===
###### tags: `ICPC` `NCPU` `NCTU` `NCPU2019`

[正賽題本](https://drive.google.com/open?id=1RqS5t_8qa77T2Tcxvjo6vqgNQkgkgdY7)
[參考測資](https://drive.google.com/open?id=1v6L6O45ILNZ5TJixaQgytggOS-O1D15q)

先貼 Sample code ，有空再來寫點講評。我的專長是胡說八道，如果你認為講評亂寫，那很可能是正常的。如果有疑問想要討論，可以來信 [e-mail] ，我再來研究該如何進行。

工商時間一：如果比賽可以寫 Kotlin 又不會 TLE，那何苦寫 JAVA。
工商時間二：其實也可以用 Python ，但 Python 太夯又在某些硬核題目一定會 TLE ，在規則修改之前，請大家不要立志當個 Python 戰士。
工商時間三：如果有菜雞發現自己被多測資 EOF 結尾坑，請參考 Problem C 跟 Problem E 的 sample code。

## Problam A

計算出輸入的數字 $n$ 能夠整除的最小 $k$ 階乘 ($k!$)。保證 $k$ 在 $1$ 到 $12$ 之間，一個一個判斷即可。命題時有確保計算過程中不會超過 32-bit 有號整數，算是相當友善的一題。

private fun nextLine() = readLine()!!
private fun nextInt() = nextLine().toInt()
private fun nextToks() = nextLine().split(" ")
private fun nextInts() = nextToks().map{it.toInt()}

fun main() {
    val m = nextInt()
    for (x in 0 until m) {
        val n = nextInt()
        var fact = 1
        for (i in 1..12) {
            fact *= i
            if (fact % n == 0) {
                println("$i")
                break
            }
        }
    }
}

## Problem B

計算 $b, b+1, \ldots, e$ 用二進位表示法時總共有多少個 $1$，如果你會使用像是 Java/Kotlin 的 `java.lang.Integer.bitCount()` 或是 C++ 的 `__builtin_popcount()` 則寫起來會非常快。當然如何快速的計算出一個整數的 set bit 有多少是一個有趣的議題也是常常被拿來面試的題目，有興趣的同學可以看一下 [Hamming weight](https://en.wikipedia.org/wiki/Hamming_weight) 的維基百科。

private fun nextLine() = readLine()!!
private fun nextInt() = nextLine().toInt()
private fun nextToks() = nextLine().split(" ")
private fun nextInts() = nextToks().map{it.toInt()}

fun main() {
    val m = nextInt()
    for (x in 1..m) {
        val (b, e) = nextInts()
        var ans = 0
        for (i in b..e) {
            ans += java.lang.Integer.bitCount(i)
        }
        println("$ans")
    }
}

註一：NCPU參賽者都對了，作為命題者感謝大家，我希望以後我能出有鑑別度的題目。原本打算要出的題目規格是 $1\le b\le e \le 10^{18}$，有興趣的同學可以想一下這樣要怎麼算。

註二：或許有些人會想要寫的非常短，像是下面這樣。現代的 C++/Java/Kotlin 都有一些方便資料處理的 functional language 類型的寫法。

private fun nextLine() = readLine()!!
private fun nextInt() = nextLine().toInt()
private fun nextToks() = nextLine().split(" ")
private fun nextInts() = nextToks().map{it.toInt()}

fun main() = (1..nextInt()).forEach {
    val (b, e) = nextInts()
    println((b..e).map{java.lang.Integer.bitCount(it)}.sum())
}

## Problem C

本題最重要的是發現操作 4 是一個幌子，只需要紀錄是否有翻轉，剩餘的就是考實做能力了。各種偷吃步都歡迎大家用，但是取巧過頭未必好除錯。本次的測試資料使用 array-based 的結構來模擬是有機會在時限內通過，但在國際賽時不建議各位這麼大膽，要知道複雜度分析套下去，很可能會要 $O(nm)$ 的時間。正確的作法是使用 linked-list ，範例程式碼即為一種實現的方法。

#include<bits/stdc++.h>

using namespace std;

struct node{
    struct node *nxt, *prv;
    long long v;
}pos[100002];

inline node* cut(node *p)
{
    // cut a node from the list via its pointer
    // return value is an implementation trick
    p->nxt->prv = p->prv;
    p->prv->nxt = p->nxt;
    p->nxt = p->prv = NULL;
    return p;
}

inline node* insert(node *p, node *q)
{
    // idea: always insert q as a successor (on the right)
    q->nxt = p->nxt;
    p->nxt->prv = q;
    q->prv = p;
    p->nxt = q;
    return q;
}

int main()
{
    int n, m, scale=0;
    while(cin >> n >> m)
    {
        scale += n+m;
        for(int i = 0; i <= n+1; i++)
        {
            // dummy head & tail
            pos[i].nxt = (i<=n)?pos+i+1:NULL;
            pos[i].prv = (i>0)?pos+i-1:NULL;
            pos[i].v = (i<=n and i > 0)?i:0;
        }
        bool rev = false;
        for(int i = 0; i < m; i++)
        {
            int op, x, y;
            cin >> op;
            if(op==4){
                rev = !rev;
                continue;
            }
            cin >> x >> y;
            node *lx=pos[x].prv, *ly = pos[y].prv;
            if(op==3){
                node *lx=pos[x].prv, *ly = pos[y].prv;
                if(lx==pos+y){
                    insert(ly,cut(pos+x));
                }
                else if(ly==pos+x){
                    insert(lx,cut(pos+y));
                }
                else{
                    insert(lx,cut(pos+y));
                    insert(ly,cut(pos+x));
                }
            }
            else if(op==(rev?1:2)){ // x to the right or reverse left of y
                if(lx==pos+y) continue;
                insert(pos+y,cut(pos+x));
            }
            else{ // x to the left or reverse right of y
                if(ly==pos+x) continue;
                insert(ly,cut(pos+x));
            }
        }
        long long ans = 0;
        if(rev)
        {
            for(node *p = pos[n+1].prv; p; p = p->prv)
            {
                ans += p->v;
                p = p->prv;
                if(!p) break;
            }
        }
        else
        {
            for(node *p = pos[0].nxt; p; p = p->nxt)
            {
                ans += p->v;
                p = p->nxt;
                if(!p) break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

不知道該怎樣說 Kotlin 的 `null` 與 `!!`

private fun nextLine() = readLine()!!
private fun nextInt() = nextLine().toInt()
private fun nextToks() = nextLine().split(" ")
private fun nextInts() = nextToks().map{it.toInt()}

data class Node(var value: Int, var next: Node? = null,var prev: Node? = null){
    fun cut(): Node {
        this.next!!.prev = this.prev
        this.prev!!.next = this.next
        this.prev = null
        this.next = null
        return this
    }
    fun insert(p: Node) {
        p.prev = this
        p.next = this.next
        this.next!!.prev = p
        this.next = p
    }
}

fun solve() {
    val (n, m) = nextInts()
    var rev = false
    var node = (0..(n+1)).map{Node(it%(n+1))}
    (0..n).map{node[it+1].prev = node[it]}
    (0..n).map{node[it].next = node[it+1]}
    for (opCnt in 1..m) {
        val op = nextInts()
        if (op[0] == 4) {
            rev = !rev
            continue
        }
        var (p, x, y) = op
        var lx = node[x].prev!!
        var ly = node[y].prev!!
        if (rev && p in 1..2) p = 3 - p
        when (p) {
            3 -> {
                if (ly!=node[x]) ly.insert(node[x].cut())
                if (lx!=node[y]) lx.insert(node[y].cut())
            }
            2 -> node[y].insert(node[x].cut())
            1 -> if (ly!=node[x]) ly.insert(node[x].cut())
        }
    }
    var ans = 0L
    var iter: Node? = node[0]
    if (!rev || n%2 == 1) iter = iter!!.next
    while (iter!=null && iter.next != null) {
        ans += iter.value
        iter = iter.next!!.next
    }
    println(ans)
}

fun main() {
    while (true) { 
        try {
            solve()
        } 
        catch (e: NullPointerException) {
            break
        }
    }
}

## Problem D

總之就是把資料讀進來，去除不可用的資料，其餘做成一些可比較大小的資料。排序，找前三個。如果找不到前三個，那就有幾個算幾個。最後，依照順序印出來。在這種時候，現代 C++/Java/Kotlin 都提供了一些相對 functional 一點的寫法。

private fun nextLine() = readLine()!!
private fun nextInt() = nextLine().toInt()
private fun nextToks() = nextLine().split(" ")
private fun nextInts() = nextToks().map{it.toInt()}

data class AP(val macAddr: String, val rssi: Int): Comparable<AP> {
    override fun compareTo(other: AP): Int {
        if(this.rssi == other.rssi)
            return this.macAddr.compareTo(other.macAddr)
        return other.rssi - this.rssi
    }
}

fun main() {
    val ncases = nextInt()
    for (case_i in 1..ncases) {
        val n = nextInt()
        val aps = (1..n).map{nextToks()}
                .filter{it.last().toInt()<=1000}
                .map{AP(it[0],it[1].toInt())}
        aps.sorted().take(3).forEach{
            val (mac, rssi) = it
            println("$mac $rssi")
        }
    }
}

## Problem E

這一題其實是個閱讀測驗，每次做一層，然後往下面填下去。請認真觀察每一個格子會貢獻他的值給下方三個格子，編號邊好沒煩惱。

private fun nextLine() = readLine()!!
private fun nextInt() = nextLine().toInt()
private fun nextToks() = nextLine().split(" ")
private fun nextInts() = nextToks().map{it.toInt()}

fun solve(n: Int) {
    var ans: Array<Array<LongArray>> = Array(n+1) {
        Array(n+1){ LongArray(n+1) {0L} }
    }
    ans[0][0][0] = 1L
    for (i in 0 until n)
        for (j in 0..i)
            for (k in 0..i) {
                ans[i+1][j][k] += ans[i][j][k]
                ans[i+1][j+1][k+1] += ans[i][j][k]
                ans[i+1][j+1][k] += ans[i][j][k]
            }
    for (i in 0..n)
        println(ans[n][i].take(i+1).joinToString(separator=" "))
}

fun main() {
    try {
        while (true) {
            solve(nextInt())
        }
    }
    catch (e: NullPointerException) {
    }
}

## Problem F

這一題可以使用遞迴或是 stack 來做。範例程式碼是用遞迴，但通常要恰當的使用 Stack 效率才會好。由於測資規模的關係，可以不用很在意實做上的複雜度。註：這一題我驗題時沒寫，一開始貼的程式碼是不知道是誰寫的，只好重新寫一份 Kotlin。不過這題相信用 Python 會更簡短。

private fun nextLine() = readLine()!!
private fun nextInt() = nextLine().toInt()
private fun nextToks() = nextLine().split(" ")
private fun nextInts() = nextToks().map{it.toInt()}

private fun extract(s: String): String {
    if ('[' in s) {
        val l = s.indexOf('[')
        var acc = 1
        for (r in (l+1)..s.length) {
            if (s[r] == '[') acc += 1
            if (s[r] == ']') acc -= 1
            if (acc == 0) {
                return s.substring(0,l-1)+
                       extract(s.substring(l+1,r))
                       .repeat(s.substring(l-1,l).toInt())+
                       extract(s.substring(r+1))
            }
        }
    }
    return s
}

fun main() {
    (1..nextInt()).map{nextLine()}.map{extract(it)}.map{println(it)}
}

## Problem G

先跟各位道歉，這題我已經忘記我當初在寫什麼了。這個題目其實規模大的時候需要點想法，但實際上規模很小，只需要討論幾件事情就好了：
1. 圖是否連通，沒有就 `n` 了
2. 圖如果連通，那就檢查邊的數量。邊數比點數少一，就是棵樹，那也是 `n`。邊同點數，那就是剛好有一個 cycle，也是 `n`。
3. 邊數比點數多 $k>0$ ，那至少會有 $k+1$ 個 Cycle：想像一個 Spanning tree，任何不在 Spanning tree 的邊都會製造出一個 cycle 且其上的邊都是屬於那個 Spanning tree 的。$k>1$ 的也就結案，是 `y: there are at least three cycles`
4. 剩下來的就是邊數比點數多一個邊需要判斷。因測資規模限制，這頂多只有 11 條邊，因此窮舉所有的可能性來判斷是否剛好有兩個 cycle 即可決定答案。註：如果圖比較大，就要檢查兩條不在 Spanning tree 上的邊是不是可以形成某 cycle 上的兩邊，由於 Spanning tree 上兩點之間的路徑唯一，要快速檢查並不難的。

#include<bits/stdc++.h>

using namespace std;

int fin(vector<int> &p, int x)
{
    if(p[x]==-1) return x;
    return p[x] = fin(p,p[x]);
}

int cc(int n, int m, const vector<pair<int, int>> &e)
{
    vector<int> p(n,-1);
    for(auto &x: e)
    {
        int u = fin(p,x.first), v = fin(p,x.second);
        if(u!=v) p[u]=v;
    }
    int cnt=0;
    for(int i = 0; i < n; i++)
        if(p[i]==-1) cnt++;
    return cnt;
}

bool connected(int n, int m, const vector<pair<int, int>> &e)
{
    return cc(n,m,e)==1;
}

bool verify(int n, int m, const vector<pair<int, int>> &e)
{
    int cnt = 0;
    for(int i = 1; i < (1<<m); i++)
    {
        vector<int> deg(n,0);
        vector<pair<int,int>> f;
        for(int j = 0; j < m; j++)
        {
            if((1<<j)&i)
            {
                deg[e[j].first]++;
                deg[e[j].second]++;
                f.push_back(e[j]);
            }
        }
        bool all_deg_2_or_0=true;
        int deg_2_cnt = 0;
        for(int j = 0; j < n; j++)
            if(deg[j]!=0 && deg[j]!=2)
                all_deg_2_or_0=false;
            else if(deg[j]==2) deg_2_cnt++;
        if(!all_deg_2_or_0) continue;
        if(cc(n,f.size(),f)==n-deg_2_cnt+1) cnt++;
    }
    return cnt >= 3;
}

void solve()
{
    vector<pair<int, int>> e;
    int n, m, u, v;
    scanf("%d%d",&n,&m);
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d",&u,&v);
        e.push_back(make_pair(u-1,v-1));
    }
    if(!connected(n,m,e) || m<=n) puts("n");
    else if(m>n+1 || verify(n,m,e)) puts("y: there are at least three cycles");
    else puts("y");
}

int main()
{
    int ncases;
    scanf("%d",&ncases);
    while(ncases--) solve();
    return 0;
}

## Problem H

這一題前面三個先特例處理。其餘的先觀察當 $\max(|x|,|y|)=k$ 時，總共會有 $4\phi(k)$ 個 $\frac{y}{x}$ 是題目說的 rational number。如果你看完錢一句話，不知道我在寫什麼，那很可能是你不認識 [Euler's Totient function](https://en.wikipedia.org/wiki/Euler%27s_totient_function)，先請你看個參考資料，這個上離散數學或是密碼學時很可能會學到。有很多數學的結論可以幫助各位同學計算 $\phi(k)$，如利用相關性質改寫 [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) 可以在 $O(n\log n)$ 算出來。因此再針對要求的問題做一次 prefix sums來計算出有多少個 rational number 是 $\max(|x|,|y|)<k$ 的，並跑至多 $O(k)$ 次 GCD 計算驗出有幾個 $\max(|x|,|y|)=k$ 的 rational number 排在輸入測資的前面。總體耗時約 $O(n\log n)$ (在 Word-RAM model 下)。

#include<bits/stdc++.h>

using namespace std;

long long phi[1000001] = {0LL,1LL};
int witness[1000001] = {0};
long long acc[1000001] = {0,3};

long long GCD(long long x, long long y)
{
    //assume 0<=x<=y
    return x?GCD(y%x,x):y;
}

long long gcd(long long x, long long y)
{
    return GCD(abs(x),abs(y));
}

void solve()
{
    long long x, y, z;
    scanf("%lld%lld",&y,&x);
    z = max(abs(x),abs(y));
    if(x<=0) printf("0\n");
    else if(gcd(abs(y),abs(x))!=1) printf("0\n");
    else if(max(abs(x),abs(y))==1) printf("%lld\n",2+y);
    else
    {
        long long ans = acc[z-1];
        if(y<0 and x+y < 0)
        {
            for(int i = 1; i <= x; i++)
                if(gcd(i,z)==1) ans++;
        }
        else if(y<0 and x+y >0)
        {
            ans += phi[z];
            for(int i = -z+1; i <= y; i++)
                if(gcd(i,z)==1) ans++;
        }
        else if(y>0 and x-y >0)
        {
            ans += 2*phi[z];
            for(int i = 1; i <= y; i++)
                if(gcd(i,z)==1) ans++;
        }
        else
        {
            ans += 3*phi[z];
            for(int i = z-1; i >= x; i--)
                if(gcd(i,z)==1) ans++;
        }
        printf("%lld\n",ans);
    }
}

int main()
{
    for(int i = 2; i <= 1000000; i++) phi[i]=i;
    for(int i = 2; i <= 1000000; i++)
        if(witness[i]==0)
        {
            phi[i] = i-1;
            for(long long j = i+i; j <= 1000000; j+=i)
                witness[j] = i, phi[j] /= i, phi[j]*=i-1;
        }
    for(int i = 2; i <= 1000000; i++)
        acc[i] = acc[i-1]+phi[i]*4;
    int ncases;
    scanf("%d",&ncases);
    while(ncases--) solve();
    return 0;
}

補個 Kotlin 版本。

import kotlin.math.*

private fun nextLine() = readLine()!!
private fun nextInt() = nextLine().toInt()
private fun nextToks() = nextLine().split(" ")
private fun nextInts() = nextToks().map{it.toInt()}

const val MAX = 1000001

var phi = IntArray(MAX+1){it}
var notPrime = BooleanArray(MAX+1){false}
var acc = LongArray(MAX+1){0L}

fun gcd(x: Int, y: Int): Int {
    return if (x==0) y else gcd(y%x, x)
}

fun solve() {
    val (y,x) = nextInts()
    val z = max(abs(x),abs(y))
    if (x<=0) println(0)
    else if (gcd(abs(x),abs(y))!=1) println(0)
    else if (z==1) println(2+y)
    else {
        var ans = acc[z-1]
        if (y<0 && x+y<0) {
            for (i in 1..x) if (gcd(i,z)==1) ans += 1
        }
        else if (y<0 && x+y>0) {
            ans += phi[z]
            for (i in (1-z)..y) if (gcd(-i,z)==1) ans += 1
        }
        else if (y>0 && x-y>0) {
            ans += 2*phi[z]
            for (i in 1..y) if (gcd(i,z)==1) ans += 1
        }
        else {
            ans += 3*phi[z]
            for (i in z downTo x) if (gcd(i,z)==1) ans += 1
        }
        println(ans)
    }
}

fun main() {
    acc[1] = 3
    for (i in 2..MAX) {
        if (notPrime[i] == false) {
            for (j in i..MAX step i) {
                notPrime[j] = true
                phi[j] /= i
                phi[j] *= i-1
            }
        }
        acc[i] = phi[i]*4 + acc[i-1]
    }
    (1..nextInt()).forEach{solve()}
}