算法课作业2 OJ for Divide and Conquer

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++];elsebox[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");		elseprintf("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..
....
*/

G - Maximum Subarray Sum

题意

最大连续子序列和

思路

简单题，注意开long long和可能超int

#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);}
}