NOIP游记[doge]

刚刚过去的NOIP2021大家还好吗?

DAY -1:看考场

DAY0:

[报数]

考场的时候没有想到预处理,害怕1e7数组会爆掉,打了一个暴力就溜了。

这个题其实就是预处理,方法有点类似于朴素筛法,

稍微做了一点点改动(时间复杂度O(nlogn))。

一个坑点:当输入的x=(1e7-2)的时候,答案是会等于1e7+1的,所以要预处理到1e7+1

(注:目前此代码可以过民间数据)


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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e7+10;
int st[N],ans[N],pos[N],cnt;//st[i]=1时表示不可以报,ans[i]表示第i个可以报的数
//pos[i]表示i是下一个可以报的数在ans里的下标,cnt用来记录一共有几个可以报的数
int s(int x)
{
    while(x)
    {
        if(x%10==7)return 1;
        x/=10;
    }
    return 0;
}
void get_sevens(int n)
{
    for(int i=1;i<=n;i++)
    {
       if(!st[i])
       {
           if(i%7==0||(s(i)))
        {
            for(int j=i;j<=n;j+=i)st[j]=1;
        }
        else
        {
            ans[cnt]=i;
            pos[i]=++cnt;
        }
    }
     }
}
int main()
{
    get_sevens(1e7+2);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int x;
        scanf("%d",&x);
        if(st[x])
        {
            puts("-1");
            continue;
        }
        printf("%d\n",ans[pos[x]]);
    }
    return 0;
 }

[数列]

考场的时候写了一个暴力,民间数据还全部挂掉了。。。

这题果然是DP,类似于数位DP,考虑直接把进位放在状态里。
定义f[z][u][a][b]对于二进制位的后z位,已经放进去u个数,此时进位到下一位的值是a,后i位中留下了b个1,此时的权值总和。

此时有:dp[z][u][a][b]=dp[z+1][u+i][a+((b+i)&1)][(b+i)>>1)]*(power[z]的i次方)*(C[u+i][i])(C表示组合数)(记得%998244353


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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1LL*998244353;
LL n,m,k,v[105],dp[105][35][35][35];
LL C[105][105],power[105][105];
LL count_one(LL x)
{
    LL ans=0;
    while(x)
    {
        x-=x&(-x);
        ans++;
    }
    return ans;
}
LL dfs(LL z,LL u,LL a,LL b)
{
    if(u==n)return (bool)(a+count_one(b)<=k);
    if(z>m)return 0;
    if(dp[z][u][a][b]!=-1)return dp[z][u][a][b];
    LL res=0;
    for(LL i=0;i<=n-u;i++)res=(res+dfs(z+1,u+i,a+((b+i)&1),(b+i)>>1)*power[z][i]%mod*C[u+i][i]%mod)%mod;
    return dp[z][u][a][b]=res;
}
int main()
{
    memset(dp,1LL*(-1),sizeof(dp));
    scanf("%lld%lld%lld",&n,&m,&k);
    for(LL i=0;i<=m;i++)scanf("%lld",&v[i]);
    C[0][0]=1; 
    for(LL i=1;i<=n;i++)
    {
        for(LL j=C[i][0]=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }
    for(LL i=0;i<=m;i++)
    {
        power[i][0]=1;
        for(LL j=1;j<=n;j++)power[i][j]=(power[i][j-1]*v[i])%mod;
    }
    printf("%lld",dfs(0,0,0,0));
    return 0;
}
[方差]

考虑a[]的差分数组b[]。

将a[i]变成a[i-1]+a[i+1]-a[i],其实就是b[]相邻的两项交换!

再通过肉眼观察,就可以得到b[]最好的情况下是先单调递减,再单调递增,这样会使得方差最小,在这里,可以使用dfs(),时间复杂度O(n!),预估?分

再次回到DP这一个思路上,有:

f[i+1][j+b[i+1]*(i+1)]=min(f[i+1][j+b[i+1]*(i+1)],f[i][j]+j*2*b[i+1]+(i+1)*b[i+1]*b[i+1])

于是我们写出了这样一个好玩的DP


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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,a[10005],b[10005],f[405][240005],nowsum=0;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<n;i++)b[i]=a[i+1]-a[i];
    sort(b+1,b+n);
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=0;i<n-1;i++)
    {
        nowsum+=b[i+1];
        for(int j=0;j<=240000;j++)
        {
            f[i+1][j+nowsum]=min(f[i+1][j+nowsum],f[i][j]+nowsum*nowsum);
            f[i+1][j+b[i+1]*(i+1)]=min(f[i+1][j+b[i+1]*(i+1)],f[i][j]+j*2*b[i+1]+(i+1)*b[i+1]*b[i+1]);
        }
    }
    int ans=0x3f3f3f3f;
    for(int i=0;i<=24000;i++)ans=min(ans,n*f[n-1][i]-i*i);
    printf("%lld",ans);
    return 0;
}

你瞧,真好看!

当然上面一个代码会出问题,因为我们的DP要使用滚动数组压维度,还有j不能每次都循环240000次。

洛谷评测机好像炸了...To be continued...

【NOIP2020】退役的总结

