51nod 的NOIP模拟赛题。希望NOIP赛前思维康复计划能有效......

同时,因为一些不可抗拒的因素......(此处省略23字......

noip-51nod.png

Day 1

A 珂朵莉的旅行

时间限制:1s空间限制:128MB分值: 100

【题目描述】

浮游大陆由 nn 个浮游岛构成,其中不同的浮游岛之间存在着飞艇航线。

由于浮游大陆的经济比较紧张,花在交通的费用不能太多,因此在保证每一个浮游岛都是联通的基础上,大贤者只修筑了 n1n-1 条航线。

在击败第五号岛的兽之后,威廉决定带辛苦战斗的珂朵莉,奈芙莲,艾瑟雅去浮游大陆旅行。

“Are you going toScarborough Fair?”

每个浮游岛本质属于不同的政体,所以它们的政策等会存在诸多差异。在旅行之前,威廉将浮游岛划分成两种,可以认为权值为 1100.由于要保证这是一次开心的旅行,所以他希望旅行之后经过的路径浮游岛的权值异或和为 00.

他们的旅行方案是这样的:从某一个节点开始,不经过重复的节点,随机的选择一个与当前节点相连的节点,直到走到无路可走,这算完成一次旅行。

由于威廉也才来到浮游大陆不久,所以他也不知道每一个节点的权值到底是 11 还是 00.

他想问问你,总共有多少种可能的钦点某些浮游岛的权值为 11(其他浮游岛权值为00)的方式,符合上文提出的条件?

由于他们没有学过数学,因此请你将答案对 109+710^{9}+7 (一个质数)取模。

【输入格式】

第一行一个整数 nn,表示浮游岛的数量。

第二行开始每行两个整数 u,vu,v,表示浮游岛 uu 和浮游岛 vv 有无向的飞艇路线相连。

【输出格式】

一行一个整数,表示答案。

【样例输入】

3
1 2
2 3

【样例输出】

10

【数据规模和约定】

对于 20%20\% 的数据,满足 1n101 \le n \le 10

对于 40%40\% 的数据,满足 1n10001 \le n \le 1000

对于额外 20%20\% 的数据,浮游岛的连接将会成为一条链。

对于 100%100\% 的数据,1n1061 \le n \le 10^{6}

【样例解释】

如果威廉选择从 11 号浮游岛出发,那么可以设置 00 个或者 22 个浮游岛权值为 11,因此共有 44 种可能。

如果威廉选择从 22 号浮游岛出发,他可以走 212-1,或者 232-3 ,因此他可以设置 00 个浮游岛权值为 11 ,或者三个浮游岛权值全部为 11.

33 出发和从 11 出发情况类似,因此共有 4+2+4=104+2+4=10 种方案。

Solution

死在树形dp上,维护每个节点 dp[u][0/1][0/1] 表示该点为颜色 0/1 ,到叶子结点路径异或和为 0/1。上、下 dp 两次,就好了(假)。

考虑一条链的情况(20pts),我们先将非端点上的数染色,如果这时钦定起点为非端点,显然只有一种合法方案。

0 - 0 - 0 - 0 - 0 - 0 - 0

对于起点两端点的情况,显然有两种合法方案。

100pts

类似地,我们考虑叶子结点和非叶子结点的情况。那么总方案数为 n=1n=1 时特判一下就好了。

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}

#define p 1000000007
int qpow(int a,int b) {
int r=1;
for(;b;b>>=1,a=1ll*a*a%p)if(b&1)r=1ll*r*a%p;
return r;
}
int n, k, ru[1000005];

int main() {
read(n);
if(n==1) return puts("1"), 0;
int u, v;
rep(i,2,n) {
read(u), read(v);
ru[u]++, ru[v]++;
}
rep(i,1,n)if(ru[i]==1) ++k;
printf("%lld\n", 1ll*qpow(2,n-k)*(n+k)%p);
return ~~(0^_^0);
}

B 奈芙莲的序列

时间限制:1s空间限制:512MB分值: 100

【题目描述】

