程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces Round #306 (Div. 2) (ABCE題解)

Codeforces Round #306 (Div. 2) (ABCE題解)

編輯:C++入門知識

Codeforces Round #306 (Div. 2) (ABCE題解)


 



A. Two Substrings time limit per test 2 seconds memory limit per test 256 megabytes

You are given string s. Your task is to determine if the given string s contains two non-overlapping substrings AB and BA (the substrings can go in any order).

Input

The only line of input contains a string s of length between 1 and 105 consisting of uppercase Latin letters.

Output

Print YES (without the quotes), if string s contains two non-overlapping substrings AB and BA, and NO otherwise.

Sample test(s) Input
ABA
Output
NO
Input
BACFAB
Output
YES
Input
AXBYBXA
Output
NO
Note

In the first sample test, despite the fact that there are substrings AB and BA, their occurrences overlap, so the answer is NO.

In the second sample test there are the following occurrences of the substrings: BACFAB.

In the third sample test there is no substring AB nor substring BA.

 

題目大意:給一個字符串,問能否找到兩個不相互覆蓋的子串AB和BA

 

題目分析:暴力掃4次,第一二次先掃AB後掃BA,第三四次先掃BA後掃AB,注意這組樣例ABACCCAB

 

 

#include 
#include 
#include 
using namespace std;
int const MAX = 1e5 + 5;

char s1[MAX], s2[MAX];
int main()
{
	scanf(%s, s1);
	memcpy(s2, s1, sizeof(s1));
	int len = strlen(s1);
	bool f1 = false;
	bool f2 = false;
	for(int i = 0; i < len; i++)
	{	
		if(s1[i] == 'A' && s1[i + 1] == 'B')
		{
			f1 = true;
			s1[i] = s1[i + 1] = '*';
			break;
		}
	}
	for(int i = 0; i < len; i++)
		if(s1[i] == 'B' && s1[i + 1] == 'A')
			f2 = true;
	if(f1 && f2)
	{
		printf(YES
);
		return 0;
	}
	f1 = f2 = false;
	for(int i = 0; i < len; i++)
	{	
		if(s2[i] == 'B' && s2[i + 1] == 'A')
		{
			f1 = true;
			s2[i] = s2[i + 1] = '*';
			break;
		}
	}
	for(int i = 0; i < len; i++)
		if(s2[i] == 'A' && s2[i + 1] == 'B')
			f2 = true;
	if(f1 && f2)
	{
		printf(YES
);
		return 0;
	}
	printf(NO
);
}

 

 

 

B. Preparing Olympiad time limit per test 2 seconds memory limit per test 256 megabytes

You have n problems. You have estimated the difficulty of the i-th one as integer ci. Now you want to prepare a problemset for a contest, using some of the problems you've made.

A problemset for the contest must consist of at least two problems. You think that the total difficulty of the problems of the contest must be at least l and at most r. Also, you think that the difference between difficulties of the easiest and the hardest of the chosen problems must be at least x.

Find the number of ways to choose a problemset for the contest.

Input

The first line contains four integers n, l, r, x (1 ≤ n ≤ 15, 1 ≤ l ≤ r ≤ 109, 1 ≤ x ≤ 106) — the number of problems you have, the minimum and maximum value of total difficulty of the problemset and the minimum difference in difficulty between the hardest problem in the pack and the easiest one, respectively.

The second line contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 106) — the difficulty of each problem.

Output

Print the number of ways to choose a suitable problemset for the contest.

Sample test(s) Input
3 5 6 1
1 2 3
Output
2
Input
4 40 50 10
10 20 30 25
Output
2
Input
5 25 35 10
10 10 20 10 20
Output
6
Note

In the first example two sets are suitable, one consisting of the second and third problem, another one consisting of all three problems.

In the second example, two sets of problems are suitable — the set of problems with difficulties 10 and 30 as well as the set of problems with difficulties 20 and 30.

In the third example any set consisting of one problem of difficulty 10 and one problem of difficulty 20 is suitable.

 

題目大意:有n個問題每個難度為ci,要選一些題出來,要求這些題的總難度不超過r且不小於l,且難度最大的和難度最小的差不能小於x,問有多少種選法

 

