出自 : http://hi.baidu.com/novosbirsk/blog/item/58c5fcfa46911e9159ee90b9.html

想到前面那种情况, 没想到后面的...代码就不转了

------------------

最近学校在搞ACM的竞赛培训。第一天的课程是网络流，半懂半不懂。之后就是组合数学，讲了Pólya原理及其应用。这道3270就是一道运用到置换群的题目。

题目的具体做法是参考刘汝佳的《算法艺术与信息学奥赛》，代码倒是自己实现的。大概思路是：
1.找出初

MXX师兄里插播的一个问题...
实在是想不到, 上CSDN问了下, tailzhou 给了一个代码.
我就不描述了...直接上代码.

#include <stdio.h>

int main()
{
    char str[]="asdssfas efsdsdss";
    int j=1;
    int n=sizeof(str)/sizeof(char);
    int idx=0;
    int coun

C++写的WA得烦了, 不知道是题意理解错还是代码有漏洞, 直接找资料用java的正则表达式写了...

转个参考资料: (出自http://www.ccw.com.cn/htm/app/aprog/01_7_31_4.asp)

如果你曾经用过Perl或任何其他内建正则表达式支持的语言，你一定知道用正则表达式处理文本和匹配模式是多么简单。如果你不熟悉这个术语，那么“正则表达式”（Regular Expressio

放了好~~~久的一道题. 以前总看着没办法, 现在回头看, 感觉也不那么难了. 就是个DP.

刚开始写的代码TLE了, 后来加强了一下判断, 优化后15MS AC.

设dp[i]为价值i的可达性. 初始dp[0]=1;

把总价值sum除2, 除不尽则不能划分. 否则dp[sum/2]为所求

挺显而易见的DP...

#include "stdio.h"
#include "string.h"

被某人拉去ZOJ帮做题...一开始写了个O(n^2)的, 华丽地TLE掉...貌似常数太大. 后来发现没利用好题目的条件, 再写了个也是O(n^2)的AC了, 貌似是130MS, 不大会看ZOJ的时间......好像最前面是分钟.

题目:

Minimum Inversion Number

---

Time limit: 1 Seconds   Memory limit: 32768K   
Total Submit: 1453 

-------------------------------------算法简述-----------------------------------------

ST算法O(nlogn)预处理,O(1)的查询指定区间的最值(以最小值为例)

基本上是把待求区间[l,r]分为两段长为len的区间

左边一段为[l,l+len-1],右边一段为[r-len+1,r]

len必须使得两段区间覆盖待求区间

设所求数组为w

两个月前AC过的一道DP题.现在发现了一个复杂度较低的算法了~贴上两次AC的代码比较一下吧.

--------------------------------------以前的--------------------------------------------

以下标i表示barn的每一种状态. 从低位向高位,第k位为1表示第k个barn未被占用,(0<=k<=m-1)

dp[i]=num表示另barn的状态为i的方法有num种

结果就是sum{dp[i]} (0<=i<=(1<<m)-1)

基本上是对每头牛扫描一遍全部状态,判断每个状态

貌似网上搜的都一样的版本(有错...貌似还不少).先把代码弄上来,如果POJ的SPJ没错的话,这代码就应该没错了.POJ 3239

有时间好好整理一下再把规则写一下.

#include "stdio.h"

int main()
{
          int n,k;
          int i;
          while(scanf("%d",&n)){
   

对每一个i(0<=i<n-1),算出区间[0,i]可以取的最大值left[i]和区间(i,n-1]的最大值right[i+1],他们的和为sum[i].left和right可以通过预处理,在计算时直接查出.

则所求为所有sum[i]中的最大值.(>0的数字少于2个的话特殊处理一下)

left的预处理:设一变量s初始为0,一直往右加,为负的时候则置0.left[i]为max(当前的s值,left[i-1]).

right同理,方向相反

一开始也是这么想的,不过在计算右区间最大值时还是想的从左到右的方向,成了O(n^2)了......

感觉这题还是挺强的...mark一下~

对并查集的扩展.看了下解题报告,总算有想法了.

sum[i]记录根结点i下面的结点数(包括自己)和up[i]记录在某结点i上面的结点数.则在一结点m之下的结点数为sum[findpar(m)]-up[m]-1   (findpar查找根结点)

在uni和findpar过程中更新sum和up的内容.(蓝色部分)

#include "stdio.h"

const int max_node=30005;

int par[max_node+1];
int up[max_node+1];
int sum[max_node+1];
int add;

int findpar(int num){