开始做noip真题

noip2006    100
之前做过一次，做了一般弃疗
今天在学校又做了一次，没什么大问题
就是程序填空那里答案的形式和我的形式不一样
话说真的有“专家上机评测”这种东西吗？

noip2007    98.5
选择题错了一个，看错了那个欧拉图的判定
问题求解也很好玩：N个人在操场里围成一圈，将这N个人按顺时针方向从1到N编号，然后从第一个人起，每隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直到操场只剩下一个人，记这个人的编号为J(N)，例如，J(5)=3，J(10)=5，等等。 则J(400)=
这题居然还给了提示：分析N=2^n+r
在提示的指引下想出了方法：首先如果N=2^n的情况，显然就是1，因为每次去掉偶数后重编号再去掉偶数，然后1号一直是奇数，所以最后肯定剩下1号。然后我们考虑现在多了r个人，显然第一轮我们至少可以干掉r个人，原因很简单：第一轮干掉的然数为(2^N+r)/2>r，所以我们干掉r个人后，假设第i个人下一个的编号为d，那么从d开始按照1,2,...,2^n编号最后肯定是一号留下，也就是d号。那么d等于多少呢，显然就是2*r+1辣

noip2008    89
选择错了3t，问题求解居然都错了一个
问题求解还是蛮有趣的：书架上有21本书,编号从1到21,从其中选4本,其中每两本的编号都不相邻的选法一共有______种.
我开始一直在用容斥做，即：C(21,4)-3*C(20,3)+2*C(19,2)-C(18,1)，然后发现这是有问题的，因为在算C(20,3)时事实上也有重复C(18,1)
正确的做法是：我们考虑已经取出了4本书，显然剩下17本，我们要把这四本书插回17本书中，要求两个不相邻，即同一个空位只能插一本，所以答案就是C(18,4)=3060
当然这种题一般动态规划是能解决的：设f[i][j]表示前i本书取j本且两两不相邻的方案数，f[i][j]=f[i-2][j-1]+f[i-1][j]

noip 2009   89.5
除了多选其他全对
然而多选只对了3题是闹哪样...
要想背古文一样背oi...
简直excited

noip2012
做了一半不想做了
选择提错了5道还有卵用啊...
感觉被文化课的作业搞的很不爽...
特别是国庆作业，妈的这也太多了吧...
算了，认了

noip2013  95.5
单选居然错了3题TAT
主定理没有理解到位啊TAT：
T(N)=2*T(N/2)+2*N
首先后面那个f(n)=2*N=O(N)！！！！这是重点...
然后主定理f(n)=log(2)/log(2)所以T(N)=N log N
然后问题求解T2很有趣，我还记得当前太SB不会作：
fn表示从n号节点跳到1号节点的平均跳跃次数
f1=0
f2=2

f2=(f1+f2)/2+1
f2/2=1
f2=2

f3=2.5

f3=(f1+f2+f3)/3+1
f3=2/3+f3/3+1
2/3*f3=5/3
f3=2.5


f4=(f1+f2+f3+f4)/4+1
  =4.5/4+f4/4+1=f4
3/4*f4=8.5/4
f4=8.5/3

4/5*f5=(f1+f2+f3+f4)/5+1
4/5*f5=(4.5+8.5/3+5)/5
f5=(4.5+8.5/3+5)/4
  =(13.5+8.5+15)/12
  =37/12

noip2014   100
AK了很正常，去年刚刚做过
不过感觉问题求解第一题很有趣，问：用1 1 2 4 8 8能组成多少个不同的4位数
我的解法是这样的：
首先考虑4位数不重复，显然就是P(4,4)=4!=24
然后考虑只有1重复，那么其他三个任选两个，然后就有3个空，把1 1插进去，一共有P(3,2)*6=36
然后考虑只有8重复，做法同上，一共有P(3,2)*6=36
最后是只有1 1 8 8，暴力1188 1818 8811 8181 1881 8118，共有6种
所以就有102种

未完待续...

决战noip2015初赛
1.电子管：1946-1958
  晶体管：1959-1964
  集成电路：1965-1970
  大规模集成电路：1971-now
