2019正睿CSP-S模拟赛十连测day7

今天上午刚考完初赛，全员90+，就只有我是80（有可能80-？），慌得一匹，洛谷讨论一面又有一堆人估分比我高，还问有没有救，我原地自闭。教练说一星期后才能出分数线，那我这一个星期看来都要在自闭中度过了。

今天这场比赛就是在自闭中度过的，感觉没能很好地集中精力做题，一直在想初赛（也许集中精力也不能打上去？），最后的分数是

100+50+0(期望10)=150(rank=25)

T1感觉还是比较送的，乱搞之中出正解，玩了玩搞了搞终于在一个小时之后弄了出来，T2有一个一眼的递归式，写了个记忆化上去，T3一看根本连思路都没有，直接自爆了。

link to this contest

A. dls的生日礼物

• 首先判掉无解的情况，就是存在三个区间互相有交
• 现在对于任意一个位置都最多只会被两个区间覆盖，每个联通块只能相间分布，两种情况，并且与其它联通块相独立，于是答案就是$2^{联通块个数}$

 1 #include<bits/stdc++.h>
 2 #define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
 3 #define For(i,a,b) for (register int i=(a);i>=(b);i--)
 4 #define mem(i,j) memset(i,j,sizeof(i))
 5 #define GO(u) for (register int j=f[u];j!=-1;j=nxt[j])
 6 #define fi first
 7 #define se second
 8 #define pb push_back
 9 #define MP make_pair
10 #define pii pair<int,int>
11 using namespace std;
12 typedef long long ll;
13 const int N=2e6+5;
14 const int mod=998244353;
15 int n,ans=1,a[N],len=0,t[N],maxr;
16 struct data
17 {
18     int l,r;
19 }f[N];
20 bool cmp(const data x,const data y) 
21 {
22     if (x.l==y.l) return x.r<y.r;
23     return x.l<y.l;
24 }
25 inline int read()
26 {
27     int x=0,f=1;
28     char c=getchar();
29     while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
30     while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
31     return f*x;
32 }
33 inline void write(int x)
34 {
35     if (x<0) putchar('-'),x=-x;
36     if (x>9) write(x/10);
37     putchar(x%10+'0');
38     return;
39 }
40 inline int val(int x) {return lower_bound(a+1,a+len+1,x)-a;}
41 inline void no()
42 {
43     printf("0\n");
44     exit(0);
45 }
46 inline int pan()
47 {
48     FOR(i,1,n) t[f[i].l]++,t[f[i].r]--;
49     FOR(i,1,len) t[i]+=t[i-1];
50     FOR(i,1,len) if (t[i]>2) return 1;
51     return 0;
52 }
53 int main()
54 {
55 //    freopen("data.in","r",stdin);
56 //    freopen("myans.out","w",stdout);
57     n=read();
58     FOR(i,1,n) f[i].l=read(),f[i].r=read(),a[++len]=f[i].l,a[++len]=f[i].r;
59     sort(a+1,a+len+1);
60     len=unique(a+1,a+len+1)-a-1;
61     FOR(i,1,n) f[i].l=val(f[i].l),f[i].r=val(f[i].r);
62     if (pan()) no();
63     sort(f+1,f+n+1,cmp);
64     maxr=0;
65     FOR(i,1,n)
66     {
67         if (f[i].l>=maxr) ans=1LL*ans*2%mod,maxr=f[i].r;
68         else maxr=max(maxr,f[i].r);
69     }
70     write(ans);
71     return 0;
72 }
73 /*
74 9
75 14 18
76 13 15
77 16 17
78 1 3
79 2 5
80 4 7
81 6 8
82 9 10
83 11 12
84 */

View Code

 

明天再改，不能gu