Qjbtiger's Home
0%

7.20测试，7.21调试总结

Posted on Edited on In Views: Valine:

这一次测试，是COCI测试，成绩一般，但收获还是有的。

第1题 组队的数量（Timsko）

【题目】有N个女生，M个男生，每2个女生和1个男生组成一队，先要取走K个人当志愿者，问最多还能组多少队？

【分析】作为第一题，难度不大。首先我们不考虑当志愿者的情况，那么枚举一下最多能有多少组。对于剩下的人，全部去当志愿者。如果还有志愿者名额，那么，名额每自减3，组数减1，直到名额没有了。

【程序】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <fstream>
using namespace std;

ifstream fin("Timsko.in");
ofstream fout("Timsko.out");

int N,M,K,group;

int main() {
    fin >> N >> M >> K;

    for (; group<=M && group*2<=N; group++);//先枚举组数

    group--;//由于算多了一组，要自减一

    int left=(N+M)-3*group;//剩下
    K-=left;//减去剩下
    for (; K>0; K-=3,group--);//名额减3，组数减1

    fout << group << endl;
    return 0;
}

第2题 突击考试（Profesor）

【题目】有N组数，每组数有A，B两个数，A，B在[1..5]的范围内。当连续的L行都含有K这个数时，问L最大为多少，以及K。（当L相等，K取最小）

【分析】题目有些难以理解。这还是一道模拟题，开一个数组，枚举每一个数的大小（只有[1..5]），看看这个数在N组数中，连续的组数最大为多少。最后输出最大即可。

要注意，A[i]==B[i]的情况，不要叠加，而有重复。

【程序】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <fstream>
using namespace std;

ifstream fin("Profesor.in");
ofstream fout("Profesor.out");

#define maxn 100000+10
#define max_grade 5+5
#define oo 100000000

int N;
int A[maxn] , B[maxn];
int X[max_grade] , Y[max_grade];//X储存当前连续最大为多少，Y储存一直最大为多少

int main() {
    fin >> N;
    for (int i = 0; i != N; ++ i)
        fin >> A[i] >> B[i];

    X[A[0]] = Y[A[0]] = X[B[0]] = Y[B[0]] = 1;
    for (int i = 1; i != N; ++ i) {
        if (A[i] == A[i-1] || A[i] == B[i-1]) X[A[i]] ++;
        else X[A[i]] = 1;
        
        if (A[i] != B[i])
            if ((B[i] == A[i-1] || B[i] == B[i-1]) && A[i] != B[i])
                X[B[i]] ++;//要注意A[i]==B[i]的情况
            else X[B[i]] = 1;

        if (X[A[i]] > Y[A[i]]) Y[A[i]] = X[A[i]];

        if (X[B[i]] > Y[B[i]]) Y[B[i]] = X[B[i]];
    }

    int max_L=-oo,min_grade=oo;
    for (int grade = 1; grade <= 5; grade ++)
        if ((Y[grade] > max_L) || ((Y[grade] == max_L) && (grade < min_grade))) {
            max_L=Y[grade];
            min_grade=grade;
        }

    fout << max_L << ' ' << min_grade << endl;
    return 0;
}

第3题 幸运数字（Sretan）

【题目】我们认为只包含4和7的数字为幸运数字，比如4, 7, 44, 47, 74…。

现在对于给定的N，请你求出第N个幸运数字。

【分析】4和7，其实我们可以看成0和1。这题明显是找规律。我们先从特殊到一般：

7.20测试，7.21调试总结 - 邱俊斌 - 邱俊斌

第一列是二进制数，其实没什么关系，只是作为对照。

第二列是序号N。

第三列是实际的幸运数字。

第四列是’4’对应’0’，’7’对应’1’的情况

我们看第四列，以28为例，我们可以先确定28的长度。我们发现，[1..2]是一位，[3..6]是两位，[7..14]是三位，[15..30]是四位，以此类推。对于长度为k的情况下，它的范围就是[2k-1..2k+1-2]。这样，枚举k即可。

我们又发现，在[2k-1..2k+1-2]的范围内，前一半是以0开头，后一半以1开头，这样，我们就确定了头一位数字了。

去掉头一位数字，后面的数字就是子问题了。我们找规律，又发现，在[2k-1..2k+1-2]的范围内，前一半区域的子问题就是，N-2k-1；后一半区域的子问题就是，N-2k。

边界就是N为0和1的情况，单独列出即可。

【程序】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <fstream>
using namespace std;

ifstream fin("Sretan.in");
ofstream fout("Sretan.out");

#define maxl 1000000

char F[maxl];
int N , len;

void read() {
    fin >> N;
}

void work() {
    int tmp = N;
    for (; tmp > 2; ) {
        int P = 1;
        for (; ((P - 1) << 1) < tmp; P <<= 1);枚举P
        int tmp_P = P;
        int Q = (-- P) << 1;
        int tmp_Q = tmp_P << 1;//P为当前区域上边界，Q为当前区域下边界
        int mid = ((Q - P + 1) >> 1) + P;
        bool up_down = (tmp < mid);//求是在上区域还是在下区域
        if (up_down) F[++ len] = '4';
        else F[++ len] = '7';

        if (up_down) tmp -= (tmp_P >> 1);
        else tmp -= (tmp_Q >> 1);
    }

    if (tmp == 2) F[++ len] = '7';
    if (tmp == 1) F[++ len] = '4';
}

void write() {
    for (int i = 1; i <= len; i++)
        fout << F[i];
    fout << endl;
}

int main() {
    read();

    work();

    write();
    return 0;
}

第4题 分糖果（Ljutnja）

