黑书 p116页上有详细的分析 代码 如下： #include <iostream> #include <math.h> using namespace std; int grid[8][8]; int d[16][9][9][9][9]; int sm[9][9]; int const INF=10000000; int n; int sum(int i,int j,int s,int t) { return sm[s][t]-sm[i][t]-sm[s][j]+sm[i][j]; } int comp(int a,int b,int c) { ...

着道题看起来是一个三维的背包问题,但是注意一个条件,就是每个组件只能放在地x到第x+w的位子上所以这时问题就可以简化复杂度,即只对第i个组件在第x位置上时的价值为j时的f最大值求解。 方程为 f[i][L][C]=max{f[i-1][L][C],f[i-1][L-w][C-c]+F[i]且L-w=x}; 还要注意个地方就是dp的顺序，x越小越i值越小 #include <iostream> #include <algorithm> using namespace std; int l,n,b; //int x,w,f,c; int F[1001][1...

1.先作出这个数的常规意义下的所有因子,再验证这些因子是否满足特定的素因子的条件. 2.用线形筛法筛出可能的素因子,hash或者二分查找. #include <iostream>#include <algorithm>using namespace std; int a[300001];int ans[60000];void prime(int n){ a[0]=1; a[1]=1; for(int i=2;i*i<=n;i++) { if(a[i]==0&amp;&amp;(i%7==1||i%7==6)) { for(int j=i*i;j<=n;j+...

这道题是最长上升序列。 由于给出的数据量过大，不能直接使用dp的方法来去最长升序，因为这样的时间为0（n^2） 下面我们考虑如下的情况： 对于第i个数来说他是否是1……i的最长上升序列的元素，就是在1……i-1中的最长上升序列最后一个值比f[i]小，那么f[i]元素就为1……i上的最长上升序列的元素。 如过不存在1……i-1的最长上升序列满足上述情况时，我们不能直接认为i就1……n上的最长升序列。这是我们可以这样的假设，假设f[i]是1……n的最长生序列的元素。那么f[i]在1……n的最长升序列的位置应该在1……i-1的最长生序列中比f[i]小的最大的元素...

dP+高精度 c[i]=c[i-1]+2*[i-2]; 这个最优的东西我是很难自己想到的，我是看报告过的。 这个转移方程，是在太痛苦了。 #include <iostream>using namespace std;int c[250][100]={0};void high_int(int m,int n,int k){ int i, index=0; for(i=99;i&amp;gt;=0;i--) { c[m][i]=(c[n][i]+c[k][i]+c[k][i]+index)%10; index=(c[n][i]+c[k][i]+c[k][i...

首先，我认为他是邪恶的，有一组邪恶的数据，害我wa了很多次。 方法就是使用贪心+bfs来实现的。 主要是要先把度数的点搜索之后在去搜索其他点。 这题花了我一晚上，几下来的时候都快两点了。 #include <iostream>#include <queue>using namespace std;const int maxn=210;typedef struct nn{ bool u; bool d; bool l; bool r; bool index; int num; bool ur; bool dr; bool lr; bool rr; }N...

就是求各种进制下求mod; m没有超给过long int 的界限，所以可以直接装换成long int 行 但是p很大。 我的方法是把每一位提出来求mod, 比如输入为2 11001 1000 变成(1*2^4modm+1*2^3modm+1modm)mod m 代码： #include <iostream>#include <math.h>using namespace std;__int64 mod(__int64 a,__int64 b){return (a%b+b)%b;}__int64 ctoi(char *a,int bb){ __int64 ans...

这题的数量过大，我能想到的就只有离散化。 然后我试着从左到右的直接算出来，很不幸超时。 最后在万般无赖的情况下，只好使用线段树来构造。 开始的时候我还想本着优化程序的原则，没有把线段树当作树状数组来使用，但是很不幸的是错了很久我都不知道为什么。 后来发现了以后，直接把每个都下到最底层（本来还是有优化的，但是废去了一个晚上，我也就不想什么有化不优化的了） 哎~~~~~~ 代码写得非常的有问题，没有严格测试过，慎用！！！ #include<cstdio>#include<cstring>#include<algorithm>#include<iostre...

这道题是典型的凸包题 关于凸包的算法可以去http://baike.baidu.com/view/707209.htm这里看到。 题目的意思就是求凸包周长再加上一个圆的面积. 这到题让我知道了，原来排序是sort（）和qsort()都是不稳定的，为此我wa了很多次。 最后还是做出来，不容易啊。 代码： #include <iostream>#include <algorithm>#include <vector>#include <math.h>#define pi 3.141592653589using namespace std;typ...

