|
|
1 #include<iostream>
2#include<malloc.h>
3using namespace std;
4
5bool cmp(int &a,int &b)//sort函数的比较函数，若将"<"改为">"则为降序排列
6   {
7 return a<b;
8 }
9
10int comp(const void*a,const void*b)//C语言qsort的升序排序函数，将return语句的a,b互换则为降序排序
11{
12 return *(int*)a-*(int*)b;
13}
14
15void sel_sort(int *s,int n)//选择排序，分为有序，无序两部分。每次迭代中选择无序部分的最小元素，并移动到有序部分的尾部
16{
17 int i,j;
18 int min;
19 for(i=0;i<n;i++)
20  {
21 min=i;
22 for(j=i+1;j<n;j++)
23 if(s[j]<s[min])
24 min=j;
25 swap(s[i],s[min]);
26 }
27}
28
29void insert_sort(int *s,int n)//插入排序，分为有序，无序两部分。每次迭代中无序部分的下一个元素被插入到有序部分的何时位置。
30{
31 int i,j;
32 for(i=1;i<n;i++)
33 {
34 j=i;
35 while((j>0)&&(s[j]<s[j-1]))
36 {
37 swap(s[j],s[j-1]);
38 j--;
39 }
40 }
41}
42
43void quick_sort(int *s,int left,int right)//快速排序
44{
45 int r=right,l=left,p=s[right];
46 while(l<r)
47 {
48 swap(s[l],s[r]);
49 while(l<r&&s[r]>p)
50 r--;
51 while(l<r&&s[l]<=p)
52 l++;
53 }
54 swap(s[left],s[r]);
55 if(left<r-1)
56 quick_sort(s,left,r-1);
57 if(right>r+1)
58 quick_sort(s,r+1,right);
59}
60
61int main()
62{
63 int i,n;
64 int *a;
65 while(cin>>n)
66 {
67 //a=(int *)malloc(n*sizeof(int));
68 a=new int[n];
69 for(i=0;i<n;i++)
70 cin>>a[i];
71 sel_sort(a,n);
72 //insert_sort(a,n);
73 //quick_sort(a,0,n-1);
74 //sort(a,a+n,cmp);//c++排序库函数
75 //qsort(a,n,sizeof(int),comp);//c排序库函数
76 for(i=0;i<n;i++)
77 {
78 cout<<a[i];
79 if(i!=n-1)
80 cout<<",";
81 if(i==n-1)
82 cout<<endl;
83 }
84 }
85 //free(a);
86 delete(a);
87 return 0;
88}
1#include <iostream>
2#include<cmath>
3using namespace std;
4
5typedef unsigned long int ULI;
6
7bool stanWin(ULI n)
8{
9 if (2<=n&&n<=9)
10 return true;
11 else
12 return false;
13}
14
15int main()
16{
17 ULI n;
18 while(cin>>n)
19 {
20 while(n>18)
21 {
22 n=ceil(n/18.0);
23 }
24 if(stanWin(n))
25 cout << "Stan wins."<<endl;
26 else
27 cout << "Ollie wins."<<endl;
28 }
29 return 0;
30}
【题目大意】
给定一个n*n的棋盘，求放置k个互不攻击的象的方法数。其中n <= 8，k <= n ^ 2。
【题目分析】
对于棋盘放车问题可以用组合数学的知识来解决，但是对于含禁区的摆放问题，虽然组合数学给出了经典的棋盘多项式+容斥原理的解法，但是实际中棋盘多项式的求解是很困难的，因此一般需要借助状态压缩动态规划求解。
现在题目中要求出互不攻击的象的方法数，象的攻击路线是斜的，是不是可以考虑采用放车的方法来解呢？将棋盘黑白染色，如果一个象在黑色的格子里面，那么它一定不会攻击到白色的格子，这样的话可以分开计数，然后最后利用乘法原理加起来就行了。把棋盘旋转45度，这样象的攻击路线就是直的了，如果只考虑一种颜色的话，那么问题就转变成了经典的放车问题了，可以利用动态规划解决。
设dp[i][j]表示前i行放了j个车的方法数，c[i]表示第i行可以放置的棋子数量，那么转移方程为：
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * (c[i] - (j - 1))
需要注意的是c数组应该是增序的，这样才能保证前面的j-1行放了车，对应这一行就有j-1个位 1 #include<iostream>
2 #include<algorithm>
3 using namespace std;
4 const int N = 70;
5
6 void init(int n, int *c1, int *c2)//将棋盘分为黑白两个区域，使得相同颜色的才在象的攻击范围内
7 {
8 memset(c1,0,sizeof(int) * N);
9 memset(c2,0,sizeof(int) * N);
10 for (int i = 1; i <= n; i++)
11 {
12 for (int j = 1; j <= n; j++)
13 {
14 if((i+j)%2)//白色区域
15 c2[(i+j)/2]++;//第(i+j)/2斜行有几个白色格子
16 else//黑色区域
17 c1[(i+j)/2]++;//第(i+j)/2斜行有几个黑色格子
18 }
19 }
20 }
21
22 void bishops(int n, int dp[N][N], int c[N])//计算过程
23 {
24 int i,j;
25 for(i=0;i<=n;i++)
26 dp[i][0]=1;
27 for(i=1;i<=n;i++)
28 for(j=1;j<=c[i];j++)
29 dp[i][j] = dp[i-1][j]+dp[i-1][j-1]*(c[i]-j+1);
30 }
31
32 int main()
33 {
34 int n, k, c1[N], c2[N], dp1[N][N], dp2[N][N], ans,i;
35
36 while(cin>>n>>k)
37 {
38 if (n==0&&k == 0)
39 break;
40 init(n,c1,c2);
41 sort(c1+1,c1+n+1);
42 sort(c2+1,c2+n);
43 memset(dp1,0,sizeof(dp1));
44 memset(dp2,0,sizeof(dp2));
45 bishops(n,dp1,c1);
46 bishops(n-1,dp2,c2);
47 ans=0;
48 for(i=0;i<=k;i++)
49 ans+=dp1[n][i]*dp2[n-1][k-i];
50 cout<<ans<<endl;
51 }
52
53 return 0;
54 }
摘要: 1 /*
2
3 N皇后问题算法思想
4
5 由于这是一个平面上棋子布局处理问题，因此，我们可以将问题看成是一个二维数组问题。给八个皇后分别编号为1,2，…,8，其中第i个皇后放置在第i行上，并这就解决了不同皇后分别摆放在不同列的问题，这样又可以把问题简化为一个一维数组的问题，假设用一维数组arr来存放皇后所放置的列，对于第i个皇后，假设它存放在ar... 阅读全文
将问题转化为点A（0,0）是否在一个凸多边形内的问题........点是否在由其他点围成的多边形里的问题又转化为斜率的问题........
1 #include <cstring>
2 #include <iostream>
3 #include <string>
4 using namespace std;
5 typedef long llint;
6 llint const maxn = 1001;
7 bool repackage(llint pkgs[][3], llint p)
8 {
9 llint i;
10 for(i=0;i<p;i++)
11 {
12 pkgs[i][0] -= pkgs[i][2]; //转换为二维
13 pkgs[i][1] -= pkgs[i][2];
14 }
15 llint x1=pkgs[0][0], y1=pkgs[0][1],x2 = pkgs[0][0], y2=pkgs[0][1];
16 for (i = 1; i < p; i++)
17 {
18 llint x = pkgs[i][0], y = pkgs[i][1];
19 llint a1 = y1 * x, b1 = x1 * y, a2 = y2 * x, b2 = x2 * y;
20 if (a1 == b1)
21 if (x1 * x + y1 * y<=0)//如果两点在一条直线上且位于不同项限则（0，0）包含在凸包内
22 return true;
23 if (a2 == b2)
24 if (x2 * x + y2 * y <= 0)
25 return true;
26 if (a1 < b1)
27 x1 = x, y1 = y; //保存斜率大的
28 if (a2 > b2)
29 x2 = x, y2 = y; //保存斜率小的
30 if (x1==x2&&y1==y2)//(0,0)点包含在凸包内则“YES”
31 return true;
32 if (y1 * x2 == y2 * x1)
33 if (x1 * x2 + y1 * y2 <= 0)
34 return true;
35 if (y1 * x2 < y2 * x1)
36 return true;
37 }
38 return false;
39 }
40 int main()
41 {
42 llint pkgs[maxn][3],p,i;
43 while(cin>>p)
44 {
45 if(p==0)
46 break;
47 for (i=0;i<p;i++)
48 cin>>pkgs[i][0]>>pkgs[i][1]>>pkgs[i][2];
49 if (repackage(pkgs,p))
50 cout << "Yes\n";
51 else
52 cout << "No\n";
53 }
54 return 0;
55 }
/*刚拿此题时一头雾水，当看完一次同余方程时方才有点头绪.....后来在又在求最值问题上遇到麻烦。最后才在数学推导下才AC此题.....第一次深刻体会到数学对解题的重要性....下面说一下我的解题思路..... 1.首先通过Gcd函数求出n1,n2的最大公约数g以及满足条件的x,y: n1*x+n2*y=n;（递归运用:x0=1,y0=0;x=y1,y=(x1-n1/n2*y1)） 显然当n不能被g整除时显然没解....这里有一个问题：Gcd函数求出的x,y为什么刚好能使得|x|+|y|最小？？请求数学达人指导 2.求出满足条件的m1,m2使得m1*n1+m2*n2=n (1)：由1得,x*n1+y*n2=g (2)....结合（1（2）:m1=n*x/g+t*n2/g,m2=n*y/g-t*n1/g;这里的t是一个参数，但仍能满足（1）式。 3.由m1>=0,m2>=0可得他t1=<t<=t2;（注意t的取值必须为整数） 4.由c=c1*m1+c2*m==》c=num1+t*(c1*n2-c2*n1)....因此c的大小取决于c1*n2-c2*n1的正负以及t的值....之后的过程在代码中很明了了。 1 #include<iostream> 2 #include<math.h>
3 using namespace std;
4 long Gcd(long p,long q,long *x,long *y)
5 {
6 long x1,y1;
7 long g;
8 if(q>p)
9 return (Gcd(q,p,y,x));
10 if(q==0)
11 {
12 *x=1;
13 *y=0;
14 return p;
15 }
16 g=Gcd(q,p%q,&x1,&y1);
17 *x=y1;
18 *y=(x1-p/q*y1);
19 return g;
20 }
21 int main()
22 { 23
24 long n,c1,c2,n1,n2,x,y,gcd,t1,t2,t,a,b;
25 //freopen("c:\\in.txt","r",stdin);
26 // freopen("c:\\8522.out","w",stdout);
27 while(cin>>n)
28 {
29 if(n==0)
30 break;
31 cin>>c1>>n1>>c2>>n2;
32 gcd=Gcd(n1,n2,&x,&y);
33 t1=ceil(-n*(double)x/(double)n2);
34 t2=floor(n*(double)y/(double)n1);
35 if((t1>t2)||(n%gcd!=0))
36 {
37 cout<<"failed\n";
38 continue;
39 }
40 if(c1*n2>=c2*n1)
41 t=t1;
42
43 else
44 t=t2;
45 a=n*x/gcd+t*n2/gcd;
46 b=n*y/gcd-t*n1/gcd;
47 cout<<a<<" "<<b<<endl;
48 }
49 return 0;
50 }
摘要: 全排列的生成1 #include<iostream>
2 using namespace std;
3
4 const int MAX=100;
5 int a[MAX];
6 bool finished=false;//是否找到了所要全部求的解
7
8 void process(int *a,int n)
9 {
10 int i,fir... 阅读全文
|