2016年10月1日训练 QAQ

据说这是zld的题

书写比赛

【问题描述】
最近，SZ 在高一各个班级都举行了书写比赛，具体内容是让同学们走上讲台在黑
板上写下几段文字。
现在，你所在的班级有 N 个人，座号分别为 1~N（即给定顺序），每个同学按座号
顺序需要书写 S 段文字。书写过程中，每个人的速度是不一样的，每个同学每个单位的
时间可以书写 Vi 段文字，当一组上讲台的人中最慢的人完成书写，就轮到下一组继续
书写。
不幸的是，老教室的讲台陈年失修，当站在上面的同学的体重大于 W 的时候就会
崩塌。每个同学的重量 Qi 是不同的，每次上台的人的重量和不能超过 W，除非你购买
了平(zhe)安(shou)保险，否则你就要付出巨额赔款。
现在，你的班主任将这个重要的任务交付给了你，要求你巧妙地在给定的顺序下安
排分组，在总时间最短的情况下完成书写比赛。如果你成功地做出了这个方案，张璐老
师保证你的班级将会获胜，你也会因此荣获“三好学生”称号。如果你无法制定出这个
方案，你将被要求抄书。
为了降低难度，善良的 S.C.帮你向张璐老师提出申请只要求你输出最短的时间，精
确到小数点后两位（四舍五入）即可。S.C.对你如此友好，你更应该完成这一道题，
不要辜负 S.C.对你的希望。
【输入格式】
第一行，共三个数 W，S，N；
接下来 N 行，按给定顺序，每行两个数 Qi 和 Vi，Vi、Qi 分别是第 i 号同学写
字的速度（段/单位时间）和他的重量。
【输出格式】
仅一行，代表最短的时间，精确到小数点后两位。
【输入输出样例】
800 300 4
53 5.0
59 3.0
38 2.0
69 2.0
150.00
【数据规模】
对于 20%的数据，有 N ≤ 15；
对于 100%的数据，有 N ≤ 2000 ; W, S ≤ 32767；
本题保证 Q ≤ W。

题解：f[i]表示第1到第i位同学的最小花费时间，易得f[i]=min(f[i],f[j-1]+时间花费)

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <stdio.h>
 4 #include <cmath>
 5 #include <string>
 6 #include <string.h>
 7 #include <numeric>
 8 #define gc getchar()
 9 #define REM main
10 using namespace std;
11 int q[233333];
12 double v[2333];
13 double dp[233333];
14 int read()
15 {
16     int xxxx=0,fuh=1;char ch=gc;
17     while(!isdigit(ch)){
18         if(ch=='-')fuh=-1;
19         ch=gc;
20     }
21     while(isdigit(ch)){
22         xxxx=(xxxx<<3)+(xxxx<<1)+ch-'0';ch=gc;
23     }
24     return xxxx*fuh;
25 }
26 int REM()
27 {
28     cin.sync_with_stdio(false);
29     int w,s,n,i,j;
30     cin>>w>>s>>n;
31     for (i=1;i<=n;i++)
32       {
33         cin>>q[i]>>v[i];
34         q[i]+=q[i-1];
35          }
36     for (i=1;i<=n;i++)
37       {
38          double yz=v[i];
39         dp[i]=s/v[i]+dp[i-1];
40         for (j=i;j>=1;j--)
41             {
42              yz=min(yz,v[j]);
43             if (q[i]-q[j-1]<=w)
44                 dp[i]=min(dp[i],s/yz+dp[j-1]);
45             else break;
46           }
47       }
48     printf("%.2lf",dp[n]);
49     return 0;
50 }

QAQ

灌水

【问题描述】
学霸 ZLD 是全年段同学 Orz 的对象，ZLD 告诉 S.C.在他小时候他的妈妈带他去
测 IQ，结果显示他的 IQ 只有 70。显然，这只能说明出 IQ 测试题的医生弱爆了，ZLD
大神不屑于去做这种水题。
经过 S.C.的调查，S.C.觉得下面这件事足以证明 ZLD 大神 IQ 的高度：ZLD 小时
候就很勤奋，小学就已经有了相当的算法水平，于是他家人决定给他一项艰巨而又有趣
的任务。在 ZLD 的老家有一大片的田，ZLD 要把水灌到他的 N(1≤N≤1000)块农田，
农田被数字 1 到 N 标记。把一块农田进行灌水有两种方法，一是从其他已经有水的农
田引水；另外也可以在这块农田建造水池。在第 i 号农田内建造一个水池需要的花费为
Wi(1≤Wi≤100100)，连接两块农田需要花费 Pij(1≤Pij≤100100, Pij=Pji, Pii=0)。ZLD
则要把这 N 片农田灌满水所需的最少费用求出来！
结果自不必说， ZLD 把这个他认为的水题给虐爆了。那么同样有志向成为神犇的你
是不是也需要这道题来证明自己的实力呢？
【输入格式】
第一行是一个整数 N；
接下来 N 行每行有一个数 Wi；
第 N+2 行到第 2N+1 行每行有 N 个数用空格隔开，第 N+1+i 行的第 j 个数代表 Pij。
【输出格式】
仅一行，输出最小费用。
【输入输出样例】
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
9
【数据规模】
对于 50%的数据，有 N ≤ 500；
对于 100%的数据，有 N ≤ 1000。

