‘’尼玛,少在那装逼。巨大少女与小人国总喜欢得志,我理解你。‘’用英语�
点击联系发帖人
时间：2014-06-08 16:48
随笔分类 - HDOJ
发布一些HDOJ的做题情况以及代码。
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2725题意：给一个字符串表示一条河。'.'表示水，其它字符表示障碍。人在岸上用石子打水漂，每次可以选择一个击中的距离和跳跃间隔。石子多次跳跃后击中障碍物或越过河则结束。每种打水漂的方案按跳跃次数（大者优）、最...
Seraph2012 阅读(103) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1394题意：给n个数字（0到n-1无重复），可以拿前面任意m个放到末尾。求拿多少个数字放到末尾后数列的逆序数最小。mark：非常经典的一个题目，来自zoj月赛。先用线段树/点树/树状数组/合并排序求出原数列的逆序数，然后递推出所有情况的逆序数取最小。这题真的是非常经典，所以4种方法我都写了一次。代码：线段树（62ms、284k、991B）： 1 # include 2 # include 3 4 5 # define m ((l+r)&&1) 6 # define lson l,m,p m)
Seraph2012 阅读(635) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1754题意：给n个数字。m次操作，每次操作更新一个数字或者查询区间最大值。mark：典型线段树题。不过a的时候学了一下树状数组求区间最值。感觉对树状数组的理解又深刻了一点。不过这个更新不是O(lgn)而是O(lgn*lgn)的，比线段树慢！代码：线段树： 1 # include 2 # include 3 4 5 #define max(a,b) (a&b?a:b) 6 7 int tr[200010 m) return q(a, b, m+1, r, rt*2+1) ;29 ..
Seraph2012 阅读(191) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1166题意：给n个数字。对这n个数字有3种操作：1. add 2.sub 3.query。分别对应把某数增加或减少一个值和查询某[l,r]区间内所有值的和。mark：最基本的线段树or树状数组的应用。话说树状数组真是简洁啊！代码：线段树 1 # include 2 # include 3 4 5 int n, tr[50010 m) return query (a, b, m+1, r, rt*2+1) ;25 return query(a, m, l, m, rt*2) + query...
Seraph2012 阅读(49) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2723题意：为了对一个文件进行访问控制，会给每个文件建立一个访问控制列表（ACL），每个列表里有若干个entity（类似于用户组），每个entity有若干个right（权限）。给出一个文件的权限更改日志，日志是ExR形式的短语构成，E是这次操作影响的entity（多个），R是right，x是一个操作符，可以为+、-、=。为+的时候表示把权限加到entity上，为-的时候表示从entity减去相应权限，为=的时候表示把entity设为相应权限。最后输出每个entity对应的权限，没有权限的不输出，2个相邻
Seraph2012 阅读(166) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2721题意：给出a、b、c、s。s是初值，每次变化有s = (a*s+b)%c。如此直到重复。这些数都写成16比特的，如果某位在所有数都是0则输出0，是1则输出1，如果都有可能输出问号。直接暴搞就可以。。。代码： 1 # include 2 # include 3 4 5 int vis[70000] ; 6 7 8 int main () 9 {10 int a, b, c, s, i,11 char ch[20] ;12 13 while (~...
Seraph2012 阅读(66) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2719题意：给一些字符串，把字符串输出。如果有题目里的那7种字符，按%数值的形式输出。代码： 1 # include 2 # include 3 4 5 char str[100] ; 6 char t[] = & !$%()*& ; 7 int p[] = {0x20, 0x21, 0x24, 0x25, 0x28, 0x29, 0x2a} ; 8 9 10 int main ()11 {12 int i,13 while (gets (str))14 {15...
Seraph2012 阅读(41) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1527题意：中文。mark：经典博弈，传说中的Wythoff’s Game。论文在此：http://scimath.unl.edu/MIM/files/MATExamFiles/Cotton_MATpaper_Final_EDITED.pdf值得一提的是论文里提到的神奇的贝蒂定理（Beatty Theorem）：若a和b都是无理数且1/a + 1/b == 1，则{[a],[2a],[3a]...}和{[b],[2b],[3b]...}这两个集合没有相同元素且他们的并组成正整数集。（[x]表示对x下取整
Seraph2012 阅读(119) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1260题意：有个人卖票。从8:00:00am开始卖。后面有n个人，每个人卖票需要ki的时间，但是相邻两个人可以合起来买，需要di的时间。问卖票人最早回家的时间。mark：一个水dp加一个时间的转换。本来可以1A的但是3wa。第一次错是因为小时数忘记处理成不大于12的数字，第二次错是因为把m%=60写成了h%=60，第三次是忘记删除调试语句。都是脑残错误。。。代码： 1 # include 2 3 4 int s[2010], d[2010], dp[2010] ; 5 6 7 int min(...
Seraph2012 阅读(222) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2603题意：从高度为3米距离天花板0.5米处抛掷一物体，倾角为a，质量为m，初速度为v。若碰到天花板则以反射定律反射出去。问物体能抛多远。mark：推公式解的物理数学题。只要还记得S = vt + 0.5gt^2的自由落体公式，根据其求出总飞行时间，剩下的都很好解决。注意解方程的时候考虑若有2个解，取哪一个。代码： 1 # include 2 # include 3 4 5 double pi = acos(-1.0), g = 9.87 ; 6 7 8 int main () 9 {10 ...
Seraph2012 阅读(80) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2602题意：骨头收集者在收集骨头。有容量为V的袋子，n个骨头，给出每个骨头的体积和价值。问最大能收集的价值。01背包。代码： 1 # include 2 # include 3 4 5 int dp[1010] ; 6 int max(int a, int b){return a&b?a:b;} 7 int val[1010], vol[1010] ; 8 9 10 void work()11 {12 int n, v, i, j, ans = 0 ;13 scanf (&%d...
Seraph2012 阅读(463) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2600题意：给一个区间p和q表示年份。给n个战争的起始年份、终止年份和战争名字（其实无用）。问[p,q]区间内最大没有战争的年份是多少。mark：600w*2的区间*100个战争如果直接开bool数组实在是很勉强。可以把战争先按起始年份再按终止年份排序，for一遍，维护一个last变量表示已经检查过的战争里最大的结束年份。具体看代码。代码： 1 # include 2 # include 3 4 5 int a[110][2] ; 6 int max(int a, int b){return a...
Seraph2012 阅读(108) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1840题意：给一个方程ax^2+bx+c==0的三个系数a、b、c。判定方程解的个数。mark：除了利用判别式，还需要注意考虑非二次的情况。代码： 1 # include 2 3 4 void work() 5 { 6 int a, b, c, 7 scanf (&%d%d%d&, &a, &b, &c) ; 8 if (a==0) 9 if (b == 0)10 if (c == 0) puts (&INF&) ;1...
Seraph2012 阅读(57) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2701题意：你有一双可以瞬移的鞋子，任务是要捕捉一直可以瞬移的萤火虫。给出自己每次瞬移的最远距离和起始坐标，再依次给出这只萤火虫出现的坐标。每次虫子出现，你都向它的坐标瞬移。一旦你和虫的距离不超过1，则认为捕捉到。问虫子在哪个坐标被捕捉到（或不能被捕捉到）。mark：阅读题。阅读了好久，题目又臭又长，只要明白了题意很容易1A。。。代码： 1 # include 2 # include 3 4 5 int r, x, 6 7 8 double dist(double ax, doubl...
Seraph2012 阅读(178) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1587题意：有n种花每种数量无限多，价格是p[i]，有m元钱最多能买多少支。mark：这题竟然不给数据范围。不过好像数据范围不大，m不超过10000，n不超过1000。一开始以为是完全背包后来发现根本就是个贪心。。。代码： 1 # include 2 # include 3 4 5 int a[1000] ; 6 int cmp(const void *a, const void *b) 7 { 8 return *(int*)a - *(int*) 9 }10 11 12 int...
Seraph2012 阅读(75) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1678题意：买3样东西，最便宜的那样可以被当做折扣而不用付钱。问n样东西最多能获得多少折扣？mark：贪心，排序后从大到小3样3样地买。代码： 1 # include 2 # include 3 4 5 int a[20010] ; 6 7 8 int cmp(const void *a, const void *b) 9 {10 return *(int*)b - *(int*)11 }12 13 14 15 void work()16 {17 int n, sum ...
Seraph2012 阅读(147) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2110题意：中文。mark：母函数。但是判有无解的时候要注意，假如答案是10000种，对10000取模后就是0，此时不能判断为无解。可以加一个数组solution表示是否有解。代码： 1 # include 2 # include 3 4 5 int n, sum, MOD = 10000 ; 6 int p[110], m[110], dp[10010], sol[10010] ; 7 8 9 int work()10 {11 int i, j,12 if (sum...
Seraph2012 阅读(112) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2303题意：输入2个数字k和l，第一个是大数（10^100），第二个数是一个上限（10^6）。问k是否有小于l的质因数，如果有，最小的是多少。mark：时限卡的比较严，先把100w以内的素数打表，然后挨个检测素数，每次用大数对这个素数取模。若模为0则为素因子。代码： 1 # include 2 3 4 5 char k[110] ; 6 int prime[1000010], isprime[1000010] ; 7 8 9 void init()10 {11 in...
Seraph2012 阅读(88) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2183题意：中文。。。mark：一开始有点晕，没看出规律。后来发现规律就是个水题。从sample里的1开始看，向右下。。。代码： 1 # include 2 # include 3 4 5 int dp[22][22] ; 6 7 8 void work(int n) 9 {10 int i, j, x,11 memset (dp, 0, sizeof(dp)) ;12 x = n/2 + 1, y = n/2 ;13 for (i = 1 ; i &...
Seraph2012 阅读(67) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1114题意：小盆友通过往猪猪存钱罐里放钱的方式攒钱做事。存钱罐除非砸坏，否则无法把钱取出。为了知道是否攒了足够的钱，对存钱罐称重。然后告诉每种钱币的重量和价值，问存钱罐里最少可能有多少钱。mark：算是一个比较裸的完全背包问题。只不过是选最小。代码: 1 # include 2 # include 3 4 5 int n, m, INF = 0x3f3f3f3 6 int p[510], w[510] ; 7 int dp[10010] ; 8 9 10 int min(int a, i...
Seraph2012 阅读(712) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1264题意：给许多矩形，求面积并。坐标是0到100内的整数。mark：把矩形覆盖的区域赋值为1。。。代码： 1 # include 2 3 4 int g[110][110] ; 5 6 7 int main () 8 { 9 int a, b, c, d, t, i, j,10 while (~scanf (&%d%d%d%d&, &a, &b, &c, &d))11 {12 if (a == -1 && b == -1
Seraph2012 阅读(77) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1727题意：给一个数字，输出它的英文。。。细节比较多，小心点就不容易出错。代码： 1 # include 2 3 4 char tab[][20] = { 5 &zero&, &one&, &two&, &three&, &four&, &five&, 6 &six&, &seven&, &eight&, &nine
Seraph2012 阅读(49) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1133题意：电影院卖票。一张票50元。一开始没有零钱。有m+n个人买票，m个人拿50元的钞票，n个人拿100的。问队伍有多少种排列方式可以使得卖票能顺利进行下去。mark：如果要使得卖票的行为进行下去，对于任意前k个人，必须满足这k个人里面拿100的人数不多于拿50的人数。结果会是一个大整数，要用高精度。公式是n!m!(m-n+1)/(m+1)。推导比较难想，和卡特兰数有关，网上有一篇文档详细写明了这个过程：http://daybreakcx.is-programmer.com/posts/17315.
Seraph2012 阅读(979) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1798题意：给两个圆的圆心和半径求相交部分的面积。mark：思路是把相交部分分成2边，每边求一个扇形减三角形的面积。注意相离和内含的情况判断。这题wa了n次，都是因为精度问题。一个三角形已知三边，求某角。可以用余弦定理直接求，也可以先用海伦公式算出面积，再用正弦定理求（误！！！）。但是海伦公式算面积后再正弦定理会产生比较大的误差！！！# include &stdio.h&# include &math.h&double xa, ya, ra, xb, yb,double
Seraph2012 阅读(91) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1753题意：中文。。。高精度正小数加法。mark：高精度加法，如果把整数部分和小数部分分开搞，比较麻烦。定义了一个struct，数组存数字，dec存的是这个数字里末尾的多少位是小数部分的。两个小数相加，先对齐小数位（位数少的在后面补0）然后当整数加法搞！wa了一次。用宏要注意！41行和42行，如果没有加{}的话，前面的if只管一句！代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 #define ExPand(a,b)
Seraph2012 阅读(279) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2197题意：中文。mark：这题一看题感觉应该是简单题，但是想了挺久。一开始看到是这种单输入单输出的，而且n达到10^9那么大，想了一下应该是公式，没啥好的思路，就果断打表，然后丢到oeis.org里，结果发现根本没公式。后来思考了一下，因为每个串所有可能肯定是2^n，设{i1,i2...im}是n的所有因数，可知非本源串的个数是2^n - sum{f[i1],f[i2]...f[im]}。其中f[i]代表长度为i的非本源串个数。这样只要枚举一下递归就可以了。犹豫了很久没写，总觉得复杂度很大。后来写完以
Seraph2012 阅读(244) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1175题意：中文不多说。mark：3WA，各种脑残错误不多说。最后一个竟然是忘记写return 0。无法直视。说下算法，这题感觉既可以dfs，也可以bfs，但是都不是特好写。好在转弯数限定为2次。那么可以尝试一下比较生猛的写法：先把起点和终点不需转弯直接可达的区域染色（形状大概是2个十字架）。如果这2个区域有重合的地方，自然是YES了。如果没有，扫每一行和每一列，看是否存在2个不同颜色区域之间都没有别的棋子（全0）的情况，如果有，则YES。否则NO。代码： 1 # include &stdio.h
Seraph2012 阅读(158) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2483题意：给一个n*m的0-1矩阵。在里面找符合条件的方阵。条件有3个：1.方阵的4条边上全为1；2.方阵内（除了4条边的）0和1的个数之差不超过1；3.方阵大小至少为2*2。问能找到几个这样的方针。mark：最朴素的做法是枚举所有的1当做要找的方阵左上角的元素。然后判断四边是否全为1，再统计内部0和1的个数。但是每次判断边上的1和计算内部1的数量复杂度太高，肯定是不行的。我们用一个数组sum[i][j]表示从矩形左上角到(i,j)这个位置里1的个数。在计算区域内1的个数的时候可以利用这个sum[i]
Seraph2012 阅读(84) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2717题意：在x坐标上，农夫在n，牛在k。农夫每次可以移动到n-1, n+1, n*2的点。求最少到达k的步数。mark：bfs。范围是2*k内。因为如果当前点大于k，执行2*n和n+1的操作都不是最佳选择。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 int vis[200010] ; 6 int q[200010] ; 7 8 9 int bfs (int n, int k)10 {11 int f = 0, r
Seraph2012 阅读(557) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2716题意：第一行给出一个字母表的排列。用其解密第二行的文本。代码： 1 # include &stdio.h& 2 3 4 5 int main () 6 { 7 char tab[30], str[100] ; 8 910 while (gets (tab))11 {12 gets (str) ;13 for(i = 0 ; str[i] ; i++)14 {15 ...
Seraph2012 阅读(80) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2715题意：给一个n，问能表示成几种连续数字的和的形式。mark：很简单，当然是枚举连续数字的个数(从1到sqrt(n))。代码： 1 # include &stdio.h& 2 3 4 int main () 5 { 6 int n, d, 7 while (~scanf (&%d&, &n)) 8 { 9 ans = 0 ;10 for (d = 1 ; d*(d+1) &= 2* d++)11 {12 ...
Seraph2012 阅读(74) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2714题意：给一串ISBN号，根据算法求出缺的(?表示)那一位。算法是各位上的数字按权相加，和必须为11的倍数。没啥好说的，直接穷举。注意不存在输出-1。代码： 1 # include &stdio.h& 2 3 4 int main () 5 { 6 char str[20] ; 7 int sum, i, 8 while (gets(str)) 9 {10 sum = 0 ;11 for (i = 0 ; str[i] ...
Seraph2012 阅读(82) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2711题意：有n个牛排成一列，每个牛有序号(1~n)，给出每个牛之前有多少个序号小于当前牛的牛数，求序号。第一头牛的未给出。mark：直接从后往前，每次找小于它但是没被选过的序号有多少个，暴力，效率是O(n^2)，200+ms。正解应该是树状数组之类的，懒得写了。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 int dp[8010], ans[8010], a[8010] ; 6 7 8 int ma
Seraph2012 阅读(99) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2710题意：输入n个数，找到最大素因子最大的那个输出。mark：此题实在是坑，1算素数不说，题目是尼玛多组输入的。。。而且我更2，5WA，刚被坑了一个同样的地方，又被坑。。。代码： 1 # include &stdio.h& 2 3 4 int dp[20010] = {0,1} ; 5 6 7 int IsPrime(int x) 8 { 910 for (i = 2 ; i*i &= i++)11 if (x %i == 0) retu...
Seraph2012 阅读(82) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2709题意：一个整数n，表示为若干个2的幂的数字和，问有多少种(mod 1e9)。mark：递推题，考虑1的个数不同，剩下的都是2的幂，可以除以2转移成更小的状态。得递推方程为dp[i] = dp[i-2] + dp[i/2]。注意初始值。代码： 1 # include &stdio.h& 2 3 4 int tab[1000010] = {1, 1, 2} ; 5 6 7 int main () 8 { 910 for (i = 3 ; i &= 1000000...
Seraph2012 阅读(109) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2708题意：给4行，统计大写字母的频率，然后按图示输出。mark：此题很坑，主要表现在：1.每行行末的空格不可以输出！2.输入是多组！！！wa了n次。一开始找max_row的时候初始化各种改错。。。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 int tab[300] ; 6 char str[100] ; 7 int max_tab[300] ; 8 9 10 int main ()11 {12 int i, j
Seraph2012 阅读(81) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1022题意：火车调度问题，栈的基本应用。。。2wa。。。变量忘记初始化。。。太2了。代码： 1 # include &stdio.h& 2 3 4 int n, ans[25] ; 5 char s1[15], s2[15] ; 6 char s[15] ; 7 8 9 int gao()10 {11 int i, p = 0, q = 0, top = 0 ;12 for (i = 0 ; i & 2* i++)13 {14 if (top != ...
Seraph2012 阅读(81) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1209题意：给5个时间（小时：分钟），将之排序。排序规则是按指针锁夹锐角小到大，若夹角相等则按时间早到晚。最后输出中间的那个时间。mark：题目很简单，角度也很好算：时针每小时走30度，每分钟走0.5度。分针每分钟走6度。做差后取绝对值，再和180比一下，如果大于180，用360减。为了避免浮点数排序的麻烦，可乘以2倍后排序。3WA。。。排序的时候if语句后面手贱多写了一个;查了半天才查出来。。。 1 # include &stdio.h& 2 # include &stdlib.h&
Seraph2012 阅读(255) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1709题意：给n个砝码的重量，问从1到重量总和中不能称出的重量的个数和分别都是谁。mark：注意新砝码可以加在左盘也可以加在右盘。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 int dp[10010] ; 6 int buff[10010] ; 7 8 9 10 int abs(int a){return a&0?-a:a;}11 12 int main ()13 {14 int i, j,
Seraph2012 阅读(218) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1060题意：n的n次方最左边的数字是多少。mark：还是取对数那招，log10(n^n)的小数部分决定了最左边的数字。代码： 1 # include &stdio.h& 2 # include &math.h& 3 4 5 int calc(long long n) 6 { 7 double ans = n * log10(n) ; 8 ans -= (long long) 9 return (int)pow(10,ans) ;10 }11 12 13 int ma..
Seraph2012 阅读(49) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1045题意：给定一个最大4*4的方形地图，里面有墙(X)和空地(.)。在每个空地上可以放大炮，但两个大炮如果在同一行或同一列并且之间没有墙阻隔的话，会互相攻击，所以不能同时存在。问最多能放多少个大炮。mark：数据小，直接dfs就可以了。1WA，把保存状态的数组开成了全局的- -。据说还可以二分匹配过。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 char g[4][4] ; 6 int vis[4][4] ; 7
Seraph2012 阅读(650) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2390题意：输入n个运动会项目的举办天和起止时间，不能同时看两场，问最多能看多少场。mark：经典贪心，注意每组输出后面都有一个空行。代码： 1 # include &stdio.h& 2 # include &stdlib.h& 3 4 5 typedef struct NODE{ 6 int s, 7 }NODE ; 8 9 10 NODE sche[50010] ;11 12 13 int cmp(const void *a, const void *b)14 {1
Seraph2012 阅读(65) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2191题意：中文。512地震默哀。mark：dp。多重背包。先做了1171再做这题就很容易了。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 int dp[110] ; 6 7 8 int main () 9 {10 int T, ans, n,11 int p, h, c, i,12 scanf (&%d&, &T) ;13 while (T--)14 {15 ...
Seraph2012 阅读(638) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1176题意：中文。mark：dp即可。。。类似数塔。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 int dp[] ; 6 int n , INF = 0x0f0f0f0 7 8 9 int main ()10 {11 int i, j, k, buff, x,12 int max_t,13 while (~scanf(&%d&,&n)&
Seraph2012 阅读(79) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1171题意：有n样物品，每样物品价值是v，件数是m。尽量把这些物品分成两堆使得两边总价值最接近。输出价值。mark：水dp，或者用母函数搞。wa了3次，trick在于结束标记是负数，而非-1。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 int dp[250010] ; 6 7 8 int main () 9 {10 int i, j, k,11 int n, m,12 while (~s...
Seraph2012 阅读(237) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2700题意：一个字符串如果有偶数个1，就是o，有奇数个1就是e。给出缺了最后一位的字符串和它的属性，求补足最后一位的字符串。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 char str[110] ; 6 7 int main () 8 { 9 int i, cnt,10 11 12 while (gets (str))13 {14 if (strcmp(str, &...
Seraph2012 阅读(113) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2707题意：在一篇文章中，每一段连续的空格代表一个0或一个1。偶数个代表1，奇数个则为0。把所有空格连起来得到一串0-1组成的二进制，再进行解密。每5个0-1二进制字符对应1个字母，末尾不足5个补零。二进制对应的十进制中，0代表空格，1代表A，2代表B……26代表Z，之后27到31分别代表',-.?。按要求解密文章。mark：暴力搞就好，题目说保证空格不出现在每行的行头和行尾，就简单多了。装逼没有好下场，1wa就wa在不想用memset，结果i+j&=cnt写成了i+j&cnt。。。
Seraph2012 阅读(121) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2703题意：有n条通道首尾相连，每个通道有一个容量p和一个通过时间sec，表示最多一次能一起进p个人，需要sec的时间通过。现在有m个人在第一条通道的开始处，他们按照策略通过n条通道。策略有2点要遵守，1是每个通道同一时间只能进一组人，2是只要通道为空并且通道口有人，通道口的人必须立刻进入通道（显然这不一定是最佳策略）。现在就按要求模拟题意，最后问m个人都通过的总用时。mark：一开始觉得是个纯阅读题，再后来发现写起来有的地方也挺难想的。数据规模较小，直接暴搞（总用时最大才780s）。代码： 1 # i
Seraph2012 阅读(96) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2572题意：中文。mark：直接暴搞。1wa，注意要取字母序最小的，长度要先判断。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 char ans[110] ; 6 char s1[110], s2[110], s3[110] ; 7 char ss[110] ; 8 9 10 int find(char s[], char p[])11 {12 int i, j, len1 = strlen(s), len2 = s
Seraph2012 阅读(131) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1804题意：要把输入的英文字符串转化成复数的形式。mark：规则就是那4条。注意y的判断还要满足前一个字符不是元音字母(aeiou)就可以了。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 char dict[25][2][25] ; 6 int n, 7 8 9 int find(char s[])10 {1112 for (i = 0 ; i & i++)13 if ...
Seraph2012 阅读(87) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1978题意：中文。mark：水题。可以dfs搞，也可以dp搞，此处是dp。写错下标wa了1次，忘记删调试信息ole一次。太2了。代码： 1 # include &stdio.h& 2 3 4 # define MOD
7 int a[110][110], dp[110][110] ; 8 int n, 9 10 11 int calc(int x, int y)12 {13 int i, j, rtn = 0 ;14 if (x == n-1 &&
Seraph2012 阅读(120) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2184题意：中文。。。就是递归了。代码： 1 # include &stdio.h& 2 3 4 5 6 7 8 int pil[3][70] ; 9 10 11 void gao(int a[], int b[], int c[])12 {13 long long mid = (1LL && (n-1)) ;14 if (n == 0)15 if (m &= mid)16 {17 c[...
Seraph2012 阅读(79) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1997题意：中文。。。mark：生生递归就好了。代码： 1 # include &stdio.h& 2 3 4 int num[4] ; 5 int pil[4][70] ; 6 7 8 9 int judge(int a[70], int b[70], int c[70], int na, int nb, int nc)10 {11 // printf (&%d\n&, n) ;12 if (n == 0) return 1 ;13 if (na <
Seraph2012 阅读(99) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1992题意：用1*2和2*1的小长方形铺垫4*W的方格有多少种方法。mark：这题真是一个非常有意思的题目，第一眼看，觉得应该是很简单的递推题，但是又秒不掉，灰常让人捉集。首先递推总是想着从后往前由已知解来推出新解。这题很容易想到当W为n的时候，用n-1的结果加上两个竖杠和n-2的结果加上题目分析的那五种中不和n-1重复的4种情况来构造。但是但是但是，这是不完全的。在推导W=3的情况时发现只有9种，然而按题目应该是11种。想了很久才发现漏掉了以下这种情况（由于对称，因此少2种）： -- -- --| .
Seraph2012 阅读(332) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1988题意：n块煎饼，尺寸分别为1至n，从上到下堆成一堆。正面朝上为+，反面朝上为-。每次可以选择上面若干块整个翻转过来。求翻转的步骤，能使得最后正面朝上，尺寸从上到下是小到大。mark：没啥困难的，每次选最大的那个经过不超过3次操作翻到最底下。sample给得很好，主要是注意最顶上1的处理就可以了。代码： 1 # include &stdio.h& 2 3 4 int n, a[35] ; 5 int ans[110], 6 7 8 int abs(int x){return
Seraph2012 阅读(123) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1987题意：就是1986的逆向。。。解码。mark：要注意的是要去掉解码出来的字符串的结尾空格。如果字符串是空串，数字和字符串之间的空格不需要去掉。一直PE，后来发现是去结尾空格的时候，i = len - 1写成了i = len。。。太2了。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 char str[410] ; 6 char out[25][25] ; 7 char ss[100], ssout[110] ;
Seraph2012 阅读(48) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1986题意：按要求把字母或空格字符串扩展成5个01字符表示的字符串以后，缠绕放置在一个r*c的矩阵里。最后一排一排输出。mark：各种wa。后来才发现是输入的问题。当字符串长度为0的时候，我本来用的是scanf的正则输入，结果事实证明不行。。。另外用来放置扩展以后的字符串的字符数组ss一开始忘记清0也wa了一次。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 char str[100] ; // less than 8
Seraph2012 阅读(124) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1981题意：给长度为n的小写字母字符串，有3种操作：&Q A&：输出当前字符串的第A个字符;&S A B&：把第A个到第B个字符都加1。a变成b，b变成c，z变成a。。。&R A B&：把从A到B的字符串逆转。输出就是Q操作的时候的输出。mark：这题真是tricky。一看8w个字符，先知道直接搞是肯定不行的。后来想了一下也没想到好办法。查了一下，原来可以记录下每次的操作，然后查询的时候根据位置往前循环，因为查找次数少，因而效率比较高。一开始w
Seraph2012 阅读(96) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1673题意：一条路上有n家商店，给出坐标。某人停车在某点后，要逛完所有商店回到车出。停车地点自选，求最少需要步行多远。mark：唬人，其实就是最大值与最小值差的两倍。代码： 1 # include &stdio.h& 2 3 4 int main () 5 { 6 int T, n, 7 int max, 8 scanf (&%d&, &T) ; 9 while (T--)10 {11 scanf (&%d&, &
Seraph2012 阅读(149) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1236题意：中文名。这种排序题已经无力吐槽了。敲错变量tle了一次- -。代码： 1 # include &stdio.h& 2 # include &stdlib.h& 3 # include &string.h& 4 5 6 typedef struct STU{ 7 char name[25] ; 8 9 }STU ;10 11 12 STU stu[1010] ;13 int scr[15] ;14 15 16 int cmp (const
Seraph2012 阅读(116) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2571题意：中文。mark：水dp。不过边界不太好处理，写成dfs+记忆化比较方便。给2组容易错的数据。应该都输出0。21 2-1 12 1-11代码： 1 # include &stdio.h& 2 3 4 int a[25][1010], vis[25][1010] ; 5 int n, m, INF = 0x0f0f0f0 6 7 8 int max(int a, int b){return a&b?a:b;} 9 10 11 int dfs(int x, int y)12
Seraph2012 阅读(221) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2570题意：中文。mark：很水的题。体积V都一样，排序后贪心就可以了。各种wa，主要还是浓度计算那儿装逼不想用实数，就用整数绕过去，结果各种想不清楚。代码： 1 # include &stdio.h& 2 # include &stdlib.h& 3 4 5 int p[110] ; 6 7 int cmp(const void *a, const void *b) 8 { 9 return *(int*)a - *(int*)10 }11 12 13 int main
Seraph2012 阅读(144) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2569题意：中文。mark：水递推。很容易得到方程dp[i] = 2*dp[i-1]+dp[i-2]。不过dp[0] = 3。注意要用long long。代码： 1 # include &stdio.h& 2 3 4 long long dp[45] = {3,3} ; 5 6 7 int main () 8 { 9 int T, n,10 for (i = 2 ; i &= 40 ; i++)11 dp[i] = 2*dp[i-1]+dp[i-2] ;1...
Seraph2012 阅读(90) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2568题意：中文。mark：看清楚题就好了。就是求二进制表示时1的个数。本来嘛递归直接可以搞，请容我装逼一下用了位运算。。。代码： 1 # include &stdio.h& 2 3 4 int calc(int x){return x?calc(x-(x&-x))+1:0;} 5 6 7 int main () 8 { 9 int T,10 scanf (&%d&, &T) ;11 while(T--)12 {13 scanf (&%d
Seraph2012 阅读(63) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2567题意：中文。没啥好说的。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 int main () 6 { 7 int T, i, 8 char s1[55], s2[55] ; 9 scanf (&%d&, &T) ;10 while (T--)11 {12 scanf (&%s%s&, s1, s2) ;13 len = strlen(s1) ;14..
Seraph2012 阅读(77) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1800题意：士兵要学骑扫帚。每个士兵有一个level，level高的能在同一把扫帚上教level低的怎么骑。一个人最多有一个老师，一个学生。也可以没有。给n个士兵的level值，问最少需要多少扫帚。mark：显然就是找出现次数最多的数字的次数。但因为数字长度多达30个字符，因此long long都存不下，用字符串。wa了一次，忘记处理前导0。代码： 1 # include &stdio.h& 2 # include &string.h& 3 # include &stdli
Seraph2012 阅读(868) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1496题意：给a,b,c,d。计算有多少组(x1,x2,x3,x4)满足方程。mark：这其实是poj1840的Eqs简化成的问题，是一个经典的hash问题，但是poj是对内存限制严格，此题则是对时间卡的更紧，TLE了好多次。首先将等式分成两边，写成a*x1^2+b*x2^2 = - c*x3^2-d*x4^2，然后枚举其中一边的所有值存起来(hash存)，再枚举另一边求解。懒得写hash，直接开200w的数组不是不行，但是很容易TLE。千万不能用O(n)的方式清零数组，应该再执行一次存数时的枚举，原来
Seraph2012 阅读(306) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2094题意：题目说的不清楚，有很多情况都没说到。不过数据很水，只要判断入度为0的点是否只有1个就可以了。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 6 char tab[] ; 7 int degree[2010] ; 8 9 10 int find(char a[])11 {1213 for (i = 0 ; i & i++)14 i...
Seraph2012 阅读(147) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2093题意：中文。成绩排序。mark：看似复杂，其实就是个排序，考察基本功。代码： 1 # include &stdio.h& 2 # include &string.h& 3 # include &stdlib.h& 4 5 6 typedef struct NODE{ 7 char name[15] ; 8 int num, 9 }NODE ;10 11 12 NODE stu[1010] ;13 14 15 int cmp(const void *
Seraph2012 阅读(69) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2079题意：中文。。。mark：母函数。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 int dp[10][45] ; 6 7 8 int main () 9 {10 int T, n, i, j, k,11 int a,12 scanf (&%d&, &T) ;13 while (T--)14 {15 scanf (&%d%d&, &n, &
Seraph2012 阅读(83) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1075题意：在输入的字符串里找词典中的进行替换。mark：诚然，我很讨厌STL，但是这题要是不用STL的话简直太恶心了。最后非常慢。。。将近TLE。代码： 1 # include &iostream& 2 # include &string& 3 # include &map& 4 # include &stdio.h& 5 6 7
8 char s[3010] ; 9 10 11 int main ()12 {
Seraph2012 阅读(86) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1071题意：按图，给出p1,p2,p3的坐标，计算阴影部分面积。mark：就是求公式咯。设y = ax^2 + bx + c。用(x1,y1),(x2,y2)相减再联合顶点坐标(-b/2a, c-b^2/4a)可以轻易求出a，b，c的值。之后算积分就可以了。注意还要减去直线和x轴所夹梯形的面积。代码： 1 # include &stdio.h& 2 # include &math.h& 3 4 5 double fun(double a, double b, double c,
Seraph2012 阅读(140) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1677题意：俄罗斯套娃是一种有宽w和高h两种属性的玩具。当wi & wj && hi & hj的时候，套娃i能被套在套娃j里。现在给出m个套娃的宽和高，问最少能套出几个套娃。mark：首先按宽度从大到小排序，得到结果以后按高度求最长非降子序列（LIS）。这题和导弹拦截系统问题一样，是经典dp。一开始偷懒写了贪心结果TLE了。代码： 1 # include &stdio.h& 2 # include &stdlib.h& 3 # include &
Seraph2012 阅读(148) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1671题意：给堆电话号码（数字，长度不大于10），如果有一个号码是另一个号码的前缀就NO，否则YES。mark：trie树来存和查找号码，但是写的有点恶心。代码：# include &stdio.h&# include &string.h&typedef struct TRIE{ int next[10] ;} TRIE ;TRIE trie[100010] ;char tb(char ch){return ch-'0';}i
Seraph2012 阅读(251) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2192题意：n个size不同的大楼，相同size的不能放在同一MagicBuilding中。问至少要多少个MagicBuilding。mark：其实就是求出现最多的那个数出现的次数，排序以后扫一次就好了。代码：# include &stdio.h&# include &stdlib.h&int a[10010] ;int cmp(const void *a, const void *b){ return *(int*)a - *(int*)}int main (){ in
Seraph2012 阅读(59) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1492题意：丑数(humble number)是一种素因子只有2、3、5、7组成的数字。给一个丑数，问它有多少因数。mark：基础数论。因为只有2、3、5、7四种素因子，因此只要求出幂次，加1后乘起来就好了。注意要用long long。代码：# include &stdio.h&long long div(long long x, int b){ int rtn = 0 ; while (x%b==0) { x /= rtn ++ ; } ...
Seraph2012 阅读(190) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2601题意：给n，找满足i*j+i+j == n的一对(i,j)，其中0&i&=j&n。mark：两边同时+1后得到(n+1)=(i+1)*(j+1)。只要从2到sqrt(n+1)枚举i+1的值就好了。不过时间有点久，2000+ms。正规的做法应该是用数论知识分解素因子。另外要考虑n是10^10，用long long（此处wa了一次）。代码：# include &stdio.h&# include &math.h&int main (){ int T, sum,
Seraph2012 阅读(96) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1506题意：给一些连续的直方柱的高（宽是1），找一个面积最大的矩形。mark：本来是个单调队列题，但是dp好像可以解。考虑每个柱往两边找能扩展到的最远的边界，乘上自己的高可获得。往两边扩展边界的时候理论复杂度是O(n)，直接做是要TLE的。先考虑往右找边界，假设之前右边所有的直方柱的边界已经被找过，并且被记录下来，假如下一个柱的高度比自己高，则直接可以跳到下一个柱的边界继续找，不断迭代后很快就能找到边界。不知道这种迭代的方法复杂度如何证明，对于每个柱子，最坏的肯定是要找n次（递减），但是最坏的情况不可能
Seraph2012 阅读(439) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2552题意：中文。。。mark：无论输入是多少。。。输出都是1。代码：# include &stdio.h&int main (){ int T ; scanf (&%d&, &T) ; while (T--) puts(&1&) ; return 0 ;}
Seraph2012 阅读(87) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2551题意：中文，直接循环可搞。代码：# include &stdio.h&long long calc(long long x){ long long i, sum = 0 ; for (i = 1 ; ; i++) { sum += i*i* if (sum &= x) }}int main (){ int T, scanf (&%d&, &T) ; while (T--)...
Seraph2012 阅读(86) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2550题意：中文。mark：2wa，没看清题意，还要按箭身长度排序，囧。代码：# include &stdio.h&# include &stdlib.h&typedef struct NODE{ int a,}NODE ;NODE num[100] ;int cmp(const void *a, const void *b){ NODE *p = (NODE*)a, *q = (NODE*) return p-&a - q-&}void outp
Seraph2012 阅读(41) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2549题意：中文。mark：水题不解释。代码：# include &stdio.h&# include &string.h&int main (){ int T ; int a, n, char str[10] ; scanf (&%d&, &T) ; while (T--) { scanf (&%d.%s %d&, &a, str, &n) ; len = strlen(str) ; if (n <
Seraph2012 阅读(85) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2548题意：中文。mark：著名的ooxx题。。。不解释。代码：# include &stdio.h&# include &math.h&int main (){ int T ; double a, b, c, scanf (&%d&, &T) ; while (T--) { scanf (&%lf%lf%lf%lf&, &a, &b, &c, &d) ; printf (&%.3l
Seraph2012 阅读(72) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2547题意：中文。mark：其实就是求两点间距离，水。注意输入数据是实数。代码：# include &stdio.h&# include &math.h&int main (){ int T ; double a, b, c, scanf (&%d&, &T) ; while (T--) { scanf (&%lf%lf%lf%lf&, &a, &b, &c, &d) ; printf (&q
Seraph2012 阅读(116) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1722题意：中文。mark：公式，p+q-gcd(p,q)。证明不懂。。。见大牛博客。http://blog.sina.com.cn/s/blog_00soe2.html代码：# include &stdio.h&int gcd(int p, int q){return p%q?gcd(q,p%q):q;}int main (){ int p, while (~scanf (&%d%d&, &p, &q)) printf (&q
Seraph2012 阅读(87) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1323题意：某数的真因子加起来比它大叫做ABUNDANT，比它小叫做DEFICIENT，相等叫做PERFECT。输入一个数，输出它是哪种情况。直接暴。代码：# include &stdio.h&int main (){ int n, ans, puts (&PERFECTION OUTPUT&) ; while (~scanf (&%d&, &n),n) { for(i = 1,ans=0 ; i & n && a
Seraph2012 阅读(46) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1328题意：输入一个字符串，没个字符后移1位后输出。代码：# include &stdio.h&int main (){ int T, i, nCase = 1 ; char str[55] ; scanf (&%d&, &T) ; while (T--) { scanf (&%s&, str) ; for(i = 0 ; str[i] ; i++) str[i] = (str[i]-'A'+1)%26+'A'
Seraph2012 阅读(38) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1334题意：输出所有(1,200]区间上满足a^3==b^3+c^3+d^3的式子。mark：水题，枚举a、b、c，在[c,a-1]区间上二分求d后验证。n次wa，二分写得挫。代码：# include &stdio.h&# include &math.h&int sqrt3(int num,int l,int r){ int mid = 210 ; if (l*l*l&num) return 0 ; if (r*r*r&num) return 210 ; while
Seraph2012 阅读(105) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2374题意：有n个碗，标号为1到n。每个碗内有一些小珠子。每次从一个碗里拿出一个珠子，此时要往所有编号小于它的碗内各放入一颗珠子。问要拿多少次才能把所有的珠子拿完。mark：直接模拟。没注意I64d，1wa。代码：# include &stdio.h&long long num[60] ;int main (){ int i, j, while (~scanf (&%d&, &n),n) { rtn = 0 ; ...
Seraph2012 阅读(56) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1335题意：前面是一个7位a进制数，表示成后面的进制。如果超过7位则输出ERROR。直接模拟。代码：# include &stdio.h&char str[40] ;int chartonum(char ch){ if (ch &= '0' && ch &= '9') return ch-'0' ; return ch-'A'+10 ;}int gao(char str[], int b){ int
Seraph2012 阅读(42) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2370题意：一个数字可以表示成若干个fibonacci数的和。求表示成fib后“右移”1位的数字。mark：打表前30个fib数，然后用贪心法可算出任何数字的fib数表示形式，再累加。代码：# include &stdio.h&# include &string.h&int fib[35] = {1,1} ;int tab[35] ;void init(){ for (i = 2 ; i &= 30 ; i++) fib[i] = fib[i-1]+fib[
Seraph2012 阅读(40) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1342题意：从给定的集合里面选出6个数字按顺序输出。把所有的选择都输出。mark：直接dfs就好了。代码：# include &stdio.h&int num[20] ;int ans[6] ;void dfs(int idx, int n){ if (n == 6) { for(i = 0 ; i & i++) if (i == 0) printf(&%d&,ans[i]) ; else ...
Seraph2012 阅读(62) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1361题意：对于一个合法的括号序列S，可以计算出P和W的值。P的第i个值表示第i个右括号前面有多少个左括号，W的第i个值表示第i个右括号会和前面第几个左括号匹配。现在给出P的值，求W的值。mark：因为数据很小，n的长度只有20，因此可以直接模拟，由P反求出S，然后由S直接求出P。代码：# include &stdio.h&# include &string.h&char str[50] ;int p[50],w[50] ;void setstr(){ int nu
Seraph2012 阅读(82) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1715题意：算fibonacci数。mark：大数运算。第1000个fib数只有200多位，直接打表好了。代码：# include &stdio.h&int fib[] ;char str[300] ;void add(int a[], int b[], int c[]){ int *p, * int i, cc = 0 ; if(a[0]&b[0])p=a, q= else p = b, q= for(i = 1 ; i&= q[0] ...
Seraph2012 阅读(117) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1370题意：有3个循环周期，周期天数分别为23、28、33。对于某一年，已知某年这3个周期的某一峰值分别是当年的第p、e、i天，问从第d天开始到最近一个满足3个周期都达到峰值的日期还有多少天。mark：据说是剩余定理。数据比较小，直接打表可过。比较蛋疼的是wa了很多次，因为算减法以后忘记取模了。。。代码：# include &stdio.h&int tab[40][40][40] ;int _0(int num){ if (num &= 0) return num + 21252 ;
Seraph2012 阅读(136) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1379题意：输入一堆字符串，按“逆序数值”排序。如果相同，按输入顺序。mark：50个字符串，每个长度是100，算逆序数是O(n^2)，复杂度是500000，直接暴力可搞。数据比较水，排序直接用qsort不用考虑输入顺序。如果非要考虑也可以，加一个下标表示原来的序号，比较的时候多比较一下就OK了。代码：# include &stdio.h&# include &stdlib.h&typedef struct STRING{ char str[110] ; int unsorted
Seraph2012 阅读(50) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1720题意：输入十六进制的a和b，输出十进制的a+b。代码：main(a,b){while(~scanf(&%x%x&,&a,&b))printf(&%d\n&,a+b);}
Seraph2012 阅读(26) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1393题意：一个钟面只有一根分针。对于一个数字d，把中面上的分针指向的时间s往后拨s的d倍。问给定d，重复这样的操作多少次能回拨到0。若不能则输出Impossible。mark：因为钟面只有60分钟，所以最多不会超过60次，直接暴力就可。代码：# include &stdio.h&int main (){ int i, s, d, int tab[100] ; while (~scanf (&%d%d&, &s, &d) &&
Seraph2012 阅读(59) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1395题意：给出n，求满足2^x mod n = 1的最小的x。mark：数论题，其实就是求a模m的阶。打素数表敲错变量，1wa。可以水过，但是最好需要知道以下知识。1. 若gcd(a,m)==1，一定存在一个正整数d&m使得a^d == 1 mod m（欧拉定理）。2. 满足条件的最小正整数d记为ord_m(a)，叫做a模m的阶。3. 若对于一个正整数a满足(1)gcd(a,m)==1;(2)ord_m(a)==φ(m)(φ(m)表示m的欧拉函数);则a叫做m的一个原根。4. 若gcd(a,m)
Seraph2012 阅读(389) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1564题意：从一个n*n的棋盘的某个角落开始，走过的格子不能再走，每次轮流移动棋子（上下左右），最后无法移动的人输。问是否有先手必胜的策略。mark：打表后看出规律。证明不会。代码：main(n){while(scanf(&%d&,&n),n)puts(n&1?&ailyanlu&:&8600&);}打表程序：# include &stdio.h&int graph[] ;int d
Seraph2012 阅读(233) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1397题意：给一个偶数，求可以表示为多少对素数对的和。mark：最大范围是2^15 = 32768。打素数表，然后枚举。理论上会TLE，但是水过了。代码：# include &stdio.h&int IsPrime[40010] ;void init(){ int i, for (i = 0 ; i &= 40000 ; i++) IsPrime[i] = 1 ; for (i = 2 ; i &= 200 ; i++) if (IsPrime[i]) ...
Seraph2012 阅读(85) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1297题意：n个字母，由F和M组成。F不能单独存在。求满足条件的字符串数目。mark：递推很容易得到方程dp[n] = 2*dp[n-1]-dp[n-2]+dp[n-3]。但是题目中n最大是1000，结果是200多位的整数，要写成大数运算，大数减法没写过。。。方程可等价为dp[n] = dp[n-1]+dp[n-2]+dp[n-4]，这样就回避了减法的问题。代码：# include &stdio.h&# include &string.h&char ans[]
Seraph2012 阅读(108) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1113题意：给一堆单词做字典，XXXXXX结束。然后给若干个单词，输出它和字典里哪些单词由同样的字母（个数也相同）组成，有多组的话按字典序输出。XXXXXX结束。mark：题意有点绕。。。思路是先把字典里的单词排序，并且每个单词计算一个值val。这个val是把单词的字母排序以后hash得到的，范围是26^6也就是3亿多一点，可以用int来表示。这样接下来每个单词输入的时候，只要比对字典里的val，相同则可以输出。不hash的话就多存一个字母排序以后的单词也可以。代码：# include &stdi
Seraph2012 阅读(185) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1141题意：atmel公司1960年发布4bits的处理器，每10年翻一番。给一个年份，问最近一次发布的处理器能运算的n!最大的n是多少。mark：最大的处理器位数是2160年的4194304bits。要算n!的二进制表示位，直接算很难，可以变成求log2后取整加1。然后因为log2(n!) = log2(1) + log2(2)...+log2(n)，所以直接O(n)就可以了。大概算到30w可以把500wbits的算出来，之后按输入二分。代码：# include &stdio.h&# in
Seraph2012 阅读(79) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1212题意：求一个数（大数）对另一个数（小数）的模。mark：大数除法求模，简单。代码：# include &stdio.h&char str[1010] ;int calc(){ int i, cc = 0 ; for (i = 0 ; str[i] ; i++) { cc = cc * 10 + str[i] - '0' ; cc %= }}int main (){ while (~scan...
Seraph2012 阅读(55) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1702题意：告诉你FIFO或FILO（先进先出、先进后出），然后对每次操作进行模拟，输出结果。mark：栈和队列的模拟。。。代码：# include &stdio.h&int dp[1010] ;void Queue(){ int front = 0, rear = 0, char str[20] ; while (n--) { gets (str) ; if (str[0] == 'I'){ sscan...
Seraph2012 阅读(80) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2059题意：中文。mark：题意有点绕。关键是算出乌龟的最短到达时间。方法就是dp了，每个站到达的最短时间是之前所有站直接转移过来的时间里最少的那个。1wa，错在double和int的转换上。。。2b了。代码：# include &stdio.h&int p[110] ;double dp[110] ;int n, vt1, vt2, c, t, L ;double min(double a, double b){return a&b?a:b;}double w(double s, d
Seraph2012 阅读(319) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2175题意：中文。mark：递归算一下就可以了。n个盘子前2^(n-1)-1次是移动n-1个盘子的操作，第2^(n-1)是移动最大那个盘子，后面又是n-1个盘子的操作。代码：# include &stdio.h&long long dfs(long long n, long long m){ long long mid = (1LL&&(n-1)) ; if (m == mid) if (m & mid) return dfs(n-1,m) ; ret
Seraph2012 阅读(36) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2137题意：把一个字符串（奇数个字符）按中间字符为轴逆时针旋转n次后，输出。mark：2WA，n居然可以为负。。。代码：# include &stdio.h&# include &string.h&void out0(char str[], int len){puts (str) ;}void out1(char str[], int len){ int i, for (i = len-1 ; i &=0 ; i--) { for (j = 0 ; j & i
Seraph2012 阅读(67) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2136题意：问一个数n最大的素因子是第几个素数。mark：之前一直TLE。素数表不打好会TLE，分解素因子的时候不加sqrt优化也会TLE。。。先打好100w的素数表，把素数的位序标记好，然后从1到sqrt(n)分解n，得到n最大的素因子后，再看是第几个。代码：# include &stdio.h&# include &math.h&int IsPrime[1000010] ;int Primes[1000010] ;int cnt = 0 ;void init(){ int i
Seraph2012 阅读(174) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2065题意：中文。mark：很多人说是指数型母函数，的确指数型母函数可秒，但是出题者的意图更可能是考察递推+矩阵乘法。按状态,长度为n的时候：D[1,n]表示偶数个A、偶数个C的情况数，D[2,n]表示偶数个A、奇数个C的情况数，D[3,n]表示奇数个A、偶数个C的情况数，D[4,n]表示奇数个A、奇数个C的情况数。有长度为n的时候情况可由长度为n-1的情况推来：(D[1,n],D[2,n],D[3,n],D[4,n])*M=(D[1,n+1],D[2,n+1],D[3,n+1],D[4,n+1])。其
Seraph2012 阅读(373) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2133题意：输入一个日期，输出不合法(illegal)或星期几。mark：直接计算该日期和0年1月1日(周六)天数差，然后模7就好，注意闰年还有合法性判断要包括0月和0日的情况。代码：# include &stdio.h&int mon[2][13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31, 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31} ...
Seraph2012 阅读(171) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1254题意：中文。mark：BFS+DFS。用BFS来展开箱子的位置和小人的位置，每个节点有2个属性，1是箱子所在位置的坐标，二是一个hash值来表示小人能位于箱子上下左右四个地方的情况（每个方向能否到达用1位来表示，共需要用15）。计算hash值的时候用DFS来穷举小人所有能到达的位置。wa了1次，DFS的时候忘记考虑小人不能穿过箱子的情况。代码：# include &stdio.h&# include &string.h&int graph[10][10] ;int n, m
Seraph2012 阅读(77) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1728题意：中文。mark：我真是弱爆了。总体思路就是BFS，只不过不是用步数来限制，而是用转弯次数。注意坐标是先纵后横。。。先拍了个DFS，理所当然地TLE了。然后拍了个BFS，其实没想清楚就拍了，结果还TLE。想了半天，BFS没理由TLE啊。然后放了2天，今天想清楚了很多细节，又拍了一个BFS，又TLE了。后来发现是加点至队列的时候，如果一个方向上的某点之前已经访问过，则不加入队列这里，直接写了continue，忘记让x和y坐标变到下一个点去了。。。代码：# include &stdio.h&
Seraph2012 阅读(363) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1180题意：中文。mark：题目没说明楼梯改变情况。sample中的路径应该是先向上走，再向右走，通过楼梯后走到头再向上，这里wa了1次。bfs+优先队列。优先队列用手写堆实现。数据规模很小。代码：# include &stdio.h&# include &string.h&char graph[25][25] ;int dr[4][2] = {0,1,0,-1,1,0,-1,0} ;int sx, sy, ex,int vis[25][25] ;int q[25*25
Seraph2012 阅读(146) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1026题意：n*m迷宫，求从(0,0)到(n-1,m-1)的最少时间。'X'是墙，'.'是空地，'1'-'9'表示有怪物，消灭之需要数字对应的时间。mark：最近一直在写搜索题。搜索题有的很费劲，但是写多也就觉得嗯，就那么回事。这题也没啥可说的，直接BFS。和最简单的BFS不同的是，判断一个过去到过的点是否可走，需要多开一个数组来记录，然后判断过去到达的时间和现在到达的时间的大小。（其实最好的方法是优先队列么。。。懒得写而已。）然后因为要求
Seraph2012 阅读(815) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1418题意：中文。mark：1wa。虽然n、m都是整形范围，但是加起来可能会超过，因此要用long long。不存在m & 2的情况。代码：# include &stdio.h&int main (){ long long n, while (~scanf (&%I64d%I64d&, &n, &m) && (n||m)) printf (&%I64d\n&, n+m-2) ; return 0 ;}
Seraph2012 阅读(41) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1562题意：求最小的[]区间内的数x满足x%a==0 && (x+1)%b==0 && (x+2)%c==0。mark：应该是用剩余定理的，不过数据那么小，直接爆了。代码：# include &stdio.h&int main (){ int T, a, b, c, scanf (&%d&, &T) ; while (T--) { scanf (&%d%d%d&, &a, &am
Seraph2012 阅读(36) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1999题意：中文。mark：打表到100w。。。（上限是试出来的。。。）代码：# include &stdio.h&int sum[1000010] ;int dp[1010] ;void init(){ int i, for (i = 1 ; i &= 500000 ; i++) for (j = 2* j &= 1000000 ; j+= i) sum[j] += for (i = 2 ; i &= 1000000 ; i+...
Seraph2012 阅读(67) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1088题意：写一个html代码显示的程序。。。mark：就是麻烦，没别的。各种PE。后来发现是只考虑了' '和'\n'，忘记考虑'\t'。。。代码：# include &stdio.h&int main (){ int ch, cnt = 0, cc = 0 ; int flag = 0, end = 1 ; char buff[100] ;// freopen (&in.txt&, &r"
Seraph2012 阅读(62) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2068题意：中文。mark：如果知道错排公式就很简单了。wa了一次。。。&=写成了&。。。PE一次。莫名其妙多加了个空格。sb了。代码：# include &stdio.h&long long c[30][30] = {1} ;long long cp[15] = {0, 0, 1} ;void init(){ int i, for (i = 1 ; i &= 25 ; i++) { c[i][0] = 1 ; for (j = 1 ; j &= i...
Seraph2012 阅读(86) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1420题意：求a^b mod c。mark：快速幂无疑是最简单的写法。不过c只有100w，也可以用数论的方法做。此处用的是快速幂。代码：# include &stdio.h&int qpow(long long a, long long b){ long long ans = 1, buff = while (b) { if (b&1) ans = (ans*buff) % b &&= 1 ; buff =...
Seraph2012 阅读(53) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1072题意：I想（从2处）逃出迷宫（3处），0是墙，1是空地。身上有定时炸弹，在第6s爆炸（只能走5步）。4处是将定时炸弹重设的工具。问它最快能否逃出迷宫。mark：bfs。多添加一个数组标记上次到达当前位置时定时炸弹的剩余秒数。代码：# include &stdio.h&# include &string.h&int n,int graph[10][10] ;int step[10][10] ;int times[10][10] ;int sx, sy, ex, ey
Seraph2012 阅读(52) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1593题意：中文。mark：1wa。直接往开始的反方向按半径逃不可以。找一个同心圆，让V1的角速度略大V2。在那个圈上0086可以甩对方一个直径后再往岸边划。代码：# include &stdio.h&# include &math.h&# define Pi acos(-1)int main (){ int R, V1, V2 ; double t1, t2 ; while (~scanf (&%d%d%d&, &R, &V1, &V
Seraph2012 阅读(53) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1231题意：中文。最大连续子川和。经典dp（不知道算不算dp）。代码：# include &stdio.h&int a[10010] ;int n, s, e, max_void find(){ int i, ss = s, ee = e, sum = max_ for (i = 1 ; i & i++) { if (sum & 0) ss = ee = sum = a[i] ; else { ...
Seraph2012 阅读(45) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1898题意：S和X比做题。他们的做题顺序是一样的，但并不是做一题交一题。S每A分钟交一次，X每B分钟交一次。问T分钟的时候是谁交的题多。mark：水。假设每分钟做1题，求出两人各自交了多少题后比较。。。代码：# include &stdio.h&int main (){ int T ; int a, b, t, aa, scanf (&%d&, &T) ; while (T--) { scanf (&%d%d%d&, &a,
Seraph2012 阅读(48) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1718题意：问给定学号在所有成绩里的排名。。。mark：无聊题。1wa，多组输入。。。代码：# include &stdio.h&int a[1100], b[1100] ;int main (){ int i, aa, ans, cnt = 0 ; while (~scanf (&%d&, &aa)) { cnt = 0 ; while (~scanf (&%d%d&, &a[cnt], &b[cnt])) { if (...
Seraph2012 阅读(35) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1286题意：中文。mark：看似很绕其实就是求欧拉函数Phi(n)。对于所有n的素因子Pi，欧拉函数Phi(n) = n * (P1-1)/P1 * (P2-1)/P2 * (P3-1)/P3 ...。对于每一个Pi，因为n总是Pi的倍数，所以可以先除再乘，不会溢出。代码：# include &stdio.h&int Primes[40000] = {2, 3} ;int PrimeNum = 2 ;int dp[40000] ;int calc(int nn){ int ans = nn,
Seraph2012 阅读(52) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1563题意：找n个数里只出现了1次的数。mark：hash搞之。大于200的最小素数是211。代码：# include &stdio.h&# include &string.h&int dp[211][2] ;void insert (int n){ int idx = n % 211 ; while (dp[idx][0] != n && dp[idx][1] != 0) idx++ ; dp[idx][0] = dp[idx][1] ++ ;}int
Seraph2012 阅读(58) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1491题意：给一个2006年的日期，问和日还差几天。mark：getdays是用于获得m月d日是当年的第几天。最后和10月21日做比较。代码：# include &stdio.h&int getdays (int m, int d){ int i, rtn = 0, month [12] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30} ; for (i = 0 ; i & i++) rtn += m...
Seraph2012 阅读(27) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1253题意：中文。。。mark：三维BFS水过。其实和二维没多大区别。代码：# include &stdio.h&# include &string.h&# define REP(i,a) for(i = 0 ; i & i++)int q[55*55*55][3] ;int graph[55][55][55] ;int step[55][55][55] ;int a, b, c,int tab[6][3] = {{0, 0, 1}, {0, 0, -1},
Seraph2012 阅读(123) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1577题意：中文。mark：gcd是否为1。注意不能有除数为0。代码：# include &stdio.h&int abs(int n){return n&0?-n:n;}int gcd(int a, int b){return a%b==0?b:gcd(b,a%b);}int main (){ int l, px, py, sx, while (~scanf (&%d&, &l), l) { scanf (&%d%d%d%d&
Seraph2012 阅读(83) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1708题意：给两个字符串s0和s1，sn是sn-1和sn-2拼接而成的。问sn中每个字母出现的次数。mark：直接递推就可以了。注意0的情况。代码：# include &stdio.h&# include &stdlib.h&# include &string.h&int t1[30], t2[30], t3[30] ;void output (int t[]){ for (i = 0 ; i & 26 ; i++) printf (&
Seraph2012 阅读(78) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2309题意：给n个数，去掉一个最大的和一个最小的，然后求平均数。蛋疼的日式英文。代码：# include &stdio.h&int main (){ int n, max_n, min_n, num, while (~scanf (&%d&, &n), n) { sum = 0 ; min_n = 1100, max_n = -1 ; for (i = 0 ; i & i++) { ...
Seraph2012 阅读(45) |
19:55:02地址：http://acm.hdu.edu.cn/showproblem.php?pid=2401题意：有1-N一共N个篮子，每个里面有很多金币。每个金币的重量是w，但是其中有一个篮子金币的重量只有w-d。现在从第一个篮子拿1个金币，第二个拿2个。。。第n-1个篮子拿n-1个。第n个不拿。把拿出来的金币称重。问金币轻的篮子编号是多少。mark：不知道第二组sample为什么可以是10。。。诡异。代码：# include &stdio.h&int main (){ int n, w, d, rst, while (~scanf (&q
Seraph2012 阅读(71) |
17:22:53地址：http://acm.hdu.edu.cn/showproblem.php?pid=2529题意：中文。mark：设v的水平分量为x，则最终距离和x的关系应该是先增后减，遂三分。。。代码：# include &stdio.h&# include &math.h&double l,double f(double x){ return sqrt(v*v-x*x)*l/x - 0.5*9.8*l*l/(x*x) ;}int main (){ double left, right, m1, m2, while (~sc
Seraph2012 阅读(56) |
04:07:41地址：http://acm.hdu.edu.cn/showproblem.php?pid=2516题意：中文。mark：完全不会。看了网上说打表看出规律似乎是Fibonacci。遂写代码。wa了一次，因为[0...43]的数量我用二分的时候居然算成了43个。。。应该是44个的。代码：# include &stdio.h&# include &stdlib.h&int dp[50] = {2, 3} ;int cmp(const void *a, const void *b){ return *(int*)a - *(int*)
Seraph2012 阅读(43) |
20:47:45地址：http://acm.hdu.edu.cn/showproblem.php?pid=2512题意：中文。。。mark：递推。dp[i][j]表示i张卡片分在j本书的种类数，有dp[i][j] = dp[i-1][j-1] + dp[i-1][j]*j。代码：# include &stdio.h&# define MOD 1000int dp[] ;int ans[2010] = {0, 1} ;int main (){ int T, int i, dp[1][1] = 1 ; for (i ...
Seraph2012 阅读(26) |
19:37:25地址：http://acm.hdu.edu.cn/showproblem.php?pid=2539题意：中文。有点点麻烦的模拟。代码：# include &stdio.h&# include &string.h&char str[110] ;int goal[20] ;int judge (char s[]){ int len = strlen(s) ; if (len & 10) return 1 ; if (s[len-8] == ' ' && s[len-7] == 'n'
Seraph2012 阅读(38) |
20:09:16地址：http://acm.hdu.edu.cn/showproblem.php?pid=2511题意：中文。mark：递归。代码：# include &stdio.h&void gao(long long n, long long time, int s, int e){ int m = 6-s- long long mid = (1LL&&(n-1)) ; if (time == mid) { printf (&%I64d %d %d\n&, n, s, e) ; } ...
Seraph2012 阅读(62) |
19:19:52地址：http://acm.hdu.edu.cn/showproblem.php?pid=2565题意：中文，模拟。代码：# include &stdio.h&# include &string.h&char graph[100] ;void output (int n){ memset (graph, ' ', sizeof (graph)) ; for (i = 0 ; i & i++) { memset(graph, ' ', sizeof(graph)) ; gr
Seraph2012 阅读(39) |
19:02:16地址：http://acm.hdu.edu.cn/showproblem.php?pid=2561题意：中文。mark：可以排序，不过也可以扫一遍。用a记录最小值，b记录次小值，更新。代码：# include &stdio.h&int main (){ int T, a, b, i, n, scanf (&%d&, &T) ; while (T--) { scanf (&%d&, &n) ; a = b = 1000 ; for (i = 0 ; i & i++)
Seraph2012 阅读(29) |
19:13:38地址：http://acm.hdu.edu.cn/showproblem.php?pid=2566题意：中文。。。mark：题目没给数据范围，实在蛋疼，水了一下。考虑到如果有n个硬币，全都是1或2，能组成[n,2n]区间内任何一个数。所以枚举面额为5的硬币个数，然后计算剩下的面额是否在剩下的1、2硬币组成的面额区间内。15ms。那个dp[]数组没用，一开始看错题了。代码：# include &stdio.h&int dp[] = {1, 1, 2, 3, 5, 9} ;int main (){ int T, i, n, m, nn, mm, a
Seraph2012 阅读(132) |
18:58:25地址：http://acm.hdu.edu.cn/showproblem.php?pid=2562题意：中文。有点不明确，其实就是第0个和第1个互换，第二个和第三个互换。。。代码：# include &stdio.h&char str[100] ;int main (){ int T, scanf (&%d&, &T) ; while (T--) { scanf (&%s%*c&, str) ; for (i = 0 ; str[i] ; i+=2) printf (&%c%..
Seraph2012 阅读(33) |
18:53:55地址：http://acm.hdu.edu.cn/showproblem.php?pid=2564题意：中文。。。没啥好说的，处理就行了。代码：# include &stdio.h&char str[1000] ;void output(char str[]){ for(i = 0 ; str[i] ; i++) { if ((i == 0 || str[i-1] == ' ') && str[i] != ' ') putchar (str[i] & 0xDF) ; }}i
Seraph2012 阅读(37) |
18:44:21地址：http://acm.hdu.edu.cn/showproblem.php?pid=1548题意：有一个奇怪的电梯，只有2个按钮，上和下。第i楼层有一个值Ki。假设在第i层，按上它会向上走Ki层，按下也一样。如果超过n层或少于1层，则原地不动。问从第a层到b层需要几次操作。mark：BFS之。代码：# include &stdio.h&# include &string.h&int aa, bb,int k[210] ;int q[210] ;int step[210] ;void bfs(){ int a, fron
Seraph2012 阅读(48) |
18:20:59地址：http://acm.hdu.edu.cn/showproblem.php?pid=2102题意：中文。。。mark：你大爷的WA+TLE一共11次才AC。做了至少8个小时。一开始以为是要在严格的T时刻到达才可以，考虑了不可回头和可回头两种情况，dfs之，TLE。。。然后加奇偶剪，还是TLE。之后搜了搜，发现时T时刻以内到都可以，然后拍了个BFS。WA。WA了n次以后才发现时空传送是一定要传送的，不是自己选可以传也可以不传的。然后还WA，想是不是真的要在T时刻才能过，然后加了奇偶剪枝（因为回头路的话可以无限延长时间），还WA。最后发现一个trick是
Seraph2012 阅读(70) |
10:46:23地址：http://acm.hdu.edu.cn/showproblem.php?pid=1240题意：给n*n*n的三维迷宫，求从起点到终点的最短步数。mark：bfs搞之。注意起点和终点也可以是'X'的情况。代码：# include &stdio.h&# include &string.h&char graph[15][15][15] ;int step[15][15][15] ;int q[1010][3] ;int tab[6][3] = { {-1, 0, 0}, {1, 0, 0}, {0, -1,...
Seraph2012 阅读(47) |
10:01:00地址：http://acm.hdu.edu.cn/showproblem.php?pid=1238题意：给n个字符串，要求找字符串符合该串是所有给出的字符串或给出字符串的反串的子串的。求最大长度。mark：先在输入的时候顺便存储所有串的反串，然后枚举第一个串的所有子串，最后kmp比较。代码：# include &stdio.h&# include &string.h&char ss[110][110] ;char sr[110] ;int next[110] = {-1} ;void getnext(char str[
Seraph2012 阅读(88) |
01:58:02地址：http://acm.hdu.edu.cn/showproblem.php?pid=1239题意：给m、a、b。求一对素数p,q(p&q)使得p*q&=m且p/q &= a/b。若有多对，输出p*q最大的一对。mark：刚开题看了半天，才看明白啥意思。看到m是10w，然后case是2000组，一下懵了，以为不能枚举。后来冷静分析下，其实可以。以下是几个比较重要的结论&分析。1）若m' = p*q，则必不存在另外一对素数p'，q'使得m' = p' * q'。2) 若p固定，q要
Seraph2012 阅读(82) |
19:52:14地址：http://acm.hdu.edu.cn/showproblem.php?pid=2141题意：给一串ai、bj、ck，一串x，问x是否能表示成ai+bj+ck。mark：不会，搜了一下。把ai+bj存起来。然后二分x-ck。。。复杂度应该是O(500*500 + lg(0)好极限。代码：# include &stdio.h&# include &stdlib.h&int a[510], b[510], c[510] ;int ab[510*510] ;int cmp(const void *a, con
Seraph2012 阅读(42) |
19:16:59地址：http://acm.hdu.edu.cn/showproblem.php?pid=2563题意：中文。递推。代码：# include &stdio.h&int dp[25][2] = {1, 0} ;int main (){ int i, for (i = 1 ; i &= 20 ; i++) { dp[i][0] = dp[i-1][0] + dp[i-1][1] ; dp[i][1] = dp[i][0] + dp[i-1][0] ; } scanf (&%d&, &n) ; ...
Seraph2012 阅读(58) |
18:25:02地址：http://acm.hdu.edu.cn/showproblem.php?pid=1597题意：中文。。。mark：要用long long。代码：# include &stdio.h&# include &math.h&int main (){ long long n, scanf (&%I64d&, &n) ; while (~scanf (&%I64d&, &n)) { a = (sqrt(1.0+8.0*n)-1) / 2 ; if (a*(a+1)/2
Seraph2012 阅读(110) |
17:35:04地址：http://acm.hdu.edu.cn/showproblem.php?pid=1799题意：中文。mark：其实就是组合数。。。因为m重循环就是在n个数字里选n个作为变量。。。代码：# include &stdio.h&int dp[] ;void init(){ int i, dp[0][0] = 1 ; for (i = 1 ; i &= 2000 ; i++) { dp[i][0] = 1 ; for (j = 1 ; j &= j++) ...
Seraph2012 阅读(119) |
16:59:50地址：http://acm.hdu.edu.cn/showproblem.php?pid=2078题意：中文，不说了。其实和m没关系。代码：# include &stdio.h&int main (){ int T, i, n, m, a, scanf (&%d&, &T) ; while (T--) { scanf (&%d%d&, &n, &m) ; min = 100 ; for (i = 0 ; i &i++) { scanf ...
Seraph2012 阅读(29) |
16:33:11地址：http://acm.hdu.edu.cn/showproblem.php?pid=2089题意：中文。。。mark：直接打表可过。代码：# include &stdio.h&int dp[1000010] ;int test (int num){ while (num) { if (num % 10 == 4 || num % 100 == 62) return 0 ; num /= 10 ; } return 1 ;}int main (){ int n, m, i ...
Seraph2012 阅读(80) |
16:20:20地址：http://acm.hdu.edu.cn/showproblem.php?pid=2152题意：中文。mark：dp搞起。代码：# include &stdio.h&# include &string.h&int dp[110][110] ;int main (){ int n, m, a, b, i, j, while (~scanf (&%d%d&, &n, &m)) { memset (dp, 0, sizeof(dp)) ; dp[0][0] = 1 ; for (i =
Seraph2012 阅读(28) |
02:41:06地址：http://acm.hdu.edu.cn/showproblem.php?pid=2203题意：中文，字符串比较。mark：把第一个串复制一次接在自己后面。然后字符串比较。据说数据很水？！我就暴了一下，结果TLE。。。好吧，刚学了KMP，用上试试，果断0ms，威力果然不小，开心。代码：# include &stdio.h&# include &string.h&char s1[200010], s2[100010] ;char buff[100010] ;int next[100010] = {-1} ;void getne
Seraph2012 阅读(70) |
23:20:50地址：http://acm.hdu.edu.cn/showproblem.php?pid=2304题意：说墙上一开始有一个插座。给n个接线板，每个有若干个可以用的插口，问能获得多少个插口。代码：# include &stdio.h&int main (){ int T, n, o, scanf (&%d&, &T) ; while (T--) { scanf (&%d&, &n) ; ans = 1 ; while (n--) { scanf ...
Seraph2012 阅读(62) |
23:07:25地址：http://acm.hdu.edu.cn/showproblem.php?pid=2317题意：给出不放广告的收入，放广告的收入和广告的花费，问结果。代码：# include &stdio.h&int main (){ int a, b, scanf (&%d&, &n) ; while (n--) { scanf (&%d%d%d&, &a, &b, &c); if (b-c & a) puts (&advertise&qu
Seraph2012 阅读(54) |
13:51:00地址：http://acm.hdu.edu.cn/showproblem.php?pid=2554题意：中文，有点绕但是能看懂，不多说了。mark：着实不会，看了网上的规律觉得好扯淡。n%4的余数是3或0的就是Y，否则是N。。。不知道怎么来的，打表也只能看到前12项，之后就非常慢了。代码（C编译）：main(n){while(scanf(&%d&,&n),n){puts((n+1)&2?&N&:&Y&);}}打表的程序也贴一下吧：# include &stdio.h&
Seraph2012 阅读(97) |
22:32:38地址：http://acm.hdu.edu.cn/showproblem.php?pid=2555题意：中文。不多解释。mark：此题真是坑爹。数据里有多个矩形覆盖一个点的情况- -。。。如果有这种情况，就算前一个矩形的周长。。。另外，在矩形边上也算是包含在陷阱内。代码：# include &stdio.h&# include &string.h&# include &stdlib.h&typedef struct point{ int x,}point pt[20010] ;int a[110][
Seraph2012 阅读(72) |
09:55:00地址：http://acm.hdu.edu.cn/showproblem.php?pid=2560题意：给n*m的0-1矩阵，问有多少个1。。。mark：这么水的题好爽！代码：# include &stdio.h&int main (){ int T, n, m, i, num, scanf (&%d&, &T) ; while (T--) { scanf (&%d%d&, &n, &m) ; sum = 0 ; for (i = 0 ; i & n* i+
Seraph2012 阅读(38) |
09:47:29地址：http://acm.hdu.edu.cn/showproblem.php?pid=1907题意：n堆石子，每次取走其中一堆的任意颗，最后一个取的人败，求判局势。mark：anti-nim，开始以为很简单，其实很难分析，搞了好久。具体可以参见2009年国家集训队贾志豪的论文。这里先给出anti-nim的结论：先手必胜当且仅当：1)sg值为0且不存在一堆sg值大于1；2)sg不为0且存在至少一堆sg值大于1。代码：# include &stdio.h&int main (){ int T, n, num, sg, scanf
Seraph2012 阅读(37) |
16:18:37地址：http://acm.hdu.edu.cn/showproblem.php?pid=2553题意：求n皇后放置的种类数。mark：因为n才10，所以直接dfs。代码：# include &stdio.h&int n, dp[11] = {0, 1} ;int ans, num[11] ;int col[11], diag[30], indiag[100] ;void dfs(int pos){ int i, if (pos == n) { ans ++ ; } for...
Seraph2012 阅读(41) |
16:40:47地址：http://acm.hdu.edu.cn/showproblem.php?pid=2082题意：中文。mark：YY了一个dp。dp[i][j]表示前i个字符组成价值为j的种类数，有dp[i][j] = dp[i-1][j-k*i]，k∈[0,a[i]]。a[i]是第i个字符的最大个数。最后把dp[26]的所有值（0除外）加起来就ok了。代码：# include &stdio.h&# include &string.h&int dp[30][60] ;int a[30] ;int main (){ int T, i, j,
Seraph2012 阅读(23) |
15:46:58地址：http://acm.hdu.edu.cn/showproblem.php?pid=1326题意：n个高矮不等的堆。每次可以从一个堆拿一块移动到另一堆。问最少移动多少次能使他们全都相等。mark：好经典的题目，不记得在哪儿看到过不只1次了。每个和平均数的差加起来除以二。代码：# include &stdio.h&int num[60] ;int abs(int n){return n&0?-n:n;}int main (){ int i, sum ,ans, nCase = 1 ; while (~scanf (&qu
Seraph2012 阅读(70) |
16:05:53地址：http://acm.hdu.edu.cn/showproblem.php?pid=1329题意：有n个棍子，依序从1开始放小球，两个相邻的球编号和必须是完全平方数。求最后一个能放下的序号。mark：最多才1300，直接模拟。代码：# include &stdio.h&# include &string.h&# include &math.h&int dp[55] ;int issquare(int a){ int b = sqrt(1.0*a) ; return b*b ==}int gao
Seraph2012 阅读(90) |
15:02:12地址：http://acm.hdu.edu.cn/showproblem.php?pid=1267题意：中文。刚开始没看懂，注意“总”字。代码：# include &stdio.h&long long dp[21][21] ;int main (){ int i, j, m, for (i = 0 ; i &= 20 ; i++) dp[0][i] = 1 ; for (i = 1 ; i &= 20 ; i++) for (j = j &= 20 ; j++) dp[i]...
Seraph2012 阅读(54) |
15:16:26地址：http://acm.hdu.edu.cn/showproblem.php?pid=1287题意：这题的题意很让人莫名。其实是说存在一个大写字母x，然后让原文（都是大写字母）和x做xor后得到密文。现在给密文求原文。因为x不知道，所以枚举x。判断方法是判断是否解密出来的原文都在'A'-'Z'范围内。代码：# include &stdio.h&int num[10010] ;int test (int x){ for (i = 0 ; i & i++) if ((n
Seraph2012 阅读(104) |
14:25:01地址：http://acm.hdu.edu.cn/showproblem.php?pid=1220题意：一个n*n*n的立方体，被切割成1*1*1的小块。两两配对，问两块公共点不超过2的对数。mark：先算出总对数，减去共面的对数。顶点8个，每个共面3对，棱12条，每条有n-2个方块，每个方块共面4对，非顶点非楞的面上小方块，每个共面5对，一共6个面，每个面有(n-2)^2个这样的小方块。剩下的内部小方块每个共面6对。最后总共面数要除以2，因为每对算了2次。代码：# include &stdio.h&int calc (int n){ int
Seraph2012 阅读(116) |
13:44:49地址：http://acm.hdu.edu.cn/showproblem.php?pid=1862题意：中文，排序。代码：# include &stdio.h&# include &stdlib.h&# include &string.h&typedef struct student{ char num[7] ; char name[9] ;}student stu[100010] ;int cmp1(const void *a, const void *b){ student
Seraph2012 阅读(38) |
14:03:37地址：http://acm.hdu.edu.cn/showproblem.php?pid=1165题意：模拟图中给出的函数计算。mark：直接记忆化肯定会爆栈。写几行就发现，m=0,1,2的规律了。m=3的时候直接爆。代码：# include &stdio.h&int mem[25] = {5, 13} ;int A(int m, int n){ if (m == 0) return n+1 ; if (m == 1) return n+2 ; if (m == 2) return n*2+3 ; if (mem[n] != 0) ...
Seraph2012 阅读(25) |
13:30:48地址：http://acm.hdu.edu.cn/showproblem.php?pid=1015题意：在给定字符集中选5个字符(v,w,x,y,z)使得满足v - w^2 + x^3 - y^4 + z^5 = target。输出字典序最大的一个。mark：dfs。1WA。一开始以为是字符集中序数}
发布一些HDOJ的做题情况以及代码。
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2725题意：给一个字符串表示一条河。'.'表示水，其它字符表示障碍。人在岸上用石子打水漂，每次可以选择一个击中的距离和跳跃间隔。石子多次跳跃后击中障碍物或越过河则结束。每种打水漂的方案按跳跃次数（大者优）、最...
Seraph2012 阅读(103) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1394题意：给n个数字（0到n-1无重复），可以拿前面任意m个放到末尾。求拿多少个数字放到末尾后数列的逆序数最小。mark：非常经典的一个题目，来自zoj月赛。先用线段树/点树/树状数组/合并排序求出原数列的逆序数，然后递推出所有情况的逆序数取最小。这题真的是非常经典，所以4种方法我都写了一次。代码：线段树（62ms、284k、991B）： 1 # include 2 # include 3 4 5 # define m ((l+r)&&1) 6 # define lson l,m,p m)
Seraph2012 阅读(635) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1754题意：给n个数字。m次操作，每次操作更新一个数字或者查询区间最大值。mark：典型线段树题。不过a的时候学了一下树状数组求区间最值。感觉对树状数组的理解又深刻了一点。不过这个更新不是O(lgn)而是O(lgn*lgn)的，比线段树慢！代码：线段树： 1 # include 2 # include 3 4 5 #define max(a,b) (a&b?a:b) 6 7 int tr[200010 m) return q(a, b, m+1, r, rt*2+1) ;29 ..
Seraph2012 阅读(191) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1166题意：给n个数字。对这n个数字有3种操作：1. add 2.sub 3.query。分别对应把某数增加或减少一个值和查询某[l,r]区间内所有值的和。mark：最基本的线段树or树状数组的应用。话说树状数组真是简洁啊！代码：线段树 1 # include 2 # include 3 4 5 int n, tr[50010 m) return query (a, b, m+1, r, rt*2+1) ;25 return query(a, m, l, m, rt*2) + query...
Seraph2012 阅读(49) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2723题意：为了对一个文件进行访问控制，会给每个文件建立一个访问控制列表（ACL），每个列表里有若干个entity（类似于用户组），每个entity有若干个right（权限）。给出一个文件的权限更改日志，日志是ExR形式的短语构成，E是这次操作影响的entity（多个），R是right，x是一个操作符，可以为+、-、=。为+的时候表示把权限加到entity上，为-的时候表示从entity减去相应权限，为=的时候表示把entity设为相应权限。最后输出每个entity对应的权限，没有权限的不输出，2个相邻
Seraph2012 阅读(166) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2721题意：给出a、b、c、s。s是初值，每次变化有s = (a*s+b)%c。如此直到重复。这些数都写成16比特的，如果某位在所有数都是0则输出0，是1则输出1，如果都有可能输出问号。直接暴搞就可以。。。代码： 1 # include 2 # include 3 4 5 int vis[70000] ; 6 7 8 int main () 9 {10 int a, b, c, s, i,11 char ch[20] ;12 13 while (~...
Seraph2012 阅读(66) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2719题意：给一些字符串，把字符串输出。如果有题目里的那7种字符，按%数值的形式输出。代码： 1 # include 2 # include 3 4 5 char str[100] ; 6 char t[] = & !$%()*& ; 7 int p[] = {0x20, 0x21, 0x24, 0x25, 0x28, 0x29, 0x2a} ; 8 9 10 int main ()11 {12 int i,13 while (gets (str))14 {15...
Seraph2012 阅读(41) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1527题意：中文。mark：经典博弈，传说中的Wythoff’s Game。论文在此：http://scimath.unl.edu/MIM/files/MATExamFiles/Cotton_MATpaper_Final_EDITED.pdf值得一提的是论文里提到的神奇的贝蒂定理（Beatty Theorem）：若a和b都是无理数且1/a + 1/b == 1，则{[a],[2a],[3a]...}和{[b],[2b],[3b]...}这两个集合没有相同元素且他们的并组成正整数集。（[x]表示对x下取整
Seraph2012 阅读(119) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1260题意：有个人卖票。从8:00:00am开始卖。后面有n个人，每个人卖票需要ki的时间，但是相邻两个人可以合起来买，需要di的时间。问卖票人最早回家的时间。mark：一个水dp加一个时间的转换。本来可以1A的但是3wa。第一次错是因为小时数忘记处理成不大于12的数字，第二次错是因为把m%=60写成了h%=60，第三次是忘记删除调试语句。都是脑残错误。。。代码： 1 # include 2 3 4 int s[2010], d[2010], dp[2010] ; 5 6 7 int min(...
Seraph2012 阅读(222) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2603题意：从高度为3米距离天花板0.5米处抛掷一物体，倾角为a，质量为m，初速度为v。若碰到天花板则以反射定律反射出去。问物体能抛多远。mark：推公式解的物理数学题。只要还记得S = vt + 0.5gt^2的自由落体公式，根据其求出总飞行时间，剩下的都很好解决。注意解方程的时候考虑若有2个解，取哪一个。代码： 1 # include 2 # include 3 4 5 double pi = acos(-1.0), g = 9.87 ; 6 7 8 int main () 9 {10 ...
Seraph2012 阅读(80) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2602题意：骨头收集者在收集骨头。有容量为V的袋子，n个骨头，给出每个骨头的体积和价值。问最大能收集的价值。01背包。代码： 1 # include 2 # include 3 4 5 int dp[1010] ; 6 int max(int a, int b){return a&b?a:b;} 7 int val[1010], vol[1010] ; 8 9 10 void work()11 {12 int n, v, i, j, ans = 0 ;13 scanf (&%d...
Seraph2012 阅读(463) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2600题意：给一个区间p和q表示年份。给n个战争的起始年份、终止年份和战争名字（其实无用）。问[p,q]区间内最大没有战争的年份是多少。mark：600w*2的区间*100个战争如果直接开bool数组实在是很勉强。可以把战争先按起始年份再按终止年份排序，for一遍，维护一个last变量表示已经检查过的战争里最大的结束年份。具体看代码。代码： 1 # include 2 # include 3 4 5 int a[110][2] ; 6 int max(int a, int b){return a...
Seraph2012 阅读(108) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1840题意：给一个方程ax^2+bx+c==0的三个系数a、b、c。判定方程解的个数。mark：除了利用判别式，还需要注意考虑非二次的情况。代码： 1 # include 2 3 4 void work() 5 { 6 int a, b, c, 7 scanf (&%d%d%d&, &a, &b, &c) ; 8 if (a==0) 9 if (b == 0)10 if (c == 0) puts (&INF&) ;1...
Seraph2012 阅读(57) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2701题意：你有一双可以瞬移的鞋子，任务是要捕捉一直可以瞬移的萤火虫。给出自己每次瞬移的最远距离和起始坐标，再依次给出这只萤火虫出现的坐标。每次虫子出现，你都向它的坐标瞬移。一旦你和虫的距离不超过1，则认为捕捉到。问虫子在哪个坐标被捕捉到（或不能被捕捉到）。mark：阅读题。阅读了好久，题目又臭又长，只要明白了题意很容易1A。。。代码： 1 # include 2 # include 3 4 5 int r, x, 6 7 8 double dist(double ax, doubl...
Seraph2012 阅读(178) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1587题意：有n种花每种数量无限多，价格是p[i]，有m元钱最多能买多少支。mark：这题竟然不给数据范围。不过好像数据范围不大，m不超过10000，n不超过1000。一开始以为是完全背包后来发现根本就是个贪心。。。代码： 1 # include 2 # include 3 4 5 int a[1000] ; 6 int cmp(const void *a, const void *b) 7 { 8 return *(int*)a - *(int*) 9 }10 11 12 int...
Seraph2012 阅读(75) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1678题意：买3样东西，最便宜的那样可以被当做折扣而不用付钱。问n样东西最多能获得多少折扣？mark：贪心，排序后从大到小3样3样地买。代码： 1 # include 2 # include 3 4 5 int a[20010] ; 6 7 8 int cmp(const void *a, const void *b) 9 {10 return *(int*)b - *(int*)11 }12 13 14 15 void work()16 {17 int n, sum ...
Seraph2012 阅读(147) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2110题意：中文。mark：母函数。但是判有无解的时候要注意，假如答案是10000种，对10000取模后就是0，此时不能判断为无解。可以加一个数组solution表示是否有解。代码： 1 # include 2 # include 3 4 5 int n, sum, MOD = 10000 ; 6 int p[110], m[110], dp[10010], sol[10010] ; 7 8 9 int work()10 {11 int i, j,12 if (sum...
Seraph2012 阅读(112) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2303题意：输入2个数字k和l，第一个是大数（10^100），第二个数是一个上限（10^6）。问k是否有小于l的质因数，如果有，最小的是多少。mark：时限卡的比较严，先把100w以内的素数打表，然后挨个检测素数，每次用大数对这个素数取模。若模为0则为素因子。代码： 1 # include 2 3 4 5 char k[110] ; 6 int prime[1000010], isprime[1000010] ; 7 8 9 void init()10 {11 in...
Seraph2012 阅读(88) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2183题意：中文。。。mark：一开始有点晕，没看出规律。后来发现规律就是个水题。从sample里的1开始看，向右下。。。代码： 1 # include 2 # include 3 4 5 int dp[22][22] ; 6 7 8 void work(int n) 9 {10 int i, j, x,11 memset (dp, 0, sizeof(dp)) ;12 x = n/2 + 1, y = n/2 ;13 for (i = 1 ; i &...
Seraph2012 阅读(67) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1114题意：小盆友通过往猪猪存钱罐里放钱的方式攒钱做事。存钱罐除非砸坏，否则无法把钱取出。为了知道是否攒了足够的钱，对存钱罐称重。然后告诉每种钱币的重量和价值，问存钱罐里最少可能有多少钱。mark：算是一个比较裸的完全背包问题。只不过是选最小。代码: 1 # include 2 # include 3 4 5 int n, m, INF = 0x3f3f3f3 6 int p[510], w[510] ; 7 int dp[10010] ; 8 9 10 int min(int a, i...
Seraph2012 阅读(712) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1264题意：给许多矩形，求面积并。坐标是0到100内的整数。mark：把矩形覆盖的区域赋值为1。。。代码： 1 # include 2 3 4 int g[110][110] ; 5 6 7 int main () 8 { 9 int a, b, c, d, t, i, j,10 while (~scanf (&%d%d%d%d&, &a, &b, &c, &d))11 {12 if (a == -1 && b == -1
Seraph2012 阅读(77) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1727题意：给一个数字，输出它的英文。。。细节比较多，小心点就不容易出错。代码： 1 # include 2 3 4 char tab[][20] = { 5 &zero&, &one&, &two&, &three&, &four&, &five&, 6 &six&, &seven&, &eight&, &nine
Seraph2012 阅读(49) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1133题意：电影院卖票。一张票50元。一开始没有零钱。有m+n个人买票，m个人拿50元的钞票，n个人拿100的。问队伍有多少种排列方式可以使得卖票能顺利进行下去。mark：如果要使得卖票的行为进行下去，对于任意前k个人，必须满足这k个人里面拿100的人数不多于拿50的人数。结果会是一个大整数，要用高精度。公式是n!m!(m-n+1)/(m+1)。推导比较难想，和卡特兰数有关，网上有一篇文档详细写明了这个过程：http://daybreakcx.is-programmer.com/posts/17315.
Seraph2012 阅读(979) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1798题意：给两个圆的圆心和半径求相交部分的面积。mark：思路是把相交部分分成2边，每边求一个扇形减三角形的面积。注意相离和内含的情况判断。这题wa了n次，都是因为精度问题。一个三角形已知三边，求某角。可以用余弦定理直接求，也可以先用海伦公式算出面积，再用正弦定理求（误！！！）。但是海伦公式算面积后再正弦定理会产生比较大的误差！！！# include &stdio.h&# include &math.h&double xa, ya, ra, xb, yb,double
Seraph2012 阅读(91) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1753题意：中文。。。高精度正小数加法。mark：高精度加法，如果把整数部分和小数部分分开搞，比较麻烦。定义了一个struct，数组存数字，dec存的是这个数字里末尾的多少位是小数部分的。两个小数相加，先对齐小数位（位数少的在后面补0）然后当整数加法搞！wa了一次。用宏要注意！41行和42行，如果没有加{}的话，前面的if只管一句！代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 #define ExPand(a,b)
Seraph2012 阅读(279) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2197题意：中文。mark：这题一看题感觉应该是简单题，但是想了挺久。一开始看到是这种单输入单输出的，而且n达到10^9那么大，想了一下应该是公式，没啥好的思路，就果断打表，然后丢到oeis.org里，结果发现根本没公式。后来思考了一下，因为每个串所有可能肯定是2^n，设{i1,i2...im}是n的所有因数，可知非本源串的个数是2^n - sum{f[i1],f[i2]...f[im]}。其中f[i]代表长度为i的非本源串个数。这样只要枚举一下递归就可以了。犹豫了很久没写，总觉得复杂度很大。后来写完以
Seraph2012 阅读(244) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1175题意：中文不多说。mark：3WA，各种脑残错误不多说。最后一个竟然是忘记写return 0。无法直视。说下算法，这题感觉既可以dfs，也可以bfs，但是都不是特好写。好在转弯数限定为2次。那么可以尝试一下比较生猛的写法：先把起点和终点不需转弯直接可达的区域染色（形状大概是2个十字架）。如果这2个区域有重合的地方，自然是YES了。如果没有，扫每一行和每一列，看是否存在2个不同颜色区域之间都没有别的棋子（全0）的情况，如果有，则YES。否则NO。代码： 1 # include &stdio.h
Seraph2012 阅读(158) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2483题意：给一个n*m的0-1矩阵。在里面找符合条件的方阵。条件有3个：1.方阵的4条边上全为1；2.方阵内（除了4条边的）0和1的个数之差不超过1；3.方阵大小至少为2*2。问能找到几个这样的方针。mark：最朴素的做法是枚举所有的1当做要找的方阵左上角的元素。然后判断四边是否全为1，再统计内部0和1的个数。但是每次判断边上的1和计算内部1的数量复杂度太高，肯定是不行的。我们用一个数组sum[i][j]表示从矩形左上角到(i,j)这个位置里1的个数。在计算区域内1的个数的时候可以利用这个sum[i]
Seraph2012 阅读(84) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2717题意：在x坐标上，农夫在n，牛在k。农夫每次可以移动到n-1, n+1, n*2的点。求最少到达k的步数。mark：bfs。范围是2*k内。因为如果当前点大于k，执行2*n和n+1的操作都不是最佳选择。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 int vis[200010] ; 6 int q[200010] ; 7 8 9 int bfs (int n, int k)10 {11 int f = 0, r
Seraph2012 阅读(557) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2716题意：第一行给出一个字母表的排列。用其解密第二行的文本。代码： 1 # include &stdio.h& 2 3 4 5 int main () 6 { 7 char tab[30], str[100] ; 8 910 while (gets (tab))11 {12 gets (str) ;13 for(i = 0 ; str[i] ; i++)14 {15 ...
Seraph2012 阅读(80) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2715题意：给一个n，问能表示成几种连续数字的和的形式。mark：很简单，当然是枚举连续数字的个数(从1到sqrt(n))。代码： 1 # include &stdio.h& 2 3 4 int main () 5 { 6 int n, d, 7 while (~scanf (&%d&, &n)) 8 { 9 ans = 0 ;10 for (d = 1 ; d*(d+1) &= 2* d++)11 {12 ...
Seraph2012 阅读(74) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2714题意：给一串ISBN号，根据算法求出缺的(?表示)那一位。算法是各位上的数字按权相加，和必须为11的倍数。没啥好说的，直接穷举。注意不存在输出-1。代码： 1 # include &stdio.h& 2 3 4 int main () 5 { 6 char str[20] ; 7 int sum, i, 8 while (gets(str)) 9 {10 sum = 0 ;11 for (i = 0 ; str[i] ...
Seraph2012 阅读(82) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2711题意：有n个牛排成一列，每个牛有序号(1~n)，给出每个牛之前有多少个序号小于当前牛的牛数，求序号。第一头牛的未给出。mark：直接从后往前，每次找小于它但是没被选过的序号有多少个，暴力，效率是O(n^2)，200+ms。正解应该是树状数组之类的，懒得写了。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 int dp[8010], ans[8010], a[8010] ; 6 7 8 int ma
Seraph2012 阅读(99) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2710题意：输入n个数，找到最大素因子最大的那个输出。mark：此题实在是坑，1算素数不说，题目是尼玛多组输入的。。。而且我更2，5WA，刚被坑了一个同样的地方，又被坑。。。代码： 1 # include &stdio.h& 2 3 4 int dp[20010] = {0,1} ; 5 6 7 int IsPrime(int x) 8 { 910 for (i = 2 ; i*i &= i++)11 if (x %i == 0) retu...
Seraph2012 阅读(82) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2709题意：一个整数n，表示为若干个2的幂的数字和，问有多少种(mod 1e9)。mark：递推题，考虑1的个数不同，剩下的都是2的幂，可以除以2转移成更小的状态。得递推方程为dp[i] = dp[i-2] + dp[i/2]。注意初始值。代码： 1 # include &stdio.h& 2 3 4 int tab[1000010] = {1, 1, 2} ; 5 6 7 int main () 8 { 910 for (i = 3 ; i &= 1000000...
Seraph2012 阅读(109) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2708题意：给4行，统计大写字母的频率，然后按图示输出。mark：此题很坑，主要表现在：1.每行行末的空格不可以输出！2.输入是多组！！！wa了n次。一开始找max_row的时候初始化各种改错。。。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 int tab[300] ; 6 char str[100] ; 7 int max_tab[300] ; 8 9 10 int main ()11 {12 int i, j
Seraph2012 阅读(81) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1022题意：火车调度问题，栈的基本应用。。。2wa。。。变量忘记初始化。。。太2了。代码： 1 # include &stdio.h& 2 3 4 int n, ans[25] ; 5 char s1[15], s2[15] ; 6 char s[15] ; 7 8 9 int gao()10 {11 int i, p = 0, q = 0, top = 0 ;12 for (i = 0 ; i & 2* i++)13 {14 if (top != ...
Seraph2012 阅读(81) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1209题意：给5个时间（小时：分钟），将之排序。排序规则是按指针锁夹锐角小到大，若夹角相等则按时间早到晚。最后输出中间的那个时间。mark：题目很简单，角度也很好算：时针每小时走30度，每分钟走0.5度。分针每分钟走6度。做差后取绝对值，再和180比一下，如果大于180，用360减。为了避免浮点数排序的麻烦，可乘以2倍后排序。3WA。。。排序的时候if语句后面手贱多写了一个;查了半天才查出来。。。 1 # include &stdio.h& 2 # include &stdlib.h&
Seraph2012 阅读(255) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1709题意：给n个砝码的重量，问从1到重量总和中不能称出的重量的个数和分别都是谁。mark：注意新砝码可以加在左盘也可以加在右盘。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 int dp[10010] ; 6 int buff[10010] ; 7 8 9 10 int abs(int a){return a&0?-a:a;}11 12 int main ()13 {14 int i, j,
Seraph2012 阅读(218) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1060题意：n的n次方最左边的数字是多少。mark：还是取对数那招，log10(n^n)的小数部分决定了最左边的数字。代码： 1 # include &stdio.h& 2 # include &math.h& 3 4 5 int calc(long long n) 6 { 7 double ans = n * log10(n) ; 8 ans -= (long long) 9 return (int)pow(10,ans) ;10 }11 12 13 int ma..
Seraph2012 阅读(49) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1045题意：给定一个最大4*4的方形地图，里面有墙(X)和空地(.)。在每个空地上可以放大炮，但两个大炮如果在同一行或同一列并且之间没有墙阻隔的话，会互相攻击，所以不能同时存在。问最多能放多少个大炮。mark：数据小，直接dfs就可以了。1WA，把保存状态的数组开成了全局的- -。据说还可以二分匹配过。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 char g[4][4] ; 6 int vis[4][4] ; 7
Seraph2012 阅读(650) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2390题意：输入n个运动会项目的举办天和起止时间，不能同时看两场，问最多能看多少场。mark：经典贪心，注意每组输出后面都有一个空行。代码： 1 # include &stdio.h& 2 # include &stdlib.h& 3 4 5 typedef struct NODE{ 6 int s, 7 }NODE ; 8 9 10 NODE sche[50010] ;11 12 13 int cmp(const void *a, const void *b)14 {1
Seraph2012 阅读(65) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2191题意：中文。512地震默哀。mark：dp。多重背包。先做了1171再做这题就很容易了。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 int dp[110] ; 6 7 8 int main () 9 {10 int T, ans, n,11 int p, h, c, i,12 scanf (&%d&, &T) ;13 while (T--)14 {15 ...
Seraph2012 阅读(638) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1176题意：中文。mark：dp即可。。。类似数塔。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 int dp[] ; 6 int n , INF = 0x0f0f0f0 7 8 9 int main ()10 {11 int i, j, k, buff, x,12 int max_t,13 while (~scanf(&%d&,&n)&
Seraph2012 阅读(79) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1171题意：有n样物品，每样物品价值是v，件数是m。尽量把这些物品分成两堆使得两边总价值最接近。输出价值。mark：水dp，或者用母函数搞。wa了3次，trick在于结束标记是负数，而非-1。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 int dp[250010] ; 6 7 8 int main () 9 {10 int i, j, k,11 int n, m,12 while (~s...
Seraph2012 阅读(237) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2700题意：一个字符串如果有偶数个1，就是o，有奇数个1就是e。给出缺了最后一位的字符串和它的属性，求补足最后一位的字符串。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 char str[110] ; 6 7 int main () 8 { 9 int i, cnt,10 11 12 while (gets (str))13 {14 if (strcmp(str, &...
Seraph2012 阅读(113) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2707题意：在一篇文章中，每一段连续的空格代表一个0或一个1。偶数个代表1，奇数个则为0。把所有空格连起来得到一串0-1组成的二进制，再进行解密。每5个0-1二进制字符对应1个字母，末尾不足5个补零。二进制对应的十进制中，0代表空格，1代表A，2代表B……26代表Z，之后27到31分别代表',-.?。按要求解密文章。mark：暴力搞就好，题目说保证空格不出现在每行的行头和行尾，就简单多了。装逼没有好下场，1wa就wa在不想用memset，结果i+j&=cnt写成了i+j&cnt。。。
Seraph2012 阅读(121) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2703题意：有n条通道首尾相连，每个通道有一个容量p和一个通过时间sec，表示最多一次能一起进p个人，需要sec的时间通过。现在有m个人在第一条通道的开始处，他们按照策略通过n条通道。策略有2点要遵守，1是每个通道同一时间只能进一组人，2是只要通道为空并且通道口有人，通道口的人必须立刻进入通道（显然这不一定是最佳策略）。现在就按要求模拟题意，最后问m个人都通过的总用时。mark：一开始觉得是个纯阅读题，再后来发现写起来有的地方也挺难想的。数据规模较小，直接暴搞（总用时最大才780s）。代码： 1 # i
Seraph2012 阅读(96) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2572题意：中文。mark：直接暴搞。1wa，注意要取字母序最小的，长度要先判断。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 char ans[110] ; 6 char s1[110], s2[110], s3[110] ; 7 char ss[110] ; 8 9 10 int find(char s[], char p[])11 {12 int i, j, len1 = strlen(s), len2 = s
Seraph2012 阅读(131) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1804题意：要把输入的英文字符串转化成复数的形式。mark：规则就是那4条。注意y的判断还要满足前一个字符不是元音字母(aeiou)就可以了。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 char dict[25][2][25] ; 6 int n, 7 8 9 int find(char s[])10 {1112 for (i = 0 ; i & i++)13 if ...
Seraph2012 阅读(87) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1978题意：中文。mark：水题。可以dfs搞，也可以dp搞，此处是dp。写错下标wa了1次，忘记删调试信息ole一次。太2了。代码： 1 # include &stdio.h& 2 3 4 # define MOD
7 int a[110][110], dp[110][110] ; 8 int n, 9 10 11 int calc(int x, int y)12 {13 int i, j, rtn = 0 ;14 if (x == n-1 &&
Seraph2012 阅读(120) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2184题意：中文。。。就是递归了。代码： 1 # include &stdio.h& 2 3 4 5 6 7 8 int pil[3][70] ; 9 10 11 void gao(int a[], int b[], int c[])12 {13 long long mid = (1LL && (n-1)) ;14 if (n == 0)15 if (m &= mid)16 {17 c[...
Seraph2012 阅读(79) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1997题意：中文。。。mark：生生递归就好了。代码： 1 # include &stdio.h& 2 3 4 int num[4] ; 5 int pil[4][70] ; 6 7 8 9 int judge(int a[70], int b[70], int c[70], int na, int nb, int nc)10 {11 // printf (&%d\n&, n) ;12 if (n == 0) return 1 ;13 if (na <
Seraph2012 阅读(99) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1992题意：用1*2和2*1的小长方形铺垫4*W的方格有多少种方法。mark：这题真是一个非常有意思的题目，第一眼看，觉得应该是很简单的递推题，但是又秒不掉，灰常让人捉集。首先递推总是想着从后往前由已知解来推出新解。这题很容易想到当W为n的时候，用n-1的结果加上两个竖杠和n-2的结果加上题目分析的那五种中不和n-1重复的4种情况来构造。但是但是但是，这是不完全的。在推导W=3的情况时发现只有9种，然而按题目应该是11种。想了很久才发现漏掉了以下这种情况（由于对称，因此少2种）： -- -- --| .
Seraph2012 阅读(332) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1988题意：n块煎饼，尺寸分别为1至n，从上到下堆成一堆。正面朝上为+，反面朝上为-。每次可以选择上面若干块整个翻转过来。求翻转的步骤，能使得最后正面朝上，尺寸从上到下是小到大。mark：没啥困难的，每次选最大的那个经过不超过3次操作翻到最底下。sample给得很好，主要是注意最顶上1的处理就可以了。代码： 1 # include &stdio.h& 2 3 4 int n, a[35] ; 5 int ans[110], 6 7 8 int abs(int x){return
Seraph2012 阅读(123) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1987题意：就是1986的逆向。。。解码。mark：要注意的是要去掉解码出来的字符串的结尾空格。如果字符串是空串，数字和字符串之间的空格不需要去掉。一直PE，后来发现是去结尾空格的时候，i = len - 1写成了i = len。。。太2了。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 char str[410] ; 6 char out[25][25] ; 7 char ss[100], ssout[110] ;
Seraph2012 阅读(48) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1986题意：按要求把字母或空格字符串扩展成5个01字符表示的字符串以后，缠绕放置在一个r*c的矩阵里。最后一排一排输出。mark：各种wa。后来才发现是输入的问题。当字符串长度为0的时候，我本来用的是scanf的正则输入，结果事实证明不行。。。另外用来放置扩展以后的字符串的字符数组ss一开始忘记清0也wa了一次。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 char str[100] ; // less than 8
Seraph2012 阅读(124) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1981题意：给长度为n的小写字母字符串，有3种操作：&Q A&：输出当前字符串的第A个字符;&S A B&：把第A个到第B个字符都加1。a变成b，b变成c，z变成a。。。&R A B&：把从A到B的字符串逆转。输出就是Q操作的时候的输出。mark：这题真是tricky。一看8w个字符，先知道直接搞是肯定不行的。后来想了一下也没想到好办法。查了一下，原来可以记录下每次的操作，然后查询的时候根据位置往前循环，因为查找次数少，因而效率比较高。一开始w
Seraph2012 阅读(96) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1673题意：一条路上有n家商店，给出坐标。某人停车在某点后，要逛完所有商店回到车出。停车地点自选，求最少需要步行多远。mark：唬人，其实就是最大值与最小值差的两倍。代码： 1 # include &stdio.h& 2 3 4 int main () 5 { 6 int T, n, 7 int max, 8 scanf (&%d&, &T) ; 9 while (T--)10 {11 scanf (&%d&, &
Seraph2012 阅读(149) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1236题意：中文名。这种排序题已经无力吐槽了。敲错变量tle了一次- -。代码： 1 # include &stdio.h& 2 # include &stdlib.h& 3 # include &string.h& 4 5 6 typedef struct STU{ 7 char name[25] ; 8 9 }STU ;10 11 12 STU stu[1010] ;13 int scr[15] ;14 15 16 int cmp (const
Seraph2012 阅读(116) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2571题意：中文。mark：水dp。不过边界不太好处理，写成dfs+记忆化比较方便。给2组容易错的数据。应该都输出0。21 2-1 12 1-11代码： 1 # include &stdio.h& 2 3 4 int a[25][1010], vis[25][1010] ; 5 int n, m, INF = 0x0f0f0f0 6 7 8 int max(int a, int b){return a&b?a:b;} 9 10 11 int dfs(int x, int y)12
Seraph2012 阅读(221) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2570题意：中文。mark：很水的题。体积V都一样，排序后贪心就可以了。各种wa，主要还是浓度计算那儿装逼不想用实数，就用整数绕过去，结果各种想不清楚。代码： 1 # include &stdio.h& 2 # include &stdlib.h& 3 4 5 int p[110] ; 6 7 int cmp(const void *a, const void *b) 8 { 9 return *(int*)a - *(int*)10 }11 12 13 int main
Seraph2012 阅读(144) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2569题意：中文。mark：水递推。很容易得到方程dp[i] = 2*dp[i-1]+dp[i-2]。不过dp[0] = 3。注意要用long long。代码： 1 # include &stdio.h& 2 3 4 long long dp[45] = {3,3} ; 5 6 7 int main () 8 { 9 int T, n,10 for (i = 2 ; i &= 40 ; i++)11 dp[i] = 2*dp[i-1]+dp[i-2] ;1...
Seraph2012 阅读(90) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2568题意：中文。mark：看清楚题就好了。就是求二进制表示时1的个数。本来嘛递归直接可以搞，请容我装逼一下用了位运算。。。代码： 1 # include &stdio.h& 2 3 4 int calc(int x){return x?calc(x-(x&-x))+1:0;} 5 6 7 int main () 8 { 9 int T,10 scanf (&%d&, &T) ;11 while(T--)12 {13 scanf (&%d
Seraph2012 阅读(63) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2567题意：中文。没啥好说的。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 int main () 6 { 7 int T, i, 8 char s1[55], s2[55] ; 9 scanf (&%d&, &T) ;10 while (T--)11 {12 scanf (&%s%s&, s1, s2) ;13 len = strlen(s1) ;14..
Seraph2012 阅读(77) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1800题意：士兵要学骑扫帚。每个士兵有一个level，level高的能在同一把扫帚上教level低的怎么骑。一个人最多有一个老师，一个学生。也可以没有。给n个士兵的level值，问最少需要多少扫帚。mark：显然就是找出现次数最多的数字的次数。但因为数字长度多达30个字符，因此long long都存不下，用字符串。wa了一次，忘记处理前导0。代码： 1 # include &stdio.h& 2 # include &string.h& 3 # include &stdli
Seraph2012 阅读(868) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1496题意：给a,b,c,d。计算有多少组(x1,x2,x3,x4)满足方程。mark：这其实是poj1840的Eqs简化成的问题，是一个经典的hash问题，但是poj是对内存限制严格，此题则是对时间卡的更紧，TLE了好多次。首先将等式分成两边，写成a*x1^2+b*x2^2 = - c*x3^2-d*x4^2，然后枚举其中一边的所有值存起来(hash存)，再枚举另一边求解。懒得写hash，直接开200w的数组不是不行，但是很容易TLE。千万不能用O(n)的方式清零数组，应该再执行一次存数时的枚举，原来
Seraph2012 阅读(306) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2094题意：题目说的不清楚，有很多情况都没说到。不过数据很水，只要判断入度为0的点是否只有1个就可以了。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 6 char tab[] ; 7 int degree[2010] ; 8 9 10 int find(char a[])11 {1213 for (i = 0 ; i & i++)14 i...
Seraph2012 阅读(147) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2093题意：中文。成绩排序。mark：看似复杂，其实就是个排序，考察基本功。代码： 1 # include &stdio.h& 2 # include &string.h& 3 # include &stdlib.h& 4 5 6 typedef struct NODE{ 7 char name[15] ; 8 int num, 9 }NODE ;10 11 12 NODE stu[1010] ;13 14 15 int cmp(const void *
Seraph2012 阅读(69) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2079题意：中文。。。mark：母函数。代码： 1 # include &stdio.h& 2 # include &string.h& 3 4 5 int dp[10][45] ; 6 7 8 int main () 9 {10 int T, n, i, j, k,11 int a,12 scanf (&%d&, &T) ;13 while (T--)14 {15 scanf (&%d%d&, &n, &
Seraph2012 阅读(83) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1075题意：在输入的字符串里找词典中的进行替换。mark：诚然，我很讨厌STL，但是这题要是不用STL的话简直太恶心了。最后非常慢。。。将近TLE。代码： 1 # include &iostream& 2 # include &string& 3 # include &map& 4 # include &stdio.h& 5 6 7
8 char s[3010] ; 9 10 11 int main ()12 {
Seraph2012 阅读(86) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1071题意：按图，给出p1,p2,p3的坐标，计算阴影部分面积。mark：就是求公式咯。设y = ax^2 + bx + c。用(x1,y1),(x2,y2)相减再联合顶点坐标(-b/2a, c-b^2/4a)可以轻易求出a，b，c的值。之后算积分就可以了。注意还要减去直线和x轴所夹梯形的面积。代码： 1 # include &stdio.h& 2 # include &math.h& 3 4 5 double fun(double a, double b, double c,
Seraph2012 阅读(140) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1677题意：俄罗斯套娃是一种有宽w和高h两种属性的玩具。当wi & wj && hi & hj的时候，套娃i能被套在套娃j里。现在给出m个套娃的宽和高，问最少能套出几个套娃。mark：首先按宽度从大到小排序，得到结果以后按高度求最长非降子序列（LIS）。这题和导弹拦截系统问题一样，是经典dp。一开始偷懒写了贪心结果TLE了。代码： 1 # include &stdio.h& 2 # include &stdlib.h& 3 # include &
Seraph2012 阅读(148) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1671题意：给堆电话号码（数字，长度不大于10），如果有一个号码是另一个号码的前缀就NO，否则YES。mark：trie树来存和查找号码，但是写的有点恶心。代码：# include &stdio.h&# include &string.h&typedef struct TRIE{ int next[10] ;} TRIE ;TRIE trie[100010] ;char tb(char ch){return ch-'0';}i
Seraph2012 阅读(251) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2192题意：n个size不同的大楼，相同size的不能放在同一MagicBuilding中。问至少要多少个MagicBuilding。mark：其实就是求出现最多的那个数出现的次数，排序以后扫一次就好了。代码：# include &stdio.h&# include &stdlib.h&int a[10010] ;int cmp(const void *a, const void *b){ return *(int*)a - *(int*)}int main (){ in
Seraph2012 阅读(59) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1492题意：丑数(humble number)是一种素因子只有2、3、5、7组成的数字。给一个丑数，问它有多少因数。mark：基础数论。因为只有2、3、5、7四种素因子，因此只要求出幂次，加1后乘起来就好了。注意要用long long。代码：# include &stdio.h&long long div(long long x, int b){ int rtn = 0 ; while (x%b==0) { x /= rtn ++ ; } ...
Seraph2012 阅读(190) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2601题意：给n，找满足i*j+i+j == n的一对(i,j)，其中0&i&=j&n。mark：两边同时+1后得到(n+1)=(i+1)*(j+1)。只要从2到sqrt(n+1)枚举i+1的值就好了。不过时间有点久，2000+ms。正规的做法应该是用数论知识分解素因子。另外要考虑n是10^10，用long long（此处wa了一次）。代码：# include &stdio.h&# include &math.h&int main (){ int T, sum,
Seraph2012 阅读(96) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1506题意：给一些连续的直方柱的高（宽是1），找一个面积最大的矩形。mark：本来是个单调队列题，但是dp好像可以解。考虑每个柱往两边找能扩展到的最远的边界，乘上自己的高可获得。往两边扩展边界的时候理论复杂度是O(n)，直接做是要TLE的。先考虑往右找边界，假设之前右边所有的直方柱的边界已经被找过，并且被记录下来，假如下一个柱的高度比自己高，则直接可以跳到下一个柱的边界继续找，不断迭代后很快就能找到边界。不知道这种迭代的方法复杂度如何证明，对于每个柱子，最坏的肯定是要找n次（递减），但是最坏的情况不可能
Seraph2012 阅读(439) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2552题意：中文。。。mark：无论输入是多少。。。输出都是1。代码：# include &stdio.h&int main (){ int T ; scanf (&%d&, &T) ; while (T--) puts(&1&) ; return 0 ;}
Seraph2012 阅读(87) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2551题意：中文，直接循环可搞。代码：# include &stdio.h&long long calc(long long x){ long long i, sum = 0 ; for (i = 1 ; ; i++) { sum += i*i* if (sum &= x) }}int main (){ int T, scanf (&%d&, &T) ; while (T--)...
Seraph2012 阅读(86) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2550题意：中文。mark：2wa，没看清题意，还要按箭身长度排序，囧。代码：# include &stdio.h&# include &stdlib.h&typedef struct NODE{ int a,}NODE ;NODE num[100] ;int cmp(const void *a, const void *b){ NODE *p = (NODE*)a, *q = (NODE*) return p-&a - q-&}void outp
Seraph2012 阅读(41) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2549题意：中文。mark：水题不解释。代码：# include &stdio.h&# include &string.h&int main (){ int T ; int a, n, char str[10] ; scanf (&%d&, &T) ; while (T--) { scanf (&%d.%s %d&, &a, str, &n) ; len = strlen(str) ; if (n <
Seraph2012 阅读(85) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2548题意：中文。mark：著名的ooxx题。。。不解释。代码：# include &stdio.h&# include &math.h&int main (){ int T ; double a, b, c, scanf (&%d&, &T) ; while (T--) { scanf (&%lf%lf%lf%lf&, &a, &b, &c, &d) ; printf (&%.3l
Seraph2012 阅读(72) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2547题意：中文。mark：其实就是求两点间距离，水。注意输入数据是实数。代码：# include &stdio.h&# include &math.h&int main (){ int T ; double a, b, c, scanf (&%d&, &T) ; while (T--) { scanf (&%lf%lf%lf%lf&, &a, &b, &c, &d) ; printf (&q
Seraph2012 阅读(116) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1722题意：中文。mark：公式，p+q-gcd(p,q)。证明不懂。。。见大牛博客。http://blog.sina.com.cn/s/blog_00soe2.html代码：# include &stdio.h&int gcd(int p, int q){return p%q?gcd(q,p%q):q;}int main (){ int p, while (~scanf (&%d%d&, &p, &q)) printf (&q
Seraph2012 阅读(87) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1323题意：某数的真因子加起来比它大叫做ABUNDANT，比它小叫做DEFICIENT，相等叫做PERFECT。输入一个数，输出它是哪种情况。直接暴。代码：# include &stdio.h&int main (){ int n, ans, puts (&PERFECTION OUTPUT&) ; while (~scanf (&%d&, &n),n) { for(i = 1,ans=0 ; i & n && a
Seraph2012 阅读(46) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1328题意：输入一个字符串，没个字符后移1位后输出。代码：# include &stdio.h&int main (){ int T, i, nCase = 1 ; char str[55] ; scanf (&%d&, &T) ; while (T--) { scanf (&%s&, str) ; for(i = 0 ; str[i] ; i++) str[i] = (str[i]-'A'+1)%26+'A'
Seraph2012 阅读(38) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1334题意：输出所有(1,200]区间上满足a^3==b^3+c^3+d^3的式子。mark：水题，枚举a、b、c，在[c,a-1]区间上二分求d后验证。n次wa，二分写得挫。代码：# include &stdio.h&# include &math.h&int sqrt3(int num,int l,int r){ int mid = 210 ; if (l*l*l&num) return 0 ; if (r*r*r&num) return 210 ; while
Seraph2012 阅读(105) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2374题意：有n个碗，标号为1到n。每个碗内有一些小珠子。每次从一个碗里拿出一个珠子，此时要往所有编号小于它的碗内各放入一颗珠子。问要拿多少次才能把所有的珠子拿完。mark：直接模拟。没注意I64d，1wa。代码：# include &stdio.h&long long num[60] ;int main (){ int i, j, while (~scanf (&%d&, &n),n) { rtn = 0 ; ...
Seraph2012 阅读(56) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1335题意：前面是一个7位a进制数，表示成后面的进制。如果超过7位则输出ERROR。直接模拟。代码：# include &stdio.h&char str[40] ;int chartonum(char ch){ if (ch &= '0' && ch &= '9') return ch-'0' ; return ch-'A'+10 ;}int gao(char str[], int b){ int
Seraph2012 阅读(42) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2370题意：一个数字可以表示成若干个fibonacci数的和。求表示成fib后“右移”1位的数字。mark：打表前30个fib数，然后用贪心法可算出任何数字的fib数表示形式，再累加。代码：# include &stdio.h&# include &string.h&int fib[35] = {1,1} ;int tab[35] ;void init(){ for (i = 2 ; i &= 30 ; i++) fib[i] = fib[i-1]+fib[
Seraph2012 阅读(40) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1342题意：从给定的集合里面选出6个数字按顺序输出。把所有的选择都输出。mark：直接dfs就好了。代码：# include &stdio.h&int num[20] ;int ans[6] ;void dfs(int idx, int n){ if (n == 6) { for(i = 0 ; i & i++) if (i == 0) printf(&%d&,ans[i]) ; else ...
Seraph2012 阅读(62) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1361题意：对于一个合法的括号序列S，可以计算出P和W的值。P的第i个值表示第i个右括号前面有多少个左括号，W的第i个值表示第i个右括号会和前面第几个左括号匹配。现在给出P的值，求W的值。mark：因为数据很小，n的长度只有20，因此可以直接模拟，由P反求出S，然后由S直接求出P。代码：# include &stdio.h&# include &string.h&char str[50] ;int p[50],w[50] ;void setstr(){ int nu
Seraph2012 阅读(82) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1715题意：算fibonacci数。mark：大数运算。第1000个fib数只有200多位，直接打表好了。代码：# include &stdio.h&int fib[] ;char str[300] ;void add(int a[], int b[], int c[]){ int *p, * int i, cc = 0 ; if(a[0]&b[0])p=a, q= else p = b, q= for(i = 1 ; i&= q[0] ...
Seraph2012 阅读(117) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1370题意：有3个循环周期，周期天数分别为23、28、33。对于某一年，已知某年这3个周期的某一峰值分别是当年的第p、e、i天，问从第d天开始到最近一个满足3个周期都达到峰值的日期还有多少天。mark：据说是剩余定理。数据比较小，直接打表可过。比较蛋疼的是wa了很多次，因为算减法以后忘记取模了。。。代码：# include &stdio.h&int tab[40][40][40] ;int _0(int num){ if (num &= 0) return num + 21252 ;
Seraph2012 阅读(136) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1379题意：输入一堆字符串，按“逆序数值”排序。如果相同，按输入顺序。mark：50个字符串，每个长度是100，算逆序数是O(n^2)，复杂度是500000，直接暴力可搞。数据比较水，排序直接用qsort不用考虑输入顺序。如果非要考虑也可以，加一个下标表示原来的序号，比较的时候多比较一下就OK了。代码：# include &stdio.h&# include &stdlib.h&typedef struct STRING{ char str[110] ; int unsorted
Seraph2012 阅读(50) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1720题意：输入十六进制的a和b，输出十进制的a+b。代码：main(a,b){while(~scanf(&%x%x&,&a,&b))printf(&%d\n&,a+b);}
Seraph2012 阅读(26) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1393题意：一个钟面只有一根分针。对于一个数字d，把中面上的分针指向的时间s往后拨s的d倍。问给定d，重复这样的操作多少次能回拨到0。若不能则输出Impossible。mark：因为钟面只有60分钟，所以最多不会超过60次，直接暴力就可。代码：# include &stdio.h&int main (){ int i, s, d, int tab[100] ; while (~scanf (&%d%d&, &s, &d) &&
Seraph2012 阅读(59) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1395题意：给出n，求满足2^x mod n = 1的最小的x。mark：数论题，其实就是求a模m的阶。打素数表敲错变量，1wa。可以水过，但是最好需要知道以下知识。1. 若gcd(a,m)==1，一定存在一个正整数d&m使得a^d == 1 mod m（欧拉定理）。2. 满足条件的最小正整数d记为ord_m(a)，叫做a模m的阶。3. 若对于一个正整数a满足(1)gcd(a,m)==1;(2)ord_m(a)==φ(m)(φ(m)表示m的欧拉函数);则a叫做m的一个原根。4. 若gcd(a,m)
Seraph2012 阅读(389) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1564题意：从一个n*n的棋盘的某个角落开始，走过的格子不能再走，每次轮流移动棋子（上下左右），最后无法移动的人输。问是否有先手必胜的策略。mark：打表后看出规律。证明不会。代码：main(n){while(scanf(&%d&,&n),n)puts(n&1?&ailyanlu&:&8600&);}打表程序：# include &stdio.h&int graph[] ;int d
Seraph2012 阅读(233) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1397题意：给一个偶数，求可以表示为多少对素数对的和。mark：最大范围是2^15 = 32768。打素数表，然后枚举。理论上会TLE，但是水过了。代码：# include &stdio.h&int IsPrime[40010] ;void init(){ int i, for (i = 0 ; i &= 40000 ; i++) IsPrime[i] = 1 ; for (i = 2 ; i &= 200 ; i++) if (IsPrime[i]) ...
Seraph2012 阅读(85) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1297题意：n个字母，由F和M组成。F不能单独存在。求满足条件的字符串数目。mark：递推很容易得到方程dp[n] = 2*dp[n-1]-dp[n-2]+dp[n-3]。但是题目中n最大是1000，结果是200多位的整数，要写成大数运算，大数减法没写过。。。方程可等价为dp[n] = dp[n-1]+dp[n-2]+dp[n-4]，这样就回避了减法的问题。代码：# include &stdio.h&# include &string.h&char ans[]
Seraph2012 阅读(108) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1113题意：给一堆单词做字典，XXXXXX结束。然后给若干个单词，输出它和字典里哪些单词由同样的字母（个数也相同）组成，有多组的话按字典序输出。XXXXXX结束。mark：题意有点绕。。。思路是先把字典里的单词排序，并且每个单词计算一个值val。这个val是把单词的字母排序以后hash得到的，范围是26^6也就是3亿多一点，可以用int来表示。这样接下来每个单词输入的时候，只要比对字典里的val，相同则可以输出。不hash的话就多存一个字母排序以后的单词也可以。代码：# include &stdi
Seraph2012 阅读(185) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1141题意：atmel公司1960年发布4bits的处理器，每10年翻一番。给一个年份，问最近一次发布的处理器能运算的n!最大的n是多少。mark：最大的处理器位数是2160年的4194304bits。要算n!的二进制表示位，直接算很难，可以变成求log2后取整加1。然后因为log2(n!) = log2(1) + log2(2)...+log2(n)，所以直接O(n)就可以了。大概算到30w可以把500wbits的算出来，之后按输入二分。代码：# include &stdio.h&# in
Seraph2012 阅读(79) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1212题意：求一个数（大数）对另一个数（小数）的模。mark：大数除法求模，简单。代码：# include &stdio.h&char str[1010] ;int calc(){ int i, cc = 0 ; for (i = 0 ; str[i] ; i++) { cc = cc * 10 + str[i] - '0' ; cc %= }}int main (){ while (~scan...
Seraph2012 阅读(55) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1702题意：告诉你FIFO或FILO（先进先出、先进后出），然后对每次操作进行模拟，输出结果。mark：栈和队列的模拟。。。代码：# include &stdio.h&int dp[1010] ;void Queue(){ int front = 0, rear = 0, char str[20] ; while (n--) { gets (str) ; if (str[0] == 'I'){ sscan...
Seraph2012 阅读(80) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2059题意：中文。mark：题意有点绕。关键是算出乌龟的最短到达时间。方法就是dp了，每个站到达的最短时间是之前所有站直接转移过来的时间里最少的那个。1wa，错在double和int的转换上。。。2b了。代码：# include &stdio.h&int p[110] ;double dp[110] ;int n, vt1, vt2, c, t, L ;double min(double a, double b){return a&b?a:b;}double w(double s, d
Seraph2012 阅读(319) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2175题意：中文。mark：递归算一下就可以了。n个盘子前2^(n-1)-1次是移动n-1个盘子的操作，第2^(n-1)是移动最大那个盘子，后面又是n-1个盘子的操作。代码：# include &stdio.h&long long dfs(long long n, long long m){ long long mid = (1LL&&(n-1)) ; if (m == mid) if (m & mid) return dfs(n-1,m) ; ret
Seraph2012 阅读(36) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2137题意：把一个字符串（奇数个字符）按中间字符为轴逆时针旋转n次后，输出。mark：2WA，n居然可以为负。。。代码：# include &stdio.h&# include &string.h&void out0(char str[], int len){puts (str) ;}void out1(char str[], int len){ int i, for (i = len-1 ; i &=0 ; i--) { for (j = 0 ; j & i
Seraph2012 阅读(67) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2136题意：问一个数n最大的素因子是第几个素数。mark：之前一直TLE。素数表不打好会TLE，分解素因子的时候不加sqrt优化也会TLE。。。先打好100w的素数表，把素数的位序标记好，然后从1到sqrt(n)分解n，得到n最大的素因子后，再看是第几个。代码：# include &stdio.h&# include &math.h&int IsPrime[1000010] ;int Primes[1000010] ;int cnt = 0 ;void init(){ int i
Seraph2012 阅读(174) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2065题意：中文。mark：很多人说是指数型母函数，的确指数型母函数可秒，但是出题者的意图更可能是考察递推+矩阵乘法。按状态,长度为n的时候：D[1,n]表示偶数个A、偶数个C的情况数，D[2,n]表示偶数个A、奇数个C的情况数，D[3,n]表示奇数个A、偶数个C的情况数，D[4,n]表示奇数个A、奇数个C的情况数。有长度为n的时候情况可由长度为n-1的情况推来：(D[1,n],D[2,n],D[3,n],D[4,n])*M=(D[1,n+1],D[2,n+1],D[3,n+1],D[4,n+1])。其
Seraph2012 阅读(373) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2133题意：输入一个日期，输出不合法(illegal)或星期几。mark：直接计算该日期和0年1月1日(周六)天数差，然后模7就好，注意闰年还有合法性判断要包括0月和0日的情况。代码：# include &stdio.h&int mon[2][13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31, 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31} ...
Seraph2012 阅读(171) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1254题意：中文。mark：BFS+DFS。用BFS来展开箱子的位置和小人的位置，每个节点有2个属性，1是箱子所在位置的坐标，二是一个hash值来表示小人能位于箱子上下左右四个地方的情况（每个方向能否到达用1位来表示，共需要用15）。计算hash值的时候用DFS来穷举小人所有能到达的位置。wa了1次，DFS的时候忘记考虑小人不能穿过箱子的情况。代码：# include &stdio.h&# include &string.h&int graph[10][10] ;int n, m
Seraph2012 阅读(77) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1728题意：中文。mark：我真是弱爆了。总体思路就是BFS，只不过不是用步数来限制，而是用转弯次数。注意坐标是先纵后横。。。先拍了个DFS，理所当然地TLE了。然后拍了个BFS，其实没想清楚就拍了，结果还TLE。想了半天，BFS没理由TLE啊。然后放了2天，今天想清楚了很多细节，又拍了一个BFS，又TLE了。后来发现是加点至队列的时候，如果一个方向上的某点之前已经访问过，则不加入队列这里，直接写了continue，忘记让x和y坐标变到下一个点去了。。。代码：# include &stdio.h&
Seraph2012 阅读(363) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1180题意：中文。mark：题目没说明楼梯改变情况。sample中的路径应该是先向上走，再向右走，通过楼梯后走到头再向上，这里wa了1次。bfs+优先队列。优先队列用手写堆实现。数据规模很小。代码：# include &stdio.h&# include &string.h&char graph[25][25] ;int dr[4][2] = {0,1,0,-1,1,0,-1,0} ;int sx, sy, ex,int vis[25][25] ;int q[25*25
Seraph2012 阅读(146) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1026题意：n*m迷宫，求从(0,0)到(n-1,m-1)的最少时间。'X'是墙，'.'是空地，'1'-'9'表示有怪物，消灭之需要数字对应的时间。mark：最近一直在写搜索题。搜索题有的很费劲，但是写多也就觉得嗯，就那么回事。这题也没啥可说的，直接BFS。和最简单的BFS不同的是，判断一个过去到过的点是否可走，需要多开一个数组来记录，然后判断过去到达的时间和现在到达的时间的大小。（其实最好的方法是优先队列么。。。懒得写而已。）然后因为要求
Seraph2012 阅读(815) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1418题意：中文。mark：1wa。虽然n、m都是整形范围，但是加起来可能会超过，因此要用long long。不存在m & 2的情况。代码：# include &stdio.h&int main (){ long long n, while (~scanf (&%I64d%I64d&, &n, &m) && (n||m)) printf (&%I64d\n&, n+m-2) ; return 0 ;}
Seraph2012 阅读(41) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1562题意：求最小的[]区间内的数x满足x%a==0 && (x+1)%b==0 && (x+2)%c==0。mark：应该是用剩余定理的，不过数据那么小，直接爆了。代码：# include &stdio.h&int main (){ int T, a, b, c, scanf (&%d&, &T) ; while (T--) { scanf (&%d%d%d&, &a, &am
Seraph2012 阅读(36) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1999题意：中文。mark：打表到100w。。。（上限是试出来的。。。）代码：# include &stdio.h&int sum[1000010] ;int dp[1010] ;void init(){ int i, for (i = 1 ; i &= 500000 ; i++) for (j = 2* j &= 1000000 ; j+= i) sum[j] += for (i = 2 ; i &= 1000000 ; i+...
Seraph2012 阅读(67) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1088题意：写一个html代码显示的程序。。。mark：就是麻烦，没别的。各种PE。后来发现是只考虑了' '和'\n'，忘记考虑'\t'。。。代码：# include &stdio.h&int main (){ int ch, cnt = 0, cc = 0 ; int flag = 0, end = 1 ; char buff[100] ;// freopen (&in.txt&, &r"
Seraph2012 阅读(62) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2068题意：中文。mark：如果知道错排公式就很简单了。wa了一次。。。&=写成了&。。。PE一次。莫名其妙多加了个空格。sb了。代码：# include &stdio.h&long long c[30][30] = {1} ;long long cp[15] = {0, 0, 1} ;void init(){ int i, for (i = 1 ; i &= 25 ; i++) { c[i][0] = 1 ; for (j = 1 ; j &= i...
Seraph2012 阅读(86) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1420题意：求a^b mod c。mark：快速幂无疑是最简单的写法。不过c只有100w，也可以用数论的方法做。此处用的是快速幂。代码：# include &stdio.h&int qpow(long long a, long long b){ long long ans = 1, buff = while (b) { if (b&1) ans = (ans*buff) % b &&= 1 ; buff =...
Seraph2012 阅读(53) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1072题意：I想（从2处）逃出迷宫（3处），0是墙，1是空地。身上有定时炸弹，在第6s爆炸（只能走5步）。4处是将定时炸弹重设的工具。问它最快能否逃出迷宫。mark：bfs。多添加一个数组标记上次到达当前位置时定时炸弹的剩余秒数。代码：# include &stdio.h&# include &string.h&int n,int graph[10][10] ;int step[10][10] ;int times[10][10] ;int sx, sy, ex, ey
Seraph2012 阅读(52) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1593题意：中文。mark：1wa。直接往开始的反方向按半径逃不可以。找一个同心圆，让V1的角速度略大V2。在那个圈上0086可以甩对方一个直径后再往岸边划。代码：# include &stdio.h&# include &math.h&# define Pi acos(-1)int main (){ int R, V1, V2 ; double t1, t2 ; while (~scanf (&%d%d%d&, &R, &V1, &V
Seraph2012 阅读(53) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1231题意：中文。最大连续子川和。经典dp（不知道算不算dp）。代码：# include &stdio.h&int a[10010] ;int n, s, e, max_void find(){ int i, ss = s, ee = e, sum = max_ for (i = 1 ; i & i++) { if (sum & 0) ss = ee = sum = a[i] ; else { ...
Seraph2012 阅读(45) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1898题意：S和X比做题。他们的做题顺序是一样的，但并不是做一题交一题。S每A分钟交一次，X每B分钟交一次。问T分钟的时候是谁交的题多。mark：水。假设每分钟做1题，求出两人各自交了多少题后比较。。。代码：# include &stdio.h&int main (){ int T ; int a, b, t, aa, scanf (&%d&, &T) ; while (T--) { scanf (&%d%d%d&, &a,
Seraph2012 阅读(48) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1718题意：问给定学号在所有成绩里的排名。。。mark：无聊题。1wa，多组输入。。。代码：# include &stdio.h&int a[1100], b[1100] ;int main (){ int i, aa, ans, cnt = 0 ; while (~scanf (&%d&, &aa)) { cnt = 0 ; while (~scanf (&%d%d&, &a[cnt], &b[cnt])) { if (...
Seraph2012 阅读(35) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1286题意：中文。mark：看似很绕其实就是求欧拉函数Phi(n)。对于所有n的素因子Pi，欧拉函数Phi(n) = n * (P1-1)/P1 * (P2-1)/P2 * (P3-1)/P3 ...。对于每一个Pi，因为n总是Pi的倍数，所以可以先除再乘，不会溢出。代码：# include &stdio.h&int Primes[40000] = {2, 3} ;int PrimeNum = 2 ;int dp[40000] ;int calc(int nn){ int ans = nn,
Seraph2012 阅读(52) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1563题意：找n个数里只出现了1次的数。mark：hash搞之。大于200的最小素数是211。代码：# include &stdio.h&# include &string.h&int dp[211][2] ;void insert (int n){ int idx = n % 211 ; while (dp[idx][0] != n && dp[idx][1] != 0) idx++ ; dp[idx][0] = dp[idx][1] ++ ;}int
Seraph2012 阅读(58) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1491题意：给一个2006年的日期，问和日还差几天。mark：getdays是用于获得m月d日是当年的第几天。最后和10月21日做比较。代码：# include &stdio.h&int getdays (int m, int d){ int i, rtn = 0, month [12] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30} ; for (i = 0 ; i & i++) rtn += m...
Seraph2012 阅读(27) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1253题意：中文。。。mark：三维BFS水过。其实和二维没多大区别。代码：# include &stdio.h&# include &string.h&# define REP(i,a) for(i = 0 ; i & i++)int q[55*55*55][3] ;int graph[55][55][55] ;int step[55][55][55] ;int a, b, c,int tab[6][3] = {{0, 0, 1}, {0, 0, -1},
Seraph2012 阅读(123) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1577题意：中文。mark：gcd是否为1。注意不能有除数为0。代码：# include &stdio.h&int abs(int n){return n&0?-n:n;}int gcd(int a, int b){return a%b==0?b:gcd(b,a%b);}int main (){ int l, px, py, sx, while (~scanf (&%d&, &l), l) { scanf (&%d%d%d%d&
Seraph2012 阅读(83) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=1708题意：给两个字符串s0和s1，sn是sn-1和sn-2拼接而成的。问sn中每个字母出现的次数。mark：直接递推就可以了。注意0的情况。代码：# include &stdio.h&# include &stdlib.h&# include &string.h&int t1[30], t2[30], t3[30] ;void output (int t[]){ for (i = 0 ; i & 26 ; i++) printf (&
Seraph2012 阅读(78) |
摘要: 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2309题意：给n个数，去掉一个最大的和一个最小的，然后求平均数。蛋疼的日式英文。代码：# include &stdio.h&int main (){ int n, max_n, min_n, num, while (~scanf (&%d&, &n), n) { sum = 0 ; min_n = 1100, max_n = -1 ; for (i = 0 ; i & i++) { ...
Seraph2012 阅读(45) |
19:55:02地址：http://acm.hdu.edu.cn/showproblem.php?pid=2401题意：有1-N一共N个篮子，每个里面有很多金币。每个金币的重量是w，但是其中有一个篮子金币的重量只有w-d。现在从第一个篮子拿1个金币，第二个拿2个。。。第n-1个篮子拿n-1个。第n个不拿。把拿出来的金币称重。问金币轻的篮子编号是多少。mark：不知道第二组sample为什么可以是10。。。诡异。代码：# include &stdio.h&int main (){ int n, w, d, rst, while (~scanf (&q
Seraph2012 阅读(71) |
17:22:53地址：http://acm.hdu.edu.cn/showproblem.php?pid=2529题意：中文。mark：设v的水平分量为x，则最终距离和x的关系应该是先增后减，遂三分。。。代码：# include &stdio.h&# include &math.h&double l,double f(double x){ return sqrt(v*v-x*x)*l/x - 0.5*9.8*l*l/(x*x) ;}int main (){ double left, right, m1, m2, while (~sc
Seraph2012 阅读(56) |
04:07:41地址：http://acm.hdu.edu.cn/showproblem.php?pid=2516题意：中文。mark：完全不会。看了网上说打表看出规律似乎是Fibonacci。遂写代码。wa了一次，因为[0...43]的数量我用二分的时候居然算成了43个。。。应该是44个的。代码：# include &stdio.h&# include &stdlib.h&int dp[50] = {2, 3} ;int cmp(const void *a, const void *b){ return *(int*)a - *(int*)
Seraph2012 阅读(43) |
20:47:45地址：http://acm.hdu.edu.cn/showproblem.php?pid=2512题意：中文。。。mark：递推。dp[i][j]表示i张卡片分在j本书的种类数，有dp[i][j] = dp[i-1][j-1] + dp[i-1][j]*j。代码：# include &stdio.h&# define MOD 1000int dp[] ;int ans[2010] = {0, 1} ;int main (){ int T, int i, dp[1][1] = 1 ; for (i ...
Seraph2012 阅读(26) |
19:37:25地址：http://acm.hdu.edu.cn/showproblem.php?pid=2539题意：中文。有点点麻烦的模拟。代码：# include &stdio.h&# include &string.h&char str[110] ;int goal[20] ;int judge (char s[]){ int len = strlen(s) ; if (len & 10) return 1 ; if (s[len-8] == ' ' && s[len-7] == 'n'
Seraph2012 阅读(38) |
20:09:16地址：http://acm.hdu.edu.cn/showproblem.php?pid=2511题意：中文。mark：递归。代码：# include &stdio.h&void gao(long long n, long long time, int s, int e){ int m = 6-s- long long mid = (1LL&&(n-1)) ; if (time == mid) { printf (&%I64d %d %d\n&, n, s, e) ; } ...
Seraph2012 阅读(62) |
19:19:52地址：http://acm.hdu.edu.cn/showproblem.php?pid=2565题意：中文，模拟。代码：# include &stdio.h&# include &string.h&char graph[100] ;void output (int n){ memset (graph, ' ', sizeof (graph)) ; for (i = 0 ; i & i++) { memset(graph, ' ', sizeof(graph)) ; gr
Seraph2012 阅读(39) |
19:02:16地址：http://acm.hdu.edu.cn/showproblem.php?pid=2561题意：中文。mark：可以排序，不过也可以扫一遍。用a记录最小值，b记录次小值，更新。代码：# include &stdio.h&int main (){ int T, a, b, i, n, scanf (&%d&, &T) ; while (T--) { scanf (&%d&, &n) ; a = b = 1000 ; for (i = 0 ; i & i++)
Seraph2012 阅读(29) |
19:13:38地址：http://acm.hdu.edu.cn/showproblem.php?pid=2566题意：中文。。。mark：题目没给数据范围，实在蛋疼，水了一下。考虑到如果有n个硬币，全都是1或2，能组成[n,2n]区间内任何一个数。所以枚举面额为5的硬币个数，然后计算剩下的面额是否在剩下的1、2硬币组成的面额区间内。15ms。那个dp[]数组没用，一开始看错题了。代码：# include &stdio.h&int dp[] = {1, 1, 2, 3, 5, 9} ;int main (){ int T, i, n, m, nn, mm, a
Seraph2012 阅读(132) |
18:58:25地址：http://acm.hdu.edu.cn/showproblem.php?pid=2562题意：中文。有点不明确，其实就是第0个和第1个互换，第二个和第三个互换。。。代码：# include &stdio.h&char str[100] ;int main (){ int T, scanf (&%d&, &T) ; while (T--) { scanf (&%s%*c&, str) ; for (i = 0 ; str[i] ; i+=2) printf (&%c%..
Seraph2012 阅读(33) |
18:53:55地址：http://acm.hdu.edu.cn/showproblem.php?pid=2564题意：中文。。。没啥好说的，处理就行了。代码：# include &stdio.h&char str[1000] ;void output(char str[]){ for(i = 0 ; str[i] ; i++) { if ((i == 0 || str[i-1] == ' ') && str[i] != ' ') putchar (str[i] & 0xDF) ; }}i
Seraph2012 阅读(37) |
18:44:21地址：http://acm.hdu.edu.cn/showproblem.php?pid=1548题意：有一个奇怪的电梯，只有2个按钮，上和下。第i楼层有一个值Ki。假设在第i层，按上它会向上走Ki层，按下也一样。如果超过n层或少于1层，则原地不动。问从第a层到b层需要几次操作。mark：BFS之。代码：# include &stdio.h&# include &string.h&int aa, bb,int k[210] ;int q[210] ;int step[210] ;void bfs(){ int a, fron
Seraph2012 阅读(48) |
18:20:59地址：http://acm.hdu.edu.cn/showproblem.php?pid=2102题意：中文。。。mark：你大爷的WA+TLE一共11次才AC。做了至少8个小时。一开始以为是要在严格的T时刻到达才可以，考虑了不可回头和可回头两种情况，dfs之，TLE。。。然后加奇偶剪，还是TLE。之后搜了搜，发现时T时刻以内到都可以，然后拍了个BFS。WA。WA了n次以后才发现时空传送是一定要传送的，不是自己选可以传也可以不传的。然后还WA，想是不是真的要在T时刻才能过，然后加了奇偶剪枝（因为回头路的话可以无限延长时间），还WA。最后发现一个trick是
Seraph2012 阅读(70) |
10:46:23地址：http://acm.hdu.edu.cn/showproblem.php?pid=1240题意：给n*n*n的三维迷宫，求从起点到终点的最短步数。mark：bfs搞之。注意起点和终点也可以是'X'的情况。代码：# include &stdio.h&# include &string.h&char graph[15][15][15] ;int step[15][15][15] ;int q[1010][3] ;int tab[6][3] = { {-1, 0, 0}, {1, 0, 0}, {0, -1,...
Seraph2012 阅读(47) |
10:01:00地址：http://acm.hdu.edu.cn/showproblem.php?pid=1238题意：给n个字符串，要求找字符串符合该串是所有给出的字符串或给出字符串的反串的子串的。求最大长度。mark：先在输入的时候顺便存储所有串的反串，然后枚举第一个串的所有子串，最后kmp比较。代码：# include &stdio.h&# include &string.h&char ss[110][110] ;char sr[110] ;int next[110] = {-1} ;void getnext(char str[
Seraph2012 阅读(88) |
01:58:02地址：http://acm.hdu.edu.cn/showproblem.php?pid=1239题意：给m、a、b。求一对素数p,q(p&q)使得p*q&=m且p/q &= a/b。若有多对，输出p*q最大的一对。mark：刚开题看了半天，才看明白啥意思。看到m是10w，然后case是2000组，一下懵了，以为不能枚举。后来冷静分析下，其实可以。以下是几个比较重要的结论&分析。1）若m' = p*q，则必不存在另外一对素数p'，q'使得m' = p' * q'。2) 若p固定，q要
Seraph2012 阅读(82) |
19:52:14地址：http://acm.hdu.edu.cn/showproblem.php?pid=2141题意：给一串ai、bj、ck，一串x，问x是否能表示成ai+bj+ck。mark：不会，搜了一下。把ai+bj存起来。然后二分x-ck。。。复杂度应该是O(500*500 + lg(0)好极限。代码：# include &stdio.h&# include &stdlib.h&int a[510], b[510], c[510] ;int ab[510*510] ;int cmp(const void *a, con
Seraph2012 阅读(42) |
19:16:59地址：http://acm.hdu.edu.cn/showproblem.php?pid=2563题意：中文。递推。代码：# include &stdio.h&int dp[25][2] = {1, 0} ;int main (){ int i, for (i = 1 ; i &= 20 ; i++) { dp[i][0] = dp[i-1][0] + dp[i-1][1] ; dp[i][1] = dp[i][0] + dp[i-1][0] ; } scanf (&%d&, &n) ; ...
Seraph2012 阅读(58) |
18:25:02地址：http://acm.hdu.edu.cn/showproblem.php?pid=1597题意：中文。。。mark：要用long long。代码：# include &stdio.h&# include &math.h&int main (){ long long n, scanf (&%I64d&, &n) ; while (~scanf (&%I64d&, &n)) { a = (sqrt(1.0+8.0*n)-1) / 2 ; if (a*(a+1)/2
Seraph2012 阅读(110) |
17:35:04地址：http://acm.hdu.edu.cn/showproblem.php?pid=1799题意：中文。mark：其实就是组合数。。。因为m重循环就是在n个数字里选n个作为变量。。。代码：# include &stdio.h&int dp[] ;void init(){ int i, dp[0][0] = 1 ; for (i = 1 ; i &= 2000 ; i++) { dp[i][0] = 1 ; for (j = 1 ; j &= j++) ...
Seraph2012 阅读(119) |
16:59:50地址：http://acm.hdu.edu.cn/showproblem.php?pid=2078题意：中文，不说了。其实和m没关系。代码：# include &stdio.h&int main (){ int T, i, n, m, a, scanf (&%d&, &T) ; while (T--) { scanf (&%d%d&, &n, &m) ; min = 100 ; for (i = 0 ; i &i++) { scanf ...
Seraph2012 阅读(29) |
16:33:11地址：http://acm.hdu.edu.cn/showproblem.php?pid=2089题意：中文。。。mark：直接打表可过。代码：# include &stdio.h&int dp[1000010] ;int test (int num){ while (num) { if (num % 10 == 4 || num % 100 == 62) return 0 ; num /= 10 ; } return 1 ;}int main (){ int n, m, i ...
Seraph2012 阅读(80) |
16:20:20地址：http://acm.hdu.edu.cn/showproblem.php?pid=2152题意：中文。mark：dp搞起。代码：# include &stdio.h&# include &string.h&int dp[110][110] ;int main (){ int n, m, a, b, i, j, while (~scanf (&%d%d&, &n, &m)) { memset (dp, 0, sizeof(dp)) ; dp[0][0] = 1 ; for (i =
Seraph2012 阅读(28) |
02:41:06地址：http://acm.hdu.edu.cn/showproblem.php?pid=2203题意：中文，字符串比较。mark：把第一个串复制一次接在自己后面。然后字符串比较。据说数据很水？！我就暴了一下，结果TLE。。。好吧，刚学了KMP，用上试试，果断0ms，威力果然不小，开心。代码：# include &stdio.h&# include &string.h&char s1[200010], s2[100010] ;char buff[100010] ;int next[100010] = {-1} ;void getne
Seraph2012 阅读(70) |
23:20:50地址：http://acm.hdu.edu.cn/showproblem.php?pid=2304题意：说墙上一开始有一个插座。给n个接线板，每个有若干个可以用的插口，问能获得多少个插口。代码：# include &stdio.h&int main (){ int T, n, o, scanf (&%d&, &T) ; while (T--) { scanf (&%d&, &n) ; ans = 1 ; while (n--) { scanf ...
Seraph2012 阅读(62) |
23:07:25地址：http://acm.hdu.edu.cn/showproblem.php?pid=2317题意：给出不放广告的收入，放广告的收入和广告的花费，问结果。代码：# include &stdio.h&int main (){ int a, b, scanf (&%d&, &n) ; while (n--) { scanf (&%d%d%d&, &a, &b, &c); if (b-c & a) puts (&advertise&qu
Seraph2012 阅读(54) |
13:51:00地址：http://acm.hdu.edu.cn/showproblem.php?pid=2554题意：中文，有点绕但是能看懂，不多说了。mark：着实不会，看了网上的规律觉得好扯淡。n%4的余数是3或0的就是Y，否则是N。。。不知道怎么来的，打表也只能看到前12项，之后就非常慢了。代码（C编译）：main(n){while(scanf(&%d&,&n),n){puts((n+1)&2?&N&:&Y&);}}打表的程序也贴一下吧：# include &stdio.h&
Seraph2012 阅读(97) |
22:32:38地址：http://acm.hdu.edu.cn/showproblem.php?pid=2555题意：中文。不多解释。mark：此题真是坑爹。数据里有多个矩形覆盖一个点的情况- -。。。如果有这种情况，就算前一个矩形的周长。。。另外，在矩形边上也算是包含在陷阱内。代码：# include &stdio.h&# include &string.h&# include &stdlib.h&typedef struct point{ int x,}point pt[20010] ;int a[110][
Seraph2012 阅读(72) |
09:55:00地址：http://acm.hdu.edu.cn/showproblem.php?pid=2560题意：给n*m的0-1矩阵，问有多少个1。。。mark：这么水的题好爽！代码：# include &stdio.h&int main (){ int T, n, m, i, num, scanf (&%d&, &T) ; while (T--) { scanf (&%d%d&, &n, &m) ; sum = 0 ; for (i = 0 ; i & n* i+
Seraph2012 阅读(38) |
09:47:29地址：http://acm.hdu.edu.cn/showproblem.php?pid=1907题意：n堆石子，每次取走其中一堆的任意颗，最后一个取的人败，求判局势。mark：anti-nim，开始以为很简单，其实很难分析，搞了好久。具体可以参见2009年国家集训队贾志豪的论文。这里先给出anti-nim的结论：先手必胜当且仅当：1)sg值为0且不存在一堆sg值大于1；2)sg不为0且存在至少一堆sg值大于1。代码：# include &stdio.h&int main (){ int T, n, num, sg, scanf
Seraph2012 阅读(37) |
16:18:37地址：http://acm.hdu.edu.cn/showproblem.php?pid=2553题意：求n皇后放置的种类数。mark：因为n才10，所以直接dfs。代码：# include &stdio.h&int n, dp[11] = {0, 1} ;int ans, num[11] ;int col[11], diag[30], indiag[100] ;void dfs(int pos){ int i, if (pos == n) { ans ++ ; } for...
Seraph2012 阅读(41) |
16:40:47地址：http://acm.hdu.edu.cn/showproblem.php?pid=2082题意：中文。mark：YY了一个dp。dp[i][j]表示前i个字符组成价值为j的种类数，有dp[i][j] = dp[i-1][j-k*i]，k∈[0,a[i]]。a[i]是第i个字符的最大个数。最后把dp[26]的所有值（0除外）加起来就ok了。代码：# include &stdio.h&# include &string.h&int dp[30][60] ;int a[30] ;int main (){ int T, i, j,
Seraph2012 阅读(23) |
15:46:58地址：http://acm.hdu.edu.cn/showproblem.php?pid=1326题意：n个高矮不等的堆。每次可以从一个堆拿一块移动到另一堆。问最少移动多少次能使他们全都相等。mark：好经典的题目，不记得在哪儿看到过不只1次了。每个和平均数的差加起来除以二。代码：# include &stdio.h&int num[60] ;int abs(int n){return n&0?-n:n;}int main (){ int i, sum ,ans, nCase = 1 ; while (~scanf (&qu
Seraph2012 阅读(70) |
16:05:53地址：http://acm.hdu.edu.cn/showproblem.php?pid=1329题意：有n个棍子，依序从1开始放小球，两个相邻的球编号和必须是完全平方数。求最后一个能放下的序号。mark：最多才1300，直接模拟。代码：# include &stdio.h&# include &string.h&# include &math.h&int dp[55] ;int issquare(int a){ int b = sqrt(1.0*a) ; return b*b ==}int gao
Seraph2012 阅读(90) |
15:02:12地址：http://acm.hdu.edu.cn/showproblem.php?pid=1267题意：中文。刚开始没看懂，注意“总”字。代码：# include &stdio.h&long long dp[21][21] ;int main (){ int i, j, m, for (i = 0 ; i &= 20 ; i++) dp[0][i] = 1 ; for (i = 1 ; i &= 20 ; i++) for (j = j &= 20 ; j++) dp[i]...
Seraph2012 阅读(54) |
15:16:26地址：http://acm.hdu.edu.cn/showproblem.php?pid=1287题意：这题的题意很让人莫名。其实是说存在一个大写字母x，然后让原文（都是大写字母）和x做xor后得到密文。现在给密文求原文。因为x不知道，所以枚举x。判断方法是判断是否解密出来的原文都在'A'-'Z'范围内。代码：# include &stdio.h&int num[10010] ;int test (int x){ for (i = 0 ; i & i++) if ((n
Seraph2012 阅读(104) |
14:25:01地址：http://acm.hdu.edu.cn/showproblem.php?pid=1220题意：一个n*n*n的立方体，被切割成1*1*1的小块。两两配对，问两块公共点不超过2的对数。mark：先算出总对数，减去共面的对数。顶点8个，每个共面3对，棱12条，每条有n-2个方块，每个方块共面4对，非顶点非楞的面上小方块，每个共面5对，一共6个面，每个面有(n-2)^2个这样的小方块。剩下的内部小方块每个共面6对。最后总共面数要除以2，因为每对算了2次。代码：# include &stdio.h&int calc (int n){ int
Seraph2012 阅读(116) |
13:44:49地址：http://acm.hdu.edu.cn/showproblem.php?pid=1862题意：中文，排序。代码：# include &stdio.h&# include &stdlib.h&# include &string.h&typedef struct student{ char num[7] ; char name[9] ;}student stu[100010] ;int cmp1(const void *a, const void *b){ student
Seraph2012 阅读(38) |
14:03:37地址：http://acm.hdu.edu.cn/showproblem.php?pid=1165题意：模拟图中给出的函数计算。mark：直接记忆化肯定会爆栈。写几行就发现，m=0,1,2的规律了。m=3的时候直接爆。代码：# include &stdio.h&int mem[25] = {5, 13} ;int A(int m, int n){ if (m == 0) return n+1 ; if (m == 1) return n+2 ; if (m == 2) return n*2+3 ; if (mem[n] != 0) ...
Seraph2012 阅读(25) |
13:30:48地址：http://acm.hdu.edu.cn/showproblem.php?pid=1015题意：在给定字符集中选5个字符(v,w,x,y,z)使得满足v - w^2 + x^3 - y^4 + z^5 = target。输出字典序最大的一个。mark：dfs。1WA。一开始以为是字符集中序数}
我要回帖
更多推荐
- ·伊利好还是飞鹤奶粉好和伊利奶粉哪个好？可以说说你家买的是哪款吗？
- ·陕西优艺墨堂家庭教育课程机构的专家导师怎么样?了解的人说一下，谢谢！
- ·孩子出汗厉害是缺锌还是缺钙睡觉出汗很多，说是有点缺钙，他她成长钙效果怎么样？
- ·请问备孕男宝夫妻想备孕男孩需要怎么调理身体呢？怎么快速怀孕？
- ·大家都给孩子吃什么长高最快D3，他她成长D3效果怎么样？
- ·a certain cat named和be named cow has been a member of my
- ·是去去监察委还是留检察院？
- ·钻孔灌注桩钢筋笼打到钢筋了怎么办？
- ·学中药学考研学校排名的人考研可以选择针灸推拿嘛
- ·南昌市学校老师办辅导班举报家教向哪里举报2014年
- ·醛的对甲基苯甲醛结构简式式是直接cho，还是需要o需在c上并加双键？
- ·i hope toapt get gradeood grade in the f_exam
- ·成均馆大学水原校区的演艺艺术专业在哪个校区？
- ·2017湖南省考分数线理科艺术一本分数线
- ·与海外名校联合招生方案的学校
- ·网络赌钱平台求个地址
- ·谁能给我写一个生管实习生每天干什么吗?
- ·《剧情谁做主》的高中学费多少作文
- ·京溪南方医院小学有提供早午餐吗
- ·小米2sroot权限会出现什么情况
- ·‘’尼玛,少在那装逼。巨大少女与小人国总喜欢得志,我理解你。‘’用英语�
- ·高考答题卡样式破损
- ·35岁的青少年驼背如何纠正也可以做矫正吗？
- ·小孩子 飞蚊症症眼前有小典影飞来飞去
- ·胸12胸11椎体压缩性骨折折3分之1
- ·肚脐上有痣边有两痣，脐眼上约1cm左右？
- ·天津保康医院肾病专家市第一中心医院看肾病怎么样
- ·有4个小朋友故事大全他们的年龄一个比一个大1岁他们的年龄的积是360，年龄最大的小朋友故事大全几,？
- ·这些是什么字？！请清宫表准吗专家解答答！
- ·哪里孕妇需要补充哪些营养充
- ·上火口臭吃什么能好好;帮忙我一下吧谢谢!!
- ·肛门有肛门长了个肉疙瘩瘩;大家用什么认真答.
- ·长痔疮是什么样子的的;请大家帮帮忙吧.
- ·小孩胃火大口臭吃什么药药;告诉我可以吗!!
- ·痔疮的痔疮手术治疗方法法;找到一个法不是运气!!.
- ·晚上夜里老是睡不着着怎么办
