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

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


了解详情 >

七つの海

ひと結び、人を結んで

比赛链接:https://ac.nowcoder.com/acm/contest/12794

非常的垃圾,这一场几乎全部都是水题== 当然还混入了大量说不清道不明的阅读理解一般又臭又长的题面…… 只能说恶心他🐎给恶心开门,恶心到家了()

实况:AK(10/10),Rank=39

PenaltyABCDEFGHIJ
1056++++1+1+1+5+1++

没什么好说的,,直接贴代码好了这将成为目前为止本博客最水题解

题解

A - Binarize It

签到,队友 A 的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int t, n, m, k;
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
int tcase;
read(tcase);
while (tcase--)
{
read(n);
printf("Input value: %d\n%d\n\n", n, int(pow(2, int(ceil(log10(n) / log10(2))))));
}
return 0;
}

虽然有些意义不明的变量(

B - g2g c u l8r

纯字符串暴力题;让我熟悉了在 C++ 中读入整行的一些操作和注意事项

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
signed main()
{
// ios::sync_with_stdio(false);
// std::cin.tie(nullptr);
// std::cout.tie(nullptr);
#if 0
freopen("in.txt", "r", stdin);
#endif
int T, q; cin >> T;
unordered_map<string, string> dict;
string s, t;
while (T --)
{
cin >> s;
getline(cin, t);
int cur = 0, size = t.length();
while (cur < size) if (t[cur] == ' ') ++ cur; else break;
dict[s] = t.substr(cur);
}
cin >> q; getline(cin, s);
while (q --)
{
getline(cin, s);
stringstream ss(s), out;
while (ss >> t)
if (dict.count(t)) out << dict[t] << ' ';
else out << t << ' ';
auto str = out.str();
cout << str << endl;
}
return 0;
}

回想起了刚入坑时在洛谷训练场写红题的恐惧(

C - Tip to be Palindrome

签到;虽然可以考虑一些手段,但是因为数据范围实在是太小了,所以只需要模拟就行了……

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
bool check(int n)
{
s = to_string(n);
for (int i = 0; i < s.length() / 2; i++)
{
int j = s.length() - i - 1;
if (s[i] != s[j])
return false;
}
return true;
}
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
int tcase;
cin >> tcase;
for (int i = 5; i <= 20000; i++)
{
if (check(i))
q.push_back(i);
}
while (tcase--)
{
cin >> n;
int l = ceil(1.0 * n * 1.2);
cout << "Input cost: " << n << endl;
int ans = q[lower_bound(q.begin(), q.end(), l) - q.begin()];
cout << ans - n << " " << ans << endl
<< endl;
}
return 0;
}

上面的代码就是先预处理完了所有的回文,然后根据输入去查找答案。

D - Soccer Standings

运算符重载题,当然前提是你读完了那又臭又长的题面描述:

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
signed main()
{
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#if 0
freopen("in.txt", "r", stdin);
#endif
int n, t, g;
cin >> n;
using team = tuple<int, int, int, int, int, int, int>;
vector<string> ss;
unordered_map<string, int> val;
vector<team> cnt;
const auto init = [&]
{
ss.clear(), val.clear();
cnt.clear();
};
const auto cmp = []
(const team &a, const team &b) -> bool
{
auto &[ano, a1, a0, aw, at, al, apt] = a;
auto &[bno, b1, b0, bw, bt, bl, bpt] = b;
auto ad = a1 - a0, bd = b1 - b0;
if (apt != bpt) return apt > bpt;
else if (ad != bd) return ad > bd;
else if (a1 != b1) return a1 > b1;
else return ano < bno;
};
string s, a, b; int aa, bb;
for (int i = 1; i <= n; ++ i)
{
init();
cin >> t >> g;
while (t --)
{
cin >> s;
ss.push_back(s);
}
sort(ss.begin(), ss.end());
t = ss.size();
for (int i = 0; i < t; ++ i)
val[ss[i]] = i,
cnt.emplace_back(i, 0, 0, 0, 0, 0, 0);
while (g --)
{
cin >> a >> aa
>> b >> bb;
int aaa = val[a], bbb = val[b];
auto &[ano, a1, a0, aw, at, al, apt] = cnt[aaa];
auto &[bno, b1, b0, bw, bt, bl, bpt] = cnt[bbb];
a1 += aa, b0 += aa, b1 += bb, a0 += bb;
if (aa > bb)
{
++ aw, ++ bl;
apt += 3;
}
else if (aa < bb)
{
++ bw, ++ al;
bpt += 3;
}
else ++ at, ++ bt, ++ apt, ++ bpt;
}
sort(cnt.begin(), cnt.end(), cmp);
cout << "Group " << i << ":\n";
for (auto &ii : cnt)
{
auto [no, _1, _0, win, tie, lose, pt] = ii;
cout << ss[no] << ' ' << pt << ' ' << win << ' '
<< lose << ' ' << tie << ' ' << _1 << ' '
<< _0 << endl;
}
cout << endl;
}
return 0;
}

确实,属性并不是都同号的 :-)

