游记&OI - 广州纪中游记 Day15 | Lucky_Glass's Blog
0%

游记&OI - 广州纪中游记 Day15

真的是最后一天了,反而没有之前向外离开的那么高兴……

新交的一个朋友 lcj ,有缘千里相见!

<题面链接> 提取码:7puf


Part1. 游记

“最后一天了,今天的模拟赛一定要好好打!”因为是最后一天了,大清早起来就像打了鸡血……我也不知道为什么……

模拟赛上也拼尽全力,AC 了一道题,而且 $O(N)$ 踩标算(ヽ(=^・ω・^=)丿),这一点没留遗憾(tl 6666,比我多5分爆踩我)。打完这最后一场模拟赛,虽然打的不错,有一种快感,但是总有一种意犹未尽的感觉,似乎之后少了这么高强度的模拟赛训练会不习惯(似乎立了一个什么惊人的 flag)……

下午跟着家长去参观了孙中山纪念馆,竟然就在学校旁边,来纪中的时候注意到了旁边有一座特别大的园,但是不知道这就是孙中山纪念馆。

因为我们是中午去参观的,人不算多,每一件实物都有机会近距离观摩(???什么玩意,输入法自己跳出来的)。然后非常尴尬的是一开始并没有注意到“No photo”,拍了几张,后面 tly 注意到提醒了我,然后我就默默的把手机收了下去 (@w@)。但是更加尴尬的是,发现许多游客根本没有注意到禁止拍照的标志,一直在合影、拍照,或许博物馆应该把标识牌放到显眼一点的地方……

反正是各种参观,顺便对应一下历史书上学到的知识点(和其他同学一起 match 历史书上的图片还挺有意思的)。

参观完纪念馆就去参观故居,反差有一点大,纪念馆里红毯、石雕、锦旗装点,而故居里徒有灶台、没有任何雕刻的木桌(然后印象最深刻的)是一个非常小的浴盆(???)仿佛仍有当年简朴之地出贤才的灵气。

最后一点小插曲,出纪念馆的时候看到旁边一棵乔木,标识牌写着“芒果树”,一群人震惊了——

- “woc 这就是芒果树!!”

- “吃了这么多年芒果才知道芒果长树上的……”

- “这芒果树这么高怎么摘啊?”

没办法,身处内地见识太少了(改革开放的伟大决策,???反正重庆也正在走向开放进步嘛)

领略了一番民国历史,也不枉此行。

下午回去听课(好惨啊),上讲台上讲了一发 $O(n)$ 做法,非常开心的装了一逼(口吐莲花)结果第三题没有听懂,现在都还没改出来,之后估计也没有机会改了大概意思就是今天的 T3 题解咕了)。然后下午就把 T1 改对了,然后一直弄 T3 没弄出来,一下午就没了 QwQ

下午放学后就放假了……我那个新疆远到而来的朋友准备去广州参加 B站 的漫展,我也好想去啊!!然而当然是没有机会的,明天清早就要走了。

- “有缘再见!”

- “这就真的是有缘再见了!bye~”

那么 罗传杰,一个看起来健硕高大乍一眼以为比我年级大结果实际上只有初二的 OIer,祝你漫展愉快~ 反正出外省游学的机会还很多,说不定哪一次又会在游学的时候碰到呢?剩下的就真的是“有缘千里相见”了……ヾ( ̄▽ ̄)Bye~Bye~

然后现在写游记的时候是晚上了,反正已经放假了,然后一群人在机房里颓废放松,然后我就捞了一套 CF Div3 的题刷水(好久没有做这么简单的题了好开心啊 ♪(^∀^●)ノ)今天晚上准备好“文娱节目”了,希望宿管能稍微宽松一点吧……

这篇游记写完了,不过不知道写完这篇游记之后会不会有一些值得写进去的东西……反正记得就写吧(然后就忘了)


Part2. Solution

少了一道 T3 写题解瞬间简单了好多

今天题目质量很高

T1. 投票(vote)

[Experience]

一开始真的犯蠢……想到一个后效性明显的 DP,然后以为想到了正解,写完过后测样例发现锅了……QwQ调试发现 DP 有后效性,还没法改正……

没办法,时间早就超过预期了,就把 T1 跳了看 T2……

