Beawin-CSDN博客

原创【混合dp I】Partitioning by Palindromes

题目来源：题目大意：对于给定的字符串，找出里面回文子串最小的总数（也就是说单个回文子串要尽可能长）规定单独一个字符可成为一个回文子串解题思路：dp，一维。一开始习惯开了二维最后判断超麻烦，仔细想想其实一维就行了啊xdp[i]：表示前i个字符里回文子串数最小的总数状态转移方程：dp[i] = min(dp[i], dp[j-1]+1)一开始dp[i]里的数值为i，即前i个字符里最多有i个回文子串每次...

2018-04-16 23:29:27 217 1

原创【数学基础03】Raising Modulo Numbers

题目来源：http://poj.org/problem?id=1995题目大意：计算(A1B1+A2B2+ ... +AHBH)mod M解题思路：模运算法则和倍增快速幂AC代码：#include <stdio.h>#include <stdlib.h>#define N 45010#define M 4long long ppp(long long a, long...

2018-03-05 21:02:38 255

原创【数学基础01】Playing with Paper

题目来源：http://codeforces.com/problemset/problem/527/A题目大意：折纸游戏。给一张长a宽b的纸（a>b），沿着比较短的那条边折，直到a=b为止解题思路：边除边余。记得判断a和b的长短。如果一开始a就是b的倍数的话直接a/b就好。说起来一开始以为算约的次数就好，迷之捣鼓了很久呢= =AC代码：#include <stdio.h>#in...

2018-02-27 18:05:30 238

原创【STL基础05】The Blocks Problem

题目来源：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=37题目大意：给出n-1个按标号顺序排列的木块，放在0~n-1个位置，根据以下四条命令进行相应操作move a onto b：把木块a、b上的木块放回原位，再把a放到b上； ...

2018-02-27 16:50:33 333

原创【简单搜索04】Booksort

题目来源：题目大意：给出n本排成一列的书的编号1~n（非顺序），通过移动一摞书插入其他书中间最终实现将书按编号排序，求最小移动次数。解题思路：迭代加深搜索。自己写怎么都不对orz跑去看了n个大佬的思路总算有个看懂的orz试着改过直接修改maxd的值而不是通过函数返回的形式但样例二和三老是死循环orzzz，有时间再看了改一下吧。AC代码：#incl

2018-02-03 17:05:40 409

原创【简单搜索02】生日蛋糕

题目来源：题目大意：做一个体积为Nπ，M层的蛋糕，要求是下一层的R和H比上一层的大。求在给定的N、M下蛋糕最小的表面积。做题的时候没饿，写题解的时候饿了……【。解题思路：dfs可行性剪枝。一开始就想到两个简单条件，剩余的体积不够了和目前的面积大于已设定的最小面积。TLE……qaq然后再追加条件剩余的理想最大体积小于实际剩余体积。碎碎念：说起来

2018-02-03 10:47:39 367

原创【简单搜索01】N皇后问题

题目来源：题目大意：在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。你的任务是，对于给定的N，求出有多少种合法的放置方法。解题思路：回溯法。要先打表，不然TLE。自觉已经精简到最简了结果还是TLE的痛苦人民得到大佬的提示要先打表，真的想以头抢地了orz

2018-02-02 15:57:37 204

原创【二分与三分06】Elevator Stopping Plan

题目来源：题目大意：一个公司只有一部电梯，电梯运行4s/层，停留10s/层（最顶层不用计算停留时间），人爬楼20s/层。给出n个人要停留的层数（按从低层到高层顺序），要使最后到达的人花费时间最小，那么怎么安排在哪些楼层停留？解题思路二分法。用一个数组表示停留层数，停的层为1，其他为0（因为设的全局数组所以每次开始前要清空），并记录停留的top层是

2018-02-02 11:21:41 360

原创【二分与三分05】Squares

题目来源：题目大意：给出n个点，判断这n个点能组成几个正方形。解题思路：排序+二分查找。枚举对角线的两个点，算出中点，再算出另外两个个对角线的点的坐标，带到原序列中查找是否有这样的点。因为枚举查找超时所以用二分，但一开始的序列不是顺序所以先用qsort排序。由于查找过程中会出现重复，所以查找完毕之后要将结果/2。PS：虽说一开始点是整数，但中