E - NIH Budget

本场为数不多的有点技术含量的题目之一——不过是个背包板子;

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
const int N = 1e5 + 5;
int dp[N];
array<pair<int, int>, 4> info[20];

signed main()
{
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#if 0
freopen("in.txt", "r", stdin);
#endif
int n = scanner.nextInt(), d, b;
for (int i = 1; i <= n; ++ i)
{
scanner(d, b);
memset(dp, 0, sizeof(int) * (b + 1));
for (int j = 0; j < d; ++ j)
for (auto &[cost, save] : info[j])
scanner(cost, save);
for (int j = 0; j < d; ++ j)
for (int x = b; x >= 0; -- x)
for (auto &[cost, save] : info[j])
if (x - cost >= 0)
maximize(dp[x], dp[x - cost] + save);
cout << "Budget #" << i << ": Maximum of " << dp[b]
<< " lives saved." << endl << endl;
}
return 0;
}

不会有人不会写背包吧,不会这个人就是我自己吧(逃

F - Interstellar Love

并查集;注意只有一个的星星的连通块不是一个星座

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
const int N = 1100;

namespace DSU
{
int fa[N], siz[N], cnt[N];

void init(int n)
{
for (int i = 0; i <= n; ++ i)
fa[i] = i, siz[i] = 1, cnt[i] = 0;
}

int father(int u)
{return fa[u] == u ? u : (fa[u] = father(fa[u]));}

void join(int x, int y)
{
int fx = father(x), fy = father(y);
if (fx == fy) return void(cnt[fx] ++);
if (siz[fx] <= siz[fy])
fa[fx] = fy, siz[fy] += siz[fx],
cnt[fy] += cnt[fx] + 1;
else fa[fy] = fx, siz[fx] += siz[fy],
cnt[fx] += cnt[fy] + 1;
}
}

signed main()
{
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#if 0
freopen("in.txt", "r", stdin);
#endif
int n = scanner.nextInt();
for (int tt = 1; tt <= n; ++ tt)
{
int s = scanner.nextInt(),
c = scanner.nextInt();
DSU::init(s + 1);
while (c --)
{
int u = scanner.nextInt(),
v = scanner.nextInt();
DSU::join(u, v);
}
bitset<N> star, fix;
for (int i = 1; i <= s; ++ i)
{
auto fa = DSU::father(i);
auto e = DSU::cnt[fa], v = DSU::siz[fa];
if (v <= 1) continue;
star.set(fa);
if (e >= v) fix.set(fa);
}
cout << "Night sky #" << tt << ": " << star.count()
<< " constellations, of which " << fix.count()
<< " need to be fixed." << endl << endl;
}
return 0;
}

G - Plate Spinning

虽然没什么内容但是被恶心到了…… 需要特判当只有一个盘子的时候始终可行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
signed main()
{
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#if 0
freopen("in.txt", "r", stdin);
#endif
int T = scanner.nextInt();
for (int i = 1; i <= T; i++)
{
int n = scanner.nextInt(),
m = scanner.nextInt();
auto t = 1.0 * n * 0.5 * 5;
print("Circus Act ", i, ":\n");
if (n == 1 || t <= 1.0 * m)
println("Chester can do it!\n");
else println("Chester will fail!\n");
}
return 0;
}

然后这一个题就奉献了快两个小时的罚时()

H - The Eternal Quest for Caffeine

除了单程往返,还要考虑源点在中间,路径绕一个环的情况;我最开始的时候就没有考虑那种情况,所以莽了()后来队友给我改成了遍历一个段,就对了(

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
const int N = 16;
array<bitset<N>, N> machine;
bitset<N> ok;

signed main()
{
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#if 0
freopen("in.txt", "r", stdin);
#endif
int n, s, m, t, x;
char state;
for (int T = 1; T; ++T)
{
cin >> n >> s >> m;
if (!n && !s && !m) return 0;
for (auto &ii : machine) ii.reset();
ok.reset();
for (int i = 1; i <= n; ++i)
{
cin >> t;
while (t--) cin >> x, machine[i].set(x);
cin >> state;
if (state == 'Y') ok.set(i);
}
int ans = 0x3f3f3f3f;
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; ++j)
{
bool haveSource = false, flag = false;
bitset<N> tmp;
for (int k = i; k <= j; ++k)
{
tmp |= machine[k];
if (k == s) haveSource = true;
if (ok[k]) flag = true;
}
if (haveSource && flag && tmp.count() == m)
ans = min(ans, (j - i) * 2);
}
cout << "Test case #" << T << ": ";
if (ans < 0x3f3f3f3f) cout << ans << endl << endl;
else cout << "Impossible" << endl << endl;
}
return 0;
}

虽然是队友给我改过的,但是这也算是我过的吧(

I - Pegasus Circle Shortcut

平面几何运算板子题:对着题目嗯模拟就成了

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
namespace Geo {...}

signed main()
{
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#if 0
freopen("in.txt", "r", stdin);
#endif
double cx, cy, sx, sy, tx, ty;
const string ans[] = {"Stick to the Circle.", "Watch out for squirrels!"};
using Geo::point, Geo::number;
const number PI = 3.1415926535897932384626;
cout << fixed << setprecision(8);
for (int T = 1, n; T; ++ T)
{
cin >> cx >> cy >> sx >> sy >> tx >> ty;
if (cx == 0. && cy == 0. && sx == 0. &&
sy == 0. && tx == 0. && ty == 0.) break;
point s(sx, sy), t(tx, ty), c(cx, cy);
point last(sx, sy), now;
number interior = 0;
for (cin >> n; n --;)
{
cin >> now.x >> now.y;
interior += now.distance(last);
last = now;
} interior += t.distance(last);
auto str0 = s - c, str1 = t - c;
auto ang = abs(str0.angle() - str1.angle());
number d = c.distance(s) + c.distance(t);
minimize(ang, 2 * PI - ang);
number circular = d * ang / 2;
bool ok = Geo::compareTo(interior, circular) <= 0;
cout << "Case #" << T << ": " << ans[ok] << endl << endl;
}
return 0;
}

当然,前提是要有靠谱的板子。

J - Lowest Common Ancestor

用数组模拟二叉树,给定两个下标求它们的 LCA 的下标;很显然,用数组模拟二叉树的子节点就是 <<= 1;所以 LCA 显然就是在二进制表示下两个节点下标的公共前缀代表的下标。

问题就是题目给的还是恶心的 16 进制;我队友拿 Python 写过了,但是我尝试拿 C++ 写崩了…… 所以最后屈服于 Java:

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
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
var sc = new Scanner(System.in);
int T = sc.nextInt();
sc.nextLine();
for (int i = 1; i <= T; ++ i)
{
var line = sc.nextLine();
var ab = line.split(" ");
var a = new BigInteger(ab[0], 16);
var b = new BigInteger(ab[1], 16);
var aa = a.toString(2);
var bb = b.toString(2);
int lim = Math.min(aa.length(), bb.length());
int cur = 0;
while (cur < lim &&
aa.charAt(cur) == bb.charAt(cur))
++ cur;
var prefix = aa.substring(0, cur);
var c = new BigInteger(prefix, 2);
System.out.printf("Case #%d: %s\n\n", i, c.toString(16));
}
}
}

🐎的,在 C++ 我都不用 printf,在 Java 里却用的一身的劲儿(

特别注意:因为 ACM 是只保证有 Java 8 的,所以上面的代码过不了编译(

后记

没什么好说的…… 只能说这样的比赛差不多得了,好自为之()

H10~JZ__G1_PZGUP1YLLUJ2.jpg

但是打的还是有那么一点点捞;要是模拟题写的这么慢准度这么差那我也差不多得了(

评论