有一天可爱的 Nephren 得到了一个序列 A\text{A},一开始,她取出序列的第一个数,形成一个新的序列 B\text{B} ,然后取出序列 A\text{A} 的第二个数,放在序列 B\text{B} 的最左边或最右边,序列 B\text{B} 此时有两个数,下一步,再取出序列 A\text{A} 的第三个数放在序列 B\text{B} 的最左边或最右边,……

现在的问题是,通过上面的步骤,可以得到 B\text{B} 的最长上升子序列的长度是多少?

【输入格式】

第一行,一个整数 NN

第二行,NN 个整数,表示序列 A\text{A}

【输出格式】

一行一个整数,表示最长上升子序列的长度。

【样例输入】

4
2 1 3 4

【样例输出】

4

【数据规模及约定】

对于 30%30\% 的数据,满足 1n201 \le n \le 20

对于 50%50\% 的数据,满足 1n10001 \le n \le 1000

对于 100%100\% 的数据, .

保证 A\text{A} 序列所有数不会超过 10910^{9}

Solution

结论:
新序列的最长上升子序列等于
max{max\{以第 ii 位为起始的最长上升子序列 ++ 以第 ii 位为起始的最长下降子序列 1-1}

正确性嘛,请读者自行证明。

乱写假贪心竟然有 45 分qwq,开心。

Code

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
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}

int n, a[200005], b[200005], f[200005][2], ans;
#define lowbit(x) (x&-x)
int t[200005];
inline void upd(int x,int d) {for(;x<=n;t[x]=max(t[x],d),x+=lowbit(x));}
inline int get(int x) {int r=0;for(;x;r=max(r,t[x]),x-=lowbit(x));return r;}

int main() {
read(n);
rep(i,1,n) read(a[i]),b[i]=a[i];
sort(b+1, b+n+1);
int m=unique(b+1,b+n+1)-b-1;
rep(i,1,n)
a[i] = lower_bound(b+1,b+m+1,a[i])-b;

for(int i=n;i>=1;--i) {
f[i][0] = get(a[i]-1)+1;
upd(a[i], f[i][0]);
} //down
memset(t, 0, sizeof t);
for(int i=n;i>=1;--i) {
f[i][1] = get(m-a[i])+1;
upd(m-a[i]+1, f[i][1]);
} //up

rep(i,1,n)
ans=max(ans, f[i][0]+f[i][1]-1);
printf("%d\n", ans);
return ~~(0^_^0);
}

奈芙莲的护符

时间限制:1s空间限制:256MB分值: 100

【题目描述】

Nephren 有 nn 个护符,每个护符的魔力容量都是无限的,并且每个护符在初始时已经被倾注了一些魔力。

Nephren 想要获得里面所有的魔力,但是她最后只能选择 kk 个护符吸收。

所以,她需要将一些护符的魔力融合到一起。但是把 ii 号护符的魔力移动到 jj 号护符需要花费 c[i][j]c[i][j] 的体力。

所以请您求出最小花费的体力。

【输入格式】

第一行,输入

下面 NN 行,每行 NN 个整数,描述 c[i][j]c[i][j]

【输出格式】

输入一个整数,即所需的最小体力值。

【样例输入】

3 3 
0 1 1 
1 0 1 
1 1 0

【样例输出】

0

【数据范围】

对于 40%40\% 的数据,满足 1n101 \le n \le 10

对于 100%100\% 的数据,满足 1kn201 \le k \le n \le 20.

所有的 c[i][j]100000,c[i][i]=0c[i][j] \le 100000,c[i][i]=0.

Solution

原题面写得有点误解。一道基础状压 dp 题。 dp[i] 表示每一个护符是否合并。

时间复杂度 .

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0

int n, k, dp[1<<20], ans, c[22][22];
int get(int x) {int r=0;for(;x;x-=x&-x,++r);return r;}

int main() {
scanf("%d%d", &n, &k);
rep(i,0,n-1)rep(j,0,n-1) scanf("%d",&c[i][j]);
memset(dp, 0x7f, sizeof dp);
ans = 0x7f7f7f7f;
dp[(1<<n)-1] = 0;
for(int z=(1<<n)-1;~z;--z) {
for(int i=0;i<n;++i)if(!((1<<i)&z))
for(int j=0;j<n;++j)if((1<<j)&z)
dp[z]=min(dp[z], dp[z|(1<<i)]+c[i][j]);
if(get(z)==k) ans=min(ans,dp[z]);
}
printf("%d\n", ans);
return ~~(0^_^0);
}

