解题报告 P4231 三步必杀

题目内容

P4231

大意:区间加等差,最后询问整个序列的异或和以及最大值

解题思路

区间加等差其实就是差分序列区间加常数,两端特殊修改。

但是注意到这里的数据范围是 1e7,线段树卡不过去,而且询问是在最后询问的,因此可以直接上二阶差分。

模拟一段区间加等差的过程:给 [3,6] 加上首项为 3,末项为 9 的等差数列:

0  0  0  0  0  0  0  0  这是原数列
0  0  3  5  7  9  0  0  这是加了等差数列之后的
0  0  3  2  2  2 -9  0  这是一阶差分
0  0  3 -1  0  0  -11 9 这是二阶差分

可见,我们如果要进行区间加等差的操作的话,需要在二阶差分上动 4 个点,分别是

d2[l]+=s;
d2[l+1]+=d-s;
d2[r+1]-=e+d;
d2[r+2]+=e;

其中 d 为公差,s 为首项,e 为末项。错误常发生于以为 d2[l+1]d2[r+1] 是不用修改的,但是实际上由于 s 可能不等于 d,故二阶差分的 l+1 处要进行处理。

最后,两次前缀和就可以还原出原序列,在还原的过程中可以顺便进行最大值查询和异或和操作。

总的复杂度 O(n+m),可以卡过去,如果是线段树的话是 O(m\log n+n),会被卡掉

要开 long long

#include <cstdio>
#include <cctype>
typedef long long ll;

const int maxn=1e7+5;
ll a[maxn],d1[maxn],d2[maxn];

inline ll read()
{
    char c = getchar();
    ll s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

int main()
{
    int n=read(),m=read();
    ll l,r,s,e;
    while(m--)
    {
        l=read(),r=read(),s=read(),e=read();
        int d=(e-s)/(r-l);//得到公差
        d2[l]+=s;
        d2[l+1]+=d-s;
        d2[r+1]-=e+d;
        d2[r+2]+=e;
    }
    ll maxans=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        d1[i]=d1[i-1]+d2[i],a[i]=a[i-1]+d1[i];//还原
        maxans=maxans<a[i]?a[i]:maxans;
        ans^=a[i];
    }
    printf("%lld %lld\n",ans,maxans);
    return 0;
}

解题报告 P4868 Preprefix sum

题目内容

P4868

