模拟赛2总结

题目

比赛经历

开局听说是看谁破百请吃饭的毒瘤题集
不愧是tkj出得题
(后来听栋老师说,都是煞笔题)

先看t1,fff是什么东西?狗狗协会?
因为有spj,尝试找突破口
手推不出-1的情况,尝试用rand帮我,所以码了个暴力,结果n到25也搞不出-1的点
看来可能根本就没有-1的情况了
那感觉就没什么突破口了
看下一题

天啊看到这种题面和排序有关的题目就虚
因为以前遇到过几次,感觉都和”冒泡排序”有关
果不其然,我这种不会冒泡排序的人虚死了
看下一题

金坷垃?没有任何思路
感觉可能要计算几何,或者扫描线之类的东西
反正不会……

难道这把就要挂机了?
好像很多人都是这样……各个都说不想交了,直接讲题什么的,毫无耐心
现在想想好像只有第二题可以搏一搏了

这种快排好奇特啊
能不能直接先把do while的那个跑一跑,然后枚举每个点,
看看后面有多少个比它小的(逆序对贡献),然后如果有再+1?
这个加入离散化后,可以用树状数组维护

发现过不了大样例啊,对拍一下试试吧
2h过去了……发现暴力超级难打
不过也不是虚度,因为通过模拟分段的无数细节,对分段性质理解加深了

然后我发现空间炸的一匹,vector也没有用(因为大数据非常良心,是一个dfs链状结构)
所以就放弃出大数据的希望了,用来对拍吧

果然逆序对是错误的
主要是两个原因:循环先执行再判断、执行复杂度直接算是当前区间长度

怎么办呢
想着交个暴力算了

然后,突然灵光一现,发现可以改良
因为每一次的复杂度贡献是按照长度来的,然后每个分段,其实就是由
【在该数后面的数中比当前小,而且最远那个】和当前,包围起来的
此时因为查错,我右边的备用小数据中已经有差不多10个了
发现每一个都满足这个性质(一定要先跑一次,单循环冒泡,这样子分段才是明确的)

然后发现这是一个平方级别的做法,不知道能拿多少分
先打了先把,很好改
试试大样例

??居然过了??
当时就激动得一匹
因为至少做法正确性没有问题
主要还是速度太慢

想办法优化
数据结构中好像只有具备结构体能力的splay能搞
但当时只有20min了!
以我的码力,这是不可能的

咦考虑一个数组(早就离散化了),存下最后那个?那询问还要按值找
哦不对是可以用线段树维护最大值的,如果保存距离的话

当时还剩15min
火速开始码
他们已经打算交了

那几分钟,我的心跳的好快好快
手指尖在键盘间笨拙地跳舞
熟悉的单点修改区间询问线段树啊,如果码出来,就有ac的希望了
那段时间好漫长,但没想到还是打完了
途中还差点被没看懂的编译错误卡住,现在想想真的好险

最后还是打完了,顺利过了大样例
然后就去吃饭了
心里虚的一匹
主要是时间太紧了,要不然能对拍一下就好了
现在回想起来,还是在暴力上花费太长时间了,虽然那可能是想出正解的基础

这些东西现在回想起来,感觉也很难说清楚吧
其实运气成分还是很大比例的
而且我这速度,后面的发展也很虚啊
三道题,用全部时间,只能做出一道题

吃饭途中得喜报
还是顺利ac了
感谢上帝……
上一次拿rk1已经是省选前了……
只是,没有人和我一样兴奋
都对自己很失望吗
不过这种东西,风水轮流转吧大概
像我上次cf,被吊锤,晚上也是难受的很

————在断网的中午,胡思乱想

T1-Analysis

请先思考后再展开

这是一个非常奇妙的做法
首先把情侣之间用无向边连接,然后把2i-1和2i连接
这样,所有环因为必定是情侣边和相邻边交替的,而且出发边和结束边一定不一样(度只有2)
所以只有偶环,也就是说是个二分图
所以就可以愉快地染色了

windows本地栈,63000左右
如果不是linux,可以考虑手动模拟

T1-Code-Std

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
const int MAXN=110000;
int hou[MAXN*2];
struct Edge
{
int y,g;
}e[MAXN*4];
int ln=0;
void ins(int x,int y)
{
ln++;
e[ln].y=y;e[ln].g=hou[x];
hou[x]=ln;
}
int col[MAXN*2];
void dfs(int x,int now)
{
col[x]=now;
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(!col[y]) dfs(y,3-now);
}
}
int a[MAXN],b[MAXN];
void main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i],&b[i]);
ins(a[i],b[i]);ins(b[i],a[i]);
}
for(int i=1;i<=n;i++) ins(2*i-1,2*i),ins(2*i,2*i-1);
for(int i=1;i<=2*n;i++) if(!col[i]) dfs(i,1);
for(int i=1;i<=n;i++) printf("%d %d\n",col[a[i]],col[b[i]]);
}
};
int main()
{
mine::main();
}

