Huah

编辑于 2022-02-13 10:00

【题解】2022牛客寒假算法基础集训营6 精

回文大师

知识点：kmp
题解：
设数组 $b$ 为 $a$ 的翻转，即 $b_i=a_{n-i+1}$
对数组 $a$ 求出 $nex$ 数组，然后那数组 $b$ 和 $a$ 去做匹配，设 $b_i$ 匹配了位置 $a_j$ ，则 $a_1a_2...a_j$ 和 $b_ib_{i-1}...b_{i-j+1}$ 构成了一个回文，对 $j$ 这个位置的计数 $+1$ ，根据 $kmp$ 的性质，设 $k=nex_j$ ，则 $a_1a_2...a_k=a_{j-k+1}...a_{j-1}a_j=b_ib_{i-1}...b_{i-k+1}$ ，因此对 $j$ 计数的同时还要对 $nex_j,nex_{nex_j},...$ 都计数，但是暴力跳 $nex$ 会 $TLE$ 。
如果把 $nex_j$ 看作 $j$ 的父亲，则 $nex$ 数组构成了一颗以 $0$ 为根节点的树（因为 $0\le nex_j<j$ ），跑完 $a$ 和 $b$ 的匹配后再在树上进行子树求和即可。

#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld\n", x); }
void out(int x, int y) { printf("%d %d\n", x, y); }
void out(ll x, ll y) { printf("%lld %lld\n", x, y); }
void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=1e6+5,mod=998244353;
int n,a[N],b[N],nex[N],ans[N];
int main()
{
  // freopen("1.in", "r",stdin);
  // freopen("1.out", "w", stdout);
  sc(n);
  for(int i=0;i<=n;i++) ans[i]=0;
  rep(i,1,n) sc(a[i]);
  nex[0]=-1;
  for(int i=1;i<=n;i++)
  {
    int k=nex[i-1];
    while(k!=-1&&a[k+1]!=a[i]) k=nex[k];
    nex[i]=k+1;
  }
  rep(i,1,n) b[i]=a[i];
  reverse(b+1,b+1+n);
  for(int i=1,j=0;i<=n;i++)
  {
    while(j!=-1&&a[j+1]!=b[i]) j=nex[j];
    j++;
    ans[j]++;
  }
  for(int i=n;i>=1;i--) ans[nex[i]]+=ans[i];
  for(int i=1;i<=n;i++) printf(i==n?"%d\n":"%d ",ans[i]);
}

价值序列

知识点：计数
题解：
首先说一个结论：删除一个数，价值必定不增。
证明可以用归纳法，对于 $n\le 2$ 显然。
对于 $n>2$ ，如果删除一个 $a_{i-1}\le a_i\le a_{i+1}$ 的位置 $i$ ，价值不变，如果删除 $a_{i-1}\ge a_i\ge a_{i+1}$ 的位置 $i$ ，价值也不变。如果删除 $a_{i-1}\le a_i\ge a_{i+1}$ 或 $a_{i-1}\ge a_i\le a_{i+1}$ ，答案只可能减少，删除一个数后 $n$ 的规模减 $1$ ，由归纳法结论得证。
接下来，考虑删除哪些数答案不会变。
把相等的数看成一个连通块，设为 $[i,j]$ ，如果满足 $a_{i-1}<a_i=...=a_j<a_{j+1}$ 或 $a_{i-1}>a_i=...=a_j>a_{j+1}$ （且要满足 $i>1,j<n$ ），则区间 $[i,j]$ 的数可以全部删除，不影响价值，这样的区间对答案贡献有 $2^{j-i+1}$ 种方案。否则区间 $[i,j]$ 的数必须保留一个，这样的区间对答案贡献 $2^{j-i+1}-1$ 种方案。把所有区间的贡献连乘起来就是答案。

