[普及]NOIP 2015 推销员贪心（推销员之死百度百科）

25-01-24 24

在本文中，我们将给您介绍关于[普及]NOIP2015推销员贪心的详细内容，并且为您解答推销员之死百度百科的相关问题，此外，我们还将为您提供关于NOIP2015推销员、NOIP2015普及组求和、NOI

在本文中，我们将给您介绍关于[普及]NOIP 2015 推销员贪心的详细内容，并且为您解答推销员之死百度百科的相关问题，此外，我们还将为您提供关于NOIP 2015 推销员、NOIP 2015普及组求和、NOIP 普及组 2014 比例简化、NOIP 普及组 2016 回文日期的知识。

本文目录一览：

[普及]NOIP 2015 推销员贪心（推销员之死百度百科）
NOIP 2015 推销员
NOIP 2015普及组求和
NOIP 普及组 2014 比例简化
NOIP 普及组 2016 回文日期

[普及]NOIP 2015 推销员贪心（推销员之死百度百科）

NOIP 2015 推销员

题意：

　　　　有一个喜欢疲劳的推销员，告诉你在一个单口胡同（数轴）中的n户家庭的位置，和向他们推销可以获得的疲劳度。分别输出向（1，2，3，4...n）户人家推销可以得到的最大疲劳值。对了，这个推销员走一格，疲劳度也会加一。

思路：

　　贪心，首先按每户人家的推销疲劳度从大到小排序，考虑选定一组，走路带来的疲劳度是定的，就是最远那个*2.

所以对于每个答案= max（sum[ i ] + mx * 2 , sum [i - 1] + h[i] ）。其中sum是排序后对推销疲劳度做的前缀和，而h[i] 保存从 i 到 n中，最大的（2 * 距离 + 推销疲劳度）。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <cstdlib>
#include <iterator>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <cctype>
using namespace std;
//#pragma GCC optimize(3)
//#pragma comment(linker, "/STACK:102400000,102400000")  //c++
#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue



typedef long long ll;
typedef unsigned long long ull;

typedef pair<ll ,ll > pll;
typedef pair<int ,int > pii;
typedef pair<int ,pii> p3;
//priority_queue<int> q;//这是一个大根堆q
//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl ''\n''

#define OKC ios::sync_with_stdio(false);cin.tie(0)
#define FT(A,B,C) for(int A=B;A <= C;++A)  //用来压行
#define REP(i , j , k)  for(int i = j ; i <  k ; ++i)
//priority_queue<int ,vector<int>, greater<int> >que;

const ll mos = 0x7FFFFFFFLL;  //2147483647
const ll nmos = 0x80000000LL;  //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3fLL; //18
const double PI=acos(-1.0);

