NOIP 2014普及组，看OI大牛怎么AC四题
NOIP 2014普及组复赛中
全国涌现了13位满分大神，他们是：
谢典霖，中山纪念中学；何继奥，中山纪念中学
梁文杰，石门实验学校；谭嘉伟，广州铁一中学
郑嘉铭，佛山桂江一中；周楷文，深圳外国语学校
林荣恩，厦门双十中学；姜度，衢州华茂外国语学校
叶昊星，杭州市建兰中学；梁晏成，镇海蛟川书院
陈威宇，慈溪上林初中；谢嘉东，慈溪上林初中
徐泽涛，余姚市实验学校
1、珠心算测验
【问题描述】
珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。
某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答:其中有多少个数，恰好等于集合中另外两个(不同的)数之和？最近老师出了一些测验题，请你帮忙求出答案。
【输入】
输入文件名为 count.in。
输入共两行，第一行包含一个整数 n，表示测试题中给出的正整数个数。
第二行有 n 个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。
【输出】
输出文件名为 count.out。
输出共一行，包含一个整数，表示测验题答案。
【输入输出样例】
count.in
4
1 2 3 4
count.out
2
【数据说明】
对于 100%的数据，3 ≤ n ≤ 100，测验题给出的正整数大小不超过 10,000。
这道题其实很简单，意思就是说给你一些数a1,a2,a3,a4...an，然后让你回答有多少个A+B=C（A ≠ B ≠ C）满足(回答C的数量，而不是等式的数量) 。
两重循环，分别枚举i=1...n,j=i+1...n，如果ai+aj这个数在集合中存在，那么you[ai+aj]←true，然后再从a1到an做一次扫描，只要you[ai]，ans++。这个算法的好处在于它很好写，不用退出什么的，也不用注意循环的顺序，而且时间复杂度是O(N2)。
但很多人没有做对的原因就是没有好好理解题意，但是根本原因其实还在于心态太骄傲了，认为是第一题就可以轻视，这样是不好的，水题我们更要做好啊，你想想同样是100分，这100分多么好拿，所以是水题、越该放平心态，细心地做。
#include<cstdio>
using name space std;
int n, a[101], i, j, count;
bool you[20001]={false};
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
you[ a[i]+a[j] ]=true;
count=0;
for(i=1;i<=n;i++)
count += you[ a[i] ];
printf("%d\n",count);
return 0;
}
2、比例简化
【问题描述】
在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有1498 人，反对的有 902 人，那么赞同与反对的比例可以简单的记为 1498:902。
不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为 5:3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。
现给出支持人数 A，反对人数 B，以及一个上限 L，请你将 A比 B 化简为 A’比 B’，要求在 A’和 B’均不大于 L 且 A’和 B’互质(两个整数的最大公约数是 1)的前下，A’/B’ ≥ A/B 且 A’/B’ - A/B 的值尽可能小。
【输入】
输入文件名为 ratio.in。
输入共一行，包含三个整数 A，B，L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。
【输出】
输出文件名为 ratio.out。
输出共一行，包含两个整数 A’，B’，中间用一个空格隔开，表示化简后的比例。
【输入输出样例】
ratio.in
1498 902 10
ratio.out
5 3
【数据说明】
对于 100%的数据，1 ≤ A ≤ 1,000,000，1 ≤ B ≤ 1,000,000，1≤ L ≤ 100，A/B ≤ L。
此道题放在第二个挺合适，特点是代码好写，但方法不是特别好想(与历年相比)，只要按部就班一步一步地来，这道题还是很容易的。 首先，想一个总体的框架：
我们发现L≤100，因此可以枚举A′和B′，然后判断是否A’B’满足上述条件，并且打擂台求比值最小的一组就行了，打擂台的复杂度是O(1)。设验证的复杂度为O(k)，则总的算法的复杂度为O(kL2)，其中L2是104，所以我们只要保证k的大小在100以内就一定没有问题。
现在要求两个分数的差值，该怎么办呢？高精除！很多人一下就想到了，但是又仔细一考虑。。。。。首先，高精除有风险，而且如果我是出题者的话，我一定会卡高精除，第二，高精除的编程复杂度很高，很容易出错而且耗时间。
于是我重新读题，找寻一些特殊的切入点，终于看到了这个东西：1≤A,B≤106，我的脑袋里瞬间就萌生出一种想法：模拟手动比较分数——就是说如果你要比较两个分数，就先把他们通分，然后比较分子的大小，如a/b和c/d比较，先把它们化成ad/bd和bc/bd的形式，然后比较ad和bc的大小，而在整个枚举的过程中，你最大的情况只需要比较A’/B’和A/B的大小，而且他们分母的乘积最大是108，到此，问题就完美地解决了！
#include<cstdio>
#include<iostream>
using name space std;
long A,B,a,b,L,besta,bestb;
long long cha_zi, cha_mu, best_cha_zi, best_cha_mu=-1, t1, t2;
void Minus(long long z1, long long m1, long long z2, long long m2, long long&cz, long long &cm)
{
z1=z1*m2;
z2=z2*m1;
m1=m2=m1*m2;
cm=m1;
cz=z1-z2;
}
bool huzhi(int x, int y)
{
int max, i;
if(x>y)max=x;
else max=y;
for(i=2; i*i<=max; i++)
{
if(x%i==0 && y%i==0)
return false;
}
return true;
}
int main()
{
cin >> A >> B >> L;
for(a=1;a<=L;a++)
{
for(b=1;b<=L;b++)
{
if( huzhi(a,b)==true)
{
Minus(a,b,A,B,cha_zi,cha_mu);
if(cha_zi>=0)
{
Minus(best_cha_zi,best_cha_mu,cha_zi,cha_mu,t1,t2);
if(t1>0 || best_cha_mu==-1)
{
best_cha_zi=cha_zi;
best_cha_mu=cha_mu;
besta=a;
bestb=b;
}
}
}
}
}
cout << besta << " "<< bestb << endl;
return 0;
}
3、螺旋矩阵
【问题描述】
一个 n 行 n 列的螺旋矩阵可由如下方法生成:
从矩阵的左上角(第 1行第 1 列)出发，初始时向右移动;如果前方是未曾经过的格子，则继续前进，否则右转;重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入 1, 2, 3, ... , n2，便构成了一个螺旋矩阵。
下图是一个 n = 4 时的螺旋矩阵。
现给出矩阵大小 n 以及 i和 j，请你求出该矩阵中第 i 行第 j列的数是多少。
【输入】
输入文件名为 matrix.in。
输入共一行，包含三个整数 n，i，j，每两个整数之间用一个空格隔开，分别表示矩阵大小、待求的数所在的行号和列号。
【输出】
输出文件名为 matrix.out。
输出共一行，包含一个整数，表示相应矩阵中第 i 行第 j 列的数。
【输入输出样例】
matrix.in
4 2 3
matrix.out
14
【数据说明】
对于 50%的数据，1 ≤ n ≤ 100;
对于 100%的数据，1 ≤ n ≤ 30,000，1 ≤ i ≤ n，1 ≤ j ≤ n。
首先处理特殊情况：
1、N=1直接输出1
2、如果要找的数字在边界上，直接计算即可
中间情况：
1、首先算出外围有多少数字
2、分四个方向计算数字排位
以上为最简单的模拟方法，方法直观，还有更简洁的方法自行思考。
#include<stdio.h>
int min(int x,int y,int z,int u){
int p;
p=x<y?x:y;
p=p<z?p:z;
p=p<u?p:u;
return p;
}
int main(){
int i,j,k,m,n;
int x,y,ans;
scanf("%d%d%d",&n,&x,&y);
if(n==1){puts("1");return0;}
k=min(x,y,n-x+1,n-y+1);
if(k==1){
if(x==1)ans=y;
else if(y==n)ans=n-1+y;
else if(x==n)ans=(n-1)*2+(n-y+1);
else if(y==1)ans=(n-1)*3+(n-x+1);
printf("%d\n",ans);
return 0;
}
ans=0;m=n;
for(i=1;i<k;i++){
ans+=(m-1)*4;
m-=2;
}
if(k==x){
ans+=y-k+1;
}else if(k==n-y+1){
ans+=m-1;
ans+=x-k+1;
}else if(k==n-x+1){
ans+=(m-1)*2;
ans+=(n-y+1)-k+1;
}else if(k==y){
ans+=(m-1)*3;
ans+=(n-x+1)-k+1;
}
printf("%d\n",ans);
return 0;
}
4、子矩阵
【问题描述】
给出如下定义:
1.子矩阵:从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵(保持行与列的相对顺序)被称为原矩阵的一个子矩阵。
例如，下面左图中选取第 2、4 行和第 2、4、5 列交叉位置的元素得到一个 2*3 的子矩阵如图所示。
2.相邻的元素:矩阵中的某个元素与其上下左右四个元素(如果存在的话)是相邻的。
3.矩阵的分值:矩阵中每一对相邻元素之差的绝对值之和。
本题任务:给定一个 n 行 m 列的正整数矩阵，请你从这个矩阵中选出一个 r 行 c 列的子矩阵，使得这个子矩阵的分值最小，并输出这个分值。
【输入】
输入文件名为 submatrix.in。
第一行包含用空格隔开的四个整数 n，m，r，c，意义如问题述中所述，每两个整数之间用一个空格隔开。
接下来的 n 行，每行包含 m 个用空格隔开的整数，用来表示问题述中那个 n 行 m 列的矩阵。
【输出】
输出文件名为 submatrix.out。
输出共 1 行，包含 1 个整数，表示满足题目述的子矩阵的最小分值。
【输入输出样例 1】
submatrix.in
5 5 2 3
9 3 3 3 9
9 4 8 7 4
1 7 4 6 6
6 8 5 6 9
7 4 5 6 1
submatrix.out
6
【输入输出样例 2】
submatrix.in
7 7 3 3
7 7 7 6 2 10 5
5 8 8 2 1 6 2
2 9 5 5 6 1 7
7 9 3 6 1 7 8
1 9 1 4 7 8 8
10 5 9 1 1 8 10
1 3 1 5 4 8 6
submatrix.out
16
【数据说明】
对于50%的数据，1≤𝑛≤12,1≤𝑚≤12,矩阵中的每个元素1≤aij ≤20;
对于100%的数据，1 ≤ 𝑛 ≤16, 1 ≤ 𝑚 ≤ 16,矩阵中的每个元素1≤ a i j ≤1000, 1 ≤ 𝑟 ≤ 𝑛,1 ≤ 𝑐 ≤𝑚。
这道题乍一眼看来就是爆搜，然而爆搜要枚举行和列，枚举的次数最大约是 8!∗8！=403202=1625702400，很明显超时，但是我们发现只枚举一层为8!=40320还是很小的，因此可以先枚举一层，另一层再考虑别的方法。
现在选一些列，使得分值最大，如果我选择了某一列，那么代价就是这列的纵向的分值的差的绝对值之和，加上它和上一个选择的列的横向对应的权值的绝对值之和，那么现在这个问题就完全变成一个一维的问题了，我们把选择某一列付出的纵向的代价叫做纵差(zc[i])，选择第i列和第j列所付出的横向的代价叫做hc[i][j](i<j)，现在把它看成一个一维的数列，选择一个数，要付出的代价就是zc[i]+hc[last][i]，last表示上一个选择的数，而这一个是否具有子结构最优性质呢？
设计状态f[i][j]表示已经选择了i个数，并且最后一个的编号为j所付出的最小代价，那么有状态转移方程： f[i][j]=min(f[i−1][k]+hc[k][j])+zc[j])(1≤i≤N,1≤j≤j,1≤k<j)。枚举的复杂度是O(N/2)!，而DP的时间复杂度是O(N3)，总的是O((N2)!∗N3)，至此，问题解决了。
以下代码是初中时候写的。。。。当时只会用拼音，数学函数也不会用，还请见谅。
#include<cstdio>
#include<cstring>
#define oo 2000000000
using name space std;
int N, M, R, C, zc[17], hc[17][17], a[17][17];
long ans, maxz;
int abs(int n)
{
if(n<0)n=-n;
return n;
}
long min(long a, long b)
{
if(a<b)return a;
else return b;
}
int geshu(long z)
{
int count=0;
while(z>0)
{
count+=z%2;
z=z>>1;
}
return count;
}
void qiu_zchc(long z)
{
int i,j,k,num[17],size,x;
x=1;
size=0;
while(z>0)
{
if(z%2==1)num[++size]=x;
x++;
z=z>>1;
}
memset(zc,0,sizeof(zc));
for(i=1;i<=M;i++)
{
for(j=1;j<size;j++)
zc[i]+=abs( a[ num[j] ][i] - a[num[j+1] ][i] );
}
memset(hc,0,sizeof(hc));
for(i=1;i<=M;i++)
{
for(j=i;j<=M;j++)
{
for(k=1;k<=size;k++)
{
hc[j][i] += abs( a[ num[k] ][i]- a[ num[k] ][j]);
}
}
}
}
long DP(long z)
{
qiu_zchc(z);
long f[17][17], Min=oo, min;
int i,j,k;
for(i=1;i<=M;i++)
f[1][i]=zc[i];
for(i=2;i<=C;i++)
{
for(j=1;j<=M;j++)
{
min=oo;
for(k=1;k<j;k++)
if( f[i-1][k]+hc[j][k] <min)min=f[i-1][k]+hc[j][k];
f[i][j] = min + zc[j];
}
}
for(j=1;j<=M;j++)
if(f[C][j]<Min)Min=f[C][j];
return Min;
}
int main()
{
int i,j;
long t, z;
scanf("%d%d%d%d",&N,&M,&R,&C);
for(i=1;i<=N;i++)
for(j=1;j<=M;j++)
scanf("%d",&a[i][j]);
maxz=1;
for(i=1;i<=N;i++)maxz=maxz*2;
maxz=maxz-1;
ans=oo;
for(z=1;z<=maxz;z++)
{
if(geshu(z)==R)
{
t=DP(z);
if(t<ans)ans=t;
}
}
printf("%ld\n",ans);
return 0;
}
猛戳下面文章，一起去冲刺NOIP复赛吧！
家长进微信交流总群，请加江哥微信：zzijiang
OIer投稿，请加江哥微信：zzijiang
信息学竞赛家长交流QQ群：532193136
信息学竞赛选手交流QQ群：465537784
WELCOME