2022-10-3总结

分组

将字符串反转一下，后缀就变成前缀了，然后就可以扔到 trie 树上了，考虑统计子树和，我们就可以知道某一个前缀可以匹配多少个字符串了，然后贪心一手，尽量能匹配的前缀都匹配上就行了。

#include <cstdio>
#include <iostream>
using namespace std;
 
typedef long long ll;
const int N = 1e6+10;
 
namespace Prime {
    bool vis[N];
    int prime[N], pcnt;
    int d[N];
    void getprime(int n)
    {
        for(int i = 2; i <= n; i++)
        {
            if(!vis[i]) prime[++pcnt] = i, d[i] = i;
            for(int j = 1; j <= pcnt and i*prime[j] <= n; j++)
            {
                vis[i*prime[j]] = true;
                d[i*prime[j]] = prime[j];
                if(i%prime[j] == 0) break;
            }
        }
    }
} using namespace Prime;
 
int n;
ll val[N];
ll sum[N];
 
int main()
{
    read(n);
    Prime::getprime(n);
    for(int i = 1; i <= n; i++)
        read(val[i]);
    for(int i = 2; i <= n; i++)
    {
        if(i&1)
        {
            sum[i-d[i]+1] += val[i];
            sum[i+d[i]] -= val[i];
        }
        else
        {
            sum[i] += val[i];
            sum[i+1] -= val[i];
        }
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++)
    {
        sum[i] += sum[i-1];
        ans = max(ans, sum[i]);
    }
    print(ans+val[1]);
}

Non-coprime DAG

ARC136E

考虑按奇偶分类，我们可以通过 $x$ 的最小质因子 $d(x)$ 来知道 $x$ 能到达哪些数，然后就做完了

#include <cstdio>
#include <iostream>
using namespace std;
 
typedef long long ll;
const int N = 1e6+10;
 
namespace Prime {
    bool vis[N];
    int prime[N], pcnt;
    int d[N];
    void getprime(int n)
    {
        for(int i = 2; i <= n; i++)
        {
            if(!vis[i]) prime[++pcnt] = i, d[i] = i;
            for(int j = 1; j <= pcnt and i*prime[j] <= n; j++)
            {
                vis[i*prime[j]] = true;
                d[i*prime[j]] = prime[j];
                if(i%prime[j] == 0) break;
            }
        }
    }
} using namespace Prime;
 
int n;
ll val[N];
ll sum[N];
 
int main()
{
    read(n);
    Prime::getprime(n);
    for(int i = 1; i <= n; i++)
        read(val[i]);
    for(int i = 2; i <= n; i++)
    {
        if(i&1)
        {
            sum[i-d[i]+1] += val[i];
            sum[i+d[i]] -= val[i];
        }
        else
        {
            sum[i] += val[i];
            sum[i+1] -= val[i];
        }
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++)
    {
        sum[i] += sum[i-1];
        ans = max(ans, sum[i]);
    }
    print(ans+val[1]);
}

T3是第十一分块，打死我我都不会