GVKun编程网logo

洛谷 P2672 推销员 解题报告

26

针对洛谷P2672推销员解题报告这个问题，本篇文章进行了详细的解答，同时本文还将给你拓展[CSP2019]划分解题报告、[jzoj4722][NOIP2016提高A组模拟8.21]跳楼机解题报告（sp

针对洛谷 P2672 推销员 解题报告这个问题，本篇文章进行了详细的解答，同时本文还将给你拓展[CSP2019] 划分 解题报告、[jzoj 4722] [NOIP2016提高A组模拟8.21] 跳楼机 解题报告 （spfa+同余）、「洛谷P1080」「NOIP2012提高组」国王游戏 解题报告、有多个推销员的旅行推销员？等相关知识，希望可以帮助到你。

本文目录一览：

洛谷 P2672 推销员 解题报告

洛谷 P2672 推销员 解题报告

P2672 推销员

题目描述

阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有N家住户，第i家住户到入口的距离为$S_i$米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的$X$家住户推销产品，然后再原路走出去。

阿明每走1米就会积累1点疲劳值，向第$i$家住户推销产品会积累$A_i$点疲劳值。阿明是工作狂，他想知道，对于不同的$X$，在不走多余的路的前提下，他最多可以积累多少点疲劳值。

输入输出格式

输入格式：

第一行有一个正整数$N$，表示螺丝街住户的数量。

接下来的一行有$N$个正整数，其中第$i$个整数$S_i$表示第$i$家住户到入口的距离。数据保证$S_1≤S_2≤…≤S_n<10^8$

接下来的一行有$N$个正整数，其中第$i$个整数$A_i$表示向第$i$户住户推销产品会积累的疲劳值。数据保证$A_i<1000$

输出格式：

输出$N$行，每行一个正整数，第$i$行整数表示当$X=i$时，阿明最多积累的疲劳值。

【数据说明】

对于 20% 的数据， 1≤N≤20 ；

对于 40% 的数据， 1≤N≤100 ；

对于 60% 的数据， 1≤N≤1000 ；

对于 100% 的数据， 1≤N≤100000 。

我就是那种贪心想不全，只会拿暴力数据结构跑的，暴力数据结构还写不出来的那种人。我为什么这么蒻啊。。

稍稍感(胡)性(乱)证明了一下，感觉好像第$i$次选的$i$个点，第$i+1$次全得选上，那好啊我一个个加每次维护一下最大值就好了。

然后开始点线段树$RMQ$，开始以为只有单点查询，把区间删减放外面做的，发现不对。。

改，写了个区间查询发现复杂度不对，这个lazy咋打啊....摸了半天，发现和普通的求和线段树的区别是在改变时一是得自下往上改，二是碰见修改区间与节点所带区间相等是得改节点儿子的lazy，而更新这个节点。

code:

