Solve Record #2

不想多说什么了,明天就是第一次noip(说不定就是最后一次了吧)

主要是整理自己以前做题目犯的很多奇葩的错误
以及整理心情吧……

bzoj篇

秀智商篇




[SCOI2006]整数划分

能拆多少3拆出多少3,剩下的拆成2
练习高精度乘法

[Ceoi2011]Match

untitled弱化,kmp+树状数组,应该不会wa

[Neerc2007]游戏

奇怪的dp算期望

[Usaco2005 Dec]Scales

我搜索做太少了QAQ……TLE到死……发现是搜索姿势不对……

[Usaco2009 Mar]Moon Mooing

模拟,不要看错题目啊喂!

[Baltic2008]Mafia

真的有这么裸的最小割么= =……不明白为啥bzoj过的人这么少

[Baltic2003]Barrel

简单的物理题,bzoj上没有spj

2103: Fire 消防站

[Shoi2005]树的双中心

树高给定,比较小,所以O(nh)水过、

1875: [SDOI2009]HH去散步

矩阵乘法

2587: [Ceoi2011]Team

dp加上输出方案,记下某个状态是由哪个状态转移过来就可以了

[Usaco2006 Mar]Mooo

[Apio2010]patrol 巡逻

容易发现这题在k=1的时候,就是找树上的一条最长链,k=2的时候,就是找两条链,使得它们的长度和-它们的重叠长度最大
通过调整法可以发现k=2,存在最优解,一条链为直径,那么这样就好dp了

for(int i=last[v];i>=0;i=next[v])

因为这个TLE不想说什么了= =

2127: happiness

最小割建模,我dinic一开始忘记加当前弧优化,TLE

[Usaco2010 Nov]Cow Photographs

逆序对的变种(或者说强化?)

[Spoj 2021]Moving Pebbles

博弈论,因为这个游戏显然不同游戏之间会互相影响……不能用sg
所以推结论,容易发现n为奇数的时候,先手必胜
n为偶数的时候,先将石头排好序
后手必胜当且仅当对于所有i,第2i-1堆石头和第2i堆的数目相等

证明略
注意输入数据的石头数目非常坑……需要高精度
不过输入数据比较弱……
我没有排序就ac了= =

1034: [ZJOI2008]泡泡堂BNB

学习clj的做法……感觉他的比较好理解……vfk的证明太长不想看……

[POI2008]BLO

割点

但是由于以前都没有实现过这个所以还是很小心地实现的= =

调了好久发现是暴int了= =感觉不科学……然后用longlong就ac了
#[Usaco2005]Part Acquisition

#[Usaco2006 Mar]Water Slides
贪心匹配即可……以前看不懂题面就没有做
#[Usaco2009 Nov]lights 燈
中途相遇法+dfs搞出最优解,高斯消元也可以,但是高斯消元后依旧要dfs弄出异或方程最优解= =

1597: [Usaco2008 Mar]土地购买

注意被其它土地包含的话,这个土地就无效了
然后排序上斜率优化就好了
cheat了= =

SGU 421 k-th Product

给出n个整数a1, a2, …, an,问从中选m个数乘积第k大是多少。
非常恶心……要手写Log 避免精度误差……
新技能get:泰勒展开加二分求log
sgu上因为精度问题过不去……
bzoj上过得去囧= =
和purpleslz交了好久……
最终放弃治疗

Big Number

两个整数N和K,输出N!的K进制的位数。
小数据直接暴力,大数据用近似公式……
大数据

int n=in(),k=in()
这样的答案这样有什么不对吗?
ans=(0.5 * log(2 * pi)+(n + 0.5)*log(n)-n*log(e))/log(k);
我不明白……
反正改称这个之后就过了……
ans=(0.5 *  log(2 * pi)+((double)n + 0.5)*log(n)-(double)n*log(e))/log(k);

谁来帮我解释一下……

1407: [Noi2002]Savage

