Codeforces Round #694 (Div. 2) 题解(A-D)

E和F通过人数太少,也由于个人能力问题,就不去补了。

A Strange Partition

题意

给出长度为n的数组和一个整数x,我们可以把其中任意两个数合并为一个数。数组的“美丽值”计算方法为数组中所有元素分别对x除法(向上取整)的和,求最大和最小的的“美丽值”。

题解

显而易见,元素越多,“美丽值”越大,反之越小。
分别除和加在一起除即为最大和最小值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f 
int main(void)
{
    int _;
    cin>>_;
    while(_--){
        ll n,x;
        cin>>n>>x;
        ll s,maxsum=0,sum=0;
        for(int i=0;i<n;i++){
            cin>>s;
            sum+=s;
            if(s%x){
              maxsum+=s/x+1;
            }
            else{
              maxsum+=s/x;
            }

        }
        if(sum%x){
              sum=sum/x+1;
            }
            else{
              sum=sum/x;
            }

        cout<<sum<<" "<<maxsum<<endl;
    }
}

B Strange List

题意

还是给出一个长度n的数组和一个整数x。从头开始遍历,如果n_i%x为0则将n个n_i/x追加到数组末端,否则停止遍历,求最终数组的和。

题解

直接模拟即可,注意内存优化。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
    int _;
    cin>>_;
    while(_--){
        deque<pair<ll,ll>> m;
        ll sum=0,flag=0;
        int n,x,s;
        cin>>n>>x;
        for(int i=0;i<n;i++){
            cin>>s;
            pair<ll,ll> p;
            p.first=s;
            p.second=1;
            m.push_back(p); 
        }
        for(int i=0;i<m.size();i++){
            sum+=m[i].first*m[i].second;
            if(m[i].first%x==0&&flag==0){
                pair<ll,ll> p;
                p.first=m[i].first/x;
                p.second=m[i].second*x;
                m.push_back(p);
            }
            else{
                flag=1;
            }
        }
        cout<<sum<<endl;
    }
}

C Strange Birthday Party

题意

Petya举办生日聚会,有n个朋友和m个礼物,Petya为每位朋友分配了一个值k_i,礼物一定按照结果顺序排列(c_j)。Petya可以给朋友送礼物(必须满足条件j\leq k_i),也可以直接给他们c_{k_{i}}美元,每个礼物只能买一次,求最小花费。

题解

把朋友排个序,然后可以拿礼物或者给钱。
从后向前遍历,因为礼物是有序的,所以便宜的礼物优先给后面,前面的直接给钱就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
    int _;
    cin>>_;
    while(_--){
        ll n,m;
        cin>>n>>m;
        ll k[n],c[m+1];
        for(int i=0;i<n;i++) cin>>k[i];
        for(int i=1;i<=m;i++) cin>>c[i];
        sort(k,k+n);
        ll sum=0,fr=1;
        for(int i=n-1;i>=0;i--){
            if(fr<=k[i]){
                sum+=c[fr];
                fr++;
            }
            else sum+=c[k[i]];
        }
        cout<<sum<<endl;
    }
}

D Strange Definition

题意

如果x和y的\frac{lcm(x,y)}{gcd(x,y)}为完全平方数,即x,y满足关系“adjacent”。
给出长度为n的数组a,每次操作会将a_i替换为所有和它具有adjacent关系的元素(包括自身)的乘积。
d_i为与a_i具有adjacent关系的元素的个数(包括其本身),数组的优美度为d_i的最大值。
现有q次查询,每次查询给一个w,求w次操作后的优美度。

题解

已知lcm(x,y)=\frac{xy}{gcd(x,y)}
那么\frac{lcm(x,y)}{gcd(x,y)}=\frac{xy}{gcd(x,y)^2}
gcd(x,y)^2一定是完全平方数,如果xy是完全平方数,则\frac{xy}{gcd(x,y)^2}是完全平方数。
所以\frac{lcm(x,y)}{gcd(x,y)}为完全平方数等价于xy为完全平方数。
首先,数组中任何一个整数a都可以表示成a=br^2(r为大于等于1的整数),当r为1时,也就是我们把所有的完全平方数约掉,只有a_i=a_j的时候,a_ia_j才满足adjacent关系。所以,这里可以得出,当w=0时,答案就是数组中个数最多元素的个数。
我们输入数据之后,用map<int,int> m保存,key为b,value为个数。
另外,由于平方的性质,一次变换和多次变换结果相同。当w大于等于1时,若b等于1,则该数和一一个完全平方数满足adjacent关系。当进行变换时,所有具有adjacent关系的数的b一定相等,奇数个b相乘一定不是完全平方数(b=1除外),偶数个b相乘一定是完全平方数。另外,如果x和y都是完全平方数,那么x和y具有adjacent关系。所以答案就是max(所有偶数个元素(b不为1)value的和+b=1的value,b_i的value(value奇数且value最大))。

#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,s;
        map<int,int> a;
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>s;
            for(int j=2;j*j<=s;j++){//去除完全平方数
                while(s%(j*j)==0){
                    s=s/(j*j);
                }
            }
            a[s]++;
        }
        int re0=0,re1=0,re2=0;
        for(auto i:a){
        //cout<<"i"<<" "<<i.first<<" "<<i.second<<endl;
           re0=max(i.second,re0);
           if(i.second%2==0) re2+=i.second;//奇数取最大
           else re1=max(re1,i.second);//偶数就相加
        }
        if(a[1]%2==1) re2+=a[1];//如果1是奇数,加上1
        re1=max(re1,re2);//奇数和偶数的最大值
        ll q,w;
        cin>>q;
        for(ll i=0;i<q;i++){
            cin>>w;
            //scanf("%lld",&w);
            if(w==0)cout<<re0<<endl;
            else cout<<re1<<endl;
        }
    }
}

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


知识共享许可协议
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
小恐龙
花!
上一篇
下一篇