solve record #1

很多水题不写总结的话以后在见到就很可能不会做了=w=

以下是记录:

bzoj 1320

即 Pku3530

解不等式

求一个最小正整数解 如果存在正整数x使得 那么解显然 考虑递归: 如果L/D与R/D之间没有一个正整数,那么引入未知数y,做一个变形

然后有

那么因为无平凡解,所以我们可以对做这个变形,得到这个方程:

这样子就缩小了范围……可以递归做了,注意边界条件

bzoj1269 [AHOI2006]文本编辑器editor

splay的裸题,没啥好说的,使劲写就好了

bzoj2721[violet5]樱花

bzoj2048 书堆

物理经典题,根据重心之类的性质弄个递推式,发现是调和和,就可以小范围暴力,大范围逼近了

推导很简单……懒得写了……类似题目推导链接

主席吐槽:这种陈题出出来干什么,我小学就知道这怎么做

bzoj 3016

问题描述

给定长度为n的一个括号序列,每次修改可以修改一个位置的括号,若这个括号为’(‘,则修改为’)’,若这个括号为’)’,则修改为’(‘,问最少修改多少个使得原括号序列合法。

解答:

主代码如下

gets(st);
n=strlen(st);
for(int i=0;i<n;i++)
{
    d+=st[i]=='('?1:-1;
    if(d<0)d+=2,ans++;
}ans+=d/2;
printf("%d\n",ans);

bzoj1984 月下“毛景”树

没明白毛景是啥...树上路径赋值路径加以及路径最大值询问,权在边上

裸树链剖,一开始权在边上让我不爽了一会……不过写完没调试没拍就a了……

bzoj1828 [Usaco2010 Mar]balloc 农场分配

排序加线段树,贪心正确性要yy一下才能弄出来……

随便写一写就1Y了……果然线段树不能更好写……

bzoj1942: [Ceoi2007]Ministry

描述

一颗有根树,每个节点最多三个子节点

叶子节点深度为1,非叶子节点深度为它孩子的深度最大值+1

给括号序列问深度为d的子树有多少本质不同的(即不同构的)

解答:

有根树同构的正常解法是括号序列最小表示……

但感觉这题上最小表示复杂度会不对……

所以就hash吧……

叶子节点的hash值为1,

v是u的子节点

别问我k,Z,P是啥,叉姐说:k是魔法!Z也是魔法!

用set去重

因为我rp不好一开始连续施法都不对,后来咒语念对了就a了

2002 [Hnoi2010]Bounce 弹飞绵羊

维护一个森林,支持link,cut,询问一个节点到根经过的节点数

普通LCT随便写,1Y

3050[Usaco2013 Jan]Seating

描述

m(m<=300,000)个操作。操作分2种:

1.A p,表示把编号最小的空着的长度为p的区间图上颜色。

2.L a b,表示把从a到b的区间(包括端点)全部擦干净(没颜色还是没颜色)。

Q:有多少个操作1不能实现?

SOL

没啥好说的,通过思考之后可以用线段树快速模拟操作以及判断1是否可行

没了

bzoj 2815: [ZJOI2012]灾难

可做题……我少数能看懂题意的zjoi题目……

建出一个叫“灾难树的玩意”……然后dfs……没了

写倍增LCA的时候手滑导致没有1Y

bzoj2600: [Ioi2011]ricehub

O(n)扫一遍

bzoj1398: Vijos1382寻找主人 Necklace

裸最小表示法

2434: [Noi2011]阿狸的打字机

以前yy过这题,弄出fail树后可以转化为询问区间[l,r]中权值为x的位置个数

当时我即不会主席树也脑残没往离线上想

现在会了就随便写一写……然后就1y了

bzoj1081: [SCOI2005]超级格雷码

题意略

乱搞题的一种?我不会做看别人代码的……XD

bzoj3143: [Hnoi2013]游走

弄出节点期望走到次数后就可以快速求边期望走到次数,然后排序贪心赋值

求节点的期望可以用高斯消元

当然模拟很多次游走说不定也能算出期望233……

唯一的坑点就是精度,我的高斯消元数值稳定性较差,double的话会刚好有0.001的误差(题目就是精确到0.001……)……用了long double才a

bzoj3110: [Zjoi2013]K大数查询

可以用全局二分碾压,我写的是线段树套线段树……动态开点下传标记是忘记开子节点就把标记清了囧……不能更傻……调了很久……

1578[Usaco2009 Feb]Stock Market

简单但需要一点想法的dp……太弱导致wa了几发

bzoj2876: [Noi2012]骑行川藏

lich讲了一下拉格朗日求极值……算是交作业……没了

1491: [NOI2007]社交网络

以前一直不知道怎么floyd求最短路个数

yy了一个居然是对的

1500: [NOI2005]维修数列

有点恶心……使劲写……然后没调过了样例就1Y了囧……我的代码比较慢

2806: [Ctsc2012]Cheat

二分加dp很好想,容易发现决策区间单调,就可以用SAM快速弄出决策区间然后单调队列优化了

2225: [Spoj 2371]Another Longest Increasing

STL在bzoj上可以碾压过去,这题可以用cdq分治(三维偏序最长链……),也可以二分加平衡树……第二种方法用stl的set的话非常好写……

2467: [中山市选2010]生成树

发现一个小性质之后随便推公式……公式是

2986: Non-Squarefree Numbers

找出第N个不是squarefree的数

dfs+容斥原理+二分

2501: [usaco2010 Oct]Soda Machine

排序后扫一遍

3039: 玉蟾宫

2890: 序列的故事

给出一个由小写英文字母组成的字符串S,再给出q个询问,要求回答S某个子串的最短循环节

就是poi19某题……hash或后缀数组可以水过

2982: combination

裸lucas定理

2274: [Usaco2011 Feb]Generic Cow Protests

给出n个数,问有几种划分方案(不能改变数的位置),使得每组中数的和大于等于0。输出方案数除以 1000000009的余数。

想个暴力dp后再想办法优化,用离散化+树状数组水过

3083: 遥远的国度

树链剖分,注意dfs时候满足dfs序性质,这样就可以支持子树查询修改,换根由于没有树的形态不变……树链剖分依旧是可以支持的..

2809: [Apio2012]dispatching

可并堆是最方便的做法,我们也可以splay启发式合并甚至上树链剖分...

我写的是skew heap ,速度还不错

2396: 神奇的矩阵

给出三个行数和列数均为N的矩阵A、B、C,判断A*B=C是否成立。

用蒙特卡洛式的方法判定,水过

2506: calc

乱搞,不需要什么高级数据结构……【其实有种思想叫小范围暴力,大范围分块,这题的分块性比较特殊】

1864: [Zjoi2006]三色二叉树

随便dp……代码可以用点技巧写得短一些……

1816: [Cqoi2010]扑克牌

二分+贪心判定……最近的某次cf有这个的类似题目

spoj COT

主席树不多说

[baltic2009]Radio Transmission

kmp即可……循环节的一些特性

bzoj1044: [HAOI2008]木棍分割

以前一直想写但一直忘记写的玩意……第一问二分第二问dp就可以了~

bzoj2072: [POI2004]MOS

一种利用贪心性的dp……经典问题

bzoj2347: [Baltic2011]Meetings

用调整法搞出一些性质,推点公式,然后就可以了

理论是那个这样就行了……算的时候要不停求x^k……我手写快速幂就tle了……然后T了三次之后改用系统的pow()函数……就过了……

主席告诉我c++自带的pow()是O(1)的

2799: [Poi2012]Salaries

推导出一个节点可以被赋值x的充分必要条件后,可以用一种奇怪的姿势碾压,推荐看hza的题解

3261: 最大异或和

函数式trie碾压

2013: [Ceoi2010]A huge tower

有N(2<=N<=620000)快砖,要搭一个N层的塔,要求:如果砖A在砖B上面,那么A不能比B的长度+D要长。问有几种方法,输出 答案 mod 1000000009的值

注意题面,在上面是指恰好在上面...然后就可以yy一些什么了吧……

1292: [CTSC2009]魔幻花园

写过题解,略过

3301

3299

3296

太水略过

1455: 罗马游戏

可并堆水过

1251: 序列终结者

splay水过

Comments

comments powered by Disqus