[数据结构与算法]【NOIP2014】普及组题目详解

T1 珠心算测验

题意：随机生成一个正整数集合，集合中的数各不相同，回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？
样例：4
????????? ~~~~~~~~~ ????????? 1 2 3 4
详解：这题放在普及组的$T1$还是很友好的。。直接三重暴力循环打满。

但是这个题坑点在$1+2$和$2+1$只能算一个（初中、小学的可能不知道集合是什么意思，简单来说就是一些元素的整合，其中的性质有一条非常关键，则是“不可重复”）

我们考虑再开一个数组，记录一下这个数有没有被算过就行了，这题其实理想的状态是拿到就能切掉的，2分钟读题，3分钟写完，二等奖到手。

$Code$:

#include<bits/stdc++.h>
using namespace std;
long long a[1000001];
long long b[1000000];
long long ans=0;
int main(){
	long long n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]==2;//这是一个标记数组！
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			for(int k=1;k<=n;k++){
				if(a[i]==a[j]) continue;
				if(a[i]+a[j]==a[k]&&b[k]!=1){ //只要不等于1那就可以算！
					ans++;
					b[k]=1;//把它标记成1
				}
			}
			
		}
	}
	cout<<ans<<endl;
	return 0;
}

T2 比例简化

题意：给定三个数$A,B,L$，将$A:B$化简为$A’:B’$，要求在$A’$和$B’$均不大于$L$且$A’$和$B’$互质（两个整数的最大公约数是$1$）的前提下，$A’/B’\ge A/B$且$A’/B’?A/B$的值尽可能小。

样例：in:1498 902 10
????????? ~~~~~~~~~ ?????????out:5 3

详解：跟T1相比，这道题是个纯纯的思维题。

题解有人写$gcd$，但是这个题可以不用写，我们需要枚举$T^2$中的数，开一个$tmp$把$i/j$的数记录下来，做$T^2$次和$a/b$的比较，如果大于等于，就求差，再找最小值。然后将$i,j$替换到$x,y$就行了。(这一步也可以放在比较前，是等价的，思考一下为什么。)

注意，因为枚举$i/j$，所以所有的数都要开成$double$类型的！

$Code$：

#include<bits/stdc++.h>
using namespace std;
int main(){
    double A,B,L,x,y;
    cin>>A>>B>>L;
    double m=10000000,tmp,k=A/B;
    for(double i=1;i<=L;i++){
        for(double j=1;j<=L;j++){
            tmp=i/j-k;//这里我们选择比较前减去这个数。
            if(tmp<m&&tmp>=0){
			x=i;y=j;m=tmp;
            }
        }
    }
    cout<<x<<" "<<y<<endl;
    return 0;
}

T3 螺旋矩阵

题意：一个“蛇形方阵”，给出$T$，输出一个$T?T$的类似于下图的矩阵
$T=4$时

1     2     3      4
12    13    14     5
11    16    15     6
10     9     8     7

给出$i,j$，查找$a(i,j)$的值输出。

详解：
一看这题有50%的数据（$n\le 100$），就应该很快的反应出这题不对劲！再看内存$125MB$

不行，这题开二维肯定是过不了的！

我们先来看看$50pts$的做法，其实就是$O(n)$模拟出蛇形方阵，（关于蛇形方阵的解法，其实就是跟一条蛇一样，T=奇数和T=偶数时不一样，如果是奇数那么在方阵中间填上$n?n$就行了，具体看代码）。然后$O(1)$把$(x,y)$跑出来就行了。

$Code（50pts）$：

#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long i,j;
long long a[4500][4500];
int main(){
	cin>>n>>i>>j;
	long long val=1;//起始值 
	long long k=n-1;//每次填充的个数 
	long long x=1,y=1;//起点 
	for(;k>0;k=k-2){
		for(int i=1;i<=k;i++){
			a[x][y++]=val++;
		}
		for(int i=1;i<=k;i++){
			a[x++][y]=val++;
		}
		for(int i=1;i<=k;i++){
			a[x][y--]=val++;
		}
		for(int i=1;i<=k;i++){
			a[x--][y]=val++;
		}
		x++,y++;//起点往右下移动一个单位 
	}
	if(n%2) a[n/2+1][n/2+1]=n*n;
	//预处理出螺旋矩阵
	cout<<a[i][j]<<endl; 
	return 0;
}

