蓝桥杯-矩阵翻硬币

2019-11-11 01:34:31

字体：大中小

来源：转载

供稿：网友

做这道题，首先是要理解清楚题目意思。没有理解清楚题目中给出的i*x，j*y是没法做题的。

两条主线： 1.对于点(x, y)，要求对行数凡是x的倍数的行进行一次翻转，对列数凡是y的倍数的列进行一次翻转 2.要关注到题目后面给出的“数据规模和约定”，给定的范围比较大，需要做一定的处理一个主意：对于10*1000这样庞大的数据类型，要么会用到数组去存储一个数，要么就一定会涉及到优化…

http://blog.csdn.net/misdom_tian_ya/article/details/44459827 这个是详解的思路

用java的优势在于：Java中自带了BigInteger类，可以在一定程度上比较好的处理大数问题。

import java.math.BigInteger;import java.util.Arrays;import java.util.Scanner;public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner cin = new Scanner(System.in); String s1 = cin.next(); String s2 = cin.next(); BigInteger ans1 = BigSqrt(s1); BigInteger ans2 = BigSqrt(s2); //System.out.PRintln(ans1+" "+ans2); BigInteger ans = ans1.multiply(ans2); System.out.println(ans); } private static BigInteger BigSqrt(String s) { int mlen = s.length(); //被开方数的长度 int len; //开方后的长度 BigInteger beSqrtNum = new BigInteger(s);//被开方数 BigInteger sqrtOfNum; //存储开方后的数 BigInteger sqrtOfNumMul; //开方数的平方 String sString;//存储sArray转化后的字符串 if(mlen%2 == 0) len = mlen/2; else len = mlen/2+1; char[] sArray = new char[len]; Arrays.fill(sArray, '0');//开方数初始化为0 for(int pos=0; pos<len; pos++){ //从最高开始遍历数组，每一位都转化为开方数平方后刚好不大于被开方数的程度 for(char num='1'; num<='9'; num++){ sArray[pos] = num; sString = String.valueOf(sArray); sqrtOfNum = new BigInteger(sString); sqrtOfNumMul = sqrtOfNum.multiply(sqrtOfNum); if(sqrtOfNumMul.compareTo(beSqrtNum) == 1){ sArray[pos]-=1; break; } } } return new BigInteger(String.valueOf(sArray)); }}

其他做法：

#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAXN 1100char n[MAXN];char m[MAXN];int sqrtn_ans[MAXN];int sqrtm_ans[MAXN];int mul_ans[MAXN];int temp1[MAXN];int Sqrt(int ans[],char n[]);int compare(int a[],int b[],int len1,int len2);int mul(int ans[],int a[],int b[],int len1,int len2);int add(int ans[],int b[],int len1,int len2);int main(){ int len1,len2,ansLen,i; scanf("%s%s",n,m); memset(sqrtn_ans,0,sizeof(sqrtn_ans)); memset(sqrtm_ans,0,sizeof(sqrtm_ans)); len1=Sqrt(sqrtn_ans,n); len2=Sqrt(sqrtm_ans,m); memset(mul_ans,0,sizeof(mul_ans)); ansLen=mul(mul_ans,sqrtn_ans,sqrtm_ans,len1,len2); for(i=ansLen-1;i>=0;i--) printf("%d",mul_ans[i]); printf("/n"); return 0;}//求大数的平方根，先将字符串数组转换成整型数组，然后在求平方根，运算结果保存在ans中，//函数返回运算结果的位数int Sqrt(int ans[],char n[]){ int len=strlen(n),ansLen,mulLen,i,j; if(len%2==0) ansLen=len/2; else ansLen=len/2+1; int *num=(int *)malloc(sizeof(int)*len); //将字符串数组转换成整型数组 for(i=0,j=len-1;i<len;i++,j--) num[j]=n[i]-'0'; for(i=ansLen-1;i>=0;i--) { int flag; memset(temp1,0,sizeof(temp1)); mulLen=1; while((flag=compare(temp1,num,mulLen,len))==-1) { ans[i]++; mulLen=mul(temp1,ans,ans,ansLen,ansLen); } if(flag==1) ans[i]--; else if(flag==0) break; } return ansLen;} //高精度*高精度乘法运算，数组a和b中存放两个操作数，a的长度为len1,b的长度为len2,//运算结果保存在ans中，函数返回运算结果的位数int mul(int ans[],int a[],int b[],int len1,int len2){ int i,j; memset(ans,0,sizeof(int)*MAXN); for(i=0;i<len1;i++) { for(j=0;j<len2;j++) { ans[i+j]+=a[i]*b[j]; } } for(i=0;i<len1+len2;i++) { ans[i+1]+=ans[i]/10; ans[i]=ans[i]%10; } for(i=len1+len2;i>=0;i--) { if(ans[i]) break; } return i+1;}//比较两个操作数的大小，若相等则返回0，否则若a>b，返回1，a<b,返回-1.int compare(int a[],int b[],int len1,int len2){ if(len1>len2) return 1; else if(len1<len2) return -1; else if(len1==len2) { int i; for(i=len1-1;i>=0;i--) { if(a[i]>b[i]) return 1; else if(a[i]<b[i]) return -1; } } return 0;}

上一篇：hashMap的原理深入理解

下一篇：Matlab R2016b 中文破解版资源 win10实测有效