【6.24校内test】T3 棠梨煎雪

【题目背景】

岁岁花藻檐下共将棠梨煎雪。

自总角至你我某日辗转天边。

天淡天青，宿雨沾襟。

一年一会信笺却只见寥寥数言。

——银临《棠梨煎雪》

【问题描述】

扶苏正在听《棠梨煎雪》的时候，山东省实验中学的 zzh 发来一道IOI2018集训队互测题：我切了这集训队题，辣鸡扶苏快过来做题。扶苏定睛一看，这不 s* 题嘛，写了一发交上去才发现自己看错题目了。但是写完的代码不能浪费，于是就有了这道题。

歌词中的主人公与她的朋友一年会有一次互相写信给对方，一共通信了 m 年。为了简化问题，我们认为他们每封信的内容都是一条二进制码，并且所有二进制码的长度都是 n。即每封信的内容都是一个长度为 n 的字符串，这个字符串只含字符 0 或 1。

这天她拿出了朋友写给她的所有信件，其中第 i 年的写的信件编号为 i。由于信件保存时间过久，上面有一些字符已经模糊不清，我们将这样的位置记为 ?，? 字符可以被解释为 0 或 1。由于她的朋友也是人，符合人类的本质，所以朋友在一段连续的时间中书写的内容可能是相同的。现在她想问问你，对于一段连续的年份区间 [l,r] 中的所有信件，假如朋友在这段时间展示了人类的本质，所写的是同一句话，那么这一句话一共有多少种可能的组成。也即一共有多少字符串 S，满足在这个区间内的所有信件的内容都可能是 S。

一个长度为 n 的只含 0,1,? 的字符串 A 可能是一个字符串 B 当且仅当 B 满足如下条件：

B 的长度也是 n
B 中只含字符 0,1
A 中所有为 0 的位置在 B 中也是 0
A 中所有为 1 的位置在 B 中也是 1
A 中为 ? 的位置在 B 中可以为 0 也可以是 1

同时她可能会突然发现看错了某年的信的内容，于是他可能会把某一年的信的内容修改为一个别的只含 0,1,? 的长度为 n 的字符串。

【输入格式】

输入文件名为 lin.in。

输入文件中有且仅有一组数据，第一行为三个正整数 n,m,q，代表字符串长度，字符串个数和操作次数。

下面 m 行，每行是一个长度为 n 的字符串，第 i 个字符串代表第 i 年信的内容。

下面 q 行，每行的第一个数字是操作编号 opt。

如果 opt=0，那么后面接两个整数 [l,r]，代表一次查询操作

如果 opt=1，那么后面接一个整数 pos，在一个空格后会有一个长度为 n 的字符串，代表将第 pos 个字符串修改为新的字符串。

【输出格式】

输出文件名为 lin.out。

对于每个查询操作，输出一行一个整数代表答案。

SOLUTION：

子任务 1： 0 次询问，直接 freopen 即可得分，期望得分 5 分。

子任务 2：考虑在询问的时候枚举所有可能出现的串，然后遍历区间所有的字符串看看是否合法。由于字符串长度为 n，且每个位置只可能是 0/1，所以一共有 2 n 中情况。时间复杂度 O(2 nmq)，期望得分 10 分。

子任务 3：考虑对于一段区间的所有字符串的第 x 个字符，一共有四种可能，确定为 0，确定为 1，都可以，都不可以。如果都不可以则输出0，如果确定为 0 或 1，则这一位只有一种可能，否则有两种可能，根据乘法原理，如果有 a 个位置都可以，则会有 2 a 种可能。输出答案即可。时间复杂地 O(nmq)，期望得分 15 分。

（感觉我的代码就是介个思路呀，但是我肿么没有分呢？？又玄学啦（改了几行吧，就对了可海星））

（啊经过一晚上不懈努力，我终于知道我错哪了：1.cnt1没有memset，然后l==r的特判也不到家（所以emm对自己无语惹））

45pts（数据水的说qwq）

#include<bits/stdc++.h>

using namespace std;

