2018.9青岛网络预选赛(H)

 传送门:Problem H

 https://www.cnblogs.com/violet-acmer/p/9664805.html

题意：

BaoBao在一条有刻度的路上行走（哈哈，搞笑），范围为

[0，n],且都是整数，在当前刻度i的前0.5米处(i+0.5)有红绿灯s[i+1]，s[i+1]='0'代表红灯，s[i+1]='1'代表绿灯，遇到红灯需要等一秒变成绿灯后才可以来到i+1处。

每隔一秒所有的灯都会变色。

且没来到一个新的起点p，所有的灯都会恢复初始状态。

题解：

打表找规律：
对于样例3
t[0,1]=1
t[0,2]=3,t[1,2]=1
t[0,3]=4,t[1,3]=2,t[2,3]=2
t[0,4]=5,t[1,4]=3,t[2,4]=3,t[3,4]=1
t[0,5]=6,t[1,5]=4,t[2,5]=4,t[3,5]=2,t[4,5]=2
设dp[i]代表来到i处的总时间
例如
dp[1]=t[0,1]=1;
dp[2]=t[0,2]+t[1,2]=4;
dp[3]=t[0,3]+t[1,3]+t[2,3]=8;
dp[4]=t[0,4]+t[1,4]+t[2,4]+t[3,4]=12;
dp[5]=t[0,5]+t[1,5]+t[2,5]+t[3,5]+t[4,5]=18;

在计算dp[3]的时候
dp[3]所包含的所有时间为
t[2,3]
t[0,2]+t[2,3]
t[1,2]+t[2,3]
第一个t[2,3]容易计算，就是判断s[2]是红灯还是绿灯，红灯为2，绿灯为1;
t[0,2]+t[1,2]也容易计算，就是dp[2];

下面来求解后两个t[2,3]的计算:
设change[i,j]表示从i处到j处红绿灯变化的总次数;
计算第一个t[2,3]需要知道change[0,2]，如果change[0,2]是奇数，则计算t[2,3]时原先的s[i]的红绿灯状态不变，反之，改变状态;
计算第二个t[2,3]亦是如此，需要知道change[1,2];

难点就在于change[0,2]与change[1,2];
计算容易发现change[0,2]=3,change[1,2]=1;
且通过计算其他的change[i,m](i<m)可以发现，change[0,m]与change[1,m],...,change[m-1,m]同奇偶，而change[m-1,m]与t[m-1,m]同奇偶
此时易得后两个t[2,3]的值是一样的，都和change[1,2]的奇偶以及s[2]状态有关。

故后两个t[2,3]的和x为
if(change[1,2]为奇) x=2*(s[i] == 1 ? 2:1);
else x=2*(s[i] == 1 ? 1:2);
合并为一句话就是
x=2*(s[2] == s[1] ? 1:2);

所以dp[i]=dp[i-1]+(i-1)*(s[i-1] == s[i-2] ? 2:1)+(s[i-1] == '1' ? 1:2);
最终结果是吧所有的dp[i]加起来(0<=i<=n)

AC代码：

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#define exp 1e-8
#define mian main
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
#define pb push_back
#define PI  acos(-1.0)
#define inf 0x3f3f3f3f
#define w(x) while(x--)
#define int_max 2147483647
#define lowbit(x) (x)&(-x)
#define gcd(a,b) __gcd(a,b)
#define pq(x)  priority_queue<x>
#define ull unsigned long long
#define scn(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pl(a,n) next_permutation(a,a+n)
#define ios ios::sync_with_stdio(false)
#define met(a,x) memset((a),(x),sizeof((a)))
using namespace std;
const int maxn=1e5+10;

ll dp[maxn];