#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld\n", x); }
void out(int x, int y) { printf("%d %d\n", x, y); }
void out(ll x, ll y) { printf("%lld %lld\n", x, y); }
void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=1e5+5,mod=998244353;
int n,a[N],p2[N];
int main()
{
  // freopen("1.in", "r",stdin);
  //   freopen("1.out", "w", stdout);
  p2[0]=1;
  for(int i=1;i<N;i++) p2[i]=p2[i-1]*2%mod;
  int t;sc(t);
  int sum=0;
  while(t--)
  {
    scanf("%d",&n);
    rep(i,1,n) sc(a[i]),ast(a[i],1,1000000000);
    int ans=1;
    for(int i=1;i<=n;i++)
    {
      int j=i;
      while(j<n&&a[j+1]==a[i]) j++;

      if(i-1>=1&&j+1<=n&&(a[i-1]<a[i]&&a[j+1]>a[i]||a[i-1]>a[i]&&a[j+1]<a[i]))
        ans=1ll*ans*p2[j-i+1]%mod;
      else ans=1ll*ans*(p2[j-i+1]+mod-1)%mod;
      i=j;
    }
    out(ans);
  }
}

数组划分

知识点：单调栈、并查集
题解：
考虑对 $a_i$ 做前缀和，设 $sum_i=\sum_{i=1}^na_i,sum_0=0$ ，对于一个位置 $i$ ，找到 $f_i=$ 最小的 $j$ 满足 $sum_j-sum_{i-1}<0(j\ge i)(如果没有这样的j则认为j=n)$ ，可以证明对于任意 $k\le j$ ，区间 $[i,k]$ 都是美丽的数组；对于任意 $(k>j)$ ，区间 $[i,k]$ 都不是美丽的数组。
对于区间 $[l,r]$ ，直接取 $[l,f_l]$ 作为第一个区间是最优的。
反证法：如果取 $[l,k]$ 是最优的 $1\le k<f_l$ ，由于 $\sum_{i=l}^{f_l}a_i<0,\sum_{i=l}^k\ge 0$ ，于是有 $\sum_{i=k+1}^{f_l}<0$ ，如果把 $[l,k]$ 作为第一个区间， $[k+1,f_l]$ 会作为第二个区间，凭空多出一个区间，显然不优。
于是对于每个 $i$ ，需要找到最小的 $j(j>i)$ 满足 $sum_j<sum_i$ ，可以用单调栈找到。
在单调栈的过程中运行到了位置 $i$ 时，可以求出所有 $l=i$ 的答案，此时单调栈上有一些位置 $i=s_{top}<s_{top-1}<...<s_{1}$ ，找到最小的 $k$ 满足 $s_k\le r$ ，那么 $[l,r]$ 的答案为 $top-k+1$ 。
如果在退栈 $s_{top}$ 的时间维护一个并查集，让 $fa_{s_{top}}=i$ ，并维护每个 $s_i$ 对应的下标 $rk_{s_i}=i$ ，则可以 $O(1)$ 找到这个 $k$ 。总的时间复杂度为 $O(n)$ 。

#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld\n", x); }
void out(int x, int y) { printf("%d %d\n", x, y); }
void out(ll x, ll y) { printf("%lld %lld\n", x, y); }
void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=5e6+5,mod=998244353;
int n,q;
int l[N],r[N];
ll a[N];
int top,rk[N],s[N],f[N],ans[N];
int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);}
int main()
{
  // freopen("6.in","r",stdin);
  // freopen("11.out","w",stdout);
  int t;sc(t);
  int sn=0,sq=0;
  while(t--)
  {
    sc(n,q);
    ast(n,1,5000000);ast(q,1,5000000);
    sn+=n;sq+=q;
    ast(sn,1,5000000);ast(sq,1,5000000);
    for(int i=1;i<=n;i++) sc(a[i]),ast(a[i],-1000000000,1000000000),a[i]+=a[i-1];
    for(int i=1;i<=q;i++) sc(l[i],r[i]),ast(l[i],1,n),ast(r[i],l[i],n),l[i]--,r[i]--;
    for(int i=1;i<=n;i++) f[i]=i;
    top=0;
    for(int i=n,j=q;i>=0;i--)
    {
      while(top&&a[s[top]]>=a[i]) 
      {
        f[s[top]]=i;
        top--;
      }
      s[++top]=i;
      rk[i]=top;
      while(j>=1&&l[j]==i)
      {
        ans[j]=top-rk[getf(r[j])]+1;
        j--;
      }
    }
    for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
  }
}

