5月27日

I'm always here if you need me.

前傳

但是 There is no time you need me.

三個人鈴聲響完挨著準(zhǔn)備進(jìn)信息教室，結(jié)果兩個人進(jìn)去之后，Mr俞把門關(guān)了，于是樊子奆就只能敲門了，關(guān)門3s后門開了，于是門上課時一直就沒關(guān)。

大掃除：

盧宇宸準(zhǔn)備去拿林燁手里的報紙：

“不行！我還要看！”

林燁可可愛愛，班長一臉無奈。

季亦貝：同學(xué)們讓一讓，人家要擦空調(diào)了。

林燁：對要擦扇貝。

我覺得我可以進(jìn)化成磕cp的人。

“是1/2吧？你們不要不說話啊，我還以為我錯了呢”

“也不要當(dāng)我是一點數(shù)學(xué)也不會啊”

歷史課下，眼保健操鈴響了，殷準(zhǔn)備去關(guān)鈴。章云皓小朋友明目張膽skip out of the front door。

“太過分了”前一秒

“你們是不是要查操啊？那快去啊”后一秒

和云再一次達(dá)成共識——單身快樂

“還有沒有什么要吐槽的?"

"蔡蔡呢"

“蔡蔡很好，蔡蔡沒什么要吐槽的”

“劉麗鈞呢？”

“小姑娘挺可愛的，就是做操不太認(rèn)真，今天早上被杜林存罵了，罵的可狠了。

CF1517E Group Photo

2500開場，美好的一天。細(xì)節(jié)好煩啊，煩的我自閉了不過完完整整做了道題

大概發(fā)現(xiàn)，一定是一段連著的，然后空一格的，最后一個（可以沒有）和前面隔很遠(yuǎn)，于是就有了分類一下前后綴種類，就有了以下五種情況，這是暴力。

		for (int i=n;i>=0 && pre[i]>suf[i+1];i--) ans++; 
		for (int i=1;i<=n;i++)
			for (int j=n;j>i;j--){
				if ((j-i-1)&1) continue;
				if (i>=2 && j<n) ans+=chk(i+1,j-1,suf[j]-2*a[n]-pre[i]+2*a[1]);//PCCC...PCPC...PPPC
				if (i>=2) ans+=chk(i+1,j-1,suf[j]-pre[i]+2*a[1]);//PCCc...PPPP
				if (j<n) ans+=chk(i+1,j-1,suf[j]-2*a[n]-pre[i]);//CCCC...PPPC
				ans+=chk(i+1,j-1,suf[j]-pre[i]); //CCC...PPP
			}

然后發(fā)現(xiàn)因為隨著j的后移，sumc會增大，所以i后移時，j一定是前移的，也就是有單調(diào)性。

所以就可以分奇偶四種情況分別做一下就好了。

#include <bits/stdc++.h>
typedef long long ll;
const int N=200005,mu=998244353;
int T,n,a[N];
ll s[N],ans,pre[N],suf[N];
int chk(int l,int r,ll sum){
	sum+=s[r]-s[l-1];
	return sum>0;
}
void solve(int L,int R,int tg1,int tg2){
	for (int i=L,j=R;i<=n;i+=2){
		ll s1=pre[i];
		if (tg1) s1-=2*a[1];
		for (;;j--){
			if (j<=i) return;
			if ((j-1-i)&1) continue;
			ll s2=suf[j];
			if (tg2) s2-=2*a[n];
			if (chk(i+1,j-1,s2-s1)) break;
		} 
		ans+=(j-i+1)/2;
	}		
}
int main(){
	scanf("%d",&T);
	while (T--){
		ans=0;
		scanf("%d",&n);
		for (int i=1;i<=n;i++) scanf("%d",&a[i]);
		for (int i=1;i<=n;i++){
			if (i>2) s[i]=s[i-2]-a[i]+a[i-1]; 
			pre[i]=pre[i-1]+a[i];
		}
		suf[n+1]=0;
		for (int i=n;i>=1;i--) suf[i]=suf[i+1]+a[i];
		//pppppcccc
		for (int i=n;i>=0 && pre[i]>suf[i+1];i--) ans++; 
		solve(2,n-1,1,1);
		solve(3,n-1,1,1);
		solve(2,n,1,0);
		solve(3,n,1,0);
		solve(1,n-1,0,1);
		solve(2,n-1,0,1);
		solve(1,n,0,0);
		solve(2,n,0,0);
		printf("%lld\n",ans%mu);
	}
} 

決策單調(diào)性，思維，細(xì)節(jié)

CF1510B Button Lock

d很小，可以暴力建一張圖，每個點向它的子集連邊。

像最小鏈覆蓋一樣，但是這里我們不止要考慮鏈的條數(shù)，還要考慮最多串中1的個數(shù)。

