当前位置: 首页 > news >正文

Educational Codeforces Round 137 (Rated for Div. 2)-赛后总结

Educational Codeforces Round 137 (Rated for Div. 2)-赛后总结Educational Codeforces Round 137 (Rated for Div. 2)-赛后总结Educational Codeforces Round 137 (Rated for Div. 2)-赛后总结Educational Codeforces Round 137 (Rated for Div. 2)-赛后总结Educational Codeforces Round 137 (Rated for Div. 2)-赛后总结Educational Codeforces Round 137 (Rated for Div. 2)-赛后总结

总结

一言难尽的一晚,一定要把题目读全面,否则会酿成大祸

习得小技巧是 随机生成数据且禁止HACK的题目,一般暴力就能够通过,也就是本次的D

 

Problem - A - Codeforces

给定·已经出现的数字,用剩下的数字来两两组合成password,样例1易知两种颜色配对有6种方案,而n种颜色配对就有 (n-1)*n/2的配对方式

#include<bits/stdc++.h>
using namespace std;

typedef long long int  ll;

int book[10];

int main()
{

/*
两两组合   n*(n-1)/2*6


*/
int t;
cin>>t;

while(t--)
{
    memset(book,0,sizeof(book));
    int n;

    cin>>n;

    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;

        book[x]=1;
    }

    int cnt=0;

    for(int i=0;i<=9;i++)
    {
        if(!book[i])
            cnt++;
    }


    cout<<max(0,(cnt)*(cnt-1)*3)<<endl;

}

    return 0;
}

Problem - B - Codeforces

给定n,使得构造的n的排列种,<=n的排列最少。易知排列中嵌套排列的情况仅仅出现在 1--m,m个数相邻,首先1是无论如何无法避免,1--n也是如此,剩下的,只要我们拆散1,2,那么一切便都被拆散。 1    。。。。。      2,比如我们想构成 3的排列,就必须先构成 n的排列。

还是比较巧妙的

#include<bits/stdc++.h>
using namespace std;

typedef long long int  ll;


int main()
{


 int t;
 cin>>t;

 while(t--)
 {
     int n;
     cin>>n;

     int ans[100];

     int l=1,r=n;
     int now=1;

     while(now<=n)
     {
         ans[l]=now;
         l++;

         now++;
         if(now>n)
            break;

         ans[r]=now;

         r--;
         now++;
     }

     for(int i=1;i<=n;i++)
     {
         cout<<ans[i]<<" ";
     }

     cout<<endl;

 }

    return 0;
}

Problem - C - Codeforces

有必要吐槽一下,赛时马虎把盖子的移动方式看成了位置i能移动给全部左面的。也就导致交了一发优先队列的贪心导致白WA一发。正解应该是DP。正着推不太好搞,索性倒着。

dp[i][0]  dp[i][1]分别代表本位置是否使用本位置盖子时带来的最大收益。

本位置有盖子的时候,可以自己给自己盖住,也可以依靠前一个盖子没盖住自己时的状态转移

没有盖子的时候,可以不盖,也可以被上一个盖子盖住

细节就是状态转移时注意继承关系

#include<bits/stdc++.h>
using namespace std;

typedef long long int  ll;

ll dp[200000+10][2];
ll a[200000+10];
int main()
{

    int t;
    cin>>t;

    while(t--)
    {
        int n;
        cin>>n;

        string s;
        cin>>s;
        s=" "+s;

        int pos=0;

        for(int i=1; i<=n; i++)
        {
            dp[i][0]=0;
            dp[i][1]=0;

            cin>>a[i];

            if(s[i]=='1')
                pos=i;

        }


        for(int i=pos; i>=1; i--)
        {
            if(s[i]=='1')
            {

                if(s[i+1]=='1')
                {

                    dp[i][1]=max(dp[i+1][0],dp[i+1][1])+a[i];

                    dp[i][0]=max(dp[i+1][1],dp[i+1][0]+a[i]);


                }
                else
                {
                    dp[i][1]=max(dp[i+1][0],dp[i+1][1])+a[i];

                    dp[i][0]=max(dp[i+1][0],dp[i+1][1]);

                }

            }
            else
            {
                if(s[i+1]=='1')
                {
                    dp[i][1]=max(dp[i+1][0],dp[i+1][1]);

                    dp[i][0]=max(dp[i+1][0]+a[i],dp[i+1][1]);


                }
                else
                {
                    dp[i][1]=max(dp[i+1][0],dp[i+1][1]);

                    dp[i][0]=max(dp[i+1][1],dp[i+1][0]);

                }

            }

          
        }

        cout<<max(dp[1][0],dp[1][1])<<endl;

    }

    return 0;
}

 Problem - D - Codeforces

