HDOJの旅

[by_041]

---

曾经有一个 序

---

目录

文章目录

• HDOJの旅
• • • • • • [by_041]
  • 曾经有一个 序
  • 目录
  • @[toc]
• [ACM Steps](http://acm.hdu.edu.cn/game)
• • Chapter One - 阶段1
  • • Section One - 基本输入输出
    • Section Two - 简单的推公式
    • Section Three - 数据结构初步、算法初步
  • Chapter Two - 阶段2
  • • Section One - 数论初步
    • • 2.1.1.最小公倍数(P1108,LCM)
      • 2.1.2.How many prime numbers(P2138)
      • 2.1.3.相遇周期(P1713)
      • 2.1.4.
      • 2.1.5.
      • 2.1.6.
      • 2.1.7.Leftmost Digit(P1060)
      • 2.1.8.小数化分数2(P1717)
• Problems Set
• • P1000 A + B Problem
  • P1001 Sum Problem
  • P1002 A + B Problem II
  • P1003 Max Sum
  • P1004 Let the Balloon Rise
  • P1005 Number Sequence
  • P1006 Tick and Tick
  • P1007 Quoit Design
  • P1008
  • P1009 FatMouse' Trade
  • P1010
  • P1011
  • P1012 u Calculate e
  • P1013
  • P1014
  • P1015
  • P1016
  • P1017
  • P1018
  • P1019
  • P1020 Encoding
  • P1021
  • P1022
  • P1023
  • P1024
  • P1025
  • P1026
  • P1027
  • P1028
  • P1029
  • P1030
  • P1031
  • P1032
  • P1033
  • P1034
  • P1035 Robot Motion
  • P1036
  • P1037
  • P1038
  • P1039
  • P1040 As Easy As A+B
  • P1041
  • P1042~1048
  • P1049 Climbing Worm
  • P1050~1059
  • P1060 Leftmost Digit
  • P1061 Rightmost Digit
  • P1062~1088
  • P1089 A+B for Input-Output Practice (I)
  • P1090 A+B for Input-Output Practice (II)
  • P1091 A+B for Input-Output Practice (III)
  • P1092 A+B for Input-Output Practice (IV)
  • P1093 A+B for Input-Output Practice (V)
  • P1094 A+B for Input-Output Practice (VI)
  • P1095
  • P1096
  • P1097
  • P1098
  • P1099
  • P1106 排序
  • P1108 最小公倍数
  • P1196 Lowest Bit
  • P1234 开门人和关门人
  • P1328 IBM Minus One
  • P1717 小数化分数2
  • P2138 How many prime numbers
  • P2161 Primes
  • P2317 Nasty Hacks
  • P2093 考试排名
  • P2095 find your present (2)
  • P2111 Saving HDU
  • P2550 百步穿杨
  • P2561 第二小整数
  • P2719 The Seven Percent Solution
  • P3188
• 附件 - 合集
• • 高精度模板（用vector_int表示，范围正整数）

ACM Steps

Chapter One - 阶段1

Section One - 基本输入输出

是对经典ACM比赛种的输入输出情况的总结

• • P1089：多组数据，一组占一行，有两个数，直到文件尾（EOF）结束
  • while(cin>>a>>b)或while(~scanf("%d%d",&a,&b))
  • P1090：第一行是一个n，后有n组数据，一组占一行，有两个数
    • 直接：输入and循环控制
  • P1091：多组数据，一组占一行，有两个数，直到0 0结束（不处理）
    • while(cin>>a>>b,a!="0"||b!="0")或while(scanf("%d%d",&a,&b),a||b)
  • P1092：多组数据，每组数据一行，每行第一个数是n，后有n个数据，直到n=0结束（不处理）
    • while(scanf("%d",&n),n)
  • P1093：T组数据，每组数据一行，每行第一个数是n，后有n个数据
    • 直接：输入and循环控制
  • P1094：多组数据，每组数据一行，每行第一个数是n，后有n个数据，直到文件尾（EOF）结束
    • while(~scanf("%d",&n))
  • P1095：P1089，外加followed by a blank line=>每组后面直接加'\n'！！！（注意）
    • 每组后直接加putchar('\n');
  • P1096：P1093 ，外加a blank line between outputs=>两组有效数据之间加'\n'！！!（注意）
    • 除最初一组每组前换行：for(int cas=1;cas<=T;cas++)and每组头加if(cas^1)putchar('\n');
    • 除最后一组每组后换行，while(T--)and每组末尾加if(T)putchar('\n');

• 其共有的头是a+b的高精度计算部分：

  #include<iostream>
  #include<string>
  #include<algorithm>using namespace std;string add(string a,string b)
  {if(a.size()<b.size())swap(a,b);reverse(a.begin(),a.end());reverse(b.begin(),b.end());int i,ii=b.size();for(i=0;i<ii;i++){a[i]+=b[i]-'0';if(a[i]>'9'){a[i]-=10;a[i+1]++;}}for(ii=a.size();i<ii;i++){if(a[i]>'9'){a[i]-=10;a[i+1]++;}}if(a[ii]==1)a+='1';reverse(a.begin(),a.end());return a;
  }
  

Section Two - 简单的推公式

可题中数据直接推得答案的公式题，类比noi的小学奥数分块

• 1.2.1.Climbing Worm(P1049)：
• 小学奥数蜗牛爬井，只要注意最后一次攀爬有以下特征：
  - 起点高度是u-d的倍数，起点高度加u大于等于井高n
  • 所以可以得到公式：$anss=((n-u)/(u-d)+bool((n-u)\%(u-d)))\ast 2+1$

#include<iostream>using namespace std;int main()
{int n,u,d;while(scanf("%d%d%d",&n,&u,&d),n|u|d){printf("%d\n",((n-u)/(u-d)+bool((n-u)%(u-d)))*2+1);}return 0;
}

• 1.2.2.Nasty Hacks(P2317)：
  • 简单的由题意得，第一个数与第二个数减去第三个数的差相比的大小等情况输出即可

#include<iostream>using namespace std;int main()
{int n,r,e,c;scanf("%d",&n);while(n--){scanf("%d%d%d",&r,&e,&c);c=r-e+c;//表示不加入广告的优势if(c)if(c>0)puts("do not advertise");elseputs("advertise");elseputs("does not matter");}return 0;
}

​

• 1.2.3.find your present (2)(P2095)：

  • 在n个数中找出唯一出现了奇数次的数

    • 法1：sort然后扫一遍
    • 法2：用map计数，然后将奇数个的输出
    • 法3：用链表的方法，奇数次出现就在对应位置新建结点，偶数次就删除现存结点

    这里的代码用的是法2

#include<iostream>
#include<map>using namespace std;int input()
{char ch;while((ch=getchar())<'0'||ch>'9');int ret=ch-'0';while((ch=getchar())>='0'&&ch<='9')ret=(ret<<1)+(ret<<3)+ch-'0';return ret;
}int main()
{int n;map<int,int>counter;map<int,int>::iterator counter_i;while((n=input())){counter.clear();for(int i=1;i<=n;i++)counter[input()]++;for(counter_i=counter.begin();counter_i!=counter.end();counter_i++){if(counter_i->second&1){printf("%d\n",counter_i->first);break;}}}return 0;
}

​

• 1.2.4.Rightmost Digit(P1061)：

  • 输出N的N次方结果的最后一位，那么对于底数，只要考虑个位即可，就只有十种情况（0～9），对应的答案就是：
    • 0（有1种）：都是0
    • 1（1）：都是1
    • 2（4）：2、4、8、6、2。。循环
    • 3（4）：3、9、7、1、3。。循环
    • 4（2）：4、6、4。。。循环
    • 5（1）：都是5
    • 6（1）：都是6
    • 7（4）：7、9、3、1、7。。循环
    • 8（4）：8、4、2、6、8。。循环
    • 9（2）：9、1、9。。循环
  • 其中，又因为其指数也是n，所以答案只可能为上方加粗的部分，只有2、3、7、8需要分类
  • 注意！！$0^0=1$！！！

  #include<iostream>using namespace std;int main()
  {int T,n;scanf("%d",&T);while(T--){scanf("%d",&n);switch(n%10){case 0:puts(n?"0":"1");break;case 1:puts("1");break;case 2:switch(n%4){case 2:puts("4");break;case 0:puts("6");break;}break;case 3:switch(n%4){case 1:puts("3");break;case 2:puts("9");break;case 3:puts("7");break;case 0:puts("1");break;}break;case 4:puts("6");break;case 5:puts("5");break;case 6:puts("6");break;case 7:switch(n%4){case 1:puts("7");break;case 2:puts("9");break;case 3:puts("3");break;case 0:puts("1");break;}break;case 8:switch(n%4){case 2:puts("4");break;case 0:puts("6");break;}break;case 9:puts("9");break;}}return 0;
  }
  

• 1.2.5.The Seven Percent Solution(P2719)：

  • 在线处理即可，遍历字符串字符，如遇到特殊字符输出转换后结果，否则直接输出当前字符，直到遇到’#'结束

  #include<iostream>using namespace std;int main()
  {char ch;while((ch=getchar())^'#'){if(ch==' '){putchar('%');putchar('2');putchar('0');continue;}if(ch=='!'){putchar('%');putchar('2');putchar('1');continue;}if(ch=='$'){putchar('%');putchar('2');putchar('4');continue;}if(ch=='%'){putchar('%');putchar('2');putchar('5');continue;}if(ch=='('){putchar('%');putchar('2');putchar('8');continue;}if(ch==')'){putchar('%');putchar('2');putchar('9');continue;}if(ch=='*'){putchar('%');putchar('2');putchar('a');continue;}putchar(ch);}return 0;
  }
  

• 1.2.6.Just A Triangle(P3188)：

  • 三角形形状判定，如果是直角三角形输出’‘good’’，是等腰三角形输出’‘perfect’’，否则都输出’‘just a triangle’’
  • 解法：先将边按长度排序，特判直角and等腰，对每种情况输出anss

  #include<iostream>using namespace std;int main()
  {int n,a,b,c;scanf("%d",&n);while(n--){scanf("%d%d%d",&a,&b,&c);if(a>b)swap(a,b);if(b>c)swap(b,c);if(a>b)swap(a,b);if(a==b||b==c){puts("perfect");continue;}if(a*a+b*b==c*c){puts("good");continue;}puts("just a triangle");}return 0;
  }
  

• 1.2.7.IBM Minus One(P1328)：

  • 字符串转换，将每个字母转化为他的字母表的下一位
  • 特别的，将’Z’转化为’A’，然后按照一定格式输出（acm经典输出格式）
  • Print a blank line after each test case.

  #include<iostream>
  #include<string>using namespace std;int main()
  {int n;string str;scanf("%d\n",&n);for(int cas=1;cas<=n;cas++){printf("String #%d\n",cas);cin>>str;for(auto it:str)putchar(it^'Z'?it+1:'A');putchar('\n');putchar('\n');}return 0;
  }
  

• 1.2.8.Lowest Bit(P1196)：

  • 法1：输入一个十进制数，输出将其转化为二进制数后最低位的1的位置
    • anss=1;while(n&1) {anss++;n>>=1;}anss=1<<anss;
  • 法2：直接有取这一位的公式：(~n+1)\&n​

  #include<iostream>using namespace std;int main()
  {int n;while(scanf("%d",&n),n){printf("%d\n",(~n+1)&n);}return 0;
  }
  

Section Three - 数据结构初步、算法初步

**数据结构初步：**熟练运用STL、struct(class)、字符串处理

**算法初步：**排序、贪心

• 1.3.1.FatMouse’ Trade(P1009)：

  • 贪心，优先选择交换收获效率最高的房间内的JavaBean即可

  #include<iostream>
  #include<vector>
  #include<algorithm>using namespace std;struct room_
  {double j,f;room_(){}room_(int a,int b):j(a),f(b){}double rate(){return j/f;}room_ input(){scanf("%lf%lf",&j,&f);return *this;}
  };
  bool operator<(room_ a,room_ b)
  {return a.rate()<b.rate();}int main()
  {double n,m,anss;vector<room_>v;while(scanf("%lf%lf",&m,&n),n!=-1||m!=-1){v.clear();anss=0;for(int i=0;i<n;i++)v.push_back(room_().input());sort(v.begin(),v.end());// for(int i=0;i<n;i++)// 	cout<<v[i].j<<'\t'<<v[i].f<<endl;while(m&&!v.empty()){// cout<<v.back().j<<'\t'<<v.back().f<<endl;if(m>=v.back().f){anss+=v.back().j;m-=v.back().f;}else{anss+=v.back().j*m/v.back().f;break;}v.pop_back();}printf("%.3lf\n",anss);}return 0;
  }
  

• 1.3.2.百步穿杨(P2550)：

  • 用**pair<int,int>**储存一种箭的长度和数量
  • 按照长度排序，然后按照此顺序输出

  #include<iostream>
  #include<vector>
  #include<string>
  #include<algorithm>using namespace std;int input()
  {char ch;while((ch=getchar())<'0'||ch>'9');int ret=ch-'0';while((ch=getchar())>='0'&&ch<='9')ret=(ret<<1)+(ret<<3)+ch-'0';return ret;
  }bool cmp(pair<int,int>a,pair<int,int>b)
  {return a.first<b.first;}//排序方式void she(int a,int b)//射箭啦啦啦
  {string str=">+";for(int i=a-2;i>0;i--)str+="-";str+="+>\n";while(b--)cout<<str;putchar('\n');
  }int main()
  {int T,n;vector<pair<int,int>>v;scanf("%d",&T);while(T--){scanf("%d",&n);v.clear();for(int i=0,tem;i<n;i++)tem=input(),			//用pair的此处要注意！！v.push_back(pair<int,int>(tem,input()));sort(v.begin(),v.end(),cmp);for(int i=0;i<n;i++)she(v[i].first,v[i].second);// for(auto it:v)			//C++11// 	she(it.first,it.second);}return 0;
  }
  

• 1.3.3.开门人和关门人(P1234)：

  • 使用自定义结构体struct tim_，储存时间和其对应的人名
  • 遍历一遍，留下第一个时间戳最小的人名，和第二个时间戳最大的人名

  #include<iostream>
  #include<string>using namespace std;struct tim_
  {string name;int h,m,s;tim_(){};tim_(int a,int b,int c):h(a),m(b),s(c){}operator >(tim_ a){if(h^a.h)return h>a.h;if(m^a.m)return m>a.m;if(s^a.s)return s>a.s;return false;}operator <(tim_ a){if(h^a.h)return h<a.h;if(m^a.m)return m<a.m;if(s^a.s)return s<a.s;return false;}
  }ne,op,ed;int main()
  {int T,n;scanf("%d",&T);while(T--){scanf("%d",&n);op=tim_(25,0,0);ed=tim_(-1,0,0);while(n--){cin>>ne.name;scanf("%d:%d:%d",&ne.h,&ne.m,&ne.s);if(ne<op)op=ne;scanf("%d:%d:%d",&ne.h,&ne.m,&ne.s);if(ne>ed)ed=ne;}cout<<op.name<<' '<<ed.name<<endl;}return 0;
  }
  

• 1.3.4.第二小整数(P2561)：

  • 就是第二小整数（之前听说有种东西叫：LRU算法）

  #include<iostream>using namespace std;int main()
  {int T,n,val,mi,mii;//最小数mi，第二小数miiscanf("%d",&T);while(T--){scanf("%d",&n);mi=mii=0x7fffffff;while(n--){scanf("%d",&val);if(val<=mi){mii=mi;mi=val;continue;}if(val<mii){mii=val;}}printf("%d\n",mii);}return 0;
  }
  

• 1.3.5.排序(P1106)：

  • 一种简单的做法是字符串扫描处理，我这里尝试的是用在线处理的方式解决

  #include<iostream>
  #include<queue>using namespace std;char ch;//ch还未处理的下一个字符
  int tin_res=0;
  char input_5()//输入合法的数字
  {while(ch<'0'||ch>'9'||ch=='5')ch=getchar();tin_res=ch-'0';while((ch=getchar())>='0'&&ch<='9'&&ch!='5')tin_res=(tin_res<<1)+(tin_res<<3)+ch-'0';return ch;
  }#define tin_number	1	//输入成功
  #define tin_endl	2	//行末
  #define tin_endflie	3	//文件结束
  int try_input()//尝试输入，并且返回输入结果
  {while(ch=='5')ch=getchar();if(ch=='\n'){ch=getchar();return tin_endl;}if(ch==EOF)return tin_endflie;input_5();return tin_number;
  }priority_queue<int,vector<int>,greater<int>>anss;void output()//输出并且清空现在的优先队列（已经存入的数）
  {while(!anss.empty()){printf("%d",anss.top());anss.pop();if(!anss.empty())putchar(' ');}return;
  }int main()
  {ch=getchar();while(1){switch(try_input()){case tin_number:// cout<<tin_res<<endl;anss.push(tin_res);break;case tin_endl:// cout<<"[\\n]"<<endl;output();putchar('\n');break;case tin_endflie:// cout<<"[end]"<<endl;output();return 0;}}return 0;
  }
  

• 1.3.6.考试排名(P2093)：

  • 按照题意进行字符串处理得到各选手的数据再按要求排序即可

  #include<iostream>
  #include<string>
  #include<vector>
  #include<algorithm>using namespace std;struct gamer_
  {string name;int accept,penalty;gamer_():name(""),accept(0),penalty(0){}void output(){// cout<<name<<'\t'<<accept<<'\t'<<penalty<<endl;printf("%-10s %2d %4d\n",name.c_str(),accept,penalty);return;}operator < (gamer_ a){if(accept^a.accept)return accept>a.accept;if(penalty^a.penalty)return penalty<a.penalty;return name<a.name;}
  };int main()
  {int n,m,player=-1;vector<gamer_>v;string str;scanf("%d%d\n",&n,&m);while(v.push_back(gamer_()),cin>>v[++player].name){for(int prb=1,j,jj,temp;prb<=n;prb++){cin>>str;if(str[0]<='0'||str[0]>'9')continue;v[player].accept++;for(temp=j=0,jj=str.size();str[j]>='0'&&str[j]<='9'&&j<jj;j++)temp=(temp<<1)+(temp<<3)+str[j]-'0';v[player].penalty+=temp;// cerr<<str<<"\t"<<temp<<'\t';temp=0;if(str[j]=='(')for(j++;str[j]^')';j++)temp=(temp<<1)+(temp<<3)+str[j]-'0';v[player].penalty+=temp*m;// cerr<<'('<<temp<<')'<<endl;}}v.pop_back();sort(v.begin(),v.end());for(int i=0,ii=v.size();i<ii;i++)v[i].output();return 0;
  }
  

• 1.3.7.Saving HDU(P2111)：

  • 第一眼以为多重背包，其实是贪心啦，排个序从价值大的开始选就行liao~

  #include<iostream>
  #include<vector>
  #include<algorithm>using namespace std;int input()
  {char ch;while((ch=getchar())<'0'||ch>'9');int ret=ch-'0';while((ch=getchar())>='0'&&ch<='9')ret=(ret<<1)+(ret<<3)+ch-'0';return ret;
  }struct treasure_
  {int p,m;treasure_(){}treasure_(int a,int b):p(a),m(b){}treasure_ in(){p=input();m=input();return treasure_(p,m);}void output(){cout<<"<treasure_> : "<<p<<'\t'<<m<<endl;return;}
  };bool operator<(treasure_ a,treasure_ b)
  {if(a.p^b.p)return a.p<b.p;return a.m<b.m;
  }
  treasure_ operator+(treasure_ a,treasure_ b)
  {return treasure_(a.p+b.p,a.m+b.m);
  }int main()
  {int v,n,anss;vector<treasure_>item;while(scanf("%d",&v),v){scanf("%d",&n);item.clear();anss=0;for(int i=0;i<n;i++)item.push_back(treasure_().in());sort(item.begin(),item.end());// for(auto it:item)// 	it.output();while(v&&!item.empty()){if(v>=item.back().m){anss+=item.back().p*item.back().m;v-=item.back().m;}else{anss+=item.back().p*v;v=0;break;}// item.back().output();// cout<<"after this anss = "<<anss<<endl;item.pop_back();}printf("%d\n",anss);}return 0;
  }
  

• 1.3.8.As Easy As A+B(P1040)：

  • 就是道裸的排序题

  #include<iostream>
  #include<vector>
  #include<algorithm>using namespace std;int input()
  {int ret;scanf("%d",&ret);return ret;
  }int main()
  {int T,n;vector<int>v;scanf("%d",&T);for(int cas=1;cas<=T;cas++){v.clear();scanf("%d",&n);for(int i=0;i<n;i++)v.push_back(input());sort(v.begin(),v.end());for(int i=0;i<n;i++)printf("%d%s",v[i],n-i-1?" ":"\n");}return 0;
  }
  

Chapter Two - 阶段2

Section One - 数论初步

**数论初步：**最大公约数（GCD）、最小公倍数（LCM）、筛质数

2.1.1.最小公倍数(P1108,LCM)

• 最小公倍数（LCM，Least common multiple）、最大公约数（GCD，Greatest common divisor）有以下关系：

  $$LCM(a,b)=a\ast b/GCD(a,b)$$

• GCD可由辗转相除法得到

#include<iostream>using namespace std;int gcd(int a,int b)
{while(a){b^=a;a^=b;b^=a;a%=b;}return b;
}int main()
{int a,b;while(~scanf("%d%d",&a,&b)){printf("%d\n",a*b/gcd(a,b));}return 0;
}

2.1.2.How many prime numbers(P2138)

• 筛质数、判断

#include<iostream>
#include<vector>
#include<bitset>using namespace std;#define SIZE_ 46441//ceil(sqrt(2147483648))+100
vector<unsigned int>prime;
bitset<SIZE_>isnp;
void built_prime()
{for(int i=2;i<SIZE_;i++){if(!isnp[i])prime.push_back(i);for(auto it:prime){if(it*i>=SIZE_)break;isnp[it*i]=true;}}// for(auto it:prime)// 	cout<<it<<endl;return;
}
bool isp(int a)//Is A a prime?
{//如果在遍历范围内特判，不然在下面的循环中会被自己除尽if(a<SIZE_)return !isnp[a];for(auto it:prime)if(a%it==0)return false;return true;
}int main()
{built_prime();int n,v,anss;while(~scanf("%d",&n)){anss=0;for(int i=0;i<n;i++){scanf("%d",&v);anss+=isp(v);}printf("%d\n",anss);}return 0;
}

2.1.3.相遇周期(P1713)

• 追击问题and分数处理
• 分析样例数据：

Sample Input:
2
26501/6335 18468/42
29359/11479 15725/19170
[v1 v2]Sample Output:
81570078/7
5431415
[anss]# Sample_1 :
anss % v1 = 0
anss % v2 = 0
anss / v1 = 2785590
anss / v2 = 26501
gcd of above2 : 1# Sample_2 :
anss % v1 = 0
anss % v2 = 0
anss / v1 = 2123615
anss / v2 = 6621318
gcd of above2 : 1# therefore :
anss=lcm(v1,v2)//在分数层面

2.1.4.

2.1.5.

2.1.6.

2.1.7.Leftmost Digit(P1060)

• 求$n^n$的最高位数字

• 尝试硬算指数结果，但是就算是快速幂要算出${(10^5)}^{(10^5)}$都要4.1s

• 但看到指数就要想起它的逆运算求对数，结合科学计数法，有：

$$\begin{gathered} \because 科学计数法有n^n=x{.}_{....}\times 10^y \\ \therefore lo{g}_{10}{n}^n=n\times lo{g}_{10}n=lo{g}_{10}x{.}_{....}+y \\ \therefore lo{g}_{10}x{.}_{....}=n\times lo{g}_{10}n-y \\ \because 其中1\le x{.}_{....}<10 \\ \therefore lo{g}_{10}x{.}_{....}<1,y=floor(n\times lo{g}_{10}n) \\ \therefore x=10^{lo{g}_{10}x}=10^{n\times lo{g}_{10}n-floor(n\times lo{g}_{10}n)} \end{gathered}$$

• 综上所述，我们最终可以得到解题关键：

  double temp=n*log(n)/log(10);

  double anss=pow(10,temp-floor(temp));

  printf("%.0lf\n",floor(anss));

• 事后：结论的式子和欧拉降幂的公式极其相似

#include<bits/stdc++.h>using namespace std;int main()
{int T,n;scanf("%d",&T);while(T--){scanf("%d",&n);double temp=1.*n*log(n)/log(10);int anss=floor(pow(10,temp-floor(temp)));printf("%d\n",anss);}return 0;
}

• 类似的，可以用科学计数法表示$n^m$（多组数据，每组占一行，包括两个正整数n、m）

#include<bits/stdc++.h>using namespace std;int main()
{int n,m;while(~scanf("%d %d",&n,&m)){double temp=1.*m*log(n)/log(10);double x=pow(10,temp-floor(temp));int y=floor(temp);printf("%lf x 10^%d\n",x,y);}return 0;
}

2.1.8.小数化分数2(P1717)

• 这时道较为综合的数学基础题，要求我们把$(0,1)$之间的有理小数转化为分数形式（eg.0.086(0123)）
• 有限位数的分数形式：化简有效位数/10^有效位数（eg.$\frac{123}{9999}=\frac{41}{3333}$）
• 循环位数的分数形式：化简有效位数/有效位数个9（eg.$\frac{86}{1000}=\frac{43}{500}$）
• 上两步骤注意前导0！！
• 求有限位数的分数形式于循环部分的分数形式和（eg.$\frac{41}{3333}+\frac{43}{500}=anss$）
• 中间可能超过int所以数据要用long long类型噢ii

#include<iostream>
#include<string>using namespace std;//把除了main()外的int改为TNT，然后。。【WA to AC的最后一步】
#define TNT long long//最大公约数（GCD，Greatest common divisor）
TNT gcd(TNT a,TNT b)
{while(a){a^=b;b^=a;a^=b;a%=b;}return b;
}//最小公倍数（LCM，Least common multiple）
TNT lcm(TNT a,TNT b)
{return a/gcd(a,b)*b;
}//约分（Reduction of a fraction）
pair<TNT,TNT>red(pair<TNT,TNT>a)
{TNT temp=gcd(a.first,a.second);return pair<TNT,TNT>(a.first/temp,a.second/temp);
}//the maximum number of the same digits相同位数的最大值(99..9)
TNT sd9(TNT a)//same digits of 9s
{TNT ret=0;while(a){ret=(ret<<1)+(ret<<3)+9;a/=10;}return ret;
}//10^a
TNT pow10(TNT a)
{TNT ret=1;while(a--)ret=(ret<<1)+(ret<<3);return ret;
}//分数(Fractional)相加
pair<TNT,TNT>frac_plus(pair<TNT,TNT>a,pair<TNT,TNT>b)
{TNT temp=lcm(a.second,b.second);return red(pair<TNT,TNT>(a.first*temp/a.second+b.first*temp/b.second,temp));
}int main()
{TNT T,pre_a,pre_b,a,b,i;//a:有限部分;b:循环部分;其等于-1(EOF)时不存在string str;pair<TNT,TNT>pa,pb;//写成分数形式的a,bcin>>T;while(T--){cin>>str;b=-1;pre_a=pre_b=a=0;for(i=2;str[i]=='0'&&i<(TNT)str.size();i++)pre_a++;for(;str[i]>='0'&&str[i]<='9'&&i<(TNT)str.size();i++)a=(a<<1)+(a<<3)+str[i]-'0';a=a?a:-1;if(str[i]=='('){for(i++;str[i]=='0';i++)pre_b++;for(b=0;str[i]>='0'&&str[i]<='9'&&i<(TNT)str.size();i++)b=(b<<1)+(b<<3)+str[i]-'0';}// cout<<str<<endl// 	<<"a = "<<a<<'('<<pre_a<<')'<<endl// 	<<"b = "<<b<<'('<<pre_b<<')'<<endl;if(~a)pa=red(pair<TNT,TNT>(a,(sd9(a)+1)*pow10(pre_a)));else pa=pair<TNT,TNT>(0,1);if(~b)pb=red(pair<TNT,TNT>(b,sd9(b*pow10(pre_b))*pow10(pre_a)*(~a?(sd9(a)+1):1)));else pb=pair<TNT,TNT>(0,1);// 分数形式anss=分数形式pa+分数形式pb;pa=red(frac_plus(pa,pb));cout<<pa.first<<'/'<<pa.second<<endl;}return 0;
}

---

Problems Set

P1000 A + B Problem

• 这是一道最基础的不定组数数据输入输出练习

#include<iostream>using namespace std;int main()
{int a,b;while(~scanf("%d%d",&a,&b))printf("%d\n",a+b);return 0;
}

P1001 Sum Problem

• 这是数学求和公式题
• 万恶的followed by a blank line首次出现的地方

#include<iostream>using namespace std;int main()
{unsigned int n;while(~scanf("%d",&n)){printf("%u\n\n",n*(n+1)>>1);}return 0;
}

P1002 A + B Problem II

• 这是高精加的模板题

#include<iostream>
#include<string>
#include<algorithm>using namespace std;string add(string a,string b)
{if(a.size()<b.size())swap(a,b);reverse(a.begin(),a.end());reverse(b.begin(),b.end());int i,ii=b.size();for(i=0;i<ii;i++){a[i]+=b[i]-'0';if(a[i]>'9'){a[i]-=10;a[i+1]++;}}for(ii=a.size();i<ii;i++){if(a[i]>'9'){a[i]-=10;a[i+1]++;}}if(a[ii]==1)a+='1';reverse(a.begin(),a.end());return a;
}int main()
{int n;string a,b;scanf("%d",&n);for(int i=1;i<=n;i++){if(i^1)putchar('\n');cin>>a>>b;printf("Case %d:\n%s + %s = %s\n",i,a.c_str(),b.c_str(),add(a,b).c_str());}return 0;
}

P1003 Max Sum

• 动规dp，求和最大的序列
• 出现了！同样万恶的Output a blank line between two cases！！

#include<iostream>using namespace std;int val[100007];int main(void)
{int T,n,sum,l,r,val_min,nex_l;scanf("%d",&T);for(int cas=1;cas<=T;cas++){if(cas^1)putchar('\n');scanf("%d",&n);scanf("%d",val+1);l=r=nex_l=1;sum=val[1];val_min=0;if(val[1]<val_min){nex_l=2;val_min=val[1];}for(int i=2;i<=n;i++){scanf("%d",val+i);val[i]+=val[i-1];if(val[i]-val_min>sum){l=nex_l;r=i;sum=val[i]-val_min;}if(val[i]<val_min){nex_l=i+1;val_min=val[i];}}printf("Case %d:\n%d %d %d\n",cas,sum,l,r);// for (int i = 0; i <= n; ++i)// 	printf("%d ",val[i]);// printf("\n%d\n",val_min);}return 0;
}

P1004 Let the Balloon Rise

• 基础容器map的使用

• 出现了经典句式：

  A test case with N = 0 terminates the input and this test case is not to be processed.

#include<iostream>
#include<string>
#include<map>using namespace std;map<string,int>counter;
map<string,int>::iterator it;int main()
{int n,maxx;string str;while(scanf("%d",&n),n){counter.clear();for(int i=1;i<=n;i++){cin>>str;// cout<<str<<endl;counter[str]++;}maxx=0;for(it=counter.begin();it!=counter.end();it++){if(it->second>maxx){maxx=it->second;str=it->first;}}cout<<str<<endl;}return 0;
}

P1005 Number Sequence

• 看数据$n\le 10^8$，明显这是一道找规律的题目
• 那么根据题给公式$f(1)=1,f(2)=1,f(n)=(A\ast f(n-1)+B\ast f(n-2))mod7$，$f(n)$只与$f(n-1)$和$f(n-2)$有关，且三者都只有$[0,,6]$这7种可能的取值
• 简言之，$f(n-1)\in [0,,6],f(n-2)\in [0,,6],f(n)$的决定式可能的情况就只剩$7\times 7=49$种了，也就是最多每49个数一个轮回，而且每49个数一定会是一个轮回（可证明噢~）
• 第一种解法：

#include<iostream>using namespace std;int main()
{int a,b,n,val_2,val_1,val;while(scanf("%d%d%d",&a,&b,&n),a||b||n){n%=49;val_2=val_1=val=1;for(int i=3;i<=n;i++){val=(a*val_1+b*val_2)%7;val_2=val_1;val_1=val;}printf("%d\n",val);}return 0;
}

• 第二个解法，找出循环节（注意：不一定会回到开始的$1,1$，不知道为啥这样的写法也是可以A的）

#include<iostream>
#include<vector>using namespace std;vector<int>sta;int main()
{int a,b,n,i;while(scanf("%d%d%d",&a,&b,&n),a||b||n){sta.clear();sta.push_back(1);sta.push_back(1);sta.push_back(1);for(i=3;i<10000;i++){sta.push_back((a*sta[i-1]+b*sta[i-2])%7);if(sta[i]==1&&sta[i-1]==1)break;}if(i>n){printf("%d\n",sta[n]);continue;}// for(int i=1;i<(int)sta.size();i++)//     cout<<sta[i]<<' ';i-=2;sta[0]=sta[i];printf("%d\n",sta[n%i]);}return 0;
}

P1006 Tick and Tick

• 关键词：时钟上的三根指针关系。画图，首先固定一根时针，然后确定分针的活动范围（时针顺时针逆时针两方向的D°开外），再对选取部分分针可能高兴的位置，放置秒针。。
• 最后得到的。。。

P1007 Quoit Design

P1008

P1009 FatMouse’ Trade

• 【1.3.1】

#include<iostream>
#include<vector>
#include<algorithm>using namespace std;struct room_
{double j,f;room_(){}room_(int a,int b):j(a),f(b){}double rate(){return j/f;}room_ input(){scanf("%lf%lf",&j,&f);return *this;}
};
bool operator<(room_ a,room_ b)
{return a.rate()<b.rate();}int main()
{double n,m,anss;vector<room_>v;while(scanf("%lf%lf",&m,&n),n!=-1||m!=-1){v.clear();anss=0;for(int i=0;i<n;i++)v.push_back(room_().input());sort(v.begin(),v.end());// for(int i=0;i<n;i++)// 	cout<<v[i].j<<'\t'<<v[i].f<<endl;while(m&&!v.empty()){// cout<<v.back().j<<'\t'<<v.back().f<<endl;if(m>=v.back().f){anss+=v.back().j;m-=v.back().f;}else{anss+=v.back().j*m/v.back().f;break;}v.pop_back();}printf("%.3lf\n",anss);}return 0;
}

P1010

P1011

P1012 u Calculate e

• 简单输出题，由样例，注意小数点后的位数（从3开始都是保留到第九位）

#include<iostream>using namespace std;int main()
{double anss=1;unsigned long long factorial=1;printf("n e\n- -----------\n0 1\n");for(int i=1;i<=9;i++){factorial*=i;anss+=1./factorial;printf("%d ",i);if(i<=2)cout<<anss<<endl;elseprintf("%.9lf\n",anss);}return 0;
}

P1013

P1014

P1015

P1016

P1017

P1018

P1019

P1020 Encoding

• 简单的字符串压缩

#include<iostream>
#include<string>using namespace std;int main()
{int T,i,ii,times;string str;scanf("%d",&T);while(T--){cin>>str;for(i=0,ii=str.size()-1;i<ii;i++){if(str[i]==str[i+1]){times=2;i++;while(str[i]==str[i+1]){times++;i++;}printf("%d%c",times,str[i-1]);}else{putchar(str[i]);}}putchar('\n');}return 0;
}

P1021

P1022

P1023

P1024

P1025

P1026

P1027

P1028

P1029

P1030

P1031

P1032

• 角谷猜想（冰雹猜想）的一般问题：问在i，j之间的角谷序列（我愿称之为此）长度最长的长度
• 需要注意，i不一定小等于j

#include<bits/stdc++.h>using namespace std;int main()
{int i,j,anss,cnt,temp;while(~scanf("%d%d",&i,&j)){printf("%d %d ",i,j);if(i>j)swap(i,j);anss=0;while(i<=j){for(cnt=1,temp=i;temp^1;cnt++)temp=(temp&1)?(temp*3+1):(temp>>1);anss=max(anss,cnt);i++;}printf("%d\n",anss);}return 0;
}

P1033

P1034

P1035 Robot Motion

• 按照规则走图，可能出现环或者走出迷宫，处理结果即可

#include<bits/stdc++.h>using namespace std;#define pii pair<int,int>#define move_N pii(-1, 0)//^
#define move_S pii( 1, 0)//v
#define move_E pii( 0, 1)//>
#define move_W pii( 0,-1)//<
pii char_to_pii(char ch)
{switch(ch){case 'N':return move_N;case 'S':return move_S;case 'E':return move_E;case 'W':return move_W;}return pii(0,0);
}int now_n,now_m;bool now_inside(pii loc)
{if(loc.first<1||loc.first>now_n||loc.second<1||loc.second>now_m)return false;return true;
}void operator+=(pii&a,pii b)
{a.first+=b.first;a.second+=b.second;return;
}int main()
{int now_start,now_step;vector<string>now_mapp;map<pii,int>now_route;pii now_loc,anss;string str;// //test:(pii)+=(pii)
// now_loc=pii(10,10);
// now_loc+=pii(1,-1);
// cout<<now_loc.first<<endl<<now_loc.second<<endl;
// cin>>str;while(scanf("%d%d",&now_n,&now_m),now_n||now_m){scanf("%d\n",&now_start);now_step=0;now_mapp.clear();now_mapp.push_back("");now_loc=pii(1,now_start);now_route.clear();anss=pii(0,0);for(int i=1;i<=now_n;i++){cin>>str;now_mapp.push_back(" "+str);}while(now_inside(now_loc)){now_step++;if(now_route[now_loc])//cycle appearance{anss=pii(now_route[now_loc]-1,now_step-now_route[now_loc]);break;}now_route[now_loc]=now_step;now_loc+=char_to_pii(now_mapp[now_loc.first][now_loc.second]);}if(anss==pii(0,0))anss=pii(now_step,0);if(anss.second)//cycle{printf("%d step(s) before a loop of %d step(s)\n", anss.first,anss.second);}else//exit{printf("%d step(s) to exit\n",anss.first);}// for(int i=1;i<=now_n;i++,putchar('\n'))// 	for(int j=1;j<=now_m;j++)// 		putchar(now_mapp[i][j]);// putchar('\n');// for(int i=1;i<=now_n;i++,putchar('\n'))// 	for(int j=1;j<=now_m;j++)// 		printf("%4d",now_route[pii(i,j)]);// cout<<endl;// cout<<"now_loc : "<<now_loc.first<<"\t"<<now_loc.second<<endl;// cout<<"anss    : "<<anss.first<<"\t"<<anss.second<<endl;// cout<<endl<<endl;}return 0;
}

P1036

P1037

P1038

P1039

P1040 As Easy As A+B

• 1.3.8

#include<iostream>
#include<vector>
#include<algorithm>using namespace std;int input()
{int ret;scanf("%d",&ret);return ret;
}int main()
{int T,n;vector<int>v;scanf("%d",&T);for(int cas=1;cas<=T;cas++){v.clear();scanf("%d",&n);for(int i=0;i<n;i++)v.push_back(input());sort(v.begin(),v.end());for(int i=0;i<n;i++)printf("%d%s",v[i],n-i-1?" ":"\n");}return 0;
}

P1041

P1042~1048

P1049 Climbing Worm

• 详见上方【A-C1-S2】总结

#include<iostream>using namespace std;int main()
{int n,u,d;while(scanf("%d%d%d",&n,&u,&d),n|u|d){printf("%d\n",((n-u)/(u-d)+bool((n-u)%(u-d)))*2+1);}return 0;
}

P1050~1059

P1060 Leftmost Digit

• 【2.1.7】

#include<bits/stdc++.h>using namespace std;int main()
{int T,n;scanf("%d",&T);while(T--){scanf("%d",&n);double temp=1.*n*log(n)/log(10);int anss=floor(pow(10,temp-floor(temp)));printf("%d\n",anss);}return 0;
}

• 类似的，可以用科学计数法表示$n^m$（多组数据，每组占一行，包括两个正整数n、m）

#include<bits/stdc++.h>using namespace std;int main()
{int n,m;while(~scanf("%d %d",&n,&m)){double temp=1.*m*log(n)/log(10);double x=pow(10,temp-floor(temp));int y=floor(temp);printf("%lf x 10^%d\n",x,y);}return 0;
}

P1061 Rightmost Digit

• 详见上方【A-C1-S2】总结

#include<iostream>using namespace std;int main()
{int T,n;scanf("%d",&T);while(T--){scanf("%d",&n);switch(n%10){case 0:puts(n?"0":"1");break;case 1:puts("1");break;case 2:switch(n%4){case 2:puts("4");break;case 0:puts("6");break;}break;case 3:switch(n%4){case 1:puts("3");break;case 2:puts("9");break;case 3:puts("7");break;case 0:puts("1");break;}break;case 4:puts("6");break;case 5:puts("5");break;case 6:puts("6");break;case 7:switch(n%4){case 1:puts("7");break;case 2:puts("9");break;case 3:puts("3");break;case 0:puts("1");break;}break;case 8:switch(n%4){case 2:puts("4");break;case 0:puts("6");break;}break;case 9:puts("9");break;}}return 0;
}

P1062~1088

P1089 A+B for Input-Output Practice (I)

• 详见上方【A-C1-S1】总结

#include<iostream>
#include<string>
#include<algorithm>using namespace std;string add(string a,string b)
{if(a.size()<b.size())swap(a,b);reverse(a.begin(),a.end());reverse(b.begin(),b.end());int i,ii=b.size();for(i=0;i<ii;i++){a[i]+=b[i]-'0';if(a[i]>'9'){a[i]-=10;a[i+1]++;}}for(ii=a.size();i<ii;i++){if(a[i]>'9'){a[i]-=10;a[i+1]++;}}if(a[ii]==1)a+='1';reverse(a.begin(),a.end());return a;
}int main()
{string a,b;while(cin>>a>>b){printf("%s\n",add(a,b).c_str());}return 0;
}

P1090 A+B for Input-Output Practice (II)

• 详见上方【A-C1-S1】总结

#include<iostream>
#include<string>
#include<algorithm>using namespace std;string add(string a,string b)
{if(a.size()<b.size())swap(a,b);reverse(a.begin(),a.end());reverse(b.begin(),b.end());int i,ii=b.size();for(i=0;i<ii;i++){a[i]+=b[i]-'0';if(a[i]>'9'){a[i]-=10;a[i+1]++;}}for(ii=a.size();i<ii;i++){if(a[i]>'9'){a[i]-=10;a[i+1]++;}}if(a[ii]==1)a+='1';reverse(a.begin(),a.end());return a;
}int main()
{int n;string a,b;scanf("%d",&n);for(int i=1;i<=n;i++){cin>>a>>b;printf("%s\n",add(a,b).c_str());}return 0;
}

P1091 A+B for Input-Output Practice (III)

• 详见上方【A-C1-S1】总结

#include<iostream>
#include<string>
#include<algorithm>using namespace std;string add(string a,string b)
{if(a.size()<b.size())swap(a,b);reverse(a.begin(),a.end());reverse(b.begin(),b.end());int i,ii=b.size();for(i=0;i<ii;i++){a[i]+=b[i]-'0';if(a[i]>'9'){a[i]-=10;a[i+1]++;}}for(ii=a.size();i<ii;i++){if(a[i]>'9'){a[i]-=10;a[i+1]++;}}if(a[ii]==1)a+='1';reverse(a.begin(),a.end());return a;
}int main()
{string a,b;while(cin>>a>>b,a!="0"||b!="0"){printf("%s\n",add(a,b).c_str());}return 0;
}

P1092 A+B for Input-Output Practice (IV)

• 详见上方【A-C1-S1】总结

#include<iostream>
#include<string>
#include<algorithm>using namespace std;string add(string a,string b)
{if(a.size()<b.size())swap(a,b);reverse(a.begin(),a.end());reverse(b.begin(),b.end());int i,ii=b.size();for(i=0;i<ii;i++){a[i]+=b[i]-'0';if(a[i]>'9'){a[i]-=10;a[i+1]++;}}for(ii=a.size();i<ii;i++){if(a[i]>'9'){a[i]-=10;a[i+1]++;}}if(a[ii]==1)a+='1';reverse(a.begin(),a.end());return a;
}int main()
{int n;string a,b;while(scanf("%d",&n),n){cin>>a;for(int i=1;i<n;i++){cin>>b;a=add(a,b);}printf("%s\n",a.c_str());}return 0;
}

P1093 A+B for Input-Output Practice (V)

• 详见上方【A-C1-S1】总结

#include<iostream>
#include<string>
#include<algorithm>using namespace std;string add(string a,string b)
{if(a.size()<b.size())swap(a,b);reverse(a.begin(),a.end());reverse(b.begin(),b.end());int i,ii=b.size();for(i=0;i<ii;i++){a[i]+=b[i]-'0';if(a[i]>'9'){a[i]-=10;a[i+1]++;}}for(ii=a.size();i<ii;i++){if(a[i]>'9'){a[i]-=10;a[i+1]++;}}if(a[ii]==1)a+='1';reverse(a.begin(),a.end());return a;
}int main()
{int n,T;string a,b;scanf("%d",&T);while(T--){scanf("%d",&n);cin>>a;for(int i=1;i<n;i++){cin>>b;a=add(a,b);}printf("%s\n",a.c_str());}return 0;
}

P1094 A+B for Input-Output Practice (VI)

• 详见上方【A-C1-S1】总结

#include<iostream>
#include<string>
#include<algorithm>using namespace std;string add(string a,string b)
{if(a.size()<b.size())swap(a,b);reverse(a.begin(),a.end());reverse(b.begin(),b.end());int i,ii=b.size();for(i=0;i<ii;i++){a[i]+=b[i]-'0';if(a[i]>'9'){a[i]-=10;a[i+1]++;}}for(ii=a.size();i<ii;i++){if(a[i]>'9'){a[i]-=10;a[i+1]++;}}if(a[ii]==1)a+='1';reverse(a.begin(),a.end());return a;
}int main()
{int n;string a,b;while(~scanf("%d",&n)){cin>>a;for(int i=1;i<n;i++){cin>>b;a=add(a,b);}printf("%s\n",a.c_str());}return 0;
}

P1095

• 详见上方【A-C1-S1】总结

#include<iostream>
#include<string>
#include<algorithm>using namespace std;string add(string a,string b)
{if(a.size()<b.size())swap(a,b);reverse(a.begin(),a.end());reverse(b.begin(),b.end());int i,ii=b.size();for(i=0;i<ii;i++){a[i]+=b[i]-'0';if(a[i]>'9'){a[i]-=10;a[i+1]++;}}for(ii=a.size();i<ii;i++){if(a[i]>'9'){a[i]-=10;a[i+1]++;}}if(a[ii]==1)a+='1';reverse(a.begin(),a.end());return a;
}int main()
{string a,b;while(cin>>a>>b){printf("%s\n\n",add(a,b).c_str());}return 0;
}

P1096

• 详见上方【A-C1-S1】总结

#include<iostream>
#include<string>
#include<algorithm>using namespace std;string add(string a,string b)
{if(a.size()<b.size())swap(a,b);reverse(a.begin(),a.end());reverse(b.begin(),b.end());int i,ii=b.size();for(i=0;i<ii;i++){a[i]+=b[i]-'0';if(a[i]>'9'){a[i]-=10;a[i+1]++;}}for(ii=a.size();i<ii;i++){if(a[i]>'9'){a[i]-=10;a[i+1]++;}}if(a[ii]==1)a+='1';reverse(a.begin(),a.end());return a;
}int main()
{int n,T;string a,b;scanf("%d",&T);// while(T--)						//法1for(int cas=1;cas<=T;cas++)					//法2{if(cas^1)putchar('\n');					//法2scanf("%d",&n);cin>>a;for(int i=1;i<n;i++){cin>>b;a=add(a,b);}printf("%s\n",a.c_str());// if(T)putchar('\n');			//法1}return 0;
}

P1097

P1098

P1099

P1106 排序

• 详见上方【A-C1-S3】总结

#include<iostream>
#include<queue>using namespace std;char ch;//ch还未处理的下一个字符
int tin_res=0;
char input_5()//输入合法的数字
{while(ch<'0'||ch>'9'||ch=='5')ch=getchar();tin_res=ch-'0';while((ch=getchar())>='0'&&ch<='9'&&ch!='5')tin_res=(tin_res<<1)+(tin_res<<3)+ch-'0';return ch;
}#define tin_number	1	//输入成功
#define tin_endl	2	//行末
#define tin_endflie	3	//文件结束
int try_input()//尝试输入，并且返回输入结果
{while(ch=='5')ch=getchar();if(ch=='\n'){ch=getchar();return tin_endl;}if(ch==EOF)return tin_endflie;input_5();return tin_number;
}priority_queue<int,vector<int>,greater<int>>anss;void output()//输出并且清空现在的优先队列（已经存入的数）
{while(!anss.empty()){printf("%d",anss.top());anss.pop();if(!anss.empty())putchar(' ');}return;
}int main()
{ch=getchar();while(1){switch(try_input()){case tin_number:// cout<<tin_res<<endl;anss.push(tin_res);break;case tin_endl:// cout<<"[\\n]"<<endl;output();putchar('\n');break;case tin_endflie:// cout<<"[end]"<<endl;output();return 0;}}return 0;
}

P1108 最小公倍数

• 2.1.1.

#include<iostream>using namespace std;int gcd(int a,int b)
{while(a){b^=a;a^=b;b^=a;a%=b;}return b;
}int main()
{int a,b;while(~scanf("%d%d",&a,&b)){printf("%d\n",a*b/gcd(a,b));}return 0;
}

P1196 Lowest Bit

• 详见上方【A-C1-S2】总结

#include<iostream>using namespace std;int main()
{int n;while(scanf("%d",&n),n){printf("%d\n",(~n+1)&n);}return 0;
}

P1234 开门人和关门人

• 详见上方【A-C1-S3】总结

#include<iostream>
#include<string>using namespace std;struct tim_
{string name;int h,m,s;tim_(){};tim_(int a,int b,int c):h(a),m(b),s(c){}operator >(tim_ a){if(h^a.h)return h>a.h;if(m^a.m)return m>a.m;if(s^a.s)return s>a.s;return false;}operator <(tim_ a){if(h^a.h)return h<a.h;if(m^a.m)return m<a.m;if(s^a.s)return s<a.s;return false;}
}ne,op,ed;int main()
{int T,n;scanf("%d",&T);while(T--){scanf("%d",&n);op=tim_(25,0,0);ed=tim_(-1,0,0);while(n--){cin>>ne.name;scanf("%d:%d:%d",&ne.h,&ne.m,&ne.s);if(ne<op)op=ne;scanf("%d:%d:%d",&ne.h,&ne.m,&ne.s);if(ne>ed)ed=ne;}cout<<op.name<<' '<<ed.name<<endl;}return 0;
}

P1328 IBM Minus One

• 详见上方【A-C1-S2】总结

#include<iostream>
#include<string>using namespace std;int main()
{int n;string str;scanf("%d\n",&n);for(int cas=1;cas<=n;cas++){printf("String #%d\n",cas);cin>>str;for(auto it:str)putchar(it^'Z'?it+1:'A');putchar('\n');putchar('\n');}return 0;
}

P1717 小数化分数2

• 【2.1.8】

#include<iostream>
#include<string>using namespace std;//把除了main()外的int改为TNT
#define TNT long long//最大公约数（GCD，Greatest common divisor）
TNT gcd(TNT a,TNT b)
{while(a){a^=b;b^=a;a^=b;a%=b;}return b;
}//最小公倍数（LCM，Least common multiple）
TNT lcm(TNT a,TNT b)
{return a/gcd(a,b)*b;
}//约分（Reduction of a fraction）
pair<TNT,TNT>red(pair<TNT,TNT>a)
{TNT temp=gcd(a.first,a.second);return pair<TNT,TNT>(a.first/temp,a.second/temp);
}//the maximum number of the same digits相同位数的最大值(99..9)
TNT sd9(TNT a)//same digits of 9s
{TNT ret=0;while(a){ret=(ret<<1)+(ret<<3)+9;a/=10;}return ret;
}//10^a
TNT pow10(TNT a)
{TNT ret=1;while(a--)ret=(ret<<1)+(ret<<3);return ret;
}//分数(Fractional)相加
pair<TNT,TNT>frac_plus(pair<TNT,TNT>a,pair<TNT,TNT>b)
{TNT temp=lcm(a.second,b.second);return red(pair<TNT,TNT>(a.first*temp/a.second+b.first*temp/b.second,temp));
}int main()
{TNT T,pre_a,pre_b,a,b,i;//a:有限部分;b:循环部分;其等于-1(EOF)时不存在string str;pair<TNT,TNT>pa,pb;//写成分数形式的a,bcin>>T;while(T--){cin>>str;b=-1;pre_a=pre_b=a=0;for(i=2;str[i]=='0'&&i<(TNT)str.size();i++)pre_a++;for(;str[i]>='0'&&str[i]<='9'&&i<(TNT)str.size();i++)a=(a<<1)+(a<<3)+str[i]-'0';a=a?a:-1;if(str[i]=='('){for(i++;str[i]=='0';i++)pre_b++;for(b=0;str[i]>='0'&&str[i]<='9'&&i<(TNT)str.size();i++)b=(b<<1)+(b<<3)+str[i]-'0';}// cout<<str<<endl// 	<<"a = "<<a<<'('<<pre_a<<')'<<endl// 	<<"b = "<<b<<'('<<pre_b<<')'<<endl;if(~a)pa=red(pair<TNT,TNT>(a,(sd9(a)+1)*pow10(pre_a)));else pa=pair<TNT,TNT>(0,1);if(~b)pb=red(pair<TNT,TNT>(b,sd9(b*pow10(pre_b))*pow10(pre_a)*(~a?(sd9(a)+1):1)));else pb=pair<TNT,TNT>(0,1);// 分数形式anss=分数形式pa+分数形式pb;pa=red(frac_plus(pa,pb));cout<<pa.first<<'/'<<pa.second<<endl;}return 0;
}

P2138 How many prime numbers

• 【2.1.2】

#include<iostream>
#include<vector>
#include<bitset>using namespace std;#define SIZE_ 46441//ceil(sqrt(2147483648))+100
vector<unsigned int>prime;
bitset<SIZE_>isnp;
void built_prime()
{for(int i=2;i<SIZE_;i++){if(!isnp[i])prime.push_back(i);for(auto it:prime){if(it*i>=SIZE_)break;isnp[it*i]=true;}}// for(auto it:prime)// 	cout<<it<<endl;return;
}
bool isp(int a)//Is A a prime?
{//如果在遍历范围内特判，不然在下面的循环中会被自己除尽if(a<SIZE_)return !isnp[a];for(auto it:prime)if(a%it==0)return false;return true;
}int main()
{built_prime();int n,v,anss;while(~scanf("%d",&n)){anss=0;for(int i=0;i<n;i++){scanf("%d",&v);anss+=isp(v);}printf("%d\n",anss);}return 0;
}

P2161 Primes

• 本质时筛质数，但是要注意该题的题设（1、2在本题不是质数；输入小等于0时就GG）

#include<bits/stdc++.h>using namespace std;#define DATA_MAX 16007vector<int>prime_table;
bitset<DATA_MAX>prime_isnp;
void prime_built()
{for(int i=2;i<DATA_MAX;i++){if(!prime_isnp[i])prime_table.push_back(i);for(auto it:prime_table)if(i*it<DATA_MAX)prime_isnp[i*it]=true;}prime_isnp[1]=true;return;
}int main()
{prime_built();prime_isnp[2]=true;int n,cas=1;while(scanf("%d",&n),n>0)printf("%d: %s\n",cas++,prime_isnp[n]?"no":"yes");return 0;
}

P2317 Nasty Hacks

• 详见上方【A-C1-S2】总结

#include<iostream>using namespace std;int main()
{int n,r,e,c;scanf("%d",&n);while(n--){scanf("%d%d%d",&r,&e,&c);c=r-e+c;//表示不加入广告的优势if(c)if(c>0)puts("do not advertise");elseputs("advertise");elseputs("does not matter");}return 0;
}

P2093 考试排名

• 【1.3.6】

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>using namespace std;struct gamer_
{string name;int accept,penalty;gamer_():name(""),accept(0),penalty(0){}void output(){// cout<<name<<'\t'<<accept<<'\t'<<penalty<<endl;printf("%-10s %2d %4d\n",name.c_str(),accept,penalty);return;}operator < (gamer_ a){if(accept^a.accept)return accept>a.accept;if(penalty^a.penalty)return penalty<a.penalty;return name<a.name;}
};int main()
{int n,m,player=-1;vector<gamer_>v;string str;scanf("%d%d\n",&n,&m);while(v.push_back(gamer_()),cin>>v[++player].name){for(int prb=1,j,jj,temp;prb<=n;prb++){cin>>str;if(str[0]<='0'||str[0]>'9')continue;v[player].accept++;for(temp=j=0,jj=str.size();str[j]>='0'&&str[j]<='9'&&j<jj;j++)temp=(temp<<1)+(temp<<3)+str[j]-'0';v[player].penalty+=temp;// cerr<<str<<"\t"<<temp<<'\t';temp=0;if(str[j]=='(')for(j++;str[j]^')';j++)temp=(temp<<1)+(temp<<3)+str[j]-'0';v[player].penalty+=temp*m;// cerr<<'('<<temp<<')'<<endl;}}v.pop_back();sort(v.begin(),v.end());for(int i=0,ii=v.size();i<ii;i++)v[i].output();return 0;
}

P2095 find your present (2)

• 详见上方【A-C1-S2】总结

#include<iostream>
#include<map>using namespace std;int input()
{char ch;while((ch=getchar())<'0'||ch>'9');int ret=ch-'0';while((ch=getchar())>='0'&&ch<='9')ret=(ret<<1)+(ret<<3)+ch-'0';return ret;
}int main()
{int n;map<int,int>counter;map<int,int>::iterator counter_i;while((n=input())){counter.clear();for(int i=1;i<=n;i++)counter[input()]++;for(counter_i=counter.begin();counter_i!=counter.end();counter_i++){if(counter_i->second&1){printf("%d\n",counter_i->first);break;}}}return 0;
}

P2111 Saving HDU

• 【1.3.7】

#include<iostream>
#include<vector>
#include<algorithm>using namespace std;int input()
{char ch;while((ch=getchar())<'0'||ch>'9');int ret=ch-'0';while((ch=getchar())>='0'&&ch<='9')ret=(ret<<1)+(ret<<3)+ch-'0';return ret;
}struct treasure_
{int p,m;treasure_(){}treasure_(int a,int b):p(a),m(b){}treasure_ in(){p=input();m=input();return treasure_(p,m);}void output(){cout<<"<treasure_> : "<<p<<'\t'<<m<<endl;return;}
};bool operator<(treasure_ a,treasure_ b)
{if(a.p^b.p)return a.p<b.p;return a.m<b.m;
}
treasure_ operator+(treasure_ a,treasure_ b)
{return treasure_(a.p+b.p,a.m+b.m);
}int main()
{int v,n,anss;vector<treasure_>item;while(scanf("%d",&v),v){scanf("%d",&n);item.clear();anss=0;for(int i=0;i<n;i++)item.push_back(treasure_().in());sort(item.begin(),item.end());// for(auto it:item)// 	it.output();while(v&&!item.empty()){if(v>=item.back().m){anss+=item.back().p*item.back().m;v-=item.back().m;}else{anss+=item.back().p*v;v=0;break;}// item.back().output();// cout<<"after this anss = "<<anss<<endl;item.pop_back();}printf("%d\n",anss);}return 0;
}

P2550 百步穿杨

• 详见上方【A-C1-S3】总结

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>using namespace std;int input()
{char ch;while((ch=getchar())<'0'||ch>'9');int ret=ch-'0';while((ch=getchar())>='0'&&ch<='9')ret=(ret<<1)+(ret<<3)+ch-'0';return ret;
}bool cmp(pair<int,int>a,pair<int,int>b)
{return a.first<b.first;}void she(int a,int b)
{string str=">+";for(int i=a-2;i>0;i--)str+="-";str+="+>\n";while(b--)cout<<str;putchar('\n');
}vector<pair<int,int>>v;int main()
{int T,n;scanf("%d",&T);while(T--){scanf("%d",&n);v.clear();for(int i=0,tem;i<n;i++)tem=input(),v.push_back(pair<int,int>(tem,input()));sort(v.begin(),v.end(),cmp);// for(int i=0;i<n;i++)		//Sorted Check// 	cout<<v[i].first<<' '<<v[i].second<<endl;for(int i=0;i<n;i++)she(v[i].first,v[i].second);// for(auto it:v)			//C++11// 	she(it.first,it.second);}return 0;
}

P2561 第二小整数

• 详见上方【A-C1-S3】总结

#include<iostream>using namespace std;int main()
{int T,n,val,mi,mii;//最小数mi，第二小数miiscanf("%d",&T);while(T--){scanf("%d",&n);mi=mii=0x7fffffff;while(n--){scanf("%d",&val);if(val<=mi){mii=mi;mi=val;continue;}if(val<mii){mii=val;}}printf("%d\n",mii);}return 0;
}

P2719 The Seven Percent Solution

• 详见上方【A-C1-S2】总结

#include<iostream>using namespace std;int main()
{char ch;while((ch=getchar())^'#'){if(ch==' '){putchar('%');putchar('2');putchar('0');continue;}if(ch=='!'){putchar('%');putchar('2');putchar('1');continue;}if(ch=='$'){putchar('%');putchar('2');putchar('4');continue;}if(ch=='%'){putchar('%');putchar('2');putchar('5');continue;}if(ch=='('){putchar('%');putchar('2');putchar('8');continue;}if(ch==')'){putchar('%');putchar('2');putchar('9');continue;}if(ch=='*'){putchar('%');putchar('2');putchar('a');continue;}putchar(ch);}return 0;
}

P3188

• 详见上方【A-C1-S2】总结

#include<iostream>using namespace std;int main()
{int n,a,b,c;scanf("%d",&n);while(n--){scanf("%d%d%d",&a,&b,&c);if(a>b)swap(a,b);if(b>c)swap(b,c);if(a>b)swap(a,b);if(a==b||b==c){puts("perfect");continue;}if(a*a+b*b==c*c){puts("good");continue;}puts("just a triangle");}return 0;
}

---

附件 - 合集

高精度模板（用vector_int表示，范围正整数）

/** 高精度	用vector_int表示正整数* * * 储存方式:* BigNum_ val;* val[0]=数字长度;* val[1]=个位数字;* val[2]=十位数字;* ......* val[val[0]]=最高位数字;* * * 已完成:* 		转换:		BigNum_trans	(val)* 		转换:		BigNum_trans(val,ret)* 		转换:		BigNum_trans	(str)* 		转换:		BigNum_trans(str,ret)* 		转换:		BigNum_trans(val,str)* 		输入:++	BigNum_input	(val)* 		输出:--	BigNum_output	(val)* 		比较:>=,<=,>,<* 		加法:+	BigNum_addition	(a,b,ret)* 		减法:-	BigNum_subtract	(a,b,ret)* 		乘法:*	BigNum_multiply	(a,b,ret)* 		次方:^	BigNum_power	(a,b,ret)* 		阶乘:		BigNum_factorial(val,ret)* 		位数:		BigNum_resize	(ret,val)//十进制位运算* 		除法:/	BigNum_division	(a,b,ret)* 		取余:%	BigNum_modulo	(a,b,ret)* 		大约:		BigNum_gcd		(a,b)* 		小倍:		BigNum_lcm		(a,b)* 		大约:		BigNum_gcd		(a,b,ret)* 		小倍:		BigNum_lcm		(a,b,ret)* * 未完成:* */#include<bits/stdc++.h>using namespace std;#define BigNum_ vector<int>const BigNum_ BigNum_0  {1, 0};
const BigNum_ BigNum_1  {1, 1};
const BigNum_ BigNum_ERR{1,-1};BigNum_ BigNum_trans(int val)
{BigNum_ ret;for(ret.push_back(0);val;ret[0]++){ret.push_back(val%10);val/=10;}return ret;
}void BigNum_trans(int val,BigNum_&ret)
{ret.clear();for(ret.push_back(0);val;ret[0]++){ret.push_back(val%10);val/=10;}return;
}BigNum_ BigNum_trans(string str)
{BigNum_ val;for(auto it:str)val.push_back(it-'0');val.push_back(str.size());reverse(val.begin(),val.end());return val;
}void BigNum_trans(string str,BigNum_&ret)
{ret.clear();for(auto it:str)ret.push_back(it-'0');ret.push_back(str.size());reverse(ret.begin(),ret.end());return;
}void BigNum_trans(BigNum_ val,string&str)
{str.clear();for(int i=val[0];i;i--)str+=(val[i]+'0');return;
}void BigNum_input(BigNum_&val)
{val.clear();string str;cin>>str;for(auto it:str)val.push_back(it-'0');val.push_back(str.size());reverse(val.begin(),val.end());return;
}void operator++(BigNum_&val)
{val.clear();string str;cin>>str;for(auto it:str)val.push_back(it-'0');val.push_back(str.size());reverse(val.begin(),val.end());return;
}void operator++(BigNum_&val,int)
{val.clear();string str;cin>>str;for(auto it:str)val.push_back(it-'0');val.push_back(str.size());reverse(val.begin(),val.end());return;
}void BigNum_output(BigNum_ val)
{for(int i=val[0];i;i--)putchar(val[i]+'0');return;
}void operator--(BigNum_ val)
{for(int i=val[0];i;i--)putchar(val[i]+'0');return;
}void operator--(BigNum_ val,int)
{for(int i=val[0];i;i--)putchar(val[i]+'0');return;
}bool operator>=(BigNum_&val_a,BigNum_&val_b)
{if(val_a[0]^val_b[0])return val_a[0]>val_b[0];for(int i=val_a[0];i;i--)if(val_a[i]^val_b[i])return val_a[i]>val_b[i];return true;
}bool operator<=(BigNum_&val_a,BigNum_&val_b)
{if(val_a[0]^val_b[0])return val_a[0]<val_b[0];for(int i=val_a[0];i;i--)if(val_a[i]^val_b[i])return val_a[i]<val_b[i];return true;
}bool operator>(BigNum_&val_a,BigNum_&val_b)
{if(val_a[0]^val_b[0])return val_a[0]>val_b[0];for(int i=val_a[0];i;i--)if(val_a[i]^val_b[i])return val_a[i]>val_b[i];return false;
}bool operator<(BigNum_&val_a,BigNum_&val_b)
{if(val_a[0]^val_b[0])return val_a[0]<val_b[0];for(int i=val_a[0];i;i--)if(val_a[i]^val_b[i])return val_a[i]<val_b[i];return false;
}void BigNum_addition(BigNum_&val_a,BigNum_&val_b,BigNum_&ret)
{ret.clear();ret.push_back(0);int i,ii=min(val_a[0],val_b[0]),this_dig,next_dig=0;for(i=1;i<=ii;i++){this_dig=val_a[i]+val_b[i]+next_dig;next_dig=this_dig/10;this_dig%=10;ret.push_back(this_dig);}for(ii=val_a[0];i<=ii;i++){this_dig=val_a[i]+next_dig;next_dig=this_dig/10;this_dig%=10;ret.push_back(this_dig);}for(ii=val_b[0];i<=ii;i++){this_dig=val_b[i]+next_dig;next_dig=this_dig/10;this_dig%=10;ret.push_back(this_dig);}if(next_dig){ret.push_back(next_dig);i++;}ret[0]=i-1;return;
}BigNum_ operator+(BigNum_ val_a,BigNum_ val_b)
{BigNum_ ret;ret.push_back(0);int i,ii=min(val_a[0],val_b[0]),this_dig,next_dig=0;for(i=1;i<=ii;i++){this_dig=val_a[i]+val_b[i]+next_dig;next_dig=this_dig/10;this_dig%=10;ret.push_back(this_dig);}for(ii=val_a[0];i<=ii;i++){this_dig=val_a[i]+next_dig;next_dig=this_dig/10;this_dig%=10;ret.push_back(this_dig);}for(ii=val_b[0];i<=ii;i++){this_dig=val_b[i]+next_dig;next_dig=this_dig/10;this_dig%=10;ret.push_back(this_dig);}if(next_dig){ret.push_back(next_dig);i++;}ret[0]=i-1;return ret;
}void BigNum_subtract(BigNum_&val_a,BigNum_&val_b,BigNum_&ret)
{if(val_a<val_b){BigNum_subtract(val_b,val_a,ret);return;}ret=val_a;for(int i=val_b[0],j;i;i--){ret[i]-=val_b[i];if(ret[i]<0){for(j=i+1;!ret[j];j++)ret[j]=9;ret[j]--;ret[i]+=10;}}while(!ret[ret[0]]&&ret[0]>1)ret[0]--;ret.resize(ret[0]+1);return;
}BigNum_ operator-(BigNum_ val_a,BigNum_ val_b)
{if(val_a<val_b)return val_b-val_a;BigNum_ ret;ret=val_a;for(int i=val_b[0],j;i;i--){ret[i]-=val_b[i];if(ret[i]<0){for(j=i+1;!ret[j];j++)ret[j]=9;ret[j]--;ret[i]+=10;}}while(!ret[ret[0]]&&ret[0]>1)ret[0]--;ret.resize(ret[0]+1);return ret;
}void BigNum_multiply(BigNum_&val_a,BigNum_&val_b,BigNum_&ret)
{ret.clear();ret.push_back(val_a[0]+val_b[0]);for(int i=1,ii=ret[0],this_dig,next_dig=0;i<=ii;i++){this_dig=next_dig;for(int j=1;j<=i;j++)if(val_a[0]>=j&&val_b[0]>=i-j+1)this_dig+=val_a[j]*val_b[i-j+1];next_dig=this_dig/10;this_dig%=10;ret.push_back(this_dig);}ret[0]-=!ret[ret[0]];return;
}BigNum_ operator*(BigNum_ val_a,BigNum_ val_b)
{BigNum_ ret;ret.push_back(val_a[0]+val_b[0]);for(int i=1,ii=ret[0],this_dig,next_dig=0;i<=ii;i++){this_dig=next_dig;for(int j=1;j<=i;j++)if(val_a[0]>=j&&val_b[0]>=i-j+1)this_dig+=val_a[j]*val_b[i-j+1];next_dig=this_dig/10;this_dig%=10;ret.push_back(this_dig);}ret[0]-=!ret[ret[0]];return ret;
}void BigNum_power(BigNum_&val_a,BigNum_&val_b,BigNum_&ret)
{if(val_b[0]==1){if(val_b[1]==0){ret=BigNum_1;return;}if(val_b[1]==1){ret=val_a;return;}}if(val_a[0]==1)if(val_a[1]==1||!val_a[1]){ret=val_a;return;}BigNum_ half_b,double_a;int this_dig,next_dig=0;half_b=val_b;for(int i=half_b[0];i;i--){this_dig=next_dig;next_dig=half_b[i]&1?5:0;half_b[i]=half_b[i]/2+this_dig;}while(!half_b[half_b[0]])half_b[0]--;double_a=val_a*val_a;if(val_b[1]&1){// ret=(double_a^half_b)*val_a;BigNum_ temp;BigNum_power(double_a,half_b,temp);BigNum_multiply(temp,val_a,ret);}else{// ret=double_a^half_b;BigNum_power(double_a,half_b,ret);}return;
}BigNum_ operator^(BigNum_ val_a,BigNum_ val_b)
{if(val_b[0]==1){if(val_b[1]==0)return BigNum_1;if(val_b[1]==1)return val_a;}if(val_a[0]==1)if(val_a[1]==1||!val_a[1])return val_a;BigNum_ half_b,double_a;int this_dig,next_dig=0;half_b=val_b;for(int i=half_b[0];i;i--){this_dig=next_dig;next_dig=half_b[i]&1?5:0;half_b[i]=half_b[i]/2+this_dig;}while(!half_b[half_b[0]])half_b[0]--;double_a=val_a*val_a;if(val_b[1]&1)return (double_a^half_b)*val_a;elsereturn double_a^half_b;
}void BigNum_factorial(BigNum_&val,BigNum_&ret)
{ret=BigNum_1;for(BigNum_ i={1,1};i<=val;i=i+BigNum_1)ret=ret*i;return;
}void BigNum_resize(BigNum_&ret,int val)
{reverse(ret.begin(),ret.end());ret.pop_back();ret.resize(val);ret.push_back(val);reverse(ret.begin(),ret.end());return;
}void BigNum_division(BigNum_ val_a,BigNum_&val_b,BigNum_&ret)
{if(val_a<val_b){ret=BigNum_ {1,0};return;}if(val_b==BigNum_0){ret=BigNum_ERR;return;}ret.clear();ret.push_back(val_a[0]-val_b[0]+1);BigNum_resize(ret,ret[0]);for(int i=val_a[0],ii=val_b[0];i>=ii;i--){BigNum_resize(val_b,i);while(val_a>=val_b){val_a=val_a-val_b;ret[i-ii+1]++;}}while(!ret[ret[0]]&&ret[0]>1)ret[0]--;ret.resize(ret[0]+1);return;
}BigNum_ operator/(BigNum_ val_a,BigNum_ val_b)
{if(val_a<val_b)return BigNum_ {1,0};if(val_b==BigNum_0)return BigNum_ERR;BigNum_ ret;ret.push_back(val_a[0]-val_b[0]+1);BigNum_resize(ret,ret[0]);for(int i=val_a[0],ii=val_b[0];i>=ii;i--){BigNum_resize(val_b,i);while(val_a>=val_b){val_a=val_a-val_b;ret[i-ii+1]++;}}while(!ret[ret[0]]&&ret[0]>1)ret[0]--;ret.resize(ret[0]+1);return ret;
}void BigNum_modulo(BigNum_ val_a,BigNum_&val_b,BigNum_&ret)
{if(val_a<val_b){ret=val_a;return;}if(val_b==BigNum_0){ret=BigNum_ERR;return;}BigNum_resize(ret,ret[0]);for(int i=val_a[0],ii=val_b[0];i>=ii;i--){BigNum_resize(val_b,i);while(val_a>=val_b)val_a=val_a-val_b;}ret=val_a;while(!ret[ret[0]]&&ret[0]>1)ret[0]--;ret.resize(ret[0]+1);return;
}BigNum_ operator%(BigNum_ val_a,BigNum_ val_b)
{if(val_a<val_b)return val_a;if(val_b==BigNum_0)return BigNum_ERR;BigNum_ ret;for(int i=val_a[0],ii=val_b[0];i>=ii;i--){BigNum_resize(val_b,i);while(val_a>=val_b)val_a=val_a-val_b;}ret=val_a;while(!ret[ret[0]]&&ret[0]>1)ret[0]--;ret.resize(ret[0]+1);return ret;
}BigNum_ BigNum_gcd(BigNum_ val_a,BigNum_ val_b)
{while(val_a>BigNum_0){swap(val_a,val_b);val_a=val_a%val_b;}return val_b;
}void BigNum_gcd(BigNum_ val_a,BigNum_ val_b,BigNum_&ret)
{while(val_a>BigNum_0){swap(val_a,val_b);val_a=val_a%val_b;}ret=val_b;return;
}BigNum_ BigNum_lcm(BigNum_ val_a,BigNum_ val_b)
{return val_a*val_b/BigNum_gcd(val_a,val_b);
}void BigNum_lcm(BigNum_&val_a,BigNum_&val_b,BigNum_&ret)
{ret=val_a*val_b/BigNum_gcd(val_a,val_b);return;
}int main()
{// //test_used:// BigNum_ a,b,c;// (BigNum_trans(321))--;cout<<endl<<endl;//(BigNum_trans("321"))--;cout<<endl<<endl;// while(true)// {// 	a++;// 	b++;// BigNum_input(a);// BigNum_input(b);// BigNum_output(a);// BigNum_output(b);// cout<<"(a>b)="<<(a>b)<<endl;// cout<<"(a<b)="<<(a<b)<<endl;// cout<<"(a>=b)="<<(a>=b)<<endl;// cout<<"(a<=b)="<<(a<=b)<<endl;// a--;// if(a==b)// 	cout<<"=";// if(a<b)// 	cout<<"<";// if(a>b)// 	cout<<">";// b--;cout<<endl;// // c=a+b;// BigNum_addition(a,b,c);// a--;cout<<"+";b--;cout<<"=";c--;cout<<endl;// // c=a-b;// BigNum_subtract(a,b,c);// a--;cout<<"-";b--;cout<<"=";c--;cout<<endl;// // c=a*b;// BigNum_multiply(a,b,c);// a--;cout<<"x";b--;cout<<"=";c--;cout<<endl;// // c=a/b// // c=a^b;// BigNum_power(a,b,c);// a--;cout<<"^";b--;cout<<"=";c--;cout<<endl;// // c=a!;// BigNum_factorial(a,c);// a--;cout<<"!=";c--;cout<<endl;// // c=a/b;// BigNum_division(a,b,c);// a--;cout<<"/";b--;cout<<"=";c--;cout<<endl;// // c=a%b;// BigNum_modulo(a,b,c);// a--;cout<<"%";b--;cout<<"=";c--;cout<<endl;// c=BigNum_gcd(a,b);// BigNum_gcd(a,b,c);// cout<<"gcd(";a--;cout<<",";b--;cout<<")=";c--;cout<<endl;// // c=BigNum_lcm(a,b);// BigNum_lcm(a,b,c);// cout<<"lcm(";a--;cout<<",";b--;cout<<")=";c--;cout<<endl;// }return 0;
}

---