大意:维护一串序列,支持单点修改和前前缀和查询(\displaystyle\sum_{k=1}^i\sum_{j=1}^ka_j

解题思路

前前缀和,就是前缀和的前缀和,既然需要查询前前缀和,那么就可以想到维护序列的前缀和,查询的时候区间查询 [1,i],修改的时候由于修改一个特定位置的数,后面的所有前缀和都会被影响,所以相当于区间修改前缀和,区间修改区间查询,很容易想到使用线段树维护。

当然用差分处理了的树状数组也可以,但是线段树明显好理解。

要注意的细节:

  • 建线段树的时候记得是记录前缀和
  • 修改 a_ix 的时候相当于 (i,n] 的前缀和都要加上 x-a_i,所以 a_i 一定要存下来

代码:

#include <cstdio>
#include <cctype>
#define L (k<<1)
#define R (L|1)
#define M ((i+j)>>1)
typedef long long ll;

const int maxn=100005;
ll a[maxn],s[maxn],f[maxn<<2],tag[maxn<<2];

int n,m;

inline ll read()
{
    char c = getchar();
    ll s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

void build(int i,int j,int k)
{
    if(i==j)
    {
        a[i]=read();
        s[i]=s[i-1]+a[i];
        f[k]=s[i];
        return;
    }
    build(i,M,L);
    build(M+1,j,R);
    f[k]=f[L]+f[R];
    return;
}

inline void down(int i,int j,int k)
{
    f[L]+=tag[k]*(M-i+1ll);
    f[R]+=tag[k]*(ll)(j-M);
    tag[L]+=tag[k];
    tag[R]+=tag[k];
    tag[k]=0;
    return;
}

void modify(int i,int j,int l,int r,int k,int d)
{
    if(i>=l && j<=r)
    {
        f[k]+=d*(j-i+1ll);
        tag[k]+=d;
        return;
    }
    if(tag[k])
        down(i,j,k);
    if(l<=M)
        modify(i,M,l,r,L,d);
    if(r>M)
        modify(M+1,j,l,r,R,d);
    f[k]=f[L]+f[R];
    return;
}

ll ask(int i,int j,int l,int r,int k)
{
    if(i>=l && j<=r)
        return f[k];
    if(tag[k])
        down(i,j,k);
    ll ans=0;
    if(l<=M)
        ans+=ask(i,M,l,r,L);
    if(r>M)
        ans+=ask(M+1,j,l,r,R);
    return ans;
}

int main()
{
    n=read(),m=read();
    build(1,n,1);
    char opt[10];
    int i;
    while(m--)
    {
        scanf("%s %d",opt,&i);
        if(opt[0]=='M')
        {
            ll x=read();
            modify(1,n,i,n,1,x-a[i]);
            a[i]=x;
        }
        else
            printf("%lld\n",ask(1,n,1,i,1));
    }
    return 0;
}

解题报告 P1827 [USACO3.4]美国血统 American Heritage

题目内容

P1827

给定一二叉树的中序和先序遍历,求后序遍历

解题思路

与求先序排列的类似,思路都是找根然后递归求解。

注意到一个子树的先序遍历的第一个元素必然是这棵子树的根,因此可以通过在中序遍历中查找这个根来获知左右子树的大小然后分开递归左右子树

#include <iostream>
#include <string>
using namespace std;

void dfs(string f,string m)
{
    if(f.empty())
        return;
    int k=m.find(f[0]);
    dfs(f.substr(1,k),m.substr(0,k));
    dfs(f.substr(k+1,f.size()-k),m.substr(k+1));
    cout<<f[0];
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    string f,m;
    cin>>m>>f;
    dfs(f,m);
    return 0;
}

解题报告 P4170 [CQOI2007]涂色

题目内容

P4170

大意:给出一块木板,要求涂色,后覆盖前,求最小笔刷数

解题思路

区间 dp。

不难发现,定义状态 f_{i,j}[i,j] 的最少次数可以满足最优子结构和无后效性,具体就是要看如何转移。

枚举端点 ij,发现如果有 s_i=s_j 的话,相当于第一次涂色的时候多涂一格,转移方程为 f_{i,j}=\min(f_{i,j-1},f_{i+1,j})

但如果 s_i\neq s_j 的话,说明没办法直接多涂一格,需要枚举中间的断点 k,由于枚举 k 的过程中必然能找到一种划分方式使得总的涂色次数加起来最优,因此只需要将断点左右加起来取最小值就可以得到该区间的答案,故有如下方程:

f_{i,j}=\min_{k\in[i,j)} \lbrace f_{i,k}+f_{k+1,j}\rbrace

#include <cstdio>
#include <cstring>

int f[55][55];

inline int min(int a,int b)
{
    return a<b?a:b;
}

int main()
{
    int n;
    char s[55];
    scanf("%s",s+1);
    n=strlen(s+1);
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)
        f[i][i]=1;
    for(int l=1;l<n;l++)
        for(int i=1,j=l+1;j<=n;i++,j++)
            if(s[i]==s[j])
                f[i][j]=min(f[i][j-1],f[i+1][j]);
            else
                for(int k=i;k<j;k++)
                    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
    printf("%d\n",f[1][n]);
    return 0;
}

解题报告 P4933 大师

题目内容

P4933

大意:求等差子序列总个数(包括长度为 1 或 2 的)

解题思路

dp,先考虑状态的设计和转移。

不难发现,如果我们考虑第 i 个数,如果第 i 个数可以接上前面的某一个等差数列,那么答案就会增加前面等差数列的长度再加一,所以考虑将以 i 结尾的等差数列存进状态里面。

我们可以令 f_i 表示以 i 结尾的等差数列的长度,但是发现貌似不同的公差会造成不同的后效性,所以我们需要将公差也存储下来,即 f_{i,j} 表示以 i 结尾,公差为 j 的最长等差数列的长度,由于公差可能为负,故处理时要加上 20000 防止下标出锅

转移:

f_{i,k}\leftarrow f_{i,k}+f_{j,k}+1

同时 ans+=f[j][k]+1

注意取模就可以了

#include <cstdio>
#include <cctype>
using namespace std;

const int maxn=1005,mod=998244353;
int n,h[maxn];
int ans,f[maxn][20005<<1];

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        h[i]=read();
    for(int i=1;i<=n;i++)
    {
        ans++;
        for(int j=1;j<i;j++)
        {
            int cur=h[i]-h[j]+20000;
            f[i][cur]+=f[j][cur]+1;
            f[i][cur]%=mod;
            ans+=f[j][cur]+1;
            ans%=mod;
        }
    }
    printf("%d\n",ans%mod);
    return 0;
}

