不知觉就咕了1.5个月


在回忆 2021 年那个刚步入初中的懵懂孩童参加 GDOI 的惊喜中感慨初中时光的飞逝。

2021 GDOI 普及组游记


Day - ∞ \infty

去年因为疫情取消了,今年难得重新举办,珍惜每一次机会吧。
前年的地点订在深圳耀华学校,忘不了住在那所学校睡不着觉,忘不了半夜12点的灯火通明,忘不了晚上8点在车流涌动的大街上漫无目的地游荡…

我发现自己越来越常用所谓“一眨眼”“弹指一挥间”这样的俗气的词汇了。但时光确是匆匆地流走了,翻翻初一写 GDKOI 的那稚嫩的文字,感慨光阴飞逝带来的忧愁滋味。我渴求心灵的成长,便也需承受物是人非的伤痛了。不写太多了,到 GDKOI 后在总结吧。

Day -5

打 THUPC,成功切3T,前两天把具体的都在这儿写了:

Link

还,蛮开心的,毕竟去年 1 题没切被乱杀。

Day -3

其实这篇文章是从今天开始写的…
今天周二,还没准备好心情,大家都还没什么感觉,就当做平时冬令营停课一样,打模拟赛。

这场题
140 QAQ

T1:一道期望 dp ,设两个人分别为 a , b a,b a,b ,总分分别为 S a , S b S_a,S_b Sa,Sb,根据题意分别有4种情况,那么共16种情况,考虑其中一种情况,若 S a > S b S_a>S_b Sa>Sb ,那么 a a a 会对 b b b 的排名产生 1 的贡献,而出现这种情况的可能性为 1 16 \frac{1}{16} 161 ,因此对于每一个 S a > S b S_a>S_b Sa>Sb a a a 都会对 b b b 产生 1 16 \frac{1}{16} 161 的贡献,于是 i i i 的期望排名为 1 + 1 16 × ( S j > S i 的情况数 ) 1+\frac{1}{16}\times(S_j>S_i的情况数) 1+161×(Sj>Si的情况数)

T2:以前遇到过类似的题,但没有想起来。可以考虑将题目倒序做,就变成了角谷猜想,还是一道比较精妙的题目。那么对于负数的情况,取到距离 1 号宇宙最近的位置后,用题目给定的第一种跳法跳到正数即可。

T3:拆式子后用树链剖分+线段树维护,还没补,咕了。

T4:dp + 李超线段树优化,也咕了。

非官方题解

Day -2

叒叕模拟赛。 题目

不知道干啥,补了前三题,T3的 LIS + 组合数学不会忘记。做法是用字符串模拟占位求出所有情况,然后用类状压求答案。

代码长但不丑。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=120005;
int n,m,k,M,tot,sum,a[105];
map<string,int> vis;
vector<string> ans;
string s;
inline int Rd(){
    int s=0,w=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
    return s*w;
}
LL c[520][520],fac[520];
void GetC(){
    fac[0]=fac[1]=1;
    for(int i=2;i<=515;i++) fac[i]=fac[i-1]*i%M;
    for(int i=0;i<=515;i++) c[i][0]=1;
    for(int i=1;i<=515;i++) for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%M;
    return ;
}
void LIS(string s,int l){ //find out all situations
    if(vis[s]) return ;
    vis[s]=1;
    ans.push_back(s);
    tot++;
    if(l==n) return ;
    for(int i=0;i<n;i++) if(s[i]=='0'){
        string t=s;
        char c='0';
        for(int j=0;j<i;j++) c=max(c,s[j]);
        t[i]=c+1;LIS(t,l+1);
    }
    return ;
}
string S[N];
map<string,int> Ad;
LL cnt[N];
void in(){
    // printf("%lld\n",tot);
    for(int i=0;i<tot;i++){
        char c='0';
        s=ans[i];
        for(int j=0;j<n;j++){
            if(s[j]=='0') s[j]=c+1,c++;
            else c=max(c,s[j]);
        }
        c='0';
        for(int j=0;j<n;j++) c=max(c,s[j]);
        if(c>=k+'0') S[++sum]=ans[i],Ad[ans[i]]=sum;
    }
    for(int i=1;i<=sum;i++)
        for(int j=0;j<n;j++)
            if(S[i][j]!='0')
                cnt[i]|=(1<<j);
    // for(int i=1;i<=sum;i++) printf("%lld ",cnt[i]);puts("");
    return ;
}
LL dp[17][N];
string nw,nt;
void modify(string &s,int ad){
    char c='0';
    for(int i=0;i<ad;i++) c=max(c,s[i]);
    s[ad]=c+1;
    return ;
}
void work(){
    // puts("");
    dp[0][1]=1;
    for(int i=0;i<m;i++){
        for(int j=1;j<=sum;j++){
            if(dp[i][j]){
                (dp[i+1][j]+=dp[i][j])%=M;
                nw=S[j];
                for(int k=0;k<n;k++){ //try to put i-th person to k-th address
                    if(nw[k]=='0'&&a[i]>=(cnt[j]+(1<<k)+1)){
                        nt=nw;
                        modify(nt,k);
                        (dp[i+1][Ad[nt]]+=dp[i][j]*c[a[i]-cnt[j]-2][(1<<k)-1]%M*fac[1<<k])%=M;
                    }
                }
                // printf("%lld\n",dp[i][j]);
            }
        }
    }
    LL ans=0;
    for(int i=1;i<=sum;i++) if(cnt[i]==(1<<n)-1) (ans+=dp[m][i])%=M;
    printf("%lld",(1ll<<n)%M*ans%M);
    return ;
}
int main(){
    n=Rd();m=Rd();k=Rd();M=Rd();
    for(int i=0;i<m;i++) a[i]=Rd();
    sort(a,a+m);
    for(int i=0;i<n;i++) s+='0';
    GetC();
    LIS(s,0);
    in();
    work();
    // for(int i=1;i<=500;i++) for(int j=1;j<=i;j++) printf("%d ",c[i][j]);
    return 0;
}

