#include <iostream>
#include <string>

using namespace std;

string a,b;
int cnt;

int main()
{
    cin>>a>>b;
    for(int i=0;i<=(int)a.size();i++)
    {
        if(a[i]!=b[i])
        {
            cnt++;
            if(a[i]=='o') a[i]='*';
            else a[i]='o';
            if(a[i+1]=='o') a[i+1]='*';
            else a[i+1]='o';
        }
    }

    cout<<cnt;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

题目描述

假定有一个无限长的数轴，数轴上每个坐标上的数都是0。

现在，我们首先进行 n 次操作，每次操作将某一位置x上的数加c。

接下来，进行 m 次询问，每个询问包含两个整数l和r，你需要求出在区间[l, r]之间的所有数的和。

输入格式

第一行包含两个整数n和m。

接下来 n 行，每行包含两个整数x和c。

再接下里 m 行，每行包含两个整数l和r。

输出格式

共m行，每行输出一个询问中所求的区间内数字和。

数据范围

$-10^9\leq x\leq 10^9$
$1\leq n,m\leq 10^5$
$-10^9\leq l,r\leq 10^9$
$-10^4\leq c\leq 10^4$

输入样例

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例

8
0
5

看到求区间和，一下想到了 前缀和 ，用s[x]表示x之前的数的和就可以了，以值为下标但是这道题x的值域太大，会MLE

我们使用一个新的科技： 离散化

还是前缀和的思想，不过是把 s 数组里面的元素映射到几个比较小的值上面

用几个数字就开多大的 s 数组, n 和 m 的值较小,就不会MLE啦

怎么映射

我们可以用一个数组 num，存下来每个用到的数字

原来我们用 s[x] 表示小于等于x的和，现在我们在num里面二分出x,把下标记作t,此时就可以用s[t]代替原来的s[x]廖！

记录数字后要排个序+判个重

Time: $\mathcal{O}((n+m)log_2n)$
Code：

#include <iostream>
#include <algorithm>

using namespace std;

const int N=1e5+10;

int n, m;
int s[3*N];
int num[3*N];
pair<int, int> query[N], add[N];//要先记录数字，所以得玩离线的，先存下操作
int idx_num, idx_add, idx_query;

int find(int x)//二分
{
    int l = 1,r = idx_num;
    while(l<r)
    {
        int mid = l+r>>1;
        if(num[mid]<x) l = mid+1;
        else r = mid;
    }
    return l;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i<=n; i++)
    {
        int x, c;
        cin >> x >> c;
        num[++idx_num] = x;
        add[++idx_add] = {x, c};
    }
    for(int i = 1; i<=m; i++)
    {
        int l,r;
        cin >> l >> r;
        num[++idx_num] = l, num[++idx_num] = r;
        query[++idx_query] = {l,r};
    }

    //排序+判重
    sort(num+1, num+idx_num+1);
    idx_num = unique(num+1, num+idx_num+1)-num-1;

    for(int i = 1; i<=idx_add; i++)
    {
        int t = find(add[i].first);
        s[t] += add[i].second;//前缀和
    }

    for(int i = 1; i<=idx_num; i++) s[i] += s[i-1];

    for(int i = 1; i<=idx_query; i++)
    {
        int l = find(query[i].first),r = find(query[i].second);
        cout << s[r]-s[l-1] << endl;//直接用s[r]-s[l-1]表示普通的（MLE）s[query.first]-s[query.second-1]
    }

    return 0;
} 

本问题以C++为准

多重背包大家都很熟悉吧

它的优化从低到高如下

• 朴素 - 多重背包I
• 二进制 - 多重背包II
• 单调队列 - 多重背包III

显然，二进制优化的代码是跑不过 多重背包III 的

但是我们可以在代码前面开挂：

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

二进制优化版本加上挂之后平均跑 372ms
单调队列优化版本平均约跑 1499ms
单调队列优化版本加上挂之后平均约跑 860ms
注：以上均为3次测验的平均

可以明显看出，二进制版本加上挂比单调队列快很多
但是二进制版本不加挂是跑不过去的，单调队列却可以

