“玲珑杯”ACM比赛 Round #18 A 前缀预处理 D dp

DESCRIPTION

今天$\mathrm{HHHH\; 考完了期末考试,他在教学楼里闲逛,他看着教学楼里一间间的教室,于是开始思考:}$

如果从一个坐标为 $(x1,y1,z1)(x1,y1,z1)\; 的教室走到(x2,y2,z2)(x2,y2,z2)\; 的距离为\; |x1-x2|+|y1-y2|+|z1-z2||x1-x2|+|y1-y2|+|z1-z2|$

那么有多少对教室之间的距离是不超过$\mathrm{RR\; 的呢?}$

INPUT

第一行是一个整数$\mathrm{T(1\le T\le 10)T(1\le T\le 10)\; ,\; 表示有TT\; 组数据\; 接下来是TT\; 组数据,对于每组数据:\; 第一行是两个整数n,q(1\le n\le 5\times 104,1\le q\le 103)n,q(1\le n\le 5\times 104,1\le q\le 103)\; ,\; 表示有nn\; 间教室,\; qq\; 次询问.\; 接下来是nn\; 行,\; 每行3个整数xi,yi,zi(0\le xi,yi,zi\le 10)xi,yi,zi(0\le xi,yi,zi\le 10)\; ,表示这间教室的坐标.\; 最后是qq\; 行,每行一个整数R(0\le R\le 109)R(0\le R\le 109)\; ,意思见描述.}$

OUTPUT

对于每个询问$\mathrm{RR\; 输出一行一个整数,表示有多少对教室满足题目所述的距离关系.}$

SAMPLE INPUT

1 3 3 0 0 0 1 1 1 1 1 1 1 2 3

SAMPLE OUTPUT

1 1 3

HINT

对于样例,1号教室和2号教室之间的距离为3, 1号和3号之间的距离为3, 2号和3号之间的距离为0

SOLUTION

题解：考虑到坐标的范围非常小,我们可以统计每一个点有多少个教室,然后枚举坐标预处理答案,然后做一个前缀和即可

要小心的是R的范围  注意乘的时候会爆int

#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <string>
#include <complex>
#define ll long long
using namespace std;
int t;
int n,q;
int mp[15][15][15];
int x[50004],y[50004],z[50004];
int s[50004];
ll sum[505];
int main()
{
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        for(int j=0;j<=10;j++)
            for(int l=0;l<=10;l++)
             for(int k=0;k<=10;k++)
               mp[j][l][k]=0;
        for(int j=0;j<=50;j++)
            sum[j]=0;
        scanf("%d %d",&n,&q);
        int jishu=0;
        for(int j=1;j<=n;j++)
        {
            scanf("%d %d %d",&x[j],&y[j],&z[j]);
            if(mp[x[j]][y[j]][z[j]]==0)
                s[jishu++]=j;
            mp[x[j]][y[j]][z[j]]++;
      }
        for(int j=0;j<jishu;j++)
        {
            for(int k=j;k<jishu;k++)
            {
                if(j==k)
                {
                    ll now=mp[x[s[j]]][y[s[j]]][z[s[j]]];
                    sum[0]+=now*(now-1)/2;
                }
                else{ 
 int dis=abs(x[s[j]]-x[s[k]])+abs(y[s[j]]-y[s[k]])+abs(z[s[j]]-z[s[k]]);
  sum[dis]+=mp[x[s[k]]][y[s[k]]][z[s[k]]]*mp[x[s[j]]][y[s[j]]][z[s[j]]];
                }
            }
        }
        for(int j=1;j<=50;j++)
            sum[j]+=sum[j-1];
        int exm;
        for(int j=1;j<=q;j++)
        {
            scanf("%d",&exm);
            if(exm>50)
                printf("%lld
",sum[50]);
            else
                printf("%lld
",sum[exm]);
        }
    }
    return 0;
}

DESCRIPTION

今天$\mathrm{HHHH\; 在操场上跑步,HHHH\; 作为一个爱运动的人,肯定会想方设法把跑步所消耗的能量减到最少.}$

现在这个操场上有$\mathrm{nn\; 个可以休息的点,他们的坐标分别为x1,x2...xn(xi\le xi+1)x1,x2...xn(xi\le xi+1)\; ,HHHH\; 刚开始在\; x1x1\; ,并且他只能在这些点休息,在中途不能停下来,否则会因为旁边的音浪太强而被晃到.}$

如果$\mathrm{HHHH\; 连续跑一段长度为ll\; 的距离,那么他将会消耗2l+a2l+a\; 的能量(aa\; 为HHHH\; 的可爱值)}$

现在给你这些点的坐标,请帮$\mathrm{HHHH\; 计算他跑到xnxn\; 点所需要消耗的能量最少是多少.}$

INPUT

第一行是一个整数$\mathrm{T(1\le T\le 10)T(1\le T\le 10)\; ,表示有TT\; 组数据\; 对于每组数据输入一行2个整数n,a (1\le n\le 105,1\le a\le 106)n,a (1\le n\le 105,1\le a\le 106)\; 表示总共有nn\; 个休息点,HHHH\; 的可爱值为aa\; .\; 接着一行nn\; 个数x1,x2...,xn(0\le xi\le 3\times 106,0\le xi+1-xi\le 30)x1,x2...,xn(0\le xi\le 3\times 106,0\le xi+1-xi\le 30)\; ,表示点的位置.}$

OUTPUT

每组数据输出一行,一个整数,表示最小需要花费的体力

SAMPLE INPUT

2 3 2 3 5 7 3 10 3 5 7

SAMPLE OUTPUT

12 26

HINT

对于第一组样例,最少的体力消耗是先从3跑到5,消耗6点体力,再从5跑到7,消耗6点体力,共12点 对于第二组样例,最少的体力消耗是直接从3跑到7,消耗26点体力.

题解：

首先我们可以想到一个简单的dp方程

$\mathrm{dp[i]=min(dp[j]+2^(dis[i]-dis[j]))+a}$

1.然后我们发现这个${\mathrm{2^x很快就会比a\; 高到不知道哪里去,所以当这个距离超过一定值的时候肯定是分开}}^{}$

跑比较划算了,所以我们只需要枚举当前点前面的几十个点再转移一下就行了

2.我们也可以简单的推导一下发现这个$\mathrm{dp方程是决策性单调的所以你懂的}$

#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <string>
#include <complex>
#define ll long long
using namespace std;
int t;
int aa[100005];
int b[100005];
ll dp[3000006];
map<int,int>mp;
int n,a;
int main()
{
    scanf("%d",&t);
    int ans=0;
    for(int j=1;j<=t;j++)
    {
        scanf("%d %d",&n,&a);
        int jishu=0;
        mp.clear();
        for(int i=1;i<=n;i++){
            scanf("%d",&aa[i]);
            if(mp[aa[i]]==0){
                b[jishu++]=aa[i];
                mp[aa[i]]=1;
            }
            }
        sort(b,b+jishu);
        for(int i=0;i<jishu;i++){
            dp[i]=1e18+1;
            }
        dp[0]=0;
        for(int i=1;i<jishu;i++)
        {
            for(int j=i-1;j>=0;j--)
            {
                if(b[i]-b[j]>30)
                    break;
                dp[i]=min(dp[i],dp[j]+(1ll<<(b[i]-b[j]))+a);
            }
        }
        printf("%lld
",dp[jishu-1]);
    }
    return 0;
}