翘课报名了CCSP2019的比赛，上次去分赛区觉得还挺好玩的这个比赛，但是由于比较菜不会读二进制文件也不开多线程就比较自闭。这次做点准备吧。
T1 简单的BFS不难发现每一轮每个人走到安全区就不会掉血了，所以每个人的终点其实是安全区。然后从安全区开始往外走就好了。注意不能斜着走左右两侧都是障碍物的。
#include<iostream>
#include<cstdio>
#include<cstring>
#include <queue>
#define ll long long
#define maxn 410
#define maxm 200010
using namespace std;
ll n, m, e, f, h;
ll g[maxn][maxn];
ll pos[maxm][2];
ll val[maxn][maxn];
ll hp[maxm];
struct node {
ll x, y;
} E[maxm];
queue<node> q;
ll xx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
ll yy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
ll Cal(node p1, node p2) {
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
int main() {
freopen("cs.in", "r", stdin);
// freopen(".ans", "w", stdout);
// freopen("C:\\Users\\yanli\\Desktop\\data\\10.in", "r", stdin);
freopen("cs.ans", "w", stdout);
scanf("%lld%lld%lld%lld%lld", &n, &m, &e, &f, &h);
for (ll i = 1; i <= m; i++)hp[i] = h;
ll x, y;
for (ll i = 1; i <= e; i++) {
scanf("%lld%lld", &x, &y);
E[i].x = x;
E[i].y = y;
}
for (ll i = 1; i <= m; i++)
scanf("%lld%lld", &pos[i][0], &pos[i][1]);
while (f--) {
ll rx, ry, r;
scanf("%lld%lld%lld", &rx, &ry, &r);
for (ll i = 1; i <= e; i++)
if (Cal(E[i], node{rx, ry}) <= r * r)g[E[i].x][E[i].y] = 0;
else g[E[i].x][E[i].y] = 1;
memset(val, -1, sizeof(val));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(Cal(node{rx,ry},node{i,j})<=r*r){
q.push(node{i,j});
val[i][j]=0;
}
while (!q.empty()) {
node now = q.front();
q.pop();
for (ll i = 0; i < 8; i++) {
ll nx = now.x + xx[i];
ll ny = now.y + yy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < n && val[nx][ny] == -1) {
if (i == 0 && g[now.x - 1][now.y] && g[now.x][now.y - 1])continue;
if (i == 2 && g[now.x - 1][now.y] && g[now.x][now.y + 1])continue;
if (i == 5 && g[now.x + 1][now.y] && g[now.x][now.y - 1])continue;
if (i == 7 && g[now.x + 1][now.y] && g[now.x][now.y + 1])continue;
val[nx][ny] = val[now.x][now.y] + 1;
if (g[nx][ny] == 0)q.push(node{nx, ny});
}
}
}
for (ll i = 1; i <= m; i++)
hp[i] -= val[pos[i][0]][pos[i][1]];
for (ll i = 1; i <= m; i++) {
scanf("%lld%lld", &x, &y);
pos[i][0] = x;
pos[i][1] = y;
}
}
for (ll i = 1; i <= m; i++)
printf("%lld\n", max(0ll, hp[i]));
return 0;
}
T2 emmmm算是不难的模拟把，我用的是set，常数写的有点大了，2s左右的时间，过几天再加一个优化版本吧（8可能的咕咕咕）。由于两次find点的策略不一样，且不能合起来（应该不能把），所以我开了两个set，然后删点的时候更新其他点的信息。
#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
int n, m;
int r[maxn], c[maxn];
int dl[maxn];
struct node {
int u, r;
bool operator<(node A) const {
if (r != A.r)return r < A.r;
return u < A.u;
}
};
struct Node {
int u, r, c;
bool operator<(Node A) const {
if (r != A.r)return r > A.r;
if (c != A.c)return c > A.c;
return u > A.u;
}
};
set<node> s;
set<Node> ss;
vector<int> G[maxn];
int init() {
int x = 0, f = 1;
char s = getchar();
while (s < '0' || s > '9') {
if (s == '-')f = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = x * 10 + s - '0';
s = getchar();
}
return x * f;
}
void up(int u, int r1, int r2, int c1, int c2) {
auto p1 = (*s.lower_bound(node{u, r1}));
s.erase(p1);
p1.r = r2;
s.insert(p1);
r[u] = r2;
auto p2 = (*ss.lower_bound(Node{u, r1, c1}));
ss.erase(p2);
p2.r = r2;
p2.c = c2;
ss.insert(p2);
r[u] = r2;
c[u] = c2;
}
void del(int now) {
dl[now] = 1;
for (int v:G[now]) {
if (dl[v])continue;
up(v, r[v], r[v] - 1, c[v], c[v] - (r[now] == 2));
if (r[v] == 2) {
for (int k:G[v]) {
if (dl[k])continue;
up(k, r[k], r[k], c[k], c[k] + 1);
}
} else if (r[v] == 1) {
for (int k:G[v]) {
if (dl[k])continue;
up(k, r[k], r[k], c[k], c[k] - 1);
}
}
}
s.erase(node{now, r[now]});
ss.erase(Node{now, r[now], c[now]});
}
bool rule() {
node now = *s.begin();
if (now.r <= 1) {
printf("%d\n", now.u);
del(now.u);
for (int v:G[now.u]) {
if (dl[v])continue;
del(v);
}
return 1;
}
return 0;
}
void go() {
del((*ss.begin()).u);
}
int main() {
freopen("set.in", "r", stdin);
// freopen("C:\\Users\\yanli\\Desktop\\ccsp\\data\\set\\set6.in", "r", stdin);
freopen("set.out", "w", stdout);
n = init();
m = init();
int u, v;
for (int i = 1; i <= m; i++) {
u = init();
v = init();
G[u].push_back(v);
G[v].push_back(u);
r[v]++;
r[u]++;
}
for (int u = 1; u <= n; u++)
if (r[u] == 2) {
for (int v:G[u])c[v]++;
}
for (int i = 1; i <= n; i++) {
s.insert(node{i, r[i]});
ss.insert(Node{i, r[i], c[i]});
}
for (int i = 1; i <= n && s.size(); i++) {
while (!rule())go();
}
return 0;
}T3 T4 T5 待做
Up一下T3
首先想到算法优化 HWNN降到HWN，然后套一个多线程。看std还用了指令向量优化，好快啊。
赛后
啊济南打铁王
先说一下题目质量还是很不错，很多新颖的题目也比较好玩。
开场先浏览了一下题面，似乎没有很明显的多线程的题。
A题过了之后，B题花了一些时间，午饭后过了。
然后看榜，C题没什么动静（其实后来才知道大家都在努力写），D题有些人得了些分。读完题面，哇，优化题，os学过似乎，先来先服务、时间片轮转什么的，好！稳一点，先写个FIFO试试水。
然后卒，最后不知怎么的那个5分，转战第五题
这题我觉得我太搞笑了。题面读的有点草，什么图形化巴拉巴拉大概就是帮助理解流水线什么的吧，我就直接上手把。amulb直接写了一句汇编之后过了。发现和x86的指令集差别挺大，但是好像和arm指令集有点像，还给了手册。emmmm 当时觉得读读手册，找找跳转指令什么的把fib过了应该不成问题。
然后手册读完了感觉还是不太会用，里面例子很少。无聊翻翻优盘，发现了计算机系统的PPT！“arm基础指令.pptx”！！！！哇，稳了啊，优盘牛逼！！
“对不起，无法打开该文件”。。。。。。
咳咳咳，我投降，吃饭饭
吃完晚饭，哇这C题怎么都过穿了啊，赶紧做。
先写49分稳一点。
好，下面写写两个表的，还有2个小时，最起码再拿23分稳住金。
写写写 49 49 49 20:30+
哇不应该啊 卧槽这xxx . xxx是个什么玩意 哇这他么 改改改
最后没改完投降了
果然银牌第一页，哎 还是计算机系统的基础知识不太够 还有题目读的不太仔细
（赛后问：“哇你们怎么那么厉害，排序的汇编都能自己写出来” “嗯？他不是给了gcc到汇编的指令了吗” “？？？？？？”）
京公网安备 11010502036488号