2018暑假牛客多校（第二场）

原题连接

https://www.nowcoder.com/acm/contest/140/J

A-run

dp[i][0]$dp[i][0]$ 表示这一步是走 1$1$ 步走到 i$i$ 的
dp[i][i]$dp[i][i]$ 表示这一步是走 K$K$ 步走到 i$i$ 的
那这一步走 1$1$ 步的话，上一步走 1$1$ 步或 K$K$ 步都行，所以 dp[i][0]=dp[i−1][0]+dp[i−1][1]$dp[i][0]=dp[i-1][0]+dp[i-1][1]$
但是如果这一步走 K$K$ 步，那么上一步只能走 1$1$ 步，因为不能连着走，所以 dp[i][1]=dp[i−1][0]$dp[i][1]=dp[i-1][0]$

#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
using namespace std;
typedef long long LL;
const LL maxn=1e5+5;
const LL MOD=1e9+7;
LL dp[maxn][2],sum[maxn];
int main()
{
    int Q,K;
    cin>>Q>>K;
    for(int i=0;i<K;i++)dp[i][0]=1;
    for(int i=1;i<K;i++)sum[i]=sum[i-1]+1;
    for(int i=K;i<=100000;i++)
    {
        dp[i][0]=dp[i-1][0]+dp[i-1][1];
        dp[i][1]=dp[i-K][0];
        if(dp[i][0]>MOD)dp[i][0]%=MOD;
        if(dp[i][1]>MOD)dp[i][1]%=MOD;
        sum[i]=sum[i-1]+dp[i][0]+dp[i][1];
        if(sum[i]>MOD)sum[i]%=MOD;
    }
    for(int i=1;i<=Q;i++)
    {
        int L,R;
        cin>>L>>R;
        cout<<((sum[R]-sum[L-1])%MOD+MOD)%MOD<<endl;
    }
}

G-transform

思路：我们先随便一个答案，假如最多可以移动 cnt$cnt$ 个，然后选一个最左边的货物大于等于 cnt$cnt$ 个的 [L,R]$[L,R]$ 区间，然后看能不能找到一个花费小于 T$T$ 的一个位置 i$i$ ，要是没找到就更新区间，更新区间就像 尺取法 那样更新，如果找到了，那么说明可能这个 cnt$cnt$ 还不是最大的 cnt$cnt$ ，就可以让 cnt$cnt$ 变大，就是二分了

sum[i]$sum[i]$ 表示物品的前缀和
cost[i]$cost[i]$ 表示花费的前缀和
易得：cost[L,i]$cost[L,i]$ (sum[i]−sum[L−1])∗x[i]−(cost[i]−cost[L−1])$(sum[i]-sum[L-1])\ast x[i]-(cost[i]-cost[L-1])$
同理：cost[i,R]=(cost[R]−cost[i−1])−(sum[R]−sum[i−1])∗x[R]$cost[i,R]=(cost[R]-cost[i-1])-(sum[R]-sum[i-1])\ast x[R]$

如果是从左往右走，因为最右边的物品是一个一个加进来的，所以要么加上 a[R]$a[R]$ 就大于 cnt$cnt$ 了，要是不加就小于 cnt$cnt$ 了，因此多余的只在 a[R]$a[R]$ 里面，所以多余的花费是 (sum−cnt)∗(X[R]−X[i])$(sum-cnt)\ast (X[R]-X[i])$，另一边同理~

但是最后的二分我有点没有明白，为什么跟平常的不一样？？？

