Codeforces Round #570 (Div. 3) B. Equalize Prices、C. Computer Game、D. Candy Box (easy version)、E. Subsequences (easy version)

B题题意：

给你n个物品的价格，你需要找出来一个值b，使得每一个物品与这个b的差值的绝对值小于k。找到最大的b输出，如果找不到，那就输出-1

题解：

很简单嘛，找到上下限直接二分。下限就是所有物品中最小的价格。上限就是所有物品中最大价格加上k

代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 #include<map>

 6 #include<math.h>

 7 using namespace std;

 8 typedef long long ll;

 9 const int maxn=1e5+5;

10 const int mod=26;

11 const int INF=0x3f3f3f3f;

12 const int block=300;

13 int main()

14 {

15     int t;

16     scanf("%d",&t);

17     while(t--)

18     {

19         int b,n,k,minn=INF,maxx=0;

20         scanf("%d%d",&n,&k);

21         for(int i=1;i<=n;++i)

22         {

23             scanf("%d",&b);

24             minn=min(minn,b);

25             maxx=max(maxx,b);

26         }

27         int mid=(minn+maxx)/2;

28         if(mid-minn<=k && maxx-mid<=k)

29         {

30             int ans=mid,m,l=mid,r=maxx+k;

31             while(l<=r)

32             {

33                 m=(l+r)/2;

34                 if(m-minn<=k)

35                 {

36                     ans=m;

37                     l=m+1;

38                 }

39                 else r=m-1;

40             }

41             printf("%d\n",ans);

42         }

43         else printf("-1\n");

44     }

45     return 0;

46 }

c题题意：

最开始有k电量，你需要玩n个回合的游戏，每一回合你可以有两个选择

1、玩游戏，但是要消耗a电量

2、边充电边玩，消耗b电量

还有一个限制：如果电量小于等于a，那就不可以玩游戏；如果电量小于等于b那就不可以边充边玩

如果玩游戏玩不了n个回合，就输出-1，否则就输出你玩游戏的次数(可不是边充边玩)

题解：

思路很容易想，但是就是实现难!

你可以先n个回合都选择第二种模式来玩游戏，看电量够不够。如果不够就直接输出-1

这里判断就可以先玩n-1个回合，看看剩下的电量大不大于b。如果大于那就证明可以玩够n个回合，否则就不可以

因为电量必须大于b才能边充边玩

然后就二分选择了几次第一个选择(即消耗电量为a) ，每一次的判断都类似上面的判断方式

还有就是要用long long

代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 #include<map>

 6 #include<math.h>

 7 using namespace std;

 8 typedef long long ll;

 9 const int maxn=1e5+5;

10 const int mod=26;

11 const int INF=0x3f3f3f3f;

12 const int block=300;

13 ll k,n,a,b;

14 bool check(ll x)

15 {

16     ll cha,ci;

17     if(x)

18     {

19         if(k-(a*(x-1))<=a) return 0;

20     }

21

22     cha=k-a*x;

23     ci=n-x;

24     if(ci==0) return 1;

25     if(cha-(b*(ci-1))<=b) return 0;

26     else return 1;

27 }

28 int main()

29 {

30     ll t;

31     cin>>t;

32     while(t--)

33     {

34         cin>>k>>n>>a>>b;

35         if(k-(b*(n-1))<=b)

36         {

37             printf("-1\n");

38             continue;

39         }

40         else

41         {

42             ll l=0,r=n,m,ans=0;

43             while(l<=r)

44             {

45                 m=(l+r)>>1;

46                 if(check(m))

47                 {

48                     ans=m;

49                     l=m+1;

50                 }

51                 else r=m-1;

52             }

53             printf("%I64d\n",ans);

54         }

55     }

56     return 0;

57 }

D题题意：

给你n个糖果，每一个糖果有一个种类，你需要用这些不同种类的糖果来弄成一个礼物

但是这个礼物里面各种类糖果的数量不能相同，你需要找出来这个礼物最多能由多少糖果构成

题解：

你会发现，如果一种糖果的个数是n，那么它可以拿出n-1、n-2、n-3来放入礼物中

注释+代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 #include<map>

 6 #include<math.h>

 7 using namespace std;

 8 typedef long long ll;

 9 const int maxn=2e5+5;

10 const int mod=26;

11 const int INF=0x3f3f3f3f;

12 const int block=300;

13 int v[maxn],w[maxn];

14 int main()

15 {

16     int t;

17     scanf("%d",&t);

18     while(t--)

19     {

20         int n,a,maxx=0;

21         scanf("%d",&n);

22         for(int i=1;i<=n;++i) //这里不能用memset，要不然会超时

23             v[i]=w[i]=0;

24         for(int i=1;i<=n;++i)

25         {

26             scanf("%d",&a);

27             w[v[a]]--;  //w是记录有多少种糖果且这种糖果的数量是v[a]

28             v[a]++;    //v是记录每一种糖果的数量

29             w[v[a]]++;

30             //printf("%d %d %d\n",a,v[a],w[v[a]]);

31             maxx=max(maxx,v[a]);

32         }

33         int ans=0,sum=0;//printf("%d**\n",maxx);

34         for(int i=maxx;i>0;--i)

35         {

36

37             ans+=w[i];

38             if(ans>0)  //如果你有一种糖果数量是5，此时这个可以来拿出来4个，来填充

39  //礼物，也可以都拿出来，这要看有没有其他种类的糖果也有这个数量个糖果

40                 sum+=i,ans--;

41         }

42         printf("%d\n",sum);

43     }

44     return 0;

45 }

E题题意：

给你一个长为n的字符串，你需要从中找出来k个不重复的子序列(注意是子序列而不是子串。子序列不需要连续，可以再原字符串中间删除字母)。如果可以找到输出你删除的总字母个数(你要是这个值尽可能地小)，如果不能输出-1

题解：

如果直接暴力dfs，那就相当于2^100,肯定会超时，那我们注意到k的值比较小，所有我们就可以找到k个子序列就可以了。又因为题目有要求输出的值尽量小。所以我们就可以按删除字符从小到大来枚举

我这里采用set去重

代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 #include<map>

 6 #include<math.h>

 7 #include<set>

 8 #include<queue>

 9 using namespace std;

10 typedef long long ll;

11 const int maxn=2e5+5;

12 const int mod=26;

13 const int INF=0x3f3f3f3f;

14 const int block=300;

15

16 int main()

17 {

18     int n,k,ans=0;

19     queue<string>r;

20     set<string>str;

21     string s;

22     cin>>n>>k;

23     cin>>s;

24     r.push(s);

25     str.insert(s);

26     while(!r.empty() && str.size()<k)

27     {

28         string ss=r.front();

29         r.pop();

30         int len=ss.size();

31         //printf("%d %d**\n",ss.length(),ss.size());

32         for(int i=0;i<len;++i)

33         {

34             string fresh=ss;

35             fresh.erase(i,1);

36             //cout<<fresh<<"**"<<endl;

37             if(!str.count(fresh) && str.size()<k)

38             {

39                 //cout<<1<<endl;

40                 r.push(fresh);

41                 str.insert(fresh);

42                 ans+=n-fresh.size();

43                 if(str.size()==k) break;

44             }

45         }

46     }

47     if(str.size()<k)

48         printf("-1\n");

49     else printf("%d\n",ans);

50 }

巴特西

Codeforces Round #570 (Div. 3) B. Equalize Prices、C. Computer Game、D. Candy Box (easy version)、E. Subsequences (easy version)

最新文章

热门文章