#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld\n", x); }
void out(int x, int y) { printf("%d %d\n", x, y); }
void out(ll x, ll y) { printf("%lld %lld\n", x, y); }
void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=5e6+5,mod=998244353;
int n,q;
int l[N],r[N];
ll a[N];
int top,rk[N],s[N],f[N],ans[N];
int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);}
const int BufferSize=1<<16;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
    if(head==tail) {
        int l=fread(buffer,1,BufferSize,stdin);
        tail=(head=buffer)+l;
    }
    return *head++;
}
inline int read() {
    int x=0,f=1;char c=Getchar();
    for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=Getchar()) x=x*10+c-'0';
    return x*f;
}
void print(int x)
{
    if(x>9) print(x/10);
    putchar(x%10|'0');
}
int main()
{
  // freopen("6.in","r",stdin);
  // freopen("11.out","w",stdout);
  int t;t=read();
  int sn=0,sq=0;
  while(t--)
  {
    n=read();q=read();
    ast(n,1,5000000);ast(q,1,5000000);
    sn+=n;sq+=q;
    ast(sn,1,5000000);ast(sq,1,5000000);
    for(int i=1;i<=n;i++) a[i]=read(),ast(a[i],-1000000000,1000000000),a[i]+=a[i-1];
    for(int i=1;i<=q;i++) l[i]=read(),r[i]=read(),ast(l[i],1,n),ast(r[i],l[i],n),l[i]--,r[i]--;
    for(int i=1;i<=n;i++) f[i]=i;
    top=0;
    for(int i=n,j=q;i>=0;i--)
    {
      while(top&&a[s[top]]>=a[i]) 
      {
        f[s[top]]=i;
        top--;
      }
      s[++top]=i;
      rk[i]=top;
      while(j>=1&&l[j]==i)
      {
        ans[j]=top-rk[getf(r[j])]+1;
        j--;
      }
    }
    for(int i=1;i<=q;i++) print(ans[i]),putchar('\n');
  }
}

删除子序列

知识点：贪心
输出 $T$ 行，第 $i$ 行一个整数为第 $i$ 组测试用例的答案。
题解：
考虑一个贪心做法，首先取 $t_m$ 在 $S$ 中出现的最大位置（设为 $p_m$ ），接下来需要找位置 $p_{m-1}$ 满足 $p_{m-1}<p_m$ ，此时所有满足 $i\ge p_m$ 且 $s_i=t_{m-1}$ 的位置都可以直接删除，因为它们不可能组成字符串 $t$ （它们缺乏 $t_m$ ），再继续找 $p_{m-2}<p_{m-1}$ ，...，一直找到 $p_1$ 结束一轮查找，把所有找到的位置删除，并把答案加 $1$ 。
重复这个查找过程，直到找不到位置，用栈实现可以做到 $O(n)$ 。
用数据结构实现，比如 $set$ 可以做到 $O(nlogn)$ 。

