NOIP2014普及组试题题解

1.珠心算测验

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e4+39+7;
int mp[N],n,a[N],ans=0;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[i]!=a[j]){
				mp[a[i]+a[j]]=1;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(mp[a[i]]){
			ans++;
		}
	}
	cout<<ans;
	return 0;
}

解题思路：

用一个哈希表统计和即可

2.比例简化

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int gcd(int a,int b){
	if(!b)return a;
	return gcd(b,a%b);
}
int a,b,l,ans1,ans2;
int main(){
	cin>>a>>b>>l;
	ans1=l;
	ans2=1;
	for(int i=1;i<=l;i++){
		for(int j=1;j<=l;j++){
			if(gcd(i,j)==1){
				if(i*b>=a*j&&ans1*j>=ans2*i){
					ans1=i;
					ans2=j;
				}
			}
		}
	}
	cout<<ans1<<' '<<ans2;
	return 0;
}

解题思路：

判断i，j是否互质，且比值大于等于a/b即可

注意事项：

1.由于c++中实数操作可能会丢失精度，所以要把a/b>c/d换成a*d>b*c

3.螺旋矩阵

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,x,y;
int dfs(int n,int x,int y){
	if(x==1)return y;
	if(y==n)return n+x-1;
	if(y==1)return 4*n-2-x;
	if(x==n)return 3*n-y-1;
	return dfs(n-2,x-1,y-1)+4*(n-1);
}
int main(){
	cin>>n>>x>>y;
	cout<<dfs(n,x,y);
	return 0;
}

解题思路：

由矩阵可以看出，分5种情况：第一种，x=1，直接返回y

                                                 第二种，x=n，可以找到规律，是3n-y-1

                                                 第三种，y=1，可以找到规律，是4n-x-2

                                                 第四种，y=n，可以找到规律，是n+x-1

　                                             第五种,在中心，返回dfs(n-2,x-1,y-1)+4(n+1)，向内递进一层

最终可以得出答案

4.子矩阵

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 39+7;
int n,m,r,c,a[N],num[N][N],sol=1e9,w[N],g[N][N],dp[N][N];
void init(){
	for(int i=1;i<=m;i++){
		w[i]=0;
		for(int j=1;j<r;j++)w[i]+=abs(num[a[j]][i]-num[a[j+1]][i]);
	}
	for(int i=1;i<=m;i++){
		for(int j=i+1;j<=m;j++){
			g[i][j]=0;
			for(int k=1;k<=r;k++){
				g[i][j]+=abs(num[a[k]][i]-num[a[k]][j]);
			}
		}
	}
}
int dpp(){
	memset(dp,0x7f,sizeof(dp));
	dp[0][0]=0;
	for(int k=1;k<=c;k++){
		for(int i=k;i<=m;i++){
			for(int j=k-1;j<i;j++){
				dp[i][k]=min(dp[i][k],dp[j][k-1]+w[i]+g[j][i]);
			}
		}
	}
	int ans=dp[c][c];
	for(int i=c+1;i<=m;i++)ans=min(ans,dp[i][c]);
	return ans;
}
void dfs(int tr){
	if(tr>r){
		
		init();
		sol=min(sol,dpp());
		return;
	}
	for(int i=a[tr-1]+1;i<=n;i++){
		a[tr]=i;
		dfs(tr+1);
	}
}
int main(){
	cin>>n>>m>>r>>c;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>num[i][j];
		}
	}
	dfs(1);
	cout<<sol;
	return 0;
}

解题思路：

暴力枚举行的组合是C(n,r)，在使用dp去计算列的最小值，每次取最小值即可,时间复杂度是O(C(n,r)*m³)