北京理工大学2018级6月月赛题解

A. Radishes

如果 $n\leq 40$ ，我们可以进行暴力求解，复杂度 $O(n^2)$

然而如果 $n>40$ ，根据抽屉原理，必定至少有一个 $l_i$ 出现了两边，此时 $|l_i-l_j|=0,\ d=0$ 。我们只要统计每一个数前两次的位置，将最多40个答案进行排序，即可。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int w[100005],l[100005];
int main()
{
    int n;
    scanf("%d",&n);
    for (int i = 1; i <= n; i++) scanf("%d%d",&l[i],&w[i]);
    if (n > 40)
    {
        bool flag = true;
        for (int i = 1; i <= n && flag; i++)
            for (int j = i + 1; j <= n && flag; j++)
                if (l[i] == l[j])
                {
                    printf("%d %d\n",i,j);
                    flag = false; break;
                }
        return 0;
    }
    double minn = 1e200;
    int x1 = 0, x2 = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1 + i; j <= n; j++)
        {
            double tmp = max(1.0 * w[i] / w[j], 1.0 * w[j] / w[i]) * abs(l[i] - l[j]);
            if (tmp < minn)
            {
                minn = tmp;
                x1 = i; x2 = j;
            }
        }
    printf("%d %d\n",x1,x2);
    return 0;
}

B. Visual Cube

~~全场最简单？~~

首先算出来整个图形的大小，用字符串数组存图，先全部初始化为.，然后一条条边进行绘制。

#include <bits/stdc++.h>
using namespace std;

char s[1005][1005];
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        int len=b*2+2*a+1;
        int height=2*b+2*c+1;
        memset(s,'.',sizeof(s));
        int now = -1;
        for (int i=1;i<=b;i++)
        {
            int nowl=2 * i - 1;
            now++;
            for (int j=1;j<=a;j++)
            {
                s[nowl][now+2*j-1]='+';
                s[nowl][now+2*j]='-';
            }
            s[nowl][now+2*a+1]='+';
            for (int j=1;j<=2*c;j++)
                s[2*i-1+j][now + 1]='|';
            nowl++; now++;
            for (int j=1;j<=a;j++)
            {
                s[nowl][now+2*j-1]='\\';
            }
            s[nowl][now+2*a+1]='\\';
        }
        int nowl=2*b;
        now++;
        for (int i=1;i<=c+1;i++)
        {
            nowl++;
            for (int j=1;j<=a;j++)
            {
                s[nowl][now + 2*j-1]='+';
                s[nowl][now + 2*j]='-';
            }
            s[nowl][now + 2*a+1]='+';
            int nowx=nowl,nowy=now + 1;
            for (int i=1;i<=2*b;i++)
            {
                nowx--; nowy--;
                if (s[nowx][nowy]=='.')
                    s[nowx][nowy]='\\';
                if (s[nowx][nowy]=='|') s[nowx][nowy]='+';
            }
            if (i==c+1) break;
            nowl++;
            for (int j=1;j<=a;j++)
            {
                s[nowl][now + 2*j-1]='|';
            }
            s[nowl][now + 2*a+1]='|';
        }
        for (int i=1;i<=height;i++)
        {
            for (int j=1;j<=len;j++) putchar(s[i][j]);
            putchar('\n');
        }
    }
    return 0;
}

C. Mr.Liang's Expression

dfs~注意前导0

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <queue>
#include <stack>
#include <functional>
#include <map>
#include <set>
#include <bitset>
#include <ctime>
#include <complex>

const int INF = 0x3f3f3f3f;
const long long INFLL = 0x3f3f3f3f3f3f3f3fll;
#define memset0(x) memset(x, 0, sizeof(x))
#define memsetM1(x) memset(x, -1, sizeof(x))
#define memsetINF(x) memset(x, INF, sizeof(x))

using namespace std;

long long ans;
double num;
char str[15];
int ops[15];
int rk[5] = { 3, 1, 1, 2, 2 };

