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

回文大师

知识点：kmp
题解：
设数组为的翻转，即
对数组求出数组，然后那数组和去做匹配，设匹配了位置，则和构成了一个回文，对这个位置的计数，根据的性质，设，则，因此对计数的同时还要对都计数，但是暴力跳会。
如果把看作的父亲，则数组构成了一颗以为根节点的树（因为），跑完和的匹配后再在树上进行子树求和即可。

#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]);
}

价值序列

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

#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);
  }
}

数组划分

知识点：单调栈、并查集
题解：
考虑对做前缀和，设，对于一个位置，找到最小的满足，可以证明对于任意，区间都是美丽的数组；对于任意，区间都不是美丽的数组。
对于区间，直接取作为第一个区间是最优的。
反证法：如果取是最优的，由于，于是有，如果把作为第一个区间，会作为第二个区间，凭空多出一个区间，显然不优。
于是对于每个，需要找到最小的满足，可以用单调栈找到。
在单调栈的过程中运行到了位置时，可以求出所有的答案，此时单调栈上有一些位置，找到最小的满足，那么的答案为。
如果在退栈的时间维护一个并查集，让，并维护每个对应的下标，则可以找到这个。总的时间复杂度为。

#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');
  }
}

删除子序列

知识点：贪心
输出行，第行一个整数为第组测试用例的答案。
题解：
考虑一个贪心做法，首先取在中出现的最大位置（设为），接下来需要找位置满足，此时所有满足且的位置都可以直接删除，因为它们不可能组成字符串（它们缺乏），再继续找，...，一直找到结束一轮查找，把所有找到的位置删除，并把答案加。
重复这个查找过程，直到找不到位置，用栈实现可以做到。
用数据结构实现，比如可以做到。

#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);
  }
}

骑士

知识点：前缀和
题解：发现只要满足即可，维护的前缀和后缀，就可以很容易得到答案，时间复杂度。

#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);
  }
}

+-串

知识点：分类讨论、模拟
题解：不妨令，每次操作相当于可以让或者，每次可以贪心往最优的方向移动，或者也可以分情况进行讨论，时间复杂度。

#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

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

#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函数、博弈
题解：把看作，把看作，可以得到一个串，把状态压缩成，可以发现操作只会让的值减少，于是可以记录每个状态的函数，的函数为输出，否则输出。

#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)

知识点：组合数学
题解：首先可以不用考虑，接下考虑有个和个，如果上述和式中出现了个，那么需要出现个，于是答案为。

#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)

给出长度为的数组，求。
数学课上，老师教了牛牛如何快速求上面式子的和：
$$

于是上述的式子就能够在的时间复杂度内被计算出来。

受到老师的启发，牛牛又想到了如何求的和。为此牛牛感到很兴奋，激动得一整夜都睡不着，第二天，牛牛就开始向牛妹炫耀自己能解决这个问题。

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

但同时，她又给牛牛提出了一个问题，给你一个整数，你能求是多少吗？

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

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

输入描述

第一行两个整数。
第二行个整数。

输出描述

输出一行一个整数，为答案除以的余数。
知识点：多项式
题解：
一道比较入门的分治。
设，有转移。
可以把看成一个多项式，根据转移有。
于是可以得到，可以采用分治，时间复杂度为。 表示多项式的次项系数。
由于撞题了，所以这个题没了，那么就送给大家当礼物好了：
http://www.51nod.com/Challenge/Problem.html#problemId=1348

祝大家接下来的比赛顺利！

全部评论
请问h题预处理里的sg[i]++是什么意思啊🤔，真的看不明白
1 回复 分享
发布于 2022-02-19 00:32
做题困难就来学，【课程】2021牛客竞赛算法入门秋季班开课啦！通过下面邀请链接报名，可立减20.0元. https://www.nowcoder.com/courses/cover/live/724?coupon=AsiMBN7 加QQ ：61194610，发一个红包 牛客竞赛语法入门班 ，通过下面邀请链接报名，可立减10.0 https://www.nowcoder.com/courses/cover/live/678?coupon=AI6lOdI 加QQ ：61194610，发一个红包
点赞 回复 分享
发布于 2022-02-13 16:02

相关推荐

11-25 16:25
西安电子科技大学 Java
2024年最热门的区块链生态系统：Solana依旧领跑
2024年，区块链领域持续活跃，各大生态系统纷纷通过技术突破、应用落地和社区活动争夺投资者的关注。根据最新数据显示，Solana生态系统以38.8%的全球投资者兴趣份额，继续领跑最受欢迎的区块链生态。与此同时，Base、TON和Sui等新兴生态系统迅速崛起，正在重新定义市场格局。一、Solana生态系统：稳居头把交椅1.&nbsp;持续的技术优势Solana因其高速低成本的区块链网络而被广泛认可，2024年进一步巩固了其技术领先地位。其TPS（每秒交易数）和低廉的Gas费用使其成为交易者和开发者的首选，尤其在模因币（Meme&nbsp;Token）和去中心化金融（DeFi）领域表现出色。关键驱动因素：2.&nbsp;市场份...
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
11-28 23:13
点赞 评论 收藏
分享
10-30 00:33
河北传媒学院 算法工程师
这是真的吗？有无tju 的佬证明一下
牛客868257804号：九个中铁八个中建
点赞 评论 收藏
分享
11-23 19:00
昆明理工大学 银行管培生
点赞 评论 收藏
分享
评论
22
5
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
233353次浏览 2031人参与
# 在职场上，你最讨厌什么样的同事 #
5714次浏览 81人参与
# 北方华创开奖 #
66012次浏览 549人参与
# 25届秋招总结 #
396617次浏览 3976人参与
# 哪些公司校招卡第一学历 #
32836次浏览 105人参与
# 地方国企笔面经互助 #
6546次浏览 16人参与
# 阿里云管培生offer #
58990次浏览 1748人参与
# ai智能作图 #
21391次浏览 262人参与
# 硬件兄弟们 甩出你的华为奖状 #
77946次浏览 625人参与
# 实习，投递多份简历没人回复怎么办 #
2435892次浏览 34703人参与
# 工作中，你有没有遇到非常爱骂人的领导？ #
4726次浏览 47人参与
# 实习与准备秋招该如何平衡 #
722815次浏览 8551人参与
# 我的实习求职记录 #
6121642次浏览 83953人参与
# 如果再来一次，你还会选择这个工作吗？ #
110472次浏览 1109人参与
# 25届机械人为了秋招做了哪些准备？ #
24993次浏览 355人参与
# 签了三方后想毁约怎么办 #
18563次浏览 111人参与
# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #
9959次浏览 213人参与
# 机械求职避坑tips #
22158次浏览 240人参与
# 游戏求职进展汇总 #
52774次浏览 344人参与
# 夸夸我的求职搭子 #
132021次浏览 1360人参与
# 腾讯求职进展汇总 #
207574次浏览 1694人参与
# 实习想申请秋招offer，能不能argue薪资 #
35786次浏览 308人参与
牛客网
牛客企业服务