訓練賽題解

A、最少攔截系統
A題是一個最長遞增子序列的題，因為題問最少需要多少攔截系統，對于每個攔截系統來說，它們所能包含的就是一組非遞增子序列，所以對于兩組中的數字來說，一定能找到后一組中的一個數字大于前一組一個數字，所以根據這個結論可得分成的組數就是所給數中的最長遞增子序列，每個數都屬于一個系統，這是一個dp的題，可以用dp來解，不過也有針對最長遞增子序列的更便捷的演算法就是如下，利用的原理就是上面講的原理，

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<math.h>
#include<vector>
#define ull unsigned long long 
using namespace std;

int main(){
	int n;
	while(cin>>n){
		vector<int>v;
		int a;
		for(int i=0;i<n;i++){
			cin>>a;
			if(v.empty()||a>v[v.size()-1]) v.push_back(a);
			else{
				int k=lower_bound(v.begin(),v.end(),a)-v.begin();
				v[k]=a;
			}
		}
		cout<<v.size()<<endl;
	}
}

B、ACboy needs your help again!
B題就是一個用stl佇列的模擬題，這個題過的還挺多的，挺好

#include<iostream>
#include<stdio.h>
#include<string>
#include<algorithm> 
#include<vector>
#include<stack>
#include<queue>
typedef long long ll;
using namespace std;

int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		string a;
		cin>>n>>a;
		if(a=="FIFO"){
			queue<int>q;
			string b;
			int c;
			while(n--){
				cin>>b;
				if(b=="IN"){
					cin>>c;
					q.push(c);
				}else{
					if(q.empty()){
						cout<<"None"<<endl;
						continue;
					}
					cout<<q.front()<<endl;
					q.pop();
				}
			}
		}else{
			stack<int>s;
			string b;
			int c;
			while(n--){
				cin>>b;
				if(b=="IN"){
					cin>>c;
					s.push(c);
				}else{
					if(s.empty()){
						cout<<"None"<<endl;
						continue;
					}					
					cout<<s.top()<<endl;
					s.pop();
				}
			}
		}
	} 
} 

C、青蛙的約會
C題是一個擴展歐幾里得演算法的題，題中說讓兩個青蛙見面，設兩個青蛙的步差為a，緯線長度是l，兩個蛙的距離為c，且緯線首位相連，可以一直繞，所以則若兩個青蛙可以見面則 ax = c + ly 存在解，所以可得要ax + ly = c 有解，所以就要用擴展歐幾里得演算法來求x和y，再倍增，最后再取余，取余的原因是 原式=（x1+k×l/g)×a+y×l= c = x1×a+k×l×a/g+y×l=c = x1×a+(k×a/g+y)×l=c，這樣就可以得到x的最小值，（題解字母含義和題中不一定一樣，這個題要注意負數情況）

#include<iostream>
#include<algorithm>
#include<cstring>
#include<math.h>
#include<map>
using namespace std;

long long ex_gcd(long long a,long long b,long long &x,long long &y){
	if(!b){
		x=1;
		y=0;
		return a;
	}
	long long d=ex_gcd(b,a%b,y,x);
	y-=x*(a/b);
	return d;
}

int main(){
	long long x,y,m,n,l;
	cin>>x>>y>>m>>n>>l;
	long long c=y-x;	
	long long g=ex_gcd(m-n,l,x,y);
	if(c%g||!(m-n)){
		cout<<"Impossible"<<endl;
		return 0;
	}
	x*=c/g;
	long long t=l/g;
	if(t<0) t=-t;
	x=(x%t+t)%t;
	cout<<x<<endl;
}

D、Inversion
D題題意是要讓陣列變有序交換k次后最少還要交換幾次，對于一個無序陣列兩兩交換變成有序許需要交換的次數就是整個陣列的逆序數，逆序數求法很多，這個題我是用歸并演算法求逆序，當然大家有其他方法也都可以，原理就是歸并在每次合并時若前比后大，則逆序應該是前面陣列的后面所有數個數，因為是從前往后合并的，且一組內是有序的，前比后大，那前的后也比后大，就這樣求逆序就可以了，

#include <iostream> 
#include <algorithm>
#include <vector> 
#include <string.h>
using namespace std;
const int maxn=1e5+7;
int a[maxn],b[maxn];
long long ans;
void un(int l,int mid,int r){
	int t=l,k=mid+1,u=l;
	while(u<=mid&&k<=r){
		if(a[u]>a[k]){
			b[t++]=a[k++];
			ans+=(long long)(mid-u+1);
		}
		else b[t++]=a[u++];
	}
	while(u<=mid) b[t++]=a[u++];
	while(k<=r) b[t++]=a[k++];
	for(int i=l;i<=r;i++){
		a[i]=b[i];
	}
}
void sortt(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1;
	sortt(l,mid);
	sortt(mid+1,r);
	un(l,mid,r);
}