inline int read(){

    int ans=;

    char last=' ',ch=getchar();

    while(ch<''||ch>'') last=ch,ch=getchar();

    while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

int n,m,q,opt,l,r;

char s[][];

int cx(int l,int r){

    long long cnt1;

    int ans=;

    int qj=r-l+;

    for(int i=;i<=n;i++){

        char d=' ';

        cnt1=;

        for(int j=l;j<=r;j++){

            if(s[j][i]=='?'){

                cnt1++;

                continue;

            }

            if(d==' ') d=s[j][i];

            if(d==s[j][i]) continue;

            else return ;

        }

        if(cnt1==qj) ans*=;

    }

    return ans;

}

int main(){

    n=read();m=read();q=read();

    if(m==)

        return ;

    for(int i=;i<=m;i++)

      scanf("%s",s[i]+);

    for(int i=;i<=q;i++){

        opt=read();

        if(opt==){

            l=read();r=read();

            cout<<cx(l,r)<<"\n";

        }

        else {

            char ss[];

            int f=read();

            scanf("%s",ss+);

            for(int i=;i<=n;i++){

                s[f][i]=ss[i];

            }

        }

    }

    return ;

}

45pts Code

#include<bits/stdc++.h>

using namespace std;

inline int read(){

    int ans=;

    char last=' ',ch=getchar();

    while(ch<''||ch>'') last=ch,ch=getchar();

    while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

int n,m,q,opt,l,r;

char s[][];

int cx(int l,int r){

    int cnt1[];

    memset(cnt1,,sizeof(cnt1));

    if(l==r) {

        int cnt=;

        for(int i=;i<=n;i++)

            if(s[l][i]=='?') cnt*=;

        return cnt;

    }

    int k=l;

    for(int i=;i<=n;i++){

        char d='x';

        for(int j=l;j<=r;j++){

            if(s[j][i]=='?'){

                cnt1[i]++;

                continue;

            }

            if(d=='x') d=s[j][i];

            if(d==s[j][i]) continue;

            else return ;

        }

    }

    int ans=;

    int qj=r-l+;

    for(int i=;i<=n;i++){

        if(cnt1[i]==qj) ans*=;

        else ans*=;

    }

    return ans;

}

int main(){

    freopen("lin.in","r",stdin);

    freopen("lin.out","w",stdout);

    n=read();m=read();q=read();

    if(m==)

        return ;

    for(int i=;i<=m;i++)

      scanf("%s",s[i]+);

    for(int i=;i<=q;i++){

        opt=read();

        if(opt==){

            l=read();r=read();

            cout<<cx(l,r)<<"\n";

        }

        else {

            char ss[];

            int f=read();

            scanf("%s",ss+);

            for(int i=;i<=n;i++){

                s[f][i]=ss[i];

            }

        }

    }

    return ;

}

最少改动的45pts Code

好了接下来是正解做法了（我不保证我能看懂因为zay太爱用指针啦）

的一部分（突然发现还有好多子任务的说）

子任务 4：

考虑 n 只有 30，可以状压到 int 中，具体的，维护两个 int，第一个 int 维护对应位是否确定为 0 或 1，第二个 int 维护如果确定为 0 或 1 了则具体是 0 还是 1。通过位运算操作一下可以快速的该区间内的信息。

具体的，考虑 a1,a2 是从 L 到某个位置左侧的区间信息，b1,b2 是该位置的区间信息，如果该询问没有能匹配的字符串，则 (a1|b1)&(a2^b2) 应该不为 0，输出 0 即可。否则 a1=a1|b1;a2=(a1|b1)&(a2&b2)。

验题人的神仙做法是维护一个 longlong，两个二进制位一组，01 代表确定为 0，10代表确定为 1，11 代表都可以，00 代表不合法，维护的时候直接按位与即可。时间复杂度 O(mq)，期望得分 15 分。

子任务 5：

考虑 n 只有 1，可以开一个线段树维护每个位置的字符是什么，pushup的时候操作一下即可。时间复杂度 O(q logm)，期望得分 15 分。

子任务 6：

世界上没有什么事情是开一棵线段树不能解决的。如果有，那就开 30 棵。时间复杂度 O(nq logm)，期望得分 10 分。

子任务 7：

考虑用一棵线段树维护子任务 4 中的状压信息，通过位运算可以把 n 省掉，于是总复杂度 O(nq + qlogm)，期望得分 30 分。

#include <cstdio>

template <typename T>

inline void qr(T &x) {

  char ch = getchar(), lst = ' ';

  while ((ch > '') || (ch < '')) lst = ch, ch=getchar();

  while ((ch >= '') && (ch <= '')) x = (x << ) + (x << ) + (ch ^ ), ch = getchar();

  if (lst == '-') x = -x;

}

const int maxn = ;

int n, m, q;

char s[maxn][];

#ifdef ONLINE_JUDGE

int Ans;

#endif

struct Tree {

  Tree *ls, *rs;

  int l, r, x/*int1*/, y/*int2*/;

  bool leg;//判断 

  Tree() {

    ls = rs = NULL;

    l = r = x = y = ;

    leg = true;

  }

  void pushup() {

    if (!(this->ls->leg && this->rs->leg)) {//左右子树都不合法

      this->leg = false;

    } else {

      if ((this->ls->x & this->rs->x) & (this->ls->y ^ this->rs->y)) {

          //只有当左右儿子对应位置是否全为1或0都相同并且左右儿子对应的y不相同时，显然不合法

        this->leg = false;

      } else {

        this->leg = true;

        this->x = this->ls->x | this->rs->x;

        this->y = this->ls->y | this->rs->y;

      }

    }

  }

};

Tree *rot;

void ReadStr(char *p);

void Update(const int x);

void Query(const int l, const int r);

void update(Tree *const u, const int p);

Tree query(Tree *u, const int l, const int r);

void build(Tree *const u, const int l, const int r);

int main() {

  freopen("lin.in", "r", stdin);

  freopen("lin.out", "w", stdout);

  qr(n); qr(m); qr(q);

  for (int i = ; i <= m; ++i) {

    ReadStr(s[i] + );//读入一串字符串的神仙操作

  }

  build(rot = new Tree, , m);

  int opt, l, r;

  while (q--) {

    opt = ; qr(opt);

    if (opt == ) {

      l = r = ; qr(l); qr(r);

      Query(l, r);

    } else {

      l = ; qr(l);

      ReadStr(s[] + );

      Update(l);

    }

  }

#ifdef ONLINE_JUDGE

  printf("%d\n", Ans);

#endif

  return ;

}

void ReadStr(char *p) {

  do *p = getchar(); while ((*p != '') && (*p != '') && (*p != '?'));

  do *(++p) = getchar(); while ((*p == '') || (*p == '') || (*p == '?'));

  *p = ;

}

void build(Tree *const u, const int l, const int r) {

  if ((u->l = l) == (u->r = r)) {//叶节点

    for (int i = ; i <= n; ++i) {//直接扫描记录即可

      if (s[l][i] != '?') {

        u->x |=  << i;

        if (s[l][i] == '') {

          u->y |=  << i;

        }

      }

    }

  } else {//不是叶节点，递归建树；

    int mid = (l + r) >> ;

    build(u->ls = new Tree, l, mid);

    build(u->rs = new Tree, mid + , r);

    u->pushup();

  }

}

Tree query(Tree *u, const int l, const int r) {

  if ((u->l > r) || (u->r < l)) return Tree();

  if ((u->l >= l) && (u->r <= r)) return *u;

  Tree _ret;

  auto ll = query(u->ls, l, r), rr = query(u->rs, l, r);

  _ret.ls = &ll; _ret.rs = &rr;

  _ret.pushup();

  return _ret;

}

void Query(const int l, const int r) {

  auto _ret = query(rot, l, r);

  if (!_ret.leg) {

#ifndef ONLINE_JUDGE

    puts("");

#endif

  } else {

    int ans = ;

    for (int i = ; i <= n; ++i) if (!(_ret.x & ( << i))) {

      ans <<= ;

    }

#ifdef ONLINE_JUDGE

    Ans ^= ans;

#else

    printf("%d\n", ans);

#endif

  }

}

void update(Tree *u, const int p) {

  if (u->ls) {

    if (u->ls->r >= p) {

      update(u->ls, p);

    } else {

      update(u->rs, p);

    }

    u->pushup();

  } else {

    *u = Tree();

    u->l = u->r = p;

    for (int i = ; i <= n; ++i) {

      if (s[][i] != '?') {

        u->x |=  << i;

        if (s[][i] == '') {

          u->y |=  << i;

        }

      }

    }

  }

}

void Update(const int x) {

  update(rot, x);

}

我尽力了，但我真的没有全看懂

end-

巴特西

【6.24校内test】T3 棠梨煎雪

最新文章

热门文章