抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

七つの海

今日、海を見た。もう怖くない

按照惯例,开始之前先码一下比赛的一些相关链接:

比赛地址: https://ac.nowcoder.com/acm/contest/4743 官方题解: https://ac.nowcoder.com/discuss/381692?type=101&order=0&pos=1&page=1

这次题目可以说是优化DP/树形数据结构专场?六个题目很大一部分都可以使用优化DP的方法来解决。但是总体感觉还是题目没有出好,很多的题目只要你思维敏捷也能方便的使用其他的方法解决。

嘛……毕竟是马后炮,怎么说都是可以的(不过有一说一,从七点发呆到九点错过比赛时间,比赛结束之后立马补题倒也是有点真实==

YS@39GS0XAKAL@L_CIKUTXN.jpg

不过比起打休闲,还是打天梯技术进步的更快,所以还是多打比赛,少自己补题休闲的好;虽然就算是事后自己做,结果好像也没做出来几个题目就是了==

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
#include <iostream>
#include <cstdio>
#include <string>

using namespace std;
typedef long long longs;

string s;
char xq[] = "XiaoQiao";
char xhh[] = "XiaoHuiHui";

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);

cin>>s;
auto x = s.find('X');
if(x==string::npos) // 必须的
{
cout<<"emm";
return 0;
}
int ca = 1, cb = 1;
int lim = s.length();
for (int i = x; i < lim; ++ i)
{
if(s[i]==xq[ca]) if(xq[ca]) ++ca;
if(s[i]==xhh[cb]) if(xhh[cb]) ++cb;
}

if(xq[ca] || xhh[cb]) cout<<"emm";
else cout<<"Happy";

return 0;
}

唯一的笔记就是string::npos不能忽视,还是要进行特判的。

B - 修路

签到题,排个序然后累加得到的就是最小生成树。

题目中的那个费用整理一下合并就可以得到费用至于每个小镇相关,而和哪两个小镇无关。

我的代码

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
#include <iostream>
#include <cstdlib>
#include <algorithm>

#define fee(a,b) (abs(f[a]-f[b]))

using namespace std;
typedef long long longs;

const int N = 1e5+5;

int n;
longs f[N];

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);

cin>>n;
longs x,y;
for(int i = 1; i <= n; ++ i)
{
cin>>x>>y;
f[i] = y*(x-y)*(x-y);
}
sort(f+1,f+1+n);
longs ans = 0;
for(int i = 1; i < n; ++ i)
ans += f[i+1]-f[i];
cout<<ans;

return 0;
}

C - 买装备

首先两种装备的消耗是给死了的。所以可以列方程,这恰好是二元一次不等式,可以线性规划。但是线性规划因为是一个浮点数,所以可能存在误差,需要对规划结果周围的数字进行一下判定,同时也需要特判解出负数的情况;

当然,因为题目写死了数据的原因,易得这个问题的单调极值性,那就可以三分来做了;同样是为了保险起见,区间缩小到一定范围就遍历求解比较就行。

如果不给死的话就是一个典型DP,但是这题目既然写死了还多组数据,显然就不是DP了。

我的代码

线性规划法:单次询问 O(1)

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
#include <iostream>
#include <algorithm>

#define getN(m) min(y-3*(m),(x-2*(m))>>2)

using namespace std;
typedef long long longs;

longs solve(int x, int y)
{
longs m = (4ll*y-x)/10ll;
longs n = getN(m);
if(m <= 0 || n <= 0)
return max(min(x>>1,y/3),min(x>>2,y));
longs ans = max(m+n,m+1+getN(m+1));
return max(ans,m-1+getN(m-1));
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);

longs t,x,y;
cin>>t;
while(t--)
{
cin>>x>>y;
cout<<solve(x,y)<<endl;
}

return 0;
}

三分答案法:单次复杂度 O(log n)

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 <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long longs;

int x,y;

longs check(longs m)
{
longs n = min((x-(m<<1))>>2, y-3*m);
return m+n;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);

