【游记】2021csp复赛

明天就是2021csp复赛了，有点小紧张

。。。。

朝花夕拾

没有匹配到noisemaker,但是有匹配到xxs
没有杀人电梯
没有空调外机 滴水
有匹配到女OIer
~~黄中好像是最寒酸的（只有两个人，别的学校都五六个十几个的）~~
始终没有窜稀 然而xs窜了，还是在考试的时候窜的。他还问监考老师有没有纸，还被监考老师嘲笑了

来点图

RP++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

赛后总结

注意事项

1.考前先看桌面上的注意事项，了解要干什么，不能干什么。
2.密码公布时，先解压试题
- Linux 用unrar 解压文件名.rar ~~考前我还临时突击了一下。。。~~
- windows 右键双击以下就行
3.别紧张
4.先浏览题目，所有题都想一想有没有思路，按自己认为的难度顺序写题目（不一定是官方的题目顺序）
5.所有题都要打暴力对拍，就算想到了正解，就算只会写暴搜，也要手动构造数据检测
6.多组数据一定要初始化，不然很有可能爆0 ~~这次就爆0了~~
7.最后的时间一定要检查文件名是否正确，freopen是否正确，是否把调试时的输出注释了，数组是否太大了，编译是否能过
8.考完放轻松，暴力能打出来已经很不错了

补一下代码

蒟蒻S组的题根本写不来

T1 airport

40分暴力分已经是我的极限了

#include <bits/stdc++.h>

#define X first

#define Y second

#define to_max(x, y) (x < y ? x = y: 0)

// #define debug

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

PII a[N], b[N];

int res1[N], res2[N];

inline char GET_CHAR() {

static char buf[N], *p1 = buf, *p2 = buf;

return p1 == p2 && (p2 = (p1 = buf) +

fread(buf, 1, N, stdin), p1 == p2) ? EOF: *p1 ++;

}

template<class T> inline void read(T &x) {

x = 0; int f = 0; char ch = GET_CHAR();

while (ch < '0' || ch > '9') {

f |= (ch == '-'); ch = GET_CHAR();

}

while (ch >= '0' && ch <= '9') {

x = (x << 1) + (x << 3) + (ch ^ 48);

ch = GET_CHAR();

}

x = f ? -x: x;

}

