Educational Codeforces Round 103 (Rated for Div. 2) 题解 (A-D)

括号位置放错了,C一直WA3,气死了,这场每题都在犯der。

A. K-divisible Sum

题意

由n个正整数组成的数组的和要整除k,求数组中的最大值。

题解

n和k搞反了,同时n>k考虑不周WA了两发,签到题都开始WA了。
k=1的时候,任何数都能整除1,直接输出1。
当n>k的时候,数组内一定只有1和2(因为和为k的倍数)。
n<=k的时候,就是k/n向上取整(要使得数最小,就必须接近平均,但不能出现小数只好向上取整。)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        ll n,k;
        cin>>n>>k;
        if(k==1){
            cout<<1<<endl;
            continue;
        }
        if(n>k){
            if(n%k) cout<<2<<endl;
            else cout<<1<<endl;
        }
        else{
           if(k%n) cout<<k/n+1<<endl;
            else cout<<k/n<<endl;
        }
    }
    return 0;

}

B. Inflation

题意

给出一个产品价格变化表,我们可以增加表中的任意数字,使得每个月的通货膨胀系数(\frac{p[i]}{\sum^{i-1}_ {i=0}p[i]}(i>0))小于等于k%,求最小增加的值。

题解

找出最大的通货膨胀系数,计算出让他小于等于k%需要增加的值即可,让最大的系数小于等于k,也就意味着所有的都会小于等于k%。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        int n,k;
        cin>>n>>k;
        vector<ll> num;
        ll s,sum=0;
        ll f=0;
        for(int i=0;i<n;i++){
            cin>>s;
            num.push_back(s);

            //cout<<s*100<<" "<<k*sum<<endl;
            if(i!=0){
                if(s*100>k*sum) f=max(f,s*100-k*sum);
            }
            sum+=s;

        }
        //cout<<f<<endl;
        if(f==0) cout<<0<<endl;
            else {
                if(f%k)cout<<f/k+1<<endl;
                else cout<<f/k<<endl;
            }
    }
    return 0;
}

C. Longest Simple Cycle

题意

有n条链子,长度c[i],从第二条开始,每条的第一个节点连接前一条的a[i]节点,最后一个结点连接前一条的b[i]节点,求连接后最长的简单环。

题解

贪心。
首先求出第一条链子能记入环的节点数,因为a[i]和b[i]的大小关系不确定,所以要加绝对值。
然后从第二条链子开始遍历,每次成环都可以以当前链子为终点,所以加上当前链子的长度。
当我们继续遍历的时候,有两种情况:
1.a[i+1]=b[i+1],这种意味着下一条链子前后连接到同一个点上,只能作为环的起始或终止。
2.a[i+1]!=b[i+1],这时候我们可以选择下一条链子的两个连接点的中间(如下图红色部分),也可以选择两边+前面的链子(如下图蓝色部分),我们取最长的。

https://enterdawn.top/wp-content/uploads/2021/01/cf1478C.png

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        int n;
        cin>>n;
        ll lon[n];
        ll con1[n];
        ll con2[n];
        ll re=0;
        ll s;
        for(int i=0;i<n;i++) cin>>lon[i];
        for(int i=0;i<n;i++) cin>>con1[i];
        for(int i=0;i<n;i++) cin>>con2[i];
        s=abs(con1[1]-con2[1])+1;
        for(int i=1;i<n;i++){
            //cout<<s<<" "<<s+lon[i]<<endl;
            re=max(re,s+lon[i]);
            if(i==n-1) break;
            if(con1[i+1]==con2[i+1]){
                s=1;
            }
            else s=max(s+lon[i]-abs(con1[i+1]-con2[i+1])+1,abs(con1[i+1]-con2[i+1])+1);
        }
        cout<<re<<endl;
    }

    return 0;

}

D. Journey

题意

有n+1个城市在一条直线上,中间有n条道路,每条道路都有方向,只能走导入方向和行进方向相同的道路,问最多经过几个城市。

题解

求每个点向左和向右的最大距离,相加即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
void swap(ll* a, ll* b) {
    int swapp = *a;
    *a = *b;
    *b = swapp;
}
ll max(ll a, ll b) {
    if (a > b) return a;
    return b;
}
ll min(ll a, ll b) {
    if (a < b) return a;
    return b;
}
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
int lcm(const int a, const int b)
{
    return a / gcd(a, b) * b;
}
bool isprime(ll num)
{
    if (num == 1)
        return 0;
    if (num == 2 || num == 3)
        return 1;
    if (num % 6 != 1 && num % 6 != 5)
        return 0;
    int tmp = sqrt(num);
    for (ll i = 5; i <= tmp; i += 6)
        if (num % i == 0 || num % (i + 2) == 0)
            return 0;
    return 1;
}
struct node{
    int top;
    int bottom;
    int num;
    /*bool operator < (node a){
        if(h!=a.h)
            return h < a.h;
        return w < a.w;
    }
    */
};
bool check(ll num,ll d){
    while(num!=0){
        if(num%10==d) return 1;
        else num=num/10;
    }
    return 0;
}
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _;
    cin>>_;
    while(_--){
       int n;
       cin>>n;
       string s;
       cin>>s;
       int numf[n+1];
       int numb[n+1];
       memset(numf,0,sizeof(numf));
       memset(numb,0,sizeof(numb));
       int f=0,i;
       for(i=0;i<=n;i++){
          if(i!=0&&((s[i-1]=='L'&&s[i]=='L')||(s[i-1]=='R'&&s[i]=='R'))){
            int fl=0;
            for(int j=i-f;j<i;j++){
                if(fl%2==0)numf[j]=f;
                fl++;
                f--;
            }
            f=0;
          }
          if(s[i]=='R') f++;
          else if(i!=0&&s[i-1]=='R'&&s[i]=='L')f++;
       }
        int fl=0;
        for(int j=i-f;j<i;j++){
            if(fl%2==0)numf[j-1]=f;
            fl++;
            f--;
        }
        f=0;
       for(i=n;i>=0;i--){
          if(i!=n&&((s[i+1]=='L'&&s[i]=='L')||(s[i+1]=='R'&&s[i]=='R'))){
            int fl=0;
            for(int j=i+f;j>i;j--){
                if(fl%2==0)numb[j+1]=f;
                fl++;
                f--;
            }
            f=0;
          }
          if(s[i]=='L') f++;
          else if(i!=n&&s[i+1]=='L'&&s[i]=='R')f++;
          //cout<<f<<endl;
       }
       fl=0;
        for(int j=i+f;j>i;j--){
            if(fl%2==0)numb[j+1]=f;
            fl++;
            f--;
        }
       for(int i=0;i<n+1;i++) cout<<numf[i]+numb[i]+1<<" ";
       cout<<endl;
    }

    return 0;

}

题目来源于https://codeforces.com/contest/1476

知识共享许可协议
Text is available under CC BY-NC-SA 4.0 unless otherwise stated.

除非特殊声明,本站所有内容均以 CC BY-NC-SA 4.0协议授权。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