主题

主题

 
   

F. Elongated Matrix

原题:http://codeforces.com/problemset/problem/1102/F

You are given a matrix a, consisting of n rows and m columns. Each cell contains an integer in it.

You can change the order of rows arbitrarily (including leaving the initial order), but you can't change the order of cells in a row. After you pick...

 
 
 
   

E. Monotonic Renumeration

原题:http://codeforces.com/problemset/problem/1102/E

You are given an array a consisting of nn integers. Let's denote monotonic renumeration of array a as an array b consisting of n integers such that all of the following conditions are met:

  • b1=0;

  • for every pair of indices i and j such that 1≤i...

 
 
 
   

D. Balanced Ternary String

原题:http://codeforces.com/problemset/problem/1102/D

You are given a string ss consisting of exactly nn characters, and each character is either '0', '1' or '2'. Such strings are called ternary strings.

Your task is to replace minimum number of characters in this string with other characters to...

 
 
 
   

C. Doors Breaking and Repairing

原题:http://codeforces.com/problemset/problem/1102/C

You are policeman and you are playing a game with Slavik. The game is turn-based and each turn consists of two phases. During the first phase you make your move and during the second phase Slavik makes his move.

There are n doors, the ii-th door initially...

 
 
 
   

Go on

大概要重新回来了吧,我想。


大概两周前,因为拿错了伞认识了两位朋友。有一位高中做OI的,居然知道我在LOFTER上写代码!当然,让人震惊的,不是“有人知道我在LOFTER上写代码”,而是“有人在LOFTER上写代码”……


今天打开电脑突然发现一件很头疼的事情。


CSDN CODE准备关闭了。

我的代码都是代码片(代码笔记),并不是项目,因此不能一键转移。

于是准备马上把代码下载下来再上传……找了很多贴代码的地方,本来敲定好准备把代码弄到码云上去,结果发现码云一小时只能上传20个文件……果断Github……

当然代价是学习了一天怎么用Github。

而且比较糟糕的时Github...

 
 
 
   

常数优化与底层优化的小技巧

  • 扯淡

常数优化:

#1

常数优化一直是OI中存在的问题。很多知名选手轻松想出了正解,或者不知名选手(如鄙人)绞尽脑汁终于想出了正解,结果出题人用(Sang)心(xin)良(Bing)苦(Kuang)卡常让本应该得到的分数丢失。

这是一种值(Ying)得(Gai)推(Bei)广(Biao)的行为,考查OIer的综合素质。不过本蒟认为,OI本应该考察的核心应该是算法而不是编程技巧。但是为了对付这样高(Wu)明(Liao)的出题人,我们需要一些小小的卡常技巧。

另一个问题是在,想出了一个稍差的解法,如一个O(nlog^3n)的解法。然而标程是O(nlog^2n)。那么我们就需要使...

 
 
 
   

LCT对子树信息的维护

  • 扯淡

以前总是以为LCT只能够维护树链信息。

现在长知识了。

总是有很多神犇,出一些 加边+删边+换根+子树查询 的问题。

那么我们拥有了LCT这种强大的数据结构之后,就可以实现了。


  • 定义

我们定义几种儿子:

  1. x的虚儿子:若在LCT中,Fa[y]=x,且y不为xSplay的儿子,那么我们称y为x的一个虚儿子。

  2. x的实儿子:x的Splay的儿子。众所周知,x的实儿子不一定是x在原树上的儿子。

再定义几种信息:

  1. x的“虚儿子信息”:x的所有的虚儿子的“总信息”。

  2. x的“总信息”:x的“虚儿子信息”+x的实儿子的“...

 
 
 
   

NanoApe Loves Sequence Ⅱ

原题:http://acm.hdu.edu.cn/showproblem.php?pid=5806

Problem Description

NanoApe, the Retired Dog, has returned back to prepare for for the National Higher Education Entrance Examination!

In math class, NanoApe picked up sequences once again. He wrote down a sequence with n numbers and a number m on...

 
 
 
   

Price List Strike Back

原题:http://acm.hdu.edu.cn/showproblem.php?pid=5808

Problem Description

There are n shops numbered with successive integers from 1 to n in Byteland. Every shop sells only one kind of goods, and the price of the i-th shop's goods is vi. The distance between the i-th shop and Byteasar's home is di.

Every...

 
 
 
   

Palace

原题:http://acm.hdu.edu.cn/showproblem.php?pid=5721

Problem Description

The last trial Venus imposes on Psyche is a quest to the underworld. She is to take a box and obtain in it a dose of the beauty of Prosperina, queen of the underworld.

There are n palaces in the underworld, which can be located...