Skip to content

Latest commit

 

History

History
2377 lines (1787 loc) · 31.8 KB

02.甲级C++11版本.md

File metadata and controls

2377 lines (1787 loc) · 31.8 KB

PTA上A级

注意，我自己习惯用的多组输入输出在PAT的败北（要注意！！！！！！总结）

A1001 A+B Format

一、思路和难点

二、代码（别人的）

#include <iostream>
#include <stack>
using namespace std;
int main()
{
    stack <int> s;
    long int a,b,x;
    int bool_1=0;
    int j=0,k=0;
    cin>>a>>b;
    x=a+b;

   if(x==0)
   {
       cout<<x;
       return 0;
   }
    
    if(x<0)
    {
        x=x*(-1);
        bool_1=1;
    }
    while(x)
    {
        s.push(x%10);
        x/=10;
        j++;
    }
    while (!s.empty())
    {
        if(bool_1==1)
        {
              cout<<'-';
              bool_1=0;
        }
        j--;
        cout<<s.top();
        s.pop();

        if(j%3==0&&j!=0)
            cout<<',';
    }
    return 0;
}

A 1002 A+B for Polynomials

  • 坑点1：最坑的一组数据：
  • 格式错误：
  • len=0的时候，直接输出0，后面不能加空格
  • 这格式真是让人服了。
  • 坑点2：如果正好相反的浮点数，那么最后这个就不能打印出来！
#include<bits/stdc++.h>
using namespace std;

static const double eps=1e-9;

int main()
{
	map<int,double> mp;

	int loop,num;
	double val;
	scanf("%d",&loop);
	while( loop-- )
	{
		scanf("%d%lf",&num, &val);
		if( mp.find(num)!=mp.end() )
		{
			mp[num]+=val;
		}
		else
		{
			mp[num]=val;
		}
	}

	scanf("%d",&loop);
	while( loop-- )
	{
		scanf("%d%lf",&num, &val);
		if( mp.find(num)!=mp.end() )
		{
			mp[num]+=val;
		}
		else
		{
			mp[num]=val;
		}
	}


	int len=0;
	//坑点2
	auto it=mp.rbegin();
	for(; it!=mp.rend(); ++it )
	{
		if( abs((*it).second-0.0)<eps )
		{
			continue;
		}	
		else
		{
			++len;
		}
	}

    //最坑的一组数据！！！
	if( 0==len )
	{
		printf("0\n");
		return 0;
	}

	it=mp.rbegin();
	printf("%d ", len );
	for(; it!=mp.rend(); ++it )
	{
		
		if( abs( (*it).second-0.0 )<eps )
		{
			continue;
		}	
		else
		{
			len--;
			//输出一定要是.1f格式
			printf("%d %.1lf%c",
			 (*it).first, (*it).second, len!=0 ? ' ' : '\n');
		}
		
	}

	//system("pause");
	return 0;
}

A1005 Spell It Right

  • 总是17/20，还有一个样例。。。后面发现是单词nine被我打成了nice。。。
  • 做个题目，单词还要会默写。。。
#include<bits/stdc++.h>
using namespace std;

static const int maxn=105;
char solve[maxn];

map<int,string> mp;
void init()
{
	string demo[10]={"zero", "one", "two", "three", "four",
	"five", "six", "seven", "eight", "nine"};
	for(int i=0; i<10; ++i)
	{
		mp[i]=demo[i];
	}
}


int main()
{
	init();
	while( ~scanf("%s",solve) )
	{

		int sum=0;

		int loop=strlen( solve );


		//下面是典型的char数组，用for auto的误区，它不会智能的把'\0'的不加，
		//它会把整个数组的元素都加一次
		//for( auto c : solve )
		while( loop-- )
		{
			sum+=( solve[loop]-'0' );
		}

		char out[105];
		sprintf(out, "%d", sum);
		int len=strlen( out );

		//printf("sum=%d\n",sum);
		for(int i=0; i<len; ++i )
		{
			printf("%s%c",mp[ out[i]-'0' ].c_str() , i!=(len-1)? ' ' : '\n');
		}

	}


	return 0;
}

A1006 Sign In and Sign Out

不是最优，但是排序的解法

或许解释了，如果是24小时制的排序比，12小时但是am和pm更好排序。

#include<bits/stdc++.h>
using namespace std;

int n;
struct node
{
	char name[20];
	int downA,downB,downC;
	int upA,upB,upC;
};

bool LessCmp(node a, node b)
{
	if( a.downA!=b.downA )
	{
		return a.downA<b.downA;
	}
	else
	{
		if( a.downB!=b.downB )
		{
			return a.downB<b.downB;
		}
		else
		{
			return a.downC<b.downC;

		}

	}
}

bool UpCmp(node a, node b)
{
	if( a.upA!=b.upA )
	{
		return a.upA>b.upA;
	}
	else
	{
		if( a.upB!=b.upB )
		{
			return a.upB>b.upB;
		}
		else
		{
			return a.upC>b.upC;
		}

	}
}