解题报告 P2831 愤怒的小鸟

题目内容

P2831

大意:(0,0) 处有一弹弓,有 n 只猪猪,弹弓发出的炮弹路径为 y=ax^2+bx,其中 a > 0,求最少的抛物线数量打掉所有猪猪。

解题思路

一开始的暴搜调了我很久,但是最后都只有 60 分,具体的思路就是两只两只的枚举猪猪,如果发现两只可以构成合法抛物线,那么就清算抛物线上的其他猪猪然后继续暴搜,但是复杂度比较高。状态的存储使用状压。

#include <cstdio>
#include <cmath>
#include <bitset>
#include <cstring>
#include <iostream>
#define EPS 1e-6
using namespace std;

class P2831
{
private:

    struct point
    {
        double x,y;
    };

    int ans;
    int n,m;
    point pig[19];
    int vis[1<<18];


    inline bool ison(point p,double a,double b)//判断点在不在抛物线上
    {
        return fabs(a*p.x*p.x+b*p.x-p.y)<=EPS;
    }

    inline bool calc(point d1,point d2,double &a,double &b)//计算过(x1,y1)和(x2,y2)的抛物线表达式
    {
        if(fabs(d1.x-d2.x)<EPS)
        {
            //cout<<"debug1"<<endl;
            return false;
        }
        if(fabs(d2.y/d2.x-d1.y/d1.x)<EPS)
        {
            //cout<<"debug2"<<endl;
            return false;
        }
        b=(d1.y*d2.x*d2.x/d1.x/d1.x-d2.y)/((d2.x*d2.x/d1.x)-d2.x);
        a=(d1.y-b*d1.x)/d1.x/d1.x;
        //cout<<"a:"<<a<<" b:"<<b<<endl;
        if(a>0)
            return false;
        return true;
    }

    void dfs(int cur,int opt,int step)
    {
        vis[cur]=min(vis[cur],step);
        //cout<<"step:"<<step<<' '<<cur<<endl;
        if(cur==(1<<n)-1)
        {
            ans=min(ans,step);
            return;
        }
        if(opt==1 && step>n/3.0+1)
            return;
        if(step>=ans || step>vis[cur])
            return;
        for(int i=0;i<n;i++)
        {
            bool flag=0;
            int now=cur;
            if(now&(1<<i))
                continue;
            now|=(1<<i);
            for(int j=0;j<n;j++)
            {
                int now2=now;
                if(now2&(1<<j))
                    continue;
                double a,b;
                if(!calc(pig[i],pig[j],a,b))
                    continue;
                flag=1;
                now2|=(1<<j);
                for(int k=0;k<n;k++)
                    if((!now2&(1<<k)) && ison(pig[k],a,b))
                        now2|=(1<<k);
                dfs(now2,opt,step+1);
            }
            if(!flag)
                dfs(now,opt,step+1);
        }
    }

public:

