【玩泥巴】NOIP初赛历题被虐有感
把最近五年的初赛题目拿出来做一下，发现自己智商和常识都明显堪忧（药丸
【Sept+Oct+Nov】NOIP校内模拟赛
嗯多谢某神牛提供的不知道是哪一年的各地的NOIP模拟赛（质量挺不错的
给我们这个偏远小渔村提供了宝贵的模拟赛资料
怎么我也高二了QAQ
NOIP玩挂就真的退役了（悲伤
【开学Sept】Contests
开学了，CF和TC的比赛就不能参加了QAQ
【开学Sept】Problems
完成度：
0/18
【字符串】Palindromic Tree & Manacher
嘛回文。
【Plan B】#5
Gold第三波。1A率捉鸡。
现在已完成：
50/50
【Plan B】#4
Gold第二波。
现在已完成：
50/50
【Plan B】#3
Gold第一波。
现在已完成：
50/50
【Plan B】#2
Silver第二波。然后就打算做Gold组了。USACO的Gold组有时候还是会有神题的。
其实Silver是有170+道的，Gold是190+
现在已完成：
50/50
【暑假Aug】Contests
暑假终于有时间做各种比赛了。
可“被虐”这个状态貌似从来都没法消除啊。。。
【暑假Aug】Problems
[CF 566A]
给2n个字符串，两两配对使得lcp最大。
贪心，在一棵子树上若有两种子串的结尾节点的话就配对，剩余的就扔到父亲集中。
【然而一开始想的是Trie上跑费用流，可怎么求方案？并不会。。。】【这种思想比贪心不知神到哪里去了】
[CF 567E]
给一有向图，问某条边有没有可能是最短路网的桥（就是走最短路必须经过这条边），若不是则需要减少多少边值才能满足要求？
两边跑个最短路，然后求最短路网内的桥边，再判断需要减少多少边值。【求桥边的正确姿势并不会】【自己都是乱搞】
[CodeVS #1 C]
有两棵树，加一条边连接起来形成树S，求S的最短直径和期望直径
预处理出每个点与树中所有点的最远距离，和每棵树的直径长度，然后O(n)扫一遍求最短直径，期望直径就排序后O(n)扫一遍
[STSR #2 B]
求\(\sum_{x=1}^n\sum_{y=1}^n gcd(x,y)(n\le10^9)\)
记忆化搜索\(f_k(n)=\sum_{x=1}^n\sum_{y=1}^n [gcd(x,y)=k]\)其中有两种性质：\(f_k(n)=f_1(n/k)\)和\(\sum_{i=1}^nf_i(n)=n*n\)
[STSR #2 C]
维护向量集，支持插入和删除向量，以及询问某个向量的点积最大值。
对于每次询问可以知道答案一定在凸壳上。以时间为轴建线段树，离线处理所有点存在的时间区间，插入线段树，树上每个点维护凸壳。\(O(nlog^2n)\)的复杂度。
【Plan B】#1
听说屯题刷更爽？
先做USACO的Silver组题。全程拿Greens的号测。
现在已完成：
50/50
【APIO2013】TASKSAUTHOR
第一次做提交答案题。。。真是一种需要脑洞的题啊。。。
NanoApe
计数器
分类
搜索
听听看？
最新留言
最新评论
链接
RSS
