0%

7.20测试,7.21调试总结

这一次测试,是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.