int main()
{

	while( ~scanf("%d",&n ) )
	{
		vector<node> solve;
		while(n--)
		{
			node temp;
			scanf("%s %d:%d:%d %d:%d:%d", temp.name, 
			&temp.downA, &temp.downB, &temp.downC, &temp.upA, &temp.upB, &temp.upC);

			solve.push_back(temp);
		}

		sort( solve.begin(), solve.end(), LessCmp);
		printf("%s ",solve[0].name);

		sort( solve.begin(), solve.end(), UpCmp);
		printf("%s\n",solve[0].name);
	}

	return 0;
}

A1008 Elevator

  • 水题
#include<bits/stdc++.h>
using namespace std;

static const int maxn=1e5+5;
int solve[maxn];
int pre=0;
int cur;
int n;

int main()
{
	while( ~scanf("%d",&n) )
	{
		int loop=n;
		while( loop-- )
		{
			scanf("%d",&solve[loop]);
		}

		int sum=0;
		cur=0;
		while( n-- )
		{
			cur=solve[n];
			if( cur==pre )
			{
				sum+=5;
			}
			else if( cur>pre )
			{
				sum+=(  (int)abs(cur-pre)*6+5  );
				pre=cur;
			}
			else
			{
				sum+=(  (int)abs(cur-pre)*4+5  );
				pre=cur;
			}
		}

		printf("%d\n", sum );
	}

	return 0;
}

A 1009 Product of Polynomials

  • 模拟
#include<bits/stdc++.h>
using namespace std;

static const double eps=1e-9;
static const int maxn=2e3+5;
double solve[maxn];
int loop;
int n;

struct node
{
	double num;
	int up;//位数
};

int main()
{
	
	while( ~scanf("%d",&n) )
	{
		int lenA,lenB;
		lenA=n;

		//对double的也是可以的
		memset( solve, 0, sizeof( solve ) );

		loop=n;
		vector<node> first(n);
		while( loop-- )
		{
			int up;
			double num;
			scanf("%d%lf",&up, &num);
			first[loop].up=up;
			first[loop].num=num;
		}

		scanf("%d",&n);
		loop=n;
		lenB=n;
		vector<node> second(n);
		while( loop-- )
		{
			int up;
			double num;
			scanf("%d%lf",&up, &num);
			second[loop].up=up;
			second[loop].num=num;
		}




		for(int i=0; i<lenA; ++i)
		{
			for(int j=0; j<lenB; ++j)
			{
				int up=first[i].up + second[j].up;
				double num=first[i].num * second[j].num;
				solve[up]+=num;
			}
		}



		int sum=0;
		loop=maxn;
		while( loop-- )
		{
            	
			if( abs(solve[loop]-0.0)>eps )
			{
				++sum;
			}
		}
		if( 0==sum )
		{
			printf("0\n");
			return 0;
		}
		else
		{
			printf("%d",sum);
		}

		loop=maxn;
		while( loop-- )
		{
			if( abs(solve[loop]-0.0)>eps )
			{
				printf(" %d %.1lf", loop, solve[loop] );
			}
		}

		printf("\n");

	}



	return 0;
}

A1011 World Cup Betting

虽然AC了，但是double的比较有瑕疵

#include<bits/stdc++.h>
using namespace std;

unordered_map<int,char> mp;
void init()
{
	mp[0]='W';
	mp[1]='T';
	mp[2]='L';
}

int main()
{
	init();
	double ans=1.0;
	double solve[3]={0.0};

	for(int i=0; i<3; ++i)
	{
		double temp;
		int index=0;
		for(int j=0; j<3; ++j)
		{
			scanf("%lf",&temp);
			if( temp>solve[i] )
			{
				solve[i]=temp;
				index=j;
			}
		}

		printf("%c ",mp[index] );
	}
	
	ans=ans*(solve[0]*solve[1]*solve[2]*0.65-1)*2;
	printf("%.2lf\n", ans );

	return 0;
}

A1019 General Palindromic Number

  • //b的进制这么大？？？大于26个字母，咋进制。。。 //那暗示我们直接用数字？？
  • 坑点：如上，结果似乎就是这样。。
//b的进制这么大？？？大于26个字母，咋进制。。。
//那暗示我们直接用数字？？
#include<bits/stdc++.h>
using namespace std;

static const int maxn=35;
int out[maxn];
int tag;
int n,b;


int solve()
{
	tag=0;
	memset( out, 0, sizeof( out ) );
    
    //这是个人求进制转换的『模板代码』
	while( n )
	{
		out[tag++]=n%b;
		n/=b;
	}

	int L=0,R=tag-1;
	while( L<R )
	{
		if( out[L]!=out[R] )
		{
			return 0;
		}
		++L;
		--R;
	}

	return 1;

}


int main(int argc, char const *argv[])
{
	
	while( ~scanf("%d%d",&n, &b) )
	{
		printf("%s\n", solve() ? "Yes" : "No");
		
		while( tag-- )
		{
			printf("%d%c",out[tag], 0!=tag ? ' ' : '\n' );
		}
		
	}


	return 0;
}