【题目】有N个小孩，有M颗糖。每个小孩有期望的糖果数a[i]，糖果不够分，每个小孩的生气指数为，他没有得到糖果数的平方。问最小生气指数之和。

【分析】要是生气指数和最小，那么他们的没有的到的糖唐数尽可能的平均。证明：

所以，糖果尽可能给需求量大的，那么，生气指数之和相对会更小。

7.20测试，7.21调试总结 - 邱俊斌 - 邱俊斌
我们先从大到小排序，枚举每一个数i，它与前一个数i+1有差距diff，若M>idiff，那么M自减idiff；若不够，那么，对于剩下的M，我们尽可能给前i名小孩M/i颗糖，剩下的M%i余数r，就给前r名小孩M/i+1颗糖，枚举剩下的每个孩子有多少颗糖，最后结算即可。

要注意，由于题目要求答案可能高达264-1，所以，需要用到unsigned long long

【程序】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <fstream>
#include <algorithm>
#include <math.h>
using namespace std;

ifstream fin("Ljutnja.in");
ofstream fout("Ljutnja.out");

#define maxn 100000+10

typedef unsigned long long ULL;//注意数据类型

int N,M;
ULL hope[maxn];
ULL sum;
void read() {
    fin >> M >> N;
    for (int i = 0; i != N; ++ i)
        fin >> hope[i];
}

bool cmp(int x,int y) {
    return x > y;
}

void work() {
    ULL tmp = M;
    sum = 0;

    for (int i = 0; i != N; ++ i) {
        ULL diff = hope[i] - hope[i+1];
        ULL cnt = i + 1;
        bool ok = (tmp >= cnt * diff);
        if (ok) tmp -= cnt * diff;//看看剩下的M颗糖是否够
        else {
            ULL P = hope[i] - (tmp / cnt);
            ULL rest = tmp % cnt;
            sum = (P - 1) * (P - 1) * rest + (cnt - rest) * P * P;//要注意，如P2要写成P*P，不要写成pow（P,2），因为会有精度误差
            for (int j = i + 1; j != N; ++ j)
                sum += hope[j]*hope[j];
            break;
        }
    }
}

void write() {
    fout << sum << endl;
}

int main() {
    read();

    sort(hope+0,hope+N,cmp);

    work();

    write();
    return 0;
}

第5题 编辑文本（Tabovi）

【题目】有N行字符，每行字符前有P[i]空格，我们想每行有K[i]个空格。现在我们可以任意选H行，每行前加一个空格或减少一个空格（算作一步）。问最少需要多少步？

【分析】其实就是有N个数（有正有负），通过如题目的操作，问最少需要多少步？

如何操作呢？其实，我们发现，对于这么一列数，我们找到

7.20测试，7.21调试总结 - 邱俊斌 - 邱俊斌

如图，一列数可以按正负，分成许多区域，找到这区域的最小值，每一个数同时减去这个最小值。那么这个区域就分成了两个部分，最小值那个数就变成了0。递归左边和右边的部分，再累加每一个最小值，即可。

要注意的是，当求负数区域时，是与求证正数区域，相反。

当然，如果不用递归，用一个栈也可以做。

而且，求这段区域的最小值（最大值），我们除了直接枚举，还可以用胜者树的办法，或是用RMQ的办法（会另外讲）。

【程序】

```c++
#include
using namespace std;

ifstream fin(“Tabovi.in”);
ofstream fout(“Tabovi.out”);

#define maxn 1000+10
#define oo 100000000

int start[maxn],end[maxn],move[maxn],n;
int ans;

void read() {
fin >> n;
for (int i = 0; i != n; ++ i)
fin >> start[i];

for (int i = 0; i != n; ++ i)
    fin >> end[i];

for (int i = 0; i != n; ++ i)
    move[i] = end[i] - start[i];

}

int get_min(int x, int y) {
int tmp = oo,pos = 0;

for (int k = x; k != y; ++ k)
    if (move[k] < tmp) {
        tmp = move[k];
        pos = k;
    }

return pos;

}

int solve1(int x, int y, int sub) {//sub储存当前区域每一个数已自减多少（无需真的枚举去减，只需用变量储存，计算是注意些，即可）
if ((y - x) == 1) return move[x] - sub;
if (x == y) return 0; //边界
int loca_min = get_min(x,y);//求最小
int tmp = move[loca_min] - sub;

return solve1(x,loca_min,tmp + sub) + solve1(loca_min+1,y,tmp + sub) + tmp;

}

int get_max(int x, int y) {
int tmp = -oo,pos = 0;

for (int k = x; k != y; ++ k)
    if (move[k] > tmp) {
        tmp = move[k];
        pos = k;
    }

return pos;

}

int solve2(int x, int y, int add) {
if ((y - x) == 1) return abs(move[x] + add);
if (x == y) return 0;
int loca_max = get_max(x,y);
int tmp = move[loca_max] + add;

return solve2(x,loca_max,abs(tmp - add)) + solve2(loca_max+1,y,abs(tmp - add)) + abs(tmp);

}

void write() {
fout << ans << endl;
}

int main() {
read();

int symbol = (move[0] > 0) ? 1 : 2;
if (move[0] == 0) symbol = 0;
int begin = 0;
for (int i = 0; i <= n; ++ i) {
    int symbol_new = (move[i] > 0) ? 1 : 2;

    if (move[i] == 0) symbol_new = 0;
    if (symbol != symbol_new) {//判断是否有正负交错
        if (move[begin] != 0) {
            if (symbol == 1)
                ans += solve1(begin,i,0);//正的情况
            else
                ans += solve2(begin,i,0);//负的情况
        }
        begin = i;
        symbol = symbol_new;//更替
    }
}

write();
return 0;

}

Thank you so much.