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

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


了解详情 >

七つの海

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

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

比赛地址: https://ac.nowcoder.com/acm/contest/5026#question

官方题解: https://ac.nowcoder.com/discuss/405216?type=101&order=0&pos=1&page=1

题目比较的简单,做起来还算是比较舒服的—— 但是最后两个题目没做出来,不太行。题解还是一如既往的中规中矩,虽然说做起来或多或少都有些思路,有的题目应该还是有一些别的简单乱搞一些的办法来解决的;

夜。大雨,家里没水==

9O14_@MZ6L~_Z_X_NQQLP_9.jpg

下次还是多打点天梯舒服一点……话说周日就要武大校赛了啊== 害,要好好打啊()下面开始:

A - 打怪

非常简单,所有的怪的hp和atk是一样的。只需要计算你会挨它几下然后计算总伤害就可以了;因为要保证自己不死,所以还需要处理一下自己的余数;总而言之细心点准没错。

然后就吃了一发罚时,bksn

我的代码

这是比赛时交的代码:

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

using namespace std;

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

int t, hp, atk, h, a;
auto solve = [&]() -> int
{
int xx = h / atk;
int yy = h - xx*atk;
int tt = yy ? xx : xx-1;
int dmg = a*tt;
cerr << dmg << endl;
if (!dmg) return -1;
else return hp%dmg ? hp/dmg : hp/dmg-1;
};

cin >> t;
while (t --)
{
cin >> hp >> atk >> h >> a;
cout << solve() << endl;
}

return 0;
}

因为是直接写的所以就顾不上美观了(

B - 吃水果

算是一个贪心题吧。关于输入的两种水果的数量,设较多的那个是x,另一个是y;简单分析一下就可以得到下面几种情况:

  • x = y: 直接吃就可以了,输出x;
  • x = 2y:消费1使得较少的翻倍,然后就变成情况1了,输出x+1;
  • x < 2y:可以先吃一点变成情况2,然后再吃完,输出x+1;
  • x > 2y:……一眼看不出来,那除了翻倍y别无他法——但是这样一定可以转化为上面某一种情况;

所以,分情况讨论完了之后就简单了:分情况判断完了返回不同的值就可以了;

此外,题解提了一句说因为规模比较小可以模拟。

我的代码

综上所述,除了第四种情况需要一个递归(甚至也不需要)之外无他;

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

using namespace std;

int solve(int n, int m)
{
if (n == m) return n;
int x = max(n,m), y = min(n,m);
if (x == y<<1) return y<<1^1;
else if (x < y<<1) return x+1;
else return solve(x,y<<1)+1;
}

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

int t, n, m;

cin >> t;
while (t --)
{
cin >> n >> m;
cout << solve(n,m) << endl;
}

return 0;
}