Day 2

LXL的雕像

时间限制:1s空间限制:256MB分值: 100

【题目描述】

地主lxl拥有一块 的土地,有一天他突发奇想,想要在自己的土地上建造若干雕像来纪念自己的伟业。

已知每个雕像底座的尺寸均为 。为了美观,lxl想把雕像排列成一个矩形网格,每个雕像与其相邻的雕像(或者与土地边缘)的距离 xx 全部相等,如下图所示。

tmp.png

xx 可以为任意非负实数。

lxl想在土地上摆尽可能多的雕像,请你告诉他此时 xx 的取值应为多少。

【输入格式】

一行三个正整数表示 l,n,ml,n,m

【输出格式】

一行一个实数 xx ,精确到小数点后六位。如果无法摆下雕像,输出 1-1

【样例输入】

2 18 13

【样例输出】

0.500000

【数据规模和约定】

对于 40%40\% 的数据,

对于 100%100\% 的数据,

Solution

设每一行放了 aa 个雕像, 每一列放了 bb 个雕像。那么就可以推柿子了...

a,ba,b,有

a=nxx+l=1+n+lx+l>0a=\frac{n-x}{x+l}=-1+\frac{n+l}{x+l}>0b=mxx+l=1+m+lx+l>0b=\frac{m-x}{x+l}=-1+\frac{m+l}{x+l}>0

a,bNa,b \in \mathbb{N} ,故 n+lx+lN\frac{n+l}{x+l} \in \mathbb{N}m+lx+lN\frac{m+l}{x+l} \in \mathbb{N} 。显然,我们要让 xx 尽可能取到最小值。
很容易想到 exgcd 求解线性方程,但 xx 是实数,那怎么做啊?qwq

类似地,设

n+lx+l=k1,m+lx+l=k2   (k1,k2N)\frac{n+l}{x+l} = k_{1}, \frac{m+l}{x+l} = k_{2}~~~(k_{1},k_{2} \in \mathbb{N})

可得:

注意到乘积均为整数,所以可以通过先解整数解来解实数 xx

更具体地,若 x+lx+l 存在一个整数解 XX,那么下面的 x+lx+l 也是成立的:

显然,XX 的一个特解为 gcd(n+l,m+l)gcd(n+l,m+l)。那么就可以二分 pp 来求得 xx 的最小值。

题解不用二分qwq

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0

int l, n, m;
double x;

int main() {
scanf("%d%d%d", &l, &n, &m);
if(l>=min(n,m)) return puts("-1"), 0;
int g = __gcd(m+l,n+l);
if(g<l) return puts("-1"), 0;
int L=1, R=1e9, mid;
while(L<=R) {
mid = (L+R)>>1;
if(1.*g>=1ll*l*mid) L=mid+1;
else R=mid-1;
}
x = 1.*g/R-l;
printf("%.6lf\n", x);
return ~~(0^_^0);
}

ZYZ的游戏

时间限制:1s空间限制:256MB分值: 100

【题目描述】

zyz上微积分A的时候觉得内容太水了,于是想了一个游戏出来打发时间。

zyz画了一棵树,然后zyz想要删去上面的 kk 条边,将其分成 k+1k+1 部分。

zyz希望得到的森林中的最长路径尽可能小。zyz当然知道啦,但他想考考你这个最小值是多少。

【输入格式】

第一行两个整数 n,kn,k

接下来 n1n-1 行,每行两个正整数 x,yx,y ,描述一条树边 (x,y)(x,y)

【输出格式】

一行一个整数,最长路径的表示最小值。

【样例输入】

6 2
1 2
1 3
1 4
2 5
3 6

【样例输出】

1

【数据规模和约定】

对于 30%30\% 的数据,

对于 60%60\% 的数据,

对于 100%100\% 的数据,

Solution

好像之前做过这道题。考虑二分答案+贪心