template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<''0''||ch>''9'') f|=(ch==''-''),ch=getchar();
    while (ch>=''0''&&ch<=''9'') x=x*10+ch-''0'',ch=getchar();
    return x=f?-x:x;
}
// #define _DEBUG;         //*//
#ifdef _DEBUG
freopen("input", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
/*-----------------------show time----------------------*/

            const int maxn = 1e5+9;
            struct node
            {
                int s,p;
            }a[maxn];
            bool cmp(const node &a,const node &b){
                return a.p > b.p;
            };
            int sum[maxn],mx,h[maxn]; 
int main(){ 
            int n;
            scanf("%d", &n);
            for(int i=1; i<=n; i++)scanf("%d", &a[i].s);
            for(int i=1; i<=n; i++)scanf("%d", &a[i].p);
            sort(a+1,a+1+n,cmp);

            for(int i=1; i<=n; i++){
                sum[i] = sum[i-1] + a[i].p;
            }
            for(int i=n; i>=1; i--){
                h[i] = max(h[i+1],a[i].s * 2 + a[i].p);
            }

            for(int i=1; i<=n; i++){
                if(mx < a[i].s) mx = a[i].s;
                int tmp = sum[i] + 2 * mx;
                tmp = max(tmp , sum[i-1] + h[i]);
                printf("%d\n", tmp);
            }
            return 0;    
}

LUOGU 2672

NOIP 2015 推销员

洛谷 P2672 推销员

洛谷传送门

JDOJ 2994: [NOIP2015]推销员 T4

JDOJ传送门

Description

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

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

Input

第一行有一个正整数N，表示螺丝街住户的数量。
接下来的一行有N个正整数，其中第i个整数Si表示第i家住户到入口的距离。数据保证S1≤S2≤…≤Sn<108。
接下来的一行有N个正整数，其中第i个整数Ai表示向第i户住户推销产品会积累的疲劳值。数据保证Ai<103。

Output

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

Sample Input

5 1 2 2 4 5 5 4 3 4 1

Sample Output

12 17 21 24 27

HINT

【样例说明】 X=1：向住户4推销，往返走路的疲劳值为4+4，推销的疲劳值为4，总疲劳值4+4+4=12。 X=2：向住户1、4推销，往返走路的疲劳值为4+4，推销的疲劳值为5+4，总疲劳值4+4+5+4=17。
X=3：向住户1、2、4推销，往返走路的疲劳值为4+4，推销的疲劳值为5+4+4，总疲劳值4+4+5+4+4=21。 X=4：向住户1、2、3、4推销，往返走路的疲劳值为4+4，推销的疲劳值为5+4+3+4，总疲劳值4+4+5+4+3+4=24。或者向住户1、2、4、5推销，往返走路的疲劳值为5+5，推销的疲劳值为5+4+4+1，总疲劳值5+5+5+4+4+1=24。 X=5：向住户1、2、3、4、5推销，往返走路的疲劳值为5+5，推销的疲劳值为5+4+3+4+1，总疲劳值5+5+5+4+3+4+1=27。

【数据说明】对于20%的数据，1≤N≤20；
对于40%的数据，1≤N≤100；
对于60%的数据，1≤N≤1000；
对于100%的数据，1≤N≤100000。

Source

NOIP2015普及组

为什么标签会是树状数组呢？

题解：

这题运用的是贪心的思想，也用了一点点的DP思想，不过看大体的意思，还是贪心。

那么贪心策略是什么呢？我们说贪心总是离不开排序，那这个排序咋排呢？？

首先我们按照推销难度排序。

大的在前。

然后我们可以用dp数组表示前i个元素里最大的疲劳值是什么。

注意这可不是答案，你要知道你排序之后的顺序就被完全打乱了，你也不知道哪个在前哪个在后，你只知道这个东西大不大而已。

多以我们再用一个dp1数组进行第二遍DP，统计的是第i个元素的路径最大值。

最后我们比较q数组（单比较推销难度）加上对应的DP数组，和q数组和DP1数组比较就行。

取最大值：

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct home
{
    int s,val;
}a[100010];
int q[100010];
int dp[100010],dp1[100010];
int n;
bool cmp(home a,home b)
{
    return a.val>b.val;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].s);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].val);
    sort(a+1,a+1+n,cmp);
    for(int i=n;i>=1;i--)
        dp[i]=max(dp[i+1],2*a[i].s+a[i].val);
    for(int i=1;i<=n;i++)
        dp1[i]=max(dp1[i-1],a[i].s);
    for(int i=1;i<=n;i++)
        q[i]=q[i-1]+a[i].val;
    for(int i=1;i<=n;i++)
        printf("%d\n",max(q[i-1]+dp[i],q[i]+2*dp1[i]));
    return 0;
}

NOIP 2015普及组求和

题目：：

一条狭长的纸带被均匀划分出了 n 个格子，格子编号从 1 到 n 。每个格子上都染了一种颜色 color_i 用 [1,m] 当中的一个整数表示），并且写了一个数字 number_i 。

定义一种特殊的三元组： (x,y,z) ，其中 x,y,z 都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：

一条狭长的纸带被均匀划分出了nn个格子，格子编号从11到nn。每个格子上都染了一种颜色color\_icolor_i用[1,m][1,m]当中的一个整数表示），并且写了一个数字number\_inumber_i。

定义一种特殊的三元组：(x,y,z)(x,y,z)，其中x,y,zx,y,z都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：

xyzxyz是整数,x<y<z,y-x=z-yx<y<z,y−x=z−y
colorx=colorzcolorx=colorz

满足上述条件的三元组的分数规定为(x+z) \times (number\_x+number\_z)(x+z)×(number_x+number_z)。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以10,00710,007所得的余数即可。

输入格式

第一行是用一个空格隔开的两个正整数nn和m,nm,n表纸带上格子的个数，mm表纸带上颜色的种类数。

第二行有nn用空格隔开的正整数，第ii数字numbernumber表纸带上编号为ii格子上面写的数字。

第三行有nn用空格隔开的正整数，第ii数字colorcolor表纸带上编号为ii格子染的颜色。

输出格式

一个整数，表示所求的纸带分数除以1000710007所得的余数。

输入输出样例

输入 #1复制

6 2
5 5 3 2 2 2
2 2 1 1 2 1

输出 #1复制

输入 #2复制

