ZMOIYNLP-CSDN博客

原创【BP神经网络】代码存放

#include<bits/stdc++.h>using namespace std;const int A=784,B=28,C=10;const double L=0.2;class BP{ private: const int IN,HN,ON; double lambda; bool isFirstTime; s

2017-01-26 10:38:24 1507

原创【SDOI2015】R2酱油记

Dayx(x≤0):Day\,x(x \le 0): 成天做题吃s中…… Day0:Day\,0: 疯狂挤公交去高铁站……晚上颓废。 Day1:Day\,1: 早上起来吃早饭，吃辣两个包子、一碗半豆腐脑、一种长得很像莴苣的菜…… 本蒟蒻吃饭太慢，等我吃完其他神犇已经走了…… 结果跟一轮一样，又是最后几个抽签……抽了153号…… 看题。令人感动……居然是pdf…… 第一题：qua

2015-05-16 22:26:39 2733

原创【bzoj2527】Meteors【整体二分】

有n个国家和m个空间站，每个空间站都属于一个国家，一个国家可以有多个空间站，所有空间站按照顺序形成一个环，也就是说，m号空间站和1号空间站相邻。现在，将会有k场流星雨降临，每一场流星雨都会给区间[li,ri]内的每个空间站带来ai单位的陨石，每个国家都有一个收集陨石的目标pi，即第i个国家需要收集pi单位的陨石。询问：每个国家最早完成陨石收集目标是在第几场流星雨过后。数据范围：1<=n,

2015-05-12 11:08:35 2442

原创【spoj1812】Longest Common Substring II 【SAM】

呵呵……#include<bits/stdc++.h>using namespace std;const int maxn=100002;struct node{ node *f,*ch[26]; int len,ml,nl;}pool[maxn*2],*cur=pool,*tail=pool,*init=pool,*b[maxn<<1];void add(int c,in

2015-05-02 22:26:08 1653

原创【spoj1811】Longest Common Substring【SAM】

SAM又神又恶心- -#include<bits/stdc++.h>using namespace std;const int maxn=250010;struct node{ node *f,*ch[26]; int ml;}pool[maxn*2],*init=pool,*cur=pool,*tail=init;void add(int c,int len){

2015-05-02 22:24:53 1779

原创关于后缀自动机的一点题目

更新中…… 后缀自动机~你为什么这么恶心~又这么神~ spoj1811LCS：拿A串建SAM然后拿B串跑一遍，能往下走就走，否则转移到他的父亲。代码戳这里。 spoj1812LCS：拿第一个串A建个SAM，然后对于每个节点额外维护两个信息nl、ml：nl表示当前串走到这个点时的匹配长度，ml表示目前为止所有串走到这个点时最小的匹配长度。因为对于一个节点他的father的Right集合一定包含这

2015-05-02 22:20:30 2324

原创【bzoj4028】【HEOI2015】公约数数列【分块暴力】

传送门http://www.lydsy.com/JudgeOnline/problem.php?id=4028 这题十分神奇…… 一开始我考虑线段树，后来又考虑分块。。但是我死在了这么一个问题上：知道每一块的GCD和XOR，那怎么查询？相当于gcd(之前的GCD,这一块某处的前缀GCD)*(之前的XOR^这一块某处的XOR)=x。。。然后我就爆炸了- - 据zzh和tdl等大神

2015-04-30 08:02:10 3012 7

原创【bzoj4027】【HEOI2015】兔子与樱花【贪心】

昨天这三道题貌似比前天好做很多啊- - 但是为什么我第二题还是T呢T T 好吧说第一题。第一题有个地方就是如果当前这个节点能被他的父亲吃掉而没被吃掉，那么他就再也不能被吃了。而如果他的父亲因为吃了他而不能被父亲的父亲吃，那也不亏。那么贪心好了。蒟蒻用了dfs。。。win下可能会爆栈。。。把它的孩子按儿子数+樱花数排序，然后能吃就吃。。#include<cstdio>#inclu

2015-04-30 07:22:23 2029

原创【bzoj4011】【hnoi2015】落忆枫音【精妙的动态规划】