int t;
cin>>t;
while(t--)
{
cin>>x>>y;

int l = 0;
int r = max(min(x/2,y/3),min(x/4,y));
while(r-l>10)
{
int t = (r-l)/3;
int m1 = l+t, m2 = r-t;
if(check(m1) > check(m2)) r = m2;
else l = m1;
}
longs ans = 0;
for(int i=l;i<=r;++i)
ans = max(ans,check(i));
cout<<ans<<endl;
}

return 0;
}

理论上是一个DP,但是这个DP你就挂了==

D - 石头游戏

异想天开的找规律,你不死谁死呢(叹气

玩家先手,如果是1,根据游戏定义那必败;那么因为大家都会采用最优战略,所以只要能转移到1的状态的状态就是必胜态;相反的,如果一个状态是必败态,那么它能转移到的状态一定都是必胜态;

所以,设每一个状态有效区间是[s,e],从必败转移到必胜的区间就是[e+1,2e+1](或者[2s,2e+1]),从必胜转移到必败就是[e+1,2e]。显然,必胜-必败区间是相互交错的。

得到了推导式,就可以算出包含输入的上限1e18的所有区间的状态。输入之后查询属于的区间后输出结果就可以。因为区间是翻倍的所以会指数级别增长,推导大约只需要进行64轮就可以完成所需要的预处理。

我的代码

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 <iostream>
#include <algorithm>

using namespace std;
typedef long long longs;

const int N = 100;
const int M = 64;

longs st[N], ed[N];

void preProcess()
{
st[0] = ed[0] = 1;
for(int i = 1; i <= M; ++i)
{
st[i] = ed[i-1] + 1;
ed[i] = (ed[i-1]<<1) + (i&1);
}
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);

preProcess();

int t;
longs n;
cin>>t;
while(t--)
{
cin>>n;
int s = upper_bound(st,st+M,n) - st;
if(s&1) cout<<"XiaoQiao"<<endl;
else cout<<"XiaoHuiHui"<<endl;
}

return 0;
}

E - 搬石头

看起来贼像一个贪心,甚至还能装模做样大胆地猜出几个结论:贪,你接着贪——贪完你就去世了==

首先对于一堆确定数量的石头,分成x次搬运成本最低的方法显然是平均分配。但是要注意如果分配出0的话就没有意义了。

然后就是贪心的不正确性:大堆的石头分成多份可能比好几堆小的分成两份带来的收益大。所以这需要DP:将两堆石头分成m份带来的最优解是可以由两堆石头不同的分割方案递推而来的;这个时候还需要引入虚堆标记,有些麻烦。

计算单堆石头的所有分割方案的成本是O(n),再加上虚堆求出整个石头堆的最佳方案的成本就是O(n³)。嗯其实还可以接受,如果数据量不是特别大的话;

但是这个题目不仅要分配方案,这堆石头还在不停的变化;每次变化都是要重新DP才能得到最优解的,这样整体的复杂度就变成了O(n⁴)了,这可不就凉凉==

刚才提到了DP是需要虚点的,所以可以利用线段树的思想,维护一个区间;每一次的石头堆的变化相当于单点修改;这样的话可以节约相当一部分的资源,每一次单点修改就是使用O(n)重新计算一堆石头的所有分割方案,然后更新相关联的区块的DP。线段树的单点修改的复杂度是O(nlog n),加上这次的修改复杂度就是O(n²log n),再算上修改次数就是O(n³log n),差不多可以接受了。

虽然线段树的常数大的离谱,但是因为跑不满等诸多原因,这个题目还是可以勉勉强强的卡过去的。

社区讨论

这道题由很多大佬认为线段树过于愚蠢,可以使用其他优秀的办法来解决;可是又语焉不详,叫人听的半懂不懂的。因为我不是大佬,所以我只能简单的做一些大佬语录。如果之后了解了这些做法还记得这里的话就再更新了。

查.无.此.人. 4# : E题怎么做都比题解优吧 闵可夫斯基和n^3 贪心每次取变化量最小的n^2log😑

boxxxx 15# : E题裸dp每次是n3,但是可以3分优化成n2logn ……

