Posts

转载自：http://www.cnblogs.com/vongang/archive/2013/03/10/2952978.html

昨天那道签到的数学题没搞出来不开心. 是时候刷一波数学了 这题题意是说,从n个数中任选m个,使得m个的和为c的倍数.

比赛的时候以为是贪心… 想了好久. 不过最后没敢写,因为没办法证明正确性,只是直觉==

如果问题中各数据的范围明确，那么无穷大的设定不是问题，在不明确的情况下，很多程序员都取0x7fffffff作为无穷大，因为这是32-bit int的最大值。如果这个无穷大只用于一般的比较（比如求最小值时min变量的初值），那么0x7fffffff确实是一个完美的选择，但是在更多的情况下，0x7fffffff并不是一个好的选择。

算是签到帖，竟然卡住了。 我数学还是太差了。。 然后去找题解。。竟然看不懂！

蠢了。 这道题显然可以搜。。 然后自己搜索的姿势果然还是不怎么地。。 最后是蔡大神过掉的。

TAG 素数 数论 素数总是一个比较常涉及到的内容，掌握求素数的方法是一项基本功。

dp方程想错了.果然还是欠练啊. 如果我们不考虑坏点,那么从 (0,0)到(x,y)的方案数是c(x+y,x)或者c(x+y,y)

问两个长度相同的字符串是否等价． 相等的条件是，两个字符串相等，或者两个偶数长度（因为要分成长度相同的两段，所以一定是偶数长度才可分）字符串平均分成两部分，每部分对应相等(不考虑顺序)

题意：给定一个六边形的六条边的长，问能分割成多少个单位正三角形．

1/************************************************************************* 2 > File Name: code/cf/#313/B.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: Wed 22 Jul 2015 09:52:54 PM CST 6 ************************************************************************/ 7 8#include<iostream> 9#include<iomanip> 10#include<cstdio> 11#include<algorithm> 12#include<cmath> 13#include<cstring> 14#include<string> 15#include<map> 16#include<set> 17#include<queue> 18#include<vector> 19#include<stack> 20#define y0 abc111qqz 21#define y1 hust111qqz 22#define yn hez111qqz 23#define j1 cute111qqz 24#define tm crazy111qqz 25#define lr dying111qqz 26using namespace std; 27#define REP(i, n) for (int i=0;i<int(n);++i) 28typedef long long LL; 29typedef unsigned long long ULL; 30 31 int a1,b1,a2,b2,a3,b3; 32bool judge (int x2,int y2,int x3,int y3) 33{ 34 if (x2<=a1&&x3<=a1&&y2+y3<=b1) 35 return true; 36 if (y2<=b1&&y3<=b1&&x2+x3<=a1) 37 return true; 38 return false; 39} 40int main() 41{ 42 cin>>a1>>b1>>a2>>b2>>a3>>b3; 43 if (judge(a2,b2,a3,b3)||judge(b2,a2,a3,b3)||judge(b2,a2,b3,a3)||judge(a2,b2,b3,a3)) 44 { 45 puts("YES"); 46 } 47 else 48 { 49 puts("NO"); 50 } 51 52 return 0; 53}

做过一道类似的题 因为是问最短，很容易想到是bfs 对于点x，可以到达点x-1,和点2*x

给一个字符串，问这个字符串中是否26个字母都出现过（大小写只出现一个就算出现过） 开个布尔数组，扫一遍即可。 嘛，做两道水题放松下== 反正也是要清的。

题意是说，给定一个有向图，对于每一条边，问是否是s到t的最短路上一定会经过的边．

很容易看出来是dp 我们左右一起，一对一对放． 对于每一对，有三种方法，分别是两左，一左一右，两右．

基础的搜索BFS和DFS,自己找题切吧… 高级搜索的题集就在下面,自己看着办吧…

＿＿＿＿＿＿ 好蠢，竟然没看出来这道题的不同之处，以为就是个搜 然后样例什么的都过了．．．

比赛的时候没搞出来，really sad. 其实这题很容易啊．．．． 首先，对于lie 的判断应该基于能放的船的个数． 能放的船的个数是随着射的点数的增加而减少的． 射完每个点后更新能放的船的个数，如果这个时候已经无法放下k条船了，说明lie了． 如果所有都射完也没发生，那么就-1.