图省事就没改成迭代了(

C - 选择题

稍微麻烦一点的题目。看题干还是比较容易想到是使用一个并查集,先把必须要答案相同的选择题合并起来,然后再分块搜索;心里想着最坏情况12个选择题全部独立,需要4¹²种情况绝对会T的……后来看看题目的样例,已经可以说是最坏情况了,因为有限制的存在,爆搜会剪枝——情况似乎大概也就369600大概的水平:3e5 << 5e8,所以大概还是可行的;实际上也是可行的就是了(就这?

题解的说法是使用DP——倒也不是没想到,甚至我的文件里还有注释掉了的写了一半的DP== 但是因为实在是有点麻烦,还是爆搜来的简单就偷懒没写了== 就结果而言是好的(

因为这个题n=12,实在是太小了()题解里还说了一些在n更大的时候可以做的一些优化:

(多重背包问题):如果数据量再大一点,可以把所有背包的体积的所有状态哈希一下,变成一个二维dp,再滚动一下第一维即可。

如果是使用DP来解的话,那就是比较经典的多重背包问题。我们定义 \(dp[i][x_1][x_2][x_3][x_4]\) 是枚举了i个物品,四个背包(答案选项)已经使用了\(x_{1..4}\)个的状态。那么转移就可以从其他不同背包转移过来,枚举所有的背包就可以了;因为每个背包有容量上限,所以有的情况是转移不了的,可以节约掉。

我的代码

比赛时直接莽了一波写了一个剪枝的暴力搜索;非常的丑陋但是因为不想重写了所以就这样:

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

using namespace std;

int max4(int a, int b, int c, int d)
{
return max(a,max(b,max(c,d)));
}

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

int na, nb, nc, nd, m;
int x, y, p[13];
for (int i = 0; i <= 12; ++ i)
p[i] = i;
function<int(int)> father = [&](int ii) -> int
{
if (p[ii] == ii) return ii;
else return p[ii] = father(p[ii]);
};
auto join = [&](int x, int y)
{
int px = father(x),
py = father(y);
p[px] = py;
};
int num[13], cnt = 0, ans = 0;
map<int,int> mm;

function<int(int,int,int,int,int)> search =
[&](int s, int a,int b, int c, int d) -> int
{
if (s == cnt) return 1;
else if (num[s] > max4(a,b,c,d)) return 0;
int ret = 0;
if (a >= num[s]) ret += search(s+1,a-num[s],b,c,d);
if (b >= num[s]) ret += search(s+1,a,b-num[s],c,d);
if (c >= num[s]) ret += search(s+1,a,b,c-num[s],d);
if (d >= num[s]) ret += search(s+1,a,b,c,d-num[s]);
return ret;
};

cin >> na >> nb >> nc >> nd >> m;
while (m --)
{
cin >> x >> y;
join(x,y);
}
memset(num,0,sizeof num);
for (int i = 1; i <= 12; ++ i)
{
if (!mm[father(i)])
mm[p[i]] = ++cnt;
++ num[mm[p[i]]];
}
cout << search(1,na,nb,nc,nd) << endl;

return 0;
}

使用并查集完了之后再统计一波——甚至还要为此开一个map是真的丑陋…… 虽然时间上大概是O(n)的而且n非常非常小,并不会带来什么影响但是还是丑陋== 下次还是少用点lambda表达式吧(

因为这个题目理论上是要DP搜索的,所以还是补了一下丑陋的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
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <cstring>
#include <map>

using namespace std;
typedef long long longs;
typedef long double longd;

const int N = 2e6+5;
const int inf = 0x7fffffff;
const longs INF = 0x7fffffffffffffff;
const double eps = 1e-8;

int max4(int a, int b, int c, int d)
{
return max(a,max(b,max(c,d)));
}

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

int na, nb, nc, nd, m;
int x, y, p[13];
for (int i = 0; i <= 12; ++ i) p[i] = i;
function<int(int)> father = [&](int ii) -> int
{
if (p[ii] == ii) return ii;
else return p[ii] = father(p[ii]);
};
auto join = [&](int x, int y)
{
int px = father(x), py = father(y);
p[px] = py;
};
int num[13], cnt = 0, ans = 0;
map<int,int> mm; int f[13][13][13][13][13];

auto dp = [&]
{
memset(f, 0, sizeof(f)); f[0][0][0][0][0] = 1;
for (int i = 1; i <= cnt; ++ i)
for (int a = 0; a <= na; ++ a)
for (int b = 0; b <= nb; ++ b)
for (int c = 0; c <= nc; ++ c)
for (int d = 0; d <= nd; ++ d)
{
auto &xx = num[i];
if (a + xx <= na) f[i][a+xx][b][c][d] += f[i-1][a][b][c][d];
if (b + xx <= nb) f[i][a][b+xx][c][d] += f[i-1][a][b][c][d];
if (c + xx <= nc) f[i][a][b][c+xx][d] += f[i-1][a][b][c][d];
if (d + xx <= nd) f[i][a][b][c][d+xx] += f[i-1][a][b][c][d];
}
return f[cnt][na][nb][nc][nd];
};

cin >> na >> nb >> nc >> nd >> m;
while (m --)
{
cin >> x >> y;
join(x,y);
}
memset(num,0,sizeof num);
for (int i = 1; i <= 12; ++ i)
{
if (!mm[father(i)])
mm[p[i]] = ++cnt;
++ num[mm[p[i]]];
}
cout << dp() << endl;

return 0;
}

至于背包的状态的哈希那就没有做了。

D - 最短路

这样的题目不出意外应该是第三次遇到了——一种显而易见的套路就是正向反向最短路,然后枚举要”修改“的边,根据最短路求出的值快速计算新值,从而进行判断;而且这个题目也没有像洛谷那个题目那样卡了遍历,可以说没有什么路子都是套路了。

关于判断的部分:首先我们可以求出原来的最短路;然后可以快速算出来的新路长度,一定是包含反转后的这条路的最短路——其他的路要不不变,要不变了也不是最短路。所以:如果它可以更新最短路,那么最短路显然变短;否则,一定不会存在其他的路可以更新最短路。

唯一有些担心的是:如果这些更新是累计的更新的话,这种针对一条边修改的套路就会失效。方法……等我想出来再说吧(

题解分析

题解里最后提了一句,问应该如何判断修改单边之后,判断最短路长度是否不变的做法。

解决这个问题之前,我们应该先意识到:如果最短路因为单边修改而缩短,那么显然这样就可以;但是如果单边的修改破坏了原有最短路,我们并不能直接看出增长之后的最短路的长度——于是就不能判定不变了。

我的代码

使用dijkstra正反扫描最短路,然后针对询问进行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
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
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
typedef long long longs;

struct edge
{
int u, v, w, next;
edge() = default;
edge(int u, int v, int w, int next)
: u(u), v(v), w(w), next(next) {}
};

const int N = 1e5+5, M = 2e5+5;

int n, m;

namespace FWS
{
int head[N];
int tail[N];
int tot;
edge ee[M*2];

void init()
{
memset(head, -1, sizeof(int)*(n+1));
memset(tail, -1, sizeof(int)*(n+1));
tot = 0;
}

void addedge(int u, int v, int w)
{
ee[tot] = edge(u,v,w,head[u]);
head[u] = tot ++;
ee[tot] = edge(v,u,w,tail[v]);
tail[v] = tot ++;
}
}

namespace dij
{
using namespace FWS;

bool vis[N];
longs ds[N], dt[N];

void dijkstra(int goal)
{
priority_queue<pair<longs ,int>> q;
int* li = goal == n ? tail : head;
longs* dis = goal == n ? dt : ds;

q.push(make_pair(0, goal));
memset(vis,0, sizeof(bool)*(n+1));
memset(dis,0x3f, sizeof(longs)*(n+1));
dis[goal] = 0;
while (!q.empty())
{
int u = q.top().second; q.pop();
if (vis[u]) continue; vis[u] = true;
for (int c = li[u]; ~c; c = ee[c].next)
{
edge& e = ee[c];
int v = e.v;
if (dis[v] >= dis[u] + e.w)
q.push(make_pair(
-(dis[v] = dis[u] + e.w),
v
));
}
}
}
}

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

int u, v, c;
int x, q;

cin >> n >> m;
FWS::init();
while (m --)
{
cin >> u >> v >> c;
FWS::addedge(u,v,c);
}
dijkstra(1); dijkstra(n);
const longs shortest = dij::ds[n];

cin >> q;
while (q --)
{
cin >> x;
auto& ii = FWS::ee[(x-1)<<1];
longs to = dij::ds[ii.v] + dij::dt[ii.u] + ii.w;
if (to < shortest) cout << "YES" << endl;
else cout << "NO" << endl;
}

return 0;
}

一直抄板子一直爽

E - 字符串

这个题目做的有点憋屈……最后一个多小时几乎都砸在这个题目上:我一直觉得这个题目是KMP,然而我对于KMP的next数组理解的并没有那么的透彻(除了板子一无所有);最后就演变成了对着log打出来的next数组找规律,嗯……找规律……属实离谱(

然而,标答给的算法是二分答案+DP——看似奇妙又显而易见,啊这……

我也许是受了吹水群里一波接着一波的KMP的影响吧。但是这个题目真的不能使用KMP吗……就算是不能使用KMP也应该有一个反例来证明才是。我想通了就再这里写清楚好了。

题解分析

显然,这个问题相当于求解:字符串s中有k个相同的子串p,要求使得 x = p.length() 最大化;显然这个x,又具有显而易见的二分单调性——x的极限值之下均可行,以上均不可行;问题转化为寻找简单的验证x是否可行的方法——然而这又可以使用显而易见的DP完成,于是就大概有做这个题的思路了。

那么这个DP具体应该怎么操作呢:直接比较字符串,且不说是不是会暴毙,想想都觉的丑陋== 这个时候就可以使用万能的hash——将所有的长度为m的子串hash化,然后使用map储存hash-dp键值对;具体的操作方法如下:

开dp数组和map:map用来存储长度为x且 hash code 为h的字符串在已经扫描过的部分中最后一次出现的位置,用开头的下标表示;dp[i]的含义是下标i开头的(长度为x)字符串在子串[begin, i + x]中出现的最大次数;知道定义之后,操作就比较的简单了:从头扫描到尾,当扫描的部分长度大于x的时候,就每次将长度为x后缀计算hash放进map中,并且标记它的开头位置;然后计算从i开始的长度为x的子串的哈希:如果这个哈希还没出现在map中,那么它出现了一次,暂且可以标记dp[i] = 1;否则,它可以从上次出现的位置转移过来,这个位置就是被map记录的位置。

然后我们二分这个x,check当子串长度为x时所有字串出现的最大次数是否能够超过k即可;特别注意要特判0——因为0不是一个字符串,上述统计方法无法正常转移,会统计出确定值1.(其实应该是∞)

想想都觉得这个hash-dp十分的诡异……如果这真的是唯一做法那我认了(但其实这题还可以使用后缀数组

我的代码

真的是debug到吐血——这样的经历说明了一件事情:标准是根据算法来的,而不是个人喜好来的== 比如这字符串哈希,一般最好是字符串存储在[1 ... n]的下标,用[L, R]来标记子串比较方便自然。然而我采用经典的[0 ... n)、[L, R)标记法,就会导致一堆情况要特判(

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

using namespace std;
typedef unsigned long long ulongs;

const int N = 2e6+5;

int n, k; char s[N];
int ff[N];

namespace StringHash
{
const int __base = 6151;
const int __offset = 97;
ulongs pow[N], var[N];

int __idx(const char ch)
{
return ch - 'a' + 1;
}

void init(const char* s)
{
pow[0] = 1; var[0] = __idx(s[0]) + __offset;
int n = strlen(s);
for (int i = 1; i < n; ++ i)
{
pow[i] = pow[i - 1] * __base;
var[i] = var[i - 1] * __base + __idx(s[i]) + __offset;
}
}

ulongs getHashCode(int l, int r)
{
if (l == r || !r) return 0ull;
auto __elim = l ? var[l - 1] : 0ull;
return var[r - 1] - __elim * pow[r - l];
}
}

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

auto check = [&](int mid) -> bool
{
if (mid == 0) return true;
using StringHash::getHashCode;
static unordered_map<ulongs, int> map;
int ret = 0, lim = n - mid;
for (int i = 0; i <= lim; ++ i)
{
if (i - mid >= 0) map[getHashCode(i - mid, i)] = i - mid;
ulongs hashcode = getHashCode(i, i + mid);
ff[i] = map.count(hashcode) ? ff[map[hashcode]] + 1 : 1;
ret = max(ret, ff[i]);
}
map.clear();
return ret >= k;
};

cin >> n >> k >> s;
StringHash::init(s);

int ll = 0, rr = n, ans = 0;
check(0);
while (ll <= rr)
{
int mm = ll + rr >> 1;
if (check(mm)) ans = mm, ll = ++ mm;
else rr = -- mm;
}
cout << ans << endl;

return 0;
}

这个代码的上一个版本也AC了,但是使用Valgrind分析发现有一处[-1]的越界访问,就离谱(

F - 林檎树

唔姆……看了下答案,我完全没有想对== 但是出于学习目的,还是把我的一些想法在这里记录一下好了:

首先肯定建树,然后用一个set维护苹果的成熟度和位置;这样每次新建苹果就会变成向set中插入节点,找到所有符合条件的苹果就变成STL的两个bound;求到一个苹果的距离就等于说是带权LCA,在所有的苹果里求一个最小值就好办了;除了带权LCA之外的都可以用STL轻松实现,美滋滋(

看起来十分的美好,但是可能被一些极端的数据卡掉——如果所有的苹果都落在了符合条件的区间内的话,就算题目给了4s也会被活活卡死== 因为没有写这只是推测,但是至少说明这个算法还需要进一步的优化或者说根本就不行。

然而……

78_0_9_S2_2LN9518NZ1DSP.jpg

事实上,当我找了半个小时发现我并没有现成的、完成度比较好的带权LCA板子之后我就放弃写这题了(

题解分析

要想做这个题,首先你要先学会线段树和点分治。明白,这就去学习点分治(

我的代码

后记

虽然这场打的还算是比较顺利的,但是实际上还是并不理想;之后的准备,一方面是要多整一点模板:有了想法却没有优秀的板子支撑实在是太令人心痛了()平时算法学习还是要注意理解——甚至到现在我还是觉得,E题可以通过魔改KMP利用next数组求解==

比赛是打不完的,今晚(明天凌晨)的cf教育场,明天AtCoder和洛谷的公开赛,后天的武大校赛…… 既来之则安之,砥砺前行,尽心尽力完成每一个题目吧。

又及:Typora里的排版到博客上渲染不了内联CSS有些难受……<br/>强制换行就很蠢(




2020-4-11 1:11:11 雨未停

评论