int opCmp(int a, int b)
{
    return rk[a] - rk[b];
}

void dfs(int i = 0, int op = 0)
{
    ops[i] = op;


    if (!str[i])
    {
        stack<double> numStack;
        stack<int> opStack;

        /*for (int j = 1; j < i; j++)
        {
            cout << ops[j] << " ";
        }
        cout << endl;*/

        numStack.push(str[0] - '0');
        for (int j = 1; j < i; j++)
        {
            int dig = str[j] - '0';

            if (ops[j] == 0)
            {
                numStack.push(dig);

                double num2 = numStack.top();
                numStack.pop();
                double num1 = numStack.top();
                numStack.pop();

                numStack.push(num1 * 10 + num2);
            }
            else
            {
                while (!opStack.empty() && opCmp(opStack.top(), ops[j]) > 0)
                {
                    double num2 = numStack.top();
                    numStack.pop();
                    double num1 = numStack.top();
                    numStack.pop();
                    switch (opStack.top())
                    {
                    case 0:
                        num1 = num1 * 10 + num2;
                        break;
                    case 1:
                        num1 = num1 + num2;
                        break;
                    case 2:
                        num1 = num1 - num2;
                        break;
                    case 3:
                        num1 = num1 * num2;
                        break;
                    }
                    numStack.push(num1);

                    opStack.pop();
                }
                opStack.push(ops[j]);
                numStack.push(dig);
            }

        }
        while (!opStack.empty())
        {
            int cOp = opStack.top();
            opStack.pop();
            double num2 = numStack.top();
            numStack.pop();
            double num1 = numStack.top();
            numStack.pop();
            switch (cOp)
            {
            case 0:
                num1 = num1 * 10 + num2;
                break;
            case 1:
                num1 = num1 + num2;
                break;
            case 2:
                num1 = num1 - num2;
                break;
            case 3:
                num1 = num1 * num2;
                break;
            }
            numStack.push(num1);
        }
        //cout << numStack.top() << endl;
        if (abs(numStack.top() - num) < 1e-6)
        {
            ans++;
        }
        numStack.pop();
        return;
    }
    if (i >= 1 && op == 0)
    {
        if (str[i - 1] == '0' && (i == 1 || ops[i - 1] != 0))
        {
            return;
        }
    }

    int dig = str[i] - '0';
    if (!str[i + 1])
    {
        dfs(i + 1, 0);
    }
    else
    {
        for (int j = 0; j < 4; j++)
        {
            dfs(i + 1, j);
        }
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
    int startTime = clock();
#endif
    cin >> str >> num;
    dfs();
    cout << ans << endl;


#ifndef ONLINE_JUDGE
    printf("Time = %dms\n", clock() - startTime);
#endif
    return 0;
}

D. Xiao Ming's String

首先如果一个字母的出现次数 $>\frac{|S|}{2}+1$ ，显然不能，则输出NO。

否则使用优先队列，每次取前两个元素进行交叉。

// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
#define LOCAL
const int maxn = 1e6 + 7;
struct alpha{
    int cnt;
    char c;
    alpha(){}
    alpha(int _cnt, char _c){
        cnt = _cnt;
        c = _c;
    }
    bool operator < (const alpha &other) const{
        return cnt < other.cnt;
    }
};

int main(int argc, char * argv[]) 
{
    string s, ans;
    cin >> s;
    int mark[maxn];
    priority_queue<alpha> q;
    bool is_ok = true;
    memset(mark, 0, sizeof(mark));
    for (int i = 0; i < s.size(); i++){
        mark[s[i] - 'a']++;
    }
    for (int i = 0; i < 26; i++){
        if (mark[i]){
            q.push(alpha(mark[i], char(i + 'a')));
        }
    }
    while (!q.empty()){
        alpha a = q.top();
        q.pop();
        if(a.cnt == 0){
            break;
        }
        ans.push_back(char(a.c));
        a.cnt--;

        alpha b = q.top();
        q.pop();
        if (b.cnt == 0){
            break;
        }
        ans.push_back(char(b.c));
        b.cnt--;
        q.push(a);
        q.push(b);
    }
    for (int i = 1; i < ans.size(); i++){
        if (ans[i] == ans[i - 1]){
            is_ok = false;
            break;
        }
    }
    if (is_ok && ans.size() == s.size()){
        cout << ans << endl;
    }
    else{
        cout << "NO" << endl;
    }
    return 0;
}

E. Mr.Liang's Sequence Problem(I)

找找因数，推推式子，注意使用long long，就完事了~

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        long long N;
        scanf("%lld",&N);
        long long count = 1, sub = sqrt(2 * N);
        for(long long k = 2; k <= sub; k++) {
            if ((N - (k * (k - 1) / 2)) % k == 0) count++;
        }
        printf("%lld\n",count);
    }
    return 0;
}