A1020 Tree Traversals

  • 本题，我故意没有使用『多组输入和输出』
  • 这是一道模板题
#include<bits/stdc++.h>
using namespace std;

int n;
int postTree[35];
int inTree[35];

struct TreeNode
{
	int val;
	TreeNode * Left;
	TreeNode * Right;
	TreeNode( int _val ): val(_val), Left( nullptr ), Right(nullptr )
	{
	}
};

//注意，我设计的『左闭，右开』
TreeNode * CreateTree( int inBegin, int inEnd, int postBegin, int postEnd )
{
	if( inBegin==inEnd || postBegin==postEnd )
	{
		return nullptr;
	}

	TreeNode * root=new TreeNode( postTree[ postEnd-1] );
	int pos=inBegin;
	for(; pos<inEnd; ++pos )
	{
		if( inTree[pos]==root->val )
		{
			break;
		}
	}

	int Len=pos-inBegin;

	root->Left=CreateTree( inBegin, inBegin+Len, postBegin, postBegin+Len );
	root->Right=CreateTree( inBegin+Len+1, inEnd, postBegin+Len, postEnd-1 );
	return root;
}


vector<int> seq;
void BFS( TreeNode * root )
{
	if( nullptr==root )
	{
		return ;
	}

	queue<TreeNode * > solve;
	solve.push( root );
	while( !solve.empty() )
	{
		TreeNode * head=solve.front();
		solve.pop();
		seq.push_back( head->val );

		if( nullptr!=head->Left )
		{
			solve.push( head->Left );
		}

		if( nullptr!=head->Right )
		{
			solve.push( head->Right );
		}
	}

}


int main()
{
	//注意：这次，我们不使用『多组输入和输出』原因：那样，堆中新建的节点，我们需要
	//自行释放，增加代码量。
	scanf("%d",&n);
	//while( ~scanf("%d",&n) )
	{

		for(int i=0; i<n; ++i)
		{
			scanf("%d",&postTree[i]);
		}
		for(int i=0; i<n; ++i)
		{
			scanf("%d",&inTree[i]);
		}

		TreeNode * root=CreateTree( 0, n, 0, n);
		seq.clear();
		BFS( root );

		for( int i=0; i<n; ++i )
		{
			printf("%d%c", seq[i], (i!=n-1)? ' ' : '\n' );
		}
	}

	return 0;
}

A1025 PAT Ranking

  • 排名方式，编程技法
#include<bits/stdc++.h>
using namespace std;

static const int maxn=1e5+5;
int n,m;
struct node
{
	string id;
	int all;//总排名
	int group;//几号考场
	int rank;//单个考场排名
	int val;
};

node solve[maxn];
bool cmp(node a, node b)
{
	if( a.val!=b.val ) return a.val>b.val;
	else return a.id<b.id;
}


int main()
{
	while( ~scanf("%d",&n) )
	{
		int Left=0;
		int right=0;
		int loop=n;
		int curGroup=0;
		int sum=0;
		while( loop-- )
		{
			++curGroup;
			Left=right;
			scanf("%d",&m);
			int inLoop=m;
			sum+=m;
			while( inLoop-- )
			{
				++right;
				cin>>solve[Left+inLoop].id>>solve[Left+inLoop].val;
				solve[Left+inLoop].group=curGroup;
			}

			sort( solve+Left, solve+Left+m , cmp);
			if( m>0 )
			{
				solve[Left+0].rank=1;
			}
			int tag=1;
			for(int i=1; i<m; ++i)
			{
				++tag;
				if( solve[Left+i].val ==solve[Left+i-1].val )
				{
					solve[Left+i].rank=solve[Left+i-1].rank;
				}
				else
				{
					solve[Left+i].rank=tag;
				}
			}

		}

		cout<<sum<<endl;
		sort( solve, solve+sum , cmp);
		if( sum>0 )
		{
			solve[0].all=1;
		}
		int tag=1;
		for(int i=1; i<sum; ++i)
		{
			++tag;
			if( solve[i].val ==solve[i-1].val )
			{
				solve[i].all=solve[i-1].all;
			}
			else
			{
				solve[i].all=tag;
			}
		}

		for( int i=0; i<sum; ++i)
		{
			cout<<solve[i].id<<" "<<solve[i].all<<" "<<solve[i].group<<" "<<solve[i].rank<<endl;
		}

	}


	return 0;
}

A1027 Colors in Mars

  • 水题
  • 但是，要注意输出格式。
  • 当然，这题，最简洁的代码显然是『打表』，但是我暂时先训练STL，打表，以后增加
#include<bits/stdc++.h>
using namespace std;

map<int,char> mp;
void init()
{
	for(int i=0; i<10; ++i)
	{
		mp[i]='0'+i;
	}
	mp[10]='A';
	mp[11]='B';
	mp[12]='C';
}


void solve(int n)
{
	//坑点1，不足2位，要输出两位格式
	if( 0==n )
	{
		printf("00");
		return;
	}

	stack<char> st;
    //下面这个代码，可以说是『求进制转换的模板』，这个while循环要非常熟练
	while( n )
	{
		st.push( mp[n%13] );
		n/=13;
	}

	//坑点1，不足2位，要输出两位格式
	if( 2!=st.size() )
	{
		printf("0");
	}

	while( !st.empty() )
	{
		printf("%c",st.top() );
		st.pop();
	}

}

