暑假CodeForces刷题Educational Codeforces Round 151 (Rated for Div. 2)（A、B、D）DP专场

目录

前言

 A. Forbidden Integer

B. Come Together

C. Strong Password

 D. Rating System

前言

        这场C题没做出来太可惜了
        

 A. Forbidden Integer

        链接：https://codeforces.com/contest/1845/problem/A

        题意：给你一个正整数n，同时你拥有除了数字x以外的无限多个1~k的数，问你能否用这些数相加来组成n

        思路：当x！=1时，你可以用n个1来表示出n，因此只需要考虑x=1时的情况，若k=1，则不可能组成n；若k=2且n为奇数，同样也不可能组成n。其余情况均可。

#include 
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
const LL maxn = 4e05+7;
const LL N=1e05+10;
const LL mod=1e09+7;
typedef pairpl;
priority_queue, greater >t;
priority_queue q;
int cmp(int a,int b)
{return a>=1;}return sum;
}
void solve() 
{int n , k , x;cin>>n>>k>>x;if(x == 1){if(k == 1){cout<<"NO\n";}else if(k == 2){if(n % 2 == 1){cout<<"NO\n";}else{cout<<"YES\n";cout<>t;while(t--){solve();}return 0;
}

B. Come Together

       链接：https://codeforces.com/contest/1845/problem/B

       题意：二维平面上三个点a，b，c，两个人从a分别走到b，c。他们只能通过上下左右来走，无法斜向走，同时要求路径最短。求他们所能一起走的距离的最大值。

这种情况之下，a（3,1），b（1,3），c（6,4）。他们所能一起走的距离最大为3     

        思路：分别对x坐标和y坐标分析，先对x进行分析，如果b，c两点均在a的同一侧，则他们可以一同行走 ,如果不在同一侧，则无法一同行走。同理，对于y来说也是一样的。最后答案则是两个加起来再加一（起始点）

#include 
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
const LL maxn = 4e05+7;
const LL N=1e05+10;
const LL mod=1e09+7;
typedef pairpl;
priority_queue, greater >t;
priority_queue q;
int cmp(int a,int b)`
{return a>=1;}return sum;
}
void solve() 
{int x[3],y[3];for(int i =  0 ; i < 3 ; i++)cin>>x[i]>>y[i];int ans = 0;int xa = x[1] - x[0] , xb = x[2] - x[0];int ya = y[1] - y[0] , yb = y[2] - y[0];if(xa > 0 && xb > 0){ans = min(xa,xb);if(ya > 0 && yb > 0){ans += min(ya,yb);}else if(ya < 0 && yb < 0){ans += min(abs(ya) , abs(yb));}}else if(xa < 0 && xb < 0){ans = min(abs(xa),abs(xb));if(ya > 0 && yb > 0){ans += min(ya,yb);}else if(ya < 0 && yb < 0){ans += min(abs(ya) , abs(yb));}		}else{if(ya > 0 && yb > 0){ans += min(ya,yb);}else if(ya < 0 && yb < 0){ans += min(abs(ya) , abs(yb));}				}cout<>t;while(t--){solve();}return 0;
}

C. Strong Password

        明天早上再补一下了...

 D. Rating System

        链接：https://codeforces.com/contest/1845/problem/D

        题意：a序列当中共有n个数和一个起评分0，总共进行n场比赛，每次比赛结束后评分加上ai（其中ai可能为负数）。此外，还有一个规则，你可以设置一个数k，使得如果你的评分达到k以上之后，在一场比赛之后评分如果小于k，则会将评分提升为k。让你求出一个k，使得最终能够得到的评分最多。

        例如序列 3 -2 1 2

        如果将k设为3，则每次比赛过后对应的评分为{3,3,4,6}，此时评分最大.

        再例如序列 -1 -2 -1

        如果将k设为0，则每次比赛过后对应的评分为{0,0,0}，此时评分最大

        思路：首先通过前缀和求出前x个数的总和。根据题意可以推出k取值为每轮比赛过后的评分。假设 , 那么总评分公式为  化简之后得到评分公式 所以问题转化为求

        所以，我们可以遍历一遍整个sum数组，同时维护当前序列x的最大前缀和max_sum和最大能够提升的评分max_point = max_sum - sum[x] ,最终max_point 所对应的max_sum就是所要求的k

#include 
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
const LL maxn = 4e05+7;
const LL N=1e05+10;
const LL mod=1e09+7;
typedef pairpl;
priority_queue, greater >t;
priority_queue q;
int cmp(int a,int b)
{return a>=1;}return sum;
}
void solve() 
{int n;cin>>n;LL a[n + 5];LL sum[n + 5];sum[0] = a[0] = 0;for(int i = 1 ;  i <= n ; i++){cin>>a[i];sum[i] = sum[i-1] + a[i];}LL maxx = sum[0] , cha = 0 , pos = 0,ans = 0;for(int i = 1 ; i<= n ; i++){if(cha > sum[i] - maxx){cha = sum[i] - maxx;ans = pos;}if(maxx < sum[i]){pos = i;maxx = sum[i];}}cout<>t;while(t--){solve();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！