头像

Zlc晨鑫




离线:1天前


最近来访(107)
用户头像
Screaming
用户头像
yxc的小迷妹
用户头像
光風霽月
用户头像
_____Xyz__
用户头像
yxᴄ
用户头像
Moon_2
用户头像
18910310021
用户头像
云衣醉梦
用户头像
种花家的市长
用户头像
StarLi9ht
用户头像
heart
用户头像
月亮供电不足
用户头像
rfx
用户头像
不高兴的兽奶
用户头像
求求了不要WA
用户头像
人生如戏ba
用户头像
代码改变头发
用户头像
jixiaobai
用户头像
检控方没有异议
用户头像
秋天寒

活动打卡代码 AcWing 1291. 轻拍牛头

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int cnt[N], s[N];
int n, a[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i ++ ) cnt[a[i]] ++ ;

    for (int i = 1; i < N; i ++ )
        for (int j = i; j < N; j += i)
            s[j] += cnt[i];

    for (int i = 1; i <= n; i ++ )
        printf("%d\n", s[a[i]] - 1);

    return 0;
}



T1

如果 $sum[k]$是奇数,一定是最优解,因为 $w[k+1] \le w[k] \le w[k - 1] … w[1]$,替换任何一个数字,结果变成 $ans2 = sum[k] - w[i] + w[j] (i \in [1, k], j \in [k + 1, n])$,而因为 $w[i] \ge w[j]$,所以 $ans2 \le ans$,所以 $ans$ 此时一定是最优解。

如果 $sum[k]$是偶数,按照贪心的做法,一定是得到最优解的。

首先证明正确性:

设$a,b,c,d$分别是$[1,k]$中最小的奇数、偶数,$[k+1,n]$中最大的奇数、偶数。

因为偶数+奇数=奇数偶数+偶数=偶数,所以当且仅当在$[1,k],[k+1,n]$中存在一对奇偶性不同的数,才能使$ans$变成一个奇数,才有解。

因为最大的奇数一定是奇数……所以正确性得证。

接着证明最优性:

$ans2 = ans - t, t = w[j] - w[i]$。

容易发现 $t$随着$w[i]$的增大而减小,随着$w[j]$的增大而增大。

当$w[j]$最小,$w[i]$最大时,取得最大值。

而题目要求的就是最大值,最优性得证。

证毕。

T2

将题解的两个步骤统一起来:

首先将 $t$ 数组从大到小排序;
对于任何一个$t_i$,选择目前总和最小的一个序列,加入进去;
所有序列和的最大值就是答案(最多 $m$ 个序列)。

假设这么贪心是错误的,我们从前往后找到第一个错误的操作。

此时队列如下。

abc.png

一般的,设当前加入的$t[i]=x$,加入序列的长度是 $y$,其它任意一个序列上面最后加入的$t[j]=a$,剩下的长度是 $b$。

根据贪心,有 $x + y \ge a + b, b \ge y , x \ge a + b$。

因为假设贪心是错误的,所以正确的方法一定是错误的一步交换一下位置,上面的情况,交换之后$y + a \le b + x$,而 $b + x \ge x + y$,所以一定不会更优。

贪心就是正确的,大概理解吧……



活动打卡代码 AcWing 1290. 越狱

#include <cstdio>
#include <iostream>

using namespace std;

#define int long long

const int mod = 100003;

int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

signed main()
{
    int m, n;
    cin >> m >> n;
    int ans = qmi(m, n, mod) - m * qmi(m - 1, n - 1, mod);
    cout << (ans % mod + mod) % mod << endl;
    return 0;
}



#include <cstdio>
#include <iostream>

using namespace std;

#define int long long

const int mod = 200907;

int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

signed main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        int a, b, c, k;
        cin >> a >> b >> c >> k;
        if (b - a == c - b) cout << (a + (b - a) * (k - 1)) % mod << endl;
        else cout << a * qmi(b / a, k - 1, mod) % mod << endl;
    }
    return 0;
}


活动打卡代码 AcWing 197. 阶乘分解

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1000010;

int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] * i <= n; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    int n;
    cin >> n;
    get_primes(n);
    for (int i = 0; i < cnt; i ++ )
    {
        int s = 0, p = primes[i];
        for (int j = n; j; j /= p) s += j / p;
        printf("%d %d\n", p, s);
    }
    return 0;
}


活动打卡代码 AcWing 196. 质数距离

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

#define int long long

const int N = 1e6 + 10;

int primes[N], cnt;
bool st[N];

void init(int n)
{
    memset(st, 0, sizeof st);
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] * i <= n && j < cnt; j ++ ) 
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

signed main()
{
    int l, r;
    while (scanf("%lld%lld", &l, &r) == 2)
    {
        init(50000);
        memset(st, 0, sizeof st);
        for (int i = 0; i < cnt; i ++ )
        {
            int p = primes[i];
            for (int j = max((int)ceil(l / p) * p, 2 * p); j <= r; j += p)
                if (j >= l) st[j - l] = true;
        }

        cnt = 0;
        // 注意1不是质数
        for (int i = 0; i <= r - l; i ++ )
            if (!st[i] && i + l >= 2) primes[cnt ++ ] = i + l;

        if (cnt < 2) 
        {
            puts("There are no adjacent primes.");
            continue;
        }

        int p1, p2;
        p1 = p2 = 0;
        for (int i = 0; i + 1 < cnt; i ++ )
        {
            int v = primes[i + 1] - primes[i];
            if (v < primes[p1 + 1] - primes[p1]) p1 = i;
            if (v > primes[p2 + 1] - primes[p2]) p2 = i;
        }
        printf("%lld,%lld are closest, %lld,%lld are most distant.\n", primes[p1], primes[p1 + 1], primes[p2], primes[p2 + 1]);
    }
    return 0;
}