check 每个答案的时候,从大到小将每个孩子的路径长度排序,若两个孩子构成的路径长度大于答案,那么就割断路径长度较大的孩子。最后统计一下割掉的边数是否 即可。

Code

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
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}

int n, k, x, dp[400005];
vector<int> d[400005];

int dfs(int u,int fa=0) {
int r=0; dp[u]=0;
if(u!=1&&d[u].size()==1) return 0; //叶结点
vector<int> s;
for(int v:d[u])if(v!=fa) {
r += dfs(v, u);
s.push_back(dp[v]);
}
sort(s.begin(),s.end());
for(int i=s.size()-1;i>=1;--i) {
if(s[i]+s[i-1]+2>x) ++r;
else {dp[u]=s[i]+1;break;}
}
if(!dp[u]) dp[u]=s[0]+1;
if(dp[u]>x) dp[u]=1, ++r;
// printf("%d -> %d\n", u, dp[u]);
return r;
}

int main() {
read(n), read(k);
int u, v;
rep(i,2,n) {
read(u), read(v);
d[u].push_back(v), d[v].push_back(u);
}
int l=1, r=n;
while(l<=r) {
x = (l+r)>>1;
if(dfs(1)<=k) r=x-1;
else l=x+1;
}
printf("%d\n", l);
return ~~(0^_^0);
}

XYK的音游

时间限制:1s空间限制:256MB分值: 100

【题目描述】

xyk最近入坑了一个新音游。

游戏界面上有 nn 个并排的按键,当前这首歌有 mm 个鼓点。游戏的玩法是在鼓点的时刻移动鼠标到对应的按键上并点击来获取分数。

对于第 ii 个鼓点,我们用 ti,wi,xit_{i},w_{i},x_{i} 来描述,表示在 tit_{i} 时刻点击第 xix_{i} 个按键会获得 wiw_{i} 的分数。

由于xyk手速很慢,每个时刻只能移动 pp 个按键的距离。也就是说如果 ss 时刻xyk的鼠标在第 pospos 个按键上,那么 s+1s+1 时刻他能够把鼠标移动到 的按键。

00 时刻xyk可以把鼠标放在任意位置。鼓点出现的时刻大于 00 。保证同一时间不会有两个鼓点。由于这款音游并不看重连击,xyk希望分数尽可能高就好。请你帮助他计算他能获得的最高分数。

【输入格式】

第一行三个正整数 n,m,pn,m,p

接下来 mm 行每行三个正整数 ti,wi,xit_i,w_i,x_i 描述第 ii 个鼓点。

【输出格式】

一行一个整数表示最大分数。

【样例输入】

5 5 1
2 42 4
3 23 4
1 70 4
2 31 5
1 85 5

【样例输出】

150

【数据规模和约定】

对于 30%30\% 的数据, p=1p=1

对于 50%50\% 的数据,

对于 100%100\% 的数据,

Solution

很容易想到一种做法:先将鼓点按照时间顺序排序,dp[i] 表示到第 ii 个鼓点的最高分数。

dp[i]=max(dp[j])+w[i]      [j<i][p(titj)xixj]dp[i] = max(dp[j]) + w[i] ~~~~~~ [j < i] \wedge [p(t_{i}-t_{j}) \geq |x_{i}-x_{j}|]

考虑更本质的东西,合法的转移必须满足:

xixjp(titj)|x_{i}-x_{j}| \leq p(t_{i}-t_{j})

也即

p(titj)xixjp(titj)-p(t_{i}-t_{j}) \leq x_{i}-x_{j} \leq p(t_{i}-t_{j})

那么就只有 pti+xiptj+xjpt_{i}+x_{i} \geq pt_{j}+x_{j}ptixiptjxjpt_{i}-x_{i} \geq pt_{j}-x_{j} 两个限制。

我们先将第一个限制排序,后面的限制用树状数组维护查询即可。

时间复杂度 O(n log n)O(n~log~n)

Code

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
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}
inline void chkmax(int &a,int b) {a=max(a,b);}
int n, m, p;
struct ak {
int t,w,x,d,u;
friend bool operator < (const ak&A,const ak&B){
return (A.d<B.d)||(A.d==B.d&&A.u<B.u);
}
}a[100005];
int b[100005];

