2013/10/13周赛

2019-04-14 16:38发布

站内文章 / 模拟电子
15230 0 965

A. Pie

1000ms 1000ms 32768KB 64-bit integer IO format: %I64d      Java class name: Main Submit Status PID: 6115 Font Size:   My birthday is coming up and traditionally I'm serving pie. Not just one pie, no, I have a number N of them, of various tastes and of various sizes. F of my friends are coming to my party and each of them gets a piece of pie. This should be one piece of one pie, not several small pieces since that looks messy. This piece can be one whole pie though.

My friends are very annoying and if one of them gets a bigger piece than the others, they start complaining. Therefore all of them should get equally sized (but not necessarily equally shaped) pieces, even if this leads to some pie getting spoiled (which is better than spoiling the party). Of course, I want a piece of pie for myself too, and that piece should also be of the same size. 

What is the largest possible piece size all of us can get? All the pies are cylindrical in shape and they all have the same height 1, but the radii of the pies can be different.

Input

One line with a positive integer: the number of test cases. Then for each test case:
---One line with two integers N and F with 1 <= N, F <= 10 000: the number of pies and the number of friends.
---One line with N integers ri with 1 <= ri <= 10 000: the radii of the pies.

Output

For each test case, output one line with the largest possible volume V such that me and my friends can all get a pie piece of size V. The answer should be given as a floating point number with an absolute error of at most 10^(-3).

Sample Input

3 3 3 4 3 3 1 24 5 10 5 1 4 2 3 4 5 6 5 4 2

Sample Output

25.1327 3.1416 50.2655    一个二分就可以了，我二分写残了，不够熟悉。   #include #include #include #include #include #include #include #include #include #include #include #define PI acos(-1.0) #define maxn 10000 #define INF 1<<25 #define eps 0.000001 typedef long long ll; using namespace std; int n,f; double rn[maxn+10],top,mid,bot; int main () { int t,i,j,k; cin>>t; while(t--) { scanf("%d%d",&n,&f); top=0; for (i=0; i=eps) { mid=(bot+top)/2; sum=0; for (i=0; i=f) bot=mid; else top=mid; } printf("%.4lf ",mid*PI); } return 0; }

B. Ants

1000ms 1000ms 30000KB 64-bit integer IO format: %lld      Java class name: Main Submit Status PID: 1971 Font Size:   An army of ants walk on a horizontal pole of length l cm, each with a constant speed of 1 cm/s. When a walking ant reaches an end of the pole, it immediatelly falls off it. When two ants meet they turn back and start walking in opposite directions. We know the original positions of ants on the pole, unfortunately, we do not know the directions in which the ants are walking. Your task is to compute the earliest and the latest possible times needed for all ants to fall off the pole.

Input

The first line of input contains one integer giving the number of cases that follow. The data for each case start with two integer numbers: the length of the pole (in cm) and n, the number of ants residing on the pole. These two numbers are followed by n integers giving the position of each ant on the pole as the distance measured from the left end of the pole, in no particular order. All input integers are not bigger than 1000000 and they are separated by whitespace.

Output

For each case of input, output two numbers separated by a single space. The first number is the earliest possible time when all ants fall off the pole (if the directions of their walks are chosen appropriately) and the second number is the latest possible such time. 

Sample Input

2 10 3 2 6 7 214 7 11 12 7 13 176 23 191

Sample Output

4 8 38 207

    想法题目，每两个蚂蚁之间的对碰可以理解成映射了位置。 //B. Ants #include #include #include #include #include #include #include #include #include #include #include #define PI acos(-1.0) #define maxn 1000 #define INF 1<<25 int a[1000005],b[1000005],c[1000005],d[1000005]; using namespace std; int main () { int N; cin>>N; while(N--) { int l,n; scanf("%d%d",&l,&n); for(int i=0;i

C. A计划

1000ms 1000ms 32768KB 64-bit integer IO format: %I64d      Java class name: Main Submit Status PID: 6246 Font Size:   可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主，因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚，告招天下勇士来拯救公主。不过公主早已习以为常，她深信智勇的骑士LJ肯定能将她救出。
现据密探所报，公主被关在一个两层的迷宫里，迷宫的入口是S（0，0，0），公主的位置用P表示，时空传输机用#表示，墙用*表示，平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置，但如果被转到的位置是墙的话，那骑士们就会被撞死。骑士们在一层中只能前后左右移动，每移动一格花1时刻。层间的移动只能通过时空传输机，且不需要任何时间。

Input

输入的第一行C表示共有C个测试数据，每个测试数据的前一行有三个整数N，M，T。 N，M迷宫的大小N*M（1 <= N,M <=10)。T如上所意。接下去的前N*M表示迷宫的第一层的布置情况，后N*M表示迷宫第二层的布置情况。