1477: 青蛙的约会

复习解线形模方程(组)

2172: Mario填格子

构造题……
需要用到大整数质因数分解= =
然后我以前也没实现过这个……
写了这个wa了很久都不明白哪里错了

LL polarRho(LL n,LL c)
{
      for(int i=2;i<=20;i++)
              if(n%i==0)return i;
      LL x=2,y=2,d=2;
      while(d==1)
      {
                 x=(MOD_MUL(x,x,n)+c)%n;
                 y=(MOD_MUL(y,y,n)+c)%n;
                 y=(MOD_MUL(y,y,n)+c)%n;
                 d=gcd(abs(x-y),n);
      }return d;
}
你有见过这样的错误么= =
LL x=2,y=2,d=2;
while(d==1){...}

还是太naive了

[Usaco2006 Jan] The Grove

2111: [ZJOI2010]Perm 排列计数

数据加强过
其实加强的数据……我感觉就是卡组合计数的计算方式……
C(m,n)=n!/((n-m)! * m!)对吧
然后很多人预处理出 f[i]=i! mod P(比如我一开始的时候= =)
算组合数的时候直接f[n]/(f[n-m] * f[m]) mod P
可是我们忽略了一个问题……当i>=P的时候,f[i]=0
然后要算C(m,n) mod P……可能虽然n>P但是C(m,n)!=0 mod P
这样子就悲剧了……
所以正确做法大概是(个人的正确做法,有更简单的吧= =)
首先用lucas定理判断C(m,n)是否等于0 mod P
然后如果确定C(m,n)不等于0 mod P
那么f[n]/(f[n-m] * f[m])的分子的p的因子的指数一定等于分母p的因子的指数,因为组合数一定是个整数……
所以我们改变f[]的定义……f[i]=i!去掉所有P因子后 mod P的值
这样子直接f[n]/(f[n-m] * f[m])就科学了

[POI2007]立方体大作战tet

树状数组+贪心……
很早以前贪心是想出来了,但是由于智商是硬伤,不知道怎么模拟……
最近yy出来了就ac了

[Usaco2010 Nov]Feed 购买饲料

dp……然后推一推就发现可以单调队列

[Usaco2007 Jan]Tallest Cow

一个条件非常重要……那么就是区间只有包含关系,没有相交关系……
知道这个就随便做了……但以前没想出来囧

[Usaco2009 Mar]Cleaning Up

一个条件非常重要……就是最优解里面的分段,每一段的种类不超过sqrt(n)
知道这个就随便O(n^1.5)dp了
因为一些,b原因调了好久……好在是1A

[Usaco2008Nov]安慰奶牛cheer

简单的最小生成树
对于一个区间集合

,b之星 集合的交与并

Description

