题目传送门

题意：给两串字符串，操作1：替换其中一个字符串的某个位置的字符 操作2：查询从p开始相等的最长连续长度

分析：树状数组可以维护一个区间内公共长度(连续)的情况，查询时用二分查找最远的端点即可。还可以用线段树去做，线段树能处理的问题很多，这题只要往右区间合并就行了。

收获：1.线段树的区间合并又做一题(虽然我写的还没AC) 2. 树状数组写起来方便又奇效！

代码1(树状数组)：

/************************************************

* Author        :Running_Time

* Created Time  :2015-8-26 9:46:09

* File Name     :I.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e6 + 10;

const int Q = 1e5 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

char s1[N], s2[N];

int L;

struct BIT   {

    int c[N];

    void init(void) {

        memset (c, 0, sizeof (c));

    }

    void updata(int i, int x)   {

        while (i <= L)   {

            c[i] += x;  i += (i & (-i));

        }

    }

    int query(int i)    {

        int ret = 0;

        while (i)   {

            ret += c[i];    i -= (i & (-i));

        }

        return ret;

    }

    int bsearch(int p, int l, int r)    {

        while (l <= r)  {

            int mid = (l + r) >> 1;

            if (query (mid) - query (p-1) == mid - p + 1)   l = mid + 1;

            else    r = mid - 1;

        }

        return l - p;

    }

}bit;

int main(void)    {

    int T, cas = 0; scanf ("%d", &T);

    while (T--) {

        scanf ("%s%s", s1 + 1, s2 + 1);

        int q;  scanf ("%d", &q);

        int len1 = strlen (s1 + 1), len2 = strlen (s2 + 1);

        L = min (len1, len2);

        bit.init ();

        for (int i=1; i<=L; ++i)    {

            if (s1[i] == s2[i]) bit.updata (i, 1);

        }

        printf ("Case %d:\n", ++cas);

        while (q--) {

            int op; scanf ("%d", &op);

            if (op == 1)    {

                int x, p;   char c; scanf ("%d%d %c", &x, &p, &c);

                ++p;

                if (p > L) continue;

                bool same = (s1[p] == s2[p]);

                if (x == 1) {

                    s1[p] = c;

                    if (same && s1[p] != s2[p])   bit.updata (p, -1);

                    else if (!same && s1[p] == s2[p])   bit.updata (p, 1);

                }

                else    {

                    s2[p] = c;

                    if (same && s1[p] != s2[p])   bit.updata (p, -1);

                    else if (!same && s1[p] == s2[p])   bit.updata (p, 1);

                }

            }

            else    {

                int p;  scanf ("%d", &p);

                ++p;

                if (p > L) {

                    puts ("0"); continue;

                }

                printf ("%d\n", bit.bsearch (p, p, L));

            }

        }

    }

    return 0;

}

代码2(线段树)：

/************************************************

* Author        :Running_Time

* Created Time  :2015-8-26 9:46:09

* File Name     :I.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e6 + 10;

const int Q = 1e5 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

char s1[N], s2[N];

struct ST   {

    int sum[N<<2];

    void push_up(int rt, int len)    {      //sum[rt<<1]表示从左子树线段左端点开始最长连续的公共的长度，如果全是公共的，

        if (sum[rt<<1] == len - (len >> 1)) sum[rt] = sum[rt<<1] + sum[rt<<1|1];        //合并右子树的线段长度

        else    sum[rt] = sum[rt<<1];

    }

    void build(int l, int r, int rt)    {

        if (l == r) {

            sum[rt] = s1[l] == s2[r] ? 1 : 0;

            return ;

        }

        int mid = (l + r) >> 1;

        build (lson);   build (rson);

        push_up (rt, r - l + 1);

    }

    void updata(int p, int c, int l, int r, int rt)    {

        if (l == r) {

            sum[rt] = c;  return ;

        }

        int mid = (l + r) >> 1;

        if (p <= mid)   updata (p, c, lson);

        else    updata (p, c, rson);

        push_up (rt, r - l + 1);

    }

    int query(int p, int l, int r, int rt)  {

        if (l == r) return sum[rt];

        int mid = (l + r) >> 1;

        if (p <= mid)   {

            int ret = query (p, lson);

            if (p + ret - 1 == mid) return ret + sum[rt<<1|1];

            else    return ret;

        }

        else    return query (p, rson);

    }

}st;

int main(void)    {

    int T, cas = 0; scanf ("%d", &T);

    while (T--) {

        scanf ("%s%s", s1 + 1, s2 + 1);

        int q;  scanf ("%d", &q);

        int len1 = strlen (s1 + 1), len2 = strlen (s2 + 1);

        int mn = min (len1, len2);

        st.build (1, mn, 1);

        printf ("Case %d:\n", ++cas);

        while (q--) {

            int op; scanf ("%d", &op);

            if (op == 1)    {

                int x, p;   char c; scanf ("%d%d %c", &x, &p, &c);

                ++p;

                if (p > mn) continue;                       //特殊情况特判

                if (x == 1) {

                    s1[p] = c;

                }

                else    {

                    s2[p] = c;

                }

                st.updata (p, (s1[p] == s2[p]), 1, mn, 1);

            }

            else    {

                int p;  scanf ("%d", &p);

                ++p;

                if (p > mn) {                               //特殊情况特判

                    puts ("0"); continue;

                }

                printf ("%d\n", st.query (p, 1, mn, 1));

            }

        }

    }

    return 0;

}

代码3(unAC)：

/************************************************

* Author        :Running_Time

* Created Time  :2015-8-26 9:46:09

* File Name     :I.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e6 + 10;

const int Q = 1e5 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

char s1[N], s2[N];

struct ST   {

    int sum[N<<2], lsum[N<<2], rsum[N<<2];

    void push_up(int rt, int len)    {

        lsum[rt] = lsum[rt<<1];

        rsum[rt] = rsum[rt<<1|1];

        sum[rt] = max (sum[rt<<1], sum[rt<<1|1]);

        if (lsum[rt] == len - (len >> 1))   lsum[rt] += lsum[rt<<1|1];

        if (rsum[rt] == len >> 1)   rsum[rt] += rsum[rt<<1];

        sum[rt] = max (rsum[rt<<1] + lsum[rt<<1|1], max (sum[rt<<1], sum[rt<<1|1]));

    }

    void build(int l, int r, int rt)    {

        if (l == r) {

            sum[rt] = lsum[rt] = rsum[rt] = s1[l] == s2[r] ? 1 : 0;

            return ;

        }

        int mid = (l + r) >> 1;

        build (lson);   build (rson);

        push_up (rt, r - l + 1);

    }

    void updata(int p, int c, int l, int r, int rt)    {

        if (l == r) {

            sum[rt] = lsum[rt] = rsum[rt] = c;  return ;

        }

        int mid = (l + r) >> 1;

        if (p <= mid)   updata (p, c, lson);

        else    updata (p, c, rson);

        push_up (rt, r - l + 1);

    }

    int query(int p, int l, int r, int rt)  {

        if (l == r) return sum[rt];

        int mid = (l + r) >> 1;

        if (p <= mid)   {

            if (p + rsum[rt<<1] - 1 >= mid)    return mid - p + 1 + query (p, rson);

            else    return query (p, lson);

        }

        else    return query (p, lson);

    }

}st;

int main(void)    {

    int T, cas = 0; scanf ("%d", &T);

    while (T--) {

        scanf ("%s%s", s1 + 1, s2 + 1);

        int q;  scanf ("%d", &q);

        int len1 = strlen (s1 + 1), len2 = strlen (s2 + 1);

        int mn = min (len1, len2);

        st.build (1, mn, 1);

        printf ("Case %d:\n", ++cas);

        while (q--) {

            int op; scanf ("%d", &op);

            if (op == 1)    {

                int x, p;   char c; scanf ("%d%d %c", &x, &p, &c);

                if (p + 1 > mn) continue;

                if (x == 1) {

                    s1[p+1] = c;

                }

                else    {

                    s2[p+1] = c;

                }

                st.updata (p+1, (s1[p+1] == s2[p+1]), 1, mn, 1);

            }

            else    {

                int p;  scanf ("%d", &p);

                if (p + 1 > mn) {

                    puts ("0"); continue;

                }

                printf ("%d\n", st.query (p + 1, 1, mn, 1));

            }

        }

    }

    return 0;

}

　　

最新文章

  1. CyclicBarrier在多线程同步运行后相互访问的问题。
  2. .NET的EF框架中：在应用程序配置文件中找不到名为&ldquo;&rdquo;的连接字符串问题
  3. 【JAVA】Quartz 任务调度和异步执行器
  4. putExtra方法
  5. spoj LCMSUM sigma(lcm(i,n));
  6. vi 技巧
  7. protractor protractor.conf.js [launcher] Process exited with error code 1 undefined:1190
  8. String StringBuffer StringBuilder （转）
  9. c#入门系列——类和对象的代码实现
  10. kettel的stream lookup报错
  11. js数组中两个有相同删除一个
  12. WIndows下将文件夹映射为磁盘
  13. golang统计出其中英文字母、空格、数字和其它字符的个数
  14. 食物链--poj1182（并查集含有关系）
  15. ABAP-ALV详解
  16. plsql oracle client没有正确安装（plsql连接远程数据库）
  17. 搜索引擎Lucene之皮毛
  18. Linux入门第二天——基本命令入门（中）
  19. java状态模式
  20. hdu 1281 棋盘游戏 (二分匹配)

热门文章

  1. Openwrt 安装软件到U盘或硬盘
  2. atomic原子操作
  3. ExpandableListView的使用以及信息的高亮显示
  4. sqlzoo练习答案--SELECT within SELECT Tutorial
  5. Windows——cmd findstr 字符串查找增强使用说明
  6. Web安全漏洞及攻击
  7. Lnixu Bash
  8. Xcode6 设置LaunchImage图标
  9. Android开发pool解析xml
  10. HTML form表单的默认提交方式