T2-Analysis

请先思考后再展开

原题 Usaco2018 Open Out of Sorts
Luogu4372
Bzoj5277

现在冷静想一想,发现我傻了,根本没有必要用线段树这种这么长的东西
因为已经离散化了,直接用数组,维护最后位置,然后搞一个【前缀最大值】就好了
这要是因为我们要维护的是位置,而这种东西可以通过比较直接确定在不在后面
然后前缀最大值这种东西,当时太紧张,再加上原本的做法是需要动态维护的,所以就没跳出来
当然复杂度没有变化

师兄的做法没看懂,不管了反正不一样

UP:讲课的时候被d飞了
8
6 1 3 2 4 5 2 4
答案是19
虽然答案一样,但画出来的线段完全不对应
(据akc研究后说,它的总数值,代表了某种总贡献,只是神仙地把操作后移了)

去膜了发官方题解
发现可以这样考虑:
对于所谓的快排下去递归冒泡,其实和对整个序列冒泡是等效的
那么考虑每个元素的贡献,就是它左右两边的分隔符都出现之前的时间长度
注意:

  1. 如果在最开始的时候,它就是单个元素,那么也会被统计一次
  2. 枚举元素的时候,是按照排序后的位置来找左右两边的

那么现在问题转化为计算n-1个分隔符出现的时间
对于在i和i+1之间那个分隔符,它出现时,序列前i个元素已经在其前面了
那么现在的关键就是第i大(稳定排序下)那个元素的位置r,要多久才能到i
显然现在位于i的那个元素,一定比位于r的那个要大,否则前面已经足够了
因为更大,那么每次冒泡,这个泡i一定会把r给换过来,也就是说每次冒泡往前一位
所以说从r到i的时间恰恰是r-i

T2-Code-Old

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
int qread()
{
int sum=0;
char c=getchar();
while(c<'0' or c>'9') c=getchar();
while(c>='0' and c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
const int MAXN=110000;
int n;
int a[MAXN];
struct Nod
{
int d,p;
}s[MAXN];
bool cmp(Nod a,Nod b) {return a.d<b.d;}
int rx=0;
void lsh()
{
sort(s+1,s+n+1,cmp);
for(int i=1;i<=n;i++)
{
if(i==1 or s[i-1].d!=s[i].d) rx++;
a[s[i].p]=rx;
}
}
struct Meg
{
int lc,rc;
int mx;
}p[MAXN*2];
int id=0;
int build(int l,int r)
{
int t=++id;
p[t].mx=0;
if(l==r) p[t].lc=p[t].rc=0;
else
{
int mid=(l+r)/2;
p[t].lc=build(l,mid);
p[t].rc=build(mid+1,r);
}
return t;
}
int mymax(int x,int y) {return x>y?x:y;}
void change(int x,int l,int r,int pos,int d)
{
if(x==0) return;
if(l==r)
{
p[x].mx=mymax(d,p[x].mx);
return;
}
int mid=(l+r)/2;
if(pos<=mid) change(p[x].lc,l,mid,pos,d);
else change(p[x].rc,mid+1,r,pos,d);
p[x].mx=mymax(p[p[x].lc].mx,p[p[x].rc].mx);
}
int ask(int x,int l,int r,int fl,int fr)
{
if(x==0) return 0;
if(l==fl and r==fr) return p[x].mx;
int mid=(l+r)/2;
if(fr<=mid) return ask(p[x].lc,l,mid,fl,fr);
else if(fl>mid) return ask(p[x].rc,mid+1,r,fl,fr);
else return mymax(ask(p[x].lc,l,mid,fl,mid),ask(p[x].rc,mid+1,r,mid+1,fr));
}
void main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) s[i].d=a[i]=qread(),s[i].p=i;
lsh();
if(n==1) {putchar('0');return;}
ll ans=n;
for(int i=1;i<=n-1;i++) if(a[i]>a[i+1]) swap(a[i],a[i+1]);
build(1,rx);
for(int i=n;i>=1;i--)
{
int j=ask(1,1,rx,1,a[i]-1);
if(j>0) ans+=j-i+1;
change(1,1,rx,a[i],i);
}
printf("%lld\n",ans);
}
};
int main()
{
mine::main();
}

T2-Code-Std

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
int mymax(int x,int y) {return x>y?x:y;}
const int MAXN=110000;
struct Nod
{
int d,p;
}p[MAXN];
bool cmp(Nod a,Nod b) {return a.d<b.d or (a.d==b.d and a.p<b.p);}
int tot[MAXN];
void main()
{
int n;scanf("%d",&n);
if(n==1) {putchar('0');return;}
for(int i=1;i<=n;i++) scanf("%d",&p[i].d),p[i].p=i;
sort(p+1,p+n+1,cmp);
int r=0;//前i小
for(int i=1;i<=n-1;i++)
{
r=mymax(r,p[i].p);
tot[i]=r-i;
}
ll ans=0;
for(int i=1;i<=n;i++)
{
int l=tot[i-1],r=tot[i];
if(l==0 and r==0) ans+=1;//do while
else ans+=mymax(l,r);
}
printf("%lld",ans);
}
};
int main()
{
mine::main();
}

