https://vjudge.net/contest/581947
A - Ultra-QuickSort
题意
每次给n个无序的数，互不重复，问最少需要多少次必要的交换操作使n个数有序。
思路
看一眼想到逆序数，然后验证了逆序数的个数符合样例，但想了一个3 2 1的话实际上只需要交换一次，但题意说的是必要交换次数也不一样是最优的交换次数，那样就太难了。
于是就简化问题求一个序列逆序数的个数，就用归并了上课讲过，可以在归并拆分返回的时候进行求逆序对，求逆序对两种，一种求每个数的右边比它小的数的个数，一种求每个数左边比它大的个数，我用第二种做的，归并返回的时候，两个数组都是有序的可以求右边的数组中每个元素，对于左边一共有几个比他大的，代码能力还行，wa了一次因为数组开的int 归并一次就写对了，我感觉我又行了哈哈哈。
#include<cstring>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=500005;
long long a[maxn],box[maxn];
long long ans;
void mergesort(int left,int right)
{
if(left>=right) return;
int mid=(left+right)/2;
mergesort(left,mid);
mergesort(mid+1,right);
int j=left;
for(int i=mid+1;i<=right;i++)
{
while(a[j]<a[i]&&j<=mid)
{
j++;
}
ans=ans+mid-j+1;
}
int i=left;
j=mid+1;
int t=1;
while(i<=mid&&j<=right)
{
if(a[i]<=a[j])
box[t++]=a[i++];
else
box[t++]=a[j++];
}
while(i<=mid)
box[t++]=a[i++];
while(j<=right)
box[t++]=a[j++];
t=1;
for(int i=left;i<=right;i++)
a[i]=box[t++];
}
int main()
{
int n;
while(scanf("%d",&n)&&n!=0)
{
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
ans=0;
mergesort(1,n);
// for(int i=1;i<=n;i++)
// printf("%d ",a[i]);
// printf("\n");
printf("%lld\n",ans);
}
return 0;
}
B - Hanoi Tower Troubles Again!
题意
给n个柱子，这个人要从第一根柱子到第n个柱子挨个往上面放球，球编号从1开始递增，要求两个相邻球编号和为完全平方数。
思路
简单模拟题
#include<cstring>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int box[55];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
memset(box,0,sizeof(box));
int i=1;
while(1)
{
int flag=0;
for(int j=1; j<=n; j++)
{
if(box[j]==0)
{
box[j]=i++;
flag=1;
break;
}
else
{
int k=(int)sqrt(box[j]+i);
if(k*k==(box[j]+i))
{
box[j]=i++;
flag=1;
break;
}
}
}
if(flag==0)
break;
}
printf("%d\n",i-1);
}
}
C - Fibonacci Again
思路：模拟题
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000005;
int f[MAXN];
int main()
{
f[0]=7;
f[1]=11;
for(int i=2;i<=1000000;i++)
f[i]=f[i-1]%3+f[i-2]%3;
int t;
while(scanf("%d",&t)!=EOF)
{
if(f[t]%3==0)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
E - Fire Net
题意
给n*n(n<=4)的格子，格子上可能有墙，或者为空地，空地可以建设碉堡，碉堡可以上下左右射击，射不穿墙，问最多可以建设多少碉堡？
思路
DFS模拟简单题
一共最多16个格子嘛，我就是从上往下，从左往右，挨个尝试每个位置，然后对于每个位置能不能安装，只需要扫描它的上方和左方是否有碉堡就可以啦，注意一下边界就好。
#include<cstring>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int m[10][10];
int n;
int ans;
void dfs(int start,int cnt)
{
if(start>n*n)
{
ans=max(ans,cnt);
// if(cnt>=4)
// {
// for(int i=1; i<=n; i++,printf("\n"))
// for(int j=1; j<=n; j++)
// printf("%d ",m[i][j]);
// printf("\n");
// }
return;
}
int row=(start-1)/n+1;
int col=(start-1)%n+1;
for(int i=start; i<=n*n; i++)
{
// 取
if(m[row][col]!=1)
{
int flag=1;
for(int j=col-1; j>=1&&m[row][j]!=1; j--)
if(m[row][j]==2)
{
flag=0;
break;
}
for(int j=row-1; j>=1&&m[j][col]!=1; j--)
if(m[j][col]==2)
{
flag=0;
break;
}
if(flag)
{
m[row][col]=2;
dfs(i+1,cnt+1);
m[row][col]=0;
}
}
// 不取
dfs(i+1,cnt);
}
return;
}
int main()
{
while(scanf("%d",&n)&&n!=0)
{
ans=0;
getchar();
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
char c;
scanf("%c",&c);
if(c=='.') m[i][j]=0;
else m[i][j]=1;
}
getchar();
}
for(int i=1; i<=n*n; i++)
{
dfs(i,0);
}
printf("%d\n",ans);
}
}
/*
4
.X..
....
XX..
....
*/
F - Gridland
题意
给n*m的房子，四通八达，距离都是1，旅行商问题
思路
看奇数和偶数，偶数可以正好跑回去，奇数需要走个斜边
#include<cstring>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
for(int i=1;i<=T;i++)
{
int m,n;
scanf("%d%d",&m,&n);
printf("Scenario #%d:\n",i);
double t=m*n;
if((m*n)%2==0)
printf("%.2lf\n",t);
else
printf("%.2lf\n",t-1+sqrt(2));
printf("\n");
}
}
G - Maximum Subarray Sum
题意
最大连续子序列和文章来源：https://www.toymoban.com/news/detail-722770.html
思路
简单题，注意开long long和可能超int文章来源地址https://www.toymoban.com/news/detail-722770.html
#include<cstring>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=2e5+5;
int a[MAXN];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
long long maxx=0;
long long ans=a[1];
for(int i=1;i<=n;i++)
{
maxx=maxx+a[i];
ans=max(maxx,ans);
if(maxx<0) maxx=0;
}
printf("%lld",ans);
}
J - Beat the Spread!
#include<cstring>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int a,b;
scanf("%d%d",&a,&b);
if((a+b)%2)
{
printf("impossible\n");
continue;
}
int maxx=(a+b)/2;
int minn=a-maxx;
if(maxx<0||minn<0)
{
printf("impossible\n");
continue;
}
printf("%d %d\n",maxx,minn);
}
}
到了这里，关于算法课作业2 OJ for Divide and Conquer的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
