当前位置: 代码迷 >> 综合 >> NOIp 2018 游记+题解
  详细解决方案

NOIp 2018 游记+题解

热度:86   发布时间:2023-12-06 07:49:56.0

写在前面

这篇游记被某文科巨佬喷为小学生日记,大家将就看下吧别较真……

在这里插入图片描述


关于我

HB无名小蒟蒻zar。
来自WFLS,高一,老年女选手。
在各大oj上以 渣儿 / juruoZAR / ouaoan 等账号潜水


day 0

星期五——
上了三节文化课,然后翘了第四节体育课出去吃饭了,然后就在校外碰到了我们班主任,被质问为什么逃课……
吃完饭又去班主任办公室交材料,并把手机忘在他桌上了整整30min……(这就很尴尬了)

下午同学们都去看考场了,我没去,但为了翘下午的数学考试溜回家了~
回家敲模板,写了十个左右,手疼放弃,早早地睡了~~


day 1
before 8:30

早上去考场的路上迷路了,8:15才到,只有两根签了,被分配了一根。
到考场发现坐在省队巨佬lyc的后面,rp++。
写了个A+B,和旁边的巨佬比了下扫雷初级谁过得快。结果……旁边的巨佬扫雷炸了,并且一直没有扫过……

密码:飞雪连天
看到的第一眼就想明天的密码是不是笑书神侠……

8:30 – 8:40

看题——

T1 铺设道路
瞬间想到积木大赛,原题?读了 3 + 3^{+} 3+遍,没发现什么问题啊?

T2 货币系统
思路很简单,就是把排序后可以用它前面的数表示的数都划掉就好了。
80%的数据好小,从数据范围来看状压可以压得下?不很会……
写个筛也许能骗一点分?

T3 赛道修建
看到二分标志性词语!看到一棵树!看到LCA!然而并不会……
看子任务:
有菊花图,有链,有裸树的直径……55分裸暴力,良心!

8:40–8:45

处理文件夹,in/out流。

8:45–9:00

5分钟敲完T1 + 一遍过样例 + 一遍过并不大的大样例。
5分钟思考???出大原题的意图。
5分钟测试了下。

9:00-10:20

做T2。

先敲了一个 n 2 a m a x \ n^2\ a_{max}  n2 amax? 的筛,手算了 5 + 5^+ 5+数据,好像思路没问题。
然后开始想80%的子任务……
感觉状压一下可以的,然后怎么办,怎么办……
过了20min后,决定放弃状压,感觉这部分子任务是假的。

那我就把之前的筛优化下交上去吧。
看了看暴力筛,发现复杂度够过80%数据了……我的20min?

然后写优化——
首先那些不需要的数可以不被筛的,这样每次就最多只用筛n个数了。
然后在程序里加了3个continue优化下,据说 continue / break 可以获得玄学效率。
测大样例,WA?发现写出了 memset(canuse,0,sizeof(0)) 这种玄学初始化……

大样例pass,时间9:45。
开始造极端数据测时间,主要测了 连续的整数 / 互质的数 / 两两不互质的数 / 随机数。
程序跑的极慢,检查发现其中一个看似很有用的 continue 没有起到一点作用,原因竟是手滑把a[i]写成了i ……

极端数据本地卡过。也许这个筛可以水 9 0 + 90^+ 90+

10:20–11:20

先写了树的直径,自测了下感觉是对的。
树的直径,过了样例1 + 样例2的m改为1 ,静态检查了2min没毛病。
然后写了链,二分 + 贪心,好像也挺简单的。
这时刚过了20min。

然后开始思考二叉树。
二分是肯定要的,然后加个LCA感觉可以。
思考时间10min,也许……可能是这样的?
把二分敲了,LCA敲了,然后就不会了。

放弃。

11:20–11:55

检查。

T1又读了两遍题,随便测了下。确认是原题。
T2不想看,又把之前测过的数据测了一遍然后跳过了。
T3检查时发现,我菊花图的思路错了!
当时我认为只用把边两两配对就好了,然后发现 m>2*(n-1) 时有单边存在?
骂了自己好多遍 ** (手动河蟹),然后开始写。

写了10min没写完……

11:55–12:00

强行打断T3菊花图的进度。
填了桌签,删了.in和.out文件,检查调试信息有没有删。
11:58时抬头看见lyc巨佬还在敲代码,被感动.jpg。

after 12:00

出考场,听见一个不认识的巨佬说他AK了……瑟瑟
遇到mzj巨佬,说T3正解树剖,但他没写。
在电梯上有巨佬说T2完全背包但他没写,我说我写了个诡异的筛,他说呵呵,心情–。
在楼下听几个人说ylh巨佬AK了?
我告诉教练我凉了,然后看见ouuan诡异地笑着出来了,说ylhAK了,看来ylh真的AK了。
打开QQ,看到各大群+oj上有许多AK祭,原题*3祭,心情-inf。

下雨没带伞淋雨跑上车,rp–。

下午写了半个线段树,不想写了,颓废。
不太想估分。


day 2
before 8:30

到得比较早,抽了签。
周围人都不认识,边上有个女孩子,前面的巨佬好像有点面熟。

