CODE FESTIVAL 2017 qual B

昨晚因为有点事就去忙了，没打后悔啊

A - XXFESTIVAL

---

Time limit : 2sec / Memory limit : 256MB

Score :  points

Problem Statement

Rng is going to a festival.

The name of the festival is given to you as a string , which ends with FESTIVAL, from input. Answer the question: "Rng is going to a festival of what?" Output the answer.

Here, assume that the name of "a festival of " is a string obtained by appending FESTIVAL to the end of . For example, CODEFESTIVAL is a festival of CODE.

Constraints

•  consists of uppercase English letters.
•  ends with FESTIVAL.

---

Input

Input is given from Standard Input in the following format:

Output

Print the answer to the question: "Rng is going to a festival of what?"

---

Sample Input 1

Copy

CODEFESTIVAL

Sample Output 1

Copy

CODE

This is the same as the example in the statement.

---

Sample Input 2

Copy

CODEFESTIVALFESTIVAL

Sample Output 2

Copy

CODEFESTIVAL

This string is obtained by appending FESTIVAL to the end of CODEFESTIVAL, so it is a festival of CODEFESTIVAL.

---

Sample Input 3

Copy

YAKINIKUFESTIVAL

Sample Output 3

Copy

YAKINIKU

---

#include<bits/stdc++.h>

using namespace std;

int main()

{

  string s;

  cin>>s;

  int l=s.length()-;

  for(int i=; i<l; ++i)

    putchar(s[i]);

  return ;

}

B - Problem Set

---

Time limit : 2sec / Memory limit : 256MB

Score :  points

Problem Statement

Rng is preparing a problem set for a qualification round of CODEFESTIVAL.

He has  candidates of problems. The difficulty of the -th candidate is .

There must be  problems in the problem set, and the difficulty of the -th problem must be . Here, one candidate of a problem cannot be used as multiple problems.

Determine whether Rng can complete the problem set without creating new candidates of problems.

Constraints

• All numbers in the input are integers.

Partial Score

•  points will be awarded for passing the test set satisfying  and .

---

Input

Input is given from Standard Input in the following format:

Output

Print YES if Rng can complete the problem set without creating new candidates of problems; print NO if he cannot.

---

Sample Input 1

Copy

5

3 1 4 1 5

3

5 4 3

Sample Output 1

Copy

YES

---

Sample Input 2

Copy

7

100 200 500 700 1200 1600 2000

6

100 200 500 700 1600 1600

Sample Output 2

Copy

NO

Not enough s.

---

Sample Input 3

Copy

1

800

5

100 100 100 100 100

Sample Output 3

Copy

NO

---

Sample Input 4

Copy

15

1 2 2 3 3 3 4 4 4 4 5 5 5 5 5

9

5 4 3 2 1 2 3 4 5

Sample Output 4

Copy

YES

---

用map看一下数据是否合法就行了

#include<bits/stdc++.h>

using namespace std;

map<int,int>M;

int main()

{

    int n,m;

    cin>>n;

    for(int i=; i<n; i++)

    {

        int x;

        cin>>x,M[x]++;

    }

    cin>>m;

    int f=;

    for(int i=; i<m; i++)

    {

        int x;

        cin>>x;

        if(!M[x])

        {

            f=;

            break;

        }

        else M[x]--;

    }

    cout<<(f?"NO\n":"YES\n");

    return ;

}

C - 3 Steps

---

Time limit : 2sec / Memory limit : 256MB

Score :  points

Problem Statement

Rng has a connected undirected graph with  vertices. Currently, there are  edges in the graph, and the -th edge connects Vertices  and .

Rng will add new edges to the graph by repeating the following operation:

• Operation: Choose  and   such that Vertex  can be reached by traversing exactly three edges from Vertex , and add an edge connecting Vertices and . It is not allowed to add an edge if there is already an edge connecting Vertices  and .

Find the maximum possible number of edges that can be added.

Constraints

• The graph has no self-loops or multiple edges.
• The graph is connected.

---

Input

Input is given from Standard Input in the following format:

Output

Find the maximum possible number of edges that can be added.

---

Sample Input 1

Copy

6 5

1 2

2 3

3 4

4 5

5 6

Sample Output 1

Copy

4

If we add edges as shown below, four edges can be added, and no more.

---

Sample Input 2

Copy

5 5

1 2

2 3

3 1

5 4

5 1

Sample Output 2

Copy

5

Five edges can be added, for example, as follows:

• Add an edge connecting Vertex  and Vertex .
• Add an edge connecting Vertex  and Vertex .
• Add an edge connecting Vertex  and Vertex .
• Add an edge connecting Vertex  and Vertex .
• Add an edge connecting Vertex  and Vertex .

---

搞成二分图然后dfs啊

然后再利用六哥的两边的个数想乘就好了

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+;

bool f=;

int c[N],cnt[];

vector<int>G[N];

void dfs(int x,int ff=)

{

    if(c[x])

    {

        f|=ff!=c[x];

        return;

    }

    c[x]=ff;

    cnt[ff]++;

    for(int u:G[x])

    dfs(u,-ff);

}

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i=; i<m; ++i)

    {

        int u,v;

        scanf("%d%d",&u,&v);

        G[u].push_back(v);

        G[v].push_back(u);

    }

    dfs();

    printf("%lld\n",f?1LL*n*(n-)/-m:1LL*cnt[]*cnt[]-m);

    return ;

}