程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces Round #306 (Div. 2)

Codeforces Round #306 (Div. 2)

編輯：C++入門知識

Codeforces Round #306 (Div. 2)

最近是怎麼了，老是掉分，sad = =.......

明明都會做，但一到比賽時，就沒有想法了。。。估計是太困了吧。。。

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

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"就可以了，還是要分別都要兩個，事後想想，這個愚蠢的問題。。。然後回過頭看，wa~，完了，又要掉分了。。。

想法呢：

就是for4遍，首先第一遍是為了先找出AB有沒有，然後for第二遍找出BA，記得把AB所在的位置要標記上；

然後如果上面找到兩種字符串的話，那麼就不用進行下面的語句了，但是沒有找到，那麼就要for先找出BA,然後就再去找AB，大致與上面找的方法相同。

#include
#include
#include
#include
#include
using namespace std;
#define maxn 111111
map mp;
char a[maxn];
int mp1[maxn],mp2[maxn];
int main(){
    scanf("%s",a);
    int len=strlen(a);
    int i,j,k,l;
    bool f1,f2;
    f1=f2=false;
    for(i=0;i 

B. Preparing Olympiad


time limit per test
2 seconds


memory limit per test
256 megabytes


input
standard input


output
standard output
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)



input3 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.


 
這道題我一開始沒有想出來，後來看別人的想法做的，就是一個dfs。
題意就是給你限定了一個范圍區間[l,r]； 然後你可以選n門課中的任意門然後要使它們的難度系數之和在這個區間范圍內，然後在你所選的課中找出最大值max，最小值min，然後它們兩個的差值要大於等於x才行，然後問你總共有幾種選課的方法。
 
#include
#include
#include
#include
using namespace std;
#define maxn  22
#define inf 99999999
int a[maxn],l,r,x,n;
int num=0;
void dfs(int cur,int sum,int ma,int mi,int cnt){
    if(sum>r) return;
    if(maa[cur]) mi=a[cur];
    if(sum>=l&&sum<=r&&(ma-mi>=x)&&cnt>=2){
        num++;
        //return    注意了，這裡並不用加return，因為我們這裡並不需要返回，因為我們要做的就是讓它不撞南牆不回頭的去搜索！！！ 
    }
    for(int i=cur+1;i 
 

C. Divisibility by Eight


time limit per test
2 seconds


memory limit per test
256 megabytes


input
standard input


output
standard output
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)



input3454

output
YES
344

input
10

output
YES
0

input
111111

output
NO


這道題我是找規律的，首先我發現後兩位數是有重復的，比如說從0~100與200~300的後兩位是重復的，從100~200與300~400的後兩位是重復的，所以我們可以對後兩位進行判斷。
代碼有點挫，先貼上來，明天再整理下。
 
#include
#include
#include
#include
using namespace std;
#define maxn 111
char a[maxn];
int mp[33];
int main(){
    scanf("%s",a);
    int len=strlen(a);
    for(int i=0;i=2&&flag) {puts("YES"); printf("112\n");return 0;}
                for(int i=0;i=2&&flag) {puts("YES"); printf("%d44\n",tx);return 0;}
                flag=false;
                for(int i=0;i

感覺就像是一個暴暴力~~~ 
還有每次必說的——加油！