> SCU-A Young tableau 
> 
> 直接搜索如果减枝的好的话是有可能过的
> 另外一种比较好的方法是
> 把所有合法的Young tableau都求出来
> 然后假设源矩阵变为特定的Young tableau
> 计算步数，这可以用置换群的相关知识来做
> 
> SCU-B Calculator
> 
> BFS就行了，注意不需要等号的情况
> 
> SCU-C Free square
> 
> 先二分答案
> 现在判断<=mid共有多少个数是能被大于1的完全平方数整除
> 这个最大平方数最大可能是sqrt(mid)*sqrt(mid)
> i从2枚举到sqrt(mid)，计算有多少个数能被i*i整除
> 计数中会出现很多重复，如何去除重复成为关键
> 一种方法是，如果i已经能被大于1的完全平方数整除，那么不计它
> 否则统计它是多少个质数的乘积，根据容斥原理
> 如果为奇数个，则加上它，偶数个，减去它
> 
> SCU-D Distinct 
> 
> 两种方法
> 一种是求得中位数后用二分求得上界和下界 O(n*log2(m)) //m为数的大小
> 一种是用代数方法求得上界和下界 O(n)
> 
> SCU-E Rain and Fgj
> 
> 很简单的网络流
> 首先把点拆成两个点，两点之间的边的权值为原来点的权值
> 原来的边的权值为无限大
> 显然最小割就是所求
> 
> SCU-F Remove 
> 
> 贪心，遇到任何一个位置，从0到9（首位从1开始）试探该位置的最小值
> 这可能需要用到当前位置的右边的最近的某个数字的位置
> 这可以用动态规划解决
> [100000][10]
> [i][j]记录当前位置为i，数字为j的右边的最近位置
> [i][j]=[i+1][j];//如果当前位置的数不为j
> [i][j]=i;//如果当前位置的数为j
> 可能还有更好的算法
> 
> SCU-G Honoi*3
> 
> 定义：把三个相同的k看成X(k);
> 定义：A(k)完成上面X(K)不用保持相同之间的顺序的情况下最少步数。显然A(1)=3,A(2)=9........
> 定义：B(k)完成上面X(k)并且保持相同之间的顺序的情况下最少步数。显然B(1)=5,B(2)=17.......
> 如果在第k块的下面的所有都已经移好了，那把第X(K)的三块放好显然我们是从第二的跟移到第三的跟在这种情况下我们移动前面A(K)四次。明显可以得到公式B(k)=A(k-1)+A(k-1)+6+B(k-1)
> A(K)的公式显然A(K)=A(K-1)+A(K-1)+3;
> 从上面的两个公式递推得到B(n)=6*2^n-7
> 
> SCU-H Common area
> 
> 可以用半平面交来解决
> 注意多边形有可能是凹的，有可能完全重合，有可能一个被另外一个完全包括
> 
> SCU-I Match*3
> 
> 用a[i][j]表示第1个字符串和第2个字符串当前位置分别为i和j的最大匹配数
> 用b[i][j]表示第1个字符串和第3个字符串
> 这是经典的DP问题，O(n^2)
> 对于每个i，求出a[i][j]的最大值，求出b[i][j]的最大值，两个最大值的最小值就为i的最大值，所有i的最大值的最大值就为答案
> 
> SCU-J Counting numbers 
> 
> 状态压缩DP 
> 设数组f[1<<16][16]:f[i][j]中的状态i为二进制数,表示16个数位的某个集合,即当前状态使用过的那些数位,f[i][j]表示由这个集合的元素排列产生的数中对m取余得j的数的个数. 
> 则f[i][j]=sum{ f[i-(1<<k)][t],且(t*10+a[k])%m==j },其中a[i]表示第i个数位上的数 
>  
>  
> SCU-K Perfect subsequece 
> 
> 两个观察 
> 1.欲求子序列中必定没有两个相同的数 
> 2.设子序列为a[i],a[i+1]...a[i+k-1],则此序列为Perfect subsequence的充要条件是它们中没有重复的数且它们的和为k*(k+1)/2 
> 所以,我们先求出对于i的左右最近的会出现重复（不一定是自身重复）的下标,左为l[i],右为r[i],O(n)的复杂度 
> 然后对于每个a[i]=1,分别向左和向右扫描, 
> 以向左扫描为例,代码如下: 
> lmax=l[i];rmin=r[i];k=1; 
>  for (j=i;j>=0;j--) 
>  { 
>       if (j<=lmax) break;       // 若a[j]与以扫描数有相同,停止 
>       if (lmax<l[j]) lmax=l[j];  
>       if (rmin>r[j]) rmin=r[j]; // 更新左右边界 
>       if (a[j]>k) k=a[j];       // 更新当前子序列的最大值 
>       if (j+k-1>=rmin) continue;// 子序列的长度为k,设子序列以j为左边界,查看右边界是否越界. 
>       if (j==0) s=sum[j+k-1]; 
>        else s=sum[j+k-1]-sum[j-1]; 
>       if (s==k*(k+1)/2 && k>ans) ans=k; // 查看子序列是否perfect 
>  } 
> 有i,j两重循环,似乎是n^2的复杂度 
> 但考虑任意a[p],它最多只可能被左右离它最近的a[q]=1各扫描过一次,所以复杂度是O(n) 
> 故总的复杂度是O(n) 

• Re:salute to guodaniu (8) angelk700 2008-09-19 09:13:27