2.第一台计算机：ENIAC，与1946年诞生于宾夕法尼亚大学
  （实际为ABC...但是那个貌似没这个出名？）
  第一台具有存储程序功能的计算机：EDVAC（有冯·诺伊曼提出并设计，第一次使用二进制）
3.冯·诺伊曼理论
  五大核心：存储器，控制器，运算器，输入设备，输出设备
  存储程序思想：把计算方法写成程序，与数据一起输入计算机中，计算，输出结果
4.字长：运算的二进制位数，现在一般为32位 64位
  主频：主时钟一秒内发出的脉冲数，在一定程度上决定计算机运行速度（但不是完全决定！）
5.CAD(design):计算机辅助设计
  CAM(manufacture):计算机辅助制造
  CAE(Engineering):计算机辅助分析
  CAI(Instruction):计算机辅助教学
  CAT(Test):计算机辅助测试
  MIS：管理信息系统（Management Information System，简称MIS）
6.CPU中央处理器
  由控制器，运算器，一些寄存器组成
7.存储器
  内存和缓存：cpu可以直接访问到的（高速缓存是为了加快cpu从缓存中读取的速度）
  外存：cpu不能直接访问的（必须调进内存才能使用） 例如光盘（CD-ROM），硬盘，软盘，闪存（也叫辅存）
  主存：大致等价于内存，严格说：只有当内存中没有高速缓存才称为主存
  高速缓存是介于cpu和主存之间的小容量存储空间，他的访问速度大致等同于cpu的速度
  主存分类：ROM RAM
8.cpu访问速度：寄存器 高速缓存（也叫快存） 内存 外存
  存储容量：外存 内存 高速缓存 寄存器
9.针式打印机、喷墨打印机、激光打印机都属于输出设备
10.地址总线：决定了cpu所能访问的最大存储器容量
  控制总线：反映了数据的状态和传输方式
  数据总线：决定每次传输数据的大小
  但每次传输的数据并不代表cpu都能访问到
11.计算机主机指除去输入 输出设备的结构
   即cpu+内存=运算器+控制器+（计算机内部）存储器
12.计算机指令系统与cpu有关
   不同厂家生产的cpu所能执行的指令集不相同
13.奇偶校验法是通过统计二进制中某个1或0的个数来判断在传输过程中是否有位置上的数字改变
   它只能得出是否出现差错，但不能检验是在哪一位发生差错的
14.总线是实际存在的，它属于计算机的硬件部分
15.常见的cpu和存储器
16.用静电吸附墨粉后转移到纸张上：是激光打印机（不是喷墨打印机）
17.绘图仪是输出设备
18.进制转换神马的，只要记住x进制转10进制和10进制转x进制就好了
   x进制转10进制：权展开求和
   10进制转x进制：整数部分/x取余倒序，小数部分*x取整正序
19.原码，反码，补码
   原码：x>=0在二进制最高位补0，x<0在二进制最高位补1
   反码：整数与原码相同，负数保持符号位不变其它取反
   补码：即在mod M意义下x的值，显然x>=0等于原码，x<0补码等于x+M（更简单的方法：反码+1）
   n为二进制所能表示的范围是[-2^n,2^n-1]
20.定点数：定点整数 定点小数
21.浮点数：阶码和尾数 N=2^E*S  E是阶码 S是尾数 如：1011101B=2+7*0.1011101
22.汉字交换码：GB2312－80标准包括了6763个汉字，按其使用频度分为一级汉字3755个和二级汉字
3008个。一级汉字按拼音排序，二级汉字按部首排序。
23.计算机软件：系统软件 应用软件
   系统软件：通常是操作系统（OS-Operating System）
   应用软件：为了某一应用目的编写的软件
24.后缀名：
  bat，com、exe、sys、tmp、zip
  doc、xls、txt、htm
  bmp、gif、jpg、psd
  wav、avi、mp3、swf
25.从软盘和可移动硬盘上删除的文件将被彻底删除
26.计算机病毒的特点：传播性、潜伏性、破坏性与隐蔽性
27.TCP/IP协议的四层：链路层，网络层，传输层，应用层
28.OSI七层：物理层，数据链路层，网络层，传输层，会话层，表示层，应用层
29.ipv5和ipv6一点关系也没有，IPv6是IPv4的替代版本。IPv6是128位 IPv4是32位！
30.WWW（World Wide Web）：万维网
   URL（Uniform Resource Locator）：统一资源定位器
   HTTP（Hypertext Transfer Protocol）：超文本传输协议
   FTP（File Transfer Protocol）：文件传输协议
   TCP（Transfer Control Protocol）：传输控制协议
   SMTP（Simple Mail Transfer Protocol）：简单邮件传输协议
