前言

人已经麻了。

正题

T1： 有点难想到，但其实就用二维偏序，树状数组即可。

思路：枚举两个点对，先枚举右下的点，再在树状数组中找到在它左上方的符合条件的点。

条件就是：两个点的前后缀和之差为\(k\)。这个可以自己画图得出。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k;
const int N=100005;
const int M=103;
int f[N][M],g[N][M];
long long a[N][M],cnt,ans;
struct BIT
{
	int v[M];
	void modify(int x)
	{
		if (!x) ++v[0]; 
		for (;x<M && x;x+=x&-x) ++v[x];
	}
	int query(int x)
	{
		int res=0;
		for (;x;x-=x&-x) res+=v[x];
		return res+v[0];
	}
} s[N*3];
signed main(){
	cin>>n>>m>>k;
	char tmp[110];
	for(int i=1;i<=n;i++){
		scanf("%s",tmp+1);
		for(int j=1;j<=m;j++){
			if(tmp[j]=='$'){
				f[i][j]=1;
				g[i][j]=1;
				cnt++;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+f[i][j];
		}
	}
	for(int i=n;i>=1;i--){
		for(int j=m;j>=1;j--){
			g[i][j]=g[i+1][j]+g[i][j+1]-g[i+1][j+1]+g[i][j];
		}
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			a[i][j]=f[i][j]-g[i+1][j+1];
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=0;j<=m;j++){
			s[a[i-1][j]+2*cnt].modify(j);//把上面的点压入
		}
		for(int j=1;j<=m;j++){
			ans+=(long long)s[a[i][j]-k+2*cnt].query(j-1);//查寻
		}
	}
	cout<<ans<<endl;
	return 0;
}

T2：

一道期望题，蒟蒻根本不会。

\(O(n^2)\)做法，模拟每一轮，把自己的球平均分给其他人。

\(O(n)\)做法，模拟每一轮，记录一个全局的tag，看对全局的奉献。每一次的给球都要加上tag再算，注意开long long

#include<bits/stdc++.h>
#define int  long long
using namespace std;
const int mod=998244353;
int fast_pow(int x,int y){
	int res=1;
	while(y){
		if(y&1){
			res=res*x%mod;
		}
		x*=x;
		x%=mod;
		y>>=1;
	}
	return res;
}
int n,tag;
int a[1000001];
int A(int &a,int b){
	return (a+=b)>=mod?a-=mod:a;
}
int Dec(int &a,int b){
	return (a-=b)<0?a+=mod:a;
}
int get(int x){
	return a[x]+tag;
}
signed main(){
	cin>>n;
	int Mod=fast_pow(n-1,mod-2);
	//cout<<Mod<<endl;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		int tmp=get(i)*Mod%mod;
		Dec(a[i],get(i));//变成-tag
		Dec(a[i],tmp);//变成新的-tag
		A(tag,tmp);//更新tag
	}
	for(int i=1;i<=n;i++){
		cout<<(a[i]+tag)%mod<<' ';
	}
	
	return 0;
}

T3：

一道很妙的题。

常规做法是枚举\(k\)的大小然后\(bfs\)删点，但是每一次删点都要重新统计连通性，所以太麻烦了。

正解是记录删点的顺序后，倒过来加点，再用并差集记录连通性，同时维护联通块的信息。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Maxn=1100000;
const ll Inf_ll=0x3f3f3f3f3f3f3f;
vector<int>g[Maxn],q[Maxn];
int deg[Maxn];
int v[Maxn],e[Maxn],d[Maxn],fa[Maxn];
bool nice[Maxn];
int n,m;
int N,M,B;

int find_fa(int x){
	if(fa[x]==x){
		return x;
	}
	return fa[x]=find_fa(fa[x]);
}

void merge(int x,int y){
	int fa_x=find_fa(x);
	int fa_y=find_fa(y);
	e[fa_x]++;
	if(fa_x==fa_y){
		return ;
	}
	fa[fa_y]=fa_x;
	e[fa_x]+=e[fa_y];
	v[fa_x]+=v[fa_y];
	d[fa_x]+=d[fa_y];
}

ll calc(int x){
	x=find_fa(x);
	return 1ll*M*e[x]-1ll*N*v[x]+1ll*B*(d[x]-(e[x]<<1));
}
int main(){
	scanf("%d%d",&n,&m);
	scanf("%d %d %d",&M,&N,&B);
	ll ans=-Inf_ll;
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		u--,v--;
		g[u].push_back(v);
		g[v].push_back(u);
		deg[u]++;
		deg[v]++;
	}
	for(int i=0;i<n;i++){
		fa[i]=i;
		d[i]=deg[i];
		v[i]=1;
		q[d[i]].push_back(i);
	}
	for(int i=0;i<n;i++){
		int len=0;
		for(int j=0;j<q[i].size();j++){
			int u=q[i][j];
			if(deg[u]==-1){
				continue;
			}
			q[i][len++]=u;
			deg[u]=-1;
			for(int k=0;k<g[u].size();k++){
				int v=g[u][k];
				if(deg[v]!=-1){
					deg[v]--;
					q[max(i,deg[v])].push_back(v);
				}
			}
		}
		q[i].resize(len);
	}
	
	int res=1;
	for(int i=n-1;i>0;i--){
		for(auto u:q[i]){
			nice[u]=1;
			for(auto v:g[u]){
				if(nice[v]){
					merge(u,v);
				}
			}
		}
		for(auto u:q[i]){
			ll v=calc(u);
			if(v>ans){
				ans=v;
				res=i;
			}
		}
	}
	printf("%d %lld",res,ans);
	return 0;
}

T4 ：

想骗分，但失败了。