int main()
{
	int a,b,c;
	init();
	while( ~scanf("%d%d%d",&a,&b,&c) )
	{
		printf("#");
		solve(a);
		solve(b);
		solve(c);
		printf("\n");
	}

	return 0;
}

A1028 List Sorting

  • 排序规则『编程手法』
#include<bits/stdc++.h>
using namespace std;

int c,n;
struct node
{
	string id;//准考证号
	string name;
	int val;
};

bool cmp(node a, node b)
{
	if( 1==c )
	{
		return a.id<b.id;
	}
	else if( 2==c )
	{
		if( a.name!=b.name ) 
		{
			return a.name<b.name;
		}
		else
		{
			return a.id<b.id;
		}
	}
	else
	{
		if( a.val!=b.val )
		{
			return a.val<b.val;
		}
		else
		{
			return a.id<b.id;
		}
		
	}
}


int main()
{

	
	while( ~scanf("%d%d",&n,&c) )
	{
		int loop=n;
		vector<node> solve(n);
		while( loop-- )
		{
			cin>>  solve[loop].id >> solve[loop].name >> solve[loop].val;
		}

		sort( solve.begin(), solve.end(), cmp );
		for(int i=0; i<n; ++i)
		{
			cout<< solve[i].id <<" "<< solve[i].name << " "<< solve[i].val << endl;
		}
	}

	return 0;
}

A1031 | Hello World for U

  • 水题
  • 余数的使用，数学的考法
#include<bits/stdc++.h>
using namespace std;


static const int maxn=1e5+5;
char solve[maxn];

int main()
{

	while( ~scanf("%s",solve) )
	{
		int len=strlen( solve );
		int L=0,R=len-1,down;
		int loop=L;
		if( 0== (len+2)%3 )
		{
			down=loop=(len+2)/3;
		}
		else
		{
			loop=(len+2)/3;
			down=loop+(len+2)%3;
		}

		int TagTemp=down-2;
		--loop;
		while( loop-- )
		{
			printf("%c",solve[L++]);
			int tag=TagTemp;
			while( tag-- )
			{
				printf(" ");
			}
			printf("%c\n",solve[R--]);
		}

		while( down-- )
		{
			printf("%c",solve[L++]);
		}
		printf("\n");
	}

	return 0;
}

A1035 Password

  • 水题
  • 下面的代码，还可以通过设计『结构体』来写
#include<bits/stdc++.h>
using namespace std;

static const int maxn=1e3+5;
char one[maxn][15];
char two[maxn][15];
int n;
bool solve[maxn];

int main()
{
	while( ~scanf("%d",&n) )
	{

		memset( solve, 0, sizeof(solve) );
		int sum=0;//表示需要修改的个数
		int loop=n;
		while( loop-- )
		{
			scanf("%s %s",one[loop], two[loop]);
			int tag=0;//表示不用修改,如果修改就为1
			int len=strlen( two[loop] );
			for(int i=0; i<len; ++i)
			{
				if('1'==two[loop][i])
				{
					tag=1; 
					two[loop][i]='@';
					solve[loop]=true;
				}
				else if( 'l'==two[loop][i] )
				{
					tag=1;
					two[loop][i]='L';
					solve[loop]=true;
				}
				else if( '0'==two[loop][i] )
				{
					tag=1;
					two[loop][i]='%';
					solve[loop]=true;
				}
				else if( 'O'==two[loop][i] )
				{
					tag=1;
					two[loop][i]='o';
					solve[loop]=true;
				}

			}
			sum+=tag;
		}

		if( sum )
		{
			printf("%d\n",sum );
			while(n--)
			{
				if( solve[n] )
				{
					printf("%s %s\n",one[n], two[n] );
				}
			}
		}
		else
		{

			if( n<=1 )
			{
				printf("There is %d account and no account is modified\n", n);
			}
			else
			{
				printf("There are %d accounts and no account is modified\n",n );
			}
		}

	}

	return 0;
}

A1036（多组输入输出在PAT——神奇的败北之地）

  • 败北的原因，好像是PAT这个『单组输入输出』比较尴尬的原因

  • 两种写法都是，如果break;//不写就会超时，写了就不超时。。。。。竟然和秋招不一样。和牛客不一样。。。

1.。用的sort

#include<bits/stdc++.h>
using namespace std;

int n;
struct node
{
	char name[30];
	char gender;//性别
	char message[30];
	int val;
};

bool cmp( node a, node b)
{
	return a.val<b.val;
}