int o[100005];
#define lowbit(x) (x&-x)
inline void upd(int x,int d) {for(;x<=m;chkmax(o[x],d),x+=lowbit(x));}
inline int get(int x) {int r=0;for(;x;chkmax(r,o[x]),x-=lowbit(x));return r;}

int main() {
read(n),read(m),read(p);
rep(i,1,m) {
read(a[i].t),read(a[i].w),read(a[i].x);
b[i]=a[i].u=p*a[i].t-a[i].x;
a[i].d=p*a[i].t+a[i].x;
}
sort(b+1,b+m+1);
int cnt=unique(b+1,b+m+1)-b-1;
rep(i,1,m) a[i].u=lower_bound(b+1,b+cnt+1,a[i].u)-b;
sort(a+1,a+m+1);

int ans=0;
rep(i,1,m) {
int tmp=get(a[i].u)+a[i].w;
chkmax(ans,tmp);
upd(a[i].u,tmp);
}
printf("%d\n", ans);
return ~~(0^_^0);
}

Day 3

Anan的派对

时间限制:1s空间限制:256MB分值: 100

【题目描述】

Anan想举办一个派对。

Anan的朋友总共有 nn 人。第 ii 个人如果参加派对会得到 cic_i 的快乐值,除他自己外每多一个人参加他会减少 did_i 的快乐值。

Anan想让这个派对的总快乐值尽可能大,在这个基础上,能来的人越多越好。

Anan想知道最佳的邀请方案的快乐值与参加人数。

【输入格式】

第一行一个正整数 nn

第二行 nn 个整数表示 cic_{i}

第三行 nn 个整数表示 did_{i}

【输出格式】

第一行一个整数最大快乐值。

第二行一个整数表示最佳方案的参加人数。

【样例输入】

6
10 10 10 10 10 9
2 2 2 2 2 3

【样例输出】

18
3

【数据规模和约定】

对于 50%50\% 的数据,

对于 100%100\% 的数据,

Solution

每次枚举参加人数,那么每个人的贡献都已经确定,那么贪心取前几大的即可。

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}

int n, c[1002], d[1002], q[1002];

int main() {
read(n);
rep(i,1,n) read(c[i]);
rep(i,1,n) read(d[i]);
int Max=0, t;
rep(x,1,n) {
int res=0;
rep(i,1,n) q[i]=c[i]-(x-1)*d[i];
sort(q+1, q+n+1, greater<int>());
rep(i,1,x) res+=q[i];
if(res>=Max) Max=res, t=x;
}
printf("%d\n%d\n", Max, t);
return ~~(0^_^0);
}

XYG的蛋糕

时间限制:1s空间限制:256MB分值: 100

【题目描述】

XYG要过生日了,他准备了一个 n×m n\times m 的矩形蛋糕请大家吃。

切蛋糕的方法如下:每次选出已经分出的某一个矩形蛋糕,一刀将其切成两个小矩形蛋糕。当然,这一刀可以选择横切或者竖切。最终XYG要把蛋糕切成 n×m n\times m 1×1 1\times 1 的小蛋糕。

XYG希望你告诉他总共有多少种不同的切法。两个切法不同当且仅当其中一个切法中存在一条刀痕,在另一个切法中不存在。

【样例输入】

3 2

【样例输出】

4

【数据规模和约定】

对于 40% 40\% 的数据, n,m15 n,m\le 15

对于 100% 100\% 的数据, n,m300 n,m\le 300

Solution

很容易想到dp,第一想法就是枚举 kk ,枚举分界线,有

dp[i][j] += dp[i][k]×dp[i][j-k] + dp[k][j]×dp[i-K][j]

显然这样会出现重复,e.g 样例。

产生重复的原因是因为划痕与划的时间无关。所以不妨按划痕的位置进行 dp,并且我们可以针对第一刀进行 dp。

设 dp[n][m][3] 分别表示

  1. 将大小为 的矩阵划分成 的方块的总方案数。
  2. 将大小为 的矩阵划分成 的方块且第一刀为横着划的方案数。
  3. 将大小为 的矩阵划分成 的方块且第一刀为竖着划的方案数。