我最近越来越感觉到我弱爆了。今天下午全机房做hnoiD2，但是我只会敲暴力……第二题看着像点分治，可是我不会写~ 看来多做题确实是真理~ 这道题精妙极了！引用一段PoPoQQQ大神的话：由朱刘算法的推论可知，如果除根节点外每个点都选择一条入边，由于没有环，因此一定会形成一个树形图；因此答案就是∏ni=2=2×degreei\prod_{i=2}^n=2\times\text{d

2015-04-26 20:50:22 2381

原创【屯题】【点分治】

MMD今天下午真是不爽，三道题全都不会。人傻就该多做题~~ 先来点点分治的题目。现在做了几题了：0 hnoiR1D2T2： zjoiR1T1：

2015-04-26 18:48:54 2161

原创【bzoj2693】jzptab【反演】

反演是不是就是拿莫比乌斯函数乱搞……如果我说错了请回复- - 倒数第三行d’变成了倒数第四行的dd’……真是精妙。然后观察到d∑d′|dd′μ(d′)d\sum_{d'|d}d'\mu(d')是积性函数，线性筛出来即可。为么我碰到的积性函数都是这么筛的： i是质数，直接算； i%prime[j]==0，f[i*prime[j]]=f[i]*prime[j]; i%prime[j]!=

2015-04-26 10:43:33 1722

原创【bzoj1978】【BeiJing2010】取数游戏 game【递推】

小 C 刚学了辗转相除法，正不亦乐乎，这小 P 又出来捣乱，给小 C 留了个难题。给 NN 个数，用 a1,a2,...,ana_1,a_2,...,a_n来表示。现在小 P 让小 C 依次取数，第一个数可以随意取。假使目前取得 aja_j，下一个数取ak(k>j)a_k(k>j)，则aka_k必须满足gcd(aj,ak)≥Lgcd(aj,ak)\ge L。到底要取多少个数呢？自然是越多越好

2015-04-25 20:40:26 1910

原创【bzoj3994】【SDOI2015】约数个数和【数论】【反演】

虽然题目上写了反演但是我不知道什么是反演……如果你把Sigma调换位置叫做反演的话。这道题题面非常简单：设d(x)d(x)为xx的约数个数，给定N、MN、M，求∑i=1N∑j=1Md(ij)\sum_{i=1}^N\sum_{j=1}^Md(ij) 当时我too naive，看到这玩意就默默地打50分暴力去了。。。今天江苏神犇们做了这道题，我顺便听明白了~~ 首先它不知用什么精妙

2015-04-21 20:59:14 5681 5

原创【bzoj2005】能量采集【GCD】

为么很多这种题把∑\sum顺序换一下就得到答案了。。。一个植物（坐标(x,y))到原点的路线上经过的植物数是gcd(x,y)（包括那个植物本身） ∑((gcd−1)∗2+1)=∑(gcd∗2−1)\sum\left((gcd-1)*2+1\right)=\sum(gcd*2-1) 因此把gcd∗2−1gcd*2-1的和求出来即可。下面说一说如何快速求∑ai=1∑bj=1gcd(i,j)\

2015-04-21 20:44:49 1702

原创【bzoj1101】Zap【神奇的∑】

传送门： http://server.mclscloud.com:5230/JudgeOnline/problem.php?id=1101 求∑ai=1∑bj=1[gcd(i,j)==d]\sum_{i=1}^a\sum_{j=1}^b[gcd(i,j)==d]. 设a≤ba \le b. 令a′=⌊ad⌋,b′=⌊bd⌋a'=\lfloor \frac ad \rfloor,b'=\lfl

2015-04-21 20:16:32 1991

原创一点数论题目

今年省选真是悲催第二天第二题没有人A，导致一堆二百五（我是说分数二百五，没有其他的意思~~）。。 bzoj1101：求∑ai=1∑bj=1[gcd(i,j)==d]\sum_{i=1}^a\sum_{j=1}^b[gcd(i,j)==d]。 bzoj2005：等价于求∑ai=1∑bj=1(2gcd(i,j)−1)\sum_{i=1}^a\sum_{j=1}^b \left( 2gcd(i,j)-

2015-04-21 19:53:48 1643

原创【UVa12298】 Super Joker II 【FFT】【生成函数】

居然因为精度问题WA掉了。。。这题要用long double，并且交c++11…… 每种花色的牌开一个系数向量，有这种牌那么系数就是1，否则为0.然后FFT乘起来就行了。#include<cstdio>#include<cstring>#include<iostream>#include<cmath>using namespace std;typedef long double re

2015-04-14 19:51:59 2124

原创 SDOI2015 R1 酱油记

貌似R1就这样结束了- -看来蒟蒻还得加油啊。这是本蒟蒻第一次省选，所以什么都不懂 - - 赶了十一点的火车周五下午两点半到的济南，然后又坐公交车晃悠到了山师（车上差点把我热死- -），我发现那个管报道的灰衣服老师是noip时监考我们那个考场的人耶~ 然后遇见了孟凡盛学长，他专门从新校区赶过来的。于是我们去了山师附中熟悉一下环境。可惜不开门。于是我们只好回宾馆。本来准备打车，

2015-04-14 16:47:49 2041

原创为什么线性筛欧拉函数i%prime[j]==0的时候phi[iprime[j]]=phi[i]prime[j]

看贾志鹏线性筛的时候想起来的。我有一个繁琐的证明- -。证明ϕ(pm)=p×ϕ(m),p为素数，m∈Z\phi(pm)=p\times\phi(m),p为素数，m\in \Bbb Z. 设m=pα⋅m′,α,m′∈N,(pα,m′)=1.m=p^{\alpha}\cdot m',\;\alpha,m'\in\Bbb N,(p^{\alpha},m')=1. 那么ϕ(m)=ϕ(m′)⋅ϕ(

2015-03-23 17:34:40 1940

原创为什么phi(p^n)=p^n-p^(n-1)

多亏yan Big God点拨我这愚笨的头脑…… 和1到pnp^n中与pnp^n不互质的数就是能被p整除的数，而这样的数共有pnp=pn−1\frac {p^n}{p}=p^{n-1}个，所以和pnp^n互质的数就有pn−pn−1p^n-p^{n-1}个。

2015-03-22 21:45:53 1974

原创【bzoj1004】Cards【Polya计数定理】【递推】

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1004 这是一道Polya好题～根据那个什么引理，本质不同的方案数等于每个置换下不同的方案数的平均值。但是Polya定理是： l=1|G|∑f∈Gkm(f)l=\frac 1{|G|} \sum_{f \in G}{k^{m(f)}} 而这里是有三种颜色，求每个置换里每个循环涂同样

2015-03-22 20:48:02 927

原创【UVa1391】宇航员分组Astronauts【2-SAT】【强连通分量】

大意：有n个宇航员，按照年龄划分，年龄低于平均年龄的是年轻宇航员，而年龄大于等于平均年龄的是老练的宇航员。现在要分配他们去A，B，C三个空间站，其中A站只有老练的宇航员才能去，而B站是只有年轻的才能去，C站都可以去。有m对宇航员相互讨厌，不能让他们在同一个空间站工作。输出每个宇航员应分配到哪个空间站，如果没有则输出No solution.这道题只要构出图来就很好办啦～～由于每个宇航员

2015-03-19 15:37:30 728

原创【UVa12167】 Proving Equivalences 【强连通分量】

给你一个有向图，问你至少添加几条有向边，使得新图强连通。求出强连通分量缩点易于下一步处理。这样我们得到了一个DAG。这个DAG里有许多出度为零（a个）或者入度为零（b个）的点。要想让它们都强连通，显然可以将它们两两配对头尾相接形成一个环，多余的随便和哪个已经配对的连都行。那么答案为max(a,b). 要是原图已经强连通，答案是0不是1。#include<stack>#incl

2015-03-18 11:35:33 584

原创【UVa11324】最大团The Largest Clique【强联通分量】【DAG】

鉴于Uva比较难上…… 有一张有向图G，求一个结点数最大的结点集，使得该结点集中任意两个节点u和v满足要么u能到v，要么v能到u（可以互相到达）。首先求强联通分量，因为同一个强联通分量里的点要么都选要么都不选…… 然后缩点得到一个有向无环图（DAG）。。令收缩后的点具有一个点权，代表这个SCC（强联通分量）原来的结点数。。然后动态规划求最长路即可。这题真是cs。。。我拓扑排序排炸

2015-03-18 11:24:03 666

原创【bzoj2243】【sdoi2011】染色【树链剖分】

这题就一裸的树链剖分。。。开个结构体data记录颜色段数，左右端点颜色，合并及下传标记和项链工厂一样。。注意从下往上提的时候把左右端点颜色反过来（详见代码）但是我还是犯了我曾经犯过的错误。。。预处理建线段树的时候我居然在build过程里用了idx！明明idx是树上节点到线段树节点的映射，不能这么用。。于是我只好又写for(int i=1;i<=n;++i) A[idx[i]]

2015-03-15 14:17:02 523

原创【bzoj1432】Function【结论题】

结论题的特点是：代码往往都很短…… 我先说一下答案：n=1的时候输出1，其余时候输出2*k，假如k>(n>>1)的话，令k=n-k+1（因为1和n-1是对称的）。为什么呢…… 我们画一个图。这是5条直线（函数）。可以看到，这些点以 A BC DEF GHIJ 的方式排列。第一个部分只经过A（这样一定是最优的）第二个部分只经过BAC 第三个部分只经过DBECF……

2015-03-12 20:01:37 904

原创【bzoj3000】Big Number【数论】【Stirling公式】

题意：问你⌊logkn!⌋+1是多少(2≤n≤231,k≤200)。我一开始想：哦？我们可以用根号n的时间把n的素因子都找出来，然后根据阶乘的素因子分解式分别计算对数然后加起来…… 呵呵，WA了。问题是，n的素因子确实可以在O(\sqrt n)的时间内分解出来，但是n!

2015-03-12 11:52:30 725

原创【bzoj1036】树的统计Count【树链剖分】【ZKW大法好】【卡常大法好】

关于这个树上路径端点会重合的问题，我们只要不判断x==y就行了。详见被注释呵呵的地方。#include<cstdio>#include<cstring>#include<iostream>using namespace std;const int maxn=30001;typedef int arr[maxn];typedef int arr1[maxn<<1];arr fa,top,

2015-03-12 11:43:27 825

原创【codvs3304 3305 3306】水果姐逛水果街系列【线段树】【树链剖分】

这三道题一个类型的…… 第一道题是有一排商店，可以买水果也可以卖水果，买水果和卖水果的价钱一样。问你从商店x走到商店y，买卖所得最大收益是多少。我们可以发现朴素的办法是一路扫过去，记录当前最小值，然后更新收益。这样应该会T（我没试过）这样丢失了很多信息。我们考虑一下能不能存起来。发现解满足区间加法。即【L，R】中最大的收益要么是【L，K】中的收益，要么是【K，R】中的收

2015-03-11 23:01:45 689

原创【spoj375】Query on a tree【树链剖分】【或者动态树，那样常数就完了T_T】

hahahaha!今天（3月12）我终于ac了……orz Yan Big God！他问我能不能$O(n)$ 建树……并且提供了一个“反映射“的思想。我想我们连反映射都可以不要……鉴于ZKW的特殊性……我们只要

2015-03-11 20:02:49 745

原创【bzoj1858】【Scoi2010】序列操作【位运算】【卡常大法好】

其实这道题用线段树神马的应该是可做的…… 但是鉴于我跪烂的位运算水平…… 我决定用位运算压常数水过去～～（其实要是数据强的话我早就完了）我一次又一次犯的,b错误耗费了我一下午的时间…… 这就是蒟蒻啊- - 一开始不知怎么回事，命令总是读不进去- - 然后发现~0U<<(r+1)有的时候不总是好用。 printf("%u\n",~0U<<32); int r=32;

2015-03-10 21:08:26 688

原创【bzoj2284】【SDOI2011】贪吃蛇【搜索】【位运算】【卡常大法好】

这道题真是太精妙了…… 传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2284 首先这题棋盘的范围是15不是12。本来原题是有special Judge的，因为要输出方案…… 但是这是oj嘛。。就输出最短时间好了- - 我一开始愚蠢的想法是xy各用一个char存，蛇长最多为8，就开个结构体数组，再开一个长度为4的记录事物的位置……

2015-03-09 16:29:56 1818

原创【poj2942】圆桌骑士Knights of the Round Table【双连通分量】【二分图】【奇圈】

传送门：http://poj.org/problem?id=2942尽管我承认这题我几乎是对着书抄的代码（因为我还不熟- -），但是我还是WA了三次- -数组又没清零。基本思想就是：首先把不互相憎恨的骑士连边。求双连通分量bcc。判断每个bcc是不是二分图，是的话这个二分图里的骑士都没法参加会议。因为形不成奇圈。奇圈就是奇数个点连成的圈啦~二分图是不可能有奇圈的（有的话

2015-03-03 16:54:24 1274

原创【bzoj1269】【AHOI2006】文本编辑器editor【Splay】

被文艺平衡树折磨了一天以后发现这道题就很好做啦~~~但是c++喜闻乐见的gets十分不好使。如果insert的字符串有空格，gets会跳过去不读空格。好在题目给了ASCII码的范围。这样就可做了。写的时候不要把功能一次性全写完，先写个基本的，排除一下低级错误……我把Move和insert写完以后发现Splay又出了几个沙茶错误- -还有居然把Next和Prev搞反了- -…

2015-03-02 14:13:21 677

原创【bzoj3223】文艺平衡树【Splay】【呵呵】

传送门：bzoj3223:文艺平衡树裸的区间翻转啦……本蒟蒻一开始就犯了一个致命的错误：按照splay节点里存的数来查找节点。YanBigGod说：应该查第k大。Orz。于是乎我查了第k大。交上去T了。原来是查第k大的时候卡死了。还好我写的非递归- -不然就爆栈了……但是我发现我又犯了错误：我原来写的是：inline int select(int

2015-03-01 14:53:55 666

原创【codevs2343】简单题【位运算】【卡常大法好】

这道题的题意十分浅显易懂。有一串很长很长不知道有多长（最长十万）的01序列，一开始全是0.要你维护两种操作：将一个区间内的数翻转（就是1变0,0变1，就是异或1）、询问某一位是0还是1.树状数组的裸题啊。但是我使用了传说中的卡常数大法~~~直接暴力修改，但是把64个01位压进了一个unsigned long long。这样修改是O(n)的，但是常数奇小- -不过位运算坑

2015-02-28 10:38:17 754

原创【poj1459】Power Network【模板题】【最大流】

传送门：http://poj.org/problem?id=1459别的没啥好说的，就是另设一个超级源S和超级汇T，把所有Power Station连到S上，把所有Consumer连到T上，然后Dinic一下就行了~（我数组又开小了T_T）#include#include#include#includeusing namespace std;struct Dinic{#de

2015-02-18 14:38:57 771

原创【bzoj3196】二逼平衡树【树套树】【线段树】【平衡树】【呵呵】

……我承认我写change函数时确实213了- -a[pos]应当在最后被修改，可我却忘了……第一次交上去的时候爆了数组，WA了……然后把数组开大，交上去，MLE了……现在我证明长度为n的序列，他的平衡树节点数组只要开到(log(2,f(n))+1)*f(n)就绝对不会爆。f(n)是指比n大的最小的2的幂，比如f(65535)=65536,f(65537)=2^17.证

2015-02-17 16:31:11 795

原创【bzoj3098】Hash Killer II【丧心病狂的大水题】

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3098hint说的有道理。如果你从n个数里随机选数，那么大约选根号n次就能选到一样的（当然选了n次还没碰上是因为RP太好了- -）。这是著名的“生日攻击”问题，详情请看这里。代码很短：PS：貌似加了srand(time(NULL))会RE...... #includ

2015-02-16 11:23:49 1239

原创 poj2777:Count Color

就是给你一个1..L的线段，不停地染色，并询问区间上由多少种颜色组成。由于颜色数很小（不大于30），便可以用一个32位整数来表示颜色的集合。自底向上更新是做集合的并（就是按位或）。同样只有在纯色时才需要下传标记。敬请指教，神犇轻喷0v0

2015-02-15 21:15:19 490

空空如也

空空如也