【历史遗留】还有记录的:HDOJ-刷题.md

HDOJの旅

[by_041]

曾经有一个 序


目录

文章目录

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;
}

文章目录

上一篇:牛客多校(2020第五场) E Bogo Sort


下一篇:如何在C中添加2个任意大小的整数?