#include <cstdio>
#define ls id<<1
#define rs id<<1|1
#define mid (L[id]+R[id]>>1)
const int N=100010;
int L[N<<2],R[N<<2],mx[N<<2],pos[N<<2],lazy[N<<2],s[N],a[N];
void build(int id,int l,int r)
{
    L[id]=l,R[id]=r;
    if(l==r) {mx[id]=s[l]+s[l]+a[l];pos[id]=l;return;}
    build(ls,l,mid);
    build(rs,mid+1,r);
    if(mx[ls]<mx[rs])
    {
        mx[id]=mx[rs];
        pos[id]=pos[rs];
    }
    else
    {
        mx[id]=mx[ls];
        pos[id]=pos[ls];
    }
}
void push_down(int id)
{
    mx[id]+=lazy[id];
    if(L[id]!=R[id])
    {
        lazy[ls]+=lazy[id];
        lazy[rs]+=lazy[id];
    }
    lazy[id]=0;
}
void change(int id,int x,int dat)
{
    if(lazy[id]) push_down(id);
    if(L[id]==R[id]) {mx[id]=dat;return;}
    if(x<=mid) change(ls,x,dat);
    else change(rs,x,dat);
    if(mx[ls]<mx[rs])
    {
        mx[id]=mx[rs];
        pos[id]=pos[rs];
    }
    else
    {
        mx[id]=mx[ls];
        pos[id]=pos[ls];
    }
}
void change0(int id,int l,int r,int delta)
{
    if(L[id]==l&&R[id]==r)
    {
        lazy[id]-=delta;
        push_down(id);
        return;
    }
    if(r<=mid) change0(ls,l,r,delta);
    else if(l>mid) change0(rs,l,r,delta);
    else change0(ls,l,mid,delta),change0(rs,mid+1,r,delta);
    if(mx[ls]<mx[rs])
    {
        mx[id]=mx[rs];
        pos[id]=pos[rs];
    }
    else
    {
        mx[id]=mx[ls];
        pos[id]=pos[ls];
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",s+i);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    build(1,1,n);
    int loc=0,las=0;
    for(int i=1;i<=n;i++)
    {
        int lp=pos[1];
        las+=mx[1];
        if(loc<pos[1])
        {
            for(int j=loc+1;j<lp;j++)
                change(1,j,a[j]);
            if(lp<n) change0(1,lp+1,n,s[lp]<<1);
            loc=lp;
        }
        printf("%d\n",las);
        change(1,lp,0);
    }
    return 0;
}

2018.6.15

[CSP2019] 划分 解题报告

[CSP2019] 划分 解题报告

[CSP2019] 划分

题意

有 $n$ 个非负整数 $a_i$ $(n \le 4 * 10^7)$, 将它们分为若干部分，记为 $S_i$, 要求 $S_{i+1} \ge S_i$, 设 $res=\sum_{i=1}^{k} S_i^2$. 求 $res$ 的最小值

思路

64 pts

考场上写的做法.

设 $f [i][j]$ 为第一段的起点为 $i$, 终点为 $j$ 时 $res$ 的最小值。朴素做法直接枚举 $i,j,k$, 将 $f [i][j]$ 从 $f [j][k]$ 转移过来.

优化：考虑中间的转移点 $j$, 对于每个 $i<j$, 合法的 $k$ 的范围是递增的，所以可以只枚举 $i,j$ 然后指针 $k$ 根据 $sum_j-sum_{i-1}$ 不断忘前移，并取最小值更新即可.

88 pts

设总共有 $k$ 个块，可以得出两个性质. 性质 1 : $k$ 越大，方案越优。感性理解 : $a^2+b^2 \le (a+b)^2$. 进一步推断出，性质 2 : $S_k$ 越小，方案越优。感性理解 : $S_k$ 越小，为了使得方案合法，就强迫前面的 $S$ 也要尽量地小，由于 $a$ 是非负整数，所以 $S$ 的值越小，$k$ 就越大，根据性质 1, 方案就越优.

这样的话我们就可以维护一个单调队列，对于每一位，找到以它为结束点时，最小的 $S_k$. 在把新元素加入单调队列时还有一些细节，详见代码.

100pts

上面的做法加个高精 (高精这种东西早就忘光了好吗...)

代码

64pts


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e3+7;
const ll inf=5e18;
int n,ty;
ll a[N],sum[N],f[N][N],ans=inf;
void read(){ }
ll p2(ll x){ return x*x; }
int main(){
  //freopen("divd.in","r",stdin);
  cin>>n>>ty;
  if(ty) read();
  else for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; }
  memset(f,127,sizeof(f));
  for(int i=1;i<=n;i++) f[i][n]=p2(sum[n]-sum[i-1]);
  for(int j=n;j>=1;j--){
    int k=n;
    ll minx=inf;
    for(int i=1;i<=j;i++){
      while(p2(sum[j]-sum[i-1])<=p2(sum[k]-sum[j])){
	minx=min(minx,f[j+1][k]);
	k--;
      }
      f[i][j]=min(f[i][j],minx+p2(sum[j]-sum[i-1]));
    }
  }
  for(int i=1;i<=n;i++) ans=min(ans,f[1][i]);
  printf("%lld\n",ans);
  return 0;
}