31.C和pascal不支持面向对象 但object pascal是面向对象语言
32.操作码就是操作指令，操作数就是输入数据
   计算机能直接执行的指令包括操作数和操作码两部分
33.编译：把高级程序编译成计算机语言，生成编译后的文件
   解释：逐句翻译，不生成文件
34.IP地址分类：最高位1..126为A类，128..191是B类，192..223是C类
35.图灵是英国人 冯·诺伊曼是美籍匈牙利人
36.第一种面向对象语言：simula 67语言 
37.
   排序法     平均时间    最差情形    稳定度    额外空间    备注
   冒泡               O(n2)      O(n2)             稳定      O(1)        n小时较好
   交换               O(n2)      O(n2)             不稳定      O(1)        n小时较好
   选择               O(n2)      O(n2)             不稳定      O(1)        n小时较好
   插入               O(n2)      O(n2)             稳定      O(1)        大部分已排序时较好
   基数               O(logRB)      O(logRB)     稳定      O(n)        B是真数(0-9)， R是基数(

个十百)
   Shell       O(nlogn)      O(ns) 1<s<2     不稳定      O(1)        s是所选分组
   快速               O(nlogn)      O(n2)             不稳定      O(nlogn)  n大时较好
   归并               O(nlogn)      O(nlogn)     稳定      O(1)        n大时较好
   堆               O(nlogn)      O(nlogn)     不稳定      O(1)        n大时较好
38.第一款cpu不是Inter发明的，在那之前有晶体管和电子管的cpu
   Intel最早发明的是微处理器
39.RAM是指可按需随意取出或存入，且存取的速度与存储单元的位置无关的存储器
   并不是指存储的位置随机
40.网络协议分层不是为了兼容，而是根据网络分层模型来的
41.P/NP问题：
    复杂度类P包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题；
    类NP由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成
   NPC问题：NP中的某些问题的复杂性与整个类的复杂性相关联.这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的.这些问题被称为NP-完全问题(NPC问题).
   一个问题如果是NPC类的，就意味着在解决该问题时，不存在一个具有多项式时间复杂度的算法。但这一点还没有得到理论上证实，也没有被否定
42.noip于1995年开始举办
   noi于1984年开始举办
   apio于2007年开始举办
   ioi于1989年开始举办
43.1948年，克劳德·香农将热力学中的熵引入信息通信领域，标志着信息论研究的开端
44.Unicode 是为了解决传统的字符编码方案的局限而产生的，它为每种语言中的每个字符设定了统一并且唯一的二进制编码，以满足跨语言、跨平台进行文本转换、处理的要求。
44.BIG5和GB 表示的汉语unicode编译方式,BIG5是繁体规范,GB是简体规范
45.浏览器是指可以显示网页服务器或者文件系统的HTML文件内容,并让用户与这些文件交互的一种软件。
   文件资源管理器是一项系统服务，负责管理数据库、持续消息队列或事务性文件系统中的持久性或持续性数据。
46.地址总线为x位，则最大寻址量为2^x byte
47.tcp/ip各层协议用途
   数据链路层是负责接收IP数据包并通过网络发送，或者从网络上接收物理帧，抽出IP数据包，交给IP层。
   网络层负责相邻计算机之间的通信，提供源节点和目的节点之间的信息传输服务，包括寻址和路由器选择等功能
   传输层提供应用程序间的通信
   应用层向用户提供一组常用的应用程序
48.Flickr，雅虎旗下图片分享网站，属于Web.2.0的应用
   Web2.0技术主要包括：博客（BLOG）、RSS、百科全书(Wiki)、网摘、社会网络（SNS）、P2P、即时信息（IM）等。
49.NOIP竞赛推荐使用的语言环境：
   推荐的：free pascal   Lazarus   Dev C++    gcc/g++
    不推荐的：TP7(turbo pascal 7)   TC(turbo C)   Visual C++