密码:笑书神侠
虽然day1已经猜到这个密码了,但是还是看错了,看成了 小叔神仙 ,敲错了3遍……良心监考老师用汉语写了密码提示。
我day1竟然猜对了密码……rp++。

抽到的这个考场有音响,四周都是扫雷的声音。

8:30–9:00

先写了繁琐的提交格式。

看题——

T1 旅行
60%的子任务是一棵树,排个序贪心下就好。
想到九省联考2018 day1T2我排个序贪个心水过的60分。
100%的数据环套树。断环为链 n 2 n^2 n2卡卡常也许可以过,有点悬?

T2 填数游戏
看到 矩阵 + 二元组 ,又想到了九省联考2018 day1T1的悲惨经历(STO ouuan)。
成功被误导想了下轮廓线dp。
n,m<=3可以手写打表。
n,m<=8可以暴力打表。
嗯,对,就是打表。

T3 保卫王国
并没有再去想 九省联考2018 ……
所以我什么都没想到……

心态–
感觉一定能写对的只有60+20+0=80分保底。
感觉今年像是假的一样,难度顺序T1–T6?

9:00–10:40

20min写了T1树的60分,过了大样例。

开始肝环套树。
先排了个序,害怕常数,放弃了 n 2 n^2 n2断环为链。
好像搜索可以过。
由于环套树的环是简单环,所以可以从1开始dfs一遍搜出环的起点。
环上的路径一定是先走字典序小的一边,再掉头。
所以搜索下就好了。
写了一个小时调过了大样例。
用了十分钟叉掉自己。
又用了十分钟过了huck数据。

发现没时间了。

10:40–11:20

左边的妹子玩纸牌,右边的小鸽鸽玩扫雷。

花了10分钟手算了n,m<=3。
然后写了半个小时暴力写不出来。
跳过。
20分祭。

11:20–11:40

左边的妹子开始睡觉,右边的小鸽鸽

好慌啊,心态–。
写了n,m<=2000的dp。

11:40–11:50

推了一下T2,没什么用。

11:50–12:00

检查格式。
内心自闭了,默默的思考退役记的格式怎么写。

after 12:00

出门听巨佬们说day2翻车了?都太fAKe了吧……
又跟教练说我凉了。

回家吃饭,没有带文化课作业,滚回学校做作业。
教室门锁了被关在了外面,rp–。


day 不想数

期中考试彻底爆炸了,不只是我,除了jason和ouuan的几乎所有信息组成员好像都炸了。
唯一的女孩子(除了我)ZSY转学了,以后竞赛可下了没人陪我吃饭了,桑心。
落咕测的380,ouuan、ylh、jason分都400+,被吊打……巨佬lyc似乎也凉了。


day 不想数 +不想数days

听说早上10点出分,课间操和一众巨佬去机房查分,发现分数竟然是暂无!
??? => GGF

中午睡过错过竞赛课+数学课+物理课,rp–。


day 不想数 +不想数days+1

听说早上8点出分,早自习还在和ouuan说要不要待会去机房查分,mjc竟然已经查到分了……
???竟然还会提前出分!
Day1:100+100+50=250
Day2:84+20+24=128
总分:378
排名:HB rank 14

day1T2捡了个AC,day2果然翻车,T1都写跪了。听说ouuan day2T1断环为链AC了?

ouuan果然是HB rank1,以后他装蒻时有证据了。
ylh HB rank5 ,Jason HB rank8,都是吊打我的巨佬啊……

被教练拉出去谈话,信心++。


总结

感觉该拿的暴力分好多没拿到,时间分配也有问题……
呜呜呜考前写的模板一点都没用到,写了一堆dfs,还是很桑心的,还是多练练暴力吧。


题解:

更新中……

day1T1:

同积木大赛——

#include<bits/stdc++.h>
using namespace std;#define read(x) scanf("%d",&x)
#define maxn 100000int n;
int a[maxn+5];int main() {
    read(n);for(int i=1;i<=n;i++) read(a[i]);int ans=0;for(int i=1;i<=n;i++) {
    if(a[i]>a[i-1]) ans+=a[i]-a[i-1];}printf("%d",ans);return 0;
}
day1T2:

暴力筛——

#include<bits/stdc++.h>
using namespace std;#define maxn 100
#define maxa 25000
#define read(x) scanf("%d",&x)int n;
int a[maxn+5];bool canuse[maxa*2+5];int s=1,ss[maxa*2+5];int main() {
    int T;read(T);while(T--) {
    memset(canuse,0,sizeof(canuse));s=1;read(n);for(int i=1; i<=n; i++) read(a[i]);sort(a+1,a+n+1);canuse[0]=true;int ans=0;for(int i=1; i<=n; i++) {
    if(!canuse[a[i]]) ans++;else continue;for(int tt=1; tt<=s; tt++) {
    int j=ss[tt];if(!canuse[j]) continue;int t=(a[n]-j)/a[i];for(int k=1; k<=t; k++) {
    int x=j+k*a[i];if(canuse[x]) continue;canuse[x]=true;ss[++s]=x;}}}printf("%d\n",ans);}return 0;
}
day1T3