By Shy

高中生涯正式退役后的最后一篇blog。

时间仓促,只能简短的写写了。


这一次省一拿到了,应该也就不再继续了。

173这个成绩,对我来说,其实心中还是略微有点遗憾的,只能责怪当初年轻的自己,如果当初再努力一点点,我还能走的更远吧。

但是我想已经足够了,在这些努力过的岁月里我收获的东西太多了。

一个陕西的OI的朋友告诉我,他停了半年的课,现在文化课已经回不去了,踩线进了省一,他只能选择继续冲省队。

我想,我是幸运的,因为我还有选择,还有退路。


与信息学竞赛的这一场偶然的相遇,我从来没有后悔。

我踏上竞赛这条道路的时候,心中并不是想着名次,而是一种纯粹的热爱,对知识的渴求。

竞赛生涯中最让我难忘的,并不是真正走上赛场的那一刻。比赛前的十几个日日夜夜的奋斗,才是真正值得我永远铭记的东西。

走的越远,越发现,进步终究是要靠一点一滴的付出。我在竞赛中的最大的收获,就是学会了静下心,把自己全身心的投入到解决问题之中。我想学习也是如此,只有投入与付出,才能真正的学到知识。

信息学竞赛的学习,给了我一种不同的思考问题的方式。例如分析问题,转化模型,这些都是在理科的学习中重要的技能与方法。在不断的学习与思考中,我真正的得到了思维上的锻炼。


比赛的地点是在师大附中,

说到这个地方我就有点PTSD,因为我在这翻了两次车了,一次是省选爆0,一次是物竞的惨败。

机房的键盘感觉不像机械键盘,反而像软键盘,还是一样的难打。

交题的模式还和省选一样,就更PTSD了。

先看了半小时题吧。

第一题一眼就是裸的拓扑排序,好写,但是涉及到了分数处理,粗略估算一下可能会爆long long,不想写高精(高精除我也不会啊)于是用unsigned long long,优化了一下通分的顺序,折腾了将近一个小时吧,太久了其实,不过没办法的事。

第二题字符串,讲真这个是我失策,考前啥都复习了偏偏没复习字符串,就像省选时复习了字符串但是没复习tarjan一样。然后看这题以为字符串DP,就没想到哈希上去。

又看了第三题和第四题吧,第三题就是个构造方案题,有点像汉诺塔,口胡了一个方案发现步数会超820000,就先放着了。

第四题有点眼熟但是想不起来哪题,似乎纪中有类似题但又不太一样,只看出可以暴力整段循环节跳。

然后又过了一小时,第二题想了个n方根号n的预处理约数的暴力算法,可以拿48,感觉不错就写了。其实判断字符串相等可以用哈希多拿一点分的,就是慌了然后没想起来。

第四题本来还想写个倍增拿多一个点的分,但是时间不够只能放弃去写暴力,写完发现情况少判了,只能调了很久,结果无解的情况忘判-1了……

写完过了大样例只剩30分钟了,赶紧写t3。写完发现checker.cpp不会用,没法测样例,干瞪眼。

最后5分钟突然明白checker怎么用了,一测大样例挂了,好惨。

然后就结束了。

这个比赛写的挺狗屎的吧,其实还是太想赢了,偏偏考的又比较偏,和我预料的有差别,所以浪费太多时间了,应该多研究部分分才对的。

oitiku上测的时候t2挂了,以为自己凉了,省一都没了,悲伤至极痛定思痛下决心攻读文化课从此不碰竞赛。

然后正式成绩没几天出来后发现t2的48活了,t1经过几次csp的格雷码什么的经验教训有了先见之明开了unsigned long long结果90了,t4虽然忘判-1但影响不大,然后高中的OI生涯就完美的落下帷幕了。

据说t2卡了哈希导致朋友的哈希结果挂到连暴力分都没有,也许我的选择还是对的吧,有时成败也是有运气的啊。

愿我们都有一个光明的前途!

 

赛后。

比赛

T1 先把数据60分拿到,剩下40分随缘打,如果没记错是这样打的

T2 排序呗就,好像是这样

T3 输入就不会了(字符串为什么会有空格啊???)

其他的可能还会比较容易

T4 深度优先搜索(不会)

把01背包代码改了一下就交了


总结:

第一次比赛还是有点慌的。。。不出意外这次第二题能A,第一题保底60,三四题能骗多少是多少了呗就。

反思:

好好学搜索!!!

最后,张老师能不能不停训啊!!!!!!

NOIP2018普及——离别前的回眸

By shy

——这不曾是我们,想要的生命,

所有的痛,依然都将会远去。

就在最后可以,说出再见之前,

让我们伴着信仰,在空中飘扬......


再见,NOIP

这是2018.11月10号的下午6点,从考场默默走出来的我,望向楼群所指向的,阴沉下来的天空,迎着从脚底而起的寒意,呢喃着:“noip,再见。”

是的,再见了。三年的时光,终究是到告别的时候了。

曾经我还是个无知的顽童,而如今,初三了,我也懂得了那份不舍与忧愁。

又一次回归到正常的生活轨道上,专心攻读文化课。