#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld\n", x); }
void out(int x, int y) { printf("%d %d\n", x, y); }
void out(ll x, ll y) { printf("%lld %lld\n", x, y); }
void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=1e6+5,mod=998244353;
int n,m;
char s[N],t[N];
int main()
{
  // freopen("1.in", "r",stdin);
  //   freopen("1.out", "w", stdout);
  int ts;sc(ts);ast(ts,1,10000);
  int sum=0;
  while(ts--)
  {
    scanf("%d%d",&n,&m);
    sc(s+1);sc(t+1);
    ast(n,1,1000000);ast(m,1,min(n,26));
    sum+=n;
    ast(sum,1,1000000);
    assert(strlen(s+1)==n);assert(strlen(t+1)==m);
    rep(i,1,n) ast(s[i],'a','z');
    rep(i,1,m) ast(t[i],'a','z');
    for(int i=1;i<=m;i++)
      for(int j=i+1;j<=m;j++) assert(t[i]!=t[j]);
    vector<int>vc[26];
    rep(i,1,n)
      vc[s[i]-'a'].emplace_back(i);
    int ans=0;
    while(true)
    {
      bool flag=true;
      int las=n+1;
      for(int i=m;i>=1;i--)
      {
        while(vc[t[i]-'a'].size()&&vc[t[i]-'a'].back()>=las) vc[t[i]-'a'].pop_back();
        if(vc[t[i]-'a'].empty()){flag=false;break;}
        las=vc[t[i]-'a'].back();
        vc[t[i]-'a'].pop_back();
      }
      if(!flag) break;
      ans++;
    }
    out(ans);
  }
}

骑士

知识点：前缀和
题解：发现只要满足 $h_j\ge \max_{i\neq j}(a_i-b_j)+1=\max_{i\neq j}a_i-b_j+1$ 即可，维护 $a_i$ 的前缀和后缀 $max$ ，就可以很容易得到答案，时间复杂度 $O(n)$ 。

#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld\n", x); }
void out(int x, int y) { printf("%d %d\n", x, y); }
void out(ll x, ll y) { printf("%lld %lld\n", x, y); }
void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=2e5+5,mod=998244353;
int n,a[N],b[N],h[N];
int main()
{
  // freopen("1.in", "r",stdin);
  //   freopen("1.out", "w", stdout);
  int t;sc(t);ast(t,1,100000);
  int sum=0;
  while(t--)
  {
    sc(n);
    ast(n,1,200000);
    sum+=n;ast(sum,1,500000);
    rep(i,1,n) sc(a[i],b[i],h[i]),ast(a[i],1,1000000000),ast(b[i],1,1000000000),ast(h[i],1,1000000000);
    vector<int>pre(n+2),bk(n+1);
    rep(i,1,n) pre[i]=max(pre[i-1],a[i]);
    nep(i,n,1) bk[i]=max(bk[i+1],a[i]);
    ll ans=0;
    rep(i,1,n)
    {
      ll s=1ll*max(pre[i-1],bk[i+1])-b[i]+1;
      ans+=max(0ll,s-h[i]);
    }
    out(ans);
  }
}

+-串

知识点：分类讨论、模拟
题解：不妨令 $a=\sum\limits_{i=1}^n s_i$ ，每次操作相当于可以让 $a_i-2$ 或者 $a_i+2$ ，每次可以贪心往最优的方向移动，或者也可以分情况进行讨论，时间复杂度 $O(|S|)$ 。

#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld\n", x); }
void out(int x, int y) { printf("%d %d\n", x, y); }
void out(ll x, ll y) { printf("%lld %lld\n", x, y); }
void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=1e5+5,mod=998244353;
int n,k;
char s[N];
int main()
{
  // freopen("1.in", "r",stdin);
  //   freopen("1.out", "w", stdout);
  int t;sc(t);ast(t,1,100000);
  int sum=0;
  while(t--)
  {
    scanf("%s",s+1);
    scanf("%d",&k);
    n=strlen(s+1);
    ast(k,1,n);ast(n,1,100000);
    sum+=n;ast(sum,1,300000);
    rep(i,1,n) assert(s[i]=='-'||s[i]=='+');
    int a=0;
    rep(i,1,n)
      if(s[i]=='+') a++;
      else a--;
    a=abs(a);
    if(k<=a/2) out(a-k*2);
    else
    {
      k-=a/2;
      a%=2;
      if(a==1) out(1);
      else out(k%2==0?0:2);
    }
  }
}

