5月25日

CF1430F Realistic Gameplay

山風好評，真涼快。合唱隊的衣服好評，zyn小西裝真好看。貪心題。

首先對于某一波怪物，要不換一次彈，打滿 \([l,r]\)，要么不換彈隨便打 \((r-l) \times k<a[i]\) ，要么介于兩個中間

先想的是dp[i]表示當前還剩i顆子彈，然后每次要不連著打要不新浪費一次彈。

后來想到不用那么多狀態，只要記dp[i]表示最后一次浪費在哪個前面，應該也能過了，詳見 Thaumaturge

然后想到可以貪心，如果下面連著的一段怪物不需要換彈，那么一定不換更優（因為要換了后面還有空隙可以換），所以就可以先算出某一段開頭處（不一定是一個），所需最小起始子彈就可以不換彈，這個從后往前推一下就好了，盡量放在后面打，因為如果 \(r_{i-1}==l_i\) 的地方可以留給上一段用，每次不僅考慮自己，還要考慮 \(r_i\) 處要留多少給下一波。然后從前往后貪一遍什么時候換彈，一定換才換。

#include <bits/stdc++.h>
typedef long long ll;
const int N=2005;
int n,k,l[N],r[N],a[N];
ll ans,dp[N];
int main(){
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++)
		scanf("%d%d%d",&l[i],&r[i],&a[i]),ans+=a[i];
	for (int i=n;i>=1;i--){
		dp[i]=(r[i]==l[i+1]?dp[i+1]:0);
		if ((ll)(r[i]-l[i]+1)*k<a[i]+dp[i])
			return puts("-1"),0;
		dp[i]=dp[i]+a[i]-(ll)(r[i]-l[i])*k;
		if (dp[i]<0) dp[i]=0;
	}
	ll res=0;
	for (int i=1;i<=n;i++){
		if (res<dp[i]){
			ans+=res;
			res=k;
		}
		res=(res-a[i])%k;
		res=(res+k)%k;
	}
	printf("%lld\n",ans);
} 

CF1425I Impressive Harvesting of The Orchard

根號分治+吉老師線段樹

有點困，看了一眼題解是根號分治以為按子樹大小分治，想了半天想不出發現是按 \(a_i\) 分治。

對于大于根號的，直接dfs記錄父親節點被采集的時間點，每次 \(+a_i\) 二分到下一次被采集，算答案。

對于小于根號的，枚舉一下不同的 \(a_i\) ，分別建一棵線段樹。對于每一次詢問，只對 \(\le T\) 的有關系，答案即為 \(\le T\) 的個數和深度和，然后再講所有 \(\le T\) 的數賦值為 \(T+a_i\)。聽說這個東西可以用吉老師線段樹做，這個東西可以參考吉老師的課件

突然去看了一眼記錄，看起來寫nq比較靠譜，不想寫了怎么辦啊。算了算了還是先不寫了

SOJ1281 簡

相同長度的鏈一樣，鏈長共6中，記搜+容斥

soj1282 單

3*n網格圖最短路求和，分治+dp+二維數點

CF1251D Nastia Plays with a Tree

又到了 水題量的夜晚時刻了！

首先肯定找一個度數為1的點當鏈頂，然后，度數>2的是肯定要斷掉某些邊的，感覺是只要優先斷兩邊度數都>2的，然后挑一個子樹的葉子節點連到某一個葉子就好了，不知道對不對，我去看題解了。

感覺題解不太符合我的想法（什么鬼話）？還是自己寫一發好了，發現連邊不用再刪邊時處理，最后隨便首尾相連就好了

沖題量失敗了，有點問題，完善一下，像樹形dp一樣先把下面做完，如果有兩條鏈就并起來，斷掉x和fa的邊，而那些多于兩條邊的也要斷掉。

#include <bits/stdc++.h>
const int N=200005;
int n,d[N],last[N],Next[N<<1],to[N<<1],edge,f[N],use[N],ans;
int son1[N],son2[N];
int T,x,y;
struct Edge{
	int x,y;
}a[N]; 
void clear(){
	for (int i=1;i<=n;i++) d[i]=0,last[i]=0,son1[i]=son2[i]=0;
	edge=0;
}
void add(int x,int y){
	to[++edge]=y;
	Next[edge]=last[x];
	last[x]=edge;
}
void dfs(int x,int y){//x/y表示和父親有沒有邊 
	f[x]=y;
	int tg1=0,tg2=0;
	for (int i=last[x];i;i=Next[i]){
		int u=to[i];
		if (u==y) continue;
		dfs(u,x);
		if (!use[u]) continue;
		if (!tg1) tg1=u;
		else if (!tg2) tg2=u;
		else{
			use[u]=0,ans++;
			son2[u]=u;
		}
	}
	if (tg1 && tg2){
		son1[x]=son1[tg1];
		son2[x]=son1[tg2];
		use[x]=0;
		if (x!=1) ans++;
	}else if (tg1) son1[x]=son1[tg1],use[x]=1;
	else son1[x]=x,use[x]=1;
}
int main(){
	scanf("%d",&T);
	while (T--){
		clear();
		scanf("%d",&n);
		for (int i=1;i<n;i++){
			scanf("%d%d",&x,&y);
			add(x,y),add(y,x);
			d[x]++,d[y]++; 
		} 
		ans=0;
		dfs(1,0);
		printf("%d\n",ans);
		int lst=son1[1];
		for (int i=2;i<=n;i++)
			if (!use[i]){
				printf("%d %d %d %d\n",i,f[i],lst,son1[i]);
				if (!son2[i]) lst=i;
				else lst=son2[i];
			}
		lst=son1[1];
	
	}
}