newcoder_lxs71

牛客练习赛 71

A

我吐了，我好菜，自己调不出来还让两个人同时帮我代调

#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cstring>
template <class T>
void read(T &x)
{
	x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
int a[12],flg=0,mid=-1,ans[110],n=0;
int main()
{
	for(int i=0;i<10;i++)
	{
		read(a[i]);
		if((a[i]&1)&&~mid) {puts("-1");return 0;}
		if((a[i]&1)&&(!~mid)) mid=i;
	}
	for(int i=1;i<10;i++)
	{
		if((a[i]||i==9)&&!flg)
		{
			if(a[i]>=2) ans[++n]=i,a[i]-=2;
			flg=1;
			for(int j=1;j<=a[0]>>1;j++)
				ans[++n]=0;
		}
		for(int j=1;j<=a[i]>>1;j++)
			ans[++n]=i;
	}
	if(n&&!ans[1]) {puts("-1");return 0;}
	for(int i=1;i<=n;i++) printf("%d",ans[i]);
	if(~mid) printf("%d",mid);
	for(int i=n;i;i--) printf("%d",ans[i]);
	return 0;
}

贪心即可

注意先放一个数再放 0

注意前导 0

B

三角形任意给共 3 个边或者角的信息，求可能的三角形个数。

分类讨论即可。

不想写，爬了。

C

求长为 $n$ 的满足如下 $m$ 个条件的排列的个数：前 $p_i$ 个数不为排列。对 20000311 取膜。

保证 $p_i$ 互不相同。

$n\le 2000,m,p_i\le n$

写这个题的时候，找到了一点学 OI 时的回忆吧。

就是那个明明不怎么弄清楚的，但是就是想先把瞎猜给写一下的感觉，然后过了。

首先分析一下限制个数为 1,2,3 时的情况是具体怎么容斥的。

然后你发现答案似乎就是

$\sum_{P_i}(-1)^{|P_i|+1}\prod_{j=1}^{|P_i|}(p_j-p_{j-1})!$

其中 $P_i$ 为 $\{p_1,p_2,\dots,p_m\}$ 的任意子序列与 $\{n\}$ 的并（原序列从小到大排序）

然后写个 $n^2$ 的 $dp$ 就可以了

#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cstring>
template <class T>
void read(T &x)
{
	x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
const int N=2010;
const int mod=20000311;
int n,m,dp[N],p[N],fac[N];
int main()
{
	read(n),read(m);
	for(int i=1;i<=m;i++) read(p[i]);
	std::sort(p+1,p+1+m);
	p[++m]=n,fac[0]=1,dp[0]=-1;
	for(int i=1;i<=n;i++) fac[i]=1ll*i*fac[i-1]%mod;
	for(int i=1;i<=m;i++)
		for(int j=0;j<i;j++)
			dp[i]=(dp[i]+1ll*(mod-dp[j])*fac[p[i]-p[j]]%mod)%mod;
	printf("%d\n",dp[m]);
	return 0;
}

好吧，正经一点，思路是这样的

你发现能快速求出来的只有满足 $1～p_i,p_i～ p_j,\dots,p_k～ n$ 是排列这样的个数，然后位置更靠后的排列会重复前面的排列，于是你对前面重复的加上或者减去进行容斥。

然后就是按照满足的条件个数进行系数分配。

D

麻烦题，不想理

E

给一颗带权树，点权为 $a_i$ ，边权为 $1$，同时给出数组 $w_i$ 求

$\frac{\sum\limits_{i=1}^{n}a_i\sum\limits_{j=1}^{n}a_j w_{dis_{i,j}}}{s^2}$

$1e5$ 对 998244353 取模

淀粉质套 NTT 好像是个套路题

有时间做做，现在代码能力肯定不行了

F

$n$ 点 $m$ 边无向图，边有权值与颜色，颜色分红蓝两种。

$q$ 次询问，每次删除边权大于 $t$ 的红边与边权小于 $t$ 的蓝边，询问与 $x$ 点联通的数量。

定义两点 $x,y$ 联通为：它们有仅过红色边路径相连，同时仅过蓝色边相连，则联通。

$n \le 2e5,m,q \le 4e5$

一眼重构树，实际细节想不清楚，先鸽了，整理板子去咯