88pts


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4e7+7;
int n,ty,pre[N],que[N],t1,t2;
ll a[N],sum[N],lst[N],ans;
void read(){};
ll p2(ll x){ return x*x; }
int main(){
  //  freopen("divd.in","r",stdin);
  //  freopen("x.out","w",stdout);
  cin>>n>>ty;
  if(ty) read();
  else for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; }
  t1=t2=1;
  que[1]=0;
  for(int i=1;i<=n;i++){
    //        printf("%d: ",i); for(int j=t1;j<=t2;j++) printf("%d ",que[j]); putchar(''\n'');
    while(t1<t2&&lst[que[t1+1]]<=sum[i]-sum[que[t1+1]]) t1++;
    pre[i]=que[t1];
    lst[i]=sum[i]-sum[pre[i]];
    while(t2>=t1&&lst[que[t2]]>=lst[i]+sum[i]-sum[que[t2]]) t2--;
    que[++t2]=i;
  }
  int p=n;
  while(p){
    ans+=lst[p]*lst[p];
    p=pre[p];
  }
  //     for(int i=1;i<=n;i++) printf("pre[%d]: %d\n",i,pre[i]);
  printf("%lld\n",ans);
  return 0;
}

[jzoj 4722] [NOIP2016提高A组模拟8.21] 跳楼机 解题报告 （spfa+同余）

[jzoj 4722] [NOIP2016提高A组模拟8.21] 跳楼机 解题报告 （spfa+同余）

题目链接：

http://172.16.0.132/senior/#main/show/4722

题目：

DJL为了避免成为一只咸鱼，来找srwudi学习压代码的技巧。
Srwudi的家是一幢h层的摩天大楼。由于前来学习的蒟蒻越来越多，srwudi改造了一个跳楼机，使得访客可以更方便的上楼。
经过改造，srwudi的跳楼机可以采用以下四种方式移动：
1、向上移动x层；
2、向上移动y层；
3、向上移动z层；
4、回到第一层。
一个月黑风高的大中午，DJL来到了srwudi的家，现在他在srwudi家的第一层，碰巧跳楼机也在第一层。DJL想知道，他可以乘坐跳楼机前往的楼层数。

题解：

一开始$h--$，把第1层给减掉方便处理

40分的做法是直接bfs统计方案数，但是这样状态数太多太大了，考虑简化方案数

定义$d_i=c$，$c$表示最小的只由操作2,3得到的且满足$c \mod x = i$的数

那么答案$ans=\sum_{i=0}^{x-1} (\lfloor \frac{h-d_i}{x} \rfloor+1)$

为什么呢？我们考虑将合法的楼层按模x分类，显然余数是由操作2,3得到的。那么我们考虑得到了最小的楼层，比它大的所有的在这个剩余系里的楼层都可以得到，而比它小的绝对得不到

按模x分类做到了不重，取完后面所有的数做到了不漏

考虑$d_i$怎么计算，显然有

$$d_{k+y}=d_k+y$$

$$d_{k+z}=d_k+z$$

这是一个最短路模型，跑一次spfa就好了

时间复杂度怎么算呢?我也没太弄懂

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;

