- 博客(154)
- 收藏
- 关注
RSS订阅
原创 [Merc Storia] 愈术士与铃之旋律
前面已经交代了闪光之石是魔宠的心回来雾降之地的遗迹后遇见了希罗他们，和魔宠战斗中进入了传送门见到了一个很大的电气国的机械，斯特拉说很像埃利亚斯一直背着的东西，而这个东西刚好能装下一个人的样子。进入另一个传送门后看见希罗表情痛苦的拿着一个闪光之石，埃利亚斯说:果然这个时代的人是不行的.，然后抢走了闪光之石，不过一部分碎片融入了梅露可体内。然后是埃利亚斯的回忆杀，提到了他和他姐姐（...
2018-04-04 09:39:56
572
1
原创 [DP+KMP+矩阵快速幂优化] BZOJ 1009
题意给定长度为m的数字串s，求不包含子串s的长度为n的数字串的数量思路状态转移方程dp[i][j]=Σ dp[i−1][k]∗a[k][j] (0<k<m)dp[i][j]=Σ dp[i−1][k]∗a[k][j] (0<k<m) dp[ i][ j] = \Sigm...
2018-09-06 21:31:46
271
原创 [基环树dp] BZOJ1040
题意给一个基环森林，每个点有一个权值 求一个点的集合,使集合里面不存在相连的两个点思路基环树: 树加一条边使之成环 如果是树就正常树形dp f[i][0]=Σ{max(f[son(i)][0],f[son(i)][1])}Σ{max(f[son(i)][0],f[son(i)][1])} \Sigma \{ max(f[son(i)][0],f[son(i)][1])...
2018-09-04 22:15:18
336
原创 [树形dp+0/1背包] POJ1947 Rebuilding Roads
题意一棵树,最少去掉几条边,能让分割下来的一部分恰好等于p思路At first glance, no thought, thought for a long time, finally understand, a subject may have a variety of ways of thinking, to find their own way of thinking,Dp[...
2018-09-03 23:08:06
178
原创 [树形dp] POJ2486
题意一颗树，n个点（1-n），n-1条边，每个点上有一个权值，求从1出发，走V步，最多能遍历到的权值思路0代表s出发回到s, 1代表s出发不回来 初始化每个rt的每个步长都是当前节点的权值 dp[root][j][0] = MAX (dp[root][j][0] , dp[root][j-k][0] + dp[son][k-2][0]);//从s出发，要回到s，需要多走两步s-t,...
2018-09-03 22:57:23
758
5
原创 [中国剩余定理+枚举] UVA11754
题意求一个数N，给出C和S，表示有C个条件，每个条件有X 和 k，然后是该个条件的k个yi，即NmodX=yj,输出满足的最小的S个N，要求正整数。思路计算total为一共能有多少种解, total小则用CRT求出所有组合的解 total数大的时候，可以通过枚举N来判断，找到一组k/x最小的最为枚举基准，然后判断即可代码//uva11754//求一组模方程的解// ...
2018-08-24 12:50:15
371
原创 [Catalan数] HDU 2067
题意在棋盘上行走,不能越过对角线思路递推式 h(0)=1,h(1)=1 h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)h(0) (n>=2) h(n)=h(n-1)*(4*n-2)/(n+1); h(n)=C(2n,n)/(n+1); 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ...
2018-08-22 10:34:28
183
原创 [错排] HDU 2049
题意N中有多少中M个数的错排思路错排公式 f[0]=1, f[1] = 0, f[2]=1 f[n]=(n-1)*(f[n-1]+f[n-2])代码// hdu 2049#include <algorithm>#include <bits/stdc++.h>#include <cstdio>#include <cstr...
2018-08-22 10:29:11
216
原创 [置换] POJ 3590
题意对每一个置换T，都存在一个 Tk=eTk=e T^k = e . 现在让你求一个n元置换，使得它的阶最大，即当Tk=eTk=e T^k = e 时，k最大。若同时存在多个这样的T，那么输出其中排序最小的。思路https://blog.csdn.net/tsaid/article/details/7389140 要想让整个置换的k最大,就是要保证置换里的每个循环节的长度之间的lc...
2018-08-17 12:48:39
368
原创 [置换群] POJ 3128
题意一个置换能否为某个置换平方的结果。思路置换幂 : https://wenku.baidu.com/view/0bff6b1c6bd97f192279e9fb.html 幂后循环节的长度与原置换长度和幂次之间的gcd有关 当前幂次 = 2 对整个置换的每个循环节长度n n为奇数, 平方后不变且仍为奇数 n为偶数, 平方后全部分裂成均等的两份,长度可能是奇数,可能是偶数 所...
2018-08-17 12:17:31
184
原创 [树的直径/贪心] HDU 4607
题意一棵树,边长1,求走过k个点花费的最小时间思路找到树最长的那段路,即树的直径 如果访问的点的个数小于直径上点的个数,则可以直接到,时间就等于点的个数 如果超过直径上点的个数,则需要中途离开直径访问别的店并返回直径,则访问其他店要花费两倍的时间来往返求直径的方法: 任取一点找到距离他最远的点,作为直径的起点 从起点找到离他最远的点,则是终点,,, 证明…..略………qw...
2018-08-16 11:28:58
194
原创 [置换群] POJ 1721 CARDS
题意第i个位置的牌是a[i],一次交换后第i个位置的牌变成a[a[i]]。 序列所有位置经过一次交换为一次交换 已知交换m次之后的序列，求原先序列思路置换群的幂,不会 经过一定次数的置换之后会回到原来的位置, 是循环的 求出循环的长度cnt,最初的序列就是当前序列再向前循环 cnt - k 次代码// https://blog.csdn.net/lianai911/...
2018-08-16 11:19:04
176
原创 [置换群] POJ 1026
题意求经过k此置换后的结果思路求出各个循环节的长度然后让k取模 注意输入输出格式代码#include <algorithm>//#include <bits/stdc++.h>#include <cstdio>#include <cstdlib>#include <cstring>#include ...
2018-08-16 11:11:52
190
原创 [置换群] POJ 3270
题意交换牛使他们的脾气指数是上升的,任意交换两个牛的位置花费两个牛脾气的和思路每次用该循环里脾气最小的牛和其他牛交换好位置用其他循环里脾气小的牛来和该循环里所有的牛交换位置(比较难想hhh代码// https://www.cnblogs.com/kuangbin/archive/2012/09/03/2669013.html#include <algorith...
2018-08-16 10:57:12
188
原创 [Burnside] POJ 2888
题意在有珠子不能相邻的情况下,有几种方案思路orz见别人的题解&代码注释代码// https://blog.csdn.net/maxwei_wzj/article/details/73024349#include <algorithm>#include <bits/stdc++.h>#include <cstdio>#...
2018-08-16 10:39:24
243
原创 [polya] POJ 1286
题意3个颜色,n个珠子,旋转+翻转思路代码#include <algorithm>//#include <bits/stdc++.h>#include <cstdio>#include <cstring>#include <iostream>using namespace std;typedef long...
2018-08-16 10:19:16
146
原创 [polya+欧拉函数] POJ 2154
题意依旧是计数,n较大,不能直接枚举 联系正常的公式 https://blog.csdn.net/maxwei_wzj/article/details/72866802 https://blog.csdn.net/acdreamers/article/details/8656247思路代码#include <algorithm>//#include &l...
2018-08-14 19:58:46
197
原创 [polya] POJ 2409
题意旋转+翻转思路组合数学第一题代码#include <algorithm>//#include <bits/stdc++.h>#include <cstdio>#include <cstring>#include <iostream>using namespace std;typedef lon...
2018-08-14 19:53:23
153
原创 [枚举] codeforces 1019A Elections
题意给竞选队伍投票,每个选民经过贿赂之后可以将票交给你 给出当前的投票情况和价格 求第一个队伍最少要花多少钱才能保证自己赢(票数超过其他所有人)思路因为可以从对方抢票,双方一减一增,不好确定最终到底多少票就能赢 枚举其他人的最多票数,求出能保证自己一定超过这个票数下的最小花费 如果当前 i 比最多票的队伍们小,则一定要从票多的人那里抢 剩下的用前述最少的票来补齐就可以了代...
2018-08-13 23:10:25
211
原创 google kickstart 2018 D A.candies
题意n个糖果之中找出一段区间,使得甜度和 < d且其中甜度为奇数的糖果数 < o 小数据限定甜度是递增d思路小范围数据 两个指针:对每个l,都使得r为符合条件的,距离l最远的那个值 更新到左指针为l+1的时候只需要从r开始再向后寻找当前的最右 Problem A Analysis https://code.google.com/codejam/contest/63...
2018-08-13 22:52:37
507
原创 [Kruskal] UVA1151
题意给你点的坐标, 还有一堆已经连好有固定花费的集合, 求花费最小的生成树思路集合只有8个, 枚举所有加入和不加入的可能性 TLE, 用到并查集的路径压缩(好像有的代码不用也可以) 注意细节 还有什么传说中的UVA的输出格式 (小声)一天就能做一道题…..代码#include <algorithm>#include <bits/stdc++.h&...
2018-07-04 20:24:55
182
原创 [Kruskal] UVA 1395
题意给出一个n节点的图，求苗条度(最大边减最小值）尽量小的最小生成树思路边按权值排序，然后就要找一个区间【l，r】,可以构成最小生成树，然后最大边减去最小边的权值，这样一次枚举区间左侧，更新最小值。代码#include <algorithm>#include <bits/stdc++.h>#include <cstdio>#incl...
2018-07-03 22:09:46
171
原创 [Archlinux] Kernel Compilation
Traditionalhttps://wiki.archlinux.org/index.php/Kernels/Traditional_compilation config改成自己的，剩下照抄就行了 booter是grubcd linux-4.1.51make cleanmake mrproperzcat /proc/config.gz > .configvim .con...
2018-07-03 16:12:35
254
原创 [oh-my-zsh] vi-mode导致上下键不能补全历史命令
不造怎么解决，干脆卸载了x https://github.com/robbyrussell/oh-my-zsh/issues/6626
2018-06-09 13:57:34
1384
1
原创 [Archlinux] Enable Scroll_Lock for lights on the keyboard
https://askubuntu.com/questions/127167/how-do-i-enable-scroll-lockxmodmap -e ‘add mod3 = Scroll_Lock’ add MODIFIERNAME = KEYSYMNAME … This adds all keys containing the give...
2018-05-26 13:54:05
164
原创 [Archlinux] NMI watchdog: Watchdog detected hard LOCKUP on cpu x
https://www.reddit.com/r/linuxquestions/comments/7lvnm7/freeze_when_shutting_downrebootinglogging_out_nmi/https://wiki.archlinux.org/index.php/NVIDIArt 舍友上次的bug一直没修好，进系统就卡死…害她弄了两周内核降级好像没用 进tty...
2018-05-19 22:37:50
5567
2
原创 [贪心] POJ 2940/uva 11054 Wine trading in Gergovia
一题街道上很多酒店，交易葡萄酒，正数为卖出葡萄酒，负数为需要葡萄酒，总需求量和总售出量是相等的，从一家店到另外一家店需要路费（路费=距离×运算量），假设每家店线性排列且相邻两店之间距离都是1,求最小路费
2018-05-03 22:09:57
224
原创 [贪心] HDU 4864 Task
题意有n个机器有m个任务，需要机器x和y都要大于等于任务的x，y就能得到500*x+2*y的任务报酬，问最多能够解决多少任务，一共能够获得多少报酬。思路先保证数量最多，再保证钱数最大 按照x降序排列， x相同的时候按照y降序排列， 这样就可以保证钱数最多 对于一个工作我们可以选择的是所有x1>x的机器， 而在这些机器中我们选择最小的y1， 这样可以保留比较大的y1使其去匹配后...
2018-05-02 23:17:29
175
原创 [贪心] HDU 3979 Monster
题意V11是一个无敌的人（打不死），但是他的攻击力有限，每回合怪物和v11同时互相攻击，问最少V11受到的伤害、思路有点要绕hhh 开始的时候可能会认为是攻击力越高越先处理。但是仔细考虑之后贪心点不仅仅由攻击力决定，还要它的生命值同时决定。勇士在攻击一个怪兽的同时别的怪兽也在攻击勇士，他们的伤害也在叠加。所以优先消灭的怪兽有两个因素同时的决定即有怪兽的攻击力和生命值的比值决定，攻击和...
2018-05-02 23:02:07
216
原创 [贪心] HDU 5500 Reorder the Books
题意给定一个从1到n的乱序序列，每次取一个数到最前面，问最少多少次能使序列变为增序。思路先找到数n的位置，在n之前找n-1，若没找到n-1，则n-1需要操作，所有小于n-1的数均需要操作；若找到了n-1，再接着往前依次找n-2，n-3，。。。假如数k找不到了，那就是至少需要k次操作。代码// https://blog.csdn.net/ymrfzr/article/deta...
2018-05-02 22:55:57
137
原创 [贪心] HDU 3661 Assignments
题意将2N个任务分成N组，保证每组当中包含一个A任务，一个B任务，每个任务需要花费的钱是a+b-t。问最小花费是多少思路令一种任务最大的加上另一种任务最小的来组成一个小组代码#include <algorithm>#include <cmath>#include <cstdio>#include <cstdlib>#i...
2018-05-02 22:53:41
131
原创 [算数基本定理] LightOJ 1341
题目大意 给出面积n，和最短边m，求能形成的矩形的个数（不能为正方形）。题目思路 根据算数基本定理有: 1.每个数n都能被分解为：n=p1^a1*p2^a2*^p3^a3……pn^an(p为素数); 2.n的正因数的个数sum为：sum=（1+a1）(1+a2)(1+a3)……(1+an); 最短边为m，若m>=sqrt（n），则无解。所以m最...
2018-05-02 22:51:19
176
原创 [贪心] HDU 5461 Largest Point
题意给定一个序列,求a*ti^ti + b *tj最大值。要求(i != j).思路由于题目数据非常大,所以估计时间复杂度只可能为O(n),所以我们可以将a*ti^ti + b *tj分成两部分(左右两部分)分别贪心求出最大值。因为i != j,所以必须记录一下下标，然后判断,如果下标不相等，max(左部分)+max(右部分),如果相等max(max(第二大的左部分)+max(右部...
2018-05-02 22:49:42
158
原创 [贪心] HDU 5281 Senior's Gun
题意 有n把枪 m个敌人 每把枪有一个攻击值a[i] 每个敌人有个防御值b[i] 如果a[i]>b[i]可以获得a[i]-b[i]的奖励 求奖励值总和的最大值思路 最大a - 最小b代码#include <algorithm>#include <cmath>#include <cstdio>#inc...
2018-05-02 22:46:41
180
原创 [Archlinux] Stuck on Loading initial ramdisk
舍友的电脑更新，卡在一半了，强行重启就卡在loading ramdisk不动了
2018-05-02 21:15:34
3226
原创 [Archlinux] 分配swap
https://wiki.archlinux.org/index.php/Swap_(%E7%AE%80%E4%BD%93%E4%B8%AD%E6%96%87)#.E8.87.AA.E5.8A.A8.E5.8C.96在win上ga了4G下来mkswap /dev/sdxy ( sda7 )# swapon /dev/sdxy//开机启动UUID=<UUID> non...
2018-04-18 20:31:02
1337
原创 [约瑟夫环] lightoj 1179
题意 Josephus思路 Josephus代码#include <cstdio>#include <cstring>#include <iostream>using namespace std;int main () { int T; scanf ( "%d", &T ); for...
2018-04-07 23:14:51
205
原创 [规律] lightoj 1148
题意 分别询问n 个人和他支持同一支队伍的人数有多少，从而算出城市里的最少总人数。思路 支持同一个队伍的人有i个，则这i个人当中每个人报数都是i - 1，不足i个i - 1时补上代码#include <algorithm>#include <cstdio>#include <cstring>#include <iost...
2018-04-07 23:09:21
185
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人