Brief description:

Problem A. Dom

… 删除一个字符串中的所有的 “CAMBRIDGE” 中的字符。。

import re
print re.sub("[CAMBRIDGE]","",raw_input())

Problem B. F7

。。n 个人参加一个比赛，（没有并列。。
。。其中第 i 名 获得 n-i+1 分。。
现在给定 n 个人一个初始分数，问最后有多少人可能获得总分第一？（并列第一也可以。。

I = lambda: map(int, raw_input().split())

n = input() 
a = [0] * n
for i in range(0, n):
	a[i] = input()

a.sort()

i = n		
best = 0

while i>=0:	
	i -= 1
	if (a[i]+n < best): break	
	if (a[i]+n-i > best): best = a[i]+n-i
print n-i-1	

（贪心。。Python 后三个点超时。。

。。。

Problem C. Koncert

。。。我这个蠢飞了啊。这个简直就是 bug 啊。
。。。进去会场里面还能带票出来给别人。跪跪跪。。。
。模拟。。

Problem D. Ljubomora

。。n 个人 m 堆石子，第 i 堆石子有 ai 个。。现在要把这 m 堆石子分给这 n
个人，要求每个人拿到的石子必须来自同一堆。。。求方案使得拿到石子最多的人拿到的最少。。
二分答案判定。。（假设答案为 x，若满足 则合法。。

Problem E. Snaga

定义 K(x) 为最小的不能整除 x 的数，定义 ( 。。
求 。

Problem F. Mars

要求构造一个 2^k 阶的排列。。
满足以此排列构造的满二叉树的每个结点，（每个结点是一个集合，以 ai 位置的数为叶子，然后每个结点由其左右子树合并而成。。
。都是一段连续的数字。。已知每对数字之间存在一个斥力。。
最小化排列相邻数字之间的斥力和。。。

Analysis:

Problem E. Snaga

注意到 的值很小（大概不超过 100 。。。
于是暴力即可。。

Problem F. Mars

F[i][j] 表示前 i 个数，最后一个是 j。我们注意到能转移到这个状态的状态，时一个长度为 low_bit(i) 的区间。
注意到我们可以用神位运算直接得到这个区间。。这样暴力的话复杂度就是 O(n^2logn) 。。。。

const int N = 1029;

int f[N][N], a[N][N];
int n, z;

int main(){

    n = _1(RD()); REP_2(i, j, n, n) RD(a[i][j]);

    FLC(f, 0x3f), RST(f[0]); FOR(i, 1, n) REP(j, n){
        int s = (j - j % low_bit(i)) ^ low_bit(i), e = s + low_bit(i);
        FOR(k, s, e) checkMin(f[i][j], f[i-1][k] + a[j][k]);
    }

    OT(*min_element(f[n-1], f[n-1]+n));
}

。动态规划，位运算。。

External link:

http://evaluator.hsin.hr/index.php
http://www.codeforces.com/blog/entry/5585

Posted by xiaodao
Category: 日常
Tags: 施工中