2352 Stars xiedi.rar(204 KB) 这道题我是用的线段树的特例，点数来完成的，算法可以看附件中，谢迪大牛的PPT。 源代码： #include <iostream>using namespace std;typedef struct Node{ int l,r; int count;}node;class PointTree //点数类{ private: node p[1<<18]; public: void init_tree(int l,int r...

广度搜素，用链表写的，代码很差，时间也很慢。不知道还有什么好方法，貌似是有的，有人用0ms过了。 #include <iostream>int chess[301][301]={0};using namespace std;typedef struct bound{ int x; int y; int count; struct bound *next; }Set;int main(){ int n; cin >>n; while(n--) { int l...

这是一道不错的数学题，开始的时候就只想到于三进制有关系，由于还有一个最优化的问题……开始还以为需要用到深搜的策略。 但是正确的解法却也是因为三进制才没有使用深搜的策略。 以三进制表示一个数： 1.如果数位上为1，则应该在右侧放上一个权值。 2.如果数位上为2，则该在左侧放上一个权值。 3.如果位数上为0，则什么都不需要做。 源代码： #include <iostream>#include <vector>#include <math.h>using namespace std;int main(){ int n; cin ...

贴道值得研究的题吧，虽然有人给出了解法,也总结出很多规律,可还是没有看到很好的证明 大意是把整数N分成不相等的任意个整数,使这些数乘积最大 有人总结了一些规律: 1.1<a1if a1=1, then a1(=1), a[t] together could be replaced by a[t]+1.reason: a[t]+1>a[t]*1 ----------------------------------------------------------------------------------------2.to all i, 1<=a[i+1]-a[i]...

给提示 XXX XXX OOO XOO OO. X.X XOO O. . X.. yes no yes 就这么点要注意的： #include <iostream>char winner[9];char toe[3][3];int X,O;int legal;using namespace std;bool islegall(){ legal=0; if((X!=O+1)&amp;&amp;(X!=O)...

用到了KMP的一些思想，主要就是求next[]函数 Problem: 2406 User: keloy Memory: 28648K Time: 282MS Language: C++ Result: Accepted Source Code #include <iostream> #include <string> using namespace std; string t; int Getnext() { int n=t.size(); int *next=new int[n+1]; int i=...

主要的思想是贪心， 用d做半径，小岛的点做圆心，圆和x轴上相交得到的区间就是可以包含这个小岛的radar,可以存在的位子。 排序，找到最多重叠点或区间，得到答案。 数据里头很变态，有d为负的情况。 在qsort的时候要注意因为用的是浮点数。 我是在wa了很多次之后终于过了…… #include <iostream>#include<math.h>#include<algorithm>using namespace std; typedef struct sea{ int x; int y;} Sea;typedef struct Radar{ ...

动态规划： 不要想当然的以为最小值就是0，（o(∩_∩)o...）我就是这么wa了一次。 代码： #include <iostream>using namespace std;long sum[101]={0};long tempsum[101]={0};long bunch[101][101]={0};long max(int i, int j)//求最大值{ long temp=-2147483648; for(int s=i;s<=j;s++) { if(sum[s]>temp) temp=sum[s]; } return temp;}void...

程序代码来自redcastle,我看了很多的关于一元同余方程的解释，都不是很名白，今天在redcastle的博客上看到了他的解释恍然大悟，终于把1061给AC了，http://hi.baidu.com/redcastle/blog/item/e6dc30d3a5574d023af3cfe0.html是代码， http://hi.baidu.com/redcastle/blog/item/934b232dbc40d336349bf7e4.html关于一元同余方程的解释。 我还是把我代码写出来 #include <iostream>using namespace...

最小生成树，题目的意思很明白，有几种方法写最小生成树，但我只会一种还把名字给忘了（呵呵）-_-!!!! #include <iostream>#define INF 0xffffffint line[27][27];int n;int count;bool contain[27];int sum;using namespace std;void initialize(){ for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) { if(i==j) line[i][j]=0; else line[i][j]=INF; } memset...

这题开始的时候就用n=log1+log2……logn,为了不超时还打了了一张表，结果很搞笑，超界了-_-!!!! 于是去看了下其他人的解题报告看到了一种方法就是使用Stirling公式。 但是这个是一个在n趋近于无穷的是后的公式，所以先还是要用前面的等到可能要超界了是后才用stirling公式。 源代码 ： #include <iostream>#include <math.h>#define maxn 100001const double e = 2.7182818284590452354, pi = 3.141592653589793239;doubl...