将x的质因子到x连一条边,相当于让图上的边的两个点染上不同颜色。

质数分成左集合,合数分到右集合,本题的图是一个二分图。

将质数染成1,合数染成2即可。

因为要求k最小,所以不能质数染成2,合数染成1。

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 100010;

int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] * i <= n; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    get_primes(n + 1);
    if (n <= 3) puts("1");
    else puts("2");
    for (int i = 2; i <= n + 1; i ++ )
        if (!st[i]) printf("1 ");
        else printf("2 ");
    return 0;
}


活动打卡代码 AcWing 1091. 理想的正方形

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1010;

int n, m, k;
int w[N][N], minv[N][N], maxv[N][N], buf[N];
int minx[N], maxx[N];
int q[N];

void get_min(int a[], int b[], int n)
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ )        
    {
        while (hh <= tt && q[hh] <= i - k) hh ++ ;
        while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;
        q[ ++ tt] = i;
        b[i] = a[q[hh]];
    }
}

void get_max(int a[], int b[], int n)
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ )        
    {
        while (hh <= tt && q[hh] <= i - k) hh ++ ;
        while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
        q[ ++ tt] = i;
        b[i] = a[q[hh]];
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &w[i][j]);

    for (int i = 1; i <= n; i ++ )
    {
        get_min(w[i], minv[i], m);
        get_max(w[i], maxv[i], m);
    }

    int ans = 2e9;
    // 注意k之前的数都是没有意义的,它们并不是窗口内真实的最大最小值
    // 统计了会WA,因为可能差值会更小
    for (int j = k; j <= m; j ++ )
    {
        for (int i = 1; i <= n; i ++ ) buf[i] = minv[i][j];
        get_min(buf, minx, n);
        for (int i = 1; i <= n; i ++ ) buf[i] = maxv[i][j];
        get_max(buf, maxx, n);
        for (int i = k; i <= n; i ++ )
            ans = min(ans, maxx[i] - minx[i]);
    }

    printf("%d\n", ans);

    return 0;
}


活动打卡代码 AcWing 1087. 修剪草坪

常规解法:

#include <cstdio>
#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

LL s[N];
int e[N], n, m;
int q[N];
LL f[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &e[i]);
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + e[i];

    int hh = 0, tt = -1;
    f[0] = 0;
    f[1] = s[1];
    tt = 0, q[0] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (q[hh] <= i - m) hh ++ ;
        while (hh <= tt && -s[q[tt]-1]+f[q[tt]-2]<=-s[i-1]+f[i-2]) tt -- ;
        q[ ++ tt] = i;
        f[i] = -s[q[hh] - 1] + f[q[hh] - 2] + s[i];
        f[i] = max(f[i], f[i - 1]);
    }

    printf("%lld\n", f[n]);

    return 0;
}
/*
考虑空位置,选择不连续超过k个奶牛工作的最大值,等价于不选择连续超过k个的奶牛不工作的最小值
和烽火传递一样了
*/

#include <cstdio>
#include <iostream>

using namespace std;

#define int long long

const int N = 100010;

int n, k;
int e[N], f[N];
int q[N];

signed main()
{
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i ++ ) scanf("%lld", &e[i]);

    int hh = 0, tt = -1;
    q[ ++ tt] = 0;
    for (int i = 1; i <= n; i ++ )
    {
        // [i - k - 1, i - 1]
        while (hh <= tt && q[hh] < i - k - 1) hh ++ ;
        f[i] = f[q[hh]] + e[i];
        while (hh <= tt && f[q[tt]] >= f[i]) tt -- ;
        q[ ++ tt] = i;
    }

    int res = 9e18;
    for (int i = n - k; i <= n; i ++ )
        res = min(res, f[i]);
    res = -res;
    for (int i = 1; i <= n; i ++ )
        res += e[i];
    printf("%lld\n", res);

    return 0;
}


活动打卡代码 AcWing 1090. 绿色通道

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 50010;

int a[N], n, t, f[N];

bool check(int len)
{
    static int q[N];
    int hh = 0, tt = -1;
    q[ ++ tt] = 0;

    for (int i = 1; i <= n; i ++ )
    {
        if (q[hh] < i - len) hh ++ ;
        f[i] = f[q[hh]] + a[i];
        while (hh <= tt && f[q[tt]] >= f[i]) tt -- ;
        q[ ++ tt] = i;
    }

    // 注意:只要f[n-len+1,n]之间有一个满足要求即可
    for (int i = n - len + 1; i <= n; i ++ )
        if (f[i] <= t) return true;
    return false;
}

int main()
{
    scanf("%d%d", &n, &t);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    int l = 0, r = n;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid + 1)) r = mid;
        else l = mid + 1;
    }

    printf("%d\n", r);

    return 0;
} 

边界!!!

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 50010;

int n, t;
int a[N], q[N], f[N];

bool check(int mid)
{
    memset(f, 0, sizeof f);
    int hh = 0, tt = -1;
    q[ ++ tt] = 0;
    for (int i = 1; i <= n; i ++ )
    {
        // [i-1-mid, i-1]
        // 空着的长度最大是mid
        while (hh <= tt && q[hh] < i - mid - 1) hh ++ ;
        f[i] = f[q[hh]] + a[i];
        while (hh <= tt && f[q[tt]] >= f[i]) tt -- ;
        q[ ++ tt] = i;
    }

    int res = 2e9;
    for (int i = n - mid; i <= n; i ++ )
        res = min(res, f[i]);

    return res <= t;
}

int main()
{
    scanf("%d%d", &n, &t);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    int l = 0, r = n; // 可能全部都可以写完
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", r);
    return 0;
}