对于 dp[n][m][1] 的转移,我们枚举第一刀横着划的位置,以上的方块第一刀为竖着划,以下的方块随意,于是有

  • dp[n][m][1]+=dp[k][m][2]*dp[n-k][m][0]

对于 dp[n][m][2] 的转移,我们枚举第一刀竖着划的位置,左边的方块第一刀为横着划,右边的方块随意,于是有

  • dp[n][m][2]+=dp[n][k][1]*dp[n][m-k][0]

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}
#define p 998244353
inline void add(int &a) {if(a>=p)a-=p;}

int n, m, dp[302][302][3];

int main() {
read(n),read(m);
dp[1][1][0]=dp[1][1][1]=dp[1][1][2]=1;
rep(i,1,n)rep(j,1,m) {
if(i==1&&j==1) continue;
rep(k,1,i-1) add(dp[i][j][1]+=1ll*dp[k][j][2]*dp[i-k][j][0]%p);
rep(k,1,j-1) add(dp[i][j][2]+=1ll*dp[i][k][1]*dp[i][j-k][0]%p);
add(dp[i][j][0]=dp[i][j][1]+dp[i][j][2]);
}
printf("%d\n", dp[n][m][0]);
return ~~(0^_^0);
}

WZD的洞洞

时间限制:1s空间限制:256MB分值: 100

【题目描述】

WZD有一个形状为直角三角形的洞洞。

平面上有 nn 个物品,每个物品有坐标 xi,yix_{i},y_{i} 和价值 wiw_{i},WZD希望用洞洞包含住价值尽可能高的物品。

由于洞洞的构造,其两条边必须平行于坐标轴,且直角在左下方(也就是说,洞洞只能平行移动),并且要求直角必须恰好落在一个物品上。

求洞洞能包含住最大价值为多少的物品。

【输入格式】

第一行一个整数 nn,表示有 nn 个礼品。

第二行两个整数 a,ba,b,表示这个直角三角形的两个直角边的长度(aa为平行于xx轴的直角边的长度,bb为平行yy轴的直角边的长度)。

接下来 nn 行,每行三个整数 xi,yi,wix_{i},y_{i},w_{i}

【输出格式】

仅一个数,表示最大价值。

【样例输入】

4
5 5
1 7 100
1 1 2
2 2 99
7 1 100

【样例输出】

101

【数据规模和约定】

40%40\% 的数据保证

100%100\% 的数据保证

100%100\% 的数据保证

Solution

难点在如何判断一个点是否在三角形内,若用线性规划,因为不同点确定的斜边不同,不是很好处理。

我们考虑构造直线: bx+ay=0bx+ay=0 ,那么所有三角形的斜边都平行于这条直线。判断点 jj 是否在点 ii 构造的直线上只需要判断点 ii 到直线的距离减点 jj 到直线的距离是否小于给定直角三角形的高。(这里的距离可以为负数)

形象化地描述,即:

维护这个东西只需要将点按照 disdis 从大到小排序即可。

这时只要满足 xj>xix_{j} > x_{i}yj>yiy_{j} > y_{i} 即可。显然这时点 jj 出现在点 ii 之前,即不可能有 xj<xix_{j} < x_{i}yj<yiy_{j} < y_{i} 。那么考虑去掉满足 xj<xi,yj>yix_{j}<x_{i},y_{j}>y_{i}xj>xi,yj<yix_{j}>x_{i},y_{j} < y_{i} 的点。

注意到这两个条件刚好相反,是互不影响的。所以用两个树状数组分别维护 xxyy 即可。

Code

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
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}

struct P{
int x,y,w;double dis;
bool operator < (const P&b)const{return dis>b.dis;}
}p[100005];
int n, a, b, ans;
queue<int> q;
int X[200005], Y[200005];
#define lowbit(x) (x&-x)
inline void add(int *t,int x,int d) {for(x+=1e5;x<=200000;t[x]+=d,x+=lowbit(x));}
inline int get(int *t,int x) {int r=0;for(x+=1e5;x;r+=t[x],x-=lowbit(x));return r;}

