- 博客(226)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 HDU 4814 Golden Radio Base
题意：将一个十进制的正数装换成phi进制的数。解法：比赛的时候太二，没有发现十进制数可以等于一个phi进制数，而不是约等于。这个想想就知道，因为一个十进制的数肯定可以表示成n*(phi^0),于是显然可以化简成一个规范的phi进制数。利用题目中给出的公式和hint可以得到两个有用的公式：phi^(n) = phi^(n-1)+phi^(n-2)2*(phi^n) = phi^(n+1)
2014-01-22 17:10:28
2034
原创 Tri_integral Winter Training 0 比赛总结
挂的是今年杭州的区域赛。CBA读完这题之后我就觉得可做，而且不是很难，就不想跟board了，所以先敲。但是敲着敲着发现有点不对头，还挺麻烦的，结果花了很多时间才敲完数组开小了，0:31:54 RE于是让ss敲已经被板刷的C题。想了想突然觉得可以贪心，于是C过了后改成贪心再交，0:46:06 WA。马上就发现自己脑抽了，怎么可能是贪心呢，重新检查是数组开小了，而且有更
2013-11-24 22:38:04
1128
原创 HDU 4771 Stealing Harry Potter's Precious
题目注意到k特别小，所以可以分别从@和有宝藏的房间出发，记录下到其他有宝藏的房间或者@的最短路长度。然后K!次枚举去这些宝藏房间的顺序即可#include #include #include #include #include using namespace std;#define MAXN 110int n,m,t,ans;char g[MAXN][MAXN];int
2013-11-24 22:37:36
775
原创 HDU 4772 Zhuge Liang's Password
题目旋转的公式：x'=n+1-yy'=x#include #include #include #include using namespace std;#define MAXN 50int n,a[4][MAXN][MAXN],b[MAXN][MAXN];int main(){ while (scanf("%d",&n)&&n) {
2013-11-24 22:33:24
820
原创 HDU 4775 Infinite Go 解题报告
题目题意：在一个有上、左边界，无右、下边界的棋盘上下棋，如果一片同颜色的棋子周围（只考虑横纵的四个格子）都是边界或者敌方的棋子，则它们会被消去。A、B两人轮流下棋，如果一方下了一个棋子使得有棋子要被消去时，先消敌方的，消完敌方后再看是否要消去己方。已知下棋的位置，求最后剩的棋子个数。题解：用map存下每个棋子的位置，就可以预处理棋子之间的邻接关系。然后依次下棋，遇到同色的棋子则用并
2013-11-18 20:25:28
1574
原创 HDU 4778 Gems Fight! 解题报告
题目题意：有一些背包，每个包里有一些宝石，A和B两人轮流操作，每次可以选一个包，将里面的宝石都放到公用坩埚里。如果坩埚里有某种颜色宝石的数目不少于s个，那么每s个这种颜色的宝石可以变成一个魔法石。如果操作者选完包后能得到魔法石，则他可以再操作一次。每个人都是最优策略（宝石尽可能比对方多），且可操作的时候必须操作，求A最多可以比B多多少魔法石。题解：可以用状压来做，i为哪些包选了，j
2013-11-18 20:15:15
1243
原创 HDU 4777 Rabbit Kingdom 解题报告
题目题意：有n个数字，m个查询，每次询问[l,r]这些数字中，和其他数都互质的数有多少个。题解：从左到右遍历，对每个数因子分解，如果它含有的因子在之前也有数含有，那么便可知那个数和它不互质，所以可以求出每个数i左边第一个和它不互质的数的位置，记为lefi，右边同理，记为rigi。然后将查询按l排序，从左往右遍历原数组，遍历到j时，若存在i使得j-1=lefi，则可知从j到(ri
2013-11-18 19:33:41
1400
原创 HDU 4770 Lights Against Dudely 解题报告
题目题意：有矩阵n*m，每个单元是一个房间，有些房间可被照亮有些不能，可被照亮的房间最多15个。在(x,y) 放置灯那么 (x,y+1 )和 (x+1,y)都会被照亮，但是有一盏灯可以转动90或者180或270度。问使得所有可被照亮的房间都被照亮且不可被照亮的房间不被照亮需要的最少的灯，不可能则输出-1.解法：可以用状压，枚举哪个房间放灯及灯转动的角度，然后看每个可照亮的房间是
2013-11-18 19:26:53
1146
原创 13.10.20 成都区域赛总结
13年区域赛的第一场，上交出题，因为时间合适，又没有上交和电子科大参加，强队应该会少一点，所以我们就选这一场。上交出过的比赛不多，不过听说和浙大风格很像，所以来之前的一个月都在刷浙大月赛，而且为了锻炼一个好的心态，卡题的时候放得下，都挑难的挂。结果就是时好时坏，我心理也不太有谱，ss一副崩溃了的样子，不过反正伸头一刀缩头一刀，想太多也没用。不知道是说普通话的人太少还是口音比较严重还
2013-10-22 16:56:03
1124
3
原创 Tri_integral Autumn Training 3 训练总结
2013年9月26日，原比赛为2010年11月浙大月赛。F场上有多人过，就先做这题。敲完后小心地测了很多样例，又检查了几遍才交，0:11 1AA敲完F后又多读了几次A，确定题意后就开始敲。0:33第一次交，WA了后来想到输入格式的问题，改了再交，1:08 2AC第一次读完C，觉得太神不能做，尽管过得很多卡在D之后，终于发现了C的水题本质2:09 1A
2013-09-27 23:12:55
903
原创 ZOJ 3433 Gu Jian Qi Tan 解题报告
题目题意：有m层，每层的boss有n个特殊部位，要击破某个部位需要吃多个cake，当然也可以不打。每层在打BOSS之前还可以捡到一些cake。求能击破的特殊部位最大数。题解：将特殊部位所需cake从小到大排序，对于当前的部位，设其在第i层，查询1~i剩余cake数是否足够，足够的话从i~1选cake来击破它。//Time:500ms//Memory:7992KB
2013-09-27 22:25:39
1076
原创 ZOJ 3430 Detect the Virus 解题报告
题目题意：要检测一个字符串中，包含多少种模式串。但是主串和模式串都用base64表示，所以要先转过来。题解：转码后，建AC自动机，老题了不多说……但是因为是从base64转来的，所以取值为0~255，因为这个坑了很久。//Time:230ms//Memory:44824KB//Length:3401B#include #include #include
2013-09-27 22:20:06
902
原创 ZOJ 3431 Escape! 解题报告
题目题意：主角要从一座塔中逃脱，每一层除了出口外，还有不超过5个的宝藏，而且每层还有倒塌时间。求在成功离开的前提下，能拿到的最大财宝价值。题解：对每一层做预处理，计算从入口选择某几个宝藏再到出口所花的最少时间。然后对每层做dp[i]，i表示到这层的时间为i，然后枚举所有选宝藏的方案来转移。//Time:190ms//Memory:280KB//Length:26
2013-09-27 22:16:21
876
原创 ZOJ 3429 Cube Simulation 解题报告
题目题意：三维空间上定义了一些操作，就不翻译了……求每个询问操作的结果题解：本来以为很难，后来发现三个坐标是独立的，所以做到当前操作时，可以维护一个映射关系，原本的xi现在应该在xj，就可以直接求了。难怪过的人最多//Time:110ms//Memory:204KB//Length:1354B#include #include #include #i
2013-09-27 22:09:46
856
原创 ZOJ 3427 Array Slicing 解题报告
题目题意：类似于python的切片操作，每次会告诉你将某个区间用某些数字代替，代替前输入这个区间内的数。题目很恶心，没说格式问题，输入中数字可能使用空格隔开也可能是用逗号隔开，而且不一定像它给的，逗号后面还有空格，所以要注意这个问题。//Time:0ms//Memory:23720KB//Length:1191B#include #include #inclu
2013-09-27 22:05:24
872
原创 ZOJ 3432 Find the Lost Sock 解题报告
题目题意：给一些长度为7的字符串（可能有空格），其中有且只有一个出现了奇数次，求这个串。题解：对每一位上的字符做异或，剩下来的就是。//Time:250ms//Memory:188KB//Length:501B#include #include #include using namespace std;#define MAXN 1000010
2013-09-27 22:01:17
894
原创 Tri_integral Autumn Training 2
H小模拟，0：30：55 WAmoor发现i-1写成了i，0：36：25 WA做完A题，再来检查，发现竟然把12×11=132写成了121，1：04：54 3YA一开始想这floyed预处理，后来发现查询不大，spfa效率更高，0：59：59 1AJss算了一下样例，确定题意，但是第二个样例算不对了，moor就敲了记忆化搜，测了10000组数据，本机跑了6s的样子，
2013-09-21 18:07:55
783
原创 杭州网预
1001 高贵冷艳的clarification一直不回答众人的问题，于是，我们敲好了以后，一直没敢交，中间还有段时间不能提交，0:41:28 WA枚举题意，0:42:33 WA发现tarjan判重边的方法是错的，改了，1:00:12 WA觉得不能再卡在1001了，开1003ss再读题，确定题意就是第一炮的意思，发现题意里的坑，特判一下答案，1:20:34 4Y1003
2013-09-21 18:05:49
754
原创 成都网预
1003 签到题，1A1004 开的第二道题，很快就YY了一个想法，抱着试一试的心态，WA了，发现第一炮连题都没有读懂，不是所有的字母都要用上，M>2时，只要用abc就可以了，改了又交，WA了场上1010过得比较多了，放下1004,开1010重新开1004，这次比较仔细，想了几种算法都找到了反例，moor提出了当n足够大的时候，最长回文子串的长度为4的想法，ss用贪
2013-09-21 18:03:23
963
原创 HDU 4731 Minimum palindrome 解题报告
题目题意：要求生成一个字符串，字符集是前m个字母，长度为n，要求包含的最长回文子串最短，多组解输出字典序最小的。题解：1、m==1时，输出n个a。2、m>2时，将“abc”循环输出。3、m==2时：打表找一下规律，当n>8的时候，可以看到开头一定是"aa",然后"aababb"循环。如果最后出现的“bb”后的字符不多于4,则将他们都替换成“a”。在做这题时，对于
2013-09-15 10:46:35
868
原创 HDU 4737 A Bit Fun 解题报告
题目题意：有n个数，求有多少个数对(i, j) 使得 ai|ai+1|ai+2| ... | aj的值小于m。题解：这题有好多种解法：解法1：边读边做，将数拆开成二进制，用pre数组表示在这一位上最近出现1的位置。当做到第j个数的时候，固定数对的右端点为j，那么就在左边找左端点i。从高位到低位和m比较，如果这一位上m是1,那么如果i～j间都是0,则肯定比m小
2013-09-15 10:38:29
865
原创 HDU 4734 F(x) 解题报告
题目题意：对于十进制数n，各位数是AnAn-1An-2 ... A2A1，定义函数 F(x) = An * 2n-1 + An-1 * 2n-2 + ... + A2 * 2 + A1 * 1。求[0,B]中，有多少个数i的F(i)题解：由于指数从10变成了2，所以数变得特别小，999999999也就4599.所以可以预处理，dp[i][j]表示[0,10^i-1]之间
2013-09-15 10:25:41
800
原创 HDU 4730 We Love MOE Girls 解题报告
题目题意：对于一个字符串，如果结尾是“desu”，则将其置换为“nanodesu”，否则在末尾加上“nanodesu”。题解：直接判最后的字符串就好了。//Time:0ms//Memory:292KB//Length:537B#include #include #include #include using namespace std;#defi
2013-09-15 10:17:19
895
原创 HDU 4724 If You Know This,You Must Have NO GF 解题报告
题目题意：Make一个文件有三种命令：1、形如Target: [component ...]，表示要生成Target，必须要先有所有的components，如果某个component还不存在，就先生成它。如果还是不行，就不生成Target。依赖关系不会成环。2、形如g++ a.o b.o -o main，完全可以忽略。3、如果行中有‘#’，则‘#’后的是注释，不用管。
2013-09-12 20:52:15
1395
原创 HDU 4723 How Long Do You Have to Draw 解题报告
题目题意：两条平行线，各有n、m个点。要连一些线，两个端点分别是两条平行线上的点，并且不能交叉。在取得最多三角形的情况下，求最小的总的线的长度。题解：贪心的策略：从左往右，记l和r为两条平行线第一个没被选的点。计算选l或选r新增的线的长度，选最小的。不能严谨地证明，但是画个图感觉是挺对的。//Time:265ms//Memory:1080KB//Length
2013-09-12 20:41:33
1286
原创 HDU 4726 Kia's Calculation 解题报告
题目题意：新定义的加法是不进位的加法。现在给两个数A和B，可由任意调整一个数的各个位的数字的顺序，但不能有前导0,求最大的加和。题解：题目没说都是正数，但姑且这么看吧。分别统计A和B0～9都有多少个，然后从9～0枚举当前位的加和。对加和都为9的组合，肯定能选则选，不用担心影响后面8、7……的组合。但是由于不能有前导0，所以最高位最大时（比如8），究竟用1+7还是2+6就不能
2013-09-12 20:37:07
913
原创 HDU 4722 Good Numbers 解题报告
题目题意：求A～B之间的数，有多少数字的各位和可由整除10。题解：简单数位DP，直接求就好。//Time:234ms//Memory:360KB//Length:868B#include #include #include using namespace std;#define MAXN 100010int arr[30];long long d
2013-09-12 20:31:05
676
原创 HDU 4727 The Number Off of FFF 解题报告
题目题意：一排士兵报数，从1开始，右边是左边+1。取其中一段给你，但是有且只有一个人报错了。求错的那个人的编号。题解：如果a[i]+1!=a[i+1]，则i+1出错了，否则第一个人错。//Time:203B//Memory:676KB//Length:630B#include #include #include using namespace std;
2013-09-12 20:28:20
787
原创 HDU 4716 A Computer Graphics Problem 解题报告
题目题意：模拟一个电池容量……题解：暴力//Time:0ms//Memory:288KB//Length:498B#include #include #include using namespace std;int main(){ //freopen("/home/moor/Code/input","r",stdin); int nc
2013-09-12 20:22:40
715
原创 2013 ACM/ICPC Asia Regional Online （吉林省赛）
1001100210031004100510061007100810091010这是网预前的一场热身赛。一开场，Moor读完1001，是道连输入都没有的签到题，于是开始敲，5分钟后1A。ss告诉我1004是道简单的几何，然后我开始敲，20分钟后交，结果n^3的复杂度T了，大概是函数调用过多吧。由于可敲题很多，决定再检查检查，Moor敲1005,这是一
2013-09-12 10:10:16
2252
原创 HDU 4709 Herding 解题报告
题意：给定平面上n个点，n解法：面积最小的多边形肯定是三角形。所以n^3的枚举点就可以//Time125MS //Memory 300K#include #include #include #include #include using namespace std;const int MAXN= 205;const double EPS = 1e-8;const dou
2013-09-12 09:39:06
878
原创 HDU 4711 Weather 解题报告
题目题意：有m座城市w种天气，已知每天从城市i到城市j的概率，和每座城市每种天气的概率。已知n天的行程每天的天气，求最有可能的这n天每天在哪座城市的序列。多组解输出字典序最小的。题解：直接DP，一天天枚举从i到j地转移。由于n最大1000,直接乘精度受不了，最好取log，并且注意概率为0时返回结果为nan，所以自己手动设一个-INF吧。比赛时3个人读题都看到了旅行了n+1天，并
2013-09-08 21:07:15
1494
2
原创 HDU 4714 Tree2cycle 解题报告
题目题意：一棵树，删一条边或加一条边的花费都是1.求将这棵树变成以条包含全部点的没有多余边的环的最小花费。题解：也就是，先将树分成尽可能少的m条链，然后再把这m条链首尾连起来，花费是2×m-1.类似于树上最长链的做法，以每个点为根的树，求全部分成链的最少数目b，和去掉一条链的最少数目a。前者可选两棵子树的a加上其它子树的b，后者同理，详见代码。//Time:1359
2013-09-08 20:57:06
852
原创 HDU 4708 Rotation Lock Puzzle 解题报告
题目题意：一个n×n（n为奇数）的矩阵，每一圈可以每次顺时针或者逆时针转一格，求最大的两条对角线上的数字和，且求最少的转动次数。题解：对于格子(i,j)其它三个和它会同时在对角线上的格子是(j,n-i-1) (n-i-1,n-j-1) (n-j-1,i)。直接加就行。//Time:15ms//Memory:368KB#include #include #
2013-09-08 20:50:46
775
原创 HDU 4706 Children's Day 解题报告
题目题意：用abcd输出size从3到10的大写N（但是中间的斜线是倒着的），而且按照向下-斜向上-向下的顺序循环地用a-z这几个字母。题解：直接暴力……//Time:0ms//Memory：284KB#include #include #include #include using namespace std;char ma[100][100];int
2013-09-08 20:46:45
621
原创 9月7日 Warming Up 总结
第二次打这种联赛，希望不要像上次一样……开场读题，我读完A题有一种可做的感觉，就打算先把头文件啊文件输入什么的弄好再研究。之后细细一想，跟以前遇到的一些问题相似，但是我不会呀，正好C有人过了，就先敲C，8分钟的时候过了。然后我决定先放下A题读别的，读完B题又有了可做的错觉。K题也有人过了，hq 读完觉得是到几何的模板题，所以我下来想B。后来想到一个push_front()的拓扑的方法，K题
2013-09-07 21:19:31
627
原创 Codeforces 336D. Vasily the Bear and Beautiful Strings 解题报告
题目题意：一个01串，0刚好有n个，1刚好有m个，每次将最后的两个数字变成一个，如果是00则变成1,否则变成0.已知n，m和最后剩的一个数字，求原串可能有多少种。题解：由题，倒过来做，1->00,而0->01,10,11，进一步地0->100,000,10,100，也即是说最后的0可以在前面塞任意多个00或10或1,最后还是0.假如原串最后是0的话，枚举中间00、10和1的个数
2013-09-06 13:49:03
1244
原创 CodeForces 115C. Plumber 解题报告
题目题意：n×m的的矩阵里，每个格子都有一个水管，并且水管是给出的4种形状的一个。有一些地方水管已经确定了，有一些还没有。若两个相邻的水管彼此没有连通则为泄漏。求不泄漏的方案数，不要求水管全部连成一条。题解：原本以为是简单的插头DP，但是看数据规模不可能。根据给出的四种水管，可知任何一种都和左右两格连且只连一个，上下也是，而且左右和上下是独立的，所以可以单独考虑一行和一列。对一
2013-09-06 11:46:26
994
原创 Aizu 1316 The Sorcerer's Donut 解题报告
题目题意：一个n×m的字符矩阵，上下相接左右相接。可以从某个格子出发，选定八方向的一个，保持这个方向不变得到任意长度的连续的字符串（当然同样位置不能选两次）。求最长的、字典序最小的、出现两次及以上的字符串。题解：暴力枚举起点和方向，哈希判重。//Memory:7872KB//Length:1305B#include #include #include #inc
2013-09-05 20:09:16
1077
1
原创 Aizu 1315 Gift from the Goddess of Programming 解题报告
题目题意：一群ACMer去祭坛祈祷，其中在God在的时候祈祷总时长最长的人会被选中……现在告诉你所有人的出入记录，并且God的编号为0,求最长的总时长。读了好几遍，不知道是不是必须当天离开，也不知道是否保证最后全部人都会离开。题解：以保万一，写得很麻烦，但我觉得忽略日期是可以的。 //Memory:1220KB//Length:1193B#include #in
2013-09-05 20:05:32
819
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人