ABC 262

D （简单dp）

题意

给定一个数组，问有多少个子数组，它的元素平均数为整数。即该子数组和能被子数组大小k整除

思路

因为数据范围只有100，所以暴力dp就行。

代码

int n,m;
int f[110][110][110];
//f[i][j][k]表示选i个数，当前选了j个数，和余i为K 的方案数
int a[110];
void solve() 
{	
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) f[i][0][0]=1;//初始化
	for(int u=1;u<=n;u++) //枚举选的个数
	{
		for(int i=1;i<=n;i++) //每次加一个新的数更新数据
		{	
			for(int j=u;j>=1;j--)//倒过来省一维
			{	
				int x=a[i]%u;
				for(int k=u-1;k>=0;k--) //这里正反遍历都可以
				{	
					f[u][j][k]+=f[u][j-1][(k-x+u)%u];
					f[u][j][k]%=mod; 
				}
			}
		}
	}
	int ans=0;
	for(int u=1;u<=n;u++) 
	{
		ans+=f[u][u][0];
		ans%=mod;//一开始忘了，直接wa了10个点
	}
	cout<<ans<<endl;
}

E

题意

一个n个点m条边的无向图，要求将k个点染成红色，其他的点染成蓝色，使得图中有偶数条边连接不同颜色的点，求方案数。

思路

考虑度数，假设红点的度数总和为S, 两端是红点的边的数量为C,两端不同颜色的边数量为D，则\(S=2C+D\) .因为题目要求D为偶数，则S也为偶数，则问题变成，从图中选择K个点，它们的度数和为偶数。

将点分为奇度数点和偶度数点，则变成了组合数学的问题。
奇度数点肯定要选偶数个，剩下的点都选偶度数点。

代码

int n,m,k;
int d[N];
int fac[N],inv[N];


int q_pow(int a,int b) //快速幂求逆元
{	
	int res=1;
	while(b) 
	{
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b/=2; 
	}
	return res;
}

void init() //预处理阶乘和逆元
{
	fac[0]=1;
	inv[0]=1;
	for(int i=1;i<N;i++) 
	{
		fac[i]=fac[i-1]*i%mod;
		inv[i]=q_pow(fac[i],mod-2);
	}
}

int cal(int n,int m) 
{
	return fac[n]*inv[n-m]%mod*inv[m]%mod;
}

void solve() 
{
	memset(h,-1,sizeof(h));
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++) 
	{
		int a,b;
		cin>>a>>b;
		d[a]++,d[b]++;
	}
	int odd=0,even=0;
	for(int i=1;i<=n;i++) if(d[i]&1) odd++;
	even=n-odd;
	int ans=0;
	for(int i=0;i<=k;i+=2) 
	{	
		if(i<=odd&&k-i<=even) ans+=cal(odd,i)*cal(even,k-i)%mod;
		ans%=mod;
	}
	cout<<ans<<endl;
}

F (单调栈)

题意

给定一个n的全排列，可以执行0到K次操作，使得排列字典序最小
操作1：删除任意一个数
操作2：将最后的元素放到开头。（即所有元素向右旋转一次）

思路

如果只是操作1，那就是经典的单调栈。（止步于此，还是看看远方的题解吧）
对于操作2，如果要旋转，应该先把最小的数放到开头，因为操作只能执行k次，所以要找最后k个数中最小的那个，旋转之后再进行单调栈。
但是对于旋转过的数，如果需要删除，则不用减少操作次数，因为旋转+删除等同于直接删除。用数组标记哪些数旋转过，删的时候判断一下就好（因为是全排列，不用考虑数字重复或者数字太大的情况）

如果执行完单调栈后操作次数还有剩余，就从后面往前删.(不需要考虑删完所有数的情况，因为K<N)

	//旋转后进行单调栈，这样写会出现一个问题
	//当cnt=0时，但栈顶元素是标记过的，则不会被删除，就会wa
	while(!a2.empty()&&cnt>0&&a2.back()>a[i]) 
	{
		if(!vis[a2.back()]) cnt--;
		a2.pop_back();
	}
	a2.push_back(a[i]);
	
	//正确写法
	while(!a2.empty()&&a2.back()>a[i]) 
	{
		if(vis[a2.back()]) cnt++;
		if(cnt>0) a2.pop_back(),cnt--;
		else break;
	}

代码

int n,m,k;
int a[N],b[N];
bool vis[N];
void solve() 
{
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	if(k==0) 
	{
		for(int i=1;i<=n;i++) cout<<a[i]<<" ";
		cout<<endl;
	 	return;
	}
	vector<int> a1,a2;

	//只执行操作1
	int cnt=k;
	for(int i=1;i<=n;i++) 
	{
		while(!a1.empty()&&cnt>0&&a1.back()>a[i]) a1.pop_back(),cnt--;
		a1.push_back(a[i]);
	}
	while(cnt>0) a1.pop_back(),cnt--;

	//旋转后

	int pos=-1,mn=1e9+10;
	for(int i=n;i>=n-k+1;i--) //找到最后k个数中最小的那个
	{
		if(mn>a[i]) mn=a[i],pos=i;
	}
	cnt=k-(n-pos+1);
	for(int i=pos;i<=n;i++) vis[a[i]]=1;

	for(int i=pos;i<=n;i++) 
	{
		while(!a2.empty()&&a2.back()>a[i]) 
		{
			if(vis[a2.back()]) cnt++;
			if(cnt>0) a2.pop_back(),cnt--;
			else break;
		}
		a2.push_back(a[i]);
	}
	for(int i=1;i<pos;i++) 
	{
		while(!a2.empty()&&a2.back()>a[i]) 
		{
			if(vis[a2.back()]) cnt++;
			if(cnt>0) a2.pop_back(),cnt--;
			else break;
		}
		a2.push_back(a[i]);
	}
	while(cnt>0) a2.pop_back(),cnt--;
	auto ans=min(a1,a2);
	for(auto &x :ans) cout<<x<<" ";
	cout<<endl;
}