这样会爆内存。

考虑100pts的做法。

好像没什么能优化的了，只能找规律了！

手画出$6x6$的方阵。

把螺旋矩阵一层一层拆开，看看目标位置在哪一层，然后加上这一层最左上角的数字$（4\times (n?1))$，即为要求的数字。

观察它们具有以下性质：

1.如果是第$1$行，那么第$j$列的数字就是$j$；
2.如果是第$1$列，那么第$i$行的数字就是$4n?4?i+2$
3.如果是第$n$列，那么第$i$行的数字就是$n+i?1$；
4.如果是第$n$行，那么第$j$列的数字就是$3n?2?j+1$

那么得出这四条性质，那么我们就可以爆搜搜出答案了！

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

T4 子矩阵

题目太长，甩个链接。
题目链接

详解：毒瘤至极的DP！

暴力能得50pts，不过我觉得暴力的想法跟正解差不多。

我们要设$f[j][k]$表示当前选了$j$个数,且强制选择第$k$个数的最小分值。

然后我们枚举在第$k$个数之前选或不选第$i$个数

易得方程$f[j][k]=min(f[j][k],f[j?1][i]+f2[i][k]);$

其中$f2[i][k]$表示$i,k$之间的差。

现在把一个数变成一列中的几个数,但我们不知道是哪几个数

那么就从$n$行中暴力搜索选出$c$行,与列相交的地方便是要选的数

现在我们有一个c*m的矩阵，也就是把序列中的数变成了c个数

我们要考虑列与列之间的分值和行与行之间的分值

因为行已经确定,则设$h[i]$为第$i$列中相邻数间的分值

由于列不确定选哪些,设$f[i][k]$为任意两列之间的分值

则 $f[j][k]=min(f[j][k],f[j?1][i]+h[k]+f2[i][j]);$

$h[k]$为选择第k列在行与行之间产生的分值

$dp[1][k]=h[k]$,即只产生行之间的分值

因为行数不超过16,我在枚举中用一个数代替判重数组
.

#include<bits/stdc++.h>
using namespace std;
int n,m,r,c;
int a[20][20],b[20][20],f[20][20],dp[20][20],h[20];
int state,ans;
int solve(){
    memset(f,0,sizeof(f));
    memset(dp,0x3f3f3f3f,sizeof(dp));
    memset(h,0,sizeof(h));
    int i,j,k;
    j=0;
    for(i=1;i<=n;i++){
        if(state&(1<<i)){
            j++;
            for(k=1;k<=m;k++){
                b[j][k]=a[i][k];
            }
        }
    }
    for(i=1;i<=m;i++){
        for(j=i+1;j<=m;j++){
            for(k=1;k<=r;k++){
                f[i][j]+=abs(b[k][i]-b[k][j]);
            }
        }
    }
    for(i=1;i<=m;i++){
    	for(j=1;j<r;j++){
    		h[i]+=abs(b[j][i]-b[j+1][i]);
        }
    }
    for(k=1;k<=m;k++){
    	dp[1][k]=h[k];
        for(j=2;j<=c&&j<=k;j++){
            for(i=1;i<k;i++){
                dp[j][k]=min(dp[j][k],dp[j-1][i]+f[i][k]+h[k]);
            }
        }
    }
    k=0x3f3f3f3f;
    for(i=c;i<=m;i++){
    	k=min(k,dp[c][i]);
    }
    return k;
}
void dfs(int x,int sum){
    if(sum==r){
        ans=min(ans,solve());
        return;
    }
    int i;
    for(i=x+1;i<=n;i++){
        state|=(1<<i);
        dfs(i,sum+1);
        state^=(1<<i);
    }
}
int main(){
    ans=0x3f3f3f3f;
    cin>>n>>m>>r>>c;
    int i,j;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    state=0;
    dfs(0,0);
    printf("%d",ans);
    return 0;
}