???

所以事实证明算法的优劣不决定成败，高铁头才是王道

望解答开挂单调队列不如开挂二进制的原因

送关注一个

附录：

以下代码均由 yxc 大佬提供

单调队列优化代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20010;

int n, m;
int f[N], g[N], q[N];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        int v, w, s;
        cin >> v >> w >> s;
        memcpy(g, f, sizeof f);
        for (int j = 0; j < v; j ++ )
        {
            int hh = 0, tt = -1;
            for (int k = j; k <= m; k += v)
            {
                if (hh <= tt && q[hh] < k - s * v) hh ++ ;
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt -- ;
                q[ ++ tt] = k;
                f[k] = g[q[hh]] + (k - q[hh]) / v * w;
            }
        }
    }

    cout << f[m] << endl;

    return 0;
}

二进制优化代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 20010;

int n, m;
int v[N], w[N];
int f[M];

int main()
{
    cin >> n >> m;

    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s)
        {
            cnt ++ ;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if (s > 0)
        {
            cnt ++ ;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt;

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

臭氧：

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
这个是从cht的打卡里拿来的

#include <iostream>
#include <algorithm>

using namespace std;

const int N=1e5+10;

int n, m;
int s[3*N];
int num[3*N];
pair<int, int> query[N], add[N];
int idx_num, idx_add, idx_query;

int find(int x)
{
    int l = 1,r = idx_num;
    while(l<r)
    {
        int mid = l+r>>1;
        if(num[mid]<x) l = mid+1;
        else r = mid;
    }
    return l;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i<=n; i++)
    {
        int x, c;
        cin >> x >> c;
        num[++idx_num] = x;
        add[++idx_add] = {x, c};
    }
    for(int i = 1; i<=m; i++)
    {
        int l,r;
        cin >> l >> r;
        num[++idx_num] = l, num[++idx_num] = r;
        query[++idx_query] = {l,r};
    }

    sort(num+1, num+idx_num+1);
    idx_num = unique(num+1, num+idx_num+1)-num-1;

    for(int i = 1; i<=idx_add; i++)
    {
        int t = find(add[i].first);
        s[t] += add[i].second;
    }

    for(int i = 1; i<=idx_num; i++) s[i] += s[i-1];

    for(int i = 1; i<=idx_query; i++)
    {
        int l = find(query[i].first),r = find(query[i].second);
        cout << s[r]-s[l-1] << endl;
    }

    return 0;
} 

#include <iostream>
#include <deque>
#include <cstring>

using namespace std;

int n,m,k;
int h[1010],e[20010],ne[20010],w[20010],idx;
int dist[1010];
bool st[1010];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

bool check(int x)
{
    memset(dist,0x3f,sizeof(dist));
    memset(st,false,sizeof(st));

    deque<int> q;
    dist[1]=0;
    q.push_front(1);

    while(q.size())
    {
        int t=q.front();
        q.pop_front();

        if(st[t])  continue;
        st[t]=true;

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i],v=w[i]>x;
            if(dist[j]>dist[t]+v)
            {
                dist[j]=dist[t]+v;
                if(v)  q.push_back(j);
                else  q.push_front(j);
            }
        }
    }

    return dist[n]<=k;
}

int main()
{
    cin>>n>>m>>k;
    memset(h,-1,sizeof(h));
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }

    int l=0,r=1e6+1;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid))  r=mid;
        else l=mid+1;
    }

    if(l==1e6+1)    cout<<-1;
    else  cout<<l;

    return 0;
}

算一下 跑步/魔法 哪个快

• 跑步： $17m/s$
• 魔法： 需要 2.5s 回满 10 点魔法，加上使用 1s 共 3.5s 计算得 $17\dfrac{1}{7} m/s$

所以魔法快

那就优先选魔法

DP
$f[i]$ 表示第 $i$ 秒最大距离
先只算魔法

算完之后看看每秒是否可以用跑步
就OK了

//You will help me for the ROOT,right?
//Must go!
//Never give up,always try!
//You konw that [***data delete***].Then, we can to END.
//No upset,we must use all to fight it!