但不会忘记的是,NOIP,另外一种方式,让我证明了自己的价值。

也许省一还是省三并不重要,重要的是,我们怀着信仰所走过的那些岁月。

继续阅读NOIP2018普及——离别前的回眸

NOIP2018pj心得

迷茫,无措,前方的路模糊不清……

T1

用fgets读入字符串。对于fgets阴影还蛮大的……

T2

先计算出两方势力,再枚举一遍要将手中的兵放哪。自认为没问题,但似乎有哪里没考虑到……

T3

应该是动态规划,但不知道怎么写转移方程式。用dfs做结果第2个测试数据过不了,找到错误了,但不知道该怎么改,白费了一小时后放弃了,转战T4。

T4

模拟(?),耗了2个小时左右,总感觉打错了但测试数据过了,担心爆空间数组还开小了,似乎因此丢了一些分……

在信息路上哭过,笑过。那么,就这样吧……

-END-

NOIP2018考试感想(成绩未出)

刚刚考完,谈一谈在考场的感想。

第一题,是一道简单的字符串题目,当然越简单就又有可能有陷阱,所以我特意检查了许多遍,希望不要出错。
第二题,是一道模拟题,考虑了很多细节,考试完之后,才发现细节原来有这么多,比如开longlong,从1-n都要扫一遍(如果多想,想节约时间,通过if判断而只考虑一个区间是绝对不可行的),当然还有判断m点等等。这些细节我都考虑到了。然而minn却开太小了,危机重重


第三题,这是一道难度很大的dp,我想出了一个转移方程,但是好像出错了,也许可以拿下20分。这题相当耗时间,很明显是不划算的。(因为输出0百分之百是有十分的,而这样做只要一秒钟,另外听说除了0的数据,其他数据输出1有20分,当然山寨数据不能如此下定义)
第四题,是有关于树的,对于树的储存和操作,我不大了解,所以直接输出1,应该有12分。这题有很多人做出来了,很多人有五十分六十分左右,甚至一百分的,这题失分是不应该的。整天手写堆,考试时不会用!!!
预估成绩有点悬。如果拿不到省一,那就是一个很好的教训了。
苏轼曾经说过:“古今立大事者,不惟有超世之才,亦有坚忍不拔之志。”这句话的意思是说,努力才是正道,即使你不是天才也无妨。
我一直以为我很强,因为在每次平常的信息考试中,在初二年段我总是考第一名,但是这是一种目光短浅的表现,在本次的NOIP的比赛就可以看出,我的实力,也就这么点。
也许我掌握的算法挺多的,但是如果我不懂得去运用,那又有什么效果呢。比赛要求的并不是我们所掌握有多少,而是我们能不能通过现有的知识去挖掘新的东西。就像《啊哈算法》中纪磊去面试时遇到难题一样。(另外在集训期间主攻的图论算法也没考到,也是有点遗憾的,当然还有线性筛没考到,也是有点遗憾的)。
本次的第四题我觉得我是可以做出来的(满分不了,也有五十),但是我受到了一个误导——听说二叉树这种东西只能用链表来存。我当时信以为真,就放弃做下去了,此时还剩下一个小时!我没有利用这个时间去做第四题,而是死死地去攻打第三道题,谁知,一个小时过去了,第三题的代码最后全部被我删除了,把原来一小时的代码复制上去,也就是说,这期间相当于——我啥也没干!可惜在于此。
题目的四大要素重要性分别是是正确性,时间复杂度,空间复杂度,简洁性。做题的时候,正确性优先,不正确的算法其他的就无从谈起。
希望在下次的训练中,能保持一种谦虚的态度,做好每一道题,把握每一次大考,争取拿到更好的成绩。我在语文周报上看见一句话:“坚其志,苦其心,劳其力,事无大小,必有所成——曾国藩”。

noip2018总结

也许,这也是退役的征兆吧……


T1 标题统计

果然不是很难……但还是花了半个小时测数据,怕错……(fgets检验了很久的正确性)


T2 龙虎斗

就在这道题炸了……

原本以为是一道简单的模拟题,然后30min搞定,检查15min,然后就去做下一题了。

也考虑到了long long,但还是炸了。

某谷一测:4分!!!!!!然后if和else加大括号24分,多加了几个long long(中间玄学操作)就64分,再加minn和ans的初始化AC了!!!(初始化不加long long只有44分)

退了退了,最多省二……


T3 摆渡车

从15:45-17:55全部在打T3,最后还是放弃了。

15min就想到了dp方程,花了30min打出一个错误代码,全部重做……

之后就爆搜,到17:00打完,考虑了很多细节,连第二个样例都过不了。

后面看到眼睛花掉,聚焦都聚焦不了,不甘的耗时间,直到最后5分钟直接骗10%数据和其他数据的“cout<<"1"<<endl;”

死磕正解,到头来竹篮打水一场空。


T4  对称二叉树

五分钟一瞥题目:

“注意:只有树根的树也是对称二叉树”

直接“cout<<"1"<<endl;”了,骗分。


某谷测100+4+20+24=148(后两题应该没有这么多分)(估计124)

省三差不多稳了……

Goodbye,OI。