int main()
{

	while( scanf("%d",&n) )
	{
		vector<node> female;
		vector<node> male;

		while( n-- )
		{
			node temp;
			scanf("%s %c %s %d",temp.name, &temp.gender, temp.message, &temp.val );

			if( 'F'==temp.gender )
			{
				female.push_back( temp );
			}
			else
			{
				male.push_back( temp );
			}
            //cout<<"OK"<<endl;
		}

		sort( female.begin(), female.end(), cmp);
		sort( male.begin(), male.end(), cmp);

		int tag=0;//表示都有
		int maxFemale,minMale;
		if( 0==female.size() )
		{
			tag=1;
			printf("Absent\n");
		}
		else
		{
			auto it=female.rbegin();
			maxFemale=(*it).val;
			printf("%s %s\n", (*it).name, (*it).message );
		}


		if( 0==male.size() )
		{
			tag=1;
			printf("Absent\n");
		}
		else
		{
			auto it=male.begin();
			minMale=(*it).val;
			printf("%s %s\n", (*it).name, (*it).message );
		}

		if( tag )
		{
			printf("NA\n");
		}
		else
		{
			printf("%d\n", maxFemale-minMale );
		}
		break;//不写就会超时，写了就不超时。。。。。竟然和秋招不一样。和牛客不一样。。。
	}


	return 0;
}

2.。用的临时变量解法

#include<bits/stdc++.h>
using namespace std;

int n;
struct node
{
	char name[30];
	char gender;//性别
	char message[30];
	int val;

	node(){};
};

void cpy( node &really, node &ctor)
{
	strcpy(really.name, ctor.name);
	really.gender=ctor.gender;
	strcpy(really.message,ctor.message);
	really.val=ctor.val;
}

bool cmp( node a, node b)
{
	return a.val<b.val;
}

int main()
{

	while( scanf("%d",&n) )
	{
		node female;
		female.val=-1;
		node male;
		male.val=0x3f3f;

		while( n-- )
		{
			node temp;
			scanf("%s %c %s %d",temp.name, &temp.gender, temp.message, &temp.val );

			if( 'F'==temp.gender )
			{
				if( temp.val>female.val )
				{
					cpy( female, temp);
				}
			}
			else
			{
				if( temp.val<male.val )
				{
					cpy( male, temp);
				}
			}
            
		}


		int tag=0;//表示都有
		int maxFemale,minMale;
		if( -1==female.val )
		{
			tag=1;
			printf("Absent\n");
		}
		else
		{
			maxFemale=female.val;
			printf("%s %s\n", female.name, female.message );
		}


		if( 0x3f3f==male.val )
		{
			tag=1;
			printf("Absent\n");
		}
		else
		{
			minMale=male.val;
			printf("%s %s\n", male.name, male.message );
		}

		if( tag )
		{
			printf("NA\n");
		}
		else
		{
			printf("%d\n", maxFemale-minMale );
		}
        break;//不写就会超时，写了就不超时。。。。。竟然和秋招不一样。和牛客不一样。。。
	}


	return 0;
}

A 1039 Course List for Student

  • 『书中写了hash避免超时，但我是用的STL』
#include<bits/stdc++.h>
using namespace std;

int n,k;
map< string,set<int> > mp;

int main()
{
	while( ~scanf("%d%d",&n,&k) )
	{
		while( k-- )
		{
			int num,loop;
			scanf("%d%d",&num,&loop);
			char temp[6];
			while( loop-- )
			{
				scanf("%s",temp);
				string str=temp;
				mp[ str ].insert( num );
			}
			
		}

		while( n-- )
		{
			char temp[6];
			scanf("%s",temp);
			string str=temp;
			int Len=mp[str].size();
			printf("%s %d",temp, Len);
			for( auto it : mp[str] )
			{
				printf(" %d", it);
			}
			printf("\n");
		}

		mp.clear();
	}

	return 0;
}

A1041 Be Unique

  • 水题
  • 『算法笔记』上说，本题需要用scanf输入，用cin会超时
  • 此外还可以用数组来hash
#include<bits/stdc++.h>
using namespace std;

static const int maxn=1e5+5;
int solve[maxn];

int main()
{
	
	int n;
	while( ~scanf("%d",&n) )
	{
		map<int,int> mp;
		for(int i=0; i<n; ++i)
		{
			scanf("%d",&solve[i]);
			mp[ solve[i] ]++;
		}

		int demo=1;
		for(int i=0; i<n; ++i )
		{
			if( 1==mp[  solve[i] ] )
			{
				demo=0;
				printf("%d\n", solve[i]);
				break;
			}
		}

		if( demo )
		{
			printf("None\n");
		}


	}


	return 0;
}

A1042 Shuffling Machine

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm> 
using namespace std;

struct node{
	char c;
	int num;
	int x;//表示当前位置
	 
}test[54]; 

bool cmp(node a,node b) 
{
	return a.x<b.x;//按照x的值，从小到大 
}


int kk[54];

