codeforces 练习

时间：2022-03-10 18:02:40

codeforces 627 D. Preorder Test

二分 + 树dp

做logn次树dp

codeforces 578D.LCS Again

给出一个字符串str，长度n<=10^6，由m种字符组成，问有多少个长度为n，与str的LCS 为 n-1的字符串t

这道题可以用dp套dp，但是我不会阿

可以找规律统计，考虑：

1.取哪个位置

2.放在哪个位置

3.放什么字符

可以知道，如果str分成了block份，每一份的字符相同，则

ans = block * n * (m - 1)

但是这样是会有一些重复计算的

这种情况会重复计算abababab这样交叉的部分

减去多计算的部分就可以了

codeforces 626 E. Simple Skewness

给出一个数组，从中取若干个数，使得新数组的平均数 - 中位数 最大

可以证明，取的一定是奇数个数

如果取了偶数个数，把最中间2个数较大的一个数去掉，情况不会变差，列个式子算一下就可以证明了。

所以奇数个数，我们就可以枚举中位数

确定了中位数后，

每次从小的数中拿x个，大的数拿x个，ans是关于x的函数，而且是先增大再减小的

就可以三分出此时最优的长度x

看了Mektpoy的代码，学到了三分的更好的姿势：

  　　　　int l = ,r = min(i-,n-i);

         while(r - l > ){

             int mid1 = l + (r - l) / ;

             int mid2 = r - (r - l) / ;

             if(check(i,mid1) < check(i,mid2))

                 l = mid1;

             else

                 r = mid2;

         }

         check(i,l);

         check(i,r);

         if(l +  < r)

             check(i,l+);

注意这里跳出循环后，可以是：

r - l = 1

r - l = 2  这个时候还需要check(l + 1)

r - l = 0 ???

所以需要check:l，r，l+1(l + 1 < r的情况下)

codeforces 600 E. Lomsat gelral

每一个节点建一棵平衡树，启发式合并，O(nlognlogn)

codeforces 117B Very Interesting Game

暴力

codeforces C. Mike and Foam

莫比乌斯 O(nsqrt(n))

codeforces 449 C. Jzzhu and Apples

贪心

487C. Prefix Product Sequence

构造

a[1] = 1,a[n] = n,a[i] = i * inv(i - 1)  (2 < i < n)

222 C. Reducing Fractions

分解因子

78 C. Beaver Game

博弈

691 F. Couple Cover

2维暴力统计，但是由于有i * j <= n 这个条件，其实复杂度是

n / 1 + n / 2 + n / 3 + ... + n / n = O(nlogn)的

225 E. Unsolvable

设第i个梅森素数是2 ^ t - 1，答案就是要求2 ^ (t - 1) - 1，t可以oeis查到

293 C. Cube Problem

给出n，求方程(a+b+c)^3 = a^3 + b^3 + c^3 + n的(a,b,c)的解数

分a = b = c，a = b,a != c，a < b < c 3种情况，暴力枚举，检验下就可以了

594  D REQ

好题

离线处理  bit维护前缀积

随机推荐

  1. 窥探Swift编程之别样的HelloWorld

    从今天就开始陆陆续续的发布一些有关Swift语言的东西,虽然目前在公司项目开发中Objective-C还是iOS开发的主力军,但是在不久的将来Swift将会成为iOS开发中的新生宠儿.所以在在Xcod ...

  2. &lbrack;linux&rsqb; 指令记录

    1> 查看linux版本号 lsb_release -a cat /etc/redhat-release

  3. js checkbox

    js checkbox <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http:/ ...

  4. &lbrack;iOS UI进阶 - 6&period;3&rsqb; UIView 动画

    1.UIView转场过渡动画   // // ViewController.m // UIViewAnimationTest // // Created by hellovoidworld on 15 ...

  5. Web Service中的XFire 传输List 自定义对象&period;

    我把这个创建的步骤和代码的贴出来,. 首先新建一个工程,取名就随便点啦..MyWebService,然后复制jar包到lib目录下, 创建包,建立接口..写一个javaBean的类, 以下是一个简单的 ...

  6. springMVC拦截器简单配置

    <!-- 拦截器 -->    <mvc:interceptors>        <mvc:interceptor>            <!-- 拦截所 ...

  7. RPC框架原理与实现

    了解一个框架最好的思路就是寻找一个该类型麻雀虽小五脏俱全的开源项目,不负所期,轻量级分布式 RPC 框架 RPC,全称 Remote Procedure Call(远程过程调用),即调用远程计算机上的 ...

  8. Windows Developer Day Review

    北京时间 3 月 8 日凌晨 1 点钟,今年的第一次 Windows Developer Day 正式召开.    因为时间太晚看不了直播,我也是第二天早上在公司看的重播.整个会议过程有很多值得去研究 ...

  9. 设计模式 — 简单工厂模式（staticFactory）

    这篇博文介绍简单工厂模式,设计模式并不是固定的二十三种,不同的书介绍的可能有出入,这篇介绍的简单工厂模式在有些书上就忽略不介绍了.设计模式是一套被反复使用的.多数人知晓的.经过分类编目的.代码设计经验 ...

  10. spark基础知识

    1.Spark是什么? UCBerkeley AMPlab所开源的类HadoopMapReduce的通用的并行计算框架. dfsSpark基于mapreduce算法实现的分布式计算,拥有HadoopM ...

相关文章