newcoder_lxs71

牛客练习赛 71

A

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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

求长为 nn 的满足如下 mm 个条件的排列的个数:前 pip_i 个数不为排列。对 20000311 取膜。

保证 pip_i 互不相同。

n2000,m,pinn\le 2000,m,p_i\le n

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

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

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

然后你发现答案似乎就是

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

其中 PiP_i{p1,p2,,pm}\{p_1,p_2,\dots,p_m\} 的任意子序列与 {n}\{n\} 的并(原序列从小到大排序)

然后写个 n2n^2dpdp 就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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;
}

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

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

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

D

麻烦题,不想理

E

给一颗带权树,点权为 aia_i ,边权为 11,同时给出数组 wiw_i

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

1e51e5 对 998244353 取模

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

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

F

nnmm 边无向图,边有权值与颜色,颜色分红蓝两种。

qq 次询问,每次删除边权大于 tt 的红边与边权小于 tt 的蓝边,询问与 xx 点联通的数量。

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

n2e5,m,q4e5n \le 2e5,m,q \le 4e5

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

  • Copyright: Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2020-2022 Dew
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信