aicheng4794-CSDN博客

转载 APAC Practice

2016 round AA. Googol Stringsmall && largeLL a[65];int dfs(LL pos, int id, bool f){ if(pos==1 || pos==a[id-1]+1) return f? 0:1; if(pos>a[id-1]) ...

2016-07-03 12:07:00 109

转载 [三分]HDOJ 5531 Rebuild

题意：给n个点，以这n个点为圆心画圆，使得所有的圆与其相邻的圆相切。求n个圆最小的面积和。分析：很容易想到确定了其中一个圆的半径之后，其他的圆的半径也能随之确定了。画一画三个点的和四个点的，会发现有区别。三个点的你会发现你稍微画次一点就不能满足与相邻的都相切的条件了而四个点的，很轻易就能画出来所以可以分成两类:奇数个点的和偶数个点...

2015-11-01 21:32:00 100

转载 [杂题]HDOJ5515 Game of Flying Circus

嗯。。。这是一道水题。。。鉴于还没人写这题的题解，那我就来写一发。题意：有个边长为300米的正方形嗯这样标号有两个人A和S，开始的时候A、S都在1(左下角)那个位置。两个人都要按照2、3、4、1的顺序走。有两个得分的方法： ①. 比对手先走到点(2或3或4或1) 先走到的得1分，后走到的不得分。 ...

2015-10-31 19:24:00 107

转载 [杂题]URAL2047. Maths

题意：构造一个长度为n的串，使得除了第一个以外，每个位置的前缀和的因子个数恰好等于该位置上的数。n$\le 100000$举个例子$a_i$：2 4 6 6 4 8 4 8 4 8 前缀和： 6 12 18 22 30 34 42 46 546的因子：1 2 3 6 为4个 ...

2015-10-10 11:02:00 122

转载 [DLX]HDOJ4069 Squiggly Sudoku

题意：有9*9的格子每个格子由五部分组成：上(16)、右(32)、下(64)、左(128)、和该格的数值(0~9) 若上下左右有分割格子的线就加上相应的数，该格的数值若为0，则是未知 1~9 则是已知然后根据分割线做数独(每行、每列、每宫都是1~9)输出无解、多解或者一个解就输出那个解这...

2015-09-18 22:21:00 402

转载 [2-sat]HDOJ3622 Bomb Game

题意：给n对炸弹，每对炸弹选其中一个爆炸。每个炸弹爆炸的半径相同圆不能相交，求最大半径2-sat简介二分半径，枚举n*2个炸弹若i炸弹与j炸弹的距离小于半径*2 则建边比如第一对炸弹的第一个与第二对炸弹的第一个距离小于半径*2　　则建立第一对炸弹的第一个$\Rightarrow$第二对炸弹的第二个、第二对炸弹的第一个$\Right...

2015-08-18 10:43:00 90

转载 [2-sat]HDOJ1824 Let's go home

中问题题意略和HDOJ 3062 一样这里每个队员都有选和不选两种，即上篇所说的$x$和$x’$建图：队长(a)留下或者其余两名队员(b、c)同时留下那么就是$a'\Rightarrow b$ 、 $a'\Rightarrow c$ (队长不在 b必须在，队长不在 c必须在)　　　　以及$b'\Rightarrow...

2015-08-17 22:24:00 74

转载 [2-sat]HDOJ3062 Party

中文题题意略学2-sat啦啦啦2-sat就是矛盾的 ($x、x’$不能同时取) m对人相互也有限制条件取出其中n个人也有可能是把一件东西分成取/不取相矛盾的两种情况 (那就要拆点啦~) 取其中n件做法是暴力和强连通两种重点在于建图：对于x，记取为 $x$，不取为$x’$对于y，记取为 $y$，不取为$y’$...

2015-08-17 19:39:00 84

转载 [优先队列]HDOJ5360 Hiking

题意：有n个人，每个人有两个参数$l$和$r$邀请他们去hiking, 当当前已经邀请到的人数大于等于$l$，并且小于等于$r$，那么这个人就会去问最多能邀请到几个人并输出依次要邀请的人的编号(编号1~n)先要按$l$排序($l$小的在前)，因为所有$l$小于等于当前已经邀请到的人数的人才能被邀请对上述能被邀请的人要在对$r$排序($r$小的在前)，优...

2015-08-06 20:50:00 59

转载 [主席树强制在线]ZOJ3888 Twelves Monkeys

题意：有n年，其中m年可以乘时光机回到过去，q个询问下面m行，x,y 表示可以在y年穿越回x年, 保证y>x下面q个询问，每个询问有个年份k问的是k年前面有多少年可以通过一种以上($\ge 2$)方法穿越回去的，其中时光机只能用一次比如案例9 3 39 16 14 1672如图对于询问6这一年：1.穿越回第1...

2015-07-26 22:38:00 130

转载 [主席树]HDOJ3874 Necklace

题意：n个数 m个询问询问的是[l, r]区间内不同的数的和没有修改，静态的主席树即可与 SPOJ QUERY一样将重复的元素建树即可注意范围：$N \le 50000$ 每个值不超过1000000也就是加起来会爆int 要用LL 1 #include <bits/stdc++.h> 2 using namespace...

2015-07-25 10:18:00 69

转载 [主席树]SPOJ DQUERY

题目链接题意：n个数 m个查询查询的是[l, r]区间内不相同的数的个数没有修改，因此静态的主席树就好了将重复的元素建树即可query的时候加起来，用区间长度(r-l+1)去减就是答案(query的是[l, r]之间重复元素的个数) 1 typedef long long LL; 2 #define lson l, m 3 #...

2015-07-25 10:14:00 74

转载 [优先队列]HDOJ5289 Assignment

题意：有多少个区间，区间内最大的数减去最小的数差小于k对每个数它所在的区间，可以只往前找(类似dp的无后效性) 比如对位置3的数，可以往前找的区间是[3, 3], [2, 3], [1, 3], [0, 3]这样这样遍历a[i] 对每个a[i]往前就可以得到所有的区间比如案例10 50 3 4 5 2 1 6 7 8 9(最小值，最大值)的形式...

2015-07-22 10:35:00 47

转载 [YY题]HDOJ5288 OO’s Sequence

题意：求这个式子 $\sum \limits_{i=1}^{n} \sum \limits_{j=1}^{m} f(i, j) mod (10^9 + 7)$ 的值就是对每个区间[i, j]枚举区间中的每个数$a_i$到$a_j$, 判断这个$a$是否对[i, j]这个区间内所有数取模都不等于0，若是，则这个区间满足条件问有多少个满足条件的区间比如案例是这样跑的 ...

2015-07-21 23:22:00 58

转载 [主席树]HDOJ4348 To the moon

题意：n个数， m个操作1.C l r d 给[l, r]区间的每个数加上d2.Q l r: 查询[l, r]区间的和3.H l r t: 查询第t个操作时[l, r]区间的和4.B t: 回到第t个操作之后因为有查询历史的区间和，故用主席树(保留了历史)区间更新直接更新到每个子节点即可出题人的题解神么链接都打不开...

2015-07-21 10:51:00 84

转载 [主席树]HDOJ4417 Super Mario

题意：n个数 m个询问 ($n、m \le 10^5$)每个询问有l, r, k 问的是[l, r]区间内有多少个数小于等于k用主席树做的话查询第i小的数与k比较即可 1 #define lson l, m 2 #define rson m+1, r 3 const int N=1e5+5; 4 int L[N<<5],...

2015-07-20 21:11:00 83

转载 [主席树]ZOJ2112 && BZOJ1901 Dynamic Rankings

题意：n个数，q个询问 (n<=50000, q<=10000)Q x y z 代表询问[x, y]区间里的第z小的数C x y 代表将(从左往右数)第x个数变成y上篇介绍了在[x, y]区间内查询第z小的数的方法(静态主席树)本题有更新操作若仍用上篇的做法，每次更新一个数，需要更新的是T[i], T[i+1]... ...T[n](...

2015-07-19 21:18:00 81

转载 [主席树]HDOJ2665 && POJ2104 && POJ2761

主席树真是神奇的物种！Orz一篇资料题意：给n、m　　下面有n个数 (编号1到n)　　　有m个询问，询问的是上面的数的编号在[l,r]之间第k小的数n、m的范围都是$10^5$是主席树的入门题借此来学习一下主席树主席数利用函数式线段树来维护数列，一般用来解决区间第k大问题空间时间的复杂度小于树套树(常数小)划分树也可以解...

2015-07-16 20:36:00 133

转载 [扫描线]POJ2932 Coneology

题意：有n个圆依次给了半径和圆心坐标保证输入的圆不相交(只有相离和内含/外含的情况)　　问有几个圆不内含在其他圆中，并分别列出这几个圆的编号(1~n)　　　　(n的范围是[1, 40000])案例画出来大概是这样的(那个原点为(50,50)的太远了，就意思一下)所以答案是3号圆和5号圆不被包含好了，若这道题n只有1000，那...

2015-07-13 15:40:00 104

转载 java版AC自动机

1 class Trie 2 { 3 int [][]Next=new int[500005][128]; 4 int []fail=new int[500005]; 5 int []end=new int[500005]; 6 int root, L; 7 int newnode() 8 { 9 ...

2015-07-09 09:04:00 219

转载 [java线段树]2015上海邀请赛 D Doom

题意：n个数 m个询问每个询问[l, r]的和，再把[l, r]之间所有的数变为平方(模为9223372034707292160LL)很明显的线段树看到这个模(LLONG_MAX为9223372036854775807) 很明显平方时会爆LL很容易发现所有数平方模了几次之后值就不再改变了而且这个“几次”相当小因此直接暴力搞就好了 ...

2015-05-26 01:43:00 92

转载 [java]2015上海邀请赛 B Base64

题意：给n和一个字符串(可以有空格) 求字符串编码n次后的字符串　　　编码方式：字符串的每个字符转化成ASCII码， ASCII码转化成8位2进制，　　将二进制数分割成6位为一组的(不够的补0)，再变成十进制数依次按照以下方式变成字母　　　转化成字母后，若长度不是4的整数倍，在字符串后面补=举个例子， The的ASCII码分别为84，104，...

2015-05-25 19:50:00 74

转载 [矩阵快速幂]HDOJ4565 So Easy!

题意：给a, b, n, m求 $\left \lceil ( a+ \sqrt b )^n \right \rceil$ % m看到 $( a+ \sqrt b )^n$ 虽然很好联想到共轭但是推出矩阵还是比较难的 $(a+\sqrt b)^n + (a-\sqrt b)^n$= $(C^0_n a^n +C^1_n a^{n-1} \sqrt...

2015-05-17 10:18:00 81

转载 [杂题]FZU2190 非提的救赎

中文题，题意不多说。本来感觉很像dp其实只要从上到下维护单调性就好了坑是......这个oj......用cin很容易TLE...... 1 //#include <bits/stdc++.h> 2 #include <cstdio> 3 #include <cstdlib> 4 #include ...

2015-05-05 22:13:00 61

转载 [模拟]ZOJ3480 Duck Typing

题意：给了一坨...按题目意思输出就好了...给一组案例100beginclass dclass c:dclass b:cclass a:bdef d.mdef d.ncall a.mend答案应该是class dclass c:dclass b:cclass a:bdef d.mdef d.ninvoke d....

2015-04-04 11:47:00 104

转载 [模拟]ZOJ3485 Identification Number

题意：给了一串15位或18位的身份证号码，求在改变最少位数的情况下，输出正确合法的身份证号合法的身份证是按照以下规则：前6位以及“Order code”三位一定合法其中X是根据前17位的值计算出来的按照如下公式 (a1就是最后一位，若为10就是X)另外题目还规定了“Date of Birth” 要在1900.1.1到2011.4.2之间...

2015-04-04 10:59:00 73

转载 [数论]ZOJ3593 One Person Game

题意：一个人要从A走到B 只能走a布、b步、(a+b)步，可以往左或右走　　问最少要走几步，不能走到的输出-1可以列出方程 $ax+by=A-B$或者　　　　 $ax+(a+b)y=A-B$或者　　　　 $bx+(a+b)y=A-B$要取这三个方程的最小的$(x+y)$根据$ax+by=gcd(a, b) $当$A-B$不是$gcd$的倍...

2015-03-31 21:47:00 70

转载 [博弈]ZOJ3591 Nim

题意：给了一串数，个数不超过$10^5$，这串数是通过题目给的一段代码来生成的int g = S; for (int i=0; i<N; i++) { a[i] = g; if( a[i] == 0 ) { a[i] = g = ...

2015-03-31 21:30:00 64

转载 [杂题]URAL1822. Hugo II's War

看懂题意的请直接跳过下一坨！本人有表达障碍！==========================================题意： (题意真的很难很难懂啊！！！去他娘的**)有一个王国，王国里有一个国王(编号为1)，他有(编号为2~n) n-1个臣子(这些臣子并不全和他有直接关系)然后呢国王要去打架，但是只有当他的x%个及以上的直系下属(与他有直接关系的臣子)...

2015-03-16 00:29:00 44

转载 [状压dp]POJ1185 炮兵阵地

中文题题意不再赘述对于中间这个“P” 根据dp的无后效性我们只需考虑前面的就变成了只需考虑：也就是状压前两行具体与HDOJ的4539类似：看HDOJ 4539仅仅是共存状态的判断不同 1 //#include <bits/stdc++.h> 2 #include <cstdio> 3 #in...

2015-03-15 10:34:00 71

转载 [状压dp]HDOJ4539 郑厂长系列故事——排兵布阵

中文题，题意不再赘述对于“？”这一格，它所能攻击到的(曼哈顿距离为2的) 前方的即“√”的四个位置那么与此格有关的即它前方两行(即状压这两行)首先预处理每行能满足的：i 和（i<<2）不能同时放然后分别枚举前一行和再前一行的所有状态(每一行的状态至多只有$2^{10}$=1024个) 判断能否共存注意mp==1处才能放...

2015-03-15 09:56:00 60

转载 [二分匹配]URAL1721Two Sides of the Same Coin

题意：给n个人，每个人都有3个参数，分别是名字，能做的事(a:statements b:testdate a、b都可以:anything)，Rank要求：一个人只能做一个事件，要两个人Rank相差2才能共同做a、b，问最多能做多少个a、b，并输出做a人的名字做b人的名字很明显是二分匹配稳定婚姻问题。一开始按照能做a的人->能做b的人建图怎么都过...

2015-03-08 17:27:00 217

转载 string

遍历string：for(string::iterator it=str.begin(); it!=str.end(); it++ cout<<*it;或者for(inti=0; i<str.length(); i++) cout<<str.at(i);substr：s=s.subst...

2015-02-12 14:29:00 35

转载 [string]Codeforces158C Cd and pwd commands

题目链接题意很清楚和linux的语句是一样的pwd输出路径 cd进入 ..回上一层目录此题完全是string的应用String的用法 1 vector<string> s; 2 int main() 3 { 4 int n; 5 scanf("%d", &n); 6 while(n...

2015-02-11 11:02:00 72

转载康拓展开

http://baike.baidu.com/item/%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80?force=1就是百度百科的康拓展开解决魔板问题的代码打了一遍调试了一下长了一下姿势感觉就是和状压一样展开就是为了标记？一共只有8格即8!=40320个状态用ans记录下每个状态从12345678开始最快能变到的步骤...

2015-02-09 10:18:00 60

转载 [水题]Codeforces337A Puzzles

题目链接题意：要在m个数里面选n个数，要求这n个数的差值要最小题意在hint里很清晰了这道题从题意到题目本身都没有什么trick写这道题完全是为了用一下#include <numeric>里面的两个小朋友：adjacent_difference 求相邻数的差 &&accumulate 求和p.s.边界要注意，都是左闭右开...

2015-02-04 20:50:00 66

转载 [水题]ZOJ3038 Triangle War II

题意：给了这样一张图有两种状态：pushed(*)和unpushed(.) 为方便起见分别成为开和关改变一个点的开关状态会同时改变与它相邻的点的开关状态比如改变5，则2、3、4、6、8、9都会改变N（行数）最多为6 即最多21个点求：任意改变开关状态后最多能有几个关着。为什么这么像高斯消元！！！每个点的状...

2015-02-04 19:58:00 71

转载 [模拟]Codeforces509C Sums of Digits

题目链接题意：给n个数a[i], 要求b[i]每位数的和等于a[i], 并且b[i]要严格递增求最小的b[i]b[0]最小一定是X9999...这样的形式后面的b[i]位数一定大于等于前一个用ans[i][0]记录b[i]的位数也就是每次从ans[i-0][0]位开始若不满足b[i]>b[i-1] 则位数加1位数加1之后必定满足b[i]>...

2015-02-02 09:56:00 63

转载 DLX模板

对于数独问题 1 const int N=16; //3*3数独 2 const int MaxN=N*N*N+10; // 一格能填9个数 9*9格 3 const int MaxM=N*N*4+10; // 9*9*4=(9+9+9)*9+9*9 (9+9+9)是9行 9列 9格 *9是9个数 9*9是81个格子 ...

2015-01-30 10:20:00 81

转载树链剖分模板

边权线段树 1 const int MAXN=10005; 2 struct Edge 3 { 4 int to, next; 5 }edge[MAXN<<1]; 6 int head[MAXN], tot; 7 int top[MAXN]; 8 int fa[MAXN]; 9 int ...

2015-01-27 20:34:00 101

空空如也

空空如也