F. Mr.Liang's Sequence Problem(II)

This IS a template problem for ~~segment tree~~ CDQ.

Solution A: CDQ

假设: $a_x$ 为原数组第 $x$ 项, 前缀和 ${\rm sum}_x=\sum\limits_{i=1}^x a_i$ , 差分 ${\rm d}_x=a_x-a_{x-1}\quad(a_0=0)$

区间查询 $[l,r]$ 的和, 实际上可以拆分为 $2$ 个前缀和的差 $({\rm sum}_r-{\rm sum}_{l-1})$

区间修改 $[l,r]$ 的值, 实际上可以表示为 $2$ 个差分数组的变化 ${\rm d}_l+=v, {\rm d}_{r+1}-=v$

考虑差分数组 ${\rm d}$ 对前缀和数组第 $n$ 项 ${\rm sum}_n$ 的影响

${\rm sum}_n=\sum\limits_{i=1}^na_i=\sum\limits_{i=1}^n\sum\limits_{j=1}^i{\rm d}_j=\sum\limits_{i=1}^n(n+1-i)\cdotp {\rm d}_i=(n+1)\sum\limits\limits_{i=1}^n{\rm d}_i-\sum\limits_{i=1}^ni\cdotp {\rm d}_i$

所以只需要维护好所有 $i(1\le i\le n)$ 的 ${\rm d}_i$ 和 $i\cdotp {\rm d}_i$ 的和, 便可以 $O(1)$ 的求出 ${\rm sum}_n$

所以按照 $\rm cdq$ 分治的经典套路, 第一维对时间分治, 第二维按照修改/查询的位置(拆分为 $2$ 个单点修改/查询)进行排序, 考虑分治的左边对右边影响的时候按照上面的做法便可以 $O(1)$ 的进行修改/查询, 复杂度: $O(n\log n)$

#include<bits/stdc++.h>
#define fi first
#define sf scanf
#define se second
#define pf printf
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(x,y) memset((x),(y),sizeof(x))
#define fup(i,x,y) for(int i=(x);i<=(y);++i)
#define fdn(i,x,y) for(int i=(x);i>=(y);--i)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
using namespace std;

const int __=4e5+5;

struct node
{
    int id;ull p,v;
}a[__],t[__];

ull ans[__];

void cdq(int l,int r)
{
    if(l==r)return;
    int m=(l+r)>>1;
    cdq(l,m),cdq(m+1,r);
    ull sum[2]={0};int x,y,z=l;
    for(x=l,y=m+1;y<=r;++y)
    {
        for(;x<=m && a[x].p<=a[y].p;t[z++]=a[x++])
            if(!a[x].id)
            {
                sum[0]=sum[0]+a[x].v;
                sum[1]=sum[1]+a[x].v*a[x].p;
            }
        if(a[y].id)
            ans[a[y].id]+=a[y].v*((a[y].p+1)*sum[0]-sum[1]);
        t[z++]=a[y];
    }
    for(int i=x;i<=m;++i)t[z++]=a[i];
    fup(i,l,r)a[i]=t[i];
}