int main() {
read(n),read(a),read(b);
double c = sqrt(a*a+b*b);
rep(i,1,n) read(p[i].x),read(p[i].y),read(p[i].w),p[i].dis=1.*(b*p[i].x+a*p[i].y)/c;
sort(p+1, p+n+1);
double d = 1.*a*b/c;
int sum=0;
rep(i,1,n) {
sum += p[i].w, q.push(i);
while(p[q.front()].dis-p[i].dis>d) {
sum -= p[q.front()].w;
add(X,p[q.front()].x,-p[q.front()].w);
add(Y,p[q.front()].y,-p[q.front()].w);
q.pop();
}
ans = max(ans, sum-get(X,p[i].x-1)-get(Y,p[i].y-1));
add(X,p[i].x,p[i].w);
add(Y,p[i].y,p[i].w);
}
printf("%d\n", ans);
return ~~(0^_^0);
}

Day 4

砍树

时间限制:1s空间限制:128MB分值: 100

【题目描述】

小D有一棵树,这棵树有 nn 个节点,n1n-1 条边,保证连通。树上每个点要么被染成黑色,要么是白色。他定义一棵树的奇怪值为:这棵树中,白色节点与黑色节点数量的差的绝对值。

img

比如这个例子中,树上有 55 个白节点,33 个黑节点,奇怪值就是 35=2|3-5|=2

小D想让你在原树中砍出来一个连通块,使得这个连通块的奇怪值最大。(注意连通块当然也会是棵树。)

【输入格式】

首先输入 nn
接下来一行 nn 个数 。若 ci=0c_i=0 ,表示节点 ii 颜色为白色,否则为黑色。
接下来 n1n-1 行,每行两个数 u,vu,v,描述树上一条连接节点 u,vu,v 的边。

【输出格式】

输出一行,表示最大的奇怪值。

【样例输入】

8
1 0 0 1 1 0 0 0
7 1
3 5
1 6
4 3
6 3
2 3
7 8

【样例输出】

4

【数据规模和约定】

对于 20%20\% 的数据,
对于 40%40\% 的数据,
对于 60%60\% 的数据,
对于 100%100\% 的数据,

Solution

考虑去绝对值,问题转化为求一个求联通块使得黑点个数-白点个数最大,及白点个数-黑点个数最大。

考虑贪心,若一个子树对答案的贡献为负数,那么他的父节点就不必选他。

Code

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 <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}

int n, c[100005];
vector<int> d[100005];
int s[100005], ans;

void dfs(int u,int fa,int f) {
if(c[u]==f) s[u]=1; else s[u]=-1;
for(int v:d[u])if(v!=fa) {
dfs(v,u,f);
s[u]+=s[v];
}
s[u]=max(s[u],0); ans=max(ans,s[u]);
}

int main() {
read(n);
rep(i,1,n) read(c[i]);
int u, v;
rep(i,2,n) {
read(u),read(v);
d[u].push_back(v), d[v].push_back(u);
}
dfs(1,0,0);
dfs(1,0,1);
printf("%d\n", ans);
return ~~(0^_^0);
}

奇怪的回文串

时间限制:1s空间限制:128MB分值: 100

小D对字符串有着奇怪的认识。对于一个字符串S,他认为S是满足“奇数-回文”性质,当且仅当这个串的所有长度为奇数的子串都是回文串。注意一个串的子串指的是串中任意连续位置形成的串,一个“奇数-回文”串本身并不需要长度为奇数。

现在小D有一个长度为 NN 的字符串S。他有 KK 次修改这个字符串的机会。每次修改,他可以选择字符串上的任意一个位置,把这个位置修改成任意一种字符。他希望使得修改后的串中满足“奇数-回文”性质的子串的长度最大。注意 KK 次机会不必用完。

【输入格式】

第一行包含两个整数 K,NK,N
接下来一行 NN 个整数,第 ii 个整数代表字符串S第 ii 位的字符。

【输出格式】

输出一个整数,表示最大可能的满足“奇数-回文”性质的子串长度。

【样例输入】

1 6
1 2 3 4 5 6

【样例输出】

3

【数据规模和约定】

对于 20%20\% 的数据,
对于 40%40\% 的数据,
对于 60%60\% 的数据,
对于 100%100\% 的数据, ,保证给定的字符串的字符为 1110910^9 间的整数。

