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
  • 所以可以得到公式： a n s s = ( ( n − u ) / ( u − d ) + b o o l ( ( n − u ) % ( u − d ) ) ) ∗ 2 + 1 anss=((n-u)/(u-d)+bool((n-u)\%(u-d)))*2+1 anss=((n−u)/(u−d)+bool((n−u)%(u−d)))∗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");
            else
                puts("advertise");
        else
            puts("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 0^0=1 00=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，第二小数mii
  	scanf("%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）有以下关系：

  L C M ( a , b ) = a ∗ b / G C D ( a , b ) LCM(a,b)=a*b/GCD(a,b) LCM(a,b)=a∗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 n^n nn的最高位数字

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

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

∵ 科 学 计 数 法 有 n n = x . . . . . × 1 0 y ∴ l o g 10 n n = n × l o g 10 n = l o g 10 x . . . . . + y ∴ l o g 10 x . . . . . = n × l o g 10 n − y ∵ 其 中 1 ≤ x . . . . . < 10 ∴ l o g 10 x . . . . . < 1 , y = f l o o r ( n × l o g 10 n ) ∴ x = 1 0 l o g 10 x = 1 0 n × l o g 10 n − f l o o r ( n × l o g 10 n ) \because科学计数法有n^n=x._{....}\times10^y\\ \therefore log_{10}{n^n}=n\times log_{10}n=log_{10}x._{....}+y\\ \therefore log_{10}x._{....}=n\times log_{10}n-y\\ \because 其中1\le x._{....}<10\\ \therefore log_{10}x._{....}<1,y=floor(n\times log_{10}n)\\ \therefore x=10^{log_{10}x}=10^{n\times log_{10}n-floor(n\times log_{10}n)} ∵科学计数法有nn=x.....​×10y∴log10​nn=n×log10​n=log10​x.....​+y∴log10​x.....​=n×log10​n−y∵其中1≤x.....​<10∴log10​x.....​<1,y=floor(n×log10​n)∴x=10log10​x=10n×log10​n−floor(n×log10​n)

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

  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 nm（多组数据，每组占一行，包括两个正整数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 ) (0,1) (0,1)之间的有理小数转化为分数形式（eg.0.086(0123)）
• 有限位数的分数形式：化简有效位数/10^有效位数（eg. 123 9999 = 41 3333 \frac{123}{9999}=\frac{41}{3333} 9999123​=333341​）
• 循环位数的分数形式：化简有效位数/有效位数个9（eg. 86 1000 = 43 500 \frac{86}{1000}=\frac{43}{500} 100086​=50043​）
• 上两步骤注意前导0！！
• 求有限位数的分数形式于循环部分的分数形式和（eg. 41 3333 + 43 500 = a n s s \frac{41}{3333}+\frac{43}{500}=anss 333341​+50043​=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,b
	cin>>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 ≤ 1 0 8 n\leq10^8 n≤108，明显这是一道找规律的题目
• 那么根据题给公式 f ( 1 ) = 1 , f ( 2 ) = 1 , f ( n ) = ( A ∗ f ( n − 1 ) + B ∗ f ( n − 2 ) ) m o d 7 f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7 f(1)=1,f(2)=1,f(n)=(A∗f(n−1)+B∗f(n−2))mod7， f ( n ) f(n) f(n)只与 f ( n − 1 ) f(n-1) f(n−1)和 f ( n − 2 ) f(n-2) f(n−2)有关，且三者都只有 [ 0 , , 6 ] [0,,6] [0,,6]这7种可能的取值
• 简言之， f ( n − 1 ) ∈ [ 0 , , 6 ] , f ( n − 2 ) ∈ [ 0 , , 6 ] , f ( n ) f(n-1)\in[0,,6],f(n-2)\in[0,,6],f(n) f(n−1)∈[0,,6],f(n−2)∈[0,,6],f(n)的决定式可能的情况就只剩 7 × 7 = 49 7\times7=49 7×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 1,1 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;
		else
			printf("%.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 nm（多组数据，每组占一行，包括两个正整数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--)						//法1
	for(int cas=1;cas<=T;cas++)					//法2
	{
		if(cas^1)putchar('\n');					//法2
		scanf("%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,b
	cin>>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 16007

vector<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");
			else
				puts("advertise");
		else
			puts("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，第二小数mii
	scanf("%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;
	else
		return 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;
}

文章目录

• 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表示，范围正整数）