现在位置: 首页 > 算法 > 文章
2019年11月09日 算法 ⁄ 共 2372字 评论关闭
Time Limit: 1000 mSec    Memory Limit : 32768 KB Problem Description Year 2900. Many people left Earth and built some cities on Mars. Currently there are N cities, some of which are connected by narrow one-way roads. The president of Mars has decided to build police stations throughout the Mars. Given the cost of building police stations at each city, we cannot build them at all cities, d...
阅读全文
2019年11月09日 算法 ⁄ 共 1300字 评论关闭
受下列文章启发: http://kukumayas.iteye.com/blog/1075610 http://blog.csdn.net/lyy289065406/article/details/6646007 把每一行每一列都当成一个节点来看待,把每个外星人的坐标当成一条边看待, 这样就可以把问题转化成求“最小点覆盖”,由于König定理,再转换成求“最大二分图匹配”, 于是就可以用匈牙利算法。匈牙利算法有一个核心概念就是找增广路,如果有增广路, 则匹配加一,而找增广路的核心就是一个交差树的概念。 ...
阅读全文
2019年11月09日 算法 ⁄ 共 2805字 评论关闭
//纯模拟 #include<iostream> #include<cstring> using namespace std; int map[101][101],A,B; struct node { char direction; int x,y; }; node robot[101]; bool judge; void F(int no,int repeat) { int i; map[robot[no].x][robot[no].y]=0; if(robot[no].direction=='N') for(i=1;i<=repeat&&(0<robot[no].y&&robot[no].y<=B)&&map[robot[no].x][robot[no].y]==0;i...
阅读全文
2019年11月08日 算法 ⁄ 共 2133字 评论关闭
啊……怎么说好呢……就这样吧…… *题目大意: * 一个1*M的棋盘上有N个棋子,初始位置一定,两人轮流操作, * 每次移动一枚棋子,要求只能向左移且至少移动一格,而且不 * 能到达或经过以前有棋子的格子,谁无法移动棋子就算输。 *解题思路: * 先考虑两个棋子靠在一起的时候,这两对棋子就构成了一个 * 奇异局势(P点)。所以可以把题目中的棋子分解为两对两对, * 两对两对之间是不需...
阅读全文
2019年11月08日 算法 ⁄ 共 2501字 评论关闭
圆上依次从0到n-1标记点,给出m个边,问当这m个边连好之后,是否有相交的 边有园外园内之分…… 2-SAT #include<iostream> #include<map> #include<string> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<queue> #include<vector> #include<algorithm> using namespace std; const int MAXN = 510; struct twosat { in...
阅读全文
2019年11月08日 算法 ⁄ 共 2408字 评论关闭
每对夫妻恰有一人坐在新娘对面,两个关系不正常的人不能都在新娘对面 问,是否有解 #include<iostream> #include<map> #include<string> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<queue> #include<vector> #include<algorithm> using namespace std; const int MAXN = 100; struct twosat { int n,c; vecto...
阅读全文
2019年11月08日 算法 ⁄ 共 1935字 评论关闭
点为0或1,看满足m个条件时,是否有解 #include<iostream> #include<map> #include<string> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<queue> #include<vector> #include<algorithm> using namespace std; const int MAXN = 1010; struct twosat { int n,c; vector<int> g[MAXN<<1]; ...
阅读全文
2019年11月08日 算法 ⁄ 共 1935字 评论关闭
点为0或1,看满足m个条件时,是否有解 #include<iostream> #include<map> #include<string> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<queue> #include<vector> #include<algorithm> using namespace std; const int MAXN = 1010; struct twosat { int n,c; vector<int> g[MAXN<<1]; ...
阅读全文
2019年11月08日 算法 ⁄ 共 1846字 评论关闭
给出一个n*m的棋盘,及一个小的矩形1*2,问用这个小的矩形将这个大的棋盘覆盖有多少种方法。 dp[i][j]:有多少种方法,可以使得第i行的状态为j dp[i][j]=sum{dp[i-1][k],k可以通过合法变化变成状态j} 0:该位置空余 1:该位置被占 有的人问,每个位置不是3种状态吗?即不放矩形,横放一个矩形,竖放一个矩形 当然了,这样定义状态也是可以的,用三进制。 用三进制的话,位运算什么的都要手写比较麻烦…… 还是二进制吧,那为何...
阅读全文
2019年11月06日 算法 ⁄ 共 2206字 评论关闭
这道题一看是大数题就知道不会做,就看了一下其他人的解题报告,千篇一律的做法: 首先把大数变成千进制数用整形数组存起来,其实所谓千进制就是每三位数当作一位数处理。 然后从小到大枚举所有小于L的素数,用同余模的各种知识对这个转换后的千进制数进行求余,这个所谓同余模处理,其实就是,设两个正整数a,b,c,有(a+b)%c=(a%c+b)%c,至于证明的话, 我不会。 最后呢,如果余数为0那么输出BAD 比L小的K质因子,如果不是的话...
阅读全文