题解：我们额外建立一个点，和原有的点连边，边权为点权，然后做一遍最小生成树就好了。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <stdio.h>
 4 #include <cmath>
 5 #include <string>
 6 #include <string.h>
 7 #include <numeric>
 8 #define gc getchar()
 9 #define REM main
10 using namespace std;
11 int n,m;
12 int fj[2000];
13 struct node
14 {
15     int x,y,w;
16 }a[2003];
17 int father[2001];
18 int find(int x)
19 {
20     return father[x]==x?x:father[x]=find(father[x]);
21 }
22 int read()
23 {
24     int xxxx=0,fuh=1;char ch=gc;
25     while(!isdigit(ch)){
26         if(ch=='-')fuh=-1;
27         ch=gc;
28     }
29     while(isdigit(ch)){
30         xxxx=(xxxx<<3)+(xxxx<<1)+ch-'0';ch=gc;
31     }
32     return xxxx*fuh;
33 }
34 /*int pow4(int a,int b)
35 {
36     int r=1,base=a;
37     while(b!=0)
38     {
39         if(b&1)
40             r*=base;
41         base*=base;
42         b>>=1;
43     }
44     return r;
45 }*/
46 bool cmp(node zy,node yz)
47 {
48     return zy.w<yz.w;
49 }
50 
51 int REM()
52 {
53 
54     int flag=0;
55     int i,j;
56     int temp;
57     n=read();
58     for (i=1;i<=n;i++)
59       fj[i]=read(),father[i]=i;
60     father[n+1]=n+1;
61     for (i=1;i<=n;i++)
62       for (j=1;j<=n;j++)
63         {
64           temp=read();
65           if (i!=j)
66           {
67           a[++flag].x=i;
68           a[flag].y=j;
69           a[flag].w=temp;}
70         }
71     for (i=1;i<=n;i++)
72       {
73         a[++flag].x=n+1;
74         a[flag].y=i;
75         a[flag].w=fj[i];
76       }
77     sort(a+1,a+flag+1,cmp);
78     int cnt=0;long long ans=0;
79     for (i=1;i<=flag;i++)
80       {
81           int fx=find(a[i].x);
82           int fy=find(a[i].y);
83           if (fx!=fy)
84             {
85                 ans+=a[i].w;
86                 cnt++;
87                 father[fx]=fy;
88             }
89           if (cnt==n)
90             break;
91       }
92     cout<<ans;
93     return 0;
94 }

qwq

礼物

【问题描述】
ZLD 蒟蒻以前只会泡汉子。现在要开始泡妹子了。但他不会，于是他就只好请教小
红如何泡妹子。
由于最近是国庆节，小红收到了他的妹子的 N 个礼物，分别从 1~N 编号，但可恶
的老鼠偷走了其中一个礼物。小红十分生气，他答应只要 ZLD 蒟蒻找到那个丢失的礼
物的编号，他就传授 ZLD 蒟蒻泡妹子绝技。
故事的结局是你帮助 ZLD 蒟蒻找到了礼物的编号，让他学会了如何泡妹子，所以
你必须帮助 ZLD 蒟蒻找到那个丢了的礼物！
【输入格式】
第 1 行为一个正整数 N；
接下来有 N-1 行，每行一个小红现在有的礼物编号。
【输出格式】
一行一个数字，为被可恶的老鼠偷走的礼物编号。
【输入输出样例】
5
2
3
1
5
4
【数据规模】
对于 30%的数据，满足 N≤500；
对于 100%的数据，满足 N≤1500000。

题解：算出1...n的和，然后一个个减掉就好了。但是这题略坑，北大zld学长给我们开2m内存。。不过不虚。QAQ

 1 #include <stdio.h>
 2 #define REM main
 3 using namespace std;
 4 
 5 int REM()
 6 {
 7     //freopen("gift.in","r",stdin);
 8     //freopen("gift.out","w",stdout);
 9     int n;
10     scanf("%d",&n);
11     int i,temp;
12     long long gcy;
13     gcy=((long long)n*(n+1))>>1;
14     for (i=1;i<=n-1;i++)
15       scanf("%d",&temp),gcy-=temp;
16     printf("%lld",gcy);
17     return 0;
18 }

23333

今天题目好水但是我写狗了。。

QAQ

2016年10月1日 训练 QAQ

2016年10月1日训练 QAQ