三分我或多或少能理解…… 但是三分优化的DP是什么操作我就不得而知了(

我的代码

这就是题解的线段树代码

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <cstring>
#include <algorithm>

#define cline(x) memset(x,0x3f,sizeof(longs)*(m1))

using namespace std;
typedef long long longs;

const int N = 405;
const longs INF = 0x3f3f3f3f3f3f3f3f;

longs f[N<<2][N];
int wide[N<<2];
int n,m,li,m1;
int a[N];
int sum = 0;

void update(int line)
{
cline(f[line]);
const int l = line<<1;
const int r = l^1;
int p;
for(int i = wide[l]; i <= m; ++ i)
for(int j = wide[r]; (p = i+j) <= m; ++ j)
f[line][p] = min(f[line][p], f[l][i]+f[r][j]);
}

void calculate(int num, int index)
{
cline(f[index]);
const int lim = min(li,a[num]);
for(int i = 1; i <= lim; ++i)
{
const longs val = a[num] / i;
const longs mod = a[num] % i;
f[index][i] = mod*(val+1)*(val+1) + (i-mod)*val*val;
}
}

void build(int l, int r, int index)
{
wide[index] = r - l + 1;
if(l==r)
{
calculate(l,index);
return;
}
int m = l+r>>1;
build(l, m, index << 1);
build(m+1, r, index << 1 ^ 1);
update(index);
}

void modify(int l, int r, int index, int x)
{
if(l==r)
{
calculate(l,index);
return;
}
int m = l+r>>1;
if(x <= m) modify(l, m, index << 1, x);
else modify(m+1, r, index << 1 ^ 1, x);
update(index);
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);

cin>>n>>m;
li = m-n+1;
m1 = m+1;
for(int i = 1; i <= n; ++ i)
{
cin>>a[i];
f[i][1] = a[i]*a[i];
sum += a[i];
}
build(1,n,1);

int q,x,v;
cin>>q;
while(q--)
{
cin>>x>>v;
sum += v-a[x];
a[x] = v;
modify(1,n,1,x);
cout<<f[1][min(m,sum)]<<endl; // 总数不超过x的石头不会被分为超过x堆
}

return 0;
}

一个特别的小细节就是要注意到分割成0是无意义的,因此需要一直统计sum

F - 吃果果

相当于说,告诉你所有的果子落地的时间和位置,当然还有营养;问你应该怎么吃才能获得最大的营养。

显然题目开始之前,先根据时间排序。对于 j > i,如果吃到了第i个果果还能吃到第j个,那么两者的时间差一定大于距离;但是因为果果有不同的营养价值,所以还是不能贪,需要DP(话说就算全是1,似乎还是要DP……)。i和j都是n的复杂度,O(n²)对于本题1e5的数据会自动暴毙==

然后接下来的部分就是题解的申必优化:

对于位置 pi ≥ pj: 能吃到的条件就可以化为 ti - pi ≥ tj - pj
对于位置 pi ≤ pj: 能吃到的条件就可以化为 ti + pi ≥ tj + pj

记 Xi = ti - pi,Yi = ti + pi;再利用树套树来优化DP的转移过程,就可以把时间复杂度降低到 O(nlog²n),就可以卡过这个题目了=

说实话我还没学树套树,不是很能理解这种做法;那就学完了在更新好了(

事后分析

这其实是一个二位偏序的问题。题解使用的算法是一种叫做树套树的在线算法:但是常数大的离谱,模板也很长。如果出错的话后果不堪设想== 但是也是可以做的。可是题目并不是要求强制在线,所以可以使用一些高效率的离线算法来解决。不仅写代码更好写,也不容易出错,时间复杂度还更低。

这个题目的离线算法Tag: CDQ分治, 带权LIS

我的代码

还没写呢(

总的来说这次的题目主要还是用来优化写代码的熟练度,以及各种树形数据结构的使用== 当然也见识到了各种DP的常见优化。在这个的指引下,又可以学习一些新的知识了。不也挺好吗( 所以说不仅要补题,还要补的是基本功和知识储备啊==

2D~HSI7CWL46_WU__M~A590.jpg

谁叫咱现在的知识储备还处于精卫填海,女娲补天的水平呢== 人要有自知之明,不会的东西就得赶快去补(

评论