迷宫2

知识点：搜索
题解：可以证明从 $(1,1)$ 到 $(n,m)$ 存在一条无环的最短路径。证明可以假设有环，如果有环，去掉环一定能让答案不增。于是问题变为找 $(1,1)$ 的 $(n,m)$ 的最短路径，对于点 $(x,y)$ ，如果 $c_{x,y}=L$ ，则 $(x,y)$ 到 $(x,y-1)$ 的花费为 $0$ ，到其它三个方向的花费为 $1$ 。可以开一个双向队列进行 $bfs$ ，如果 $(x,y)$ 到 $(x',y')$ 的花费为 $0$ 则把 $(x',y')$ 压入队首，否则压入队尾，对每个已经更新的点打上标记，每个点最多被压入队列 $4$ 次。时间复杂度 $O(nm)$ 。

#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld\n", x); }
void out(int x, int y) { printf("%d %d\n", x, y); }
void out(ll x, ll y) { printf("%lld %lld\n", x, y); }
void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=1005,mod=998244353;
int n,m,dis[N][N],pre[N][N];
char s[N][N];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
char dir[]={'D','U','R','L'};
bool vis[N][N];
int main()
{
  // freopen("1.in", "r",stdin);
  //   freopen("1.out", "w", stdout);
  int t;sc(t);ast(t,1,200);
  int sum=0;
  while(t--)
  {
    sc(n,m);ast(n,1,1000);ast(m,1,1000);
    sum+=n*m;
    ast(sum,1,2000000);
    rep(i,1,n) sc(s[i]+1),assert(strlen(s[i]+1)==m);
    rep(i,1,n) rep(j,1,m) assert(s[i][j]=='L'||s[i][j]=='R'||s[i][j]=='U'||s[i][j]=='D');
    rep(i,1,n) rep(j,1,m) dis[i][j]=inf,vis[i][j]=false;
    dis[1][1]=0;
    deque<pair<int,int>>q;
    q.push_back({1,1});
    while(!q.empty())
    {
      int x=q.front().first,y=q.front().second;q.pop_front();
      if(vis[x][y]) continue;
      vis[x][y]=true;
      for(int i=0;i<4;i++)
      {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx<1||xx>n||yy<1||yy>m) continue;
        int ndis=dis[x][y]+(dir[i]!=s[x][y]);
        if(ndis<dis[xx][yy])
        {
          dis[xx][yy]=ndis;
          pre[xx][yy]=i;
          if(ndis==dis[x][y]) q.push_front({xx,yy});
          else q.push_back({xx,yy});
        }
      }
    }
    printf("%d\n",dis[n][m]);
    int x=n,y=m;
    while(!(x==1&&y==1))
    {
      int xx=x-dx[pre[x][y]],yy=y-dy[pre[x][y]];
      if(s[xx][yy]!=dir[pre[x][y]])
        printf("%d %d %c\n",xx,yy,dir[pre[x][y]]);
      x=xx;y=yy;
    }
  }
}

寒冬信使2

知识点：SG函数、博弈
题解：把 $w$ 看作 $1$ ，把 $b$ 看作 $0$ ，可以得到一个 $01$ 串 $s_1,s_2,...,s_n$ ，把 $s_1,s_2,...,s_n$ 状态压缩成 $X=\sum_{i=0}^{n-1}2^i*s_{i+1}$ ，可以发现操作只会让 $X$ 的值减少，于是可以记录每个状态的 $SG$ 函数， $X$ 的 $SG$ 函数为 $0$ 输出 $No$ ，否则输出 $Yes$ 。

