2010年东北大学ACM程序设计竞赛冬季校赛题解

8题只做出4题比较easy的题，而且做得挺麻烦，看来还要多练练。

AC的题如下

NEUOJ 1112I Love Apple

Description

So many people love apple and there is a problem about apple.

An Apple Word is a word that consists of only the letters A, P, L, and E, in that exact relative order. There must be exactly one A, two or more Ps, exactly one L and exactly one E. Case does not matter.

For example, "Apple" and "apPpPPlE" are Apple Words, while "APLE", "Apples", "Aplpe" and "coconut" are not. You are given a string word which you must turn into an Apple Word. For each character in word, you can either replace it with a different letter or leave it unchanged. No other operations, like inserting new characters or deleting existing characters, are allowed.

Please find the minimal number of characters you must replace to get an Apple Word. If it's impossible, output -1.

Input

There're multiple test cases.
Each case is a string contain between 1 and 50 characters, inclusive.
Each character in input string will be an uppercase letter ('A'-'Z') or a lowercase letter ('a'-'z').

Output

For each case, output the minimal number of characters you must replace to get an Apple Word, If it's impossible, output -1

Sample Input

apPpPPlE
APLE
NEUAcmer

Sample Output

0
-1
8

Hint

Source

2010年东北大学ACM程序设计竞赛冬季校赛

#include <iostream>
#include <cstring>
using namespace std;
//判断是否是appleword
bool isappleword(char * s){
	bool flag = false;
	if((s[0] == 'a' || s[0] == 'A') && (s[1] == 'p' || s[1] == 'P') && (s[2] == 'p' || s[2] == 'P'))
	{
		int len = strlen(s);
		if ((s[len-1] == 'e' || s[len-1] == 'E') && (s[len-2] == 'l' || s[len-2] == 'L')){
			flag = true;
			for (int i = 2;i<=len-3;i++)
			{
				if (s[i] != 'P' && s[i] != 'p')
				{
					flag = false;
				}
			}
		}
	}
	if (flag)
	{
		return true;
	}
	return false;
}
int main(){
	char s[60];
	bool flag;
	int len;
	int changenum;
	int i;
	while (scanf("%s",s) != EOF)
	{
		flag = isappleword(s);
		len = strlen(s);
		if (flag)
		{
			cout<<0<<endl;
			flag = false;
			continue;
		}
	else if(len < 5){
			cout<<-1<<endl;
			continue;
		}
	
	else{
			changenum = 0;
			if (s[0] != 'a' && s[0] != 'A')
			{
				s[0] = 'a';
				changenum++;
			}
			if (s[1] != 'p' && s[1] != 'P')
			{
				s[1] = 'p';
				changenum++;
			}
			if (s[2] != 'p' && s[2] != 'P')
			{
				s[2] = 'p';
				changenum++;
			}
			if (s[len-1] != 'e' && s[len-1] != 'E')
			{
				s[len-1] = 'e';
				changenum++;
			}
			if (s[len-2] != 'l' && s[len - 2] != 'L')
			{
				s[len-2] = 'l';
				changenum++;
			}
			for (i = 3;i < len-2 ;i++)
			{
				if (s[i] != 'p' && s[i] != 'P')
				{
					s[i] = 'p';
					changenum++;
				}
			}
			cout<<changenum<<endl;
			changenum = 0;
		}
			
	}
	return 0;	
}

Problem 1114 - A Easy Problem

Description

Risk is a board game played on a world map. This world is divided into regions by borders.
Each region is controlled by a player (either you or one of your opponents). Any region that
you control contains a positive number of your armies.
In each turn, you are allowed to move your armies. Each of your armies may either stay
where it is, or move from a region to a bordering region under your control. The movements
are performed one by one, in an order of your choice. At all times, each region must contain
at least one army.
For strategic purposes, it is important to move your armies to regions that border your
opponents’ regions and minimize the number of armies on your regions that are totally surrounded
by other regions under your control. You want your weakest link, i.e., the border
region with the minimum number of armies, to be as strong as possible. What is the maximum
number of armies that can be placed on it after one turn?

Input

On the first line a positive integer: the number of test cases, at most 100. After that per test
case:
One line with an integer n (1 <= n <= 100): the number of regions.
One line with n integers ai (0 <= ai <= 100): the number of your armies on each region.
A number 0 indicates that a region is controlled by your opponents, while a positive
number indicates that it is under your control.
n lines with n characters, where each character is either ‘Y’ or ‘N’. The i-th character
of the j-th line is ‘Y’ if regions i and j border, and ‘N’ otherwise. This relationship is
symmetric and the i-th character of the i-th line will always be ‘N’.
In every test case, you control at least one region, and your opponents control at least
one region. Furthermore, at least one of your regions borders at least one of your opponents’
regions.

Output

Per test case:
One line with an integer: the maximum number of armies on your weakest border
region after one turn of moving.

Sample Input

2
3
1 1 0
NYN
YNY
NYN
7
7 3 3 2 0 0 5
NYNNNNN
YNYYNNN
NYNYYNN
NYYNYNN
NNYYNNN
NNNNNNY
NNNNNYN

Sample Output

1
4

Hint

Source

2010年东北大学ACM程序设计竞赛冬季校赛

