Solution

A

高精度加法板子，注意$10^k$不需要使用普通的高精度乘方，可以直接求出。

B

較容易發現規律:

①當$a=0,b=0$時，顯然輸出$0$；
②當$a=0$時，我們只需要將$a$乘上一個巨大的值，將$b$除以一個巨大的值即可，代價爲$q$；
③$b=0$同理；

④當$a≠b$且$a,b≠0$時，我們需要這麼操作:
(1)使用一次操作①($x=min(a,b)$)或操作②($x=∞$)，使$a$與$b$中有一個數爲$0$；
(2)此時情況即爲前已討論過的②或③。
可以發現，此時代價爲$min(p,q)+q$，其中$min(p,q)$是將$a,b$中一個數改爲$0$的代價。

⑤當$a=b$且$a,b≠0$時，我們可以：
(1)使用一次操作①($x=a$)，即可滿足要求，代價爲$p$；
(2)操作方法與④相同，代價爲$min(p,q)+q$。
故此時代價爲$min(p,min(p,q)+q)$。

綜上所述，我們可以在$O(1)$時間複雜度內求出答案。

C

考慮，對於某一位有$x$個$0$，$y$個$1$，若$k$的該位上填$0$，則對答案的貢獻爲$y×v_i$，否則貢獻爲$x×v_i$，其中$v_i$表示第$i$位的位權。

於是，我們貪心地從高位掃到低位，嘗試讓該位等於$1$。如果可以填$1$就填$1$，否則填$0$。

但是，關注到，如果我們這麼貪心地填，可能出現到後來無論怎麼填，該值都會超過$m$的現象。於是，我們維護一個後綴和，表示從該位向後，所能得到的最小值。

for (int i=maxlen-1;i>=1;i--)  pre[i]=min(cnt[i][0],cnt[i][1])*v[i]+pre[i+1];

其中，$pre_i$表示了後綴和 (suf) ，$cnt_i$表示第$i$個二進制位上0/1出現的次數，$v_i$表示第$i$位的位權。

求出了$pre$後我們能幹什麼？可以發現，我們對於每一位，心裏都有數了。即，如果該位填了$1$，但是該位的貢獻加上後面的最小值(即$pre_{i+1}$)超過了$m$，那麼該位就絕對不能填$1$。這樣做的好處在於，不會出現後面無論如何都無法使$\sum_{i=1}^n k\ xor\ a_i≤m$，即在貪心後後悔的現象。

時間複雜度$O(n{log_2t}+m{log_2t})$，其中$t$表示$a$序列中的最大值。

D

考慮樹形$dp$。

狀態設計: $dp_{i,0}$表示，當$i$的父邊大於$i$的權值時，以$i$爲根的子樹中各邊的士兵數量之和的最大值；$dp_{i,1}$表示的唯一區別是，$i$的父邊不大於$i$的權值。

考慮神仙狀態轉移。

設$a$節點的點權爲$x$，$a$節點的孩子$son$點權爲$y$。

①已選定$a->son$邊的權值比$a$的點權大。
(1)若$x>y$，則$son$的最大貢獻爲$dp_{son,0}+m$，注意此時我們在$a->son$的邊上放了$m$個士兵，可以使答案最大化且不與條件互斥。
(2)若$x≤y$，則$son$的最大貢獻爲$max(dp_{son,0}+m,dp_{son,1}+y)$；其中$dp_{son,0}+m$與$(1)$相同，$dp_{son,1}+y$的決策中，$a->son$的邊權爲$y$。

②已選定$a->son$邊的權值不大於$a$的點權。
(1)若$x≤y$，則$son$的最大貢獻爲$dp_{son.1}+x$；
(2)若$x>y$，則$son$的最大貢獻爲$max(dp_{son,0}+x,dp_{son,1}+y)$。

