irachex's Blog

Andrew Stankevich's Contest #1 总结

2009-01-17T18:12:00.009+08:00

ZOJ2013 / SGU193 Chinese Girls' Amusement

题意：已知n，求最大的整数k，满足k<=n/2 && gcd(k,n)==1

算法：数论　高精度　O(1)

当n为奇数时, gcd(n,(n-1)/2)=gcd(n,n-1)=1 , k=(n-1)/2
当n为偶数时,若n/2为偶数, gcd(n,n/2-1)=gcd(n/2,n/2-1)=1,k=n/2-1

当n为偶数时,若n/2为奇数, gcd(n,n/2-2)=gcd(n/2,n/2-2)=1 , k=n/2-2

ZOJ2014 / SGU194 Reactor Cooling

题意：求一可行流，满足容量上下界限制条件和流量平衡条件

算法：拆边网络流 O(n^2*m)

直接套上下界网络流的算法。新建源汇s,t。对于每条边(u,v),下界是b,上界是c,则新图中c'(u,v)=c(u,v)-b(u,v) , c'(s,v)=b(u,v) , c'(u,t)=b(u,v)。然后从s做最大流。若从s发出的边都是满载的，则可行流存在。

ZOJ2015 / SGU195 New Year Bonus Grant

题意：在树中找最大匹配

算法：TreeDP 或 Greedy O(n)

TreeDP没什么说的。Greedy就是从叶子开始往上走直接贪，能匹配就匹配

ZOJ2016 / SGU196 Matrix Multiplication

题意：给n个点m条边的无向图，给出一个n*m矩阵A[i,j]=1当且仅当第j条边的一个端点是i，求AT*A的所有元素的和 (AT[i,j]=A[j,i])

算法: 数学　O(n)

令B=AT*A,则B[i,j]=sigma(AT[i,k]*A[k,j])=sigma(A[k,i]*A[k,j]) ,1<=k<=n

sigma(B[i,j])

=sigma(sigma(sigma(A[k,i]*A[k,j] , 1<=k<=n) , 1<=j<=n),1<=i<=n)

=sigma(D[i]^2,1<=i<=n) ,即所有点度数的平方和

ZOJ2017 / SGU197 Nice Patterns Strike Back

题意：将n*m的矩阵染黑白两色，使不出现边长大于1的颜色都相同的正方形，有多少种方法

算法：DP+矩阵乘法　O(2^m*logn)

由于m<=5，很容易想到状态压缩DP用0..2^m-1表示状态，建一个邻接矩阵b[s1,s2]=1当s1能转移到s2，否则为0。然后转移方程为d[i,s2]=sigma(d[i-1,s1]+1,b[s1,s2]==1)=sigma(d[i-1,s1]*b[s1,s2])。所以d[n]=d[1]*b^(n-1)，然后用快速幂算b^(n-1)，结果就出来了

ZOJ2018 / SGU198 Get Out!

题意：给一堆平面上的圆，询问某个圆是否可以在不与任何圆相交的情况下到达到任意远

算法：计算几何

待补充.....

ZOJ2019 / SGU199 Beautiful People

题意：有n个人，每人有两个属性ai,bi。当ai<aj && bi<bj时两个人i,j不会产生矛盾。找出尽量多的人，使这些人之间不会产生矛盾。

算法：LIS O(nlogn)

把所有人按ai<aj || ai==aj && bi>bj排序，然后求b的lis

ZOJ2020 / SGU200 Cracking RSA

题意：给出质因子是前t个质数的m个数，取其中一个子集，使集合所有元素的积是一个完全平方数。求这样的非空子集的个数

算法：高斯消元　异或方程组　O(t*m*m)

使子集所有元素的积是完全平方数的充要条件是每个质因子的个数是偶数。列t个方程组，每组m项a[i,j]*x[j]，a[i,j]是系数，表示第j个数的i质因子的个数的奇(1)偶(0)，x[j]表示第j个数选(0)还是不选(1)。方程右端全为0。然后高斯消元，若变元个数是k的话，结果就是2^k-1

有问题请留言或给我发Email

Ulm Local Contest 1996-2007 总结

2009-01-17T17:16:00.006+08:00

题大部分都比较简单，或比较无聊

POJ1780 Code

题意：求一个长度为10^n+n-1的数字串，包含0..10^n-1的每个数的串(不足n位的前面补0)仅一次

算法：Euler Circuit O(10^n)

有点自动机的味道，一个n-1位的数字串作为一个状态的话，状态转移就是末尾加上0..9中的一个数，去掉第一位。每个点的状态转移对应一个数的串，要使每个串出现且仅出现一次，想到欧拉回路。10^n-1个点，每个点连10条边，以(n-1)个0为起点做欧拉回路(注意:会堆栈溢出，欧拉路要用非递归)

POJ2566 Bound Found

题意：已知一列数和一个数t，求这列数的一个子序列(连续)，是这个子序列的和的绝对值最接近t

算法：O(nlogn+n)

求出来所有的前缀和sum[i]，把sum从小到大排序，然后两个指针扫一遍就ok(因为abs(sum[i]-sum[j])==abs(sum[j]-sum[i])，所以...)

POJ2941 Homogeneous Squares

题意：n*n的方格中选n个格子，使这n个两两独立(独立是不同行不同列x1!=x2 && y1!=y2)。每个格子中有一个权值，若所有选法的格子之和都相等，那么这个矩阵就是homogeneous,否则不是，判断一个给出的矩阵是否homogeneous

算法：O(n^2)

原矩阵是homogeneous等价于每个2*2的子矩阵是homogeneous。因为把一种选法任意改变两个数就能得到另一种选法，而和的改变只是那两个格子，这两个格子必然是行列对换的(要不然就和其他的不“独立”了)，所以就是任何能组成正方形的四个点的对角线和相等的话就ok

POJ3370 Halloween treats

题意：已知n个数，从中选出若干个使之和是c(c小于n)的倍数

算法：抽屉原理　O(n)

一个不起眼的条件c小于n是这题的关键。设sum[i]为前缀和，由于c小于n，所以sum[1],sum[2],sum[3]...sum[n] 分别mod c的余数肯定至少有两个相同，比如sum[i]%c==sum[j]%c，那么(sum[j]-sum[i])%c==0，i+1..j这个序列一定符合条件。

有问题请留言或给我发Email

原则

2008-09-12T13:06:00.000+08:00

反物质

Hello World!

2008-08-22T02:01:00.000+08:00

#include <iostream>
using namespace std;
int main() {
cout << "Hello,world!" << endl;
return 0;
}