#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld\n", x); }
void out(int x, int y) { printf("%d %d\n", x, y); }
void out(ll x, ll y) { printf("%lld %lld\n", x, y); }
void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=15,mod=998244353;
int n,sg[1<<10];
char s[N];
bitset<105>vis;
int main()
{
  // freopen("1.in", "r",stdin);
//   freopen("1.out", "w", stdout);
  for(int i=1;i<1<<10;i++)
  {
    vis.reset();
    for(int j=0;j<10;j++)
      if(i>>j&1)
      {
        if(j==0) vis[sg[i^(1<<j)]]=true;
        else
        {
          for(int k=0;k<j;k++) vis[sg[i^(1<<j)^(1<<k)]]=true;
        }
      }
      while(vis[sg[i]]) sg[i]++;
  }
  int t;scanf("%d",&t);ast(t,1,5000);
  while(t--)
  {
    sc(n);ast(n,1,10);
    sc(s+1);assert(strlen(s+1)==n);
    int st=0;
    for(int i=1;i<=n;i++)
      if(s[i]=='w') st|=1<<(i-1);
    printf(sg[st]?"Yes\n":"No\n");
  }
}

A+B问题

知识点：模拟
题解：
数组模拟即可。

#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld\n", x); }
void out(int x, int y) { printf("%d %d\n", x, y); }
void out(ll x, ll y) { printf("%lld %lld\n", x, y); }
void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=4e5+5,mod=998244353;
int k,c[N];
char a[N],b[N];
int main()
{
  // freopen("1.in", "r",stdin);
//   freopen("1.out", "w", stdout);
  sc(k);ast(k,2,10);
  sc(a+1);sc(b+1);
  int n=strlen(a+1),m=strlen(b+1);
  if(n!=1) assert(a[1]!='0');
  if(m!=1) assert(b[1]!='0');
  rep(i,1,n) ast(a[i],'0','0'+k-1);
  rep(i,1,m) ast(b[i],'0','0'+k-1);
  reverse(a+1,a+1+n);
  reverse(b+1,b+1+m);
  rep(i,1,max(n,m))
  {
    if(i<=n) c[i]+=a[i]-'0';
    if(i<=m) c[i]+=b[i]-'0';
  }
  n=max(n,m);
  rep(i,1,n)
  {
    c[i+1]+=c[i]/k;
    c[i]%=k;
    if(c[n+1]) n++;
  }
  for(int i=n;i>=1;i--) putchar(c[i]+'0');
}

牛妹的数学难题(easy version)

知识点：组合数学
题解：首先 $0$ 可以不用考虑，接下考虑有 $n$ 个 $1$ 和 $m$ 个 $2$ ，如果上述和式中 $1$ 出现了 $i$ 个，那么 $2$ 需要出现 $k-i$ 个，于是答案为 $\sum_{i=0}^kC(n,i)*C(m,k-i)*2^{k-i}$ 。

#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld\n", x); }
void out(int x, int y) { printf("%d %d\n", x, y); }
void out(ll x, ll y) { printf("%lld %lld\n", x, y); }
void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=1e7+5,mod=998244353;
int n,k,a[N];
ll f[N],invf[N],p2[N];
ll C(int n,int m)
{
    if(n<m) return 0;
    return f[n]*invf[m]%mod*invf[n-m]%mod;
}
int main()
{
  // freopen("1.in", "r",stdin);
//   freopen("1.out", "w", stdout);
  f[0]=f[1]=invf[0]=invf[1]=1;
  rep(i,2,N-1)
  {
    f[i]=f[i-1]*i%mod;invf[i]=(mod-mod/i)*invf[mod%i]%mod;  
  }
  rep(i,2,N-1) invf[i]=invf[i-1]*invf[i]%mod;
  p2[0]=1;
  rep(i,1,N-1) p2[i]=p2[i-1]*2%mod;
  sc(n,k);
  ast(n,1,10000000);
  ast(k,1,n);
  int vis[3];
  memset(vis,0,sizeof(vis));
  rep(i,1,n) sc(a[i]),ast(a[i],0,2),vis[a[i]]++;
  ll ans=0;
  for(int i=0;i<=k;i++)
    ans=(ans+C(vis[2],i)*p2[i]%mod*C(vis[1],k-i)%mod)%mod;
  out(ans);
}

