金币阵列问题
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 110;
int a[N][N], b[N][N], temp[N][N];
int n,m;
//对temp进行行变换
void changeRow(int x)
{
for(int i = 1;i <= m;i ++)
{
temp[x][i] ^= 1;
}
}
//交换temp中的两列
void changeCol(int x,int y)
{
for(int i = 1;i <= n;i ++)
{
int t = temp[i][x];
temp[i][x] = temp[i][y];
temp[i][y] = t;
}
}
//将a数组copy到temp数组中
void copy()
{
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
temp[i][j] = a[i][j];
}
//判断temp[][]数组的第x列与b[][]数组的第y列是否相同
bool isSame(int x, int y)
{
bool flag = true;
for(int i = 1;i <= n;i ++)
if(temp[i][x] != b[i][y])
{
flag = false;
break;
}
return flag;
}
int get()
{
int res = 0;
//将第一列通过行变换转换成b[][]数组的第一列
for(int i = 1;i <= n;i ++)
if(temp[i][1] != b[i][1])
{
res ++;
changeRow(i);
}
for(int i = 2;i < m;i ++)
{
if(isSame(i, i)) continue;
for(int j = i + 1;i <= m;i ++)
{
if(isSame(j, i))
{
res ++;
changeCol(j, i);
break;
}
}
}
/*cout << res << " ++++ " << endl;*/
//判断最后一列是否相同
if(isSame(m, m)) return res;
return 0x3f3f3f3f;
}
int main()
{
int T;
scanf("%d", &T);
while(T --)
{
scanf("%d%d", &n, &m);
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
scanf("%d", &a[i][j]);
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
scanf("%d", &b[i][j]);
int ans = 0x3f3f3f3f;
for(int i = 1;i <= m;i ++)
{
//将a数组copy到temp中
copy();
int res = 0;
if(i != 1) res ++;
changeCol(1, i);//原来数组的第i列与第1列交换
res += get();
ans = min(ans, res);
}
if(ans == 0x3f3f3f3f) printf("%d\n", -1);
else printf("%d\n", ans);
}
return 0;
}
排列的字典序问题
题解
算出具体编号
我们可以从从开始算，因为不能有重复，以1开头的后面有7位数有17！，然后以2开头的后面有六位数，但第二位要小于6，即有1、3、4、5满足，有46！，然后以26...开头的后面有5位数，要求第三位要小于4，即有1，3满足，有2*5！，，，依次类推。。。
看例子：
tot=0；
比2小的数有1个，则 tot+=1*7！；
比6小的数有4个，则 tot+=4*6！；
比4小的数有2个，则 tot+=2*5！；
比5小的数有2个，则 tot+=2*4！；
比8小的数有3个，则 tot+=3*3！；
比1小的数有0个，则 tot+=0*2！；
比7小的数有1个，则 tot+=1*1！；
比3小的数没有；
（注：在排列中，求比某个数小的数的个数时，排除之前出现过的数）
找下一个序列的方法
找规律 + 二分
举例说明：3 4 5 2 1 --> 3 5 1 2 4
- 1、从末端往前找，找到第一个下降的元素的位置
k，即5 -> 4是下降的，因此找到4这个元素对应的位置1（从0开始） - 2、从
[k + 1,n - 1]区间中找到大于nums[k]的最小值，由于该区间具有单调性，可以用二分查找，找到了l == 5 - 3、交换
k和l位置的元素，即交换4和5，序列变成3 5 4 2 1 - 4、将
[k + 1,n - 1]区间的元素逆序，变成3 5 1 2 4
#include <iostream>
using namespace std;
void reverse(int a[], int l, int r)
{
while(l < r) swap(a[l ++], a[r -- ]);
}
int main()
{
int n ;
cin >> n;
int nums[n + 10];
for(int i = 0;i < n;i ++)
{
cin >> nums[i];
}
int fac[n + 10];
fac[0] = 1;
for(int i = 1;i <= n;i ++)
fac[i] = fac[i - 1] * i;
int res = 0;
for(int i = 0;i < n;i ++)
{
int cnt = 0;
for(int j = i + 1;j < n;j ++)
if(nums[j] < nums[i])
cnt ++;
res += cnt * fac[n - 1 - i];
}
cout << res << endl ;
//1、从右往左找到第一个下降的点k
int k = n - 2;
while(k >= 0 && nums[k] >= nums[k + 1]) k --;
if(k == -1)
{
reverse(nums, 0, n - 1);
}
else
{
//2、从[k + 1,n - 1]区间中找到 > nums[k] 的最小值
int l = k + 1,r = n - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(nums[mid] > nums[k]) l = mid;
else r = mid - 1;
}
//3、交换k和l的位置
swap(nums[k],nums[l]);
//4、将[k + 1,n - 1]区间的元素逆序
reverse(nums,k + 1,n - 1);
}
for(int i = 0;i < n;i ++)
cout << nums[i] << " " ;
cout << endl;
return 0;
}
石子合并问题
#include <iostream>
#include <cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 110;
int a[N];
int f[N][N];
int g[N][N];
int s[N];
int main()
{
int n;
cin >> n;
for(int i = 1;i <= n;i ++)
cin >> a[i];
//计算前缀和
for(int i = 1;i <= n;i ++)
s[i] = s[i - 1] + a[i];
for(int len = 2;len <= n;len ++)
{
for(int l = 0;l + len - 1 <= n;l ++)
{
int r = l + len - 1;
f[l][r] = INF;
g[l][r] = -INF;
for(int k = l;k < r;k ++)
{
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
}
}
}
cout << f[1][n] << endl;
cout << g[1][n] << endl;
return 0;
}
多元Huffman编码问题
#include<bits/stdc++.h>
using namespace std;
long long datas[100001];
int n;
long long maxNum,minNum;
// 两堆 合并 ，合并的费用为新的一堆的石子数
long long Max(int k){// 求最大的总费用:每次都要 找最大两堆 的进行合并
priority_queue<long long> q;//使用 优先队列 ，优先队列排序方式为大顶堆 。堆顶的为最大。所以 求 最大费用，则为 每次的堆顶的值 进行k=2 次合并
for(int i=0;i<n;i++) q.push(datas[i]);//将数据 存入优先队列
//最大费用 两两合并 最后的值 最优，所以 求最大k =2
while((int)q.size()>k){//两两合并， 若 优先队列里面的值的个数 大于两个 ，那么 对数据 进行k=2次堆顶相加 求和
long long sum=0;//sum 是两个 先后堆顶相加的值，合并之后，需要把sum 继续放进 优先队列里面 ，继续参与下面的合并
for(int i=0;i<k;i++){
sum+=q.top();//sum 加上堆顶的值
q.pop();//同时需要把这个 堆顶的值删除
}
maxNum+=sum;//最大合并 费用 更新
q.push(sum);//将合并的值 继续放进 优先队列 参与 下面的合并
}
while(!q.empty()){//合并 之后 优先队列（即堆） 里面还剩下 k =2 个 数据 这两堆合并 的费用 就是它们的两个的和
maxNum+=q.top();//最大费用值 + 剩余的 两对 合并费用 结束
q.pop();
}
return maxNum;//返回最大值
}
long long Min(int k){
//优先队列 默认的是大顶堆，求最小费用 需要用到 小顶堆
priority_queue<long long,vector<long long>,greater<long long> > q;//从小到大的顺序排列队列中的数据
for(int i=0;i<n;i++) q.push(datas[i]);
//算最小得分 最后留出k-1个数来合并才能得到最小值
int tmp=n;//tmp 代表 n 堆 石子 //可一下合并，费用最小，
//此判断 主要是 n 堆石子 大于 最大k堆 合并 ，要让前 x个数据 和k-x 个0 凑成k 堆，
if(tmp>k){
while(tmp>k){// tmp=n 能拆成 多少个 (k-1) 以及剩下tmp 个 数据
tmp=tmp-(k-1);
}
//下面 的 k-tmp 个0 和 剩下的 tmp 个数据 合并成 一堆。 然后 和已经拆成的(k-1)一堆 进行合并 成新的一堆，如此 (k-1) (k-1) (k-1).... 继续合并
for(int i=0;i<k-tmp;i++)//要让前面的k-tmp个数刚好能合并成1堆，需要加上k-m个零，用零来填充
q.push(0);
}
while((int)q.size() > k){
long long sum=0;
for(int i=0;i<k;i++){
sum+=q.top();
q.pop();
}// 个合并 合并之后的数据 放进 优先队列里面
minNum+=sum;
q.push(sum);
}//当m<=k的时候，可以一下合并，所以 最小费用 就是 各个之和
while(!q.empty()){//这里 minNum +剩余 的 k个 就是最小值； 相当于 minNum+ 最小的k个一次合并的值
minNum+=q.top();
q.pop();
}
return minNum;
}
int main()
{
int k;
maxNum=0;//初始化 最大 费用 0
minNum=0;//初始化 最小 费用 0
cin>>n>>k;//输入n堆石子，每次至少选2 堆最多选k堆石子合并
for(int i=0;i<n;i++){
cin>>datas[i];//输入n 堆石子 数据
}
maxNum=Max(2);//k =2 求最大 k=2
minNum=Min(k);//k 堆
cout<<maxNum<<" "<<minNum<<endl;
return 0;
}
最小重量机器设计问题
1、算法设计：
a.部件有n个，供应商有m个，分别用array2[i][j]和array1[i][j]存储从供应商j 处购得的部件i的重量和相应价格，d为总价格的上限。
b.用递归函数machine(i)来实现回溯法搜索排列树（形式参数i表示递归深度）。
① 若cp>d，则为不可行解，剪去相应子树，返回到i-1层继续执行。
② 若cw>=bestw，则不是最优解，剪去相应子树，返回到i-1层继续执行。
③ 若i>n，则算法搜索到一个叶结点，用bestw对最优解进行记录，返回到i-1层继续执行；
④ 用for循环对部件i从m个不同的供应商购得的情况进行选择(1≤j≤m）。
c.主函数调用一次machine(1)即可完成整个回溯搜索过程，最终得到的bestw即为所求最小总重量。
2.算法时间复杂度：
程序中最大的循环出现在递归函数mchine(i)中，而此函数遍历排列树的时间复杂度为O(n!),故该算法的时间复杂度为O(n!)。
#include<bits/stdc++.h>
using namespace std;
int n,m,d;
int array1[100][100];//cij
int array2[100][100];//wij
int cw=0;
int cp=0;
int bestw=1000000;
int x[100];//记录所选部门
int x1[100];
void machine(int t){
if(t>=n){
if(cw<bestw){
bestw=cw;
for(int i=0;i<n;i++){
x1[i]=x[i];
}
}
return;
}
for(int i=0;i<m;i++){
cp+=array1[t][i];
cw+=array2[t][i];
x[t]=i;
if(cp<=d && cw <=bestw){
machine(t+1);
}
cp-=array1[t][i];
cw-=array2[t][i];
}
}
int main()
{
cin >> n >> m >> d;
memset(x1,0,sizeof(x1));
memset(x,0,sizeof(x));
memset(array1,0,sizeof(array1));
memset(array2,0,sizeof(array2));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin >> array1[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin >> array2[i][j];
}
}
machine(0);
cout << bestw << endl;
for(int i=0;i<n;i++){
cout << x1[i]+1 << " ";
}
return 0;
}
n皇后问题
- 按行继续比遍历，其中
col[x],dg[y - x + n],udg[x + y]分别记录的是该位置的列，斜，反斜线上是否已经存在过，若均不存在，填入皇后，并递归到下一行
6fc1d403abbb3318b3d86d47d6ca9da.png
时间复杂度 )
#include <iostream>
using namespace std;
const int N = 20;
int g[N][N];
bool col[N], dg[N], udg[N];//dg表示正斜，udg表示反斜
bool dfs(int y,int n)
{
if(y == n)
{
for(int i = 0;i < n;i ++)
{
for(int j = 0;j < n;j ++)
{
if(g[i][j] == 1)
{
cout << j + 1 << " ";
break;
}
}
}
return true;
}
for(int x = 0;x < n;x ++)
{
if(!col[x] && !dg[y - x + n] && !udg[x + y])
{
g[y][x] = 1;
col[x] = dg[y - x + n] = udg[x + y] = true;
if(dfs(y + 1, n)) return true;
col[x] = dg[y - x + n] = udg[x + y] = false;
g[y][x] = 0;
}
}
return false;
}
int main()
{
int n;
cin >> n;
dfs(0, n);
return 0;
}
图片题解
依次遍历所有的猫，通过第u个数往现有的k个集合中放，遍历所有情况
第u个数往第1辆车放
第u个数往第2辆车放
…
第u个数往第k辆车放
新开集合，第u个数往第k + 1集合中放
网友评论