    int solve()
    {
        ans=0x3f3f3f3f;
        memset(vis,0x3f,sizeof(vis));
        scanf("%d %d",&n,&m);
        for(int i=0;i<n;i++)
            scanf("%lf %lf",&pig[i].x,&pig[i].y);
        dfs(0,m,0);
        return ans;
    }
};

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        P2831 a;
        printf("%d\n",a.solve());
    }
    return 0;
}

于是我放弃了调暴搜,在题解区发现了一种神奇的东西叫状压 dp,用 f_i 表示状态 i 需要的最少抛物线条数。同时抛物线预处理成能通过的点的集合,记作 para_j,转移方程如下:

f_{i|para_j}=\min(f_{i|para_j},f_i+1)

预处理抛物线的时候首先枚举单个的猪猪,因为每只猪猪必过一个抛物线,然后再枚举第二个猪猪,如果能构成的抛物线合法的话再将其他在抛物线上的点加入即可。

关于数学:要求过 (x_1,y_1)(x_2,y_2) 的抛物线 y=ax^2+bxab 的值,列出来式子然后消元即可。

b=\frac{\frac{y_1x^2_2}{x_1^2}-y_2}{\frac{x_2^2}{x_1}-x_2}\
a=\frac{y_1-bx_1}{x_1^2}

代码如下:

#include <cstdio>
#include <cmath>
#include <cstring>
#define EPS 1e-6
using namespace std;

struct point
{
    double x,y;
};

int n,m,para[200],f[1<<18],cnt;

inline bool ison(point p,double a,double b)//判断点在不在抛物线上
{
    return fabs(a*p.x*p.x+b*p.x-p.y)<=EPS;
}

inline bool calc(point d1,point d2,double &a,double &b)//计算过(x1,y1)和(x2,y2)的抛物线表达式
{
    if(fabs(d1.x-d2.x)<EPS)//判断横坐标相等的情况
        return false;
    if(fabs(d2.y/d2.x-d1.y/d1.x)<EPS)//判断构不成抛物线的情况
        return false;
    b=(d1.y*d2.x*d2.x/d1.x/d1.x-d2.y)/((d2.x*d2.x/d1.x)-d2.x);
    a=(d1.y-b*d1.x)/d1.x/d1.x;
    if(a>0)
        return false;
    return true;
}

inline int min(int a,int b)
{
    return a<b?a:b;
}

void pre()//预处理
{
    scanf("%d %d",&n,&m);
    memset(f,0x3f,sizeof(f));//先赋极大值
    cnt=0;//cnt为抛物线的数量
    point pig[18];
    for(int i=0;i<n;i++)
        scanf("%lf %lf",&pig[i].x,&pig[i].y);
    for(int i=0;i<n;i++)
    {
        para[cnt++]=1<<i;//先加入一个新抛物线
        for(int j=i+1,vis=0;j<n;j++)//定义的vis是枚举过的小猪,避免重复
        {
            if((1<<j)&vis)//判重
                continue;
            double a,b;
            if(!calc(pig[i],pig[j],a,b))//如果不合法
                continue;
            para[cnt]=1<<i;//先暂时加进去只有第一只猪猪的抛物线
            for(int k=j;k<n;k++)//然后枚举加新点进去
            {
                if(ison(pig[k],a,b))//如果第k只猪猪在上面
                {
                    vis|=(1<<k);//更新vis数组
                    para[cnt]|=(1<<k);//更新抛物线
                }
            }
            cnt++;//然后抛物线的条数要加一
        }
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        pre();
        f[0]=0;
        for(int i=0;i<(1<<n);i++)//枚举每个状态
            for(int j=0;j<cnt;j++)//枚举每一条抛物线
                f[i|para[j]]=min(f[i|para[j]],f[i]+1);//状态转移
        printf("%d\n",f[(1<<n)-1]);//输出答案
    }
    return 0;
}

解题报告 P1336 最佳课题选择

题目内容

P1336

一共写 n 篇论文,一共 m 个课题,对于第 i 个课题如果写 x 篇则需花费 A_i\times x^{B_i} 的时间,求最小时间

