noip2014普及组复赛题解

余姚中学 罗方炜

1. 珠心算测验

注意看清题意：其中有多少个数，恰好等于集合中另外两个(不同的)数之和。这样的题意加上100的规模，建议暴力3个for: #include #include #include #include using namespace std; int n;

int a[105]; int main(){

freopen(\ freopen(\ scanf(\

for(int i=1; i<=n; i++){ scanf(\ }

sort(a+1,a+n+1); int res=0;

for(int i=1; i<=n; i++){ int ok=0;

for(int j=1; j<=n && !ok; j++) if(j!=i){

for(int k=1; k<=n && !ok; k++) if(a[k]!=a[j]){ if(a[j]+a[k]==a[i]) ok=1; } }

res+=ok; }

printf(\ return 0; } 2. 比例简化

L很小，还是枚举，然后比较的话建议用乘法比较，避免精度问题： #include #include #include using namespace std; int A,B,L;

int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b); }

int main(){

freopen(\ freopen(\ scanf(\ int ba=1000000,bb=1; for(int i=1; i<=L; i++){

for(int j=1; j<=L; j++){

if(gcd(i,j)==1 && i*B>=j*A){

1

余姚中学 罗方炜

if(ba*j>=bb*i){ ba=i, bb=j; } } } }

printf(\ return 0; } 3. 螺旋矩阵

没一圈的数量有规律的，最外面一圈(n-1)*4，然后每往里n-2，直到后要么只有一个点，要么4个点。

所以可以先确定是在哪圈里，然后暴力走一圈就行： #include #include #include using namespace std; int n,x,y; int solve(){

scanf(\ int ceng=min(x, n+1-x);

ceng=min(ceng, min(y, n+1-y)); int num=0, len=n-1;

for(int i=1; i

if(len==0) ad=1; else ad=len*4; num+=ad; }

num++;

int nx=ceng, ny=ceng;

if(nx==x && ny==y) return num; for(int i=1; i<=len; i++) { ny++; num++;

if(nx==x && ny==y) return num; }

for(int i=1; i<=len; i++){ nx++; num++;

if(nx==x && ny==y) return num; }

for(int i=1; i<=len; i++){ ny--; num++;

if(nx==x && ny==y) return num; }

for(int i=1; i

if(nx==x && ny==y) return num; }

return -1; }

int main(){

2

余姚中学 罗方炜

freopen(\ freopen(\ int res=solve(); printf(\ return 0; } 4. 子矩阵

可以用二进制状态枚举取了哪些列，然后对于行的选取，可以DP,预处理每一行的代价，任意两行之间的代价，那么 dp[j][i]=min(dp[j][i], dp[k][i-1]+val[k][j]+dp[j][1]);

代码写的不是很顺，为了调试写了很多输出注释语句： #include #include #include #include using namespace std;

int g[25][25],f[25][25],dp[25][25],val[25][25]; int n,m,x,y,res; int count(int v){ int ret=0; while(v){

if(v&1) ret++; v>>=1; }return ret; }

void gao(){

//printf(\

for(int i=1; i<=n; i++){

for(int j=i+1; j<=n; j++){ val[i][j]=0;

for(int k=1; k<=y; k++) val[i][j]+=abs(f[i][k]-f[j][k]); //printf(\ } }

for(int i=1; i<=x; i++){

for(int j=i; j<=n; j++) dp[j][i]=100000000; }

for(int i=1; i<=n; i++){ dp[i][1]=0;

for(int j=2; j<=y; j++){

dp[i][1]+=abs(f[i][j]-f[i][j-1]); } }

//printf(\

for(int i=2; i<=x; i++){ for(int j=i; j<=n; j++){ //dp[j][i]=100000000; for(int k=i-1; k

3

余姚中学 罗方炜

//printf(\= %d %d\\n\ } } }

for(int i=x; i<=n; i++) res=min(res, dp[i][x]); // printf(\}

void solve(){

scanf(\ for(int i=1; i<=n; i++){

for(int j=1; j<=m; j++) { scanf(\ } }

res=100000000;

for(int i=0; i<(1<

for(int j=0; j

if( ((i>>j)&1) ==0) continue; ++r;

for(int k=1; k<=n; k++) f[k][r]=g[k][j+1]; }

/*for(int j=1; j<=n; j++){

for(int k=1; k<=y; k++) printf(\ printf(\ }printf(\ gao(); }

printf(\}

int main(){

freopen(\ freopen(\ solve(); return 0; }

%d

4