Day -1

抓紧时间复习了感觉来了。
所以没有什么时间写这篇预游记,可以发现这里往上写的内容都不算多,有一定原因是去集中注意力完善知识网络,当然偶尔溜一下神去外面逛一下,挺好。

今日某谷做题记录。

发这几张照片前我也没看过。

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

有被自己感动到。

相信会有结果与过程成正比的那一天。(哭了。

还有一件比较有感触的事情,就是今天在离开图书馆的时候被管理员问道昨天下午为什么没来。因为集训,昨天回了教室补 whk,没想到不知不觉中管理已经认识我了。

梦无疆,行致远

Day 0

下午 3:00 出发,在去广州的路上,直到现在(3:57)才想起来写游记。起初很无聊,看书但静不下来,便拍了几张照片。下了高速,映入眼帘的就是各具特色的高楼大厦,尽管寒假的时候已然来过一回,但那次只不过是走马观花,没有时间欣赏。希望这次来可以重新好好地审视一下这个城市——广州。

在广州六中考试。领了一手选手证和纪念袋(包括和往年一样的 GDOI 纪念笔和)

车流量和人流量都极大,刚好又碰上星期五下午,这也倒给了我的目光驻足的时间,但是手机没电,没有拍下太多的照片,车上的同学都显得没有见过世面,我以一副镇定的神情掩盖底下那虚伪自尊的面容。

广州是个生活速度很快的城市,这与中山不同。比如初中的学校周围,街道很少,每到晚上就会有种恬然静谧的感觉,如同乡村,没有什么声响。但广州的街道无时无刻不是那样生机勃勃,从凌晨2点仍奔驰的汽车中可以深切地感受到。

第二次入住酒店,不过是一个人的双人房。

挺奇妙的。
订到了一间隔壁有同学的房间,但其实并没有算串过房。只能认为对于多数人来说,电子产品这样的“新科技”应该会更重要。

房间确实挺高级,干净整洁,床头有“明亮模式”“阅读模式”“电视模式”“睡眠模式”,灯光会随着模式的改变发生亮度与位置的改变,洗手间和客厅都有音乐配备,窗帘和纱帘也一律自动化。感慨人工智能对先进城市的影响确实是极大了,且一二线城市之间还是有一定的差距。

挺贵,三天两晚1200。

晚上和同学教练出去逛了,酒店离广州塔大概三四公里,本以为已无望出行,但广州地铁又一次惊艳了我。

转了一次乘,搭乘时间共计 23 秒。

没有办法想象的是,在洒满灯光的广州这座城市下,还有一个不为外人所知的繁荣的地下都市,我愿称之为 地下城

咕一张图片。

广州的地铁布局十分精当,以经济贸易区为中心,呈散射状,广州塔处在正中央。我们在转乘的过程中向下走到了另一号线,根据铁路图的交点,应该就上下两部分。共 4 层,其中 -1,-3 层为贸易区,-2,-4 为候车区。我驻足于人群中,感受经济中心这独特的景色。

让我感触较深的是地下城形形色色的人。在广州生活时间已长让他们的行动显得熟练,相信这般忙碌的生活对于他们是标配。

行人们是不抬头的,我看不清他们的脸,猜不透他们的想法。他们有着不同的目的地,走着不同的路,过着截然不同的生活,每天对着相似的日子,但丝毫没有流露出被生活压倒的痕迹,在平凡中默默地耐住寂寞,在寂寞中默默地坚守着理想。

回酒店已逾十点,串了一下房发现没什么意思,也没复习太久。
不知道干啥,开了会儿电视,然而突然卡死了,摆烂。

12:15 睡,01:15 热醒,睡不着,开了空调,还是热,调成 21 度,约 2 点入眠。

Day 1

咕了两个月继续写
在房间先被闹钟叫醒,又被服务电话吵醒。

酒店自助早餐好评。

等考场开放,看了会儿学校图书馆借的书,带上巧克力糖的进考场。
(然而看的最短路进阶两天都没考,只起了安慰作用。

考试时间 9 : 30 − 12 : 30 9:30 - 12:30 9:3012:30

开题。压缩密码是好久不见,应该是对应去年 GDOI 的取消。
T1 看着很板,求两个矩阵的积,而数据范围是 1 0 6 10^6 106,时限 2 秒。
T2 推式子题,T3 数据范围很小,时限 5 秒,但往状压上靠发现连暴力分都拿不到。

于是果断决定打 T3 暴力。

调完发现时间还早,回去看 T1,

Day 2

本来以为能更上一层楼的,没想到还是失败了。

咕咕。

Logo

欢迎加入我们的广州开发者社区,与优秀的开发者共同成长!

更多推荐