int main()
{
    ll n;int q;sf("%lld%d",&n,&q);
    int idx=0,qdx=0;
    while(q--)
    {
        int op;ull l,r;
        sf("%d%llu%llu",&op,&l,&r);
        if(op==1)
        {
            ull v;sf("%llu",&v);
            a[++idx]={0,l,v};
            a[++idx]={0,r+1,-v};
        }
        else
        {
            ++qdx;
            a[++idx]={qdx,r,1};
            a[++idx]={qdx,l-1,-1ull};
        }
    }
    cdq(1,idx);
    fup(i,1,qdx)
        pf("%llu\n",ans[i]);
    return 0;
}

Solution B: Segment Tree

当然良心的懋懋把这题实现开到了1.5s，线段树可以通过

离散化后线段树, 注意线段树离散化后是 $4\times 10^5$ 个点(每个线段包含 $2$ 个端点)

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5+5;
typedef long long ll;
int Case = 1;
vector<unsigned long long>ve;
struct node{
    int op;
    long long l, r;
    unsigned long long val;
}Q[maxn];
struct point{
    int l, r;
    unsigned long long len;
    unsigned long long sum;
    unsigned long long lazy;
    int mid() {
        return (l+r)/2;
    }
}tr[maxn<<2];
void pushup(int rt) {
    tr[rt].len = tr[rt<<1].len + tr[rt<<1|1].len;
    tr[rt].sum = tr[rt<<1].sum + tr[rt<<1|1].sum;
}
void build(int rt, int l, int r) {
    tr[rt].l = l;tr[rt].r = r;
    if(l == r) {
        tr[rt].len = ve[l]-ve[l-1];
        return;
    }
    int mid = tr[rt].mid();
    build(rt<<1, l, mid);
    build(rt<<1|1, mid+1, r);
    pushup(rt);
}
void pushdown(int rt) {
    if(tr[rt].lazy) {
        unsigned long long x = tr[rt].lazy;
        tr[rt<<1].lazy += x;
        tr[rt<<1|1].lazy += x;
        tr[rt<<1].sum += x*tr[rt<<1].len;
        tr[rt<<1|1].sum += x*tr[rt<<1|1].len;
        tr[rt].lazy = 0;
    }
}
void update(int rt, int l, int r, unsigned long long val) {
    //cout<<l<<" "<<r<<endl;
    if(tr[rt].l == l && tr[rt]. r == r) {
        tr[rt].lazy += val;
        tr[rt].sum += val*tr[rt].len;
        return;
    }
    pushdown(rt);
    int mid = tr[rt].mid();
    if(r <= mid) update(rt<<1, l, r, val);
    else if(l > mid) update(rt<<1|1, l, r, val);
    else {
        update(rt<<1, l, mid, val);
        update(rt<<1|1, mid+1, r, val);
    }
    pushup(rt);
}
unsigned long long query(int rt, int l, int r) {
    //cout<<l<<" "<<r<<endl;
    if(tr[rt].l == l && tr[rt].r == r) {
        return tr[rt].sum;
    }
    pushdown(rt);
    int mid = tr[rt].mid();
    if (r <= mid)
      return query(rt << 1, l, r);
    else if (l > mid)
      return query(rt << 1|1, l, r);
    else
      return query(rt << 1, l, mid) + query(rt << 1|1, mid+1, r);
}
int getid(long long x) {
    return lower_bound(ve.begin(), ve.end(), x)-ve.begin()+1;
}
void solve() {
    //freopen("in.txt", "r", stdin);
    long long n;int q;
    scanf("%lld%d", &n, &q);
    for(int i = 1; i <= q; i++) {
        scanf("%d", &Q[i].op);
        if(Q[i].op == 1) {
            scanf("%lld%lld%llu", &Q[i].l, &Q[i].r, &Q[i].val);
        }
        else scanf("%lld%lld", &Q[i].l, &Q[i].r);
        Q[i].r++;
        ve.push_back(Q[i].l);
        ve.push_back(Q[i].r);
    }
    sort(ve.begin(), ve.end());
    ve.erase(unique(ve.begin(), ve.end()), ve.end());
    int len = ve.size();
    build(1, 1, len-1);
    for(int i = 1; i <= q; i++) {
        long long l = Q[i].l, r = Q[i].r;
        int op = Q[i].op;
        if(op == 1) update(1, getid(l), getid(r)-1, Q[i].val);
        else
          printf("%llu\n", query(1, getid(l), getid(r)-1));
    }
    return;
}
int main() {
    //g++ -std=c++11 -o2 1.cpp -o f && ./f < in.txt
    //ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt","w",stdout);
#endif
while(Case--) {
    solve();
    }
return 0;
}

