• edu cf #137 Div.2(A~D)


    edu Cf #137 Div.2

    A. Password

    • 题意

      • 一个四位数密码,只含有两种数,每种数有两个。已知有n种数不是密码中使用的数,问密码有多少种可能
    • 题解

      • 排列组合,当确定密码中使用某两种数时,其共有6种密码可能。所以由n先确定能选出多少种2个数的组合,组合数*6即为答案
    • 代码

    #include 
    
    using namespace std;
    
    void solve() {
        int n;cin>>n;
        for(int i=0;i<n;i++){
            int x; cin>>x;
        }
        n=10-n;
        cout<<3*n*(n-1)<<'\n';
    }
    
    int main() {
        int t; cin>>t;
        while(t--) solve();
        
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    B. Permutation Value

    • 题意

      • 构造一个n的排列,使得排列中连续子序列也是排列的数量最小
    • 题解

      • 贪心构造,因为排列一定需要1,所以把1放在最边上,同时把2放在另一边,此时连续子序列为排列的数量为2,[1] , [1…n] 。中间的随便放。
    • 代码

    #include 
    
    using namespace std;
    
    void solve() {
        int n; cin>>n;
        for(int i=1;i<=n;i++)
            if(i&1) cout<<i<<' ';
        for(int i=n;i>=1;i--)
            if(i%2==0) cout<<i<<' ';
        cout<<'\n';
    }
    
    int main() {
        int t; cin>>t;
        while(t--) solve();
        
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    C. Save the Magazines

    • 题意

      • 有一排n个箱子,箱子里面装有书,有的箱子没有盖子有的有盖子。
      • 现在可以进行如下操作,将i的盖子放在i-1号箱子上面,操作次数不限
      • 现在要下雨了,请计算做多能有多少书不被淋湿
    • 题解

      • 贪心,最简单的想法,当前一个箱子的书比当前箱子的书多,且此箱子有盖子前面箱子没有盖子,那么就交换这两个箱子的盖子。
      • 不失一般性的,我们需要把一个箱子有盖子延伸到一段位置的箱子都有盖子。因为只能向前移动一个,所以只需要考虑这段1的前面一个0,然后考虑这段的书移动还是不移动更优。
      • 通过上面的模拟得到最终的箱子状态,把答案相加即可
    • 代码

    #include 
    
    using namespace std;
    const int N=2e5+10;
    
    int a[N],sum[N];
    char s[N];
    
    void solve() {
        long long res=0;
        int n; cin>>n;
        cin>>s+1;
        int last=-1;
        for(int i=1;i<=n;i++) {
            cin>>a[i];
            sum[i]=sum[i-1]+a[i];//前缀和,用于计算一段箱子书的和比较
        }
        for(int i=1;i<=n;i++) {
            if(s[i]=='0') last=i;//上一个0的位置
            else if(last!=-1) {//能移动的情况下
                if(sum[i]-sum[last]<sum[i-1]-sum[last-1]) {//移动更优
                    s[i]='0'; s[last]='1';//那么移动,s中的盖子变化
                    last=i;//上一个0的位置变化
                }
            }
        }
        for(int i=1;i<=n;i++)//计算答案
            if(s[i]=='1') res+=a[i];
        cout<<res<<'\n';
    }
    
    int main() {
        int t; cin>>t;
        while(t--) solve();
        
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    D. Problem with Random Tests

    • 题意

      • 给一个01串,选出两个字串,使得两个子串的或运算的值最大,求能够得到的或运算最大值
    • 题解

      • 贪心+暴力,首先第一个子串一定是字符串本身(或者说是去掉前导零的字符串本身),因为这样能保证前面的1一定最或运算中保留下来,尽可能最大了。而另一个串的任务就是把字符串最靠前的0经过或运算后变成1,这样贪心最大。
      • 当另一个子串也为字符串本身时,是不能达到上述所说的把0变成1的,可以依次把这个子串右移,而这种方式一定可以造出或运算值最大的两个子串。
      • 右移几次?由于给的字符串是随机的,连续50个全部是1的可能性为1/20^50,几乎不可能,所以暴力移动50次即可
    • 代码

    #include 
    #include 
    #include 
    #include 
    
    using namespace std;
    
    string erase_lead_zeros(string s) {//去除前导零
        int i=0,len=s.size();
        for(i=0;i<len-1;i++) 
            if(s[i]=='1') break;
        return s.substr(i);
    }
    
    int main() {
        int n; string s;
        cin>>n>>s;
        
        bitset<1000005> a(s),b(s);//bitset可以进行运算,而且还能和string互通有无
        string ans=a.to_string();
        for(int i=1;i<=50;i++) 
            ans=max(ans,(a | (b>>i)).to_string());
        
        cout<<erase_lead_zeros(ans)<<'\n';
        
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
  • 相关阅读:
    mybatis查询mysql 数据库中 BLOB字段,结果出现乱码
    C++提高:04STL- 函数对象
    155. 最小栈
    pymysql创建数据库连接
    JDBC概述
    将按顺序表存储的数组转化为链式二叉树并且按照先序、中序、后序排列分别输出
    GO的继承重写多态反射学习
    css 高级选择器
    Github仓库每日更新京东、淘宝、天猫各品类优惠券
    C++核心编程
  • 原文地址:https://blog.csdn.net/m0_49843646/article/details/127431838