題目分析:n等於15,隨便搞,我是直接深搜,簡潔明了

 

 

#include 
#include 
#include 
using namespace std;
int const INF = 0x3fffffff;
int n, l, r, x;
int c[20];
int ans;

void DFS(int idx, int ma, int mi, int sum) //第幾個題,當前最大,當前最小,難度總和
{
	if(idx == n + 1)
		return;
	if(sum <= r && sum >= l && x <= ma - mi && idx == n)
		ans ++;
	DFS(idx + 1, max(ma, c[idx]), min(mi, c[idx]), sum + c[idx]); //選第idx個
	DFS(idx + 1, ma, mi, sum); //不選第idx個
	return;
}

int main()
{
	scanf(%d %d %d %d, &n, &l, &r, &x);
	for(int i = 0; i < n; i++)
		scanf(%d, &c[i]);
	ans = 0;
	DFS(0, 0, INF, 0);
	printf(%d
, ans);
}

 

 



C. Divisibility by Eight time limit per test 2 seconds memory limit per test 256 megabytes

You are given a non-negative integer n, its decimal representation consists of at most 100 digits and doesn't contain leading zeroes.

Your task is to determine if it is possible in this case to remove some of the digits (possibly not remove any digit at all) so that the result contains at least one digit, forms a non-negative integer, doesn't have leading zeroes and is divisible by 8. After the removing, it is forbidden to rearrange the digits.

If a solution exists, you should print it.

Input

The single line of the input contains a non-negative integer n. The representation of number n doesn't contain any leading zeroes and its length doesn't exceed 100 digits.

Output

Print NO (without quotes), if there is no such way to remove some digits from number n.

Otherwise, print YES in the first line and the resulting number after removing digits from number n in the second line. The printed number must be divisible by 8.

If there are multiple possible answers, you may print any of them.

Sample test(s) Input
3454
Output
YES
344
Input
10
Output
YES
0
Input
111111
Output
NO

 

題目大意:給個數字,問刪去其中一些數字後能不能被8整除

 

題目分析:打了個小表,找了找規律,首先有8或0的直接可以,其次包含16,24,32,56,64,72,96之一的都可以,再其次,先找一個奇數,它後面為12,36,44,52,76,92之一的都可以,數字長度很小,暴搞

 

 

#include 
#include 
int const MAX = 105;
char s[MAX];
int len;
// 0
// 8
// 16
// 24
// 32
// 56
// 64
// 72
// 96
// 112
// 136
// 144
// 152
// 176
// 192
// 312
// 336
bool judge1(int i, char ch1, char ch2)
{
	if(s[i] == ch1)
	{
		for(int j = i + 1; j < len; j++)
		{
			if(s[j] == ch2)
			{	
				printf(YES
%c%c
, ch1, ch2);
				return true;
			}
		}
	}
	return false;
}

bool judge2(char ch, int i, char ch1, char ch2)
{
	for(int j = i + 1; j < len; j++)
	{
		if(s[j] == ch1)
		{
			for(int k = j + 1; k < len; k ++)
			{
				if(s[k] == ch2)
				{	
					printf(YES
%c%c%c
, ch, ch1, ch2);
					return true;
				}
			}
		}
	}
	return false;
}

int main()
{
	scanf(%s, s);
	len = strlen(s);
	for(int i = 0; i < len; i++)
	{
		if(s[i] == '0')
		{
			printf(YES
0
);
			return 0;
		}
		if(s[i] == '8')
		{
			printf(YES
8
);
			return 0;
		}
		if(judge1(i, '1', '6'))
			return 0;
		if(judge1(i, '2', '4'))
			return 0;
		if(judge1(i, '3', '2'))
			return 0;
		if(judge1(i, '5', '6'))
			return 0;
		if(judge1(i, '6', '4'))
			return 0;
		if(judge1(i, '7', '2'))
			return 0;
		if(judge1(i, '9', '6'))
			return 0;
		if((s[i] - '0') % 2 == 1 && judge2(s[i], i, '1', '2'))
			return 0;
		if((s[i] - '0') % 2 == 1 && judge2(s[i], i, '3', '6'))
			return 0;
		if((s[i] - '0') % 2 == 1 && judge2(s[i], i, '4', '4'))
			return 0;
		if((s[i] - '0') % 2 == 1 && judge2(s[i], i, '5', '2'))
			return 0;
		if((s[i] - '0') % 2 == 1 && judge2(s[i], i, '7', '6'))
			return 0;
		if((s[i] - '0') % 2 == 1 && judge2(s[i], i, '9', '2'))
			return 0;
	}
	printf(NO
);
}

 

 

 