Solution

显然满足条件的串形如 abababa ,那么我们可以枚举子串,按奇数位和偶数位分别统计出现次数最多的字符,然后判断所需操作次数 (lenmax1max2)(len-max_1-max_2) 是否 k\leq k 即可。

在枚举上优化,我们可以用在数组上用双指针优化,枚举复杂度 O(n)O(n) ,判断复杂度 O(log n)O(log~n),总复杂度 O(n log n)O(n~log~n)

Code

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
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}

int n, k, a[500005], b[500005];
int num[2][500005], ans;
struct P{
int id,w;
bool operator < (const P&rhs)const{return w>rhs.w;}
};
set<P> s[2];

int main() {
read(k),read(n);
rep(i,1,n) read(a[i]),b[i]=a[i];
sort(b+1,b+n+1);
int m=unique(b+1,b+n+1)-b-1;
rep(i,1,n) a[i]=lower_bound(b+1,b+m+1,a[i])-b;

int r=1;
rep(l,1,n) {
while(r<=n) {
if(num[r&1][a[r]]) s[r&1].erase(P{a[r],num[r&1][a[r]]});
s[r&1].insert(P{a[r],++num[r&1][a[r]]});

++r;
if(r-l-(*s[0].begin()).w-(*s[1].begin()).w<=k) ans=max(ans,r-l);
else break; //break时 不++r会导致a[r]被重复插入
}
s[l&1].erase(P{a[l],num[l&1][a[l]]--});
if(num[l&1][a[l]]) s[l&1].insert(P{a[l],num[l&1][a[l]]});
}
printf("%d\n", ans);
return ~~(0^_^0);
}

范围查询

时间限制:1s空间限制:128MB分值: 100

【题目描述】

小D得到了一个数组 。他对这个数组A进行了 qq 个查询,每个查询都会给定四个数 left,right,x,yleft,right,x,y,你需要求出在数组A中,有多少位置 ii 满足下列条件:

其中 表示,aia_ixx 取模的值为 yy

【输入格式】

首先输入两个数 n,qn,q
接下来一行 nn 个数
接下来 qq 行,每行四个数 left,right,x,yleft,right,x,y ,描述一个询问。

【输出格式】

输出 qq 行,表示每个询问对应的答案。

【样例输入】

5 3
250 501 5000 5 4
0 4 5 0
0 4 10 0
0 4 3 2

【样例输出】

3
2
2

【数据规模和约定】

总共有 1010 个数据点。
对于第 个数据点,
对于第 个数据点,
对于 100%100\% 的数据,

Solution

数据出锅了...... 重造数据:Download 提取码:59de

xx 较小时,我们可以预处理每个数模 xx 的值,然后对于每个模数直接上前缀和,那么询问就很方便了。时间复杂度

xx 较大时,问题等价于求序列在 [l,r][l,r] 的个数和,而 xx 较大且 ai40000a_{i} \leq 40000 ,所以的不同数的个数不是很多。所以我们可以记录一下每个数出现的位置(vector),然后在里面二分左右端点就好了。时间复杂度

综合以上两种算法,取 时综合时间复杂度最优。

下面给出 xx 较大时的算法代码(其实稍卡常也可以跑过去)。

Code

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
39
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
inline void read(int &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}

int n, q;
vector<int> v[40005];
int buf[50], siz;
inline void print(int x) {
if(x==0){putchar(48);return;}
siz=0; while(x) buf[++siz]=x%10,x/=10;
while(siz) putchar(48+buf[siz--]);
}

int main() {
read(n), read(q);
register int x, y;
int l, r;
rep(i,1,n) read(x),v[x].push_back(i);
register int ans=0;
while(q--) {
read(l),read(r),read(x),read(y),++l,++r;
if(x==0) {puts("0");continue;}
ans=0;
for(;y<=40000;y+=x)
ans+=(upper_bound(v[y].begin(),v[y].end(),r)-v[y].begin())-
(lower_bound(v[y].begin(),v[y].end(),l)-v[y].begin());
print(ans);
putchar('\n');
}
return ~~(0^_^0);
}

Day 5