A - Is It A Tree? Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%lld & %llu Submit
Status
Practice
POJ 1308 Description A tree is a well-known data structure that is either empty (null, void, nothing) or is a set of one or more nodes connected by directed edges between nodes satisfying the following properties.
There is exactly one node, called the root, to which no directed edges point. Every node except the root has exactly one edge pointing to it. There is a unique sequence of directed edges from the root to each node. For example, consider the illustrations below, in which nodes are represented by circles and edges are represented by lines with arrowheads. The first two of these are trees, but the last is not.
In this problem you will be given several descriptions of collections of nodes connected by directed edges. For each of these you are to determine if the collection satisfies the definition of a tree or not. Input The input will consist of a sequence of descriptions (test cases) followed by a pair of negative integers. Each test case will consist of a sequence of edge descriptions followed by a pair of zeroes Each edge description will consist of a pair of integers; the first integer identifies the node from which the edge begins, and the second integer identifies the node to which the edge is directed. Node numbers will always be greater than zero. Output For each test case display the line “Case k is a tree.” or the line “Case k is not a tree.”, where k corresponds to the test case number (they are sequentially numbered starting with 1). Sample Input 6 8 5 3 5 2 6 4 5 6 0 0
8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0
3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1 Sample Output Case 1 is a tree. Case 2 is a tree. Case 3 is not a tree.
跟前天的题目代码差不多 改一下输出的东西就过了
#include<stdio.h> #include<string> #include<cstring> #include<queue> #include<algorithm> #include<functional> #include<vector> #include<iomanip> #include<math.h> #include<iostream> #include<sstream> #include<set> using namespace std; const int M = 100005; int a,b; int father[M]; bool circle; bool visit[M]; int edgenum,vnum; void initial( ) { for( int i=0 ; i<M ; i++ ) father[i] = i,visit[i]=false; circle = false; edgenum = vnum = 0; } int find( int x ) { return x == father[x] ? x : father[x] = find(father[x]); } void merge( int a,int b ) { if( a == b ) circle = true; int x, y; x = find(a); y = find(b); if( x != y ) { father[x] = y; edgenum++; } else circle = true; } int main() { int cases=1; while( true ) { initial( ); scanf("%d%d",&a,&b); if( a==0 && b==0 ) { printf("Case %d is a tree.\n",cases); cases++; continue; } if( a==-1 && b==-1 ) break; visit[a] = true; visit[b] = true; merge( a,b ); while( true ) { scanf("%d%d",&a,&b); if( a==0 && b==0 ) break; visit[a] = true; visit[b] = true; merge( a, b ); } for( int i=0 ; i<M ; i++ ) if( visit[i] ) vnum++; if( !circle && edgenum+1 == vnum ) printf("Case %d is a tree.\n",cases); else printf("Case %d is not a tree.\n",cases); cases++; } return 0; }B题和C题都是最近一次cf上的题目 前天晚上(或者说昨天凌晨)熬夜打了一下那场比赛 虽然当时没做出来C 不过昨天就看了题解 留了代码 今天直接交了~
B - Interesting drink Time Limit:2000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u Submit
Status
Practice
CodeForces 706B Description Vasiliy likes to rest after a hard work, so you may often meet him in some bar nearby. As all programmers do, he loves the famous drink “Beecola”, which can be bought in n different shops in the city. It’s known that the price of one bottle in the shop i is equal to xi coins.
Vasiliy plans to buy his favorite drink for q consecutive days. He knows, that on the i-th day he will be able to spent mi coins. Now, for each of the days he want to know in how many different shops he can buy a bottle of “Beecola”.
Input The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of shops in the city that sell Vasiliy’s favourite drink.
The second line contains n integers xi (1 ≤ xi ≤ 100 000) — prices of the bottles of the drink in the i-th shop.
The third line contains a single integer q (1 ≤ q ≤ 100 000) — the number of days Vasiliy plans to buy the drink.
Then follow q lines each containing one integer mi (1 ≤ mi ≤ 109) — the number of coins Vasiliy can spent on the i-th day.
Output Print q integers. The i-th of them should be equal to the number of shops where Vasiliy will be able to buy a bottle of the drink on the i-th day.
Sample Input Input 5 3 10 8 6 11 4 1 10 3 11 Output 0 4 1 5 Hint On the first day, Vasiliy won’t be able to buy a drink in any of the shops.
On the second day, Vasiliy can buy a drink in the shops 1, 2, 3 and 4.
On the third day, Vasiliy can buy a drink only in the shop number 1.
Finally, on the last day Vasiliy can buy a drink in any shop.
#include<stdio.h> #include<string> #include<cstring> #include<queue> #include<algorithm> #include<functional> #include<vector> #include<iomanip> #include<math.h> #include<iostream> #include<sstream> #include<set> #include<map> using namespace std; const int MAX=100005; int F[MAX]= {0}; int main() { cin.sync_with_stdio(false); int n,x,high=0,low=999999; cin>>n; for (int i=0; i<n; i++) { cin>>x; low=min(low,x); high=max(high,x); F[x]++; } for (int i=low; i<=high; i++) { F[i]+=F[i-1]; } int q; cin>>q; for (int i=0; i<q; i++) { cin>>x; if (x<low) cout<<0<<endl; else if (x>high) cout<<F[high]<<endl; else cout<<F[x]<<endl; } return 0; }C - Hard problem Time Limit:1000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u Submit
Status
Practice
CodeForces 706C Description Vasiliy is fond of solving different tasks. Today he found one he wasn’t able to solve himself, so he asks you to help.
Vasiliy is given n strings consisting of lowercase English letters. He wants them to be sorted in lexicographical order (as in the dictionary), but he is not allowed to swap any of them. The only operation he is allowed to do is to reverse any of them (first character becomes last, second becomes one before last and so on).
To reverse the i-th string Vasiliy has to spent ci units of energy. He is interested in the minimum amount of energy he has to spent in order to have strings sorted in lexicographical order.
String A is lexicographically smaller than string B if it is shorter than B (|A| < |B|) and is its prefix, or if none of them is a prefix of the other and at the first position where they differ character in A is smaller than the character in B.
For the purpose of this problem, two equal strings nearby do not break the condition of sequence being sorted lexicographically.
Input The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of strings.
The second line contains n integers ci (0 ≤ ci ≤ 109), the i-th of them is equal to the amount of energy Vasiliy has to spent in order to reverse the i-th string.
Then follow n lines, each containing a string consisting of lowercase English letters. The total length of these strings doesn’t exceed 100 000.
Output If it is impossible to reverse some of the strings such that they will be located in lexicographical order, print - 1. Otherwise, print the minimum total amount of energy Vasiliy has to spent.
Sample Input Input 2 1 2 ba ac Output 1 Input 3 1 3 1 aa ba ac Output 1 Input 2 5 5 bbb aaa Output -1 Input 2 3 3 aaa aa Output -1 Hint In the second sample one has to reverse string 2 or string 3. To amount of energy required to reverse the string 3 is smaller.
In the third sample, both strings do not change after reverse and they go in the wrong order, so the answer is - 1.
In the fourth sample, both strings consists of characters ‘a’ only, but in the sorted order string “aa” should go before string “aaa”, thus the answer is - 1.
#include<stdio.h> #include<string> #include<cstring> #include<queue> #include<algorithm> #include<functional> #include<vector> #include<iomanip> #include<math.h> #include<iostream> #include<sstream> #include<set> #include<climits> #include<map> using namespace std; typedef long long ll; ll C[200000],F[100005][2]; int n; string A[200000],B[2000000]; int main() { memset(F,-1,sizeof(F)); cin.sync_with_stdio(false); cin>>n; for (int i=1; i<=n; i++) cin>>C[i]; for (int i=1; i<=n; i++) { cin>>A[i]; B[i]=A[i]; reverse(B[i].begin(),B[i].end()); } F[1][1]=C[1]; F[1][0]=0; for (int i=2; i<=n; i++) { if (A[i]>=A[i-1]&&F[i-1][0]!=-1) F[i][0]=F[i-1][0]; if (A[i]>=B[i-1]&&F[i-1][1]!=-1) { if (F[i][0]!=-1) F[i][0]=min(F[i][0],F[i-1][1]); else F[i][0]=F[i-1][1]; } if (B[i]>=A[i-1]&&F[i-1][0]!=-1) F[i][1]=F[i-1][0]+C[i]; if (B[i]>=B[i-1]&&F[i-1][1]!=-1) { if (F[i][1]!=-1) F[i][1]=min(F[i-1][1],F[i][1]-C[i])+C[i]; else F[i][1]=F[i-1][1]+C[i]; } if (F[i][0]==-1&&F[i][1]==-1) break; } if (F[n][0]==-1&&F[n][1]==-1) cout<<-1<<endl; else if(F[n][0]!=-1&&F[n][1]!=-1) cout<<min(F[n][0],F[n][1])<<endl; else if(F[n][0]==-1) cout<<F[n][1]<<endl; else cout<<F[n][0]<<endl; return 0; }但是不得不说 有些人的话说出来真是恶心
D - BST Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%lld & %llu Submit
Status
Practice
POJ 2309 Description Consider an infinite full binary search tree (see the figure below), the numbers in the nodes are 1, 2, 3, …. In a subtree whose root node is X, we can get the minimum number in this subtree by repeating going down the left node until the last level, and we can also find the maximum number by going down the right node. Now you are given some queries as “What are the minimum and maximum numbers in the subtree whose root node is X?” Please try to find answers for there queries.
Input In the input, the first line contains an integer N, which represents the number of queries. In the next N lines, each contains a number representing a subtree with root number X (1 <= X <= 2 31 - 1). Output There are N lines in total, the i-th of which contains the answer for the i-th query. Sample Input 2 8 10 Sample Output 1 15 9 11
#include<stdio.h> #include<string> #include<cstring> #include<queue> #include<algorithm> #include<functional> #include<vector> #include<iomanip> #include<math.h> #include<iostream> #include<sstream> #include<set> #include<climits> #include<map> using namespace std; int Lowbit(int x) { return x&(-x); } int main() { int n,a; scanf("%d",&n); for(int i=0; i<n; i++) { scanf("%d",&a); int Ans=Lowbit(a); printf("%d %d\n",a-Ans+1,a+Ans-1); } return 0; }E - Game Prediction Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit
Status
Practice
HDU 1338 Description Suppose there are M people, including you, playing a special card game. At the beginning, each player receives N cards. The pip of a card is a positive integer which is at most N*M. And there are no two cards with the same pip. During a round, each player chooses one card to compare with others. The player whose card with the biggest pip wins the round, and then the next round begins. After N rounds, when all the cards of each player have been chosen, the player who has won the most rounds is the winner of the game. Given your cards received at the beginning, write a program to tell the maximal number of rounds that you may at least win during the whole game. Input The input consists of several test cases. The first line of each case contains two integers m (2 <= m <= 20) and n (1 <= n <= 50), representing the number of players and the number of cards each player receives at the beginning of the game, respectively. This followed by a line with n positive integers, representing the pips of cards you received at the beginning. Then a blank line follows to separate the cases.
The input is terminated by a line with two zeros. Output For each test case, output a line consisting of the test case number followed by the number of rounds you will at least win during the game. Sample Input 2 5 1 7 2 10 9
6 11 62 63 54 66 65 61 57 56 50 53 48
0 0 Sample Output Case 1: 2 Case 2: 4
#include<stdio.h> #include<string> #include<cstring> #include<queue> #include<algorithm> #include<functional> #include<vector> #include<iomanip> #include<math.h> #include<iostream> #include<sstream> #include<set> #include<climits> #include<map> using namespace std; bool Have[1005]; int main() { cin.sync_with_stdio(false); int m,n,cases=0,a; while (cin>>m>>n) { memset(Have,0,sizeof(Have)); cases++; if (m==0&&n==0) break; for (int i=0; i<n; i++) { cin>>a; Have[a]=true; } int temp=0,Ans=0; for (int i=n*m; i>=1; i--) { if (Have[i]) { if (temp==0) Ans++; else temp--; } else { temp++; } } cout<<"Case "<<cases<<": "<<Ans<<endl; } return 0; }F - Apple Tree Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%lld & %llu Submit
Status
Practice
POJ 3321 Description There is an apple tree outside of kaka’s house. Every autumn, a lot of apples will grow in the tree. Kaka likes apple very much, so he has been carefully nurturing the big apple tree.
The tree has N forks which are connected by branches. Kaka numbers the forks by 1 to N and the root is always numbered by 1. Apples will grow on the forks and two apple won’t grow on the same fork. kaka wants to know how many apples are there in a sub-tree, for his study of the produce ability of the apple tree.
The trouble is that a new apple may grow on an empty fork some time and kaka may pick an apple from the tree for his dessert. Can you help kaka?
Input The first line contains an integer N (N ≤ 100,000) , which is the number of the forks in the tree. The following N - 1 lines each contain two integers u and v, which means fork u and fork v are connected by a branch. The next line contains an integer M (M ≤ 100,000). The following M lines each contain a message which is either “C x” which means the existence of the apple on fork x has been changed. i.e. if there is an apple on the fork, then Kaka pick it; otherwise a new apple has grown on the empty fork. or “Q x” which means an inquiry for the number of apples in the sub-tree above the fork x, including the apple (if exists) on the fork x Note the tree is full of apples at the beginning
Output For every inquiry, output the correspond answer per line. Sample Input 3 1 2 1 3 3 Q 1 C 2 Q 1 Sample Output 3 2
F题看了题解也写不出 代码只能过样例 交上去就WA 还没看出哪里搞错了
题解链接 : http://www.cnblogs.com/gj-Acit/p/3236843.html
