CSP-J 2019复赛分析

【CSP-J 2019 】复赛分析

前言(？？？？)

总的来说，这次复赛感觉考的很不满意，至于原因，感慨万分！关键是：期中考试了！偏偏是这个时候！

- 由于我是一个初二的蒟蒻，所以考试前先定了一个目标：前两道题AC（可是现实与想象就是差INF），后两道题写个AC自动机或随机数什么的，不然就打暴力骗点分什么的。怀着这样美好的心情出发。
- 我自我感觉良好—— AK IOI

DAY -4

坐标：育才成功学校教学楼七楼
比赛前的我们开始准备放松心态：

DAY -2

坐标：育才成功学校教学楼七楼
心里想：调整调整心态吧，什么都别干了，就当放了半天假。
事实上：卧槽——还有N道题没有做......
这几天，我们将这几年的初赛题都一本正经的刷了几遍(顺便将期中考试的作业都过了几遍)

DAY 1

坐标：？？
今天考试了！

祝我：

cpp
while(1){
rp+=inf;
}

T1:数字游戏

这道题绝对是千万年以来最简单的题。
官方代码：

cpp

#include <iostream>
#include <cstdio>
using namespace std;

int main() {

freopen("number.in", "r", stdin);
freopen("number.out", "w", stdout);
string s;
cin >> s;

int ans = 0;
for (int i = 0; i < 8; ++i)
if (s[i] == '1')
ans ++;
cout << ans << endl;
fclose(stdin);
fclose(stdout);
return 0;
}

T2:公交换乘

花了一个多小时时间去调试，所以我的代码有点......还是看官方的吧：

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
struct Node
{
long long type, price, t;
} a[200000];

vector<Node> v;

int main()
{

freopen("transfer.in", "r", stdin);
freopen("transfer.in", "w", stdout);

int n;

cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i].type >> a[i].price >> a[i].t;

long long sum = 0;
for (int i = 1; i <= n; ++i)
{

if (a[i].type == 0)
{
sum += a[i].price;
v.push_back(a[i]);
}
else
{
bool flag = false;
for (int j = 0; j < v.size(); ++j)
{

if (a[i].t - v[j].t <= 45)
{
if (a[i].price <= v[j].price)
{
flag = true;
v.erase(v.begin() + j);
break;
}
}
else
{
v.erase(v.begin() + j);
j--;
}
}
if (!flag)
sum += a[i].price;
}
}
cout << sum << endl;

fclose(stdin);
fclose(stdout);
return 0;
}

T3：纪念品

背包问题。
官方代码：

cpp

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int t, n, m;
int f[20000];
int a[200][20000];
int main()
{

freopen("souvenir.in", "r", stdin);
freopen("souvenir.out", "w", stdout);

cin >> t >> n >> m;

for (int i = 1; i <= t; ++i)
for (int j = 1; j <= n; ++j)
cin >> a[i][j];

for (int i = 2; i <= t; ++i) {

memset(f, 0, sizeof(f));
for (int j = 1; j <= n; ++j) {
for (int k = a[i - 1][j]; k <= m; k++) {
f[k] = max(f[k], f[k - a[i - 1][j]] + a[i][j] - a[i - 1][j]);
}
}
m += f[m];
}
cout << m << endl;
fclose(stdin);
fclose(stdout);
return 0;
}

T4：加工零件

图论，最短路问题。
官方代码：

cpp
#include <bits/stdc++.h>
using namespace std;
struct Edge
{
int u, v, next;
} e[400000];
int n, m, u, v, tot, query, f[200000], d[200000][2];
bool used[200000];
queue<int> q;
void add(int u, int v)
{
tot++;
e[tot].u = u;
e[tot].v = v;
e[tot].next = f[u];
f[u] = tot;
}
int main()
{
freopen("work.in", "r", stdin);
freopen("work.out", "w", stdout);
cin >> n >> m >> query;
for (int i = 1; i <= m; ++i)
{
cin >> u >> v;
add(u, v);
add(v, u);
}
memset(d, 0x3f, sizeof(d));
memset(used, false, sizeof(used));
d[1][0] = 0;
used[1] = true;
q.push(1);
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = f[u]; i > 0; i = e[i].next)
{
int v = e[i].v;
if (d[u][0] + 1 < d[v][1])
{
d[v][1] = d[u][0] + 1;
if (!used[v])
{
used[v] = true;
q.push(v);
}
}
if (d[u][1] + 1 < d[v][0])
{
d[v][0] = d[u][1] + 1;
if (!used[v])
{
used[v] = true;
q.push(v);
}
}
}
used[u] = false;
}
for (int i = 1; i <= query; ++i)
{
int a, l;
cin >> a >> l;
if ((d[a][0] <= l && l % 2 == 0) || (d[a][1] <= l && l % 2 == 1))
printf("Yes
");
else
printf("No
");
}
fclose(stdin);
fclose(stdout);
return 0;
}

结果，你知道吗，心态爆炸的我在赛场上......

总结&感想

这次参加联赛，看了下往年的题目和分数线，发现只要该拿的分不挂就可以拿到。可是今年在考场上的感觉题目比往年似乎更难（一下有两道黑题），暴力都没能打出来。部分分好像比往年更多，拿到150+还是很轻松的。