解题思路

泛化物品的背包,价值随着分给他的大小而变化。由于数据范围比较小,所以直接枚举第 i 个课题选择的数量 k 即可,转移方程:

f_{i,j}=\min(f_{i,j},f_{i-1,j-k}+A_i\times k^{B_i})

然后边界就是 f_{1,i}=A_1\times i^{B_1},最后使用滚动数组优化一下即可

不开 long long 见祖宗

代码:

#include <cstdio>
#include <cctype>
#include <cstring>
typedef long long ll;

ll n,m,a[25],b[25],f[205];

inline ll read()
{
    char c = getchar();
    ll s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline ll min(ll a,ll b)
{
    return a<b?a:b;
}

inline ll ksm(ll base,ll p)//写了个快速幂
{
    ll ans=1;
    for(;p;p>>=1)
    {
        if(p&1)
            ans*=base;
        base*=base;
    }
    return ans;
}

int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
        a[i]=read(),b[i]=read();
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++)
        f[i]=a[1]*ksm(i,b[1]);
    //边界
    for(int i=2;i<=m;i++)
        for(int j=n;j>=0;j--)
            for(int k=0;k<=j;k++)
                f[j]=min(f[j],f[j-k]+a[i]*ksm(k,b[i]));//进行转移
    printf("%lld\n",f[n]);
    return 0;
}

解题报告 P1941 飞扬的小鸟

虽说 AFO 了,但是我做下题总还是可以的吧我不想学文化课

题目内容

flappy bird 的改编题,地图为 n\times m,分别是长和高。每秒钟内可以点击多次屏幕,在第 i 位置处点击一次屏幕可以在下一秒上升 x_i 格,不点击屏幕下降 y_i 格,不能碰到管道或者触底(高度为 0),求如果可以通过游戏的最小点击屏幕次数或不可以通过游戏的话最多通过的管道数。

解题思路

考虑 f_{i,j} 表示到达 (i,j) 的最少点击次数,如不能到达用 INF 表示。

于是可以将状态的转移抽象成背包,每次可以选择点击无数次或者下降一次,转移方程如下:

f_{i,j}=\min(f_{i,j-x_i},f_{i-1,j-x_i})+1

这是上升来的,意义就是从前一秒的状态点击一次或者从当前秒再点击一次取最优

f_{i,j}=\min(f_{i,j},f_{i-1,j+y_i})

这就是下降来的

这题需要注意的地方:

  • 上升的过程是一个完全背包(可以点击屏幕无限次),下降的是 0-1 背包
  • 有可能会飞出去(大于 m),这个时候要特判,将其还原

我使用了结构体封装地图的每一格,包含了是否有管道,下降/上升的高度以及最高能通过的高度以及最低能通过的高度。

最后统计答案的时候如果不能过,那就从最后往前寻找第一个能过的点,然后统计前面有多少管道

代码:

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define a(x) game[x]
using namespace std;

const int maxn = 10005, INF = 0x3f3f3f3f;
int n, m, k;
int f[maxn][3005];

struct node
{
    int x, y, high, low;
    bool flag;
} game[maxn];

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

