周赛题解

Problem A

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 26   Accepted Submission(s) : 1

Problem Description

Five hundred years later, the number of dragon balls will increase unexpectedly, so it's too difficult for Monkey King(WuKong) to gather all of the dragon balls together. 

His country has N cities and there are exactly N dragon balls in the world. At first, for the ith dragon ball, the sacred dragon will puts it in the ith city. Through long years, some cities' dragon ball(s) would be transported to other cities. To save physical strength WuKong plans to take Flying Nimbus Cloud, a magical flying cloud to gather dragon balls. 
Every time WuKong will collect the information of one dragon ball, he will ask you the information of that ball. You must tell him which city the ball is located and how many dragon balls are there in that city, you also need to tell him how many times the ball has been transported so far.

 

Input

The first line of the input is a single positive integer T(0 < T <= 100). For each case, the first line contains two integers: N and Q (2 < N <= 10000 , 2 < Q <= 10000). Each of the following Q lines contains either a fact or a question as the follow format: T A B : All the dragon balls which are in the same city with A have been transported to the city the Bth ball in. You can assume that the two cities are different. Q A : WuKong want to know X (the id of the city Ath ball is in), Y (the count of balls in Xth city) and Z (the tranporting times of the Ath ball). (1 <= A, B <= N)

 

Output

For each test case, output the test case number formated as sample output. Then for each query, output a line with three integers X Y Z saparated by a blank space.

 

Sample Input

2 3 3 T 1 2 T 3 2 Q 2 3 4 T 1 2 Q 1 T 1 3 Q 1

 

Sample Output