於是，我們求出了，每個孩子節點對$a$的兩種貢獻(①②)。假設第一種貢獻組成的序列爲$A$，第二種貢獻組成的序列爲$B$，這兩個序列的長度都是$pos$。我們假設要讓$a$節點的$k$條子邊的權值比$a$的權值大，相當於在$A$序列中選$k$個數，在$B$序列中選$pos-k$個數，並使我們選的數之和儘可能得大。

現在思考如何快速求得這個問題。

我們先假設選了$A$序列中的所有數，現在我們要把一些選的數改成$B$序列的數。可以發現，對於一次改動，對答案的貢獻爲$B_i-A_i$，現在我們要進行最多$pos-k$次改動，使得貢獻與$A$序列中各數之和儘可能得大。

於是，我們只需要建立一個數組$C$，其中$C_i=B_i-A_i$，並在$C_i$中選擇最多$pos-k$個數使得和儘可能得大，這個和就是貢獻之和的最大值。顯然，我們直接將$C$從大到小排序，選前$pos-k$個數即可；如果目前看到的這個數已經不大於$0$了，就直接跳出回圈，否則累加。

於是，我們可以在$log_2n$的時間複雜度內進行狀態轉移。

總時間複雜度$O(nlog_2n)$。

---

幾個卡點:

①回溯時容易對當前的$A,B,C$陣列產生變動，我們要先向下遞回，然後再轉移：

for (int i=head[now];i;i=e[i].next)
	{
		if (e[i].to!=fath)  dfs(e[i].to,now);
	}
for (int i=head[now];i;i=e[i].next)
{
	轉移……
}

②邊界條件: 葉節點$l$的狀態，即$dp_{l,0}=-inf$，$dp_{l,1}=0$；之所以$dp_{l,0}=-inf$，是因爲若$l$的父邊比$l$的點權還要大，那麼$l$節點的城主就會造反。

③若當前節點$rt$的點權爲$m$，則$dp_{rt,0}$的值是$-inf$，這是因爲不可能出現$rt$的點權小於$rt$的父邊的情況。

Code

A

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

int n,x,last=10000;
int a[10005];

signed main()
{
	cin>>n>>x;
	if (n==0)  cout<<x+1<<endl;
	else if (n==1)  cout<<10+x<<endl;
	else
	{
		a[last-n]=1;
		for (rg int i=last-n+1;i<=last;++i)  a[i]=0;
		
		a[last]+=x;
		for (int i=last;i>=1;i--)
		{
			a[i-1]+=(a[i]/10);
			a[i]=a[i]%10;
		}
		int flag=0;
		for (int i=1;i<=last;i++)
		{
			if (a[i])  flag=1;
			if (flag==1)  cout<<a[i];
		}
		cout<<endl;
	}
	return 0;
}

B

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

int a,b,c,d;

signed main()
{
	cin>>a>>b>>c>>d;
	if (a==0&&b==0)  cout<<0<<endl;
	else if (a==0||b==0)  cout<<d<<endl;
	else if (a==b)  cout<<min(c,min(c,d)+d)<<endl;
	else cout<<min(c,d)+d<<endl;
	
	return 0;
}

C

#include <bits/stdc++.h>
#define int unsigned long long
#define rg register
using namespace std;
const int maxlen=51;

int n,q,m,x,pos=0,tot=0;
bool a[100005][65],ans[65];
int v[65],cnt[65][5],pre[65];

inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	
	while (ch<'0'||ch>'9')
	{
		if (ch=='-')  w=-w;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9')
	{
		s=(s<<1)+(s<<3)+(ch^'0');
		ch=getchar();
	}
	return s*w;
}