二分。

#include<bits/stdc++.h>
using namespace std;#define maxn 50000
#define read(x) scanf("%d",&x)int cnt[maxn+5],f[maxn+5];struct Edge{
    int u,v,w,f;Edge(){
    }Edge(int uu,int vv,int ww) {
    u=uu,v=vv,w=ww;}Edge(Edge oth,int ff) {
    u=oth.u,v=oth.v,w=oth.w,f=ff;}bool operator < (const Edge& oth) const {
    return f<oth.f;}
};int n,m;vector<Edge> g[maxn+5];vector<Edge> chd[maxn+5];void dfs(int x,int fa,int mid) {
    cnt[x]=f[x]=0;chd[x].clear();for(int i=0;i<g[x].size();i++) {
    Edge y=g[x][i];if(y.v==fa) continue;dfs(y.v,x,mid);f[y.v]+=y.w;if(f[y.v]>=mid) cnt[x]++;else chd[x].push_back(Edge(y,f[y.v]));}if(chd[x].size()==0) {
    return ;}sort(chd[x].begin(),chd[x].end());int L=0,R=chd[x].size()-1,mm=-1,dd=0;while(L<R) {
    if(chd[x][L].f+chd[x][R].f>=mid) cnt[x]++,dd++,L++,R--;else L++;		}L=0,R=chd[x].size()-1;while(L<=R) {
    int Mid=(L+R)/2;int flg=0;int l=0,r=chd[x].size()-1;if(l==Mid) l++;if(r==Mid) r--;while(l<r) {
    if(chd[x][l].f+chd[x][r].f>=mid) flg++,l++,r--;else l++;if(l==Mid) l++;if(r==Mid) r--;}if(flg==dd) L=Mid+1,mm=Mid;else R=Mid-1;}if(mm!=-1) f[x]=max(f[x],chd[x][mm].f);return ;
}bool judge(int mid) {
    int ans=0;dfs(1,0,mid);for(int i=1;i<=n;i++) ans+=cnt[i];return ans>=m;
}int main() {
    int L=0,R=0;read(n),read(m);for(int i=1;i<n;i++) {
    int x,y,z;read(x),read(y),read(z);R+=z;g[x].push_back(Edge(x,y,z)),g[y].push_back(Edge(y,x,z));}R/=m;int ans;while(L<=R) {
    int mid=(L+R)/2;if(judge(mid)) L=mid+1,ans=mid;else R=mid-1;}printf("%d",ans);return 0;
}
day2T1:

O(n) dfs可过,考试时写挂了鸭?
代码量有点大,变量名用得也不是很清晰,以至于造成手滑……

#include<bits/stdc++.h>
using namespace std;#define maxn 5000
#define read(x) scanf("%d",&x)int n,m;
vector<int> a[maxn+5];vector<int> ans;void dfs(int x,int fa) {
    ans.push_back(x);for(int i=0; i<a[x].size(); i++) {
    int y=a[x][i];if(y==fa) continue;dfs(y,x);}return ;
}bool vis[maxn+5];
int rt=0,rtt=0;void dfs1(int x,int fa) {
    vis[x]=true;for(int i=0; i<a[x].size(); i++) {
    int y=a[x][i];if(y==fa) continue;if(vis[y]) {
    rt=rtt=y;break;}dfs1(y,x);if(rt) break;}if(!rt) vis[x]=false;if(x==rt) rt=0;return ;
}int x1,x2;
bool use[maxn+5];
int flg=false;
int nn=0;void dfs2(int x,int nxt) {
    if(vis[x]&&x>nxt&&flg==1) {
    flg=2;return ;}if(x==nn) flg=2;use[x]=true;ans.push_back(x);if(x==rtt) {
    for(int i=0; i<a[x].size(); i++) {
    int y=a[x][i];if(use[y]) continue;if(vis[y]) {
    nn=y;}}for(int i=0; i<a[x].size(); i++) {
    int y=a[x][i];if(use[y]) continue;if(vis[y]&&2!=flg) {
    flg=1;}dfs2(y,i==a[x].size()-1?nxt:(use[a[x][i+1]]==0?a[x][i+1]:(i==a[x].size()-2?nxt:a[x][i+2])));}return ;}for(int i=0; i<a[x].size(); i++) {
    int y=a[x][i];if(use[y]) continue;else dfs2(y,i==a[x].size()-1?nxt:(use[a[x][i+1]]==0?a[x][i+1]:(i==a[x].size()-2?nxt:a[x][i+2])));}return ; 
}int main() {
    read(n),read(m);for(int i=1; i<=m; i++) {
    int x,y;read(x),read(y);a[x].push_back(y);a[y].push_back(x);}for(int i=1; i<=n; i++) sort(a[i].begin(),a[i].end());if(m==n-1) {
    dfs(1,0);for(int i=0; i<ans.size(); i++) printf("%d ",ans[i]);} else {
    dfs1(1,0);dfs2(1,1e9);for(int i=0; i<ans.size(); i++) printf("%d ",ans[i]);}return 0;
}
  相关解决方案