Educational Codeforces Round 95 (Rated for Div. 2)

原题链接

题外话

恢复性训练

A

题意

  一开始有一个树枝,然后每次和商人交易有两种方案
  - 1.减去一个树枝获得x个树枝
  - 2.减去y个树枝获得1个煤炭
  问你最少需要交换多少次才能获得k个火炬(一个火炬是由一个树枝 + 一个煤炭组成)

思路

   -  先判断出一共需要多少个树枝 <=> k*y+k-1(因为一开始有一个树枝)
   -  然后用这个一共需要的树枝数量除以(x-1)(因为每次都会减去一个树枝)
   -  记得判断一下 这个 一共需要的树枝数量 和  (x-1) 的关系 因为如果能模取不为零的话 需要多加一次交易
   -  最后加上一下兑换煤炭的数量即可

代码

#include <cstdio>
#include <algorithm>
#include<iomanip>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include<stack>

#include <cassert>
#include<map>
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define pb push_back
#define de(x) cerr<<#x<<" = "<<x<<endl
#define __i __int128
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)

#else
#define dbg(...)
#endif
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pLL;
const int inf=0x7fffffff;
const int N =5e5+10;
const int maxn = 200010;

void clear(unsigned char *pta, int size )
{//结构体初始化
    while(size>0)
    {
        *pta++ = 0;
        size --;
    }
}

LL   n, k, m ;
LL ar[200006],br[200005],cr[200005],dr[200005];
LL i,j,g;
LL dp[200006][2];

const int maxp = 1e5;

void answer(){
    cin >>n>> m>>k;
    LL cnt = k*m+k;
    cnt -- ;
    LL sum = cnt/(n-1)+ k;
    if(cnt%(n-1)!=0)sum ++;
    cout<<sum <<endl;

    return ;
}
int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0), cout.tie(0);

    int t;scanf("%d",&t);
    while(t--)answer();


    return 0;

}

B

题意

   给你一个数组,然后告诉你一些数组中的数字不能 进行移动,剩下的可以进行移动。
   然后通过移动这些允许移动的数字,使得P (从a1开始往后加的数字)<0 的情况最早出现( **还有一个条件就是如果加上下个数还是为负数,那么就继续加下去** ),求出这样的数组

思路

  因为要找最早的下标,所以需要用到贪心的思路, 肯定是能移动的数字sort 一下,从大往小排序,这样才能出现最早的数标是小于0的

代码

#include <cstdio>
#include <algorithm>
#include<iomanip>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include<stack>

#include <cassert>
#include<map>
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define pb push_back
#define de(x) cerr<<#x<<" = "<<x<<endl
#define __i __int128
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)

#else
#define dbg(...)
#endif
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pLL;
const int inf=0x7fffffff;
const int N =5e5+10;
const int maxn = 200010;

void clear(unsigned char *pta, int size )
{//结构体初始化
    while(size>0)
    {
        *pta++ = 0;
        size --;
    }
}

LL   n, k, m ;
LL ar[200006],br[200005],cr[200005],dr[200005];
LL i,j,g;
LL dp[200006][2];

const int maxp = 1e5;
int cmp(int a, int b){
    return a>b;

}
void answer(){
    cin >>n;int num =1;
    for(int i=1;i<=n;i++)cin >>ar[i];
    for(int i=1;i<=n;i++){
        cin >>br[i];
        if(!br[i]){
            cr[num++] =ar[i];
        }
    }
    sort(cr+1,cr+num,cmp);num =1 ;
    for(int i=1;i<=n;i++){
        if(!br[i]){
            ar[i] = cr[num++];
        }
    }
    for(int i=1;i<=n;i++)cout<<ar[i]<<" ";cout<<endl;

    return ;
}
int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0), cout.tie(0);

    int t;scanf("%d",&t);
    while(t--)answer();


    return 0;

}

C

题意

  就是说你和你的一个朋友玩一个游戏,然后这个游戏有n个boss ,分为 0 (简单) , 1 (困难) ,你的朋友只能打过 0 的boss (如果碰见 1 的boss ,你的朋友可以选择使用跳过卡), 你两个都可以 , 然后 你俩一次可以选择一个或者两个boss 进行解决 , 从你的朋友开始,然后在轮到你,这样下去,直到boss 全被消灭。问你最少需要多少个通关卡

思路

一开始以为是个贪心的简单题, 然后在wa了两次后,发现事情不简单,之后在网上找到的题解说是一个经典的dp问题(被自己菜枯)
- 直接用dp思路, 因为一开始固定是你的朋友开局, 所以确定dp【1】【0】(我设置的 0为朋友状态 , 1 为 你的状态) = 第一个数组的数,然后因为可能你的朋友可以继续搞个boss , 所以设置一下dp【2】【0】 = dp【1】【0】 + 第二个数组的数
- 因为第二个数可能由你开始解决所以设置一下dp【2】【1】 = 第一个数(表示第一个关卡你的朋友就用了跳关卡)
- 状态转移方程就是题面上说的意思 dp【i】【0】 = min(dp【i-1】【1】+ ar【i】,dp【i-2】【1】+ ar【i-1】+ ar【i-2】), dp【i】【1】 = min(dp【i-1】【0】,dp【i-2】【0】)(因为你不需要跳关,所以不需要加)
- 这样因为最后只需要统计一下min(dp【n】【0】,dp【n】【1】)就行(因为只需要判断为 1 的数量就行 )

代码

#include <cstdio>
#include <algorithm>
#include<iomanip>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include<stack>
#include <cassert>
#include<map>
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define pb push_back
#define de(x) cerr<<#x<<" = "<<x<<endl
#define __i __int128
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)

#else
#define dbg(...)
#endif
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pLL;
const int inf=0x7fffffff;
const int N =5e5+10;
const int maxn = 200010;

void clear(unsigned char *pta, int size )
{//结构体初始化
    while(size>0)
    {
        *pta++ = 0;
        size --;
    }
}

LL   n, k, m ;
LL ar[200006],br[200005],cr[200005],dr[200005];
LL i,j,g;
LL dp[200006][2];

const int maxp = 1e5;
int cmp(int a, int b){
    return a>b;

}
void answer(){
    cin >>n;
    for(int i=1;i<=n;i++)cin >>ar[i],dp[i][1] = dp[i][0] = maxn;
    dp[1][0] = ar[1] ,dp[2][0] = ar[1]+ar[2];
    dp[2][1] = ar[1];
    for(int i=3;i<=n;i++){
        dp[i][0] = min(dp[i-1][1] + ar[i] , dp[i-2][1] + ar[i-1] + ar[i]);
        dp[i][1] = min(dp[i-1][0] , dp[i-2][0]);
    }
    cout<<min(dp[n][0], dp[n][1])<<endl;
    return ;
}
int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0), cout.tie(0);

    int t;scanf("%d",&t);
    while(t--)answer();


    return 0;

}

上一篇:高德AR & 车道级导航技术演进与实践


下一篇:多维数组简介