解题笔记_ Noip2017 N校联考模拟赛 [题解] [懵逼]

NOIp前的第一场模拟赛, 回光返照

T1

懵逼的 题目

大意: 给定n个非负数, 找任意个数, 使他们的和可以被n整除
输出这些数的下标
时空: $O(n)$要求

扯淡的 题解

大概开考1h+的时候想出来的方法吧…
记一个前缀和fr[i] = (a[1] + a[2] + a[3] + ... + a[i]) % n
不难想出如果有两个前缀和相等, 那么后面的减去前面的, 得到的中间的数的和, 就可以被n整除
结了
那么为什么一定有解呢?
舒老师: 因为前缀和取模有n (0 到 n - 1)种取值, 而前缀和的个数有n + 1 (fr[0] 到 fr[n])个, 所以一定有两个值相等
结了(%%%舒老师rank1)

又及: 出题人写的SPJ出了问题…没有判断无输出的情况…结果不输出就能AC…
GoodGame
233333333333怼出题人3连
1x
2x
3x!

沙茶的 代码

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
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000000 + 5)
#define INF (1000000000)
#define LL long long
using namespace std;
LL n;
int vis[MAXN];
LL sum = 0;
inline LL mread();
void ret();
int main()
{
// freopen("set.in", "r", stdin);
// freopen("set.out", "w", stdout);
n = mread();
int srx;
for (int i = 1; i <= n; i++)
{
srx = mread();
srx %= n;
sum += srx;
sum %= n;
if (vis[sum])
{
printf("%d\n", i - vis[sum]);
for (int j = vis[sum] + 1; j <= i; j++)
{
printf("%d ", j);
}
ret();
}
else if (!sum)
{
printf("%d\n", i);
for (int j = 1; j <= i; j++)
{
printf("%d ", j);
}
ret();
}
vis[sum] = i;
}
puts("-1");
ret();
}
void ret()
{
fclose(stdin);
fclose(stdout);
exit(0);
}
inline LL mread()
{
LL re = 0;
char x = 0;
while (x < '0' || x > '9')
{
x = getchar();
}
while (x <= '9' && x >= '0')
{
re = (re << 1) + (re << 3) + x - '0';
x = getchar();
}
return re;
}

T2

懵逼的 题目

题目大意: 有n个数, 任意排列, 求去掉最少几个数可以让序列中没有两个相邻的两个相同的数
输出最小去掉的个数
时空: 依旧是O(n)时间, 但空间是毒瘤的4M

扯淡的 题解

考场上想到任何一个数的个数都不能大于(n >> 1) + 1, 然而并没有什么卯月, 写了个二分判断去掉的个数然后MLE了, 加之考场当时很吵(此处应该有HZC老师的: “你们知道什么是考试嘛”), 思考不能(借口)然后就爆零了…
正解是: 找个数大于(n >> 1) + 1的数, 然后统计这个数出现的次数, 减去(n >> 1) + 1即可
↑废话
那么这么找这个数呐?
这就需要智商了(所以我就没想出来)…
ID = 0, cnt = 0, 遇到一个数A[i], 如果cnt == 0: {ID = A[i];} 否则: {如果ID == A[i]: {cnt++} 否则: {cnt--}}
最后的ID就是要找的数
想一想为什么: 设我们已经找到了这个数, 那么这个数一定是s(这个数的个数) > n - s(n - s即为其它数的个数和) + 1, 而上面的代码保证了遇到两个不相等的数就让cnt0靠近, 所以如果最后cnt != 0, 那么这个ID就是要找的数(所有的与他不同的数都不能让他变为0)
听说BZOJ上有道题就是这样做?
水经验去

沙茶的 代码

这个题输入什么的略显鬼畜…但大体意思不变

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <map>
#define MAXN (50000000 + 5)
#define MAXM (1000 + 5)
#define MAXK (30 + 5)
#define INF (1 << 30)
#define MOD (10000007)
#define LL long long
using namespace std;
int n;
int m;
int k;
int ma[MOD];
int srx[MAXM];
int sry[MAXM];
int srz[MAXM];
int coun[MAXM];
int ans;
bool pd(int);
void ef();
int main()
{
freopen("read.in", "r", stdin);
freopen("read.out", "w", stdout);
cin >> m >> k;
for (int i = 1; i <= m; i++)
{
cin >> coun[i];
n += coun[i];
}
for (int i = 1; i <= m; i++)
{
cin >> srx[i];
}
for (int i = 1; i <= m; i++)
{
cin >> sry[i];
}
for (int i = 1; i <= m; i++)
{
cin >> srz[i];
}
int s = (1 << k) - 1;
for (int i = 1; i <= m; i++)
{
ma[srx[i]]++;
if (ma[srx[i]] > (n >> 1))
{
n--;
ans++;
}
LL last = srx[i];
for (int j = 1; j < coun[i]; j++)
{
last = (last * sry[i] + srz[i]) & s;
ma[last]++;
if (ma[last] > (n >> 1))
{
n--;
ans++;
}
}
}
cout << ans;
fclose(stdin);
fclose(stdout);
return 0;
}

/*
4 2
1 1 1 1
1 1 1 2
0 0 0 0
0 0 0 0
*/

T3

不可做

没看懂题解也没听懂学长讲的

又挖了个坑

DP神的良心题解

这里写图片描述

结了

听说好多学长和大佬萌都写挂了?
听说是在纠结T1到底可不可以选重复的元素(原题是选一个子集)?
然后我就混了个Rank4???
SMG????我就打了个T1啊 啊喂!
这辈子的RP都耗没了…

感觉还是需要看看DP + 开拓思维啊…

去食堂碰见Au爷居然吓得我没有去MOD感觉丢了五个亿

By 非洲人 Cansult

我が名は吹雪!