int main()
{

	int s=0;//表示，第几个数字
	 
	for(int j=1;s<13;s++,j++)
	{
		test[s].c='S';
		test[s].num=j;
		test[s].x=s;
	}
	
	for(int j=1;s<26;s++,j++)
	{
		test[s].c='H';
		test[s].num=j;
		test[s].x=s;
	}
	
	for(int j=1;s<39;s++,j++)
	{
		test[s].c='C';
		test[s].num=j;
		test[s].x=s;
	}
	
	for(int j=1;s<52;s++,j++)
	{
		test[s].c='D';
		test[s].num=j;
		test[s].x=s;
	}
	
	for(int j=1;s<54;s++,j++)
	{
		test[s].c='J';
		test[s].num=j;
		test[s].x=s;
	}
	
	
	int n;
	scanf("%d",&n);
	
	for(int i=0;i<54;i++)
	{
		scanf("%d",&kk[i]);
	}
	
	for(int i=0;i<n;i++)
	{
		
		for(int j=0;j<54;j++)
		{
			test[j].x=kk[j];
		}
		sort(test,test+54,cmp);
	}
	
	
	for(int j=0;j<53;j++)
	{
		printf("%c%d ",test[j].c,test[j].num);
	}
	printf("%c%d",test[53].c,test[53].num);
	
	return 0;
 }

A 1046 Shortest Distance

//#include<iostream>
#include<cstdio>

//using namespace std;

//int lowbit(int x)
//{
//	return x&(-x);
//}
//
//int getSum(int x,int c[])
//{
//	int sum_temp=0;
//	for(int i=x;i>0;i-=lowbit(i))
//	{
//		sum_temp+=c[i] ;
//	}
//	
//	return sum_temp;
//}





int main()
{
	int sum=0;
	int n;
	scanf("%d",&n);
	
	int test[n];//存响铃的 
	int bit[n];//he，1表示。。。
	 
	for(int i=1;i<n;i++)
	{
		scanf("%d",&test[i]);
		sum+=test[i];
		bit[i]=sum;
	}
	scanf("%d",&test[0]);
	sum+=test[0];
	
	
	
	
	
	int one;
	scanf("%d",&one);
	
	int out[one];//shuch 
	
	int a,b;
	int num=0;
	for(int i=0;i<one;i++)
	{
		scanf("%d%d",&a,&b);
		
		int temp=a;
		if(a>b)
		{
			a=b;
			b=temp;
		}
		
		if((b-a==1)&&(a==1))
		num=bit[1];
		else if((b-a==1)&&(a!=1))
		num=bit[a]-bit[a-1];
		else if((a==1)&&(b-a)>1)
		num=bit[b-1];
		else
		num=bit[b-1]-bit[a-1];
//		for(int jj=a;jj<b;jj++)
//		{
//			num+=test[jj];
//		}
		
		if(num<(sum-num))
		out[i]=num;
		else
		out[i]=sum-num;
		
		num=0;
	}
	
	
	for(int i=0;i<one-1;i++)
	{
		printf("%d\n",out[i]);
	}
		printf("%d",out[one-1]);
		
		
	
	return 0;
 }

A1047 Student List for Course

  • 坑点：//注意，可能1-k中有课程，谁都不选，样例2就是这个特例。
  • 原书上用的strcmp解答的
#include<bits/stdc++.h>
using namespace std;


int n,k;
int main()
{

	while( ~scanf("%d%d",&n,&k) )
	{
		vector< vector<string> > solve( k+1 );
		for(int i=0; i<n; ++i)
		{
			char name[6];
			int loop;
			scanf("%s %d",name,&loop);
			string temp=name;
			while( loop-- )
			{
				int tag;
				scanf("%d",&tag);
				solve[tag].push_back( temp );
			}
		}



		for( int i=1; i<=k; ++i)
		{
            //注意，可能1-k中有课程，谁都不选，样例2就是这个特例。。。
			printf("%d %d\n", i, solve[i].size() );
			sort( solve[i].begin(), solve[i].end() );
			for( auto temp : solve[i] )
			{
				printf("%s\n", temp.c_str() );
			}

		}
	}

	return 0;
}

A1048 Find Coins

  • 坑点：//要注意m=14,然后只有1个7的情况
#include<bits/stdc++.h>
using namespace std;

static const int maxn=1e5+5;
int solve[maxn];

int main()
{

	int n,m;
	while( ~scanf("%d",&n) )
	{
		scanf("%d",&m);
		map<int,int> mp;
		for(int i=0; i<n; ++i)
		{
			scanf("%d",&solve[i] );
			mp[ solve[i] ]++;//要注意m=14,然后只有1个7的情况
		}

		int tag=1;
		for( auto it : mp )
		{
            int num=it.first;
			if( mp[ m-num ]  )
			{
                if( (m-num)==num && 1==mp[num])
                {
                    break;
                }
				tag=0;
				printf("%d %d\n",it.first, m-(it.first) );
				break;
			}
		}

		if( tag )
		{
			printf("No Solution\n");
		}



	}

	return 0;
}

A1050 String Subtraction

  • 哈希水题
#include<bits/stdc++.h>
using namespace std;

int main()
{
    char first[100005];
    char second[100005];
    
 	cin.getline(first, 100005);
  	cin.getline(second, 100005);
    

    
    int lenA=strlen( first );
    int lenB=strlen( second );

    map<char,int> mp;
    for(int i=0; i<lenB; ++i)
    {
    	mp[ second[i] ]=1;
    }

    for(int i=0; i<lenA; ++i)
    {
    	if( 0==mp[ first[i] ] )
    	{
    		cout<<first[i];
    	}
    }
     
    cout<<endl;

    return 0;
}

