HGOI7.26集训题解

2019-04-14 17:59发布生成海报

站内文章 / 模拟电子

16696 0

class="markdown_views prism-github-gist">

题解

今天第一天和二中的神仙在一起做题…但是本蒟蒻只能在电脑前看着北大神仙打架啊……人家AK我60……对OI丧失信心。
这是一套连lzw4896s都不怎么会的神仙题。

第一题——第一题（diyiti）<——你没有看错

【题目描述】

给定两个01串，S,T(下标从0开始）。

支持如下3种操作：

    修改S第i位的字符，即0->1,1->0.

    修改T第i位的字符，即0->1,1->0.

    查询S[a..a+l-1],T[b..b+l-1]的相似度。

相似度定义如下:

s,t两个字符串的相似度=sigma_{i=0}^{|s|-1} sim(s[i],t[i])

sim(a,b) 有四个参数p_{0,0},p_{0,1},p_{1,0},p_{1,1}。 sim(a,b)的返回值为p_{a,b}。

输入 第一行一个非空字符串S

第二行一个非空字符串T

第三行一个操作个数Q

接下来Q行，每行为”1 i”,”2 i”或”3 a b l p_{0,0} p_{0,1} p_{1,0} p_{1,1}”

输出 若干行，每行对应每个3操作的答案。

样例输入
1010
6
3 0 0 4 1 2 3 4
1 1
3 0 1 3 4 3 7 6
2 2
3 1 0 2 4 5 3 4
3 1 0 3 8 8 8 8
样例输出
10 19 7 24
提示
【数据范围】

10%, |S|,|T|<=1000,Q<=1000

10%, |S|,|T|<=50000,Q<=50000,3操作的p值都为1

10%, |S|,|T|<=50000,Q<=50000,所有操作为3操作且a,b,l相同

20%, |S|,|T|<=50000,Q<=50000,3操作的a,b值为0

50%, |S|,|T|<=100000,Q<=100000,0<=p<=50,由于数据随机生成，可以默认3操作l的期望为|S|/6

题目的前50%的数据比较水….所以裸暴力可以拿到（难道不是 $O (q n)$ ？？？）
题目的80%的数据比较一般，可以快读优化得到（后悔没有打快读orz）
对于最后面的两个点。只能说比较神仙了。完全没有板子。
由于匹配度与区间内的1的个数（或者说0的个数）有关所以可以利用压位和位运算来处理。
不保守的情况下，就来先压缩20位。
先将前20位所有情况下的二进制的1的个数递推求好。
再来处理每一个串，以任意位置为开头的20位的所压缩的数记录好。
更新时需要连续更新有关的20位。
查询时类似于分块，一段段地进行查询。对于散块的情况，可以直接暴力，对于整块的情况，只要将上下两端异或一下然后数1就可以了，而这里的1的个数已经处理好了，每块 $O (1)$ 的查询时间。
这样子大概就可以水过了。
但却实，数据可能比较水。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
void fff(){
    freopen("diyiti.in","r",stdin);
    freopen("diyiti.out","w",stdout);
}
const int MAXN=100010;
char S[MAXN],T[MAXN];
int mi[22],v[1048576];
int s[MAXN],t[MAXN],si[MAXN],ti[MAXN],n,m;
int Q,ans=0,a,b,l;
int v0,v1,v2,v3;

int read(){
    int x=0;
    char ch;
    ch=getchar();
    while (ch<'0'||ch>'9'&&ch!='-') ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
void solve(int li,int ri,int len){
    if(len<20){
        for (int i=0;i<=len-1;i++){
            ans=ans+si[li+i]*v2+ti[ri+i]*v1;
            if((si[li+i]==1)&&(ti[ri+i]==1)) ans=ans+(v3-v1-v2);
        }
        return;
    }
    ans=ans+v[s[li]]*v2+v[t[ri]]*v1;
    ans=ans+v[s[li]&t[ri]]*(v3-v1-v2);
    solve(li+20,ri+20,len-20);
}
int main(){
    scanf("%s%s",S,T);
    n=strlen(S),m=strlen(T);
    mi[1]=1;
    for (int i=2;i<=20;i++) mi[i]=mi[i-1]*2;
    for (int i=0;i'0';
    for (int i=0;i<m;i++) ti[i]=T[i]-'0';
    for (int i=1;i<=2*mi[20]-1;i++) 
        v[i]=v[i/2]+(i%2);
    int sum=0;
    for (int i=n-1;i>=n-20;i--) sum=sum+mi[n-i]*si[i];
    s[n-20]=sum;
    for (int i=n-21;i>=0;i--){
        sum=sum/2;
        sum=sum+mi[20]*si[i];
        s[i]=sum;
    }
    sum=0;
    for (int i=m-1;i>=m-20;i--) sum=sum+mi[n-i]*ti[i];
    t[m-20]=sum;
    for (int i=m-21;i>=0;i--){
        sum/=2;
        sum=sum+mi[20]*ti[i];
        t[i]=sum;
    }
    scanf("%d",&Q);
    while (Q--){
        int tampo;
        tampo=read();
        if(tampo==1){
            int pos;
            pos=read();
            for (int i=pos;i>=pos-19;i--){
                if(i>=0) s[i]=s[i]^mi[i-pos+20];
            }
            si[pos]=1-si[pos];
            }
        if(tampo==2){
            int pos;
            pos=read();
            for (int i=pos;i>=pos-19;i--){
                if(i>=0) t[i]=t[i]^mi[i-pos+20];
            }
            ti[pos]=1-ti[pos];
        }
        if(tampo==3){
            a=read(),b=read(),l=read();
            v0=read(),v1=read(),v2=read(),v3=read();
            ans=l*v0;
            v1=v1-v0;
            v2=v2-v0;
            v3=v3-v0;
            solve(a,b,l);
            printf("%d
",ans);
        }
    }
}

这个算法确实比较难想到…所有人都在想区间，反而没有人想到分块压位了….

第二题——第二题（dierti）

【题目描述】

 询问如下多重集（数字可以重复的集合）的个数：

这个集合中有n个数字，每个数字在1..L之间，n为偶数。

这n个数字能分成n/2组，使得每组有两个数，且这两个数的积不超过c。

答案很大，对10^9+7取模。

输入 一行三个正整数，n,L,c

输出 一个整数，答案

样例输入
4 10 10
样例输出
107
提示
【数据范围】

10%, n=2,L<=1000,c<=1000

20%, n<=8,L<=10,c<=10

20%, n<=100,L<=100,c<=100

10%, n<=100,L<=500,c<=500

40%, n<=2000,L<=2000,c<=2000

其实暴力打对了可以打30的但手残，没有打对。10分。
看这个最开始以为是数位dp或者是组合题。但真的没有先到是纯的dp。
讲一下方程吧… $f [i] [j] [k]$ 表示第i组一对为 $(j, k)$ 的方案数。
则 $f [i] [j] [k] = f [i - 1] [j - x] [k - y]$ 表示上一组为 $(j - x, k - y)$ 。
OK那这个方程就是五维的dp了。但用脚想想就知道是不可能吧！
那需要进行压缩。
记 $g [i] [j] [k] = s u m (f [i + 1] [j] [k])$ ， $s [i] [j] [k] = s u m (f [i + 1] [j - x] [k + x])$ 作为前面的前缀和。

f [i] [j] [k] = \sum_{x, y}^{x \leq j, y \geq k} f [i - 1] [x] [y]

那么就可以得出 $f [i] [j] [k] = s [i - 1] [j] [k]$ ，因为当前状态是所有上一步当前状态的情况数总和。
那么就可以推出:
$g [i] [j] [k] = g [i] [j] [k + 1] + f [i] [j] [k]$
$s [i] [j] [k] = s [i] [j - 1] [k] + g [i] [j] [k]$
由于需要考虑重复的问题（是个集合，无序）那么就要保证不重复了。从 $a 1, a n, a 2 a n - 1 . . . " role="presentation"> a 1, a n, a 2$

HGOI7.26集训题解

题解

第一题——第一题（diyiti）<——你没有看错

第二题——第二题（dierti）

Ta的文章更多 >>

热门文章