- 博客(117)
- 问答 (1)
- 收藏
- 关注
RSS订阅原创 HDU3038 How Many Answers Are Wrong【巧妙并查集】
题目链接http://acm.hdu.edu.cn/showproblem.php?pid=3038思路题意就是说，不停的给你区间和，问你和前面已给出的矛盾的有几个。首先，对于给定的一系列区间[a, b]，只有有某个点相邻的区间，我们才能把它结合，得出新的信息。像[1, 8], [6, 10]这样的不相邻的区间，我们得不出除了他们俩本身以外的任何信息。但例如[1, 10], [1,3], [6,10
2017-07-10 16:25:53
598
原创 HDU5303 Delicious Apples【贪心】【DP】
题目链接http://acm.hdu.edu.cn/showproblem.php?pid=5303思路题意就是说一个环形路径上有很多个苹果，你的背包容量有k，问你把所有苹果拿回起点的最小路径花费。如果不是环形，很明了，先排个序，然后设dp[i]表示拿完前i个苹果的最小花费，则当i<=k，dp[i] = dis[i]，否则dp[i] = dis[i] + dp[i-k]但这题是环形的，所以光把它拆成
2017-07-09 00:10:13
512
原创 CodeForces 652F. Ants on a Circle
题目链接http://codeforces.com/problemset/problem/652/F思路题意是说一个环上有几只蚂蚁，有各自的运动方向，然后蚂蚁碰撞会立刻改变方向，问你t秒之后各个蚂蚁的位置。这是一个经典的蚂蚁碰撞问题。有两点重要结论：首先，蚂蚁碰撞可以视作没有碰撞，穿过去了，不过编号会发生改变。其次，蚂蚁的相对位置不变。所以，t秒之后，蚂蚁的分布我们很容易就可以计算出来，然后只要确定
2017-07-07 15:27:58
512
原创 17th浙大校赛 ZOJ3952 Fibonacci Sequence Chicken Edition【汇编】
题意让你用汇编实现求斐波那契第n项(n<=30)思路比赛时按正常思路想了好写了一发WA了，然后突然想到能不能写30个if，兴冲冲写完WA了，看了遍题目才发现有10^4字数限制，白白浪费半小时。后来实在找不到bug，现场写了个模拟编译器来运行了下，发现运行行数超过限制了（汇编代码写太丑，吃了学校没开汇编课的亏），但是当时时间就剩10分钟了，根本来不及优化，不得已作罢。回去后优化了15分钟就AC了，欲哭
2017-04-10 21:40:09
906
原创 HZNU2016年秋季学期程序设计基础第一次考试题解
A.CCJ的一见如旧给2取余的结果除了1和0还有可能是其他？ 直接输出hello world即可#include<stdio.h>int main(void){ printf("hello world\n"); return 0;}B.CCJ的异想天开题目描述有点拗口，就是跟着题目意思写一遍你会发现最后输出的就是a+b。#include<stdio.h>void main(
2016-11-11 21:48:31
1753
2
原创 CodeForces 711C.Coloring Trees【DP】
题目链接http://codeforces.com/problemset/problem/711/C思路设dp[i][x][l]代表涂完前i棵树，美丽值为x，最后一棵树的颜色为l的最小代价。 那么 for each 1<=c<=m 若第i棵树没颜色 dp[i][x+1][c]=min(dp[i][x+1][c],dp[i-1][x][l]+p[i][c]) , if c!=l d
2016-08-30 01:03:50
1058
原创 UVALive 7392 Bundles of Joy【bitset】【类树形DP】【杂题】
sourcehttps://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=710&page=show_problem&problem=5414Regionals 2015 :: North America - Rocky Mountain思路就是说去买蛋糕，有几个套餐，套餐间互不相交，问你最
2016-08-07 21:16:56
493
3
原创 UVALive 7272 Promotions【拓扑排序】【bitset】
题目链接https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5324思路大意就是说，给你一张拓扑图，表示员工间的优劣，然后给你a,b，问能升职人数分别为a,b时，一定能升职的人有几个，还有升职人数为b时，不可能升职的人数有几个。那么只用求出每个点的
2016-08-06 22:39:59
622
原创 40th Asia Region, Tehran Site, Problem I: Cafebazaar【最大费用可行流】
题目大意就是有n个人，m个app，有几个人是关键人，必须得开发app，有几个app是关键app，必须得被开发。 然后每个人仅可以开发指定的几个app，分别可获得不同的钱 每个人仅可开发一个app，一个app仅可有一个人开发。 问你，在关键人和关键app能不能满足，能的话，最大钱是多少。思路以样例为例：2 41 11 32 1 8 2 103 2 2 3 10 4 50建立网络流如上，
2016-08-05 19:47:57
907
原创 CF698A. Vacations【DP】
题目链接http://codeforces.com/problemset/problem/698/A思路设dp[i][j]表示在第i天干第j种事情，前i天的最小休息天数。 j=0表示休息，1打代码，2运动。不可能的状态置为INF，转移方程就很简单了，具体见代码。 比赛时愣是没想到用dp，早上瞄一眼题解才发现这么简单，总归还是太弱了。AC代码#include <iostream>#include
2016-07-20 12:44:18
878
原创 POJ1451 T9【Trie】
题目链接http://poj.org/problem?id=1451思路让你模拟手机输入法。 我这里是同步造了两棵字典树，一颗以字母为节点，统计probability，另一颗以键盘数字为节点，存当前按键路径probability最大的词和它的probability。 同步的方法是，用一个映射，将一个单词映射成数字，从而在两棵树之间同步插入。看了下网上的代码，好像不用第一棵树也能算出probabi
2016-07-04 11:33:19
358
原创 HDU1247 Hat’s Words【Trie】
题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1247思路叫你在字典中找一些字符串，约束条件：可以拆分成两个已有的字符串 直接暴力肯定超时，所以把所有的词都放在字典树里咨询就可以了。 不过这样复杂度还是有点高，但是竟然能过，看来这题数据还是比较小的。AC代码#include <iostream>#include <string>using nam
2016-07-03 12:23:36
354
原创 PAT L2-012. 关于堆的判断【数据结构】
题目链接https://www.patest.cn/contests/gplt/L2-012思路题目本身不难，就是字符串处理有点繁琐。 但是有个巨坑！就是你必须得边push边造堆，不能一次性读完再造堆，两者造出来的顺序是不一样的！为此改了十多遍（累觉不爱） 这里用了STL的make_heap，自己手写也可以，不怎么长。AC代码#include <iostream>#include <queue
2016-06-07 13:39:02
2607
原创 PAT 团体程序设计天梯赛-练习集 L2-001. 紧急救援 【dijkstra】
题目链接http://blog.csdn.net/tc_to_top/article/details/51427223思路题意是求个最短路，要求路径长度和最短的前提下，点权和最大，并求出长度相等的最短路有几条，并输出路径，是dijkstra的灵活运用。这种题好像写过很多遍了，但这次还是不能一次过，调试了半天。点权和最大很好解决，给dis加一个属性就可以了。输出最短路径，可以用一个数组记录每个点的前驱
2016-05-31 19:19:12
2344
原创 PAT 团体程序设计天梯赛-练习集 L2-006. 树的遍历【数据结构】
题目连接https://www.patest.cn/contests/gplt/L2-006思路给你一棵二叉树的后序和中序遍历，叫你输出层次遍历。 首先找到根节点，就是后序的最后一个数。 然后分别在中序中找这个数的左边和右边，分别挑出在后序中排最后的数，注意遇到已经确定过的数要停止搜索。AC代码#include <iostream>#include <cstdio>#include <cst
2016-05-19 20:57:12
1142
原创 CodeForces 666B. World Tour【BFS】
题目链接http://codeforces.com/problemset/problem/666/B思路给你一张有向图，叫你给出四个点的序列，使得这四个点依次间的最短路之和最大。n有3000，直接枚举四个点肯定超时，所以枚举b、c两个点，然后BFS预处理出能到b的最远的3个点，和c能到的最远的3个点。 之所以是3个点是因为，有可能备选点会和已定点重合，例如abc都定好了，然后d的备选是a、b，那就
2016-05-08 21:19:04
1301
原创 CodeForces 666A. Reberland Linguistics【DP】
题目链接http://codeforces.com/problemset/problem/666/A思路题意就是给你一个字符串，删掉最前面5个字符，问剩下的字符串，从右往左不停拿掉长度为2或3的字符串，且不能连续两次拿相同的字符串，可以不拿完，问所有的拿法中，拿掉的字符串组成的集合是什么，字典序输出。这题虽说代码形式不太像DP，但却用到了DP的思维。从右往左推，设valid[i]表示存不存在一种方案
2016-05-04 08:44:44
1271
原创 ZOJ 3946 Highway Project【dijkstra】【贪心】
题目链接http://icpc.moe/onlinejudge/showProblem.do?problemId=5718思路给你一个无向图，每条边有一个时间c和花费d，叫你选一些边，使得点0到其他所有点的时间之和最小，其次，使总花费最小。因为要使得点0到其他所有点的时间之和最小，所以是个最短路问题，用dijkstra找最短路，为了让花费最小，更新距离的时候，如果耗时相等，但新边的花费比旧边少的话，
2016-04-24 19:31:56
1478
原创 POJ 3071 Football【概率DP】
题目链接http://poj.org/problem?id=3071思路概率DP，方程本身很简单，设dp[i][j]为第i支队伍撑过第j轮的概率。 则对第j轮i所有的可能对手k，dp[i][j]+=dp[i][j-1]*dp[k][j-1]*p[i][k]。但是难点就是怎么找出可能对手k，上网搜了下发现可以巧妙的用二进制搞定。把ijk都从0开始编号，那么在第j轮，i和k可能是对手当且仅当i和k的第
2016-04-18 21:29:47
605
原创 HDU 5667 Sequence【矩阵快速幂】【欧拉函数】
题目链接http://acm.hdu.edu.cn/showproblem.php?pid=5667思路给你fn=⎧⎩⎨⎪⎪1,ab,abfcn−1fn−2,n=1n=2otherwisef_n=\left\{\begin{matrix} 1 ,&n=1 \\ a^b,&n=2 \\ a^bf_{n-1}^cf_{n-2},&otherwise \end{matrix}\right.，叫你
2016-04-17 19:26:56
663
原创 CSU 1711 Kinfolk【模拟】
题目链接http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1711思路题意有点复杂，不好说，看原题吧。就是找到两点层数差距p，和他们的公共祖先离他们层数较小的点的差距q，然后分类讨论。 c是层数较大的那个点的相应的和另一个点同层的父辈。AC代码#include <iostream>#include <algorithm>#include <str
2016-04-17 17:34:10
346
原创 FZU 2214 Knapsack problem【DP】【超大容量背包】
题目链接http://acm.fzu.edu.cn/problem.php?pid=2214思路咋一看是个01背包问题，但背包容量很大，有10910^9，数组肯定开不下，所以要换种思路。就是设dp[i]为拿到总价值为i的物品时所需的最小的背包容量，那么dp[tot_v]=tot_w，其他初始化为INF，然后对于第i个物品，遍历所有价值j，dp[j-v[i]]=min(dp[j-v[i]],dp[j]
2016-04-16 15:44:27
2467
原创 FZU 2215 Simple Polynomial Problem【模拟】【表达式计算】
题目链接http://acm.fzu.edu.cn/problem.php?pid=2215思路题意就是叫你把给你的多项式化到最简，输出各项系数。表达式计算用栈实现就行了，但这题需要改动下，数据栈内不能直接存数字了，而要存多项式，定义一个数组c[i]表示xix^i 的系数，然后自己实现下加法乘法即可。AC代码#include <iostream>#include <cmath>#include
2016-04-14 19:02:01
829
原创 ACM/OI 对拍程序的写法
转载请注明出处：http://blog.csdn.net/wlx65003/article/details/51149196搞程序设计竞赛的同学很多时候都会因为WA但苦苦找不到错误数据而苦恼，虽然肉眼debug的能力也很重要，但有的时候一直手打数据测试两三天也没有必要。这里就介绍一种对拍程序的写法，是我改进过的，自认为效率应该是比较高了。如果你懒得学实现细节了，想直接使用，那么下面...
2016-04-14 11:04:55
21018
18
原创 ZOJ 3930 Dice Notation【模拟】【字符串】
题目链接http://www.icpc.moe/onlinejudge/showProblem.do?problemId=5690思路题目有点长，其实前面都是废话，直接看样例都能看懂。三件事1.Expand dice notations. The< dice> field like “3d5” should be expanded to “([d5] + [d5] + [d5])”. If on
2016-04-12 10:10:19
544
原创 ZOJ 3862 Intersection【贪心】【几何】【模拟】
题目链接http://icpc.moe/onlinejudge/showProblem.do?problemId=5474思路题意是给你很多条线段，你可以交换任意两个点，叫你给出一种交换序列，使得最后没有两条线段是相交的。这里要贪心一下，就是把点按x小优先，x相等y大优先排好序，然后两个两个连起来。 如下图：至于怎么把两个点连起来，只用交换这两个点 其中一个点，和另一个点的相连点 即可。AC代码#
2016-04-11 21:06:16
451
原创 HDU 3549 Flow Problem【最大流】
题目链接http://acm.hdu.edu.cn/showproblem.php?pid=3549思路最大流的入门题，参考http://www.cnblogs.com/luweiseu/archive/2012/07/14/2591573.html不停BFS找增广路，每找到一条，正向边减去流量，反向边增加流量，直到找不到增广路为止。这题两点之间是可能有多条边的，所以读图的时候记得合并下。AC代码#
2016-03-30 21:55:28
354
原创 ZOJ 1654 Place the Robots【二分图匹配】
题目链接http://www.icpc.moe/onlinejudge/showProblem.do?problemCode=1654思路题意是给你一张n*m的网格，其中#代表墙，o代表空地，*代表草，让你在空地上放机器人，任意行列不得出现多个机器人，除非他们之间有墙相隔，现在问你最多能放几个器械人。这题比赛时学长说是二分图匹配，二分图匹配我会，可这题跟二分图啥关系？纠结到了结束都没想出来。后来问了
2016-03-27 19:11:42
509
原创 ZOJ 3790 Consecutive Blocks【离散化】【贪心】
题目链接http://icpc.moe/onlinejudge/showProblem.do?problemCode=3790思路先贴代码，迟点写。AC代码#include <iostream>#include <iomanip>#include <fstream>#include <sstream>#include <cmath>#include <cstdio>#include <c
2016-03-21 20:53:02
479
原创 ZOJ 1100 Mondriaan's Dream【状态压缩】【DP】【DFS】
题目链接http://www.icpc.moe/onlinejudge/showProblem.do?problemId=100思路先贴代码，迟点写。AC代码#include <iostream>#include <iomanip>#include <fstream>#include <sstream>#include <cmath>#include <cstdio>#include <
2016-03-21 20:50:11
532
原创 ZOJ 3596 Digit Number【状态压缩】【BFS】
题目链接http://icpc.moe/onlinejudge/showProblem.do?problemId=4680思路给你n,m，问n的倍数中，最小的，只用了m个数字的（可重复用）是什么。这是我第一次见到这么鬼畜的题，看着题解都打了一下午。首先是状态压缩，用十位二进制数表示选了哪些数，后面跟三位十进制数表示当前的数除以n的余数。然后用BFS保证位数递增，然后大循环里新加的数从小到大遍历，这样
2016-03-19 21:35:25
700
原创 ZOJ 3620 Escape Time II【dfs】
题目链接http://icpc.moe/onlinejudge/showProblem.do?problemCode=3620思路就是给你个无向带权图，每个点也有个价值，问在时间用完前，从起点走到终点，能获得的最大价值是多少。数据范围相当小，但这题可以走回头路，所以如何判重是个大问题。不然数据再小死循环了也没用。有个比较难想到思路是：每条边最多走两次，而且是来回各一次。这么想吧，走回头路的情况只有一
2016-03-19 15:16:54
368
原创 POJ 2488 A Knight's Journey【dfs】
题目链接http://poj.org/problem?id=2488思路题意就是给你p*q的棋盘，行号1~p，列号A~A+q，问你一个马走遍整个棋盘的字典序最小的路径。那就遍历起点，列优先，行其次，然后深搜，深搜的分支也要列小的优先，列一样的行小的优先。然后把路径保存下来，能行的话直接返回就行。但是这么玩的话时间复杂度咋一想是26×26×826×2626\times 26\times 8^{26\t
2016-03-19 12:59:18
415
原创 ZOJ 2853 Evolution【矩阵快速幂】
题目链接http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1853思路题意是n个物种，m次进化，给你每次进化的变换P(i,j)，表示每次有P(i,j)的i物种变到了j物种，给你每个物种的初始数量，问m次进化后，第n-1个物种的数量是多少。这相当于对原来的物种数量做多次线性变换，我们定义一个矩阵，其中aija_{ij}表示每次j物种有
2016-03-16 20:17:16
765
原创 ZOJ 3497 Mistwald【矩阵快速幂】【图论】
题目链接http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4320思路题意是给你一张图，起点是1，终点是m*n，一旦走到终点就立马停止不能再走了，问你可不能正好P步到达终点。可能输出maybe，一定输出true，不可能输出false。这里要用到离散数学的一个定理，就是一张图的邻接矩阵A，P次方后得到的邻接矩阵APA^P 中的元素ai
2016-03-15 19:39:38
700
原创 HDU 1257 最少拦截系统【贪心】【DP】
题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1257思路题意是给你n发导弹的高度，一个系统只能拦截高度非递增的一系列导弹，问最少需要几个系统。有一种思路是求最长上升子序列，则这个子序列的长度即为答案，因为这个子序列中任意两个炮弹不能用一个系统拦截，而其他炮弹都能跟子序列中的某一个归为一组（这句不理解）。这种思路暂时还没想明白。这里用的是另一种贪心的思路
2016-03-14 22:05:36
535
原创 nyoj 306 4th河南省赛 走迷宫【dfs】【二分】
题目链接http://acm.hznu.edu.cn/JudgeOnline/problem.php?id=1852思路参考：http://www.cnblogs.com/algorithms/archive/2012/07/10/2584420.html比赛时这道没有写出来，思路是dfs+二分，这种类型的题这是第二次遇到了，看来这种思路适用性还是挺广的。就是二分遍历难度差mid，然后判断这个难度差
2016-03-05 23:23:15
790
原创 ZOJ 3777 11th省赛 B Problem Arrangement【状态压缩DP】
题目链接http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5264思路题意就是n个题目，第i个题目放到第j个位置的有趣值是p[i][j]，问你随机排列使得有趣值总和大于等于m的期望值是多少。 这个期望值很好算就是n!/cnt。直接dfs会超时，这里用到了DP，而DP的话，如果设dp[i][j]表示放了前i个题目，有趣值总和为j的方
2016-03-04 22:14:18
550
原创 ZOJ 3601 9th省赛 B Unrequited Love【模拟】
题目链接http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3601思路题意就是说给你一堆人名和各自喜欢的人，然后有q个咨询，每个咨询给你一个聚会名单，如果其中有人喜欢着所有其他的人，且不被任何其他人喜欢，那么就符合条件，按字典序输出符合条件的所有人名。题目本身比较水，就是我题目看太快了，没看到还有同性恋这种情况（一脸卧槽）,于是
2016-03-03 16:11:59
506
原创 ZOJ 3705 10th 省赛 A Applications【模拟】
题目链接http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3705思路算是比较简单的模拟题吧，题意太长就不讲了。 比赛时是最后的时间做这题的，结果看太快了没看到分数相同时要按名字字母顺序排，导致WA到最后。 后来debug时想着按分数增序然后输出后m个，结果比较名字时写的还是小于导致名字成增序，逆着输出就是降序了，于是又de
2016-02-29 17:54:24
415
空空如也
VS 调试时怎么看二维动态数组
2016-03-15
TA创建的收藏夹 TA关注的收藏夹
TA关注的人