int main()
{
    n = read(), m = read(), k = read();
    for (int i = 1; i <= n; i++)
    {
        a(i).x = read(), a(i).y = read();
        a(i).high = m, a(i).low = 1;
    }
    int p, l, h;
    for (int i = 1; i <= k; i++)
    {
        p = read(), l = read(), h = read();
        a(p).flag = 1,
        a(p).high = h - 1,
        a(p).low = l + 1;
    }
    memset(f, INF, sizeof(f));
    for (int i = 1; i <= m; i++)
        f[0][i] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = a(i).x + 1; j <= m + a(i).x; j++)
            f[i][j] = min(f[i][j], min(f[i][j - a(i).x] + 1, f[i - 1][j - a(i).x] + 1));
        for (int j = m; j <= m + a(i).x; j++)
            f[i][m] = min(f[i][m], f[i][j]);
        for (int j = 1; j <= m - a(i).y; j++)
            f[i][j] = min(f[i][j], f[i - 1][j + a(i).y]);
        for (int j = 1; j < a(i).low; j++)
            f[i][j] = INF;
        for (int j = m; j > a(i).high; j--)
            f[i][j] = INF;
    }
    int ans = INF;
    for (int i = 1; i <= m; i++)
        ans = min(ans, f[n][i]);
    if (ans < INF)
    {
        printf("1\n%d\n", ans);
        return 0;
    }
    for (int i = n - 1; i >= 1; i--)
        for (int j = 1; j <= m; j++)
            if (f[i][j] < INF)
            {
                ans = 0;
                for (int t = 1; t <= i; t++)
                    if (a(t).flag)
                        ans++;
                printf("0\n%d\n", ans);
                return 0;
            }
}

解题报告 P5524 [Ynoi2012]NOIP2015洋溢着希望

题目内容

P5524

大意:维护一个序列 a,使其支持以下操作:

  • 给定 lr,求 \displaystyle\sum_{i=l}^r\sin(a_i)
  • 给定 lrv,让 [l,r] 中的每一个数加 v

解题思路

终于有一道我可以做的 Ynoi 了 qwqwq

最简单的 Ynoi,没有之一,像我这种只会线段树的 sb 都可以切了它 qwq

观察这题,发现要求维护的是 \sum\sin(a_i),而我们需要进行区间加某数的操作,所以考虑对 \sum\sin(a_i+v) 进行展开:

\begin{aligned}
&\sum_{i=l}^r\sin(a_i+v)\
=&\sum_{i=l}^r(\sin a_i\cos v+\sin v\cos a_i)\
=&\cos v\sum_{i=l}^r\sin a_i+\sin v\sum_{i=l}^r\cos a_i
\end{aligned}

所以我们需要维护两棵线段树,一棵维护 \sum\sin a_i,一棵维护 \sum\cos a_i,而涉及到 \sum\cos a_i 的修改怎么办呢?见下

\begin{aligned}
&\sum_{i=l}^r\cos(a_i+v)\
=&\sum_{i=l}^r(\cos a_i\cos v-\sin a_i\sin v)\
=&\cos v\sum_{i=l}^r\cos a_i-\sin v\sum_{i=l}^r\sin a_i
\end{aligned}

所以两个要同时修改,要建立临时变量来存储之前的 \sum\sin a_i\sum\cos a_i。然后为了优化常数不被卡,每次修改的时候要预处理 \sin v\cos v,不然会被卡。

lazytag 要开 long long,不然在玄学的在 line 几万处 WA

#include <cstdio>
#include <cctype>
#include <cmath>
#define L (k<<1)
#define R (L|1)
#define M (i+j>>1)
typedef long long ll;

const int maxn=2e5+5;
double fsin[maxn<<2],fcos[maxn<<2];
int n,m;
ll tag[maxn<<2];

inline ll read()
{
    char c=getchar();
    ll s=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
        s=10*s+c-'0',c=getchar();
    return s;
}

void build(int i,int j,int k)
{
    if(i==j)
    {
        int x=read();
        fsin[k]=sin(x);
        fcos[k]=cos(x);
        return;
    }
    build(i,M,L);
    build(M+1,j,R);
    fsin[k]=fsin[L]+fsin[R];
    fcos[k]=fcos[L]+fcos[R];
    return;
}

void down(int i,int j,int k)
{
    double lsin=fsin[L],rsin=fsin[R],lcos=fcos[L],rcos=fcos[R];
    double sine=sin(tag[k]),cosi=cos(tag[k]);
    fsin[L]=lsin*cosi+lcos*sine;
    fcos[L]=lcos*cosi-lsin*sine;
    tag[L]+=tag[k];
    fsin[R]=rsin*cosi+rcos*sine;
    fcos[R]=rcos*cosi-rsin*sine;
    tag[R]+=tag[k];
    tag[k]=0;
    return;
}

