Posts match “ CodeForces ” tag:

http://codeforces.com/problemset/problem/25/e

直接上solve()函数,简洁明了:

int solve()
{
    int i, j, minlen = mx * 3;
    For(i, 2) Forr(j, i + 1, 3) if (contain(i, j) || contain(j, i))
    {
        int x = len[i] > len[j] ? i : j, y = 3 - i - j;
        if (contain(x, y) || contain(y, x)) return max(len[x], len[y]);
        return len[x] + len[y] - max(overlap(x, y), overlap(y, x));
    }
    do minlen = min(minlen, len[0] + len[1] + len[2] - overlap(id[0], id[1]) - overlap(id[1], id[2]));
    while (next_permutation(id, id + 3));
    return minlen;
}
继续阅读

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=704
http://codeforces.com/gym/100379

题意很简单,给你两个斐波那契进制数,求二者相加得到的斐波那契进制数。

一位一位地算,每算一位就处理一下。

附:
Zeckendorf's theorem
Fibonacci coding

继续阅读

http://codeforces.com/gym/100379

首先说一个一般的方法,可以解决k阶线性齐次递推关系的通解的相邻两项之比的极限。
首先循环10遍后判断是否存在二者中至少有一个为0的情况,有就输出NO。
(10遍就够了,毕竟题目所给的都是整数)
若没有,记为递推式各项前面的系数
则由于

所以先把算出来,然后迭代1000次,结束后判断是否有即可。

但是二阶的递推是可以直接解出通解的,利用通解判断就行(见下方代码),复杂度O(1)。

继续阅读

http://codeforces.com/contest/427

A题手速题,2min AC
B题用RMQ过的。。其实只要维护一个<=t的cnt计数值就行了。。

int ans = 0, cnt = 0;
while (n--)
{
    scanf("%d", &val);
    if (val <= t) ++cnt;
    else cnt = 0;
    if (cnt >= c) ++ans;
}
printf("%d", ans);

C题强联通分量,注意用long long【怎么还有这么裸的模板题。。
D题后缀数组,建好高度数组后判断h[i]>h[i-1]&&h[i]>h[i+1]即可(代码太长,贴在最下方)
E题要计算路线和值,我们可以换个思路来累加——不按时间顺序累加,而是按这段路重复走的次数累加:

// 输入已经保证是有序的
ll ans = 0LL;
for (int i = 0, j = n - 1; i < j; i += m, j -= m) ans += (ll)(a[j] - a[i]);
printf("%I64d\n", ans << 1LL);
继续阅读

http://codeforces.com/problemset/problem/338/D

由于gcd(i,j)为i的因子,所以拿样例1来说,5,2,1均为行号的因子,所以行号至少是lcm(5,2)=10的倍数。
推而广之,行号至少是的倍数。

再看列号。
由于gcd(i,j)同时又为j的因子,设序列最左边的数的列号为j,则有

所以有

解此同余方程组即得j

最后判断下j+k-1是否<=m

陷阱:

  1. 求lcm需中途判断是否会超long long;
  2. 求出j后还要验证下能否还原出a数组,如果还原不了,由于这一行的数是周期性的,所以后面的j也不能满足,故输出NO
继续阅读

http://codeforces.com/contest/438

A题
考虑删除点的顺序,从点的大的往小的删除,然后考虑边的删除,我们会发现每条边对结果的“贡献”都是

B题
采用“边建图边计算”的方式。
依旧以边为主,首先对边按照min(a[u], a[v])递减排序,然后按此顺序加边,即用并查集动态维护连通分量。
由于边是按照min(a[u], a[v])递减排序的,所以两个连通分量上之间的连线所产生的“贡献”必为min(a[u], a[v]) * num[find(u)] * num[find(v)](根据乘法原理,以及这条边是桥),连通分量内的连线不产生贡献(因为不会经过)。

D题
如何处理操作2?
注意到若m<=a,则a%=m使a至少削减一半,所以这题维护区间和值以及区间最值,暴力完成操作2即可AC。

CF 443A

print len(set(raw_input() + ', ')) - 4

CF 133A

print "YNEOS"[not set('HQ9')&set(raw_input())::2]

CF 146A

n, t = input(), raw_input()
print ['NO', 'YES'][set(t) <= set('47') and sorted(t[:n/2] * 2) == sorted(t)] # 直接排序比统计47更简洁