#include <iostream>

using namespace std;

int N,S,T;
int f[300100];

int main()
{
    cin>>N>>S>>T;

    for(int i=1;i<=T;i++)
    {
        if(N>=10)
        {
            f[i]=f[i-1]+60;
            N-=10;
        }
        else
        {
            f[i]=f[i-1];
            N+=4;
        }
    }

    for(int i=1;i<=T;i++) 
    {
        f[i]=max(f[i],f[i-1]+17);
        if(f[i]>=S)
        {
            cout<<"Yes"<<endl<<i;
            return 0;
        }
    }

    cout<<"No"<<endl<<f[T];

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main()
{
    char a[11];
    int b[10],i,key=0,cnt=0;
    gets(a);
    for(i=0;i<strlen(a);i++)
    {
        if(a[i]-'0'>=0 && a[i]-'0'<=9)
            b[i]=a[i]-'0';
        else
            key=1;
    }
    if(key==1)
    {
        cout<<'-';
            for(i=strlen(a)-1;i>0;i--)
            {
                if(b[i]==0&&cnt==0)
                    continue;
                cnt=1;
                cout<<b[i];
            }
    }
    else
    {
        for(i=strlen(a)-1;i>=0;i--)
            {
                if(b[i]==0&&cnt==0)
                    continue;
                cnt=1;
                cout<<b[i];
            }
    }
    return 0;
}

#include <iostream>
#include <cstring>

using namespace std;

int n,m;
int score[360],s[5];
int f[40][40][40][40];

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)  cin>>score[i];
    while(m--)
    {
        int x;
        cin>>x;
        s[x]++;
    }

    for(int a=0;a<=s[1];a++)
        for(int b=0;b<=s[2];b++)
            for(int c=0;c<=s[3];c++)
                for(int d=0;d<=s[4];d++)
                {
                    int t=score[a+2*b+3*c+4*d];
                    f[a][b][c][d]=t;
                    if(a)  f[a][b][c][d]=max(f[a][b][c][d],f[a-1][b][c][d]+t);
                    if(b)  f[a][b][c][d]=max(f[a][b][c][d],f[a][b-1][c][d]+t);
                    if(c)  f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c-1][d]+t);
                    if(d)  f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c][d-1]+t);
                }

    cout<<f[s[1]][s[2]][s[3]][s[4]];

    return 0;
}

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int n,maxx=0xcfcfcfcf;
int v[110];
char p[110];
int f[60][60],g[60][60];
vector<int> num;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)  cin>>p[i]>>v[i];
    for(int i=n+1;i<=2*n;i++)  v[i]=v[i-n],p[i]=p[i-n];

    for(int i=1;i<=n;i++)
    {
        int a[60];
        char b[60];

        //以a,b做一个无环的区间dp
        for(int j=1;j<=n;j++)  a[j]=v[i+j-1];
        for(int j=1;j<n;j++)   b[j]=p[i+j];
        memset(f,0xcf,sizeof(f));
        memset(g,0x3f,sizeof(g));

        for(int i=1;i<=n;i++)   f[i][i]=g[i][i]=a[i];
        for(int len=2;len<=n;len++)
            for(int l=1;l+len-1<=n;l++)
            {
                int r=l+len-1;
                for(int k=l;k<r;k++)
                    if(b[k]=='t')    
                    {
                        f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]);
                        g[l][r]=min(g[l][r],g[l][k]+g[k+1][r]);
                    }
                    else  
                    {
                        f[l][r]=max(f[l][r],max(f[l][k]*f[k+1][r],g[l][k]*g[k+1][r]));
                        g[l][r]=min(g[l][r],min(f[l][k]*f[k+1][r],g[l][k]*g[k+1][r]));
                    }
            }

        if(f[1][n]>maxx)
        {
            num.clear();
            maxx=f[1][n];
            num.push_back(i);
        }
        else if(f[1][n]==maxx)  num.push_back(i);
    }


    cout<<maxx<<endl;
    for(int i=0;i<(int)num.size();i++)  cout<<num[i]<<' ';

    return 0;
}