G. q_Wq's Dating

显然要求两个人手上的串一样也就是这个串是回文串

树上的回文子串查询问题无法使用类似于 Mancher 的算法解决。

考虑哈希的解法。首先假定节点 $1$ 为根，将无根树转换为有根树。对于树上每个节点，预处理维护两个哈希值： $HashUp(i)$ 表示从节点 $i$ 到节点 $1$ 的路径上的字母序列的哈希值， $HashDown(i)$ 表示从节点 $1$ 到节点 $i$ 的路径上的字母序列的哈希值。则树上任意一有向简单路的哈希值均可计算。处理查询时，只需要检查从 $u$ 到 $v$ 的哈希值是否与从 $v$ 到 $u$ 的哈希值相同即可。

#include <bits/stdc++.h>
using namespace std;

const int MAXN=400005;
const int mod=998244353;
struct node{
    int id;
    long long pre,en;
    int prelen,enlen;
    vector<int> G;
}mapp[MAXN];
char s[MAXN];
int degree[MAXN];
long long pp[MAXN],pq[MAXN];
int depth[MAXN];
int parent[MAXN][25];

void dfs(int x, int y)
{
    depth[x] = depth[y] + 1;
    parent[x][0] = y;
    for (auto &i: mapp[x].G)
        if (i != y) dfs(i, x);
}
void build(int root, int n)
{
    dfs(root, 0);
    for (int i = 1; i <= 20; i++)
        for (int j = 1; j <= n; j++)
            parent[j][i] = parent[parent[j][i - 1]][i - 1];
}
int lca(int u, int v)
{
    for (int i = 20; i >= 0; i--)
    {
        if (depth[parent[u][i]] >= depth[v])
            u = parent[u][i];
        if (depth[parent[v][i]] >= depth[u])
            v = parent[v][i];
    }
    for (int i = 20; i >= 0; i--)
        if (parent[u][i] != parent[v][i])
        {
            u = parent[u][i];
            v = parent[v][i];
        }
    if (u != v)
    {
        u = parent[u][0];
        v = parent[v][0];
    }
    return u;
}
void dfs1(int now,int last)
{
    mapp[now].pre=(mapp[last].pre*1001+s[now])%mod;
    mapp[now].prelen=mapp[last].prelen+1;
    for (auto &i:mapp[now].G)
        if (i!=last)
            dfs1(i,now);
}
long long qpow(long long base, long long index) {
    long long ans = 1;
    while (index) {
        if (index & 1)
            ans = ans * base % mod;
        base = base * base % mod;
        index >>= 1;
    }
    return ans;
}
void dfs2(int now,int last)
{
    if (now==1)
    {
        mapp[1].en=s[1];
        mapp[1].enlen=1;
        return;
    }
    for (auto &i:mapp[now].G)
        if (i!=last&&mapp[i].prelen<mapp[now].prelen)
        {
            dfs2(i,now);
            mapp[now].enlen=mapp[i].enlen+1;
            mapp[now].en=(mapp[i].en+s[now]*pp[mapp[i].enlen])%mod;
        }
}
inline long long gethash(int u,int v)
{
    int t=lca(u,v);
    long long tmp1=((mapp[u].en-mapp[t].en)%mod+mod)%mod*pq[mapp[t].enlen]%mod;
    long long tmp2=((mapp[v].pre-mapp[t].pre*pp[mapp[v].prelen-mapp[t].prelen]%mod)%mod+mod)%mod;
    long long ans=((tmp1*1001+s[t])%mod*pp[mapp[v].prelen-mapp[t].prelen]%mod+tmp2)%mod;
    //printf("%d %d %d %lld %lld %lld\n",u,v,t,tmp1,tmp2,ans);
    return ans;
}
int main()
{
    mapp[1].pre=mapp[1].en=mapp[1].prelen=mapp[1].enlen=0;
    int n;
    scanf("%d",&n);
    pp[0]=1; pp[1]=1001;
    for (int i=2;i<=n;i++) pp[i]=pp[i-1]*1001%mod;
    pq[0]=1; pq[1]=qpow(1001,mod-2);
    for (int i=2;i<=n;i++) pq[i]=pq[i-1]*pq[1]%mod;
    scanf("%s",s+1);
    for (int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        mapp[u].G.emplace_back(v);
        mapp[v].G.emplace_back(u);
        degree[u]++; degree[v]++;
    }
    build(1,n);
    dfs1(1,0);
    for (int i=2;i<=n;i++)
        if (degree[i]==1)
            dfs2(i,0);
    int Q;
    scanf("%d",&Q);
    while (Q--)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        if (gethash(u,v)==gethash(v,u))
            printf("Happy!\n");
        else printf("555\n");
    }
    return 0;
}