D题最为坑人,或许突破点在 “禁止HACK”上面,随机数字且禁止HACK的言外之意就是HACK必定会导致程序出错,也就暗示了我们使用暴力在随机数据的前提下是能够很大概率通过的。

另外一点小思维就是,s1必定选择整个串,s2的选择应该选择第一段连续的1

贪心的想,我们必须要消灭前面的零才能使得答案最优。而如果前导零存在,那么无论如何不会被消去。反之,前导零后面那几个1,所带领的后缀是我们消去之后0的关键。那么第二段,第三段的1呢?根本不用考虑,因为只要有第二段1,就说明了第二段之前是有至少一个0,而我们依靠第二段1引领的后缀永远无法消灭这段0,因为我们是从最后一位开始与原始串进行配对的。

所以仅仅需要考虑第一段1就可以。枚举第一段1中哪个1与第一个零配对,求出来最大即可

#include<bits/stdc++.h>
using namespace std;

typedef long long int  ll;


struct node

{
    int pos,cnt;

};
queue<node>q1,q2;
int a[1000000+10];

int main()
{

//先把全部1的位置装填,压入队列,第一个位置能够满足
//的,保留,接下来看第二个位置,保留,直到达到n

int n;
cin>>n;

string s;
cin>>s;
int len=0;

s=" "+s;

string now="";

int pos=0;

for(int i=1;s[i]!='1'&&i<=n;i++)
{
    now+=s[i];

    pos=i;
}

now="";

int pos2=n+1;

for(int i=pos+1;s[i]=='1'&&i<=n;i++)
{
    pos2=i;
    now+=s[i];

}


string ans="";

for(int i=pos+1;s[i]=='1'&&i<=n;i++)
{
    string temp="";

    int fuck=i;

    for(int j=pos2+1;j<=n;j++)
    {
        if(s[fuck]=='1'||s[j]=='1')
            temp+="1";
        else
            temp+="0";

        fuck++;
    }

    ans=max(ans,temp);
}

if(now.size()==0)
{
    cout<<0;
    return 0;

}
cout<<now+ans<<endl;

    return 0;
}

 

相关文章:

  • 【热门话题】Yarn:新一代JavaScript包管理器的安装与使用
  • mysql8.x在windows server2019安装并设置主从同步难点问题
  • 提高三维模型数据的立体裁剪技术
  • ODCC春季全会召开|忆联持续5年以领先技术为ODCC项目研究提供支持
  • LeetCode 20.有效的括号
  • (day 22)JavaScript学习笔记(内置对象1之Number、Math、Date)
  • 【React架构 - Scheduler中的MessageChannel】
  • 提升 Node.js 服务端性能:Fastify 框架
  • 代码随想录Leetcode474. 一和零
  • 【java】使用springMVC优雅的响应数据
  • JVM相关面试题
  • x-cmd pkg | horcrux - 采用 Secret sharing 的文件加密工具
  • Python图形处理
  • 【网站架构】4核CPU的MySQL调优3万RPS吞吐量?数据库集群高可用
  • Codeforces Round #828 (Div. 3)-赛后总结
  • C语言指针个人理解
  • 网络安全系统性学习路线「全文字详细介绍」
  • 你有一份奖学金,请注意查收~浙江财经大学 MBA奖学金
  • 手把手教你Linux的服务管理
  • 实验三 Windows窗体的设计及常用控件(1)
  • 【计算机毕业设计】java SpringBoot校园大学生志愿者服务系统
  • 【深入理解Kafka系列】第六章 __consumer_offsets(位移主题)
  • 脑机接口科普0008——侵入式与非侵入式
  • Nginx网站服务
  • Python游戏嗷大喵快跑设计
  • nginx负载均衡高可用部署
  • 【附源码】计算机毕业设计SSM怦然心动网上服装商城
  • YOLOv5实现佩戴安全帽检测和识别(含佩戴安全帽数据集+训练代码)
  • 【以太网硬件十六】双绞线有哪些种类?
  • 从零开始配置tensorflow深度学习环境(含cuda以及其他依赖)
  • 模型机的组合逻辑控制器
  • 私域流量和公域流量有何区别?为什么要打造自己的私域流量?