当前位置: 代码迷 >> 综合 >> Codeforces 1279(A,B,C,D) round79(rated for Div.2 )
  详细解决方案

Codeforces 1279(A,B,C,D) round79(rated for Div.2 )

热度:5   发布时间:2023-12-22 14:11:06.0

传送门

A. New Year Garland

题意:将r个红灯和g个绿灯b个蓝灯串成一串,如果能使相邻两个灯不同色就输出YES,否则输出NO。(开头和结尾可以同色)。

思路:简单的思路,个数最多的灯max,个数最少的灯min,个数居中的灯mid。只要是(max-min)>mid+1;就是合法的方案。

AC代码:

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=2*1e5+5;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){
    int r,g,b;cin>>r>>g>>b;if(r<g){
    int t=r;r=g;g=t;}if(r<b){
    int t=r;r=b;b=t;}if(g<b){
    int t=g;g=b;b=t;}if(r-b>g+1)cout<<"NO"<<endl;else cout<<"YES"<<endl;}return 0;
}

B. Verse For Santa

题意:Vasya要在圣诞老人面前背诵n段诗歌,第i段需要花费ai分钟,圣诞老人给他s分钟背诵,背诵了多少段可以得到多少个礼物,期间可以跳过一段(全程只能跳一段或不跳)来获取更多的礼物。如果需要跳,输出被跳段落的地址,否则输出0.

思路:这个题我首先想到的就是用结构体来做,用id表示第i个位置以前的做大值地址,用ma来表示这个最大值,用su来表示背诵前i段需要的总时间。
再倒着遍历找到某个位置的su-ma<=s,输出这个位置的最大值id就行。(没想到这种方法还能过,哈哈~)

AC代码:

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=2*1e5+5;
struct node{
    ll su,ma,id;
}a[MAXN];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll t;cin>>t;while(t--){
    int n,s; cin>>n>>s;int tmp,maxx=-INF;for(int i=1;i<=n;i++){
    cin>>tmp;if(i==1){
    maxx=tmp;a[i].su=tmp;a[i].ma=tmp;a[i].id=i;}else{
    a[i].id=a[i-1].id;if(tmp>maxx){
    maxx=tmp;a[i].id=i;}a[i].ma=maxx;a[i].su=a[i-1].su+tmp;}}
// for(int i=1;i<=n;i++){
    
// cout<<a[i].su<<" "<<a[i].ma<<" "<<a[i].id<<endl;
// }for(int i=n;i>0;i--){
    if(i==n&&a[i].su<=s){
    cout<<0<<endl;break;}if(a[i].su>s&&a[i].su-a[i].ma<=s){
    cout<<a[i].id<<endl;break;}}}return 0;
}

C. Stack of Presents

题意:圣诞老人手上有n个礼物(乱序),需要按一定顺序送出m个礼物。第一个礼物如果在n个礼物中的i位置,那么他需要取出前面i-1个礼物才能送出礼物i,并且还需要把前i-1个礼物排序(使下一个需要送出的礼物用时最少,即在第一个位置)后放回去。计算送出这m个礼物总共需要花费的最少时间?

思路:标记第一个礼物在n个礼物中的位置为pose,若后面的礼物在它之前,则time+=1(因为前面的排序必定是最优的方案),若后面的礼物在它之后,用时time+=2*(i-1)+1,并且更新pose的值。(但是需要注意答案的数据范围)

AC代码:

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=2*1e5+5;
int a[MAXN],b[MAXN],d[MAXN];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll n,m,t;cin>>t;while(t--){
    cin>>n>>m;for(int i=1;i<=n;i++){
    cin>>a[i];d[a[i]]=i;}ll ans=0,pose=-1;for(int i=1;i<=m;i++){
    cin>>b[i];if(d[b[i]]>pose) ans+=2*(d[b[i]]-i)+1,pose=d[b[i]];else ans++;}cout<<ans<<endl;}return 0;
}

D. Santa’s Bot

哎,到这题我就不行了,呜呜~太菜了!!
只有向鱼姐姐学习啦!