void modify(int i,int j,int l,int r,int k,int d)
{
    if(i>=l && j<=r)
    {
        double ssin=fsin[k],ccos=fcos[k];
        double sine=sin(d),cosi=cos(d);
        fsin[k]=ssin*cosi+ccos*sine;
        fcos[k]=ccos*cosi-ssin*sine;
        tag[k]+=d;
        return;
    }
    if(tag[k])
        down(i,j,k);
    if(l<=M)
        modify(i,M,l,r,L,d);
    if(r>M)
        modify(M+1,j,l,r,R,d);
    fsin[k]=fsin[L]+fsin[R];
    fcos[k]=fcos[L]+fcos[R];
    return;
}

double ask(int i,int j,int l,int r,int k)
{
    if(i>=l && j<=r)
        return fsin[k];
    if(tag[k])
        down(i,j,k);
    double ans=0;
    if(l<=M)
        ans+=ask(i,M,l,r,L);
    if(r>M)
        ans+=ask(M+1,j,l,r,R);
    return ans;
}

int main()
{
    n=read();
    build(1,n,1);
    m=read();
    int t,l,r,v;
    while(m--)
    {
        t=read(),l=read(),r=read();
        if(t==1)
        {
            v=read();
            modify(1,n,l,r,1,v);
        }
        else
            printf("%.1f\n",ask(1,n,l,r,1));
    }
    return 0;
}

解题报告 P2758 编辑距离

题目内容

P2758

给定三种字符串操作,分别是插入,修改和删除(都针对一个字符),求字符串 a 变化为 b 的最小操作次数

解题思路

经典的 dp 问题,考虑如何设计状态使得状态不具后效性并且满足最优子结构。不妨假设两个字符串的下标都从 1 开始,并定义 f_{i,j} 为字符串 1 的前 i 位转为字符串 2 的前 j 位所需的最少操作次数。不难发现这样定义的状态满足上述性质,所以开始设计转移。

上面提到有三种基本的操作,因此考虑怎样操作能使得次数最小化。如果是在串 1 的后面添加字符,则状态由 f_{i,j-1}+1 转移而来,如果是删除字符,则由 f_{i-1,j}+1 转移而来,如果是改变字符,那就从 f_{i-1,j-1}+1 转移而来。特别的,如果当前涉及到的这两个字符串的对应位是相同的,改变字符的操作就不需要加一了。而为了使当前的 f_{i,j} 最优,我们需要将前面所有能到达 f_{i,j} 的决策取最小值。转移方程如下:

定义变量 k,当 a_i=b_i 时,k=0,反之 k=1,方程如下:

f_{i,j}=\min(f_{i-1,j}+1,f_{i,j-1}+1,f_{i-1,j-1}+k)

写出了方程,要注意的是边界条件。所有的 f_{i,0} 都为 i,所有的 f_{0,j} 都为 j。我们要输出的是 f_{l_1,l_2},搞清楚以上几点,就可以写代码了

#include <cstdio>
#include <cstring>

char s1[2010],s2[2010];
int f[2010][2010];

inline int min(int a,int b)
{
    return a<b?a:b;
}

int main()
{
    scanf("%s",s1+1);
    scanf("%s",s2+1);
    int l1=strlen(s1+1),l2=strlen(s2+1);//都是为了字符串下标做的处理
    memset(f,0x3f3f3f3f,sizeof(f));
    for(int i=0;i<=l1;i++)
        f[i][0]=i;
    for(int i=0;i<=l2;i++)
        f[0][i]=i;
    for(int i=1;i<=l1;i++)
        for(int j=1;j<=l2;j++)
        {
            if(s1[i]!=s2[j])//如果对应位不相等
                f[i][j]=min(f[i-1][j-1]+1,min(f[i-1][j]+1,f[i][j-1]+1));
            else
                f[i][j]=min(f[i-1][j-1],min(f[i-1][j]+1,f[i][j-1]+1));
        }
    printf("%d\n",f[l1][l2]);
    return 0;
}