{A1,A2……Ak}(K>1,Ai不等于Aj(i不等于J),定义其权值

S=|A1∪A2∪……AK| * |A1∩A2……∩Ak|

即它们的交区间的长度乘上它们并区间的长度。

显然,如果这些区间没有交集则权值为0。

Your Task

给定你若干互不相等的区间,选出若干区间使其权值最大。

虽然是,b之星的题目,但是题目还是很好的= =……

首先推结论:调整法容易证明,不可能选两个以上的区间……

所以答案一定是两个区间的权值……

然后排序后发现可以利用某种单调性避免O(n^2)枚举……

1633: [Usaco2007 Feb]The Cow Lexicon

dp……别想复杂了……我一直在想ac自动机之类的……

[Usaco2006 Mar]Lights Out

可以idfs……但状压dp靠谱一些吧……

1956: Pku3763 Tour in Wonder Land

输入一棵树,添加最少的边使得存在从1开始的哈密尔顿回路
SOL
其实这个的答案就是树的最少链覆盖数= =
证明自己思考

1907树的路径覆盖

贪心即可……
树形dp也可以

3038: 上帝造题的七分钟2

GSS4,并查集解决

3037: 创世纪

内向树,题解的解法比较有趣:
先枚举一条环上的边,然后删掉,当成普通的树dp来做
然后再保留这条边,再来一次树dp……还是比较好写的= =

1590: [Usaco2008 Dec]Secret Message

Trie

1095: [ZJOI2007]Hide 捉迷藏

贴的qtree4点分治代码……

2565: 最长双回文串

manacher

1950: [Ceoi2006]Link

学习了wzy的环套内向树的写法……感觉简洁多了……

1224: [HNOI2002]彩票

各种剪枝……

3256: 基因序列相似性问题

就是CF某题……当时我比赛的时候要求输出方案……结果我wa到死……
这题不需要输出方案……随便做= =
其实输出方案的话……姿势正确也是很好写的

2424: [HAOI2010]订货

随意dp,可以网络流……
dp需要一个小优化……还是比较显然的……

2720: [Violet 5]列队春游

推导结论……忘记怎么证明了= =

3048: [Usaco2013 Jan]Cow Lineup

利用某些单调性,可以O(n),我比较沙茶,上了主席树……






cojs篇

,b篇









做cojs的历年 noip原题……

[NOIP2009] 最优贸易

很显然的SPFA……但是SPFA写错一定是智硬对吧……

[NOIP2009] Hankson的趣味题

写的分解质因数……复杂度大概是比较稳定的……写完一大坨之后才知道人家暴枚也能过……
所幸是1A

[NOIP2009] 潜伏者

这种题目不能1A的都是脑残,对我就是脑残……数据弱,我的代码少判了一个情况,居然拿了90

[NOIP2010] 引水入城

yy不出覆盖区间连续我真是太,b了……区间覆盖的贪心还写错更,

[NOIP2010] 乌龟棋

无脑dp

520. [NOIP2010] 关押罪犯

无脑并查集

518. [NOIP2010] 机器翻译

无脑模拟

632. [NOIP2011] 观光公交

贪心,暴力nk,更快的方法不会,yy了很久
网络流的图不会建囧……

[NOIP2011] 聪明的质检员

直接按次数二分

[NOIP2011] 计算系数

算组合数,快速幂
其实也可以不用快速幂……只用递推……但是我忘记怎么做了……

[NOIP2011] 玛雅游戏

搜索,不需要剪枝,因为写得姿势比较正确,加上样例比较强,十分钟就1A了

[NOIP2011] 选择客栈

这种题目还1A不了,是不是很智障……
数组开小呵呵呵,边界条件错误呵呵呵

[NOIP2011] 铺地毯

题目看错呵呵呵

[NOIP2012] 疫情控制

想了个错误贪心呵呵呵
证明错误后搞不出正确的呵呵呵
狂交呵呵呵

[NOIP2012] 借教室

写个线形做法都能wa呵呵……
忘记开文件输入输出呵呵

[noip2012]同余方程

……

[NOIP2012]开车旅行……

要注意set< pair< int,int> >要是lower _ bound一个比set里面所有pair都大的pair时,返回的指针很奇怪= =
如果是set< int >的话会返回一个set中的最大值(为空则为0)
因为这个掉了20HP

[NOIP2012]国王游戏

我是,b我自豪,高精度数字大小比较写错能更, ?

[NOIP2012] Vigenère 密码

我是,b……忘记关调试信息2333





codechef篇:

六道sb题做掉了……还有challenge和三道恶心题目
既然是一个嘴巴选手,那么就嘴巴ak好了

codeforces篇

智商硬伤,面对某n=3 * 10^5的题目,怒上O(nlog^3n)方法……光荣tle

总结:

以下是最近的沙茶错误:

  1. 文件输入输出
  2. 关调试输出
  3. 复杂度算错
  4. stl用错
  5. 看错题
  6. 数组开小
  7. 贪心想错
  8. 高精度写错
  9. 各种手误却不写对拍
  10. 智商压制

Comments

comments powered by Disqus