Previous Posts
-
十二 13, 2011
No Commentshdu 1271 整数对
整数对，比赛时完全没想到这想的方法，只是一味去暴力，结果当然难逃超时的命运，然后只可以放弃。 看了别人的解题报告，才知道所以然，还看了很久 思路：设A是一个合适的的数的话，则将A分成三个部分 A = a+b*10^k+c*10^(k+1);k表示去掉A的第k位数 得B = a+c*10^(k+1); N = a*2+b*10^k+c*11*10^(k+1);利用这种结构，去枚举N的每一位就可以，这里还不明白就去研究下代码啦，笨，是木有办法的说，我就是其中一个………… #include <iostream> #include <set> using namespace std; int N; set<int> res; int main() { while(cin >>N && N) { res.clear(); for(int k = 1;k <= N;k *= 10) { int a,b,c; int temp = N/k; c = temp/11; b = temp%11; if((b >...
-
十二 12, 2011
No Commentshdu 2579 Dating with girls(2)
又来贴题了，此题不是自己想出来的，看了大，自己根本不知道要如何处理，墙会消失这一点，一直纠结……，想不到竟如此简单………… 开个三维数组标记mark[x][y][time%k] ，代表x,y这点在time%k时是否走过，因为如果time%k相同的话以后的状况将会重复之前走过的状况 #include <iostream> #include <queue> #define MAX 110 #define K 11 using namespace std; struct State { int x,y; int time; }; inline bool operator<(const State& lh,const State rh) { return lh.time > rh.time; } const int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}; char Grah[MAX][MAX]; bool mark[MAX][MAX][K]; int Row,Col,k; inline bool Judge(const State& Now) { if(Now.x...
-
十二 08, 2011
No Commentshdu 1560 dfs(迭代加深)
第一次接触迭代加深搜索的思想：每次dfs,都给定其一个遍历时最大深度，一旦达到这个深度则退出搜索。 别人都说它结合的深搜和广搜的优点，我着实不是很明白，每次都会对之前的所有层次重新遍历一次，我认为这样是什么浪费时间的事情。我理解是，它限制深度时可以防止盲目加深深度，最后导致时间空间都无法承受的情况，因为有时候你并不能估计到解的深度，盲目一个方向深搜的话可能一直找不到解，然后又要回溯，或者要很深的深度才找到解，这和空间，时间就什分可怕。而每次限制了深度就可以遍历这个深度下的所有可能情况，可能就已经找到了一个解，就不必要加深深度了。总之一句话，我觉得其最大的作用就是防止盲目加dfs造成的深度过大而导致空间我时间都无法承受的情况。 这题的代码： #include <iostream> #include <string> using namespace std; const string DNA = "ACGT"; string Str[10]; int Depth; //迭代搜索限制的深度 int Pos[10]; int nStr; int ans; void Dfs(int mlen,int Pos[]) {//cout <<mlen <<' '; if(mlen > Depth) return ; int Max = 0; for(int i = 0;i < nStr;i++) {//cout << Pos[i] <<' '; //最长还要加深多少...
-
十二 02, 2011
No Commentshdu 1059 多重背包
虽说是用单调队列优化，平均O(VN)的算法，不过大概是用STL实现的原因，竟不如，大牛背包九讲里面的二进制思想优化来得快，再一次见证的STL的小小悲哀。 单调队列优化的代码（用了取模，不过听说这个可以AC不过却是错误的）： #include <iostream> #include <deque> #define MAX 360005 using namespace std; int dp[MAX]; int iNums[7]; deque<int> Index,Value; int main() { int work = 0; while(true) { bool IfEnd = true; int iBag = 0; for(int i = 1;i <= 6;i++) { cin >>iNums[i]; iNums[i] %= 2; //技巧，取余，否则超时 iBag += i*iNums[i]; if(iNums[i] > 0) IfEnd...
-
十二 02, 2011
No Commentshdu 2546 饭卡
选最贵的那个用5元买，其余的n-1种菜就是简单的01背包问题了 证明：假设最后买的价钱是v1并不是最贵的，最贵的假钱为vmax,最后总消费为v1+max1，第一，如果max1中不包含最贵的那种则将max1+vmax > v1+max1是必然的;如果max1包含最贵的vmax，也就是说我选不选最贵的最后买，都会买了最贵的，这样就相当时，除最贵的菜种，其余n-1种是在不超过m-5中尽可能地多消费。 #include<iostream> #include<algorithm> #define N 1001 using namespace std; int dp[N*2]; int meal[N]; int main() { int n,m; int iBag; while(cin >>n && n) { for(int i = 0;i < n;i++) { cin >>meal[i]; } sort(meal,meal+n); cin >>m; iBag = m-5; if(m < 5) { cout <<m <<endl; continue; } memset(dp,0,sizeof(dp)); for(int...
-
十二 02, 2011
No CommentsMFC学习篇-CFileDialog
CFileDialog 派生自 CCommonDialog 1.构造函数 explicit CFileDialog( BOOL bOpenFileDialog, //TRUE代表打开对话框，FALSE代表另存为对话框 LPCTSTR lpszDefExt = NULL,//设置默认打开或另存为的文件后缀 LPCTSTR lpszFileName = NULL,//设置默认打开或保存的文件名 DWORD dvFlags =...
-
十一 23, 2011
No CommentsHDU 2955 Robberies
以后要抢银行记得打妈咪 01背包的变形，这里由于概率是小数，不可以用像01背包那样直接用其作状态，所以从其取得的值入手，状态转移方程为:dp[i][j] = max{dp[i-1][j],dp[i-1][j-w[i]]*v[i]},其中dp[i][j]表示从前i个银行中抢到j的钱存活的最大概率，w[i] 为第i个银行的钱，v[i]为抢第i个银行时不被抓的概率。 用滚动数组实现，注意一下初始化，其实这个初始化还是值得研究下的说 #include<iostream> #define N 101 #define MAX 10001 using namespace std; int iaValue[N]; double daWeight[N]; double daDpMax[MAX]; double dBag; int iNBanks; int main() { int iCases; cin >>iCases; while(iCases--) { cin >>dBag >>iNBanks; int Max = 0; for(int i = 0;i < iNBanks;i++) { cin >>iaValue[i] >>daWeight[i]; daWeight[i] = 1-daWeight[i];...
-
十一 23, 2011
No CommentsHDU 1557 权利指数
大概是题目数据弱，还是我感觉有问题2^20次方的复杂度不会超时？各种暴各种过，什么母函数，二进制代表状态什么的……………… 深搜，不敢说是水过的，虽然看起来的确水，大概是我自己也水吧 #include<iostream> #define N 21 using namespace std; int iNGroups; int iaTickets[N]; int iaResult[N]; bool bVisted[N]; int iAve; //int count; void Dfs(int sum,int k) { if(k >= iNGroups) {//count++; if(sum > iAve){//if(bVisted[0] && sum-iaTickets[0] <= iAve) cout <<sum <<' '; for(int i = 0;i < iNGroups;i++) { if(bVisted[i] && sum-iaTickets[i] <= iAve) iaResult[i]++; }...
-
十一 21, 2011
No CommentsHDU 2191 单调队列优化
从什么是单调队列开始，看到我都有点蛋疼了，其实单调队列是个很简单的数据结构，它的伟大在于区间求最值时间平摊下来可达到O(n),对许多DP问题可以特到很好的优化效果，而多重背包就是其中之一。我是看dd大牛的背包九讲的说，哎~~别人一个高中生就如此强大，自卑啊 其实网上对于多重背包用单调队列优的内容很少，说是这样说，在此我也不想多讲，因为没理解透的说，在此推荐一篇文章（国家队论文的说，又是一个牛B的高中生）：http://wenku.baidu.com/view/8ab3daef5ef7ba0d4a733b25.html 我说一点，就是一定要明白到，对于DP[j*v+d] 的最大值一定只可能由 DP[(j-k)*V+d]得到，k为这物品取多少件，d当然就是余数 看代码吧： #include<iostream> #include<deque> #define MAX 101 using namespace std; int n,m; int iaPrice[MAX],iaWeight[MAX],iaNum[MAX]; deque<int> Index,Value; //单调队列，分别用于保持下标与权值单调 int iaDpMax[MAX]; int main() { int iCases; cin >>iCases; while(iCases--) { cin >>n >>m; for(int i = 0;i < m;i++) { cin >>iaPrice[i] >>iaWeight[i] >>iaNum[i]; } //多重背包 memset(iaDpMax,0,sizeof(iaDpMax)); for(int i = 0;i < m;i++)...
-
十一 19, 2011
No Commentshdu 1251 统计难题-trie树-字典树
以前就一直听淳淳说字典树，字典树什么的，感觉好似好神奇，一直没有搞，终于在USACO看到一题，然的找了个PPT定了这题 ，原来还是很好理解的，不过这应该只是字典树最最基本的应用字典树，应用在字符处理上是这么叫，不过它的应用应远不止于 此，所以还是喜欢叫它作Trie树，就字典树而言，它以公共前缀的方式保存字符串，节省了不少空间，而且便于统计，每个节 点保存的是字符串中的一个字母。当中有个域n表示字树的数量。哦，忘了，一棵m度的Trie树或者为空，或者由m棵m度的Trie 树构成。 还是看代码吧，才刚开始做，不好总结的说： #include<iostream> #include<string> using namespace std; class TrieTree{ public: void insert(const string&); int research(const string&); TrieTree(); private: TrieTree* Child[26]; int nChilds; }; TrieTree::TrieTree() { nChilds = 0; for(int i = 0;i < 26;i++) { Child[i] = NULL; } } void TrieTree::insert(const string& hl) { TrieTree* Current; TrieTree* NewNode; Current =...