牛妹的数学难题(hard version)

给出长度为 ${n}$ 的数组 ${a_1,a_2,...,a_n}$ ，求 ${\sum\limits_{i=1}^n\sum\limits_{j=i+1}^na_i*a_j}$ 。
数学课上，老师教了牛牛如何快速求上面式子的和：
$ $\sum\limits_{i=1}^n\sum\limits_{j=i+1}^na_i*a_j=\frac{\sum\limits_{i=1}^n\sum\limits_{j=1}^na_i*a_j-\sum_{i=1}^na_i*a_i}{2}\\=\frac{\sum\limits_{i=1}^na_i\sum\limits_{j=1}^na_j-\sum_{i=1}^na_i*a_i}{2}=\frac{(\sum\limits_{i=1}^na_i)^2-\sum_{i=1}^na_i^2}{2}$ $

于是上述的式子就能够在 ${O(n)}$ 的时间复杂度内被计算出来。

受到老师的启发，牛牛又想到了如何求 ${\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\sum\limits_{k=j+1}^na_i*a_j*a_k}$ 的和。为此牛牛感到很兴奋，激动得一整夜都睡不着，第二天，牛牛就开始向牛妹炫耀自己能解决这个问题。

牛妹看到牛牛这个问题，虽然她觉得很简单，但是为了鼓励牛牛勇于发现问题的精神，她还是夸赞了牛牛。

但同时，她又给牛牛提出了一个问题，给你一个整数 ${k}$ ，你能求 ${\sum\limits_{i_1=1}^n\sum\limits_{i_2=i_1+1}^n...\sum\limits_{i_k=i_{k-1}+1}^na_{i_1}*a_{i_2}*...*a_{i_k}}$ 是多少吗？

这可把牛牛难到了，牛牛无法解决这个问题，但是牛牛知道你是一个天才程序员，于是他拿着这个问题来向你求助，作为牛牛的好朋友，你能帮帮他解决牛妹的这个数学难题吗？

由于答案可能很大，你只需要输出答案除以 ${998244353}$ 的余数。

输入描述

第一行两个整数 ${n,k(1\le n\le 200000,1\le k\le n)}$ 。
第二行 ${n}$ 个整数 ${a_1,a_2,...,a_n(1\le a_i\le 10^9)}$ 。

输出描述

输出一行一个整数，为答案除以 ${998244353}$ 的余数。
知识点：多项式
题解：
一道比较入门的分治 $FFT$ 。
设 $f_{n,k}={\sum\limits_{i_1=1}^n\sum\limits_{i_2=i_1+1}^n...\sum\limits_{i_k=i_{k-1}+1}^na_{i_1}*a_{i_2}*...*a_{i_k}}$ ，有转移 $f_{n,k}=f_{n-1,k}+f_{n-1,k-1}*a_n$ 。
可以把 $f_{n,0},f_{n,1},...,f_{n,n}$ 看成一个多项式 $F(n)=\sum_{i=0}^nf_{n,i}x^i$ ，根据转移有 $F(n)=F(n-1)*(1+a_nx)$ 。
于是可以得到 $f(n,k)=[x^k]\prod_{i=1}^n(1+a_ix)$ ，可以采用分治 $FFT$ ，时间复杂度为 $O(nlog^2n)$ 。 $[x^k]\prod_{i=1}^n(1+a_ix)$ 表示多项式 $\prod_{i=1}^n(1+a_ix)$ 的 $k$ 次项系数。
由于撞题了，所以这个题没了，那么就送给大家当礼物好了：
http://www.51nod.com/Challenge/Problem.html#problemId=1348