H. Mr.Liang's Sequence Problem(III)

不难打表答案就是 $(\frac{n}{2}+1)$

在不打表( $T=1$ )之前，这题是这样做的：

定义: $f(n)$ 为 $\lfloor \frac{n}{1}\rfloor,\lfloor \frac{n}{2}\rfloor,\cdots,\lfloor \frac{n}{n}\rfloor$ 中不同数字的个数, 那么有一个比较经典的结论: $f(n)=2\cdotp \lfloor \sqrt n\rfloor-\Big[\lfloor \sqrt n\rfloor\cdotp(\lfloor \sqrt n\rfloor+1)\gt n\Big]$

可以观察到: 若 $1\le x\le y$ , 那么 $f(x)\le f(y)$ , 因此 $f(n)$ 关于 $n$ 满足单调性, 所以可以进行二分, 找到 $f(n)=m$ 的最小值 $l$ 以及 $f(n)=m+1$ 的最小值 $r$ , 答案就是: $(r-l)$

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int T;
    scanf("%d",&T);
    while (T--){
        long long x;
        scanf("%lld",&x);
        printf("%lld\n",x / 2 + 1);
    }
    return 0;
}

I. SuPer Fast Algorithm

不难发现，这是一个SPFA的代码，需要你hack它，也就是你要使得他TLE。

打开百度
搜索SPFA怎么卡

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <complex>
#include <random>
#include <stack>
#include <time.h>
#define SET0(X) memset(X,0,sizeof(X));
#define SET_1(X) memset(X,-1,sizeof(X));
#define RAND(a,b) ((rand() % (b-a+1))+ a)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct edge{int u,v,w;};
vector<edge>v;