Case 1: 2 3 0 Case 2: 2 2 1 3 3 2

 题解：并差集，父节点，根节点个数，压缩路径，缺一不可；错了无数次；；；不会压缩路径；这个路径是从父节点开始逐步向根节点压缩；

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int ball[10010],ti[10010],q[10010],N;
int find(int x){int temp=ball[x];
    if(x==ball[x])return x;
    ball[x]=find(ball[x]);//此处递归找到父节点； 
    q[x]+=q[temp];//找到父节点后逐步执行下面这句话，temp的值随这递归被保存着； 
     return ball[x];//压缩路径。理解递归就好； 
}
void merge(int x,int y){
    int f1,f2;
    f1=find(x);f2=find(y);
    if(f1!=f2){
        ball[f1]=f2;ti[f2]+=ti[f1];
        q[f1]++;
    }
}
int main(){char m[5];
    int T,A,B,Q,flot=0,k=0;
    scanf("%d",&T);
    while(T--){flot++;k=0;
        scanf("%d%d",&N,&Q);
    for(int i=1;i<=N;++i)ti[i]=1,ball[i]=i,q[i]=0;
    printf("Case %d:
",flot);
        while(Q--){
            scanf("%s",m);
            if(strcmp(m,"T")==0){
                scanf("%d%d",&A,&B);
                merge(A,B);
            }
            else{
                scanf("%d",&A);
                k=find(A);find(A);find(A);find(A);find(A);find(A);find(A);//find(A)放函数里面就出错了； 
                printf("%d %d %d
",k,ti[k],q[A]);
            }
        }
    }
    return 0;
}

Problem D

Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 145   Accepted Submission(s) : 61

Problem Description

话说上回讲到海东集团面临内外交困，公司的元老也只剩下XHD夫妇二人了。显然，作为多年拼搏的商人，XHD不会坐以待毙的。
  一天，当他正在苦思冥想解困良策的时候，突然想到了自己的传家宝，那是公司成立的时候，父亲作为贺礼送来的一个锦囊，徐父当时交代，不到万不得已的时候，不要打开它。“现在不正是最需要的时候吗？”，一边想，XHD一边找到了这个精心保管的锦囊，打开一看，里面只有一句话“杭城北麓千人洞有宝”。
  二话不说，XHD拿起一个大口袋就出发了，这个千人洞他是知道的，小的时候，爸爸曾经带他来过这个隐蔽的路口，并告诉他，这是千人洞。他现在才明白爸爸当初这句话的含义。
  尽管有点印象，XHD还是花了很大的精力才找到这个异常隐蔽的洞口，走进一看，几乎惊呆了，真的是眼花缭乱！不过尽管宝贝的种类不少，但是每种宝贝的量并不多，当然，每种宝贝单位体积的价格也不一样，为了挽救HDU，现在请你帮忙尽快计算出来XHD最多能带回多少价值的宝贝？（假设宝贝可以分割，分割后的价值和对应的体积成正比）

 

Input

输入包含多个测试实例，每个实例的第一行是两个整数v和n(v,n<100)，分别表示口袋的容量和宝贝的种类，接着的n行每行包含2个整数pi和mi(0<pi,mi<10)，分别表示某种宝贝的单价和对应的体积，v为0的时候结束输入。 <="" div="">

 

Output

对于每个测试实例，请输出XHD最多能取回多少价值的宝贝，每个实例的输出占一行。

 

Sample Input

2 2 3 1 2 3 0

 

Sample Output

5

题解：贪心思路；

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct Node{
    int m,v;
};
int cmp(Node a,Node b){
    return a.m>b.m;
}
Node th[110];
int main(){int tot;
    int V,n;
    while(scanf("%d",&V),V){tot=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++)scanf("%d%d",&th[i].m,&th[i].v);
        sort(th,th+n,cmp);
        for(int i=0;V;i++){
            if(th[i].v<V){
                V-=th[i].v;tot+=th[i].m*th[i].v;
            }
            else tot+=V*th[i].m,V-=V;
        }
        printf("%d
",tot);
    }
    return 0;
}

Problem E

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 84   Accepted Submission(s) : 25

Problem Description

某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数。。。，以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。

 

Input

本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。

 

Output

共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。

 

Sample Input

2 20 40

 

Sample Output

1 7 19 1 19 37

题解：水题；

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int m[5010],n;
int search(){int tot=0;
    for(int i=1;i<=n;i++){
        if(m[i])tot++;
    }
    return tot;
}
int main(){int N,temp,k;
    scanf("%d",&N);
    while(N--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i)m[i]=i;k=1;
        while(search()>3){
            if(k==1){temp=0;
        for(int i=1;i<=n;i++){
                if(m[i])temp++;
                if(temp%2==0)m[i]=0;
            }
                }
                else{temp=0;
                    for(int i=1;i<=n;++i){
                        if(m[i])temp++;
                        if(temp%3==0)m[i]=0;
                    }
                }
                k=3-k;
        }temp=0;
        for(int i=1;i<=n;++i){
            if(m[i]){if(temp)printf(" ");
                printf("%d",m[i]);
                temp++;
            }
        }
        puts("");
    }
    return 0;
}

TIANKENG’s restaurant

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 1627    Accepted Submission(s): 586

Problem Description

TIANKENG manages a restaurant after graduating from ZCMU, and tens of thousands of customers come to have meal because of its delicious dishes. Today n groups of customers come to enjoy their meal, and there are Xi persons in the ith group in sum. Assuming that each customer can own only one chair. Now we know the arriving time STi and departure time EDi of each group. Could you help TIANKENG calculate the minimum chairs he needs to prepare so that every customer can take a seat when arriving the restaurant?

 

Input

The first line contains a positive integer T(T<=100), standing for T test cases in all.

Each cases has a positive integer n(1<=n<=10000), which means n groups of customer. Then following n lines, each line there is a positive integer Xi(1<=Xi<=100), referring to the sum of the number of the ith group people, and the arriving time STi and departure time Edi(the time format is hh:mm, 0<=hh<24, 0<=mm<60), Given that the arriving time must be earlier than the departure time.

Pay attention that when a group of people arrive at the restaurant as soon as a group of people leaves from the restaurant, then the arriving group can be arranged to take their seats if the seats are enough.

 

Output

For each test case, output the minimum number of chair that TIANKENG needs to prepare.

 

Sample Input

2 2 6 08:00 09:00 5 08:59 09:59 2 6 08:00 09:00 5 09:00 10:00

 

Sample Output

11 6

 题解：区间找最大数；在一个区间就加上；然后max—element找最大值；刚开始的思路是排序，类似今年暑假不ac写的，没想周到就wa了；

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAX(x,y) x>y?x:y
using namespace std;
const int MAXN=1510;
/*struct Node{
    int num;
    int s,e;
};
int cmp(Node a,Node b){
/*    if(a.e1!=b.e1)return a.e1<b.e1;
    else return a.e2<b.e2;
    return a.e<b.e;
}*/
int time[MAXN];
/*int judge(int x,int y,int a,int b){
    if(x>a)return 1;
    else if(x<a)return 0;
    else if(y>b)return 1;
    else return 0;
}*/
int main(){
    int T;
    int N,tot,num,t,max,hh,mm,s,e;
    scanf("%d",&T);
    while(T--){memset(time,0,sizeof(time));
        scanf("%d",&N);
        for(int i=0;i<N;i++){
    scanf("%d %d:%d",&t,&hh,&mm);
    s=hh*60+mm;
    scanf("%d:%d",&hh,&mm);
    e=hh*60+mm;
    for(int j=s;j<e;j++)time[j]+=t;
        }
        printf("%d
",*max_element(time,time+MAXN));
        }
    return 0;
}

Problem C

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 114   Accepted Submission(s) : 80

Problem Description

给你一个高为n ，宽为m列的网格，计算出这个网格中有多少个矩形，下图为高为2，宽为4的网格.

 

Input

第一行输入一个t, 表示有t组数据，然后每行输入n,m,分别表示网格的高和宽 ( n < 100 , m < 100).

 

Output

每行输出网格中有多少个矩形.

 

Sample Input

2 1 2 2 4

 

Sample Output

3 30

题解：这个题竟然没写出来。。。。。以前写过，，两种思路:C(n,2)*C(m,2)理解：矩形有四条边，在所有的线中任选两条横线和两条竖线；这样就组成矩形了；

思路二：m*(m-1)/2   *   n*(n-1)/2  横着矩形有m*(m-1)/2个，竖着的只需要把横着的格数看成1；就变成跟横着个数一样n*(n-1)/2两者想乘就好；

Problem B

Time Limit : 4000/2000ms (Java/Other)   Memory Limit : 131072/65536K (Java/Other)

Total Submission(s) : 35   Accepted Submission(s) : 2

Problem Description

Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs N (1 ≤ N ≤ 20,000) planks of wood, each having some integer length L_i (1 ≤ L_i ≤ 50,000) units. He then purchases a single long board just long enough to saw into the N planks (i.e., whose length is the sum of the lengths L_i). FJ is ignoring the "kerf", the extra length lost to sawdust when a sawcut is made; you should ignore it, too.

FJ sadly realizes that he doesn't own a saw with which to cut the wood, so he mosies over to Farmer Don's Farm with this long board and politely asks if he may borrow a saw.

Farmer Don, a closet capitalist, doesn't lend FJ a saw but instead offers to charge Farmer John for each of the N-1 cuts in the plank. The charge to cut a piece of wood is exactly equal to its length. Cutting a plank of length 21 costs 21 cents.

Farmer Don then lets Farmer John decide the order and locations to cut the plank. Help Farmer John determine the minimum amount of money he can spend to create the N planks. FJ knows that he can cut the board in various different orders which will result in different charges since the resulting intermediate planks are of different lengths.

 

Input

Line 1: One integer N, the number of planks 
Lines 2..N+1: Each line contains a single integer describing the length of a needed plank

 

Output

Line 1: One integer: the minimum amount of money he must spend to make N-1 cuts

 

Sample Input

3 8 5 8

 

Sample Output

34

题解：优先队列；注意结果要int64才对；

代码：

#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
int main(){int N,temp;
    while(~scanf("%d",&N)){
        priority_queue<int,vector<int>,greater<int> >dl;
    while(N--){scanf("%d",&temp);
        dl.push(temp);
    }__int64 sum=0,sum1,sum2;
    while(!dl.empty()){sum1=0;
        sum1=dl.top();
        dl.pop();
        sum2=0;
        if(!dl.empty()){
            sum2=dl.top();
            dl.pop();
        }
        sum+=sum1+sum2;
        if(!dl.empty())dl.push(sum1+sum2);
    }
    printf("%I64d
",sum);
    }
    return 0;
}

The least one

Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 560    Accepted Submission(s): 215

Problem Description

  In the RPG game “go back ice age”(I decide to develop the game after my undergraduate education), all heros have their own respected value, and the skill of killing monsters is defined as the following rule: one hero can kill the monstrers whose respected values are smaller then himself and the two respected values has none common factor but 1, so the skill is the same as the number of the monsters he can kill. Now each kind of value of the monsters come. And your hero have to kill at least M ones. To minimize the damage of the battle, you should dispatch a hero with minimal respected value. Which hero will you dispatch ? There are Q battles, in each battle, for i from 1 to Q, and your hero should kill Mi ones at least. You have all kind of heros with different respected values, and the values(heros’ and monsters’) are positive.

 

Input

  The first line has one integer Q, then Q lines follow. In the Q lines there is an integer Mi, 0<Q<=1000000, 0<Mi<=10000.

 

Output

  For each case, there are Q results, in each result, you should output the value of the hero you will dispatch to complete the task.

 

Sample Input

2 3 7

 

Sample Output

5 11

 

题解：二分+打表，stl里面的二分好用些，并且不容易出错；

代码：

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
using namespace std;
const int MAXN=100010;
int pri[MAXN],dp[10100],t;
void prime(){int i;
memset(pri,0,sizeof(pri));
    pri[0]=pri[1]=1;
    for(i=2;i<sqrt(MAXN*1.0);i++){
        for(int j=i*i;j<MAXN;j+=i)pri[j]=1;
    }
    for(i=0,t=0;i<MAXN;i++){
        if(!pri[i])dp[t++]=i;
    }
}
int main(){
    int T,n,x;
    prime();
    //for(int i=0;i<t;i++)printf("%d ",dp[i]);
    //printf("%d ",t);
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        printf("%d
",*upper_bound(dp,dp+t,n));
    }
    return 0;
}

Problem H

Time Limit : 1000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 25   Accepted Submission(s) : 3

Problem Description

现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（A类）、文具（B类）、差旅（C类），要求每张发票的总额不得超过1000元，每张发票上，单项物品的价值不得超过600元。现请你编写程序，在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。

 

Input

测试输入包含若干测试用例。每个测试用例的第1行包含两个正数 Q 和 N，其中 Q 是给定的报销额度，N（<=30）是发票张数。随后是 N 行输入，每行的格式为： m Type_1:price_1 Type_2:price_2 ... Type_m:price_m 其中正整数 m 是这张发票上所开物品的件数，Type_i 和 price_i 是第 i 项物品的种类和价值。物品种类用一个大写英文字母表示。当N为0时，全部输入结束，相应的结果不要输出。

 

Output

对每个测试用例输出1行，即可以报销的最大数额，精确到小数点后2位。

 

Sample Input

200.00 3 2 A:23.50 B:100.00 1 C:650.00 3 A:59.99 A:120.00 X:10.00 1200.00 2 2 B:600.00 A:400.00 1 C:200.50 1200.50 3 2 B:600.00 A:400.00 1 C:200.50 1 A:100.00 100.00 0

 

Sample Output

123.50 1000.00 1200.50

 题解：这个题，各种错，本来想用背包，奈何是double型的，就感觉用不成，最后学长讲可以用背包只需要乘以100将double化成int最后再除，还可以用dp；

注意：
1.数组至少要开到3000050；
2.是单类物品不能超过600元，不是单项，如A:310 A:320，那A类物品为630元，不符合要求，不能报销；
3.用scanf()读入的话，要先读掉类型字符前的一个空格。

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MIN(x,y) x<y?x:y
#define MAX(x,y) x>y?x:y
using namespace std;
int fp[31],bag[3000050];
int main(){int m,N,t,SUM,temp1;char c;
    double Q,flot,sum,temp,s,z,max,S[3];
    while(scanf("%lf%d",&Q,&N),N){memset(fp,0,sizeof(fp));t=0;
    SUM=0;memset(bag,0,sizeof(bag));
        while(N--){flot=1;sum=0;
            scanf("%d",&m);memset(S,0,sizeof(S));
            while(m--){
                getchar();
                scanf("%c:",&c);
                //printf("%c
",c);
                if(c!='A'&&c!='B'&&c!='C'){
                    flot=0;
                }
                scanf("%lf",&temp);sum+=temp;
                if(flot)S[c-'A']+=temp;
                if(sum>1000)flot=0;
                for(int i=0;i<3;i++){
                    if(S[i]>600)flot=0;
                }
            }
            if(flot){
                fp[t]=(int)(sum*100);//printf("*****%d %.2lf
",t,sum);
            SUM+=fp[t];t++;
            }
        }temp1=(int)(Q*100);
        //sort(fp,fp+t);
    //    for(int i=0;i<t;++i)printf("%.2lf ",fp[i]);puts("");
        for(int i=0;i<t;i++){
            for(int j=temp1;j>=fp[i];j--){
                bag[j]=MAX(bag[j],bag[j-fp[i]]+fp[i]);
            }
        }
        printf("%.2lf
",bag[temp1]/100.0);
    }
    return 0;
}