CODE FESTIVAL 2017 qual B
昨晚因為有點事就去忙了,沒打后悔啊
A - XXFESTIVAL
Time limit?: 2sec /?Memory limit?: 256MB
Score :?100?points
Problem Statement
Rng is going to a festival.
The name of the festival is given to you as a string?S, 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?s" is a string obtained by appending?FESTIVAL?to the end of?s. For example,?CODEFESTIVAL?is a festival of?CODE.
Constraints
- 9≤|S|≤50
- S?consists of uppercase English letters.
- S?ends with?FESTIVAL.
Input
Input is given from Standard Input in the following format:
SOutput
Print the answer to the question: "Rng is going to a festival of what?"
Sample Input 1
Copy CODEFESTIVALSample Output 1
Copy CODEThis is the same as the example in the statement.
Sample Input 2
Copy CODEFESTIVALFESTIVALSample Output 2
Copy CODEFESTIVALThis string is obtained by appending?FESTIVAL?to the end of?CODEFESTIVAL, so it is a festival of?CODEFESTIVAL.
Sample Input 3
Copy YAKINIKUFESTIVALSample Output 3
Copy YAKINIKU?
#include<bits/stdc++.h> using namespace std; int main() {string s;cin>>s;int l=s.length()-8;for(int i=0; i<l; ++i)putchar(s[i]);return 0; }?
B - Problem Set
Time limit?: 2sec /?Memory limit?: 256MB
Score :?200?points
Problem Statement
Rng is preparing a problem set for a qualification round of CODEFESTIVAL.
He has?N?candidates of problems. The difficulty of the?i-th candidate is?Di.
There must be?M?problems in the problem set, and the difficulty of the?i-th problem must be?Ti. 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
- 1≤N≤200,000
- 1≤Di≤109
- 1≤M≤200,000
- 1≤Ti≤109
- All numbers in the input are integers.
Partial Score
- 100?points will be awarded for passing the test set satisfying?N≤100?and?M≤100.
Input
Input is given from Standard Input in the following format:
N D1 D2 … DN M T1 T2 … TMOutput
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 3Sample Output 1
Copy YESSample Input 2
Copy 7 100 200 500 700 1200 1600 2000 6 100 200 500 700 1600 1600Sample Output 2
Copy NONot enough?1600s.
Sample Input 3
Copy 1 800 5 100 100 100 100 100Sample Output 3
Copy NOSample 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 5Sample 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=0; i<n; i++){int x;cin>>x,M[x]++;}cin>>m;int f=0;for(int i=0; i<m; i++){int x;cin>>x;if(!M[x]){f=1;break;}else M[x]--;}cout<<(f?"NO\n":"YES\n");return 0; }?
C - 3 Steps
Time limit?: 2sec /?Memory limit?: 256MB
Score :?500?points
Problem Statement
Rng has a connected undirected graph with?N?vertices. Currently, there are?M?edges in the graph, and the?i-th edge connects Vertices?Ai?and?Bi.
Rng will add new edges to the graph by repeating the following operation:
- Operation: Choose?u?and?v?(u≠v)?such that Vertex?v?can be reached by traversing exactly three edges from Vertex?u, and add an edge connecting Vertices?uand?v. It is not allowed to add an edge if there is already an edge connecting Vertices?u?and?v.
Find the maximum possible number of edges that can be added.
Constraints
- 2≤N≤105
- 1≤M≤105
- 1≤Ai,Bi≤N
- The graph has no self-loops or multiple edges.
- The graph is connected.
Input
Input is given from Standard Input in the following format:
N M A1 B1 A2 B2 : AM BMOutput
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 6Sample Output 1
Copy 4If 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 1Sample Output 2
Copy 5Five edges can be added, for example, as follows:
- Add an edge connecting Vertex?5?and Vertex?3.
- Add an edge connecting Vertex?5?and Vertex?2.
- Add an edge connecting Vertex?4?and Vertex?1.
- Add an edge connecting Vertex?4?and Vertex?2.
- Add an edge connecting Vertex?4?and Vertex?3.
搞成二分圖然后dfs啊
然后再利用六哥的兩邊的個數想乘就好了
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; bool f=0; int c[N],cnt[3]; vector<int>G[N]; void dfs(int x,int ff=1) {if(c[x]){f|=ff!=c[x];return;}c[x]=ff;cnt[ff]++;for(int u:G[x])dfs(u,3-ff); } int main() {int n,m;scanf("%d%d",&n,&m);for(int i=0; i<m; ++i){int u,v;scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);}dfs(1);printf("%lld\n",f?1LL*n*(n-1)/2-m:1LL*cnt[1]*cnt[2]-m);return 0; }?
轉載于:https://www.cnblogs.com/BobHuang/p/7639623.html
總結
以上是生活随笔為你收集整理的CODE FESTIVAL 2017 qual B的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: JS高级 - 面向对象5(继承,引用)
- 下一篇: 同步控制 之“重入锁”