const int N=1e5+15;
const ll inf=1e18;
ll h,x,y,z;
int vis[N];
ll d[N];
void spfa()
{
    queue <int> q;
    for (ll i=0;i<x;i++) d[i]=inf;
    d[0]=0;q.push(0);vis[0]=1;
    while (!q.empty())
    {
        ll k=q.front();q.pop();vis[k]=0;
        if (d[(k+y)%x]>d[k]+y) 
        {
            d[(k+y)%x]=d[k]+y;
            if (!vis[(k+y)%x]) q.push((k+y)%x),vis[(k+y)%x]=1;
        }
        if (d[(k+z)%x]>d[k]+z) 
        {
            d[(k+z)%x]=d[k]+z;
            if (!vis[(k+z)%x]) q.push((k+z)%x),vis[(k+z)%x]=1;
        }
    }
}
int main()
{
    scanf("%lld%lld%lld%lld",&h,&x,&y,&z);
    --h;
    spfa();
    ll ans=0;
    for (ll i=0;i<x;i++) if (h>d[i]) ans+=(h-d[i])/x+1;
    printf("%lld\n",ans);
    return 0;
}

 

「洛谷P1080」「NOIP2012提高组」国王游戏 解题报告

「洛谷P1080」「NOIP2012提高组」国王游戏 解题报告

P1080 国王游戏

题目描述

恰逢 $H$国国庆，国王邀请$n$位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 $n$ 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

输入输出格式

输入格式：

第一行包含一个整数$n$，表示大臣的人数。

第二行包含两个整数 $a$和 $b$，之间用一个空格隔开，分别表示国王左手和右手上的整数。

接下来 $n$行，每行包含两个整数$a$ 和 $b$，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

输出格式：

一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

输入输出样例

输入样例#1：

3 
1 1 
2 3 
7 4 
4 6

输出样例#1：

2

说明

【输入输出样例说明】

按11、22、33 这样排列队伍，获得奖赏最多的大臣所获得金币数为 22；

按 11、33、22 这样排列队伍，获得奖赏最多的大臣所获得金币数为22；

按 22、11、33 这样排列队伍，获得奖赏最多的大臣所获得金币数为 22；

按22、33、11这样排列队伍，获得奖赏最多的大臣所获得金币数为99；

按 33、11、22这样排列队伍，获得奖赏最多的大臣所获得金币数为 22；

按33、22、11 这样排列队伍，获得奖赏最多的大臣所获得金币数为 99。

因此，奖赏最多的大臣最少获得 22个金币，答案输出 22。

【数据范围】

对于 20%的数据，有 1≤ n≤ 10,0 < a,b < 81≤n≤10,0<a,b<8；

对于 40%的数据，有1≤ n≤20,0 < a,b < 81≤n≤20,0<a,b<8；

对于 60%的数据，有 1≤ n≤1001≤n≤100；

对于 60%的数据，保证答案不超过 10^9109；

对于 100%的数据，有 1 ≤ n ≤1,000,0 < a,b < 100001≤n≤1,000,0<a,b<10000。

NOIP 2012 提高组 第一天 第二题

思路

我们假设一个正确的序列中有两个元素 i 与 i + 1,他们左右手的数字分别为Ai，Bi，Ai+1，Bi+1

排在i大臣前面的所有人的左手上的数的乘积为T(以下向下取整省略不写)

这两位大臣得到最多的硬币为 max( T / Bi, (T * Ai) / Bi+1 ) = Ans1

假设交换这两位大臣 则他们得到最多硬币数变为 max( T / Bi+1, (T * Ai+1) / Bi ) = Ans2

要求Ans1 <= Ans2，原序列顺序可能不是最优（否则这两位大臣交换能得到更有策略）

所以要使 T / Bi 和 (T * Ai) / Bi+1都小于等于Ans2即可满足要求

由于T / Bi <= (T * Ai+1) / Bi ，T / Bi 肯定能满足要求，只要使 ( T * Ai ) / Bi+1 也小于等于 Ans2即可

(T * Ai) / Bi+1 肯定大于等于 T / Bi+1 ，所以只能使 (T * Ai+1) / Bi 大于等于(T * Ai) / Bi+1 ,否则不能达到要求

然后我们就可以列出不等式 (T * Ai) / Bi+1 <= (T * Ai+1) / Bi

因为T是正数，所以可以同时消去

Ai / Bi+1 <= Ai+1 / Bi

同乘Bi+1Bi

