_WA自动机的blog

过期高中生。

Goodbye2021题解

发表于 阅读次数： Valine：

简简单单4篇题解，这场打得实在不好。

C

题意

定义一个数组是“高明的”，当且仅当对于\(\forall 1\le l\le r \le n\)，有\(a_l + ... +a_r=\frac{1}{2}(r-l+1)(a_l+a_r)\).给定一个整数序列A，求至少修改多少个数（可以修改成任意实数），可以把A变成“高明的”序列。

\(n\le 70\)

题解

序列的和=（首项+末项）*项数/2，容易（？想到等差数列。好吧，除了我都想到了，不知道我怎么想的。。 考虑三个数的情况，不难看出一定是等差数列。根据题意得，任取3个连续的数都是等差数列，则A修改后必定为等差数列。n的范围很小，所以暴力枚举哪两个数不变，扫一遍看看改几个就行了。

代码

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
#include <cstdio>
#include <algorithm>
#include <cmath>

using std::abs;
using std::min;
using std::max;

const int N=73;
const int S=410;
const int delta=203;
const double eps=1e-3;

int a[N];

int f[N][N][S];

bool equal(double x,double y){if (abs(x-y)<=eps) return true;return false;}

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int n;
        scanf("%d",&n);
        for (int i=1;i<=n;++i)
            scanf("%d",a+i);
        int ans=max(n-2,0);
        for (int i=1;i<=n;++i)
            for (int j=i+1;j<=n;++j)
            {
                double d=((double)a[j]-a[i])/(j-i);
                int cnt=0;
                for (int k=1;k<=n;++k)
                    if (!equal(a[i]-(i-k)*d,a[k])) ++cnt;
                ans=min(ans,cnt);
            }
        printf("%d\n",ans);
    }
}

D

题意

给定一个整数序列A和一个整数x，要求选出最多的元素，使得所有平均数小于x且长度不小于2的区间，至少有一个数没被选中。问最多选出几个元素。

题解

把序列整体减去x，则平均数小于x对应和为负数。要保证不选出连续的和为负数的区间，只需要不选出长度为2和3的负数区间就可以了。所以可以dp，记录最近的3个数有没有选过即可。

代码

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
#include <cstdio>
#include <algorithm>
#include <cstring>

using std::max;

const int N=5e4+1000;

int a[N];
int f[N][2][2][2];

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int n;
        scanf("%d",&n);
        for (int i=1;i<=n;++i)
            scanf("%d",a+i);
        int x;
        scanf("%d",&x);
        for (int i=1;i<=n;++i)
            a[i]-=x;
        memset(f,0,sizeof(f));
        for (int i=1;i<=n;++i)
        {
            f[i][0][0][0]=max(f[i-1][1][0][0],f[i-1][0][0][0]);
            f[i][0][0][1]=max(f[i-1][1][0][0],f[i-1][0][0][0])+1;
            f[i][0][1][0]=max(f[i-1][1][0][1],f[i-1][0][0][1]);
            f[i][0][1][1]=0;
            if (a[i-1]+a[i]>=0) f[i][0][1][1]=max(f[i-1][0][0][1],f[i-1][1][0][1])+1;
            f[i][1][0][0]=max(f[i-1][0][1][0],f[i-1][1][1][0]);
            f[i][1][0][1]=max(f[i-1][0][1][0],f[i-1][1][1][0])+1;
            f[i][1][1][0]=max(f[i-1][0][1][1],f[i-1][1][1][1]);
            f[i][1][1][1]=0;
            if (i>2 && a[i-2]+a[i-1]+a[i]>=0 && a[i-1]+a[i]>=0) f[i][1][1][1]=max(f[i-1][0][1][1],f[i-1][1][1][1])+1;
        }
        int ans=0;
        for (int i=1;i<=n;++i)
            for (int j=0;j<=1;++j)
                for (int k=0;k<=1;++k)
                    for (int w=0;w<=1;++w)
                        ans=max(ans,f[i][j][k][w]);
        printf("%d\n",ans);
    }
}