Posts

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

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

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个字母都出现过（大小写只出现一个就算出现过） 开个布尔数组，扫一遍即可。 嘛，做两道水题放松下== 反正也是要清的。

将博客搬至CSDN

题意是说，给定一个有向图，对于每一条边，问是否是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问题。

D. Symmetric and Transitive time limit per test 1.5 seconds memory limit per test 256 megabytes input standard input output standard output Little Johnny has recently learned about set theory. Now he is studying binary relations. You’ve probably heard the term “equivalence relation”. These relations are very important in many areas of mathematics. For example, the equality of the two numbers is an equivalence relation.

http://baike.baidu.com/link?url=nsN1-rcs3Gs0jNurWLSDk6AJ9jmhl_3pfkQmYK7vZoe7BsoTij48Si3It9XeNM4uA7gST-1ITQsAx0bv5si9_q