保命代码:
- #include <stdio.h>
- #include <memory.h>
- #include <math.h>
- #include <string>
- #include <vector>
- #include <set>
- #include <stack>
- #include <queue>
- #include <algorithm>
- #include <map>
- #define I scanf
- #define OL puts
- #define O printf
- #define F(a,b,c) for(a=b;a<c;a++)
- #define FF(a,b) for(a=0;a<b;a++)
- #define FG(a,b) for(a=b-1;a>=0;a--)
- #define LEN 100
- #define MAX 0x06FFFFFF
- #define V vector<int>
- using namespace std;
- typedef long long ll;
- int main(){
- // http://lx.lanqiao.cn/problem.page?gpid=T126
- // freopen("D:/CbWorkspace/blue_bridge / 矩阵翻硬币. txt","r",stdin);
- ll n,m;
- scanf("%lld%lld",&n,&m);
- printf("%lld",ll(sqrt(n))*ll(sqrt(m)));
- return 0;
- }
- View Code
套路理解:
先看 n = 1 的情况: 对于 (1 , m), 只要看它翻转的次数奇偶就能确定它最终的状态因为 x = 1, 每次第一行都要参与翻转, 当 y 能整除 m 的时候,(1 , m) 会翻转,(1 , m)全过程翻转的次数取决于 m 的约数个数, 1 的约数个数为 1 , 3 的约数个数为 2, 5 的约数个数为 2, 9 的约数个数为 3 当 m = k^2 (k = 1 ,2 ,3...) 其约数个数为奇数, 否则 其约数个数为偶数 因为一般数约数都是成对出现, 而一个数的平方数, 有两个约数相等
所以, 最后(1 , m) m = k^2 (k = 1 ,2 ,3...) 最终状态为 0, 其他则为 1
而最后 0 的个数总和 count = sqrt(m) , 取整
再来看一般情况:(n , m)最后状态是什么? 现在行的变化也是它翻转的因素从上面容易推出, 当 m 确定后, 他的翻转次数为 n 的约数个数而 (n , m) 翻转的次数 = (n 的约数个数 * m 的约数个数)刚才分析了, 只有在 (n , m) 翻转的次数为奇数时 它的最终状态为 0 而只有 奇数 * 奇数 = 奇数, 所以 n ,m 的约数个数必须为奇数, 即: n = k^2 (k = 1 ,2 ,3...) 且 m = j^2 (j = 1 ,2 ,3...)
最后得出结论:
对于 n 行 m 列矩阵, 经过 Q 操作后 反面的次数 count = sqrt(n) * sqrt(m) ,(取整后再相乘)
高精度开方:
假设位数为 len 的整数, 开方取整后为一个 lenSqrt 位数
当 len 为偶数, lenSqrt = len / 2 .
当 len 为奇数, lenSqrt = (len / 2) + 1 .
证明很简单, 这里就不证了
现在就简单了, 位数确定了从高位到低位一位一位地确定比如: sqrt(1028) , 表示对 1028 开方取整
它开方取整后两位数. 先看第一位:
取 0, 00 * 00 < 1028 所以 sqrt(1028) > 00
取 1, 10 * 10 < 1028 所以 sqrt(1028) > 10
取 2, 20 * 20 < 1028 所以 sqrt(1028) > 20
取 3, 30 * 30 < 1028 所以 sqrt(1028) > 30
取 4, 40 * 40 > 1028 所以 sqrt(1028) < 40 , 所以第一位取 3
第二位:
取 0, 30 * 30 < 1028 所以 sqrt(1028) > 30
取 1, 31 * 31 < 1028 所以 sqrt(1028) > 31
取 2, 32 * 32 < 1028 所以 sqrt(1028) > 32
取 3, 33 * 33 > 1028 所以 sqrt(1028) < 33 , 所以 sqrt(1028) = 32
大数是一样的道理, 只不过大数用字符串保存, 字符串相乘也要自己来实现
结果只得了 70 分:
- #include <stdio.h>
- #include <memory.h>
- #include <math.h>
- #include <string>
- #include <string.h>
- #include <vector>
- #include <set>
- #include <stack>
- #include <queue>
- #include <algorithm>
- #include <map>
- #define I scanf
- #define OL puts
- #define O printf
- #define F(a,b,c) for(a=b;a<c;a++)
- #define FF(a,b) for(a=0;a<b;a++)
- #define FG(a,b) for(a=b-1;a>=0;a--)
- #define LEN 3000
- #define MAX 0x06FFFFFF
- #define V vector<int>
- using namespace std;
- typedef long long ll;
- struct hp{
- int len;
- int s[LEN+1];
- hp(){
- len=1;
- int i;
- for(i=1;i<=LEN;i++){
- s[i]=0;
- }
- }
- hp(char* ch){
- int i;
- len=strlen(ch);
- for(i=1;i<=len;i++)
- s[i]=ch[len-i]-48;
- for(;i<=LEN;i++)
- s[i]=0;
- }
- void print(){
- int i;
- for(i=len;i>=1;i--)
- printf("%d",s[i]);
- }
- string output(){
- int i;
- string ans;
- for(i=len;i>=1;i--){
- char buf[100];
- sprintf(buf,"%d",s[i]);
- ans+=buf;
- }
- return ans;
- }
- };
- int compare(const hp& a,const hp& b){
- int len=max(a.len,b.len);
- while(len>0 && a.s[len]==b.s[len]) len--;
- if(len==0)
- return 0;
- else return a.s[len]-b.s[len];
- }
- void multiplyh(const hp& a,const hp& b,hp& c){
- int i,j,len=a.len+b.len+1;
- c=hp();
- for(i=1;i<=a.len;i++){
- for(j=1;j<=b.len;j++){
- c.s[i+j-1]+=a.s[i]*b.s[j];
- c.s[i+j]+=c.s[i+j-1]/10;
- c.s[i+j-1]%=10;
- }
- }
- while(len>1 && c.s[len]==0) len--;
- c.len=len;
- }
- void square(const hp&a,hp &c){
- multiplyh(a,a,c);
- }
- void sqrth(const hp&a,hp &c){
- int i,j,len=(a.len+1)/2;
- c=hp();
- hp t;
- c.len=len;
- for(i=len;i>=0;i--){
- for(j=0;j<=9;j++){
- c.s[i]=j;
- square(c,t);
- if(compare(t,a)>0){
- c.s[i]=j-1;
- break;
- }
- }
- }
- }
- int main(){
- // http://lx.lanqiao.cn/problem.page?gpid=T126
- // freopen("D:/CbWorkspace/blue_bridge / 矩阵翻硬币. txt","r",stdin);
- char buf[LEN];
- scanf("%s",buf);
- hp a(buf);
- scanf("%s",buf);
- hp b(buf);
- hp c,d,e;
- sqrth(a,c);
- sqrth(b,d);
- multiplyh(c,d,e);
- e.print();
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2501205.html