E. Brackets in Implications time limit per test:2 seconds memory limit per test:256 megabytes

Implication is a function of two logical arguments, its value is false if and only if the value of the first argument is true and the value of the second argument is false.

Implication is written by using character '\', and the arguments and the result of the implication are written as '0' (false) and '1' (true). According to the definition of the implication:

\

\

\

\

When a logical expression contains multiple implications, then when there are no brackets, it will be calculated from left to fight. For example,

\.

When there are brackets, we first calculate the expression in brackets. For example,

\.

For the given logical expression \ determine if it is possible to place there brackets so that the value of a logical expression is false. If it is possible, your task is to find such an arrangement of brackets.

Input

The first line contains integer n (1 ≤ n ≤ 100 000) — the number of arguments in a logical expression.

The second line contains n numbers a1, a2, ..., an (\), which means the values of arguments in the expression in the order they occur.

Output

Print NO (without the quotes), if it is impossible to place brackets in the expression so that its value was equal to 0.

Otherwise, print YES in the first line and the logical expression with the required arrangement of brackets in the second line.

The expression should only contain characters '0', '1', '-' (character with ASCII code 45), '>' (character with ASCII code 62), '(' and ')'. Characters '-' and '>' can occur in an expression only paired like that: (->) and represent implication. The total number of logical arguments (i.e. digits '0' and '1') in the expression must be equal to n. The order in which the digits follow in the expression from left to right must coincide with a1, a2, ..., an.

The expression should be correct. More formally, a correct expression is determined as follows:

Expressions 0, 1 (without the quotes) are correct. If v1, v2 are correct, then v1->v2 is a correct expression. If v is a correct expression, then (v) is a correct expression.

The total number of characters in the resulting expression mustn't exceed 106.

If there are multiple possible answers, you are allowed to print any of them.

Sample test(s) Input
4
0 1 1 0
Output
YES
(((0)->1)->(1->0))
Input
2
1 1
Output
NO
Input
1
0
Output
YES
0

 

題目大意:給四個轉移式子,然後給一個0/1串問是否存在某總計算方式使得最後答案為0,存在則輸出任意一種合法的方式

 

 

題目分析:從給的四個式子中可以發現如果結果要為0,最後一位必須是0,現在要做的就是再最後一個0之前構造1,我們可以發現如果最後一個0的前面一個是1,那麼不管這個1之前是什麼最後答案都是1,因為0 ->1=1,1 ->1=1,即與前面的值無關,所以我們轉過來考慮不可能的情況,考慮最後一個0的前面是0,因為要構1,又0->0=0,1->0=0也就是說這個0前面不能是1,依次類推可以得到,如果倒數第二個0的前面都是1,那必然無解,否則就有解

 

 

#include 
#include 
int const MAX = 1e6 + 5;
int n, a[MAX];

int main()
{
    scanf(%d, &n);
    for(int i = 1; i <= n; i++)
        scanf(%d, &a[i]);
    if(n == 1)	//特判一個數
    {
        if(a[1] == 1)
            printf(NO
);
        else
            printf(YES
0
);
        return 0;
    }
    if(a[n] == 1)
    {
    	printf(NO
);
        return 0;
    }
    bool flag = false;
    for(int i = 1; i <= n - 2; i++)
    {
        if(a[i] != 1)
        {
        	flag = true;
            break;
        }
    }
    if(!flag && a[n - 1] == 0 && a[n] == 0) //1111111 1 0Y  0 0N
    {
    	printf(NO
);
        return 0;
    }
    printf(YES
);
    for(int i = 1; i <= n - 2; i++)
        printf((%d->, a[i]);
    printf(%d, a[n - 1]);
    for(int i = 1; i <= n - 2; i++)
    	printf());
    printf(->0
);
}

 

 

D也是個構造,沒來及補

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved