2018.11.23 浪在ACM集训队第六次测试赛(div.3) 解题报告

感觉发现了自己的一些薄弱的环节。首先是A题当场忘掉了如何分离数位,然后慢慢推的。。。B题的话属于我没看清题意。。。C题比较简单,D题是一个裸的01背包变式,其实我已经忘了01背包是啥了啊QAQ幸亏之前背了一下要不这题是彻彻底底的做不上来了。。。。

详细题解请阅读全文。


问题 A: 数字统计(单点1s,128M)

题目描述
请统计某个给定范围[L, R]的所有整数中,数字 2 出现的次数。 
比如给定范围[2, 22],数字 2 在数 2 中出现了 1 次,在数 12 中出现 1 次,在数 20 中出 现 1 次,在数 21 中出现 1 次,在数 22 中出现 2 次,所以数字 2 在该范围内一共出现了 6 次。 

输入
输入共 1 行,为两个正整数 L 和 R,之间用一个空格隔开。

输出
输出共 1 行,表示数字 2 出现的次数。

样例输入
2 22 

样例输出
6 

提示
【数据范围】 
1 ≤ L ≤ R≤ 10000。

我的思路就是先进行一下预处理,把每一个数字的2的个数先找出来存到数组里,然后再扫一遍[l,r]统计答案就好。时间复杂度是线性的。

但是处理数位的时候突然忘记了数位分离怎么写,现场推了一下(我真的是弱啊)

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#define maxn 23333
using namespace std;
int ans[maxn];
int l, r;
int sum = 0;
int work(int x) {
    int ans = 0;
    while (x != 0) {
        if (x % 10 == 2)
            ans++;
        x /= 10;
    }
    return ans;
}

int main() {
    for (int i = 1; i <= 10086; i++) {
        ans[i] = work(i);
    }
    cin >> l >> r;
    for (int i = l; i <= r; i++) {
        sum += ans[i];
    }
    cout << sum;
//    system("pause");
    return 0;
}

问题 B: 接水问题(单点1s,128M)

题目描述
学校里有一个水房,水房里一共装有 m 个龙头可供同学们打开水,每个龙头每秒钟的 供水量相等,均为 1。 
现在有 n 名同学准备接水,他们的初始接水顺序已经确定。 
将这些同学按接水顺序从 1 到 n 编号,i 号同学的接水量为 wi。 
接水开始时,1 到 m 号同学各占一个水龙头,并同时打 开水龙头接水。 
当其中某名同学 j 完成其接水量要求 wj 后,下一名排队等候接水的同学 k 马上接替 j 同学的位置开始接水。 
这个换人的过程是瞬间完成的,且没有任何水的浪费。 
即 j 同学第 x 秒结束时完成接水,则 k 同学第 x+1 秒立刻开始接水。 
若当前接水人数 n’不足 m, 则只有 n’个龙头供水,其它 m−n’个龙头关闭。 
现在给出 n 名同学的接水量,按照上述接水规则,问所有同学都接完水需要多少秒。 

输入
第 1 行 2 个整数 n 和 m,用一个空格隔开,分别表示接水人数和龙头个数。 
第 2 行 n 个整数 w1、w2、……、wn,每两个整数之间用一个空格隔开,wi表示 i 号同 学的接水量。 

输出
输出只有一行,1 个整数,表示接水所需的总时间。

样例输入
5 3
4 4 1 2 1 

样例输出
4

提示
【输入输出样例 说明】 
第 1 秒,3 人接水。 
第 1 秒结束时,1、2、3 号同学每人的已接水量为 1,3 号同学接完 水,4 号同学接替 3 号同学开始接水。 
第 2 秒,3 人接水。第 2 秒结束时,1、2 号同学每人的已接水量为 2,4 号同学的已接 水量为 1。 
第 3 秒,3 人接水。第 3 秒结束时,1、2 号同学每人的已接水量为 3,4 号同学的已接 水量为 2。4 号同学接完水,5 号同学接替 4 号同学开始接水。 
第 4 秒,3 人接水。第 4 秒结束时,1、2 号同学每人的已接水量为 4,5 号同学的已接 水量为 1。 
1、2、5 号同学接完水,即所有人完成接水。 总接水时间为 4 秒。 
【数据范围】 
1 ≤ n ≤ 10000,1 ≤ m ≤ 100 且 m≤ n; 1 ≤ wi ≤ 100。 