int id[20][10010],n=10,cnt,m=100000/n,a[1000000];
int r(){
    return rand();
}
int main(){
    srand((unsigned)time(NULL));
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            id[i][j]=++cnt;
            a[cnt]=cnt;
        }

    int SIZE=990;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            if(i<n){
                v.push_back(edge{id[i][j],id[i+1][j],1});
                if(j<m){
                    v.push_back(edge{id[i][j],id[i+1][j+1],r()%SIZE+10});
                    v.push_back(edge{id[i+1][j+1],id[i][j],r()%SIZE+10});
                }
            }
            if(j<m){
                v.push_back(edge{id[i][j],id[i][j+1],r()%SIZE+10});
            }
        }
    random_shuffle(v.begin(),v.end());
    printf("%d %d\n",cnt,(int)v.size());
    for(int i=0;i<v.size();++i)
        printf("%d %d %d\n",a[v[i].u],a[v[i].v],v[i].w);
    return 0;
}

J. Regular Expression

对所有的字符串 $t_i$ 建立AC自动机, 由于 $\sum |t_i| \leq 10^3$ ，那么AC自动机上节点数 $\leq 10^3$

$dp[i][j]$ 代表: 考虑字符串 $s$ 前 $i$ 个字符, 在自动机上状态为 $j$ 的答案

若 $s_{i + 1} = '?'$ ，则 $\mathrm{d} \mathrm{p}[i+1][k]=\max (\mathrm{d} \mathrm{p}[i+1][k], \mathrm{d} \mathrm{p}[i][j]+\mathrm{words})$ ， $k$ 为状态 $j$ 读入字符 $a,b,c,\cdots,z$ 后转移的状态。

若 $s_{i + 1} \neq '?'$ ，则 $\mathrm{d} \mathrm{p}[i+1][k]=\max (\mathrm{d} \mathrm{p}[i+1][k], \mathrm{d} \mathrm{p}[i][j]+\mathrm{words})$ ， $k$ 为状态 $j$ 读入字符 $s_{i+1}$ 后转移的状态。

$words$ 为以状态 $k$ 结尾的单词的个数

$dp[i][j]$ 第一维可以使用滚动数组优化掉。

#include <bits/stdc++.h>
#define fi first
#define se second
#define sf scanf
#define pf printf
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define fo(i,a) for(int i=1;i<=(a.n);i++)
#define mem(x,y) memset((x),(y),sizeof(x))
#define fup(i,x,y) for(int i=(x);i<=(y);i++)
#define fdn(i,x,y) for(int i=(x);i>=(y);i--)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

const int __=1e3+5;

int dp[2][__];

struct AhoCorasickAutomaton
{
    static const int alp=26;

    static int to_idx(char ch)
    {
        return ch-'a'+1;
    }

    struct Trie
    {
        struct node
        {
            int nex[alp+1],last,num;
            void clear()
            {
                num=last=0;
                mem(nex,0);
            }
        }t[__];

        Trie() {clear();}

        node& operator[](int x){return t[x];}

        int idx;

        void insert(char s[])
        {
            int x=0;
            for(int i=1;s[i];++i)
            {
                int k=to_idx(s[i]);
                if(!t[x].nex[k])
                {
                    t[x].nex[k]=++idx;
                    t[idx].clear();
                }
                x=t[x].nex[k];
            }
            ++t[x].num;
        }

        void clear(){idx=0;t[0].clear();}
    }t;

    AhoCorasickAutomaton() {clear();}

#define nex(x) t[x].nex[i]
#define fail(x) t[x].nex[0]

    void get_fail()
    {
        queue<int>Q;Q.push(0);
        while(!Q.empty())
        {
            int x=Q.front();Q.pop();
            for(int i=1;i<=alp;++i)
                if(nex(x))
                {
                    Q.push(nex(x));
                    if(x)fail(nex(x))=nex(fail(x));
                }
                else nex(x)=nex(fail(x));
            if(t[fail(x)].num)t[x].last=fail(x);
            else t[x].last=t[fail(x)].last;
            t[x].num+=t[t[x].last].num;
        }
    }

