比賽傳送門
作者： fn

簽到題

H題 War of Inazuma (Easy Version) / 稻生之戰(簡易版)

題目大意
給n維超立方體染色，使每個頂點相鄰的點中，和這個頂點顏色相同的不超過 ? n ? \lceil \sqrt{n}\rceil ?n ?? 個，

考察內容
貪心

分析
貪心策略，第一個標記為0，之后每次在之前的基礎上每位取反，然后加到末尾即可，

#include<bits/stdc++.h> // H
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
using namespace std;
const int N=1e7+10;
ll n,m,a[N];

int main(){ 
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n;
	
	ll len=pow(2,n);  
	
	a[0]=0;
	int pos=1;
	for(int i=0;i<n;i++){
		ll num=pow(2,i);
		for(int j=1;j<=num;j++){
			a[pos]=1-a[pos-num];
			pos++;
		}
	}
	
	for(int i=0;i<len;i++){
		cout<<a[i];
	}
	cout<<endl;

	return 0;
}

進階題

F題 Train Wreck / 失事列車

題目大意
舊火車站只有一條帶有死胡同的軌道，它就像一個堆疊:每次你要么把一輛火車推入車站，要么把最近添加的火車彈出車站，

每天有n列火車進站出站， 檢查員已經決定了今天的“推”和“彈出”的順序，

設計一個方案，讓每次進堆疊后的序列都不同，

輸出一個解決方案，不可能時輸出"NO" ，

考察內容
貪心，樹的遍歷，優先佇列

分析
將堆疊操作視為樹，要求轉化為給每一個節點染色，使得從根到每一個節點的鏈所構成的顏色序列兩兩不同，
注意到兩個都在第 i 層的節點，如果它們的父親不同，則從根到它們父親的鏈所構成的顏色序列不同，這使得從根到它們的鏈所構成的顏色序列一定不同，（因為刪去序列最后一項后得到的序列不同）因此，條件可以轉化為每個點的各個兒子顏色互不相同，
對于一個節點，假設其有 k k k 個兒子，我們選取剩余火車數最多的 k k k 個顏色對應上去，可以用優先佇列實作，

#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
const int M=2e6+9;
int n,m,id;
char c[M];
int b[M],a[M],t[M],co[M];
vector<int>g[M];
void push(int x,int y){
	for(t[x+=n-1]=y;x;x>>=1)t[x>>1]=b[t[x]]>b[t[x^1]]?t[x]:t[x^1];
}
void dfs(int u){
	for(auto v:g[u]){
		co[v]=t[1];
		b[t[1]]--;
		if(b[t[1]]<0){
			puts("NO");
			exit(0);
		}
		push(co[v],0);
	}
	for(auto v:g[u]){
		push(co[v],co[v]);
	}
	for(auto v:g[u])dfs(v);
}
void out(int u){
	if(u)printf("%d ",co[u]);
	for(auto v:g[u])out(v);
}
int main(){
	scanf("%d%s",&n,c+1);
	for(int i=1;i<=n*2;++i){
		if(c[i]=='(')a[++m]=++id,g[a[m-1]].eb(a[m]);
		else m--;
	}
	for(int i=1,x;i<=n;++i)scanf("%d",&x),b[x]++,push(x,x);
	dfs(0);
	puts("YES");
	out(0);
	puts("");
	return 0;
}

A題 Browser Games / 瀏覽器游戲

題目大意

在即將到來的n天里，將在一個網站上發布n個瀏覽器游戲，每天發布一個新游戲，用戶必須打開相應的URL才能下載游戲，

然而，一旦用戶以某種方式找到一個未發布游戲的URL，游戲的資料就會泄露出去，為了暫時解決這個問題，管理員決定在服務器端添加一系列非空字串作為確認前綴，當請求的URL確實對應于一個游戲（無論是否發布），并且至少有一個確認前綴是該URL的前綴時，服務器將回應正確的游戲資料；否則，服務器將宣告沒有找到該游戲，

輸出每次新游戲發布后，服務器所需的最小確認前綴數量，

注：記憶體限制32mb

樣例輸入

3
ufoipv.ofu
hsbocmvfgboubtz.kq
hfotijo.njipzp.dpn/kb

樣例輸出

1
2
2 

樣例解釋

-在第一天，使用 “ufoipv.ofu” 作為URL的游戲已經發布，而其他兩款游戲應該是不可用的， 因此，以“u”作為唯一的確認前綴是充分的，

-在第二天，用“u”和“hs”作為確認前綴就足夠了， 請注意，以“u”和“h”作為確認前綴是不可行的，這可能導致使用 “hfotijo.njipzp.dpn/kb” 作為URL的游戲資料泄露，

-在最后一天，三款游戲全部發布， 因此，用“u”和“h”作為確認前綴就足夠了， 注意，不允許使用空字串作為唯一的確認前綴，因為確認前綴應該是非空的，

考察內容
字典樹（trie），字串，空間復雜度優化

分析
加強自 2020 年 ICPC 銀川賽區 K 題，
首先我們不考慮空間限制，先對所有字串建立一棵字典樹，并將每個串對應字典樹上的節點標為黑點，每次操作會將一個黑點變為白點，目標是將盡可能少的非根節點標紅使得任意一個白點到根的路徑上都有被標紅的節點，且任意一個黑點到根的路徑上都沒有被標紅的節點，
我們記錄下每個點的子樹里有多少個黑點，每次有一個黑點變為白點的時候，首先標紅這個白點，然后我們將所有的紅色標記盡可能往上推就能得到最少被標紅的節點數，

為了優化空間，我們觀察到字串只有 n 個，比字典樹的節點數少一個串長的系數，如果我們能縮掉只有一個兒子的非關鍵點，只保留 n 個關鍵點以及字典樹上的分叉節點，就能得到只有 O ( n ) O(n) O(n) 個節點的經過壓縮的字典樹，從而通過此題，
我們考慮自頂向下地遞回構建這棵樹，并且在構建的程序中對 n 個字串進行排序，當我們位于某個節點時，維護節點的深度資訊，以及當前節點的子樹中的字串，注意到在對所有字串排序之后，這些字串的下標會構成一個區間，我們可以通過深度資訊得到這些字串對應位置的字符，并使用桶排序完成對區間的劃分，如果能劃分出多個區間則遞回下去構建各個子樹，否則不需要新建節點，當某個節點只剩一個串時即可退出遞回程序，

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
string s[N];
int id[N],ans[N],n;
bool cmp(int a,int b) {return s[a]<s[b];}
void dfs(int l,int r,int x,int k)
{
    if  (l==r)  return;
    int maxx=0,i,j;
    for(i=l,j=l; i<=r; i++)
    {
        maxx=max(maxx,id[i]);
        if(i==r||s[id[i]][k]!=s[id[i+1]][k])
        {
            ans[maxx]++,ans[x]--;
            dfs(j,i,maxx,k+1);
            j=i+1,maxx=0;
        }
    }
}
int main()
{
    cin>>n;
    for (int i=1; i<=n; i++)
        cin>>s[i],id[i]=i;
    if (n==1) {cout<<1<<endl; return 0;}
    sort(id+1,id+1+n,cmp);
    dfs(1,n,n+1,0);
    for (int i=1; i<=n; i++)
        ans[i]=ans[i-1]+ans[i],cout<<ans[i]<<endl;
    return 0;
}