網址：代碼部落

一：?相濡以沫 β（代碼請自寫）

? ? ? ? 簽到題，如果a[i]<=a[i+1]? a[i]=a[i+1],反之，直接輸出No

二? ?共同富裕（代碼請自寫）

? ? ? ?簽到題，用sort+前綴和? ?如果最富有的個?的平均值都?于 x的話, ?數就不能滿?,(把富有的?換成不富有的 ?,平均值只會縮?) 我們將數組從?到?排序,依次判斷前 i富有的?的均值滿不滿?即可。

? ? ? ? 注：開 long long ！開 long long ！開 long long ！

三??序列消消樂

? ? ? ? 思路：如果數據有解，2~n必定存在一個等號'='，刪除它后，剩余的序列可以按照給定邏輯反復處理，將問題轉化為線性轉移。令dp[i]表示前i個數是否都能被刪除。顯然，只有當存在一個j使得f[j]=1且aj+1=ai時，我們才能選擇兩個數aj+1和ai來刪除范圍內的所有數，從而使得dp[i]=1。時間復雜度為O(n^2)，可以獲得60分。

????????優化上述邏輯,能否根據aj+1=ai=x?這個數值直接判斷前? 1~j能否刪除,從?減少內層for循環 考慮維護?個 vis數組, vis[x]=1表示數值 x前?的數都能被刪除，當 a[i]=x如果vis[x]=1 ,即可得出f[i]=1 如果 f[i-1]=1,可得出vis[x]=1;

? ? ? ? 代碼

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int t,n,m,a[N];
int b[N],sum;
void check(){for(int i=1;i<=n;i++){if(b[i]>=1ll*m*(n-i+1)){cout<<n-i+1<<endl;return ;}}cout<<0<<endl;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>t;while(t--){cin>>n>>m;memset(b,0,sizeof(b));for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);for(int i=n;i>=1;i--) b[i]=b[i+1]+a[i];check();}return 0;
}

四?黑白翻轉

? ? ? ? 思路：?先翻轉是以?為單位的,我們可以想到????的線性轉移 設狀態 fi為前i的"獨特性"總和的最?值 考慮 fi和fi-1?之間?法轉移 因為我們不清楚地i?的狀態,不清楚第i-1?的狀態 同樣要計算fi也需要知道i+1?的狀態 所以我們豐富下狀態fi,a,b,c 表示第i-1,i,i+1?這三?的翻轉狀態分別為a,b,c (0表示不翻轉, 1表示翻轉) 的情況下, 前i?的"獨特性"總和的最?值 同時定義gi,a,b,c?表示第i-1,i,i+1 這三?的翻轉狀態分別為a,b,c的情況下, 第i ?每個?格數 的"獨特性"總和. 這個可以直接在原圖的基礎上以 O(n)的時間復雜度直接計算出來. 最后可得狀態轉移?程為:

????????fi,a,b,c = max?(d=0,d=1) fi-1,d,a,b+gi,a,b,c

代碼：

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m,d[N][N],dp[N][3][3][3];
int check(int x,int y,int a,int b,int c){int t=0;if(y-1>=1){t+=(d[x][y]!=d[x][y-1]);}if(y+1<=m){t+=(d[x][y]!=d[x][y+1]);}if(x-1>=1){t+=((d[x][y]^b)!=(d[x-1][y]^a));}if(x+1<=n){t+=((d[x][y]^b)!=(d[x+1][y]^c));} return t*t*t;
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%1d",&d[i][j]);}}for(int i=1;i<=n;i++){for(int a=0;a<=1;a++){for(int b=0;b<=1;b++){for(int c=0;c<=1;c++){for(int d=0;d<=1;d++){dp[i][a][b][c]=max(dp[i][a][b][c],dp[i-1][d][a][b]);}for(int j=1;j<=m;j++){dp[i][a][b][c]+=check(i,j,a,b,c); }}}}	}int maxx=0;for(int a=0;a<=1;a++){for(int b=0;b<=1;b++){for(int c=0;c<=1;c++){maxx=max(maxx,dp[n][a][b][c]);}}}printf("%d",maxx);return 0;
}