{%hackmd @lumynou5/dark-theme %}
# 113成大資工特殊選才甲組
<font size=5>**內文所有資料皆非官方 解為我個人寫出 不保證正確性**</font>
<font size=4>**喔然後 成大的機器#pragma沒用喔**</font>
## 前言
我不是這年的 純粹解好玩w
[題目](https://hackmd.io/4B_8QdOJRU2V5BUW3NlbZw?both)(今年考生自己記的)
總榜(今年考生自行截圖 非我本人放出)
## pA
### 題敘
有$n$點$m$邊和$k$個特殊點 問所有特殊點和滿足(對某個特殊點 他是唯一的最近點)的點有幾個
### 輸入
輸入第一行$n$ $m$ $k$
後接$m$行 每行三個整數$x$ $y$ $w_i$
最後一行$k$個數$s_i$ 代表特殊點
$2\leq k\leq n\leq2\times 10^5$
$1\leq m\leq min(2\times 10^5,\frac{n(n-1)}2)$
$1\leq x,y\leq n,x\ne y$
$1\leq s_i\leq n,s_i\neq s_j,i\neq j$
$1\leq w_i\leq 10^9$
### 輸出
一數為總數
### 解
可以發現 因為特殊點是最後給 所以最簡單只能儲存每個點的最近點 再看一遍所有特殊點
code如下 時間複雜度最佳\=平均\=最差$O(n+m)$ 空間$O(n)$
如果先給特殊點 可以做一次離散化再做儲存 會把$n$降到$k$ 但本題$k$可能會到$n$ 就沒寫code
時間複雜度最佳\=平均\=最差$O(k+m)$ 空間$O(k)$
:::spoiler code

#include <stdio.h>
int a[200005][2]={0},n,m,k,i=0,x,y,w;
int main(){
    for(scanf("%d%d%d",&n,&m,&k);i<m;++i){
        scanf("%d%d%d",&x,&y,&w);
        if(a[x][1]==w)a[x][0]=-1;
        if(!a[x][0]||a[x][1]>w)a[x][0]=y,a[x][1]=w;
        if(a[y][1]==w)a[y][0]=-1;
        if(!a[y][0]||a[y][1]>w)a[y][0]=x,a[y][1]=w;
    }
    for(i=0;i<k;++i)scanf("%d",&x),a[x][1]=-1,a[x][0]!=-1&&(a[a[x][0]][1]=-1);
    for(i=1,k=0;i<=n;++i)if(a[i][1]<0)++k;
    printf("%d",k);
}

:::
## pB
### 題敘
兩個陣列A,B 長度皆為$\frac n2$ merge成C 滿足C是一個n permutation
其中A可能有一數被錯誤的放到前面 其他不變
### 輸入
第一行一數n
第二行n個數代表C的每一項
### 輸出
若沒錯 輸出"no"
有錯則輸出"yes" 並輸出一行字典序最小的A和一行最大的A
:::spoiler Chung教授的慘案
:::
$n為偶數且4\leq n\leq2\times10^5$
### 解
讀取同時找逆序是誰(記為$l,r$ $l\gt r$)
字典序小比較簡單 按照$[1,r)\cup \{l\}\cup \{r\}\cup (r,n]-\{l\}$的順序取到$\frac n2$個就好
字典序大分段看數量
用不到陣列

時間複雜度最佳\=平均\=最差$O(n/2)$ 空間$O(1)$
這題原本$1sec$ $n\leq10^6$ 一定要io優化才過 後來賽前改成$1.5sec$ $2\times 10^5$
結果居然有人io優化+vector+輸出時排序一次還能過
:::spoiler code

#include <stdio.h>
#define N 1<<26
char buf[N],*p1=buf,*p2=buf;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++)
int gi(){
	int n=0;char c;
	for(;(c=gc())<='9'&&'0'<=c;n+=c-'0')n*=10;
	return n;
}
char buf2[N],*pp=buf2;
void pc(const char c){
    if(pp-buf2==N)fputs(buf2,stdout),pp=buf2;
    *pp++=c;
}
void pi(int n){
	long long i=1;
	for(;n>=i;)i*=10;
	for(i/=10;i;i/=10)pc('0'+((n/i)%10));
}
int main(){
    int n,i=1,j,l=0,r;
    for(n=gi(),r=gi();i<n&&l<r;++i,r=gi())l=r;
    if(l<r)puts("no");
    else{
        puts("yes");
        /*字典序小的*/
        for(n>>=1,j=2,i=1;i<r&&j<n;++i,++j){pi(i);pc(' ');}
    	pi(l);pc(' ');pi(r);
        for(++i;i<n<<1&&j<n;++i){
            if(i==l)continue;
            pc(' ');pi(i);
            ++j;
        }
        pc('\n');
        /*字典序大的*/
        if(r<=n+1){//只要先放l,r 後面倒著回來夠放
        	pi(l);pc(' ');pi(r);
        	for(i=n+2+!!(l<=n+2);i<=n<<1;++i){
        		if(i==l)continue;
        		pc(' ');pi(i);
        	}
        }
        else{//需要從前面補幾項 後面一路順著輸出
        	for(i=n+1;i<r;++i)pi(i),pc(' ');
        	pi(l);pc(' ');pi(r);
        	for(i=r+1;i<=n<<1;++i){
        		if(i==l)continue;
        		pc(' ');pi(i);
        	}
        }
    }
    fputs(buf2,stdout);
    return 0;
}

:::
## pC
### 題敘
觀察+dp題 測題的時候一直被唬爛解過 後來測資加強度 最終解應該差不多是預期解
code後補
<!--
### 輸入
### 輸出
### 解
#### code
-->
## pD
### 題敘
多重背包 不過是好幾個背包那種 不想寫:/
<!--
### 輸入
### 輸出
### 解
#### code
-->
## pE
### 題敘
CF3000題 等我打到3000再說 而且這題沒有子題分 大家一致地跳過他了
<!--
### 輸入
### 輸出
### 解
#### code
-->