void work(PII a[], int n, int m, int res[]) {

priority_queue<PII, vector<PII>, greater<PII>> p;

表示已经有飞机的廊桥

X--->飞机离开的时间

Y--->廊桥的编号

priority_queue<int, vector<int>, greater<int>> q;

表示当前是空的廊桥

for (int i = 1; i <= n; ++ i) q.push(i);

for (int i = 1; i <= m; ++ i) {

while (p.size() && p.top().X <= a[i].X) {

如果一个廊桥中的飞机可以出

则空出这个廊桥

q.push(p.top().Y);

p.pop();

}

如果有空闲的廊桥则将当前的飞机安排到编号最小的飞机上

if (q.size()) {

int t = q.top(); q.pop();

++ res[t];

p.push({a[i].Y, t});

}

for (int i = 1; i <= n; ++ i) res[i] += res[i - 1];

}

int main() {

int n, m1, m2;

read(n), read(m1), read(m2);

for (int i = 1; i <= m1; ++ i) read(a[i].X), read(a[i].Y);

for (int i = 1; i <= m2; ++ i) read(b[i].X), read(b[i].Y);

sort(a + 1, a + 1 + m1);

sort(b + 1, b + 1 + m2);

work(a, n, m1, res1);

work(b, n, m2, res2);

int res = 0;

for (int i = 0; i <= n; ++ i) to_max(res, res1[i] + res2[n - i]);

printf(%d\n, res);

}

T2 bracket

这题怎么想都不会写，，，（题目没看懂，本来有15分暴力分）

看题解应该是区间dp

就贴一个xs的15pts的暴力好了

#include<bits/stdc++.h>

using namespace std;

const int N=510,M=1e9+7;

typedef long long ll;

int n,k;

string s;

char now[N];

vector<char> add;

int cnt=0;

bool check(){

if(now[0]=='*'||now[n-1]=='*') return 0;

vector<char> kuo,youu;

int xin=0;

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

if(now[i]=='('){

xin=0;

kuo.push_back(now[i]);

if(now[i+1]=='*') youu.push_back(1);

else youu.push_back(0);

}

else if(now[i]=='*'){

xin++;

if(xin>k) return 0;

}

else{

xin=0;

if(kuo.empty()) return 0;

kuo.pop_back();

if(now[i-1]=='*'&&youu.back()){

for(int j=i-1;now[j]!='(';j--){

if(now[j]==')') return 0;

}

youu.pop_back();

}

if(!kuo.empty()) return 0;

return 1;

}

ll dfs(char ss){

add.push_back(ss);

if(add.size()==cnt){

for(int i=0,j=0;i<n;i++){

if(s[i]!='?') now[i]=s[i];

else now[i]=add[j++];

}

// for(int i=0;i<n;i++) printf(%c,now[i]);

// cout<<\n;

if(check()){

add.pop_back();

return 1;

}

else{

add.pop_back();

return 0;

}

ll ans=((dfs('(')+dfs(')'))%M+dfs('*'))%M;

add.pop_back();

return ans;

}

int main(){

//freopen(bracket.in,r,stdin);

//freopen(bracket.out,w,stdout);

scanf(%d%d,&n,&k);

cin>>s;

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

if(s[i]=='?'){

cnt++;

}

printf(%lld,((dfs('(')+dfs(')'))%M+dfs('*'))%M);

return 0;

}

T3 palin

100

101

102

103

104

105

106

107

108

109

110

111

112

113

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int v[N];

char ans[N], cur[N];

struct Deque {

int s[N], hh, tt;

inline int ft() {return s[hh];}

inline int bk() {return s[tt - 1];}

inline void pushbk(int x) {s[tt ++] = x;}

inline void pushft(int x) {s[-- hh] = x;}

inline void popbk() {-- tt;}

inline void popft() {++ hh;}

inline void cr() {hh = tt = 0;}

inline bool empty() {return hh >= tt;}

inline int size() {return tt - hh;}

inline void debug() {

for (int i = hh; i < tt; cout << s[i ++] << ' ');

puts();

}

} a, b;

int see(int l, int r, int val) {

for (int i = l; i <= r; ++ i)

if (v[i] == val)

return i;

return -1;

}

bool pan(int n) {

int id = 1;

while (id <= (n << 1) && cur[id] == ans[id]) ++ id;

return id <= (n << 1) && cur[id] < ans[id];

}

void check(int n) {

int now = 2;

while (true) {

#ifdef DEbug

cout << NOW_is_debug: << now << endl;

a.debug(), b.debug();

#endif

if (a.empty() && b.empty()) break;

else if (b.empty()) {

if (a.ft() != a.bk()) {

cur[1] = 'Z'; return;

}

cur[now] = cur[n * 2 - now + 1] = 'L';

a.popbk(), a.popft();

} else if (a.empty()) {

if (b.bk() != b.ft()) {

cur[1] = 'Z'; return;

}

cur[now] = cur[2 * n - now + 1] = 'R';

b.popft(), b.popbk();

} else {

if (a.ft() == a.bk() && a.size() > 1) {

cur[now] = cur[2 * n - now + 1] = 'L';

a.popft(), a.popbk();

} else if (a.bk() == b.ft()) {

cur[now] = 'L';

cur[2 * n - now + 1] = 'R';

b.popft(), a.popbk();

} else if (b.bk() == a.ft()) {

cur[now] = 'R';

cur[2 * n - now + 1] = 'L';

a.popft(), b.popbk();

} else if (b.bk() == b.ft() && b.size() > 1) {

cur[now] = 'R';

cur[2 * n - now + 1] = 'R';

b.popft(), b.popbk();

} else {

cur[1] = 'Z'; return;

}

++ now;

}

int main() {

int T;

scanf(%d, &T);

while (T --) {

int pos, n;

ans[1] = 'Y';

scanf(%d, &n);

for (int i = 1; i <= n * 2; ++ i) scanf(%d, v + i);

a.cr(), b.cr();

pos = see(2, n * 2, v[1]);

for (int i = pos - 1; i >= 2; -- i) a.pushbk(v[i]);

for (int i = pos + 1; i <= n * 2; ++ i) b.pushbk(v[i]);

cur[1] = 'L';

cur[n * 2] = 'L';

check(n);

if (pan(n)) {

for (int i = 1; i <= n * 2; ++ i) ans[i] = cur[i];

}

a.cr(), b.cr();

pos = see(1, n * 2 - 1, v[n * 2]);

for (int i = pos - 1; i; -- i) a.pushbk(v[i]);

for (int i = pos + 1; i <= n * 2 - 1; ++ i) b.pushbk(v[i]);

cur[1] = 'R';

cur[n * 2] = 'L';

check(n);

if (pan(n)) {

for (int i = 1; i <= n * 2; ++ i) ans[i] = cur[i];

}

// for (int i = 1; i <= n * 2; ++ i) printf(%c, ans[i]);

// puts();

if (ans[1] == 'Y') puts(-1);

else {

for (int i = 1; i <= n * 2; ++ i) printf(%c, ans[i]);

puts();

}

return 0;

}

T4 traffic

黑题就nm离谱

【游记】2021csp复赛

朝花夕拾

来点图

RP++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

赛后总结

注意事项

补一下代码

T1 airport

T2 bracket

T3 palin

T4 traffic

发表回复 取消回复

发表回复取消回复