Output

如果骑士们能够在T时刻能找到公主就输出“YES”，否则输出“NO”。

Sample Input

1 5 5 14 S*#*. .#... ..... ****. ...#. ..*.P #.*.. ***.. ...*. *.#..

Sample Output

YES
   一个三维的BFS，其实和二维没有太大的区别，裸题。    琦神的代码看着舒服......    #include #include #include #include #include #include #include #include #include #include #include #define PI acos(-1.0) #define maxn 1000 #define INF 1<<25 typedef long long ll; using namespace std; char a[2][12][12]; int n,m,t; struct node { int x,y,z; int s; }; int in(int x, int y) { if (x>=0 && x=0 && y q; node st; int visit[2][12][12]={0},i,j,k; int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; st.x=st.y=st.z=st.s=0; visit[0][0][0]=1; q.push(st); bool flag=false; while(!q.empty()) { st=q.front(); q.pop(); node tp; for (i=0; i<4; i++) { tp.x=st.x+dir[i][0]; tp.y=st.y+dir[i][1]; tp.z=st.z; tp.s=st.s+1; if (tp.s>t) { cout<<"NO"<>cas; while(cas--) { cin>>n>>m>>t; memset(a,0,sizeof(a)); for (i=0; i<2; i++) for (j=0; j>a[i][j][k]; bfs(); } return 0; }

D. King Arthur's Knights

1000ms 1000ms 32768KB Special Judge 64-bit integer IO format: %I64d      Java class name: Main Submit Status PID: 26133 Font Size:   I am the bone of my sword. Steel is my body, and the fire is my blood.
- from Fate / Stay Night
You must have known the legend of King Arthur and his knights of the round table. The round table has no head, implying that everyone has equal status. Some knights are close friends with each other, so they prefer to sit next to each other.

Given the relationship of these knights, the King Arthur request you to find an arrangement such that, for every knight, his two adjacent knights are both his close friends. And you should note that because the knights are very united, everyone has at least half of the group as his close friends. More specifically speaking, if there are N knights in total, every knight has at least (N + 1) / 2 other knights as his close friends.

Input

The first line of each test case contains two integers N (3 <= N <= 150) and M, indicating that there are N knights and M relationships in total. Then M lines followed, each of which contains two integers ai and bi (1 <= ai, bi <= n, ai != bi), indicating that knight ai and knight bi are close friends.

Output

For each test case, output one line containing N integers X1, X2, ..., XN separated by spaces, which indicating an round table arrangement. Please note that XN and X1 are also considered adjacent. The answer may be not unique, and any correct answer will be OK. If there is no solution exists, just output "no solution".

Sample Input

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

Sample Output

1 2 3 1 4 2 3
       DFS
#include #include #include #include #include #include #include #include #include #include #include #define PI acos(-1.0) #define maxn 160 #define INF 1<<25 typedef long long ll; using namespace std; int n,m; int b[maxn]; int mp[maxn][maxn]; int visit[maxn]={0}; bool flag=false; void dfs(int t, int x) { int i; if (flag) return; if (t==n+1) { if (mp[b[n]][b[1]]) { flag=true; for (i=1; i

E. Flowers

2000ms 2000ms 65536KB 64-bit integer IO format: %I64d      Java class name: Main Submit Status PID: 26111 Font Size:   As is known to all, the blooming time and duration varies between different kinds of flowers. Now there is a garden planted full of flowers. The gardener wants to know how many flowers will bloom in the garden in a specific time. But there are too many flowers in the garden, so he wants you to help him.

Input

The first line contains a single integer t (1 <= t <= 10), the number of test cases.
For each case, the first line contains two integer N and M, where N (1 <= N <= 10^5) is the number of flowers, and M (1 <= M <= 10^5) is the query times. 
In the next N lines, each line contains two integer Si and Ti (1 <= Si <= Ti <= 10^9), means i-th flower will be blooming at time [Si, Ti].
In the next M lines, each line contains an integer Ti, means the time of i-th query.

Output

For each case, output the case number as shown and then print M lines. Each line contains an integer, meaning the number of blooming flowers.
Sample outputs are available for more details.

Sample Input

2 1 1 5 10 4 2 3 1 4 4 8 1 4 6

Sample Output