50.c++运算符优先级
51.windows 9x是一种多任务图形方式的操作系统
52.二叉树的度是指叶子结点的个数，不是指连的边数
53.在微型计算机系统中，I/O接口位于总线和输出输入设备之间。 
54.调制解调器把计算机上的数字信号转成沿电话线传输的模拟信号，另一边的调制解调器收到模拟信号后在转化为数字信号
55.网络操作系统！=一般的操作系统，如dos,os/2不属于网络操作系统
56.冷启动:关机状态下按POWER启动计算机，叫做冷启动 。 
   复位启动:按机箱上的RESET按纽来启动，叫复位启动 。
   热启动:通过开始菜单、任务管理器或者快捷键，重新启动计算机，叫热启动。 
57.微机内的存储的地址是以字节编址的
58.ASCII码是七位二进制数组成
59.常见数据库：DB2 Oracle Informix Sybase   SQL Server   PostgreSQL   mySQL
60.结构化程序设计的一种基本方法是自顶向下，逐步求精

【题目描述】：

【题目解法】：
    不要被tag吓倒了，其实是个SB经典题辣
    我们枚据一下分割点，变成两边去最大值
    我们考虑一边，我们可以弄出前缀异或
    然后变成两个数异或最大，直接上主席树拆位贪心即可
    然后在弄个后缀
    两边加起来max一下就好

阅读更多……

【题目描述】：
    一个正整数数列 A[1]…A[n]，
    那么 目标是求另一个正整数数列 B[1]…B[n]， 使得对于任意的 1≤i<n 有 B[i] ≤B[i+1]，
    而且使得 Ans = Max{|A[j]-B[j]|,1≤j≤n}尽量 小。
【题目解法】：
    我们发现只有逆序对才会对答案产生影响
    我们把所有逆序对提到同一高度即可
    显然两个逆序对变成他们的中位数最优
    因此我们取逆序对之差的最大值作为答案
    最后把答案/2即可

阅读更多……

【题目描述】：
    平面上有N个点，Xaviera想找出周长最小的三角形。
    由于点非常多，分布也非常乱，所以Xaviera想请你来解决这个问题。
    为了减小问题的难度，这里的三角形也包括共线的三点。
【题目解法】：
    我们可以用类似分治法求最近点对的方法去做
    对点集按照x坐标排序
    首先设计solve(l,r)表示求[l,r]间的点构成的最小周长三角形
    然后我们分治solve(l,mid) solve(mid+1,r)
    现在我们就要考虑处理两边的点共同构成的最小周长三角形
    我们知道在该题中三角形内任意两边之和大于等于第三边
    所以假设我们现在的最有答案为ans，那么任意一条边的长度不得超过ans/2才可能成为最优解
    所以我们以a[mid].x作为中间的基准，向两边各延伸ans/2个单位，只有这些点才可能构成最优解
    然后我们把这些点按照y坐标排序
    如果两个点的y坐标之差>ans/2那么显然也不能成为最优解
    然后据说这样每个点最多和16个点进行判断
    所以复杂度就是O(n log n log n * 16 * 16)
    当然内部排序可以归并做到O(n log n * 16 * 16)

阅读更多……

【写在前面】：
    为什么要来写这个东西呢？
    记得第一次解除是在初三的时候，具体动机我已经忘了
    但是那是太弱了，没有看懂，只是强行记住了一些结论
    这次的NOI2015 Day2 T3告诉我这是个很有用的东西
    我们不是Po姐，所以如果不会最小流T3就是死路一条...
【参考】：

http://www.cnblogs.com/kane0526/archive/2013/04/05/3001108.html

http://www.cnblogs.com/iwtwiioi/p/3826483.html?utm_source=tuicool

代码参考：http://blog.csdn.net/qq172108805/article/details/7802832

【分类】：
    首先这种问题大致可以分为3类：
    无源汇有上下界最大流
    有源汇有上下界最大流
    有源汇有上下界最小流
    （为啥没有“无源汇有上下界最小流”呢？