A 1054The Dominant Color 20

  • 水题

  • 求超过一半的数字

方法一：使用C++语言特性解，不是面试最优解！当然，可以AC

  • 注意：由于是

  • map<int,int> mp;//我没有用mp.find( val_Key )
//查找mp.find( val_Key )!=mp.end();//这个写法是重点

  • //注意，C++11的这种for循环，用的是map<int,int> mp中的元素类似。不是迭代器！！！

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int a,b;
	while( ~scanf("%d%d",&a,&b) )
	{
		map<int,int> mp;
		int temp;
		int loop=a*b;
		while( loop-- )
		{
			scanf("%d",&temp);
			mp[temp]++;
		}	
		
		int num=0x3f3f3f;
		int count=0;
		
        //注意，C++11的这种for循环，用的是map<int,int> mp中的元素类似。不是迭代器！！！
		for( auto it : mp )
		{
			if( (it).second > count )
			{
				num=it.first;
				count=(it).second;
			}
		}
		
		printf("%d\n",num);
		
		
	}
	
	return 0;
}

方法2，使用『摩尔投票法』

思路：

由于题目要求必须超过『半数』（我们可以想象，假设，这些数字都隔着放，其他的元素插入到他们中间，总会有半数的那个在某个位置领近，当然11和222和3333这样的，也需要考虑）

有超过半数的数字相同，如果采用两两不相同的数相互抵消的做法，最后一定会剩下那个超过半数的数字。

比LeetCode上更好理解的『摩尔投票法求众数的步骤』

ans 『存答案（数字）』

count是计数变量，『计数ans出现的次数』

输入某元素val的时候进行

判断val和ans

  • val==ans
    • 则++count
  • val!=ans
    • （1）0==count，则ans=val，count=1 ，翻译为中文很容易理解算法：元素val出现1次
    • （2）--count，ans不变，，如果不想等，则令其抵消1次

转换为代码就是

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int a,b;
	while( ~scanf("%d%d",&a,&b) )
	{
		
		int val;
		int loop=a*b;
		
		//翻译为中文很容易理解算法：元素ans出现0次 （哨兵写法）
		int ans=0x3f3f3f;
		int count=0;
		while( loop-- )
		{
			scanf("%d",&val);
			
			if( val==ans )
			{
				++count;
			}
			else
			{
				//核心代码
				if( 0==count )
				{
					ans=val;
					count=1;
				}
				else
				{
					--count;
				}
			}
			
		}	
		
		printf("%d\n",ans);
	}
	
	return 0;
}

A1058 1058 A+B in Hogwarts

  • 水题
#include<bits/stdc++.h>
using namespace std;

int main()
{
	int firstA,firstB,firstC;
	int secondA,secondB,secondC;
	while( ~scanf("%d.%d.%d %d.%d.%d",&firstA, &firstB, &firstC
		, &secondA, &secondB, &secondC) )
	{
		int carry=0;
		int temp=(firstC+secondC)%29;
		carry = (firstC+secondC)/29 ? (firstC+secondC)/29 :0 ;
		firstC=temp;

		temp=(firstB+secondB+carry)%17;
		carry = (firstB+secondB+carry)/17 ? (firstB+secondB+carry)/17 :0 ;
		firstB=temp;


		firstA=firstA+secondA+carry;

		printf("%d.%d.%d\n",firstA,firstB,firstC);
	}


	return 0;
}

A 1063 Set Similarity

  • set中判断元素在不在，有find和count
#include<bits/stdc++.h>
using namespace std;

const int maxn=55;
set<int> solve[maxn];

int n;


void mySolve(int a, int b)
{
	//注意手法，求并集的
	int down=solve[a].size()+solve[b].size();
	int up=0;
	//注意遍历手法
	for( auto it : solve[a] )
	{
		//注意，查找结果
		//此外，查看在set中有没有出现，我使用的是find，其实还有count
		if( solve[b].end() !=solve[b].find( it ) )
		{
			++up;
			--down;
		}
		
	}

	printf("%.1f%%\n", up*100.0/down);
}

int main()
{
	while( ~scanf("%d",&n) )
	{

		for(int i=1; i<=n; ++i)
		{
			int innerLoop;
			scanf("%d",&innerLoop);
			while( innerLoop-- )
			{
				int temp;
				scanf("%d",&temp);
				solve[i].insert(temp);
			}

		}


		int M;
		scanf("%d",&M);
		while( M-- )
		{
			int a,b;
			scanf("%d%d",&a,&b);

			mySolve(a,b);
		}

	}


	return 0;
}

A1065 A+B and C (64bit)（很有用的技巧，判断64位的溢出）

技巧：判断long long相加和相减的溢出，技巧

《计算机组成原理》中指出，如何两个正数之和等于负数，或者两个负数之和等于正数，就是溢出。

我们需要考虑，两个整数相加所会导致的正溢出或者负溢出

