BZOI2730 | HNOI2012 矿场搭建

几句话题解:

先跑Tarjan求点双统计每个点双有几个割点

2个及以上->安全

1个->非这个割点随便建个出口

没->建两个

组合数学瞎算一波

 

#洛谷3917 异或序列

对于100% 的数据,1≤n≤105

做法是求异或前缀和然后按位讨论贡献

如果当前位k有奇数个1那么贡献为(numof1×numof0)×(1<<k)

 

USACO 草鉴定Grass Cownoisseur

In an effort to better manage the grazing patterns of his cows, Farmer John has installed one-way cow paths all over his farm. The farm consists of N fields, conveniently numbered 1..N, with each one-way cow path connecting a pair of fields. For example, if a path connects from field X to field Y, then cows are allowed to travel from X to Y but not from Y to X.

Bessie the cow, as we all know, enjoys eating grass from as many fields as possible. She always starts in field 1 at the beginning of the day and visits a sequence of fields, returning to field 1 at the end of the day. She tries to maximize the number of distinct fields along her route, since she gets to eat the grass in each one (if she visits a field multiple times, she only eats the grass there once).

As one might imagine, Bessie is not particularly happy about the one-way restriction on FJ’s paths, since this will likely reduce the number of distinct fields she can possibly visit along her daily route. She wonders how much grass she will be able to eat if she breaks the rules and follows up to one path in the wrong direction. Please compute the maximum number of distinct fields she can visit along a route starting and ending at field 1, where she can follow up to one path along the route in the wrong direction. Bessie can only travel backwards at most once in her journey. In particular, she cannot even take the same path backwards twice.

INPUT: (file grass.in)

The first line of input contains N and M, giving the number of fields and the number of one-way paths (1 <= N, M <= 100,000).

The following M lines each describe a one-way cow path. Each line contains two distinct field numbers X and Y, corresponding to a cow path from X to Y. The same cow path will never appear more than once.

OUTPUT: (file grass.out)

A single line indicating the maximum number of distinct fields Bessie

can visit along a route starting and ending at field 1, given that she can

follow at most one path along this route in the wrong direction.

四句话题解(非常简单):

Tarjan瞎缩一波点

然后单原SPFA求点1能到的点的答案贡献

然后跑单汇SPFA求能到点1的点的答案贡献

最后枚举反边判相连求答案

 

SDOI2005 遗传代码

此题luogu无题解

所以来一篇

用DSU+特判解决问题

 

先求一下森林和每棵树节点数

对于每个节点分别统计对答案贡献

最后特判一下单独的节点,还要+1

日常水这种题

 

BZOJ3289 Mato的文件管理

Time Limit: 40 Sec (Total)

Memory Limit: 128 MB

莫队+树状数组维护

类(jiu)似(shi)冒泡排序的过程

注意优化时间

BZOJ1876 | SDOI2009 SuperGCD

更相减损术+高精度板子

压位1000ms

注意对偶数优化,一奇一偶可以÷2

两个偶数同时÷2再乘回去可以优化减法次数

带修莫队板子

丢板子还需要别的内容吗

题目参见数颜色

USACO 2007MAR Face The Right Way

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 6005 Accepted: 2777

Description

Farmer John has arranged his N (1 ≤ N ≤ 5,000) cows in a row and many of them are facing forward, like good cows. Some of them are facing backward, though, and he needs them all to face forward to make his life perfect.

Fortunately, FJ recently bought an automatic cow turning machine. Since he purchased the discount model, it must be irrevocably preset to turn K (1 ≤ K  N) cows at once, and it can only turn cows that are all standing next to each other in line. Each time the machine is used, it reverses the facing direction of a contiguous group of K cows in the line (one cannot use it on fewer than K cows, e.g., at the either end of the line of cows). Each cow remains in the same *location* as before, but ends up facing the *opposite direction*. A cow that starts out facing forward will be turned backward by the machine and vice-versa.

Because FJ must pick a single, never-changing value of K, please help him determine the minimum value of K that minimizes the number of operations required by the machine to make all the cows face forward. Also determine M, the minimum number of machine operations required to get all the cows facing forward using that value of K.

Input

Line 1: A single integer: N 
Lines 2..N+1: Line i+1 contains a single character, F or B, indicating whether cow i is facing forward or backward.

Output

Line 1: Two space-separated integers: K and M

Sample Input

Sample Output

Hint

For K = 3, the machine must be operated three times: turn cows (1,2,3), (3,4,5), and finally (5,6,7)
呐 题意就这样
然后我们考虑枚举k做一个O(n^3)显然很简单
优化?尺取法
枚举k,从左到右对背面的牛操作
考虑能够影响当前牛的操作,是当前减去(k-1)的区间
然后统计一下这个区间有多少个操作对2取模就可以得到当前判断。
这样用一个类似前缀和的东西维护就行了 见代码
O(n^2)