int main ()
{
    int t;
    scn(t);
    string s;
    while(t--)
    {
        cin>>s;
        int len=s.length();
        met(dp,0);
        dp[1]=(s[0] == '0' ? 2:1);
        for(int i=1;i<len;i++)
            dp[i+1]=dp[i]+i*((s[i]==s[i-1])?2:1)+((s[i] == '1') ? 1:2);

        ll ans=0;
        for(int i=1;i<=len;i++)
            ans += dp[i];
        printf("%lld
",ans);
    }
    return 0;
}

---

分割线：2019.5.8

一年的训练，思维开阔了不少；

今早醒来，我大致看了一下去年写的这篇题解；

感觉打表的暴力味很浓厚，缺乏一些证明；

昨天比赛的时候，依稀记得做过这道题；

还记得我写过题解，但，题解内容早已忘却；

无奈，重新找规律；

不过，这次不再是单纯的打表找规律，而是找了一下区间之间内在的联系；

回归正题；

定义 dp[ i ] 表示以 i 灯结尾所花费的总时间；（红绿灯的位置 1,2,.....,n）

dp[i]=[0,i]+[1,i]+....+[i-1,i];//[x,i] 表示从x点开始，到达 i 灯所需的总花费

先来看看如下式子：

[x,i]与[y,i]同奇偶（x < i , y < i）

证明：

　　不妨设 x < y，那么 [x,i] = [x,y]+[y,i]

　　①[y,i]为奇数

　　　　如果[x,y]为奇数，那么，势必会改变[y,i]红绿灯的初始状态，[y,i]为偶数；

　　　　如果[x,y]为偶数，那么，[y,i]的红绿灯状态就不会改变，[y,i]为奇数；

　　②[y,i]为偶数

　　　　如果[x,y]为奇数，那么，势必会改变[y,i]红绿灯的初始状态，[y,i]为奇数；

　　　　如果[x,y]为偶数，那么，[y,i]的红绿灯状态就不会改变，[y,i]为偶数；

　　综上，[x,i]与[y,i]同奇偶，换句话说就是以第 i 个灯结尾的区间，同奇偶；

有了这个公式，这道题就解决一大半了；

假设dp[0,...,i-1]已求出，如何根据已求出的dp推导出dp[i]呢？

dp[i]=[0,i]+[1,i]+.....+[i-2,i]+[i-1,i]

　   =[0,i-1]+[i-1,i]+[1,i-1]+[i-1,i]+....+[i-2,i-1]+[i-1,i]+[i-1,i]

　   =[0,i-1]+[1,i-1]+....+[i-2,i-1]+[i-1,i]+[i-1,i]+....+[i-1,i]+[i-1,i]

       =dp[i-1]+[i-1,i]+[i-1,i]+....+[i-1,i]+[i-1,i]

现在，问题的关键就在于如何求解不同的[i-1,i]所花费的时间；

根据上面推的公式可得：

　　(1):[0,i-1],[1,i-1],.....,[i-2,i-1]同奇偶；

　　(2):[0,i],[1,i],.....,[i-2,i],[i-1,i]同奇偶；

由这(1)(2)可得出：

　　[i-1,i],[i-1,i],....,[i-1,i]同奇偶；

如何求出这(i-1)个的[i-1,i]是同奇还是同偶呢？

[i-2,i]与[i-1,i]同奇偶，即[i-2,i-1]+[i-1,i] 与 [i-1,i]同奇偶；

①[i-1,i]为偶数

　　如果[i-2,i-1]为奇数，那么[i-1,i]为奇数；

　　反之，[i-1,i]为偶数；

①[i-1,i]为奇数

　　如果[i-2,i-1]为奇数，那么[i-1,i]为偶数；

　　反之，[i-1,i]为奇数；

总结：如果[i-1,i]与[i-2,i-1]同奇偶，[i-1,i]为偶数，反之，[i-1,i]为奇数；

定义数组s，s[i]代表i处的红绿灯状况；

dp[i]=dp[i-1]+(i-1)*(s[i] == s[i-1] ? 2:1)+(s[i] == '1' ? 1:2);

AC代码：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=1e5+10;

char s[maxn];
ll dp[maxn];

ll Solve()
{
    int len=strlen(s+1);
    mem(dp,0);
    dp[1]=(s[1] == '0' ? 2:1);///先求出dp[1]
    for(int i=2;i <= len;++i)
        dp[i]=dp[i-1]+(i-1)*(s[i] == s[i-1] ? 2:1)+(s[i] == '1' ? 1:2);

    ll ans=0;
    for(int i=1;i<=len;++i)
        ans += dp[i];

    return ans;
}
int main ()
{
    int test;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%s",s+1);
        printf("%lld
",Solve());
    }
    return 0;
}