T3-Analysis

请先思考后再展开

原题 Usaco2018 Jan Sprinklers
Luogu4184
Bzoj5187

首先,最后的可行多边形一定是一个外凸边形
那么有一个重要的性质,就是对于这种形状(大概是两个阶梯围成的)

然后这种图形的可行解非常好处理,因为对于每个点,它的另一个端点的可行区域就在其左下侧区域中
如果要直接暴力的话,现在就可以得到50分了

考虑处理出每一列的up和low表示上下界
这个东西的维护,可以考虑先记录一个转折点,然后最后再线性推一推就好了(因为有单调性)

接下来推柿子
$$
\sum_{i=0}^{n-1}
{
\sum_{j=low[i]+1}^{up[i]}

\sum_{k=low[i]}^{j-1} i-left[k]

}
$$

$$
\sum_{i=0}^{n-1}
{
\sum_{j=low[i]+1}^{up[i]}

i \times (j-low[i])
-
\sum_{k=low[i]}^{j-1} left[k]

}
$$

$$
\sum_{i=0}^{n-1}
{
i \times
\sum_{j=low[i]+1}^{up[i]}

(j-low[i])
-
\sum_{k=low[i]}^{j-1} left[k]

}
$$

$$
\sum_{i=0}^{n-1}

\frac{
i (up[i]-low[i]) (up[i]-low[i]+1)
}{2}
-
\sum_{j=low[i]+1}^{up[i]}
\sum_{k=low[i]}^{j-1} left[k]

$$

$$
\sum_{i=0}^{n-1}

\frac{
i (up[i]-low[i]) (up[i]-low[i]+1)
}{2}
-
\sum_{t=low[i]}^{up[i]-1} left[t] \times (up[i]-t)

$$

$$
\sum_{i=0}^{n-1}

\frac{
i (up[i]-low[i]) (up[i]-low[i]+1)
}{2}
-
up[i] \times \sum_{t=low[i]}^{up[i]-1} left[t]
+
\sum_{t=low[i]}^{up[i]-1} left[t] \times t

$$

$$
\sum_{i=0}^{n-1}

\frac{
i (up[i]-low[i]) (up[i]-low[i]+1)
}{2}
-
up[i] \times \sum_{t=low[i]}^{up[i]-1} left[t]
+
\sum_{t=low[i]}^{up[i]-1} left[t] \times t

$$

所以维护一个前缀和就好了

T3-Code-Std

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
//use-v4
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAXN=110000;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int up[MAXN],low[MAXN],left[MAXN];
ll slf1[MAXN],slf2[MAXN];
void main()
{
int n;scanf("%d",&n);
memset(up,-1,sizeof up);
memset(low,63,sizeof low);
memset(left,63,sizeof left);
for(int i=1;i<=n;i++)
{
int x,y;scanf("%d%d",&x,&y);
up[x]=mymax(up[x],y);
low[x]=mymin(low[x],y);
left[y]=mymin(left[y],x);
}
int lw=INF;
for(int i=0;i<=n-1;i++)//下阶梯
{
if(low[i]!=INF) lw=mymin(lw,low[i]);
if(lw!=INF) low[i]=lw;
}
int upp=0;
for(int i=n-1;i>=0;i--)//上阶梯
{
if(up[i]!=-1) upp=mymax(upp,up[i]);
if(upp!=0) up[i]=upp;
}
int lf=INF;
for(int i=0;i<=n-1;i++)//左阶梯
{
if(left[i]!=INF) lf=mymin(lf,left[i]);
if(lf!=INF) left[i]=lf;
}
slf1[0]=left[0];slf2[0]=0;
for(int t=1;t<=n-1;t++)
{
slf1[t]=(slf1[t-1]+left[t])%MOD;
slf2[t]=(slf2[t-1]+(ll)left[t]*t%MOD)%MOD;
}
ll ans=0;
for(int i=0;i<=n-1;i++)
{
if(up[i]>=low[i]) ans+=ll(up[i]-low[i])*(up[i]-low[i]+1)/2 %MOD *i;
ans%=MOD;
if(low[i]>0) ans-=(ll)up[i]*(slf1[up[i]-1]-slf1[low[i]-1]) %MOD;
else ans-=(ll)up[i]*slf1[up[i]-1] %MOD;
if(low[i]>0) ans+=slf2[up[i]-1]-slf2[low[i]-1];
else if(up[i]>0) ans+=slf2[up[i]-1];
ans=(ans%MOD+MOD)%MOD;
}
printf("%lld",ans);
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/80fa.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%