    int ac(char s[],int len)
    {
        dp[0][0]=0;
        for(int i=1,f=1;i<=len;++i,f=!f)
        {
            mem(dp[f],-1);
            for(int j=0;j<=t.idx;++j)
            {
                if(dp[!f][j]==-1)continue;
                if(s[i]!='?')
                {
                    int x=to_idx(s[i]),y=t[j].nex[x];
                    dp[f][y]=max(dp[f][y],dp[!f][j]+t[y].num);
                    continue;
                }
                for(int k=1;k<=alp;++k)
                {
                    int y=t[j].nex[k];
                    dp[f][y]=max(dp[f][y],dp[!f][j]+t[y].num);
                }
            }
        }
        int ans=0;
        for(int i=0;i<=t.idx;++i)
            ans=max(ans,dp[len&1][i]);
        return ans;
    }

    void clear(){t.clear();}
}aca;

char a[__],b[__];

int main()
{
    mem(dp,-1);
    int m;sf("%s%d",a+1,&m);
    for(int i=1;i<=m;++i)
    {
        sf("%s",b+1);
        aca.t.insert(b);
    }
    aca.get_fail();
    pf("%d\n",aca.ac(a,strlen(a+1)));
    return 0;
}

K. Mr.Liang's Sequence Problem(IV)

1.数位 $\rm dp$

数位 $\rm dp$ 简单题, 可能被发现的比较晚

${\rm dp}[i][j]$ 代表长度为 $i$ , 数位总和为 $j$ 的所有数字的数位之和

#include<bits/stdc++.h>
#define fi first
#define sf scanf
#define se second
#define pf printf
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(x,y) memset((x),(y),sizeof(x))
#define fup(i,x,y) for(int i=(x);i<=(y);++i)
#define fdn(i,x,y) for(int i=(x);i>=(y);--i)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
using namespace std;

struct DigitalDynamicProgramming
{
    int bit[20];
    ll dp[20][200];

    DigitalDynamicProgramming() {memset(dp,-1,sizeof(dp));}

    ll dfs(int len,int sum,bool lim)
    {
        if(!len)return sum;
        if(!lim && ~dp[len][sum])return dp[len][sum];
        int r=lim?bit[len]:9;

        ll res=0;
        for(int i=0;i<=r;++i)
        {
            res+=dfs(len-1,sum+i,lim && i==bit[len]);
        }
        if(lim)return res;
        return dp[len][sum]=res;
    }

    ll cal(ll x)
    {
        if(x<0)return 0;
        int idx=0;
        for(;x;x/=10)bit[++idx]=x%10;
        return dfs(idx,0,true);
    }
}dp;

int main()
{
    ll l,r;sf("%lld%lld",&l,&r);
    pf("%lld\n",dp.cal(r)-dp.cal(l-1));
    return 0;
}

2.计算贡献

考虑数字 $0,1,2,\cdots ,9$ 分别在个位, 十位, 百位, $\cdots$ 出现的次数, 不难发现:

个位每 $10$ 个数字出现一个循环, 每个循环中每个数字分别出现 $1$ 次

百位每 $100$ 个数字出现一个循环, 每个循环中每个数字分别出现连续 $10$ 次

千位每 $1000$ 个数字出现一个循环, 每个循环中每个数字分别出现连续 $100$ 次

$\cdots$

以此类推

#include<bits/stdc++.h>
#define fi first
#define sf scanf
#define se second
#define pf printf
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(x,y) memset((x),(y),sizeof(x))
#define fup(i,x,y) for(int i=(x);i<=(y);++i)
#define fdn(i,x,y) for(int i=(x);i>=(y);--i)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
using namespace std;

ll cal(ll n)
{
    ll res=0;
    for(ll m=10;m<=n*10;m*=10)
        for(int i=0;i<=9;++i)
        {
            res+=n/m*(m/10)*i;
            if(n%m+1>=i*m/10)
                res+=min(n%m+1-i*m/10,m/10)*i;
        }
    return res;
}

int main()
{
    ll l,r;sf("%lld%lld",&l,&r);
    pf("%lld\n",cal(r)-cal(l-1));
    return 0;
}