2019/7/19 CF808（div2)

A.Lucky Year

对于只存在一个不为0的位数，那么先把位数求出来，若只有一个，那么是1～9，任意+1都满足，所以为1，若不是1，那么就是最高位+1 ，后面全是0，减去原来的数字。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int y,count=0,x,d;
 6     cin>>y;
 7     d=y;
 8     while(y!=0)
 9     {
10         count++;
11         if((y/10)==0)
12         x=y;
13         y=y/10;
14     }
15     if(count==1)
16     cout<<"1";
17     else
18     {
19       // cout<<x<<count<<endl;
20         x=(x+1)*pow(10,count-1);
21        // cout<<x<<endl;
22         cout<<x-d;
23     }
24     return 0;
25 }
A

B. Average Sleep Time

输入一个n，k,求k长度为前缀的前缀和，直接暴力模拟。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() 
{
    ll n,k;
    cin>>n>>k;
    ll a[n];
    for(ll i=0;i<n;i++)   cin>>a[i];
    ll ans = 0,sum=0;
    for(ll i=0;i<k;i++)   ans += a[i];   sum = ans;
    for(ll i=1;i<n-k+1;i++)
    {
        ans -= a[i-1] ;
        ans += a[i+k-1] ;
        sum +=ans;
    }
    double an = sum/(double)(n-k+1);
   printf("%.12lf
", an);
}
B

 

C.Tea Party

题目意思为，有n个人，每个人有a[i]的杯子，有一个为w多的茶水，使每个杯子的水大于等于一般（体积为整数），不存在体积较大的者的水比体积较小者的水少，求方案。

所以，贪心，刚开始都给一半，但是要向上取整，如果w不够直接不存在，如果w有剩余，那么就要根据体积的多少降序直接放入（坑点在于因为是整数，所以存在奇偶，又因为sort是

稳定的排序，所以要以前的体积来排序。）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3  
 4 #define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
 5 #define ll long long 
 6 #define mp make_pair
 7 #define ss second
 8 #define ff first
 9 #define pb push_back
10 #define PDI pair<double, int>
11 #define PII pair<int, int>
12  
13 int n,w;
14 PII a[300];
15  
16 int f[300];
17  
18 bool cmp(PII a, PII b)
19 {
20     return a.first > b.first;
21 }
22 int main()
23 {
24 //    fast;
25     
26     cin >> n >> w;
27     int x;
28     for (int i = 1; i <= n; i ++)
29     {
30         cin >> x;
31         a[i].first = x;
32         
33         f[i] = (x + 1) / 2;
34         w -= (x + 1) / 2;
35         a[i].second = i;
36     }
37     if(w < 0)
38     {
39         puts("-1");
40         return 0;
41     }
42     sort(a + 1, a + n + 1, cmp);
43     for (int i = 1; i <= n; i ++)
44     {
45         a[i].first = a[i].first - f[a[i].second]; 
46     }
47     
48     for (int i = 1; i <= n; i ++)
49     {
50         if(w >= a[i].first)
51         {
52             w -= a[i].first;
53             f[a[i].second] += a[i].first;
54         }
55         else
56         {
57             f[a[i].second] += w;
58             w = 0;
59             break;
60             
61         }
62     }
63     
64     for (int i = 1; i <= n; i ++)
65     printf("%d ", f[i]);
66     
67 }
C

D.  Array Division

给定一组序列，让你只能把其中一个任意移动位置，然后分成俩个数列，和相等。

第一种方法，那么我们就维护前缀和，如果和为奇数，没有方案。如果是偶数，对与前k的数列来说，它只能删除或得到

某个数，那么我们维护前缀和，如果小于sum/2，那么就在后面找一下，有没有这个少的部分的数字。如果等于，那么成功。如果大于，只能说明加了一个多余的数字，要删除它，那么它

就在我加过的数字里面，用map来储存数字和个数。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3  
 4 #define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
 5 #define ll long long 
 6 #define mp make_pair
 7 #define ss second
 8 #define ff first
 9 #define pb push_back
10  
11 typedef pair<int, int> P;
12  
13 const int N = 1e6 + 10;
14 int a[N];
15 ll sum[N];
16  
17 unordered_map<ll, int> first, second;
18  
19 int main()
20 {
21     int n;
22     cin >> n;
23     for (int i = 1; i <= n; i ++)
24         {
25         cin >> a[i];
26         sum[i] = sum[i - 1] + a[i];
27          }
28     if(sum[n] % 2 == 1)
29     {
30         puts("NO");
31         return 0;
32     }
33     ll t = sum[n] / 2;
34     
35     first[a[1]] = 1;
36     for (int i = 2; i <= n ; i++)
37     {
38         second[a[i]] ++;
39     }
40     ll res = 0;
41     for (int i = 1; i <= n; i ++)
42     {
43         first[a[i]] ++;
44         second[a[i]] --;
45         
46         res += a[i];
47         if(res == t)
48         {
49             puts("YES");
50             return 0;
51         }
52         else if(res < t)
53         {
54             if(second[t - res] > 0)
55             {
56                 puts("YES");
57                 return 0;
58             }
59         }
60         else
61         {
62             if(first[res - t] > 0)
63             {
64                 puts("YES");
65                 return 0;
66             }
67         }
68     }
69     
70     puts("NO");
71     
72     return 0;
73 }
D1

第二种方法，对于任意一个数字a[i]来说，只有三种结果加入前缀，加入后缀，不动。加入前缀，等于要在前缀中找到sum/2-a[i]的位置，然后插进去。 加入后缀，等于要在后缀中找到sum/2 -a[i]，因为

我们是用前缀和来维护后缀和，那么对于前缀来说就是寻找sum/2 + a[i]。然后二分。

 1  #include <bits/stdc++.h>
 2  using namespace std;
 3 typedef long long ll;
 4  const int N=100010;
 5 ll s[N],a[N],sum;
 6  int n;
 7 bool find(int l,int r,ll x)
 8  {
 9      while(l<=r)
10     {
11          int mid=(l+r)/2;
12          if(s[mid]==x)
13              return 1;
14         if(s[mid]<x)
15              l=mid+1;
16          else r=mid-1;
17      }
18    return 0;
19  }
20  int main()
21  {
22     scanf("%d",&n);
23      for(int i=1;i<=n;i++)
24      {
25          scanf("%lld",&a[i]);
26          sum+=a[i];
27          s[i]=s[i-1]+a[i];//求前缀和
28      }
29      if(sum&1)
30      {
31          cout<<"NO"<<endl;
32          return 0;
33      }
34      sum/=2;
35     for(int i=1;i<=n;i++)
36      {
37          if(find(i+1,n,sum+a[i])||find(1,i-1,sum-a[i]))
38         {
39              cout<<"YES"<<endl;
40              return 0;
41          }
42      }
43      cout<<"NO"<<endl;
44      return 0;
45  }
D2

E.Selling Souvenirs

一个01背包问题，然后暴力不行。但是重量只有1， 2 ， 3。首先枚举使用1， 2，dp[m]的最大值。那么加入3的时候， 可以比较加入了几个三的时候值最大。

#include <bits/stdc++.h>

#define ll long long
#define MAXN 300005

using namespace std;

struct node{
    ll v,s1,s2;
}dp[MAXN];

ll goods[4][MAXN];
ll num[4];
ll sum[MAXN];

int cmp(ll a,ll b){
    return a > b;
}

int main(){
    ll n,m,w,c;
    while(~scanf("%lld %lld",&n,&m)){
        memset(goods,0,sizeof(goods));
        memset(num,0,sizeof(num));
        memset(dp,0,sizeof(dp));
        for(ll i = 0;i < n;i++){
            scanf("%lld %lld",&w,&c);
            goods[w][++num[w]] = c;
        }
        for(ll i = 1;i <= 3;i++){
            sort(goods[i] + 1,goods[i] + 1 + num[i],cmp);
        }
        for(ll i = 1;i <= num[3];i++){
            sum[i] = sum[i - 1] + goods[3][i];
        }
        for(ll i = 1;i <= m;i++){
            dp[i] = dp[i - 1];
            if(dp[i - 1].v + goods[1][dp[i - 1].s1 + 1] > dp[i].v){
                dp[i].v = dp[i - 1].v + goods[1][dp[i - 1].s1 + 1];
                dp[i].s1 = dp[i - 1].s1 + 1;
                dp[i].s2 = dp[i - 1].s2;
            }
            if(i >= 2 && dp[i - 2].v + goods[2][dp[i - 2].s2 + 1] > dp[i].v){
                dp[i].v = dp[i - 2].v + goods[2][dp[i - 2].s2 + 1];
                dp[i].s1 = dp[i - 2].s1;
                dp[i].s2 = dp[i - 2].s2 + 1;
            }
        }
        ll ans = 0;
        for(ll i = 0;i <= num[3] && i * 3 <= m;i++){
            ans = max(ans,dp[m - i * 3].v + sum[i]);
        }
        printf("%lld
",ans);
    }
}
E

F.Card Game

不会。

G.Anthem of Berland

不会。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/xwdzuishuai/p/11215378.html