Case #1: 0 Case #2: 1 2 1
   先来一个范神的哈希写的  #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int s[100005],t[100005],q[100005],c[500005],ans[500005]; int main() { int tt; cin>>tt; for (int cs=1; cs<=tt; cs++) { int n,m; scanf("%d%d",&n,&m); int cnt=0; for (int i=1; i<=n; i++) { scanf("%d%d",&s[i],&t[i]); c[++cnt]=s[i]; c[++cnt]=t[i]; } for (int i=1; i<=m; i++) { scanf("%d",&q[i]); c[++cnt]=q[i]; } sort(c+1,c+n*2+m+1); map mp; for (int i=1; i<=n*2+m; i++) if (mp.find(c[i])==mp.end()) mp[c[i]]=i; // for (map::iterator p=mp.begin();p!=mp.end();p++) // cout<first<<'$'<second<  再来一个魏神用排序写的 #include #include #include #include #include #include #include #define MAXN 111111 #define MAXM 111 #define INF 1000000000 using namespace std; typedef pair P; P ask[MAXN], boom[MAXN]; int n, m; priority_queue, greater > q; int ans[MAXN]; int main() { int T; int cas = 0; scanf("%d", &T); while(T--) { while(!q.empty()) q.pop(); scanf("%d%d", &n, &m); for(int i = 0; i < n; i++) { scanf("%d%d", &boom[i].first, &boom[i].second); } sort(boom, boom + n); for(int i = 0; i < m; i++) { scanf("%d", &ask[i].first); ask[i].second = i; } sort(ask, ask + m); int j = 0; for(int i = 0; i < m; i++) { while(j < n && boom[j].first <= ask[i].first) { q.push(boom[j].second); j++; } while(!q.empty()) { if(q.top() >= ask[i].first) break; else q.pop(); } ans[ask[i].second] = q.size(); } printf("Case #%d: ", ++cas); for(int i = 0; i < m; i++) printf("%d ", ans[i]); } return 0; }

F. 最大连续子序列

1000ms 1000ms 32768KB 64-bit integer IO format: %I64d      Java class name: Main Submit Status PID: 5431 Font Size:   给定K个整数的序列{ N1, N2, ..., NK }，其任意连续子序列可表示为{ Ni, Ni+1, ..., 
Nj }，其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个， 
例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和 
为20。 
在今年的数据结构考卷中，要求编写程序得到最大和，现在增加一个要求，即还需要输出该 
子序列的第一个和最后一个元素。

Input

测试输入包含若干测试用例，每个测试用例占2行，第1行给出正整数K( < 10000 )，第2行给出K个整数，中间用空格分隔。当K为0时，输入结束，该用例不被处理。

Output

对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元 
素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个（如输入样例的第2、3组）。若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素。 

Sample Input

6 -2 11 -4 13 -5 -2 10 -10 1 2 3 4 -5 -23 3 7 -21 6 5 -8 3 2 5 0 1 10 3 -1 -5 -2 3 -1 0 -2 0

Sample Output

20 11 13 10 1 4 10 3 5 10 10 10 0 -1 -2 0 0 0 HintHint Huge input, scanf is recommended.    贪心，就一个想法  //F. 最大连续子序列 #include int main() { int i,k,sum,flag,start,end,itemp,max; int a[10005]; while(scanf("%d",&k) && k!=0) { flag=0; for(i=0;i=0) flag=1; } max=0; if(flag==0) { printf("%d %d %d ",max,a[0],a[k-1]); continue; } else { sum=a[0]; max=a[0]; itemp=0; start=0; end=0; for(i=1;imax) { max=sum; start=i; end=itemp; } } printf("%d %d %d ",max,a[end],a[start]); } } }

G. {A} + {B}

5000ms 5000ms 32768KB 64-bit integer IO format: %I64d      Java class name: Main Submit Status PID: 5612 Font Size:   给你两个集合，要求{A} + {B}.
注:同一个集合中不会有两个相同的元素.

Input

每组输入数据分为三行,第一行有两个数字n,m(0 Output 针对每组数据输出一行数据,表示合并后的集合,要求从小到大输出,每个元素之间有一个空格隔开.

Sample Input

1 2 1 2 3 1 2 1 1 2

Sample Output

1 2 3 1 2
先来一个用STL中set写的#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int main() { int a,b; while(scanf("%d%d",&a,&b)!=EOF) { set s; int t; for (int i=1; i<=a; i++) { scanf("%d",&t); s.insert(t); } for (int i=1; i<=b; i++) { scanf("%d",&t); s.insert(t); } set::iterator p=s.begin(); printf("%d",*p); p++; for (; p!=s.end(); p++) printf(" %d",*p); puts(""); } return 0; }
   在来一个用指针模拟运算的，时间复杂度最小。 #include #include #include #include #include #include #include #include #include #include #include #define PI acos(-1.0) #define maxn 10000 #define INF 1<<25 typedef long long ll; using namespace std; int a[maxn+10],b[maxn+10],c[maxn*2+10]; int main () { int n,m,i,j,t; while(cin>>n>>m) { for (i=0; ib[j]) { c[t++]=b[j]; j++; } if (a[i]==b[j]) { c[t++]=a[i]; i++; j++; } } while(i

热门文章