NanoApe's Blog

既是咸鱼又是辣鸡

CodeChef糊做

NanoApe posted @ 2016年6月13日 21:50 in 蒟蒻不做题提前退役 with tags codechef , 2002 阅读

update:16.07.12

MMPROD

n 个数选择 k 个使得乘积最大

容易知道排序完乘积最大的方案肯定是某段前缀+某段后缀,然后转对数使得乘法变加法,多加一个变量来储存符号,枚举比较大小即可

FAIRPAIR

两组 n 个数,两两匹配,要使相同数匹配对数最小,并询问方案

暴力配对一发,然后对于一对相同数匹配,暴力枚举拆开其他哪对匹配能拆开来来合法交换

(或者变成匈牙利求最大匹配,然而总是 TLE)

LISLDS

构造长度为 n 的排列,使得其 LIS 和 LDS 为给定数值

构造题啊,那么我们可以将 n 分成 LDS 份,左边那份总比右边大,然后每份大小不超过 LIS,并且从小到大排序

MINSHIFT

给随机字符串,或者随机修改一个字符,或者将某个子串提出来询问最小表示法

随机字符串嘛,那我们算下,$26^4>10^5$,好极!我们就以 4 个字符为单位预处理,然后就区间询问最小值,再通过链表找到出发点,然后暴力比较大小,修改就维护上述信息

复杂度玄学(因为随机)

REGIONS

一棵树,问将每条边切断后剩余两棵树的直径

第一次 dfs 求出子树直径,第二次 dfs 求出边上子树的直径,然后维护下奇奇怪怪的信息,例如子树最深叶子、子树直径啊什么的

FURGRAPH

博弈游戏,双方轮流选点,最后得分为各自子图边权和,求最优策略下最后的分差;每次新加一条边并在线维护其最后分差

首先这类博弈游戏,我们可以将边权一分为二,分给点,然后点排序后分差就是奇偶位置的差,用Treap维护即可

SEAGCD2

给长度 n 和范围 [1,m],问有多少不同的序列满足不同位的数互质,$M \le 100$

状压 (2,3,5,7) 的状态,然后直接枚举质因子计算即可

POLYEVAL

给多项式,求当 x=0..786432 的时候多项式模 786433 的值

观察模数,786433=2^18*3+1,NTT 可以求出 $x=g^3,g^6...$ 的值,然后用三进制 FFT 求出全部值

(这里只是用到了三进制 FFT 的蝴蝶操作合并而已)

TRAVTREE

弄棵树,每次往集合内加一条路径,每次加询问和集合内多少条路径相交

两种相交类型,就是新加路径的lca在多少条路径上,或者是有多少lca在新加的路径上,注意lca重合的路径会算两次

然后就链剖即可


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter