CSP 2021 总结

CSP 2021 总结

PJ

开题顺序:1342

应该先做 T2 ,导致我 T2 直接看错

T1、T3

T1 :直接推规律即可,考场的想法应该正确

T3 :好家伙直接 map 走起

T2

最崩溃的来了 :\(5000\times8000=4e7\) 是吧,愣是给我看成了 \(4e8\)

然后想打插入排序(正解)骗分,发现插入排序不对,就直接 sort

。。。。。。。。

。。。。。。。。

。。。。。。。。

心 态 炸 裂

退役吧

T4

考试时想到双链表,过了小数据,但没过大数据

浪费了太多时间,导致了 T2 直接挂

总结

考试的心态不好,太急了,连 T1 都要好久才沉下心来想

今年的 pj 比较水,没有说什么没想到。

但是代码实现弱 —— T4 挂了,并浪费大量时间

眼花缭乱——四千万看成四亿

TG

T1

直接枚举廊桥+堆,暴力 \(O(nm\log n)\)

正解:设 \(c_i\) 表示 \(i\) 个廊桥能停靠的飞机,则 \(ans=\max c_{1,i}+c_{2,n-i}\)

考虑到每一个廊桥加入都会使得飞机可以停靠。

即 \(c_i=c_{i-1}+x\) , 因为 \(c_0=0\) ,于是可以通过已知 \(c_{i-1}\) 推出 \(c_i\)

考虑求 \(x\) ,因为先到先得,原有的廊桥是被占满的,于是新加的廊桥只会影响没有停廊桥的飞机

模拟,若当前飞机停靠的结束时间是 \(t\) ,每次查询停靠开始时间最接近 \(t\) 的停靠,用一个 set 即可

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m1,m2,c1[N],c2[N],ans;
struct rg {
	int l,r;
    bool operator <(rg A) const {
        return l<A.l;
    }
}x[N],y[N];
set<rg>S;
set<rg>::iterator it;
int main() {
    freopen("airport.in","r",stdin);
    freopen("airport.out","w",stdout);
	scanf("%d%d%d",&n,&m1,&m2);
	for(int i=1;i<=m1;i++)scanf("%d%d",&x[i].l,&x[i].r);
	for(int i=1;i<=m2;i++)scanf("%d%d",&y[i].l,&y[i].r);
	sort(x+1,x+m1+1);
	sort(y+1,y+m2+1);
    S.clear();
    for(int i=1;i<=m1;i++)S.insert(x[i]);
    for(int i=1,vl,p;i<=n;i++) {
        vl=p=0;
        while(1) {
            it=S.lower_bound((rg){p,0});
            if(it==S.end())break;
            ++vl,p=it->r,S.erase(it);
        }
        c1[i]=c1[i-1]+vl;
    }
    S.clear();
    for(int i=1;i<=m2;i++)S.insert(y[i]);
    for(int i=1,vl,p;i<=n;i++) {
        vl=p=0;
        while(1) {
            it=S.lower_bound((rg){p,0});
            if(it==S.end())break;
            ++vl,p=it->r,S.erase(it);
        }
        c2[i]=c2[i-1]+vl;
    }
    for(int i=0;i<=n;i++)
        ans=max(ans,c1[i]+c2[n-i]);
	printf("%d",ans);
} 

T2

区间 dp ,想到后直接放弃

T3

大模拟,对于第一个是 \(L\) 或 \(R\) 分类讨论

问题简化为两个栈,如何轮流弹出栈顶使序列是个回文序列

可通过奇怪证明,发现若能弹出则一定可以弹出。

于是按照字典序枚举情况即可

考场就想到了正解,但是一些奇怪的错误被 hack 了

。。。。。。。。

。。。。。。。。

。。。。。。。。

心 态 炸 裂

退役吧

题解:这里可以把栈变成双端队列,每次弹出一对相同的数,组成回文

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int T,n,x[N<<1],fl,p,ans[N<<1];
struct que {
    int q[N<<1],l,r;
    inline void clear() { l=1,r=0; }
    inline void push(int a) { q[++r]=a; }
    inline int Fr() { return q[l]; }
    inline int Bk() { return q[r]; }
    inline bool empty() { return l>r; }
    inline void Pf() { ++l; }
    inline void Pb() { --r; }
    inline int Sz() { return r-l+1; }
}A,B;
void make(int op) {
	int p1=1,p2=n;
	if(op==1)++p1;
	else --p2;
    A.clear(),B.clear();
	for(int i=p-1;i>=p1;i--)A.push(x[i]);
    for(int i=p+1;i<=p2;i++)B.push(x[i]);
    for(int i=2;i<=n/2;i++) {
        if(A.empty() && B.empty())break;
        if(B.empty()) {
            if(A.Fr()!=A.Bk())
                return;
            ans[i]=ans[n-i+1]=1;
            A.Pb(),A.Pf();
        } else if(A.empty()) {
            if(B.Fr()!=B.Bk())
                return;
            ans[i]=ans[n-i+1]=2;
            B.Pb(),B.Pf();
        } else {
            if(A.Sz()>1 && A.Fr()==A.Bk())
                ans[i]=ans[n-i+1]=1,A.Pb(),A.Pf();
            else if(A.Bk()==B.Fr())
                ans[i]=1,ans[n-i+1]=2,A.Pb(),B.Pf();
            else if(A.Fr()==B.Bk())
                ans[i]=2,ans[n-i+1]=1,A.Pf(),B.Pb();
            else if(B.Sz()>1 && B.Fr()==B.Bk())
                ans[i]=ans[n-i+1]=2,B.Pb(),B.Pf();
            else return;
        }
	}
	fl=1;
}
int main() {
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&n),n<<=1;
		for(int i=1;i<=n;i++) {
			scanf("%d",&x[i]);
		}
		ans[n]=1;
		fl=0;
		ans[1]=1;
		for(int i=2;i<=n;i++)
			if(x[i]==x[1]) {
				p=i; break;
			}
		make(1);
		if(!fl) {
			ans[1]=2;
			for(int i=1;i<n;i++)
				if(x[i]==x[n]) {
					p=i; break;
				}
			make(n);
		}
		if(!fl)puts("-1");
		else {
			for(int i=1;i<=n;i++) {
				if(ans[i]==1)putchar('L');
				else putchar('R');
			}
			puts("");
		}
	}
}

T4

What?

看懂大意后直接再见

总结

很好——暴力没有挂,至少能有分

我* —— 实现上的失误,还是代码实现能力差

大总结

  1. 代码实现能力弱
  2. 思维不够发散,一些结论不难的题想不到
  3. 考试的心态不够好,过于心急,导致半天一筹莫展

过去的都过去了,希望今年 noip 能拿到 50 分

上一篇:C语言文件操作


下一篇:理论八:如何用迪米特法则(LOD)实现“高内聚、松耦合”?