大概就是先假裝所有鏈頂無父親，假裝源點是父親，要暴力構(gòu)造清零 \((S,x',|s_x+1|)\) ，然后左邊一列出點，右邊一列入點，\((x,y',0)\) 表示把 \(y\) 繼承于 \(x\) 后可以省下的，\((S,x,1,0)\),\((x',T,1,0)\) 保證每個點都考慮到，最小費用最大流即可

好像就做完了，輸出方案再做一做就好了。

#include <bits/stdc++.h>
const int M=70005,N=2205,INF=1e9;
char s[N][10];
int n,m,edge,last[N],Next[M<<1],w[M<<1],to[M<<1],d[N],cnt,match[N];
int dis[N],vis[N],v[M<<1],flow[N],S,T,a[N],f[N],id[N][N];
std::queue<int> q;
void add(int x,int y,int ww,int zz){
	//printf("%d %d %d %d\n",x,y,ww,zz);
	to[++edge]=y;
	Next[edge]=last[x];
	last[x]=edge;
	w[edge]=ww;
	v[edge]=zz;
}
int c(int x){
	return (x&1)?x+1:x-1;
}
void Add(int x,int y,int ww,int zz){
	add(x,y,ww,zz);
	add(y,x,0,-zz);
}
bool chk(int x,int y){
	for (int i=0;i<m;i++)
		if (s[y][i]=='1' && s[x][i]=='0') return 0;
	return 1;
}
bool SPFA(){
	memset(dis,0x3f,sizeof(dis));
	memset(flow,0x3f,sizeof(flow));
	dis[S]=0;
	q.push(S);
	vis[S]=1;
	while (q.size()){
		int x=q.front();
		q.pop();
		vis[x]=0;
		for (int i=last[x];i;i=Next[i]){
			int u=to[i];
			if ((!w[i]) || dis[x]+v[i]>=dis[u]) continue;
			dis[u]=dis[x]+v[i];
			f[u]=i;
			flow[u]=std::min(flow[x],w[i]);
			if (!vis[u]) q.push(u),vis[u]=1;
		}
	}
	return dis[T]<INF;
}
struct Edge{
	int x,y,id;
}e[M];
int main(){
	scanf("%d%d",&m,&n);
	for (int i=1;i<=n;i++){
		scanf("%s",s[i]);
		int cnt=0;
		for (int j=0;j<m;j++)
			if (s[i][j]=='1') cnt++;
		a[i]=cnt;
	}
	S=2*n+1,T=S+1;
	for (int i=1;i<=n;i++) Add(S,i,1,0),Add(S,i+n,1,a[i]+1),Add(i+n,T,1,0);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++){
			if (i==j) continue;
			if (chk(i,j)) Add(i,j+n,1,0),e[++cnt]={i,j,edge}; 
		}
	int cost=-1;
	while (SPFA()){
		cost+=dis[T]*flow[T];
		int u=T;
		while (u!=S){
			w[f[u]]-=flow[T];
			w[c(f[u])]+=flow[T];
			u=to[c(f[u])];
		}
	}
	printf("%d\n",cost);
	for (int i=1;i<=cnt;i++)
		if (w[e[i].id]){
			match[e[i].y]=e[i].x;
			d[e[i].x]++;
		}
	int tg=0;
	for (int i=1;i<=n;i++){
		if (d[i]) continue;
		if (tg) printf("%c ",'R');
		tg=1;
		int u=i;
		for (int j=0;j<m;j++) if (s[u][j]=='1') printf("%d ",j);
		while (match[u]){
			int v=match[u];
			for (int j=0;j<m;j++)
				if (s[v][j]=='1' && s[u][j]=='0') printf("%d ",j);
			u=v;
		}
	}
}

網(wǎng)絡(luò)流

逐漸因懶于看題解而學(xué)會自己做題

CF1521E Nastia and a Beautiful Matrix

想了一下。

下界，肯定就是四個都填三個，角的地方頂上。

上界，直接一行空一行，答案一定是 \(\sqrt n\) 級別的。

有一種感覺，是先隔行填了，然后，選不相同的填上去，只要不沖突即可達(dá)到下界。那么一定是先眾數(shù)全填，別的數(shù)填完，然后去補(bǔ)眾數(shù)下面的，也就是如果眾數(shù) \(x \le 2(n-x)\) 那么就做完了。

有點問題，其他數(shù)填到最后會崩。那就不要隔行，先四個格子填一個，填滿一遍在每個格子填第二個，就行了，這樣就不會崩了。

如果 大于 的話。那也做完了？每四個格子最多兩個眾數(shù)，眾數(shù)填完別的隨便填就好了。

想不清楚 我們來找一個短一點的 題解 瞧一瞧

查了半天錯回去發(fā)現(xiàn)掉落re...原來數(shù)組開小了

#include <bits/stdc++.h>
int T,n,m,a[100005];
int c[600][600],ans;
void solve(int t1,int t2,int x,int &mx){//填眾數(shù)，盡量使接下來的數(shù)不會沖突，也就是剩下非對角線
	if (!mx) return;
	for (int i=t1;i<=ans;i+=2)
		for (int j=t2;j<=ans;j+=2){
			c[i][j]=x,mx--;	
			if (!mx) return;
		}
}
void solve2(int t1,int t2,int &p){//按不同格依次填，保證不會沖突
	for (int i=t1;i<=ans;i+=2)
		for (int j=t2;j<=ans;j+=2){
			if (c[i][j]) continue;
			while (p<=m && (!a[p])) p++;
			if (p>m) return;
			c[i][j]=p;
			a[p]--;
		}
}
int main(){
	scanf("%d",&T);
	while (T--){
		scanf("%d%d",&n,&m);
		int mx=0,x=0;
		for (int i=1;i<=m;i++){
			scanf("%d",&a[i]);
			if (a[i]>mx) mx=a[i],x=i; 
		}
		int L=(int)sqrt(n),R=(int)sqrt(n*2)+1;
		while (L<=R){
			int mid=(L+R)>>1,s,s2;
			if (mid&1) s=(mid-1)*(mid-1)/4*3+mid+mid-1;
			else s=mid*mid/4*3;
			s2=((mid+1)/2)*mid;
			if (s>=n && s2>=mx) ans=mid,R=mid-1;
			else L=mid+1; 
		}
		printf("%d\n",ans);
		for (int i=1;i<=ans;i++)
			for (int j=1;j<=ans;j++) c[i][j]=0;
		solve(1,2,x,mx);
		solve(1,1,x,mx);
		a[x]=0;
		int p=1;
		solve2(1,2,p);
		solve2(1,1,p);
		solve2(2,1,p);
		for (int i=1;i<=ans;i++,puts(""))
			for (int j=1;j<=ans;j++) printf("%d ",c[i][j]);
	}
}

CF1442D Sum

2800沖沖沖！

PA: 2800以上的就不要去做了。于是每日計劃2500+2600+2700+2800 的快樂生活開始了。

堆？凸包？背包？...題解！

我們來思考一個問題，如果你當(dāng)前選了一個你不想選的，那一定是因為后面有一個值得選的，那如果后面值得選了，那因為不降，后面那一連串都值得，感性理解，一個數(shù)組會被全選完。最多會有一個因 \(k\) 的限制而無法選到。還是題解比較理性一點。

問題轉(zhuǎn)化，對于全選的數(shù)組，一定按總和與個數(shù)的比擇優(yōu)選擇。

所以枚舉最后那個數(shù)組，把別的排個序，掃一遍取前多少個？

發(fā)現(xiàn)他wa了，感覺這個思路不太行，需要用到背包，又是一個缺一背包，可以用分治來做。

但是開始想一個問題，如果這個東西沒有選完，那排序后比他小的還會被完全選嗎？當(dāng)然會，所以乖乖地明天早上來寫分治吧！沖題量失敗。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=3005;
int n,k,siz[N],cnt;
ll dp[N],ans,tmp[20][N];
vector<int> a[N]; 
struct point{
	ll x;
	int v;
}b[N];
void upd(int x,ll y){
	for (int i=k;i>=x;i--)
		dp[i]=std::max(dp[i-x]+y,dp[i]);
}
void solve(int L,int R){
	if (L==R){
		ll sum=0;
		for (int i=1;i<=siz[L] && i<=k;i++){
			sum=sum+a[L][i-1];
			ans=std::max(ans,sum+dp[k-i]);
        }
		return;
	}
	int now=++cnt;
	memcpy(tmp[now],dp,sizeof(dp));
	int mid=(L+R)>>1; 
	for (int i=mid+1;i<=R;i++)
		upd(b[i].v,b[i].x);
	solve(L,mid);
	memcpy(dp,tmp[now],sizeof(dp));
	for (int i=L;i<=mid;i++)
		upd(b[i].v,b[i].x);
	solve(mid+1,R);
	memcpy(dp,tmp[now],sizeof(dp));
	cnt--; 
}
int main(){
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++){
		ll sum=0;
		scanf("%d",&siz[i]);
		a[i].resize(siz[i]);
		for (int j=0;j<siz[i];j++)
			scanf("%d",&a[i][j]),sum+=a[i][j];
		b[i]={sum,siz[i]};
	}
	solve(1,n);
	printf("%lld\n",ans);
}

分治，dp，結(jié)論

1-mid的悲劇....