#include <iostream>
using namespace std;
int sqnum[105];
int score[10005] = {0};
int dafen(int num){
	int i,j;
	int s=0;
	for (i = 0;i < 101;i++)
		for (j = i;j < 101;j++)
	{
			if (sqnum[i] + sqnum[j] == num)
			s++;
	}
	return s;
}
int main(){
	//先打表，0-10000的平方数
	int i,j=0;
	int n , l,r;
	 
	for (i =0 ; i*i <=10000;i++)
	{
		sqnum[j++] = i*i;
	}
	
	cin >> n;
	while (n--)
	{
		cin>>l>>r;
		//对l-r之间的每个数都进行打分存于数组中
		for (i = l;i<=r;i++)
		{
			score[i] = dafen(i);
		}
		//在score中找最大的分数
		int temp = score[0];
		for(i = l;i<=r;i++){
			if (score[i] > temp)
			{
				temp = score[i];
			}
		}
		for (i=r;i>=l;i--)
		{
			if (score[i] == temp)
			{
				cout<< i<<endl;
				break;
			}
		}
	}
	return 0;
}

Problem 1116 - Double Xor

Description

once upon a time, there is a very strange computer. Its memory consists of several bits, each initially set to 0, and it can only perform the following type of operation:

Choose one of the bits in memory, and choose a value - 0 or 1. All the bits between the selected bit and the last bit in memory, inclusive, will be set to the chosen value.

For example, if the memory is "0010", and you choose the second bit and a value of 1, the memory will change to "0111". You are given a string mem.

The number of characters in mem is equal to the number of bits in the computer's memory. Compute the minimum number of operations required to set the computer's memory equal to mem.

Input

There're multiple test cases.
Each case contain a string which is mem. It will contain only the characters '0' (zero) or '1' (one) and between 1 and 50 characters, inclusive.

Output

For each test cases only a integer indicate the minimum times of operations required to set the computer's memory equal to mem.

Sample Input

0100
111000111

Sample Output

2
3

Hint

Source

2010年东北大学ACM程序设计竞赛冬季校赛

#include <iostream>
#include <cstring>
using namespace std;
bool strcmpyang(char *targets1,char *mems2){
	int len = strlen(targets1);
	bool equalflag = true;
	for (int i = 0;i < len;i++)
	{
		if (targets1[i] != mems2[i])
		{
			equalflag = false;
		}
	}
	return equalflag;
}
int main(){
	char targetmem[50];
	char mem[50];
	int i,j,times,len,pre;
	while (scanf("%s",targetmem) != EOF)
	{
		len = strlen(targetmem);
		memset(mem,'0',len);
		times = 0;
		pre = 0;
		while (!strcmpyang(targetmem,mem))
		{
			times++;
			if (times%2 == 1)
			{
				for (i = pre;i < len; i++)
				{
					if (targetmem[i] == '1'){
						pre = i;
						break;
					}
				}
				for (j = i;j<len;j++)
				{
					mem[j] = '1';
				}
			}
			if (times%2 == 0)
			{
				for (i = pre;i < len; i++)
				{
					if (targetmem[i] == '0'){
						pre = i;
						break;
					}
				}
				for (j = i;j<len;j++)
				{
					mem[j] = '0';
				}
			}
		}
		cout<<times<<endl;
	}
	return 0;
}

Problem 1117 - Strange Computer

Description

once upon a time, there is a very strange computer. Its memory consists of several bits, each initially set to 0, and it can only perform the following type of operation:

Choose one of the bits in memory, and choose a value - 0 or 1. All the bits between the selected bit and the last bit in memory, inclusive, will be set to the chosen value.

For example, if the memory is "0010", and you choose the second bit and a value of 1, the memory will change to "0111". You are given a string mem.

The number of characters in mem is equal to the number of bits in the computer's mem ory. Compute the minimum number of operations required to set the computer's memory equal to mem.

Input

There're multiple test cases.
Each case contain a string which is mem. It will contain only the characters '0' (zero) or '1' (one) and between 1 and 50 characters, inclusive.

Output

For each test cases only a integer indicate the minimum times of operations required to set the computer's memory equal to mem.

Sample Input

0100
111000111

Sample Output

2
3

Hint

Source

2010年东北大学ACM程序设计竞赛冬季校赛

#include <iostream>
#include <cstring>
using namespace std;
bool strcmpyang(char *targets1,char *mems2){
	int len = strlen(targets1);
	bool equalflag = true;
	for (int i = 0;i < len;i++)
	{
		if (targets1[i] != mems2[i])
		{
			equalflag = false;
		}
	}
	return equalflag;
}
int main(){
	char targetmem[50];
	char mem[50];
	int i,j,times,len,pre;
	while (scanf("%s",targetmem) != EOF)
	{
		len = strlen(targetmem);
		memset(mem,'0',len);
		times = 0;
		pre = 0;
		while (!strcmpyang(targetmem,mem))
		{
			times++;
			if (times%2 == 1)
			{
				for (i = pre;i < len; i++)
				{
					if (targetmem[i] == '1'){
						pre = i;
						break;
					}
				}
				for (j = i;j<len;j++)
				{
					mem[j] = '1';
				}
			}
			if (times%2 == 0)
			{
				for (i = pre;i < len; i++)
				{
					if (targetmem[i] == '0'){
						pre = i;
						break;
					}
				}
				for (j = i;j<len;j++)
				{
					mem[j] = '0';
				}
			}
		}
		cout<<times<<endl;
	}
	return 0;
}