signed main()
{
	cin>>n;
	for (rg int i=1;i<=n;++i)
	{
		pos=maxlen+1;
		x=read();
		
		while (x)
		{
			a[i][--pos]=x%2;
			x/=2;
		}
	}
	v[maxlen]=1;
	for (rg int i=maxlen-1;i>=1;--i)  v[i]=v[i+1]*2;
	for (rg int i=1;i<=maxlen;++i)
	{
		for (rg int j=1;j<=n;++j)  cnt[i][0]+=a[j][i];
		cnt[i][1]=n-cnt[i][0];
	}
	pre[maxlen]=min(cnt[maxlen][0],cnt[maxlen][1]);
	for (rg int i=maxlen-1;i>=1;--i)  pre[i]=min(cnt[i][0],cnt[i][1])*v[i]+pre[i+1];
	
	cin>>q;
	while (q--)
	{
		m=read();
		int flag=1;
		for (rg int i=1;i<=maxlen;++i)
		{
			if (m>=v[i]*cnt[i][1]+pre[i+1])  ans[i]=1,m-=v[i]*cnt[i][1];
			else if (m>=v[i]*cnt[i][0]+pre[i+1])  ans[i]=0,m-=v[i]*cnt[i][0];
			else
			{
				flag=0;
				break;
			}
		}
		if (flag==0)
		{
			cout<<-1<<endl;
			continue;
		}
		tot=0;
		for (rg int i=maxlen;i>=1;--i)
		{
			tot+=v[i]*ans[i];
			pos*=2;
		}
		printf("%lld\n",tot);
	}
	return 0;
}

D

#include <bits/stdc++.h>
#define int long long
#define inf 2000000007
using namespace std;

int n,m,cnt=0;
int a[500005],head[500005],dp[500005][2],small[500005],big[500005];

struct edge
{
	int next;
	int to;
}e[1000005];

bool cmp(int x,int y)
{
	return x>y;
}

inline int up(int x,int y)
{
	if (x%y==0)  return x/y;
	else return (x/y)+1;
}

inline void add_edge(int u,int v)
{
	cnt++;
	e[cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}

inline void dfs(int now,int fath)
{
	int flag=1,pos=0,pos2=0,tot0=0,tot1=0,now0,now1;
	for (int i=head[now];i;i=e[i].next)
	{
		if (e[i].to!=fath)  dfs(e[i].to,now);
	}
	for (int i=head[now];i;i=e[i].next)
	{
		if (e[i].to!=fath)
		{
			flag=0;
			
			if (a[now]<=a[e[i].to])  small[++pos]=dp[e[i].to][1]+a[now];
			else small[++pos]=max(dp[e[i].to][0]+a[now],dp[e[i].to][1]+a[e[i].to]);
			
			if (a[now]!=m)
			{
				if (a[now]>a[e[i].to])  big[++pos2]=dp[e[i].to][0]+m;
				else big[++pos2]=max(dp[e[i].to][0]+m,dp[e[i].to][1]+a[e[i].to]);
			}
			else big[++pos2]=-inf;
			
			tot0+=small[pos];
			tot1+=small[pos];
		}
	}
	if (flag==1)
	{
		dp[now][0]=-inf,dp[now][1]=0;
		return;
	}
	if (now!=1)  now1=pos/2;
	else now1=up(pos,2ll)-1;
	now0=max(now1-1,0ll);
	for (int i=1;i<=pos;i++)  big[i]=big[i]-small[i];
	sort(big+1,big+pos+1,cmp);
	
	for (int i=1;i<=pos;i++)
	{
		if (big[i]<=0)  break;
		if (now0)  tot0+=big[i],now0--;
		if (now1)  tot1+=big[i],now1--;
	}
	dp[now][0]=tot0,dp[now][1]=tot1;
	if (pos==1)  dp[now][0]=-inf;
}

signed main()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++)  cin>>a[i];
	for (int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		add_edge(u,v);
		add_edge(v,u);
	}
	dfs(1,0);
	cout<<dp[1][1]<<endl;
	
	return 0;
}

總結

又是一場賽後諸葛亮的比賽，$D$由於時間原因程式碼沒調完，導致$323$滾粗……

唉，還是太菜了QAQ