2018-02-01 11:09:11 201

原创【二分与三分03】Copying Books

题目来源：题目大意：将n本页数为p1，p2，……，pm（顺序排列）的书分给k个抄写员抄写，每个抄写员速度一样且每个抄写员只能抄写编号相邻的书，求抄写时间最少的分组。解题思路：二分法与贪心。通过二分法求出一个抄写员最多需要抄写的页数，然后按照这个页数来分组，前面的组尽量分得多一点。初始下界和上界是最后一本书的页数和所有书的总页数。分组标记的时候

2018-02-01 00:21:50 261

原创【二分与三分04】Ultra-QuickSort

题目来源：题目大意：通过交换两数位置对数列进行排序，求把一串数列化为有序的最小的交换次数。解题思路：归并排序求逆序对。（同Brainman，只是格式和数据范围不一样）P……Plus Ultra？？（固有幻视x）AC代码：#include #include #include #define N 500010long long c[N],

2018-01-31 17:34:06 240

原创【二分与三分02】Brainman

题目来源：题目大意：通过交换两数位置对数列进行排序，求把一串数列化为有序的最小的交换次数。解题思路：归并排序求逆序对。↑虽然是这样说，不过第一次写好痛苦啊忘了考虑一边排完一边还剩这种情况，而且还改一半天都没发现 AC代码：#include #include #include #define N 1010int ans;

2018-01-31 16:24:07 199

原创【二分与三分01】Cable master

题目来源：题目大意：把n段绳子切成k段x长度的绳子，求x的最大值。解题思路：二分法。绳子总长/k为x的期望，x不会大于这个期望。AC代码：#include #include #include #define N 10010int n, k;double c[N];int check(double mid){

2018-01-31 14:17:15 312

原创【STL基础07】HDU-1263-水果

题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=1263题目大意：将水果按照产地→种类（数量）的字典序输出。解题思路：二维map，迭代器遍历。又一个明明我的代码和别人差不多但为什么别人A我W系列（。map定义在全局是需要每次都clear的。AC代码：#include #include

2018-01-30 17:36:52 263

原创【STL基础06】UVA-10815-Andy's First Dictionary

题目来源：https://cn.vjudge.net/problem/UVA-10815题目大意：找出文本里各不相同的单词然后按顺序排列。解题思路：用set，set中元素唯一（集合概念）且有序。PS：分隔单词的不只有空格/空行（stringstream可把所有非单词字符转为空格），新的一行Ctrl+Z算结束。代码以后有时间会改成C++，求放过

2018-01-30 15:41:33 388

原创【STL基础04】UVA-10474-Where is the Marble?

题目来源：https://cn.vjudge.net/problem/UVA-10474题目大意：有几块标着数字的大理石，把它们顺序排列，给出几个数字，找出首个编号与这些数字相同的大理石在序列中的位置。解题思路：STL sort和lower_bound(由于博主还不太习惯C++所以自己造了个破烂轮子结果最后还造错了（十次WA贡献给写错的排序算

2018-01-30 15:23:17 240

原创【STL基础03】HDU-1237-简单计算器

题目来源：https://cn.vjudge.net/problem/HDU-1237题目大意：读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。解题思路：用栈。3个char数组，一个double数组，c1保存计算式，c2暂时保存读到的数字，在读到数字后第一个空格时将c2整体转化为浮点数（atof）压入d中，重置c2，读到

2018-01-30 15:05:01 345

原创【STL基础02】UVA-673-Parentheses Balance

题目来源：https://cn.vjudge.net/problem/UVA-673题目大意：每个“（”或“[”是否有对应的“）”或“]”与之相匹配。解题思路：用栈。如果遇到“（”或“[”，则压入栈，如果遇到“）”或“]”，则与栈顶元素进行匹配，配对成功则将栈顶元素弹出栈，不成功no，最后栈中元素为零yes，不为零no。AC代码：#inclu

2018-01-30 14:45:21 298

原创【STL基础01】HDU-1702-ACboy needs your help again!

题目来源：https://cn.vjudge.net/problem/HDU-1702题目大意：编程实现栈（stack）和队列（queue）。解题思路：栈（先进后出），队列（先进先出）。AC代码：#include #include #include #define N 100#define M 10void FIFO(c

2018-01-30 14:16:09 227

雄英通信站