【问题】：
    尽管三类问题有些不同，但相同点就是“有上下界”
    何谓“有上下界”呢？
    顾名思义：给出A(u,v)<=B(u,v)（(u,v)属于网络图）
    那么对于任意一条边(u,v)，他的流量满足A(u,v)<=f(u,v)<=B(u,v)
    即每条边最少流过A(u,v)，最多流过B(u,v)
【基础】：
    对于网络流来说有一条性质最为基础，即流量平衡
    既满足：sigma(f(u,i))=sigma(f(i,v))
【一些约定】：
    为了方便说话，我们做一些约定：
    设网络图为G=(V,E)
    设E中的每条起点为u终点为v下界为down上界为up的边为(u,v,down,up)
【无源汇有上下界最大流】：
    首先我们这样想：既然要满足所有下界被满足，那么我们可以直接流过下界
    也就是说我们可以把边(u,v,down,up)直接改为(u,v,0,up-down)
    这样题目就转化为没有下界的网络流了
    但是注意【基础】中所提及的流量守恒，这样跑出来的结果不一定满足流量守恒
    那么我们怎么判断是否存在一种方案满足流量守恒呢？
    我们从简单入手：假设有两条边(u,i,down1,up1)和(i,v,down2,up2)
    我们第一条边初始流过down1，第二条边初始流过down2
    我们发现如果down1=down2那么一切平安无事
    如果down1>down2那么说明我们的第二条边还要流过down1-down2
    如果down1<down2那么说明我们的第一条边还要流过down2-down1
    那么怎么使得这些边满足呢？
    我们设置源点s，汇点t
    如果down1>down2，那么连边(s,i,0,down1-down2)
    如果down1<down2，那么连边(i,s,0,down2-down1)
    然后如果跑最大流发现与s相连和与t相连的边都都流满了那么说明一下两个事实：
    “如果down1>down2那么说明我们的第二条边能够流过down1-down2”
    “如果down1<down2那么说明我们的第一条边能够流过down2-down1”
    那么原图存在满足的流，这样就可以判断可行性了
    由于没有实际的源汇，所以求没有必要求出最大流
【有源汇有上下界最大流】：
    顾名思义就是有源点s和汇点t
    首先我们可以判定是否存在可行流
    我们添加边(t,s,0,INF)就可以把图转化为无源汇的网络图了
    然后添加S，T，用上面的方法即可判定
    然后现在求得的maxflow并不是答案
    因为此时只是满足了所有下界，原图中s t的一些路径上还有残余的流量没有跑完
    所以我们就要把S，T以及相连的正向边删去，然后求s到t的maxflow，两次的maxflow之和即为答案
    注意第二次求最大流时虽然删除了S，T但是与之相连的反向弧并没有消失，所以实际上点集V还是包含了S，T的（注意初始点集大小