最近的一场:
CF #253 (Div. 1) A

import itertools
n, cards = input(), map(set, set(raw_input().split()))
for sz in range(11):
  for hints in map(set, itertools.combinations('RGBYW12345', sz)):
    if len(cards) == len(set(map(tuple, (hints & x for x in cards)))):
      print sz
      exit()

附一个列表解析:
CF 66A

n = input()
print [type for type, x in(('byte', 7), ('short', 15), ('int', 31), ('long', 63), ('BigInteger', 1000)) if 2 ** x > n][0]

巧妙地结合reducelambda
CF 462A

n = input()
b = ['x'*(n+2)]
b += ['x'+raw_input()+'x' for i in range(n)]
b += ['x'*(n+2)]
print 'NO' if any(reduce(lambda x, y : x ^ y, (b[x/n+1+i][x%n+1+j] == 'o' for (i, j) in zip((1,0,-1,0), (0,1,0,-1)))) for x in range(n*n)) else 'YES'

持续更新。。

http://codeforces.com/contest/154

C题

观察能力+Hash。
注意到若两个点 u,v 能成为doubles,那么 u,v 对除了它们之外的其他所有点的连接关系是一样的。这样就可以用 Hash 判同了。
另外,分开判断 u,v 之间是否有连线的情况:没连线直接判,有连线需要加上自身该点。
最后注意用 long long 统计。

继续阅读

http://codeforces.com/contest/387

E题

贪心+树状数组。
很明显,从最小的开始删除得到的香肠最多。做个位置标记,然后往set里面加要留下的数(从小到大)的位置值,并对每一个要删除的数(这个不加到set中)求出其往左往右能到达的位置值,然后用树状数组统计这一区间有多少个没有删除的数,即为得到的香肠数。

继续阅读

http://codeforces.com/contest/301

A题

注意到在若干次操作后,我们可以使序列中的 0,2,4,... 个元素改变符号,并且,当n为奇数的时候,我们可以改变奇数个元素的符号。从而在n为奇数时我们可以改变任意多个元素的符号,而在n为偶数时只能改变偶数个与元素的符号。
继续讨论n为偶数的情况,若负数有偶数个,则都变为正即可;若负数有奇数个,则需要看绝对值最小的那个在原序列中是负数还是正数,若是负数则不改,若是整数则把那个负数改为正。

附 Python 代码:

n = input()
a = map(int, raw_input().split())
aa = map(abs, a)
print sum(aa) - (1 - n % 2) * len([i for i in a if i < 0]) % 2 * 2 * min(aa)

B题

很明显,每条边i-j的权值为(abs(x[i] - x[j]) + abs(y[i] - y[j])) * c - a[i]

(只贴出与题目有关的代码,宏定义见 GitHub

const int mx = int(1e2) + 5;

int d[mx][mx], a[mx], x[mx], y[mx];
int floyd(int n) {int i, j, k; For(k, n) For(i, n) For(j, n) Qmin(d[i][j], d[i][k] + d[k][j]); return d[0][n - 1];}

int main()
{
    int n, c, i, j;
    SII(n, c);
    SA(a + 1, i, n - 2);
    For(i, n) SII(x[i], y[i]);
    For(i, n) For(j, n) if (j != i) d[i][j] = (abs(x[i] - x[j]) + abs(y[i] - y[j])) * c - a[i];
    PI(floyd(n));
    return 0;
}

D题

只有查询,必然离线。
由于序列是1~n的某个全排列,我们可以从1~n逐步更新,同时进行计算。
我们可以用1~R的对数减去1~L-1的对数,但是这样算的结果包含了一个属于1~L-1另一个属于L~R的对数,减之。(在写的过程中还有很多细节,详见代码)

代码:

继续阅读

http://codeforces.com/contest/91

C题

求无向图中简单回路的个数。
自己画了几个图发现,其中k是不断加边产生的连通次数。

#include<cstdio>
int m, x, y, ans = 1, fa[100005];
int find(int x){return fa[x] ? fa[x] = find(fa[x]) : x;}
int main()
{
    scanf("%*d%d", &m);
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d", &x, &y);
        if (find(x) == find(y)) ans = ans * 2 % 1000000009;
        else fa[find(x)] = find(y);
        printf("%d\n", ans - 1);
    }
}