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 ，有空再來寫點講評。我的專長是胡說八道，如果你認為講評亂寫，那很可能是正常的。如果有疑問想要討論，可以來信 mzshieh@nctu.edu.tw ，我再來研究該如何進行。
工商時間一：如果比賽可以寫 Kotlin 又不會 TLE，那何苦寫 JAVA。
工商時間二：其實也可以用 Python ，但 Python 太夯又在某些硬核題目一定會 TLE ，在規則修改之前，請大家不要立志當個 Python 戰士。
工商時間三：如果有菜雞發現自己被多測資 EOF 結尾坑，請參考 Problem C 跟 Problem E 的 sample code。
## Problam A
計算出輸入的數字 $n$ 能夠整除的最小 $k$ 階乘 ($k!$)。保證 $k$ 在 $1$ 到 $12$ 之間，一個一個判斷即可。命題時有確保計算過程中不會超過 32-bit 有號整數，算是相當友善的一題。
```kotlin=
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) 的維基百科。
```kotlin=
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 類型的寫法。
```kotlin=
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 ，範例程式碼即為一種實現的方法。
```cpp=
#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` 與 `!!`
```kotlin=
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 一點的寫法。
```kotlin=
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
這一題其實是個閱讀測驗，每次做一層，然後往下面填下去。請認真觀察每一個格子會貢獻他的值給下方三個格子，編號邊好沒煩惱。
```kotlin=
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 會更簡短。
```kotlin=
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 上兩點之間的路徑唯一，要快速檢查並不難的。
```cpp=
#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 下)。
```cpp=
#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 版本。
```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()}
}
```
Sign in with Wallet
Connect another wallet