最后只好骗了 50 的部分分(话说为什么实际上可以有 70 分啊???然而我真的就只判断了数据规模在 $50\%$ 内才计算,现在想好像不太 OK)

[Solution]

首先这是一道结论题,然后结论不知道怎么证明,似乎可以感性理解、打表证明一下

结论就是:把所有人按 $p_i$ 从小到大排序,则选取的人一定是最前面和最后面的一些。比如将所有人排序后,每个人的编号为 $\{1,2,3,4,5,6,7,8\}$,我们可能选择 $\{1,2,3\}$ 、$\{5,6,7,8\}$,或是 $\{1,2,6,7,8\}$,但是不可能选择 $\{2,3,7\}$、$\{1,2,4\}$ 等等……

所以我们可以考虑 DP —— 先将所有人按 $p_i$ 排序
f[i][j] 表示选择 1i 的所有人,有 j 个人投“好”的概率;
g[i][j] 表示选择 in 的所有人,有 j 个人投“好”的概率;

f[i][j] 的状态转移举例(因为 g[i][j] 的转移是基本类似的):

考虑第 i 个人是否投了“好”,若是,则对概率的贡献为 p[i]*f[i-1][j-1] ;否则贡献为 (1-p[i])*f[i-1][j] 。所以 f[i][j]=p[i]*f[i-1][j-1]+(1-p[i])*f[i-1][j]

然后枚举选择了第 1i 的所有人和 m-i+1m 的所有人(加起来恰好 m 个人);再枚举第 1i 的所有人中有 j 个投了“好”,则第 m-i+1m 的所有人投了 m/2-j 个“好”。也就是说选择前 i 个人和后 m-i 个人,投了 m/2 个 “好” 的概率为:

对于每一个 imax 即可。

[Source]

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const bool Debug=false;
const int N=2000;

int n,m;
double p[N+3],f[N+3][N+3],g[N+3][N+3];

int main(){
if(!Debug)
freopen("vote.in","r",stdin),
freopen("vote.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lf",&p[i]);
p[i]=(int(p[i]*100+0.5))/100.0;
}
sort(p+1,p+1+n);
g[n+1][0]=1;f[0][0]=1;
for(int i=1;i<=m;i++)
for(int j=0;j<=m;j++)
f[i][j]=f[i-1][j]*(1-p[i])+(j? f[i-1][j-1]*p[i]:0);
for(int i=n;i>=n-m+1;i--)
for(int j=0;j<=m;j++)
g[i][j]=g[i+1][j]*(1-p[i])+(j? g[i+1][j-1]*p[i]:0);
double ans=0;
for(int i=0;i<=m;i++){
double res=0;
for(int j=0;j<=m/2;j++)
res+=f[i][j]*g[n-(m-i)+1][m/2-j];
ans=max(ans,res);
}
printf("%.7f\n",ans);
return 0;
}

T2. 动态数点 (point)