【有源汇有上下界最小流】：
    这个似乎是最难的，我们考虑依旧有上述方法
    然而我们发现了反例，如下图：(http://www.cnblogs.com/kane0526/archive/2013/04/05/3001108.html)

    原图存在循环流我们没有利用，导致最小流变大
    我们考虑这样做：先不添加(t,s,0,INF)，直接跑一边Sap(S,T)，然后加上(t,s,0,INF)，在跑一遍Sap(S,T)
    第二次的Sap如果满流那么就存在可行解，并且(t,s)的反向弧的流量就是答案
    因为此时正向弧流量最大，那么反向弧就最小啦...
【有源汇有上下界费用流】：
    方法如出一辙（注意此时边的四元组变成五元组，即多了一个费用）
    我们依旧连边(t,s,0,INF,0)
    然后建立S T，依旧按照入度出度连边即可
    然后跑EK(S,T)即可
    UPD：注意这样跑是不对的，我们还要把S T还有(t,s,0,INF,0)删去，然后再跑EK(s,t)才对，理由同上！

例题什么的以后再补

zoj 3231

【题目大意】：
    给你一棵Iphone 苹果 ios 树，然后每个结点上有一定的Iphone 苹果 ios 树，你要将Iphone 苹果 ios 运输达到某个状态，使得均方差最小。 将Iphone 苹果 ios x个从a->b的花费是x*w，w是边权。
【题目解法】：
    上下界费用流
    显然每个数都应该尽量往平均数靠拢，但是如果平均数不是整数，就要考虑某些点可能会多一个
    设平均数为ave
    连边(s,i,0,a[i],0)
    连边(i,j,0,INF,w)
    连边(i,t,ave,ave+1,0)
    用上面的方法即可，注意要跑两边EK

阅读更多……

【题目描述】：
    在完成了古越州圆盘密码的研究之后，考古学家小布来到了南美大陆的西部。相传很久以前在这片土地上生活着两个部落，一个部落崇拜闪电，另一个部落崇拜高山，他们分别用闪电和山峰的形状作为各自部落的图腾。小布的团队在山洞里发现了一幅巨大的壁画，壁画上被标记出了N个点，经测量发现这N个点的水平位置和竖直位置是两两不同的。小布认为这幅壁画所包含的信息仅与这N个点的相对位置有关，因此不妨设坐标分别为(1, y1) , (2, y2), ..., (n, yn)，其中y1~yn是1~N的一个排列。小布的团队打算研究在这幅壁画中包含着多少个图腾，其中闪电图腾的定义图示如下（图腾的形式只与4个纵坐标值的相对大小排列顺序有关）：

崇拜高山的部落有两个氏族，因而山峰图腾有如下两种形式，左边为A类，右边为B类（同样，图腾的形式也都只与4个纵坐标值的大小排列顺序有关）：

小布的团队希望知道，这N个点中两个部落图腾数目的差值。因此在本题中，你需要帮助小布的团队编写一个程序，计算闪电图腾数目减去山峰图腾数目的值，由于该值可能绝对值较大，本题中只需输出该值对16777216的余数（注意余数必为正值，例如-1对16777216的余数为16777215）。
【题目解法】：
    我表示给我一百年也想不到补集转换，就算告诉我，下面那块给我十天也不一定弄出来TAT...
    首先补集转换：
    f[1324]-f[1243]-f[1432]
    =f[1x2x]-f[1423]-(f[12xx]-f[1234])-(f[14xx]-f[1423])
    =f[1x2x]-f[12xx]+f[1234]-f[14xx]
    =f[1x2x]-(f[1xxx]-f[13xx]-f[14xx])+f[1234]-f[14xx]
    =f[1x2x]-f[1xxx]+f[13xx]+f[1234]
    我们先做一些预处理：
    利用树状数组求出L[i],R[i]分别表示i左边/右边比a[i]小的个数
    利用树状数组求出L1[i]表示i左边j满足a[j]<a[i]的L[j]之和
    利用树状数组求出L2[i]表示i左边j满足a[j]<a[i]的j之和
    利用树状数组求出L3[i]表示i左边j满足a[j]<a[i]的a[j]之和
    然后：
    f[1234]：枚举3的位置，那么右边就是(n-i-R[i])，左边就是L1[i]乘起来即可
    f[1xxx]：枚举1的位置，右边(n-i-R[i])，那么直接C(n-i-R[i],3)即可
    f[1x2x]：比较麻烦，我们枚举2的位置，那么右边就是(n-i-R[i])，左边1x设为(x,y)，要满足x<y且a[y]>a[i]，那么我们考虑容斥，我们直接求出2左边含有1的对就是L[i]*(i-1)，然后我们考虑不合法的有两部分：一部分为y<x，那么就是L2[i]；另一部分就是x<y但是a[y]<a[i]的部分，那么就是C(L[i],2)
    f[13xx]：更麻烦，我们枚举3的位置，那么4的话就有(n-i-R[i])个，然后我们设1和那个2的位置为(x,y)，所以我们再次容斥，求出(x,y)满足x<i,a[x]<a[i],a[y]<a[i]，那么就有L[i]*(a[i]-1)（我来解释一下，首先对于x，方案就是L[i]，然后对于y只有大小限制，显然就有a[i]-1个），但是合法的只有其中的y>i且a[x]<a[y]，然后我们考虑不合法的，也有两部分QAQ：一部分是x<y<i，那么就有C(L[i],2)；第二部分就是a[x]<a[y]但是x>y的部分（我在来解释一下为什么不用减去a[x]>a[y]的部分，因为我们考虑a[x]>a[y]且x>y就是123，那么和上一部分就重合了），这一部分就是L3[i]

    看了题解（orz hzwer）先嘴巴AC一发，然后写啊写
    说实话，代码还是挺好写的就是想的太复杂了...
    一晚上就这么过去了TAT......

UPD：托上面flag的福，我居然在10天内想出来了另一种方法

【另一种解法】：
    首先嘛，补集转换是一样的
    然后f[1234]，f[1xxx]比较简单也是一样的
    我们考虑剩下两个
    f[1x2x]：我们枚举2的位置，那么左边就是(n-i-R[i])，然后我们就转化为求出f[132]的答案（注意那个3是指在前三个里面是最大的），我们考虑随便选去(x,y)满足x<i y<i a[x]<a[y]，那么这一块很好求就是把y的L数组做成树状数组即可，然后我们要减去f[231]，这一块也很好做，我们维护一个数组Lmax[i]，我们从左到右插入a[i]时，我们修改Lmax[1..a[i]]+1（即表示23的对数），然后我们枚举是是查询[a[i]+1..n]的和就好，区间修改区间查询线段树就好
    f[13xx]：我们考虑右边有一个4，他的位置和大小都很好确定，直接枚举3，那么4就是(n-i-R[i])，然后我们考虑那个1和2，设为(x,y)，我们变成求f[132]（⊙▂⊙，貌似可以用上面的方法求？你想多了，我们现在枚举的是3不是2）我们考虑数字对(x,y)满足x<i y>i且a[x]<a[i] a[y]<i的对数，就是L[i]*R[i]，然后我们考虑balabalabalabal...没必要这么复杂，我们直接考虑，令Lmin[i]初始是为L[i]，我们从右到左枚举a[i]是令Lmin[a[i]+1..n]-1，然后查询Lmin[1..a[i]-1]，线段树就好...
【总结】：
    我们发现上面的瓶颈在于f[132]，然后枚举的位置不同，解法也不同
    我们考虑一下原因，假设f[xxxx]有3的是确定的，那么我们考虑如果枚举的那个是最大或者最小的，它是可以直接用线段树求的，否则就要考虑容斥原理了，原因嘛，yy一下吧，我已经傻逼了...

阅读更多……

【题目描述】：

【题目解法】：
    哦，忘了给数据范围了,n<=8...显然搜索
    我们考虑剪枝就好
    1.首先只搜一半，另一半是对称的
    2.考虑每个人与最后一个人的胜负情况可以直接算出来
    3.如果当前这个人的得分大于目标得分直接剪掉
    4.（强力剪枝？）我们用f[i]表示某个人用1，3弄出i的最少次数，然后根据当前搜索的情况剪枝
    T了好几发QAQ...

阅读更多……

【写在前面】：
    其实嘛，所谓的总结也就是两道题目罢了
    （标题只是吸引你们系列？
    UPD：下面的叙述中有些地方会把麻将和纸牌弄混，凑合这看吧，道理是一样的（雾...
【麻将问题】：
    首先这类问题大概是怎么样的呢？
    它应该是基于麻将和纸牌一类游戏的变种（说了一句废话= =|||
    对于这类问题，题目一般不会做成题答让你和AI比智商？
    一般的，这类游戏会有若干种麻将，每种有若干张
    所谓的“话”可以理解为顺子（数字连续的3张或4张）和刻子（数字一样的3张）
    考虑胡牌：即为一副麻将，拿出一对对子后，剩下的全部组成若干句话
    纸牌问题的话，倒没什么特别的规矩，顺应题目吧（雾...
【问题解法】：
    我们考虑实际问题好了...

bzoj 1816: [Cqoi2010]扑克牌

【题目描述】：
    你有n种牌，第i种牌的数目为ci。另外有一种特殊的牌：joker，它的数目是m。你可以用每种牌各一张来组成一套牌，也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌。比如，当n=3时，一共有4种合法的套牌：{1,2,3}, {J,2,3}, {1,J,3}, {1,2,J}。 给出n, m和ci，你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里（可以有牌不使用）。
【题目解法】：
    看似爆搜的节奏（事实上似乎真的可以...
    我们考虑答案具有单调性，即x合法，那么x+1也合法，因此我们转化成二分+判定性问题
    对于x，判断是否合法
    我们先考虑joker，他有m张，但是当二分到x时，他只能用min(x,m)张（显然
    然后我们考虑一种贪心原则，考虑第i种牌，计算他的数量离x还差多少，如果差值的总和不超过min(x,m)，那么x就成立
    证明的话个人感觉比较抽象，我们这样考虑，每次找出剩余牌最少的那个，然后用joker补，这样最后我们补的joker数就是每种牌与x的差值，并且每套牌中只有一个joker，然后就成立了

bzoj 1028: [JSOI2007]麻将

【题目描述】:
    麻将是中国传统的娱乐工具之一。麻将牌的牌可以分为字牌（共有东、南、西、北、中、发、白七种）和序数牌（分为条子、饼子、万子三种花色，每种花色各有一到九的九种牌），每种牌各四张。在麻将中，通常情况下一组和了的牌（即完成的牌）由十四张牌组成。十四张牌中的两张组成对子（即完全相同的两张牌），剩余的十二张组成三张一组的四组，每一组须为顺子（即同花色且序数相连的序数牌，例如条子的三、四、五）或者是刻子（即完全相同的三张牌）。一组听牌的牌是指一组十三张牌，且再加上某一张牌就可以组成和牌。那一张加上的牌可以称为等待牌。　　
    在这里，我们考虑一种特殊的麻将。在这种特殊的麻将里，没有字牌，花色也只有一种。但是，序数不被限制在一到九的范围内，而是在1到n的范围内。同时，也没有每一种牌四张的限制。一组和了的牌由3m + 2张牌组成，其中两张组成对子，其余3m张组成三张一组的m组，每组须为顺子或刻子。现给出一组3m + 1张的牌，要求判断该组牌是否为听牌（即还差一张就可以和牌）。如果是的话，输出所有可能的等待牌。
【题目解法】：
    首先考虑每种牌如果出现在3个顺子里，那么显然可以变成三对刻子，所以把每种牌mod 3一下就好了
    然后枚举听的牌，在枚举对子，然后O(N)扫一遍，暴力判断是否合法即可
【其他解法】：
    其实这题据说还能用爆搜+hash+set，具体解法看下面
    不过我觉得这题的数据范围略大...用dp貌似比较蛋疼？

bzoj 1860: [Zjoi2006]Mahjong麻将

【题目描述】：

【题目解法】：
    我们考虑沿用上一题的方法，发现不可行，原因是与这道题目存在4张牌的刻子，我们无法使用正确的贪心算法
    那么我们考虑爆搜，我们发现每个位置的牌只于下个位置，下下个位置有关
    因此我们设计状态dfs(x,state,flag)表示当前到达第x位,x x+1 x+2的数量状态为state，是否存在对子（flag）
    其实本质上应该是个dp，但是它真的很暴力...
    然后我们用set存下三个量进行判重，至于那个state用最简单的hash即可：把三个位置上的数量拼起来（注意要补满三位）即可
    然后暴力枚举当前放对子，还是顺子，还是3张牌的刻子，还是4张牌的刻子
    貌似状态很多...不过跑的飞快
【标解】；
    虽然我有标解的程序，但是完全看不懂啊...
    我在下面会贴出来，求大神解释？

【总结】：
    嘛，如果你耐心的看完了，你会发现...什么鬼？就是3篇题解嘛...
    没错就是三篇题解+一些吐槽罢了，求轻D...

阅读更多……

【题目描述】：
    给定一棵树,设计数据结构支持以下操作
    1 u v d 表示将路径(u,v)加d
    2 u v 表示询问路径(u,v)上点权绝对值的和
【题目解法】：
    看似很不可做，因为有些树的符号在求和时要改变
    然而我们观察一下数据范围：对于100%的数据，n,m <= 10^5 且 0<= d,|a_i|<= 10^8
    为什么d没有绝对值符号呢？这样我们可以发现一条重要的结论：所有数最多只会从负数变成正数一次
    也就是说加入在某次+d后某个数由负数变成了正数，那么我们就暴力修改即可
    由于这样的暴力只会有n次，所以复杂度就是O(n log n)，显然是用线段树实现
    然后只要维护区间最大负数值判断即可
【未完待续？】：
    如果d可以为负数怎么破？
【调整栈空间】：
    编译时加上  -Wl,--stack,10000000

阅读更多……