Ai * Bi <= Ai+1 * Bi+1

所以，只要按Ai * Bi从小到大排序就不成问题了。（当然别把国王也排序了）

注意要加高精度。

代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 10005

struct ppp{
    int a, b;
}p[MAXN];

int n;

bool cmp( ppp x, ppp y ){
    return x.a * x.b < y.a * y.b;
}

int s[4005], len;
int ans[4005], ans_l(0);

void Mul( int x ){
    int t(len);
    for ( int i = 1; i <= len; ++i ) s[i] *= x;
    for ( int i = 1; i <= len + 5; ++i ){
        if ( s[i] ) t = i;
        s[i + 1] += s[i] / 10;
        s[i] %= 10;
    }
    len = t;
}

void Copy( int c[], int c_l ){
    for ( int i = 1; i <= c_l; ++i ) ans[i] = c[i];
    ans_l = c_l;
}

void Out( int s[], int l ){
    for ( int i = l; i >= 1; --i ) printf( "%d", s[i] );
    putchar(''\n'');
}
void Div( int x ){
    int c[4005], l(-1);
    for ( int i = 1; i <= len; ++i ) c[i] = s[i];
    for ( int i = len; i >= 1; --i ){
        c[i - 1] += ( c[i] % x ) * 10;
        c[i] /= x;
        if ( c[i] && l == -1 ) l = i;
    }
    if ( ans_l == l ){
        bool flg(0);
        for ( int i = l; i >= 1; --i )
            if ( ans[i] < c[i] ){ flg = 1; break; }
            else break;
        if ( flg ) Copy( c, l );
    }
    if ( ans_l < l ) Copy( c, l );
}


int main(){
    scanf( "%d", &n );
    scanf( "%d%d", &p[0].a, &p[0].b );
    for ( int i = 1; i <= n; ++i ) scanf( "%d%d", &p[i].a, &p[i].b );
    sort( p + 1, p + n + 1, cmp );
    s[1] = 1; len = 1;
    Mul( p[0].a );
    for ( int i = 1; i <= n; ++i )
        Div( p[i].b ), Mul( p[i].a );
    Out( ans, ans_l );
    return 0;
}

完事！！！

有多个推销员的旅行推销员？

有多个推销员的旅行推销员？

我有一个问题已被有效地简化为具有多个推销员的旅行推销员问题。我有一个从初始位置访问的城市列表，并且必须访问销售人员数量有限的所有城市。

我试图提出一种启发式方法，想知道是否有人可以伸出援手。例如，如果我有20个城市有2个销售人员，那么我考虑采用的方法是2步方法。首先，将20个城市随机分为10个城市，每个城市有2个推销员，然后我会发现每个城市的巡回演出似乎都是独立的，只有几次迭代。之后，我想交换城市或将城市分配给另一位推销员，然后找到旅行团。实际上，这将是TSP，然后是最小制造期问题。这样做的问题是，它太慢了，很难很好地邻里交换或分配城市。

任何人都可以就我可以如何改善上述情况提出建议吗？

编辑：

每个城市的地理位置都是已知的，推销员的起点和终点都在相同的地方。目标是最大程度地减少最大行驶时间，从而解决这种最小的制造跨度问题。因此，例如，如果salesman1花费10个小时，而salesman2花费20个小时，则最长行驶时间将是20个小时。

今天的关于洛谷 P2672 推销员 解题报告的分享已经结束，谢谢您的关注，如果想了解更多关于[CSP2019] 划分 解题报告、[jzoj 4722] [NOIP2016提高A组模拟8.21] 跳楼机 解题报告 （spfa+同余）、「洛谷P1080」「NOIP2012提高组」国王游戏 解题报告、有多个推销员的旅行推销员？的相关知识，请在本站进行查询。

本文标签：

上一篇开发者如何提升和推销自己（开发者如何提升和推销自己的能力）

下一篇「译」开发者如何提升和推销自己（如何激发开发者选项）

相关文章