15 4
5 10 8 2 2 2 9 9 7 7 5 6 4 2 4
2 2 3 3 4 3 3 2 4 4 4 4 1 1 1

输出 #2复制

说明/提示

【输入输出样例 1 说明】

纸带如题目描述中的图所示。

所有满足条件的三元组为： (1, 3, 5), (4, 5, 6)(1,3,5),(4,5,6)。

所以纸带的分数为(1 + 5) \times (5 + 2) + (4 + 6) \times (2 + 2) = 42 + 40 = 82(1+5)×(5+2)+(4+6)×(2+2)=42+40=82。

对于第 11 组至第 22 组数据， 1 ≤ n ≤ 100, 1 ≤ m ≤ 51≤n≤100,1≤m≤5；

对于第33 组至第 44 组数据， 1 ≤ n ≤ 3000, 1 ≤ m ≤ 1001≤n≤3000,1≤m≤100；

对于第 55 组至第66组数据， 1 ≤ n ≤ 100000, 1 ≤ m ≤ 1000001≤n≤100000,1≤m≤100000，且不存在出现次数超过2020的颜色；

对于全部 1010 组数据， 1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000, 1 ≤ color\_i ≤ m,1≤number\_i≤1000001≤n≤100000,1≤m≤100000,1≤color_i≤m,1≤number_i≤100000

分析：：

1）直接枚举 x,y,z 复杂度n^3,必定超时

2）通过题意不难发现 2*y=x+z；很明显有 x ，z 同奇偶关系，然后直接枚举x，z 复杂度n^2 也会TLE；

3）比较好的思想我们可以采用分组，先颜色分组再奇偶分组

推理：：

不妨假设一组中有k个数，(记录的是初始位置)x[1],x[2],x[3].......x[k];（number）y[1],y[2],y[3]....y[k];

答案=(x[1]+x[2])*(y[1]+y[2])+(x[1]+x[3])*(y[1]+y[3])+(x[1]+x[4])*(y[1]+y[4])+.......+(x[1]+x[k])*(y[1]+y[k])

+(x[2]+x[3])*(y[2]+y[3])+(x[2]+x[4])*(y[2]+y[4])+......+(x[2]+x[k])*(y[2]+y[k])

.......

+(x[k-1]+x[k])*(y[k-1]+y[k]);

整理合并=（不会就注意我加粗地方）

x[1]*(y[1]+y[2]+y[1]+y[3]+y[1]+y[4]+....+y[1]+y[k])

+x[2]*(y[1]+y[2]+y[2]+y[3]+y[2]+y[4]+....y[2]+y[k])

.............

+x[k]*(y[1]+y[k]+y[2]+y[k]+...y[k-1]+y[k])

=x[k]*(y[k]*(n-2)+y[1]+y[2]+y[3]+.....y[k]);

我们可以预先求出y[1]+...y[k],然后直接带入求和即可，复杂度n

千万记得 %10007

详细见代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=10007;
const int maxn=1e5+5;
int ma[maxn];//记录number
int mb[maxn];//记录颜色
int a[maxn][2];//统计分组后的个数
int sum[maxn][2];//y[1]->y[k]的和
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int ans=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&ma[i]);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&mb[i]);
        a[mb[i]][i&1]++;
        sum[mb[i]][i&1]=(sum[mb[i]][i&1]+ma[i])%MOD;
    }
    for(int i=1;i<=n;i++)
    {
        ans=(ans+i*((a[mb[i]][i&1]-2)*ma[i]%MOD+sum[mb[i]][i&1]))%MOD;//应用总结出来的式子
    }
    printf("%d\n",ans);
    return 0;
}

NOIP 普及组 2014 比例简化

传送门

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

题解：

　　一开始想多了，以为得保证两者之间的相对比率，至少不能改变的太离谱啊。

　　but，直接暴力就过了。。。。。。。

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define eps 1e-8
 5 #define P pair<int ,int >
 6 const int maxn=100+10;
 7 int A,B,L;
 8 int prime[maxn][maxn];
 9 int tot[maxn];
10 bool isPrime(int x,int y)//判断 x 与 y 是否互质
11 {
12     if(x < y)
13         swap(x,y);
14     for(int i=2;i <= y;++i)
15         if(x%i == 0 && y%i == 0)
16             return false;
17     return true;
18 }
19 void Solve()
20 {
21     P res;
22     res=P(0,0);
23     for(int i=1;i <= L;++i)
24         for(int j=1;j <= L;++j)
25             if(isPrime(i,j) && i*B >= j*A)
26             {
27                 if(res.first == 0 || i*res.second < j*res.first)
28                     res.first=i,res.second=j;
29             }
30     printf("%d %d\n",res.first,res.second);
31 }
32 int main()
33 {
34     scanf("%d%d%d",&A,&B,&L);
35     Solve();
36 }