1/************************************************************************* 2 > File Name: code/cf/#315/E.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年08月15日 星期六 13时48分36秒 6 ************************************************************************/ 7#include<iostream> 8#include<iomanip> 9#include<cstdio> 10#include<algorithm> 11#include<cmath> 12#include<cstring> 13#include<string> 14#include<map> 15#include<set> 16#include<queue> 17#include<vector> 18#include<stack> 19#define y0 abc111qqz 20#define y1 hust111qqz 21#define yn hez111qqz 22#define j1 cute111qqz 23#define tm crazy111qqz 24#define lr dying111qqz 25using namespace std; 26#define REP(i, n) for (int i=0;i<int(n);++i) 27typedef long long LL; 28typedef unsigned long long ULL; 29const int inf = 0x7fffffff; 30const int N=5E2+7; 31int flag[N],flag2[N]; 32int f[N][N]; 33int a[N]; 34char s[N]; 35int ans[N]; 36int len,n,m; 37char s1[13],s2[13]; 38int p1,p2,q1,q2,dq1,dq2; 39void add(int p,int q,int flag[]) 40{ 41 int dq = q * n + p;//找到元辅音状态为q，第p的点的下标 42 for (int i=1;i<=2*n;++i) 43 { 44 if (f[dq][i]==0) continue; 45 flag[i]=1;//找到所有由dp出发的边指向的点，表示选了dp点一定要选的点。 46 } 47} 48bool check(int flag[]) 49{ 50 for (int i=1;i<=n;++i) 51 if (flag[i]==1&&flag[i+n]==1) return false; //判断是否存在矛盾 52 //（选了j点后，既要选择某点k的元音，也要选择某点k的辅音）　53 return true; 54} 55bool dfs(int pos,int x) 56{ 57 if (pos>n) return true;//如果能形成一个长度为n的单词，说明这种语言有word 58 bool g[2]; 59 g[0]=g[1]=false; 60 for (int i=x;i<=len;++i)//从当前字母x往后枚举 61 { 62 for (int j=1;j<=2*n;++j) flag2[j]=flag[j];//为了不影响原始数组，复制一个布尔数组出来。 63 add(pos,a[i],flag2);//找到所有选了pos点一定要选的点 64 if (check(flag2)&&(!g[a[i]])) 65 { 66 g[a[i]]=true; 67 for (int j=1;j<=2*n;++j) flag[j]=flag2[j]; 68 ans[pos]=i;//将第pos位置的字母变成i 69 if (dfs(pos+1,1)) return true; 70 else return false;//只要有一位找不到合适的字母形成单词，那么肯定就构不成单词。 71 } 72 } 73 return false; 74} 75int main() 76{ 77 scanf("%s",s); 78 len=strlen(s); //0表示辅音，１表示原因，下同。 79 for (int i=1;i<=len;++i)//len 表示字母表中一共有的字母的个数 80 { 81 if (s[i-1]=='V') 82 { 83 a[i] = 0; 84 } 85 else 86 { 87 a[i] = 1; 88 } 89 } 90 memset(f,0,sizeof(f)); 91 scanf("%d%d",&n,&m); 92 for (int i=1;i<=m;++i)//1..n表示元音的点，n+1..2*n 表示辅音的点 93 { 94 scanf("%d",&p1); 95 scanf("%s",s1); 96 if (s1[0]=='V') q1=0;else q1=1; 97 scanf("%d",&p2); 98 scanf("%s",s2); 99 if (s2[0]=='V') q2=0;else q2=1; 100 dq1=q1*n+p1;dq2=q2*n+p2;//找到这组关系对应的点。 101 f[dq1][dq2]=1;//连一条由dq1指向dq2的边，表示如果选了dp1点，那么一定选dp2点　102 dq1=(1-q2)*n+p2;dq2=(1-q1)*n+p1;//找到逆否命题对应的点　103 // （"如果选１，一定选２"的逆否命题是，"如果不选２，一定不选１"） 104 f[dq1][dq2]=1; //在连一条边 105 } 106 for (int i=1;i<=2*n;++i) f[i][i]=1; 107 for (int k=1;k<=2*n;++k)//floyd ，把所有间接相连的边直接相连 108 { 109 for (int i=1;i<=2*n;++i) 110 for (int j=1;j<=2*n;++j) 111 f[i][j]|=f[i][k]&f[k][j]; 112 } 113 scanf("%s",s+1); 114 bool ok=false; 115 for (int i=n;i>=0;--i) //倒着扫，每次只改变最后一位的字母，字母从小往大枚举 //这样就可以保证字典序最小。 116 { 117 memset(flag,0,sizeof(flag)); 118 for (int j=1;j<=i;++j) 119 { 120 add(j,a[s[j]-'a'+1],flag); 121 ans[j]=s[j]-'a'+1; 122 } 123 if (!check(flag)) continue; 124 if (dfs(i+1,s[i+1]-'a'+1+1)) 125 { 126 ok=true; 127 break; 128 } 129 } 130 if (!ok) printf("-1\n"); 131 else 132 { 133 for (int i=1;i<=n;++i) printf("%c",ans[i]+'a'-1); 134 } 135 return 0; 136}

【2-SAT问题】 现有一个由N个布尔值组成的序列A，给出一些限制关系，比如A[x] AND A[y]=0、A[x] OR A[y] OR A[z]=1等，要确定A[0..N-1]的值，使得其满足所有限制关系。这个称为SAT问题，特别的，若每种限制关系中最多只对两个元素进行限制，则称为2-SAT问题。