#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
using namespace std;
typedef long long LL;
const LL maxn=5e5+5;
LL sum[maxn];//物品的前缀和 
LL cost[maxn];//花费前缀和 
LL a[maxn],X[maxn];
LL N,T;
LL getsum(int L,int R,int x,LL cnt,bool cmd)            //区间内拿cnt个放到x位置的花费，cmd=0是不要右边多余的 
{
    LL res=0;
    LL surplus=sum[R]-sum[L-1]-cnt;                 //多余不用拿的货物个数 
    res+=(sum[x]-sum[L-1])*X[x]-(cost[x]-cost[L-1]);
    res+=(cost[R]-cost[x-1])-(sum[R]-sum[x-1])*X[x];
    if(cmd==0)res-=surplus*(X[R]-X[x]);                 //如果是不要右边的，那只有在R处多了几个 
    else res-=surplus*(X[x]-X[L]);                      //同理，不要左边的， 
    return res;
}
int judge(LL cnt)
{
    LL L=1,R=1,x=1;
    while(1)
    {
        while(R<N&&sum[R]-sum[L-1]<cnt)R++;
        if(R>N)break;
        if(sum[R]-sum[L-1]<cnt)break;
        if(x<L)x=L;                                                 //保证枚举的位置在区间内 
        while(x<R&&getsum(L,R,x,cnt,0)>getsum(L,R,x+1,cnt,0))x++;   //找到更好的位置就更新 
        if(getsum(L,R,x,cnt,0)<=T)return 1;                         //能达到这个货物的个数而且花费小于要求，那么就满足条件 
        L++;
    }
    L=R=x=N;
    while(1)
    {
        while(L>1&&sum[R]-sum[L-1]<cnt)L--;
        if(L<1)break;
        if(sum[R]-sum[L-1]<cnt)break;
        if(x>R)x=R;
        while(x>L&&getsum(L,R,x,cnt,1)>getsum(L,R,x-1,cnt,1))x--;
        if(getsum(L,R,x,cnt,1)<=T)return 1;
        R--;
    }
    return 0;
}
int main()
{
    cin>>N>>T;
    T>>=1;                                              //花费要乘2 
    for(int i=1;i<=N;i++)scanf("%lld",&X[i]);
    for(int i=1;i<=N;i++)
    {
        scanf("%lld",&a[i]);
        sum[i]=sum[i-1]+a[i];
        cost[i]=cost[i-1]+a[i]*X[i];
    }
    LL L=0,R=sum[N]+1;
    while(L+1<R)
    {
        LL mid=L+(R-L)/2;
        int jud=judge(mid);
        if(jud)L=mid;
        else R=mid;
    }
    cout<<L<<endl;
}

J-fram

题意：给一个 N×M$N\times M$ 的菜地，会喷洒 T$T$ 次农药，然后是给出每个菜地里蔬菜的类型，接下来给左上和右下的两个点(x1,y1),(x2,y2)$(x1,y1),(x2,y2)$，以及这种要喷洒的农药类型 t$t$ ，问：有多少蔬菜会死？

思路：我们把农药和蔬菜都用一个字母表示
比如：样例 1$1$ 中每个菜为：

[abbc]$$\left[\begin{array}{cc}a& b\\ b& c\end{array}\right]$$

喷洒之前为

[0000]$$\left[\begin{array}{cc}0& 0\\ 0& 0\end{array}\right]$$

第一次喷洒 b$b$ 这种类型的农药，变为：

[bbbb]$$\left[\begin{array}{cc}b& b\\ b& b\end{array}\right]$$

第二次喷洒 a$a$ 这种农药，变为：

[bb+abb]$$\left[\begin{array}{cc}b& b\\ b+a& b\end{array}\right]$$

每个位置只有对应的那种字母才不会死，如果有其他的字母那就会死，因此，把喷洒了农药的每个元素对蔬菜里的元素取模，要是有其他字母那肯定不会为 0$0$

所以只用看有多少个取模后不会为 0$0$

思路挺简单的

但是我们变成又不好弄 a,b,c$a,b,c$ 这种变量，那怎么办，于是就随机弄一个 Hash$Hash$ 值来代表字母，这个 Hash$Hash$ 值要越乱越好，才能保证每个 Hash$Hash$ 值对应每一个字母~

#include"bits/stdc++.h"
#define Rand(L,R) (L+sui()%(R-L))
using namespace std;
typedef long long LL;
const int maxn=1e6+6;
int N,M,Q;
LL Hash[maxn];
vector<LL>Mp[maxn],Tree[maxn];
void Add(int x,int y,LL v)
{
    for(int i=x;i<=N;i+=(i&-i))
    {
        for(int j=y;j<=M;j+=(j&-j))Tree[i][j]+=v;
    }
}
LL getsum(int x,int y)
{
    LL res=0;
    for(int i=x;i>=1;i-=i&-i)
    {
        for(int j=y;j>=1;j-=j&-j)res+=Tree[i][j];
    }
    return res;
}
int main()
{

    mt19937 sui(time(NULL));
    for(int i=1;i<=1000000;i++)Hash[i]=(LL)rand()*1e6+rand()*rand();
    while(cin>>N>>M>>Q)
    {
        for(int i=0;i<=N;i++)Mp[i].resize(M+5),Tree[i].resize(M+5);
        for(int i=1;i<=N;i++)
        {
            for(int j=1;j<=M;j++)
            {
                int t;
                scanf("%d",&t);
                Mp[i][j]=Hash[t];
            }
        }
        while(Q--)
        {
            int x1,y1,x2,y2,t;
            scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&t);
            Add(x1,y1,Hash[t]);
            Add(x1,y2+1,-Hash[t]);
            Add(x2+1,y1,-Hash[t]);
            Add(x2+1,y2+1,Hash[t]);
        }
        int ans=0;
        for(int i=1;i<=N;i++)
        {
            for(int j=1;j<=M;j++)
            {
                if(getsum(i,j)%Mp[i][j])ans++;
            }
        }
        printf("%d\n",ans);
    }
}