【题解】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-19 09:05
已编辑
蚌埠铁三小 硬件开发
硬件本科面试技巧
前言&nbsp;鼠鼠因保研形势摇摆不定，且放弃考研，而选择本科直接就业；因在求职中，受牛客网的帮助甚多，一方面，正所谓“吃水不忘挖井人”，且关于本科就业经验贴相对较少，鼠鼠斗胆抛砖引玉，整理并分享鼠鼠自己面试的经验，希望能给后续本科就业和从事硬件的萌新们一些求职的经验以及启发；本帖构思主要包括自我介绍、专业面试、HR面试、面试反问等内容。&nbsp;offer：康冠&nbsp;TCL&nbsp;光迅&nbsp;迪普&nbsp;格力&nbsp;长园深瑞&nbsp;海能达&nbsp;比亚迪&nbsp;艾为&nbsp;正浩&nbsp;锦浪&nbsp;欣旺达&nbsp;海康威视等（鼠鼠无集邮癖，offer多为点击即送的公司，绝大部分在谈薪阶段就已拒绝，没有恶意占用资源）；&nbsp;待面试：全科（人才库）&nbsp;华为（...
查看12道真题和解析 牛客创作赏金赛 华为求职进展汇总
点赞 评论 收藏
分享
11-16 08:40
武汉工程大学 IT技术支持
点赞 评论 收藏
分享
10-18 00:17
第一拖拉机制造厂拖拉机学院 Java
又来了哈
hr天天给我发消息😅
牛客279957775号：铁暗恋
点赞 评论 收藏
分享
昨天 00:46
辽宁大学 集成电路IC设计
点赞 评论 收藏
分享
22 5 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
245420次浏览 1999人参与
# 学历or实习经历，哪个更重要 #
40895次浏览 297人参与
# 北方华创开奖 #
22678次浏览 257人参与
# 地方国企笔面经互助 #
2506次浏览 6人参与
# 你最想要的公司福利是？ #
39683次浏览 123人参与
# 选完offer后，你后悔学本专业吗 #
10127次浏览 75人参与
# 面试题刺客退退退 #
136892次浏览 2090人参与
# 国企/银行/研究所公司爆料 #
89610次浏览 411人参与
# 应届生被毁约被毁意向了怎么办 #
26932次浏览 238人参与
# 一觉醒来，我觉醒了超级打工人系统 #
2811次浏览 35人参与
# 机械应届生薪资要多少才合适？ #
12359次浏览 60人参与
# 查收我的offer竞争力报告 #
16498次浏览 224人参与
# 校招入职后的感受 #
156830次浏览 1959人参与
# 你觉得第一学历对求职有影响吗？ #
14844次浏览 121人参与
# 没有实习经历，还有机会进大厂吗 #
804802次浏览 13813人参与
# 我的工作日记 #
21104次浏览 270人参与
# 不给转正的实习，你还去吗 #
1516489次浏览 16963人参与
# 寒假躺平还是提前实习 #
58311次浏览 438人参与
# 总结:哪家公司面试体验感最差 #
25602次浏览 129人参与
# 秋招OC许愿 #
226299次浏览 1868人参与
# 如何写一份好简历 #
601589次浏览 8426人参与
牛客网
牛客企业服务