这不是noip原题吗(逃

好吧一开始是我没看清题意,所以这个题花的时间稍微长一点。它实际上是让你模拟一下这个接水过程,然后保证时间利用率是最高的。

注意到他们的初始接水顺序已经确定,意思是说,接水顺序不用再进行额外的处理。

想一下,实际生活中排队应该怎么排呢?

现在有一堆队伍等待接水,每条队伍的长度都不一样,你是要在哪条队伍里进行排队呢?一般我们会选择等待人数最少的队伍进行排队,换到这个题上讲,哪个队伍目前花费的时间最短,我们就应该去哪里排队。

那就好办了。我们开一个临时数组记录一下当前队伍长度,算法思路就是下面这个:

  1. 按顺序考虑每一个人需要接水的时间
  2. 在当前队列里找到等待时间最小的一个,进去排队(指更新临时数组)
  3. 更新答案(因为这个人进去以后答案可能会变化,也就是总接水时间有可能会变长)

我这里为了方便,用了两个函数,一个函数用来寻找当前接水时间最小的队伍,它返回一个序号,表示现在这个人应该在这个队伍进行接水。另一个函数用来更新答案。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#define maxn 23333
using namespace std;
int n, m;
int w[maxn];
int now_length[maxn];
int ans = -1;

int find_min_way() {
    int ans = 1;
    for (int i = 2; i <= m; i++) {
        if (now_length[i] < now_length[ans])
            ans = i;
    }
    return ans;
}

void upd_ans(){
    int min_now = 1;
    for (int i = 2; i <= m; i++) {
        if (now_length[min_now] < now_length[i])
            min_now = i;
    }
    ans = now_length[min_now];
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    memset(now_length, 0, sizeof(now_length));
    for (int i = 1; i <= n; i++) {
        int choose = find_min_way();
        now_length[choose] += w[i];
        upd_ans();
    }
    cout << ans;
//    system("pause");
    return 0;
}

问题 C: 明明的随机数(单点1s,128M)

我觉得要是按照难度排序的话这个题应该放第一题啊(逃

题目描述
明明想在学校中请一些同学一起做一项问卷调查。
为了实验的客观性,他先用计算机生成了N个1到1000之间的随机整数(N≤100),对于其中重复的数字,只保留一个,
把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,
按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。 

(我觉得我应该学一下新的排版方式,先这样凑活着看吧,我会再改的)

输入
输入文件有2行, 
第1行为1个正整数,表示所生成的随机数的个数:N 
第2行有N个用空格隔开的正整数,为所产生的随机数。 


输出
输出文件也是2行. 
第1行为1个正整数M,表示不相同的随机数的个数。 
第2行为M个用空格隔开的正整数,为从小到大排好序的不相同的随机数。 


样例输入
10
20 40 32 67 40 20 89 300 400 15

样例输出
8
15 20 32 40 67 89 300 400

读入数据时进行判重,我的做法比较简单,开一个bool数组,记录每一个数字有没有出现过,如果有就不进行存储,需要一个额外的变量记录能存下来的数的个数,这个变量的值就是不相同的随机数的个数,然后对这个数组进行排序就可以了。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#define maxn 2333
using namespace std;
bool used[maxn];
int num[maxn];
int sum;
int n;
int a;
int main() {
    cin >> n;
    memset(used, false, sizeof(used));
    for (int i = 1; i <= n; i++) {
        cin >> a;
        if (!used[a]) {
            used[a] = true;
            num[++sum] = a;
        }
    }
    sort(num + 1, num + sum + 1);
    printf("%d\n", sum);
    for (int i = 1; i <= sum; i++) {
        cout << num[i];
        if (i != sum)
            cout << " ";
    }
//    system("pause");
    return 0;
}

问题 D: 开心的金明(单点1s,128M)

题目描述
金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。
更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。
今天一早金明就开始做预算,但是他想买的东西太多了,肯定会超过妈妈限定的N元。
于是,他把每件物品规定了一个重要度,分为5等:用整数1~5表示,第5等最重要。
他还从因特网上查到了每件物品的价格(都是整数元)。他希望在不超过N元(可以等于N元)的前提下,使每件物品的价格与重要度的乘积的总和最大。 

设第j件物品的价格为v[j],重要度为w[j],共选中了k件物品,编号依次为j1,j2,……,jk,
则所求的总和为: 

v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。(其中*为乘号) 

请你帮助金明设计一个满足要求的购物单。 


输入
 第1行,为两个正整数,用一个空格隔开: N m(其中N(<30000)表示总钱数,m(<25)为希望购买物品的个数。) 
 从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,每行有2个非负整数 v p 
(其中v表示该物品的价格(v<=10000),p表示该物品的重要度(1~5)) 

输出
输出文件只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<100000000)。 


样例输入
1000 5
800 2
400 5
300 5
400 3
200 2

样例输出
3900

整个题目散发着01背包的气息。但有我校大佬使用模拟A了这道题。。。

它就是01背包例题的一个变式,只不过原来模型里的价值变成了价格乘以重要度,费用就是上边的价格,背包容量是总钱数。

01背包:有一个容量为m的背包,有n个物品,每一个物品i的重量为w[i],价值为v[i]。
要求选择一些物品放入背包中,每种物品只能最多使用一次,使得在不超重的情况下让背包中所有物品价值总和最大。
正常向解法:设状态数组f[i][j]为把前i个物品放入一个容量为j的背包中所能获得的最大价值(以下同设),则状态转移方程为:

f[i][j] = max(f[i-1][j],f[i-1][j-w[i]]+v[i])

可优化至一维数组,令j从大到小枚举。

f[j] = max(f[j],f[j-w[i]]+v[i])

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#define maxn 233333
using namespace std;
int m, n;
int w[maxn];
int v[maxn];
int f[maxn];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> v[i] >> w[i];
        w[i] *= v[i];
    }
    for (int i = 1; i <= m; i++) {
        for (int j = n; j >= v[i]; j--)
            if (j >= v[i])
                f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
    cout << f[n];
//    system("pause");
    return 0;
}

-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。