网址：代码部落

一： 相濡以沫 β（代码请自写）

        签到题，如果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;
}