A了A了(“噫好了!我AC了!”

[Experience]

因为决心最后一次要好好打,就决定一定要想出一道题的正解。

发现这道题的思路非常清晰,就试着写了一发,然后一测样例……(oh)又调试了二十几分钟,然后发现自己的标记数组没清空(没脸见人了

改了之后,发现自己写了一个非常非常优秀的 $O(n)$ 算法,愉快 AC。

Tab. 赛后发现其实我写的是一个 $O(n\log n)$ 算法,因为我最后对答案排了一个序……其实主要是我偷懒,只要换种输出答案的方式就不必要排序了。

因为这是我自己想出来的做法,我一定要多写一点!

[Solution]

= 方法

考虑对每一个点 i 储存 lef[i]rig[i] ,表示 lef[i]rig[i] 的所有数都被 a[i] 整除。(In fact,并不是每个 i 都会计算 lef[i]rig[i],这是一个优化,有了这个优化,算法能变为 $O(n)$,之后解释)

那么我们可以从左到右枚举 i ,计算 rig[i]。从 rig[i]=i 开始暴力尝试向右扩展 rig[i] —— 如果下一个数字仍然可以被 a[i] 整除,则将 rig[i]++,并且把新扩展到的那一个点打上一个标记vistag[rig[i]]=i

然后我们把 i++。如果 vistag[i] 有值,则查看 a[i] 是否等于 a[vistag[i]] ,如果等于,则 rig[i]=rig[vistag[i]],然后 continue,否则直接 continue。

以上是 rig[] 的计算,lef[] 只是把 i 改成从右到左枚举而已。

求出 lef[],rig[] 后,我们枚举 i ,则对应的区间就是 lef[i]rig[i],找到最长的几个区间,然后储存到答案里面即可(因为最长区间的长度都是一样的,只要从左到右找区间,储存的答案就是从左到右有序的)

= 举例

比如 a[]={2,4,2,8,6,3,9}

  1. i=1,扩展 rig[i]4vistag[1~4]=1
  2. i=2vistag[2] 有值,且 a[2]!=a[vistag[2]],直接 continue;
  3. i=3vistag[3] 有值,且 a[3]==a[vistag[3]]rig[3]=rig[vistag[3]] ,即 rig[3]=4,然后 continue;
  4. i=4vistag[4] 有值,且 a[4]!=a[vistag[4]],直接 continue;
  5. i=5,发现 rig[5] 不能扩展,rig[5]=5vistag[5]=5
  6. i=6rig[6] 扩展到 7vistag[6~7]=6
  7. i=7vistag[7] 有值,且 a[7]!=a[vistag[7]],直接 continue;
  8. 清空 vistag[]!!!(emm……)

那么我们最后得到的 rig[]={4,0,4,0,5,7,0}

那么 lef[] 就留给 reader 们试试计算了,如果你算出来 lef[]={1,0,1,4,0,5,7},那就 OK 了,你应该已经理解了这种做法。

= 证明

首先时间复杂度显然 $O(n)$,每个点只会被计算一次。

然后我们来证明 —— “vistag 有值的点不用再暴力计算(即continue掉)”,仍然拿 rig[] 来证明。

j=vistag[i],那么 jrig[j] 的所有数都会被 a[j] 整除,且 a[rig[j]+1] 不会被 a[j] 整除。

那么可以证明,如果计算 rig[i],则有 rig[i]<=rig[j],因为 a[i]a[j] 倍数,则 a[rig[j]+1] 也不会被 a[i] 整除,所以 rig[i] 最大也只能达到 rig[j]

以上证明了 rig[i]<=rig[j]

因为 a[i]a[j] 整除,则显然 a[i]>=a[j]

  1. a[i]>a[j] 时,则 a[i] 不整除 a[j],那么 lef[i]>j ,而 lef[j]<=j所以 lef[j]<lef[i]。此时存在 lef[j]<lef[i]<=rig[i]<=rig[j],显然 lef[i]rig[i] 这个区间并不优,所以不必要计算。
  2. a[i]==a[j] 时,不难证明 lef[i]==lef[j]rig[i]==rig[j],所以直接让 rig[i]=rig[j] 即可。

综上,这是一个正确的 $O(n)$ 算法。

[Source]

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=500000;
typedef long long ll;

int n,nans,ans;
ll num[N+3];
int lef[N+3],rig[N+3],rans[3*N+3];
int tagvis[N+3];

int main(){
freopen("point.in","r",stdin);
freopen("point.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&num[i]),lef[i]=rig[i]=i;
for(int L=1;L<=n;L++){
if(tagvis[L]){
if(num[L]==num[tagvis[L]]) rig[L]=rig[tagvis[L]];
continue;
}
int R=L;
while(R<=n){
if(num[R]<num[L]) break;
if(num[R]%num[L]) break;
tagvis[R]=L;
R++;
}
rig[L]=R-1;
}
memset(tagvis,0,sizeof tagvis); //!!!!!!!
for(int R=n;R>=1;R--){
if(tagvis[R]){
if(num[R]==num[tagvis[R]]) lef[R]=lef[tagvis[R]];
continue;
}
int L=R;
while(L>=1){
if(num[L]<num[R]) break;
if(num[L]%num[R]) break;
tagvis[L]=R;
L--;
}
lef[R]=L+1;
}
for(int i=1;i<=n;i++){
int siz=rig[i]-lef[i];
if(siz>ans) nans=0,ans=siz;
if(ans==siz && rans[nans]!=lef[i]) rans[++nans]=lef[i];
}
printf("%d %d\n",nans,ans);
for(int i=1;i<=nans;i++)
if(rans[i]!=rans[i-1]){
if(i!=1) printf(" ");
printf("%d",rans[i]);
}
printf("\n");
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com,欢迎提问!