#include<cstdio>

int out[11]={0};

int test(long long a,long long b,long long c)
{
	//1表示true 
	long long t=a+b;
	 
	if((a>0)&&(b>0)&&(t<=0))
	{
		//相加太大的溢出 
		return 1; 
	}
	else if((a<0)&&(b<0)&&(t>=0))
	{
		//两个负数相加的溢出
		return 0; 
	}
	else if(t>c)
	return 1;
	else
	return 0;
	
 } 

int main()
{
	int n;
	scanf("%d",&n);
	
	long long a,b,c;
	
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld",&a,&b,&c);
		out[i]=test(a,b,c);
	}
	
	int i=1;
	for(;i<n;i++)
	{
		if(out[i])
		printf("Case #%d: true\n",i);
		else
		printf("Case #%d: false\n",i);
	}
	
	if(out[i])
	printf("Case #%d: true",i);
	else
	printf("Case #%d: false",i);
	
	
	return 0;
 }

A1069 The Black Hole of Numbers |

见乙题解： B1019 数字黑洞

A1071 Speech Patterns

  • 多组输入和输出
string str;
while( getline(cin,str) )
  • isalnum( str[loop] )记忆
#include<bits/stdc++.h>
using namespace std;

string str;
map<string,int> mp;

void trave( int index )
{
	if( str[index]>='A' && str[index]<='Z' )
	{
		str[index]+=32;
	}

}

void solve()
{
	int Len=str.size();
	int loop=0;
	while( loop<Len )
	{
		string temp;
		while( loop<Len && isalnum( str[loop] ) )
		{
			trave( loop );
			temp+=str[loop];
			++loop;
		}

		if( 0!=temp.size() )
		{
			mp[temp]++;
		}

		while( loop<Len && 0==isalnum( str[loop] ) )
		{
			++loop;
		}
	} 

}


int main()
{

	while( getline(cin,str) )
	{
		solve();
		int have=-1;
		string temp;
		for( auto it : mp )
		{
			if( it.second>have )
			{
				temp=it.first;
				have=it.second;
			}
		}

		cout<<temp<<" "<<have<<endl;
		str.clear();
		mp.clear();
	}

	return 0;
}

A1077 Kuchiguse

  • 注意：getchar放的位置
  • PTA中C++中不能用gets的替代
  • 题目其实还是比较水，主要注意格式
#include<bits/stdc++.h>
using namespace std;

static const int maxn=256+5;
char solve[maxn][maxn];
int n;
int loop;
int len;

int main()
{
	while( ~scanf("%d",&n) )
	{
        getchar();//注意在这，不然，最后1个样例过不了

		len=maxn;
		loop=n;
		while( loop-- )
		{
			cin.getline(solve[loop], maxn);
		    //cout<<solve[loop]<<endl;
			int tempLen=strlen( solve[loop] );
			reverse( solve[loop], solve[loop]+tempLen );
			len=min(len,tempLen);
		}

		int res;
		for(res=0; res<len; ++res)
		{
			int tag=0;//表示相等
			for(int j=0; j<(n-1); ++j)
			{
				if( solve[j][res]!=solve[j+1][res])
				{
					tag=1;
					break;
				}
			}
			if( tag )
			{
				break;
			}
		}

		if( 0==res )
		{
			printf("nai\n");
		}
		else
		{
			while( res-- )
			{
				printf("%c",solve[0][res]);
			}
			printf("\n");
		}
			
		//break;
	}

	return 0;
}

A1083 List Grades (25分)

  • 水题

//『算法笔记』上说：经过测试，考生数量不会超过50 //我在写的时候，也考虑过这个。但是题目中没有讲，我只能大概以为是大学一个院系，也就几百，也能这么排序 //反正考点是sort的『规则函数』，我自己随便编的名字

#include<bits/stdc++.h>
using namespace std;

struct  node
{
	char name[30];
	char num[30];
	int val;
};

//我随便给他取个名字吧：根据它的功能，我叫他为『规则函数』，因为它就是体现排序规则的函数
bool cmp(node a, node b)
{
	return a.val>b.val;
}

int main()
{
	int n,Left,Right;
	while( ~scanf("%d",&n) )
	{
		vector<node> solve;
		while( n-- )
		{
			node temp;
			scanf("%s %s %d",temp.name, temp.num, &temp.val);
			solve.push_back( temp );
		}
		scanf("%d%d",&Left,&Right);
		sort( solve.begin(), solve.end(), cmp);

		int tag=0;
		for( auto temp: solve )
		{
			if( temp.val >=Left && temp.val<=Right )
			{
				printf("%s %s\n",temp.name, temp.num);
				tag=1;
			}
		}

		if( 0==tag )
		{
			printf("NONE\n");
		}
	}

	return 0;
}

A1085Perfect Sequence

  • 请看乙级代码

A1092 To Buy or Not to Buy

  • 请看乙级代码

A1104 Sum of Number Segments

见乙级题解：B1049 数列的片段和

  • 对题目没有很明确的思路，要记得举几个简单的例子找规律