int main(){
	int n,k;
	while(~scanf("%d%d",&n,&k)){
		ans=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		sortt(1,n);
		if(k>=ans) printf("0\n");
		else printf("%lld\n",ans-(long long)k);
	}
} 

E、Monkey Party
E題是一個區間dp的題，emm，過的不多···，這個題題意是兩個猴子介紹認識就要把它們認識的都介紹一邊認識，可以把它簡化為兩堆合并成一堆的代價就要把兩堆的和相加起來，算所有合成一堆的最小代價，這是一個區間dp的板子題，三層for回圈，最外層遍歷區間長度，中間層遍歷區間起點，最下面一層遍歷區間中的合并點，這樣來求小區間合并成大區間的最小代價，最后得到最大區間的最小合并代價，

#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<cstring>
#include<string>
#include<vector>
using namespace std;
int a[2010];
int dp[2010][2010];
int s[2010][2010];
int inf=0x3f3f3f3f;

int main(){
	int n;
	while(cin>>n){
		for(int i=1;i<=n;i++){
			cin>>a[i];
			a[i+n]=a[i];
		}
		memset(dp,inf,sizeof(dp));
		for(int i=1;i<=n*2;i++) a[i]+=a[i-1];
		for(int i=1;i<=n*2;i++){
			dp[i][i]=0;
			s[i][i]=i;
		}
		for(int len=1;len<n;len++){
			for(int i=1;i<=n;i++){
				int j=i+len;
				for(int k=s[i][j-1];k<=s[i+1][j];k++){
					if(dp[i][k]+dp[k+1][j]+a[j]-a[i-1]<dp[i][j]){
						dp[i][j]=dp[i][k]+dp[k+1][j]+a[j]-a[i-1];
						s[i][j]=k;
					}
				}
			}
		}
		int m=1e9;
		for(int i=1;i<=n;i++){
			m=min(m,dp[i][i+n-1]);
		}
		cout<<m<<endl;
	}               
}

F、Radar Installation
F題是一個貪心題，但是也要拐個彎的貪，這個題的題意就是問最少需要多少個點雷達覆寫所有的島嶼，說實話，要是從雷達的角度來考慮這個問題，要畫半圓，這很麻煩很難想，所有要從逆向思維來思考這個問題，從島嶼的角度來思考，要覆寫這個島嶼，能放雷達的區域有多大，最后把那些重復的區域合并起來，讓雷達盡量放在最多重復的區域，這樣可以保證雷達放的最少，

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <string>
#include <queue>
#define ll long long
using namespace std;
struct node{
	double x,y;
}e[1010],t[1010];
bool cmp(node a,node b){
	return a.x<b.x;
}

int main(){
	int n,d;
	int cnt=1;
	while(~scanf("%d%d",&n,&d)&&n){
		int f=0;
		for(int i=0;i<n;i++){
			scanf("%lf%lf",&e[i].x,&e[i].y);
		}
		for(int i=0;i<n;i++){
			if(e[i].y>d){
				cout<<"Case "<<cnt++<<": "<<-1<<endl;
				f=1;
				break;
			}
		}
		if(f) continue;
		double temp;
		for(int i=0;i<n;i++){
			temp=e[i].x;
			double s=sqrt(d*d-e[i].y*e[i].y);
			t[i].x=temp-s;
			t[i].y=temp+s;
		}
		sort(t,t+n,cmp);
		int ans=0;
		for(int i=0;i<n;i++){
			ans++;
			double xx=t[i].y;
			i++;
			for(;i<n;i++){
				if(t[i].x<=xx){
					if(t[i].y<xx) xx=t[i].y;
				}else{
					i--;
					break;
				}
			}
		}
		cout<<"Case "<<cnt++<<": "<<ans<<endl;
	}
}

G、棋盤問題
G題題意是，這是個中文題就不說題意了，這題用的是dfs演算法，比較經典的dfs棋盤問題的變形，很暴力的一道題，本來想用來簽到的···，我相信大家不會的話看了代碼就一定會懂的，就找能放棋子的地方來遍歷就行了，

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
int inf=0x3f3f3f3f;
int n,k;
char mp[10][10];
bool vis[10];
int ans;
void dfs(int x,int cnt){
	if(cnt==k){
		ans++;
		return;
	}
	if(x>=n){
		return;
	}
	for(int i=0;i<n;i++){
		if(!vis[i]&&mp[x][i]=='#'){
			vis[i]=1;
			dfs(x+1,cnt+1);
			vis[i]=0;
		}
	}
	dfs(x+1,cnt);
}

int main()
{
	while(~scanf("%d%d",&n,&k)){
		if(n==k&&k==-1){
			break;
		}
		ans=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				cin>>mp[i][j];
			}
		}
		dfs(0,0);
		cout<<ans<<endl;
	}
}