View Code

NOIP 普及组 2016 回文日期

传送门

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

题解：

　思路1：

　　相关变量解释：

　　　　year1,month1,day1 : date1对应的年、月、日

　　　　year2,month2,day2 : date2对应的年、月、日

　　这道题算是考思维+Code能力？？

　　易得，每一年最多有一个回文日期；

　　例如 2000 的回文日期为 2000 0002

　　for i : year1 to year2

　　　　找到每个 i 的回文日期对应的月(month)、日(day)，并进行两个判断

　　　　(1):判断month,day是否合法。

　　　　(2):判断当前日期是否在date1与date2之间

　思路2.

　　枚举月和日对应的回文年份，看其回文组成的八位数是否在date1和date2内，什么意思呢？

　　例如，对于01月23日，其对应的回文年份为3210，其回文组成的八位数为 32100123，在和输入的date1与date2比较，看是否在其中，如果在，Count++;

　　不用特判某一年是否为闰年，为什么呢？

　　某年是否为闰年只会影响 2 月的天数，2月最多有 29 天，其对应的回文年份为 9220，但9220是闰年。

　　思路2来自集训队队员博客：https://blog.csdn.net/QLU_minoz/article/details/83450635

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define isSat(x) ((x) >= 1 &&(x) <= 12)//判断是否为合法的月份
 4 #define isRun(x) ((x%4 == 0 && x%100 != 0) || (x%400 == 0))//判断是否为闰年
 5 
 6 char data[2][8];
 7 int monthDay[2][13]={{0,31,28,31,30,31,30,31,31,30,31,30,31}, //0 : 平年
 8                      {0,31,29,31,30,31,30,31,31,30,31,30,31}};//1 : 闰年
 9 
10 int Transform(int a,int b,int d){//将字符串对应的年、月、日转化成数子
11     int num=0;
12     for(int i=a;i <= b;++i)
13         num=num*10+(data[d][i]-''0'');
14     return num;
15 }
16 void Search(int year,char *s){
17     int index=0;
18     do
19     {
20         s[index++]=year%10+''0'';
21         year /= 10;
22     }while(year != 0);
23 }
24 void Solve()
25 {
26     int year1=Transform(0,3,0),month1=Transform(4,5,0),day1=Transform(6,7,0);
27     int year2=Transform(0,3,1),month2=Transform(4,5,1),day2=Transform(6,7,1);
28     int res=0;
29     int pre=0;
30     for(int i=year1;i <= year2;++i)
31     {
32         char s[4];
33         Search(i,s);//找到将当前的年份的回文
34         int month=(s[0]-''0'')*10+(s[1]-''0'');//当前年份的回文对应的月
35         int day=(s[2]-''0'')*10+(s[3]-''0'');//日
36         if(!isSat(month) || day > monthDay[isRun(i)][month])
37             continue;
38         if(year1 == year2)
39         {
40             if(month > month1 || (month == month1 && day >= day1))
41             {
42                 if(month < month2 || (month == month2 && day <= day2))
43                     res++;
44             }
45         }
46         else
47         {
48             if(i == year1)
49                 res += (month > month1 || (month == month1 && day >= day1) ? 1:0);
50             else if(i == year2)
51                 res += (month < month2 || (month == month2 && day <= day2) ? 1:0);
52             else//如果year1 != year2 ，且 i != year1 && i != year2 ，则当前合法的日期一定在date1和date2之间
53                 res++;
54         }
55     }
56     printf("%d\n",res);
57 }
58 int main()
59 {
60     scanf("%s%s",data[0],data[1]);
61     Solve();
62 }

思路1

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int date1,date2;
 4 int monthDay[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
 5 
 6 void Solve()
 7 {
 8     int res=0;
 9     for(int i=1;i <= 12;++i)//枚举月份
10         for(int j=1;j <= monthDay[i];++j)//枚举每月对应的日
11         {
12             int year=j%10*1000+j/10*100+i%10*10+i/10;//当前月，日对应的回文年份
13             int cnt=year*10000+i*100+j;//回文日期对应的八位数
14             res += (cnt >= date1 && cnt <= date2 ? 1:0);
15         }
16     printf("%d\n",res);
17 }
18 int main()
19 {
20     scanf("%d%d",&date1,&date2);
21     Solve();
22 }