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!

沙茶的 代码

#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上有道题就是这样做?
水经验去

沙茶的 代码

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

#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

我が名は吹雪!