edward_mj

[SPOJ pgcd]【容斥原理】【常数】

【地址】http://www.spoj.pl/problems/PGCD/

【题目大意】

10组数据，给定(m,n)，问gcd(i,j)=素数的对数(1<=i<=m,1<=j<=n) m,n<=10^7

【算法】

不妨设m

先筛出素数和miu函数。

然后暴力容斥。

for (int d=2;d<=m;d++) if (prime[d])

for (int j=1;j<=m/d;j++)

ans+=miu(j)*(m/d/j)*(n/d/j)

这样是 m lg m的

miu是容斥系数。

特别地miu[1]=1。

miu[i]=1 i为Square-Free-Number并且i有偶数个素因子

miu[i]=-1 i为Square-Free-Number并且i有奇数个素因子

miu[i]=0 other

这样会TLE。

那么看我们所求。

sigma{ miu[j]*( m/(d*j) )*n/( n/(d*j) ) } 其中d*j<=m && d为素数

尝试枚举d*j的值。令x=d*j，由于d为素数，令x=p1^k1 * p2^k2 * p3^k3 … 其中pi为素数。

那么现在看看会出什么结果。

1、

假如ki全为1。那么从里面拿出一个素数d，会剩下一个Square-Free-Number。

设x有t个素因子。

j含有的素因子个数必然为t-1。所以所有的j的miu值都一样。而取法有t种于是ans+= ( ((t-1)&1)?-1:1 ) * t * (m/x) * (n/x)

2、

假如ki有一个是2，其它全是1，那么只能拿出那个ki=2的，否则剩下的不是SFN，miu值=0，无须计算。

这样设拿走了那个ki=2的一个素因子以后，剩下t个素因子。那么显然 ans+=( (t&1)?-1:1 )*(m/x)*(n/x)

3、

其它的不可能拿走一个素数以后得到SFN了。于是miu值都=0，不必考虑。

于是。。。枚举x。然后按照上面的情况分别搞就行了。

实际上都是P[x]*(m/x)*(n/x)的形式。由于上面的分类是针对x这个数值的，所以可以通过筛选法把P[x]预处理出来。

然后for (int x=2;x<=m;x++) ans+=P[x]*(m/x)*(n/x)就行了。

但是这样还不够快。

注意到m/x和n/x都只有sqrt级别个结果。于是随着x的递增，(m/x)*(n/x)只有sqrt(m)+sqrt(n)级别个结果。

通过对P[]建立前缀和数组，可以迅速知道区间的P[]之和。那么对于(m/x)*(n/x)相同的部分，直接跳过一整段，

ans+=(S_P[r]-S_P[l-1])*(m/x)*(n/x) 其中(m/l) * (n/l) == (m/r) * (n/r) 。

【时间复杂度】

一开始的筛O(n)的

后面每个询问sqrt(n)的。

【其它】

出现了很诡异的事件- -，我用O(n)的筛，45S。

用O(n lg n)的筛，31S。

不明真相中。

【CODE】

#include

using namespace std;

const int N=(int)1e7;

int F[N+5];

int cnt_1[N+5];

int cnt_2[N+5];

int S[N+5];

void Get_Prime(){

S[2]=0;

for (int i=2;i<=N;i++){

if (cnt_1[i]==0){

F[i]=i;

cnt_1[i]=1;

//这个筛是n lg n的- -，但不知道为什么，居然比线性筛快。求指导。。。

for (int j=i+i,c=2;j<=N;j+=i,c++){

cnt_1[j]++;

if (c==i){

cnt_2[j]++;

if (cnt_2[j]==1 && j/i/i%i==0) cnt_2[j]++;

c=0;

}

for (int j=2,k=i+i;j<=F[i];j++,k+=i){

if (k>N) break;

F[k]=j;

cnt_2[k]=cnt_2[i]+(j==F[i]); //计算k有多少个i^2形式的因子

cnt_1[k]=cnt_1[i]+1; //计算k有多少个因子。

}

int t;

int &c1=cnt_1[i];

int &c2=cnt_2[i];

if (c2==0)

if (c1&1)

t=c1;

else

t=-c1;

else

if (c2==1) t=( (c1&1)?1:-1 );

else t=0;

S[i+1]=S[i]+t;

}

int main(){

Get_Prime();

int Tc,m,n,d1,d2,Next_1,Next_2,Next;

scanf("%d",&Tc);

while (Tc–){

scanf("%d%d",&m,&n);

if (m>n) swap(m,n);

long long ans=0;

for (int i=2;i<=m;){

d1=m/i;

d2=n/i;

Next_1=m/d1+1; //Next_1>i && m/Next_1>m/i

Next_2=n/d2+1; //they are the same

Next=Next_1

ans+=(long long)(S[Next]-S[i])*d1*d2;

i=Next;

}

printf("%lldn",ans);

}

[POI2007 Zap]容斥原理

【url】http://www.zybbs.org/JudgeOnline/problem.php?id=1101

【题目大意】没法大意了- -，直接原题吧。

【算法】

直接暴力容斥可以在O(min(a,b))时间复杂度内解决一个询问。

先a/=d,b/=d

答案为Sum(d[i]*(a/i)*(b/i))，2<=i<=a其中d[i]是容斥系数。

那么可知a/i只有sqrt(a)级别种结果。b/i也只有sqrt(b)级别种结果。

也就是说随着i的递增，a/i和b/i总的变化数是sqrt(a)+sqrt(b)级别的。

于是对于a/i和b/i相同的放一组。一共只会有sqrt(a)+sqrt(b)级别组。通过对d构建前缀和数组可以做到O(1)处理每一组。

然后就没了。

【其它】

作为AC的门徒、外加NOI2010囧人，此题不切说不过去- –

【CODE】

#include

const int N=50005;

int d[N];

int S[N];

bool prime[N];

void predo(){

memset(prime,true,sizeof(prime));

for (int i=2;i<=50000;i++) d[i]=1;

for (int i=2;i<=50000;i++)

if (prime[i]){

for (int j=i+i;j<=50000;j+=i){

prime[j]=false;

if (j/i%i==0) d[j]=0;

d[j]=-d[j];

}

d[i]=-1;

}

S[1]=0;

for (int i=2;i<=50000;i++) S[i]=S[i-1]+d[i];

}

void swap(int &x,int &y){

int t=x;

x=y;

y=t;

}

int min(int x,int y){return x

int Get_Next(int a,int b){ // let ret=a/b this function get the smallest number x satisfy a/x!=ret && x>b

return a/(a/b)+1;

}

int main(){

predo();

int Tc;

scanf("%d",&Tc);

while (Tc–){

int m,n,dd;

scanf("%d%d%d",&m,&n,&dd);

m/=dd;

n/=dd;

long long ans=(long long)m*n;

if (m>n) swap(m,n);

for (int i=2;i<=m;){

int Next=min(Get_Next(m,i),Get_Next(n,i));

long long tmp=(long long)(m/i)*(n/i);

ans+=(S[Next-1]-S[i-1])*tmp;

i=Next;

}

printf("%lldn",ans);

}

Codeforces Beta Round #71 （A～D）

直接模拟即可。10^6

【题目大意】

m*n的方格(m,n<=4*10^4)，有一些格子坏掉了(数目<=10^3)。然后以

for (int i=1;i<=m;i++)

for (int j=1;j<=n;j++)

的顺序填好的格子，依次填上Carrots Kiwis Grapes.

然后有<=10^3个询问，问第i行第j列的格子是什么。waste表示坏格子。

【算法】

(i,j)->(i-1)*n+j

然后根据排序二分。得出<=自己的坏掉的格子的数目。

【题目大意】

给定一个10^5的串，然后给出10个小串，他们的长度都<=10。然后问你大串满足不包含小串的最长连续子串是多少。

【算法】

令C[i]表示以大串第i位为结尾和小串匹配时的最短小串长度。如果没有小串和大串在以i为结尾的地方匹配，那么C[i]=oo。

然后就i递增地扫描，然后记now为当前以i为结尾的最长匹配长度。如果now>=C[i],那么now=C[i]-1。记录过程中最大的now与位置即可。

【时间复杂度】

10^7 —暴力

10^6 —KMP

10^5 —自动机

【题目大意】

1..n个格子，有黑白，一开始全白。其中有k个不相同的key_blocks。然后有m种操作。每种操作为L[i]，表示可以选择一段长度为L[i]连续格子翻转。

问最少多少步使得所有key_blocks变黑，其他格子全白。

【算法】

看了解题报告、

这个模型的转换确实挺巧妙的。

令b[i]=a[i]^a[i-1]。其中a[i]就是原格子的黑白状态。那么b[i]=0表示a[i]==a[i-1]。否则不等。

添加a[0]=0。那么用b可以完整表示出a。(要添加a[n+1]=0,b[n+1]=a[n]^a[n+1]，key_blocks如果前后没有，就要1变2了)

然后翻转连续的一段，就会只更改b的两个值x和x+L[i]，1<=x<=n+1。这样模型就很适合反映情况了。

更改两个b的值表示两个点有边，那么问题变成我们选择一些边，使得key_blocks对应的点度为奇数，其它点度为偶数。

因此答案必然可以分割为若干条简单路径，每条简单路径的起始点和结束点都是key_blocks，而且每个key_blocks会被覆盖1次且仅1次。于是可以bfs算出各个key_blocks间的最短距离。然后SCDP取得最优解。

可见把模型转化成合适的形式是很重要的。

【时间复杂度】

mnk + 2^(2k) * k

这场之后rating达到新高1922。= =，希望接下来一场多人点的把我带红。

这两天缺席了一场TC，一场CF、据说这两场都很好涨rating？555555555555555

[SWJTU1705 GreatAccepted]【贪心】

【Link】http://acm.swjtu.edu.cn/JudgeOnline/showproblem?problem_id=1705

【题目大意】

n个数，你每次可以取<=3个数出来将他们都-1。然后放回去。问将所有数变为0至少需要多少次操作。

输出的两个数中第二个数是Sum

【算法】

lcc大神一下就秒杀了。我完全YY不出来。

first of all，每次取最大的3个出来减这种贪心是肯定没问题的。

但是数目太多了。

考虑每次都只能将一个数-1。

所以答案至少是最大那个数。

设m1是最大那个数，m2是次大那个数。

那么看看m1什么时候会将答案卡住。

很容易想到就是每次m1都减，减到最后的情况。然后看剩下的2个名额怎么去减。

用这两个名额，

要么是m2把这个名额卡住了，

要么减到最后剩下一个1，

要么是除了m1全部减为0。

(原因可以模拟一开始的贪心看看)

后面两种就判一下是不是Sum-m1<=m1*2就可以了。

第一种的卡住，只能发生在m2一直减，减到最后的情况，所以就是Sum-m1-m2<=m2。

答案被卡住的情况解决了，剩下的就是没被卡住的情况。

这些情况的答案都是Sum/3向上取整。

还是参见一开始的贪心，现在假设n>3(n<=3必然是答案是m1)每次我们都选最大的3个减。最后因为不会再被m1卡住了。设这些数中最小值为min，容易必然能够转到下面3种情况中的一种。

1、所有数都=min

2、2个数=min，其余数=min+1

3、1个数=min，其余数=min+1

转化为这个以后、、不断的3个3个减。。。很容易知道最后要么刚好减完，要么剩一个1，要么剩2个1。因为都是3个3个减，所以就和它% 3的结果有关系。。。于是就是Sum/3向上取整了= =

【其它】

Orz lcc大神

【CODE】

#include

using namespace std;

int main(){

int Tc,n;

int a[1005];

scanf("%d",&Tc);

for (int k=1;k<=Tc;k++){

scanf("%d",&n);

for (int i=0;i

scanf("%d",&a[i]);

sort(a,a+n);

int Sum=0,ans;

for (int i=0;i

if (n<=3) ans=a[n-1];

else

if (Sum-a[n-1]-a[n-2]<=a[n-2])

ans=a[n-1];

else

if ( Sum-a[n-1]<=a[n-1]*2 )

ans=a[n-1];

else ans=(Sum+2)/3;

printf("Case #%d: ",k);

printf("%d %dn",ans,Sum);

}

[ZOJ1030 Farmland]【狗狗40题】【计算几何】【绕圈圈】【判点是否在多边形内】

【题目大意】

给定一个简单平面无向图。n<=200。每个点给出坐标

问图中包含边数为k的圈有多少个。

这些圈要满足：

1、面积>0

2、不能有其它的点或者边在圈内

【算法分析】

和大妈题#3的area(ZOJ2361)差不多。

先枚举起始边，然后对于路径中最后的两个点，x,z，构成向量x->z，然后再在与x相连的点集里找一个点y，满足x->z逆时针绕到x->y所夹的角最大。

然后就这样绕，注意每条边x->y只能走一次。因为从x->y绕多一遍只能绕出之前绕过的圈。方向不同(y->x)分开看待。

当我们找到一开始那个点时，实际就找到了圈了。

但是我们可能顺时针算了这个圈一次，逆时针又算了一次。而实际上，如果走逆时针走重复的话，必然和本次的起始点是一样的。

于是每次加答案时只需要判判把整条路径逆过来有没有出现过就行了。(我直接set < vector

然后再枚举看圈圈内有没有其它的点在。

这个要用到判点是否在多边形内。

基本上就这样。

【其它】

好像无论多暴力都0MS。

2Y。一开始没有注意到可能有杂点可能在多边形

T_T，好长好长

【CODE】

#include

using namespace std;

const int N=256;

const double eps=1e-7;

const double INF=1e50;

const double pi=acos(-1);

int sign(double x){

if (x<-eps) return -1;

if (x> eps) return 1;

return 0;

}

struct TPoint {double x,y;};

TPoint operator – (TPoint A,TPoint B){

TPoint ret;

ret.x=A.x-B.x;

ret.y=A.y-B.y;

return ret;

}

double operator ^ (TPoint A,TPoint B){

return A.x*B.y-A.y*B.x;

}

double operator * (TPoint A,TPoint B){

return A.x*B.x+A.y*B.y;

}

double Length(TPoint v){

return sqrt(v.x*v.x+v.y*v.y);

}

double Get_Angle(TPoint v1,TPoint v2){

return acos(v1*v2/Length(v1)/Length(v2));

}

bool On_Seg(TPoint p,TPoint A,TPoint B){

if (sign((p-A)^(B-A))!=0) return false;

if (min(A.x,B.x)<=p.x+eps && p.x<=max(A.x,B.x)+eps

&& min(A.y,B.y)<=p.y+eps && p.y<=max(A.y,B.y)+eps)

return true;

return false;

}

bool Seg_Cross(TPoint p1,TPoint p2,TPoint p3,TPoint p4){

return

sign( ( (p2-p1) ^ (p3-p1) ) * ( (p2-p1) ^ (p4-p1) ) ) <= 0 &&

sign( ( (p3-p4) ^ (p1-p4) ) * ( (p3-p4) ^ (p2-p4) ) ) <= 0;

}

set < pair

set < vector

vector

TPoint P[N];

int Tc,n;

int Need;

int Ans;

int v[N];

bool Inside(TPoint p){

int cnt=0;

TPoint oth;

oth.x=INF;

oth.y=p.y;

for (int i=0;i

if ( On_Seg(p,P[Path[i]],P[Path[i+1]]) ) return false;

for (int i=0;i

TPoint A=P[Path[i]];

TPoint B=P[Path[i+1]];

if (A.y

if (sign(A.y-B.y)==0) continue;

if (sign(p.y-A.y)==0) continue;

if (Seg_Cross(p,oth,A,B))

cnt++;

}

return cnt&1;

}

int check(){

if (Path.size()<4) return 0;

T_path.clear();

for (int i=Path.size()-1;i>=0;i–)

T_path.push_back(Path[i]);

if (Path_Hash.count(T_path)) return 0;

for (int i=1;i<=n;i++) v[i]=0;

for (int i=0;i

v[Path[i]]=1;

for (int i=1;i<=n;i++)

if (!v[i])

if (Inside(P[i])) return 0;

return 1;

}

void dfs(int st,int z,int x,int Len){

if (Len>Need) return;

if (x==st){

if (Len==Need && check()){

Ans++;

Path_Hash.insert(Path);

}

return;

}

int best=-1;

double best_angle=-INF;

for (int i=0;i

int y=G[x][i];

int s=sign( (P[x]-P[z])^(P[y]-P[z]) );

double angle=0;

if (!( s==0 && sign( (P[x]-P[z])*(P[y]-P[x]) )<0 )){

if (s < 0){

angle=Get_Angle(P[z]-P[x],P[y]-P[x]);

}

if (s > 0){

angle=2*pi-Get_Angle(P[z]-P[x],P[y]-P[x]);

}

if (s == 0){

angle=pi;

}

if (angle>best_angle){

best_angle=angle;

best=y;

}

if (best==-1) return;

int y=best;

if (Hash.count(make_pair(x,y))) return;

Hash.insert(make_pair(x,y));

Path.push_back(y);

dfs(st,x,y,Len+1);

}

void solve(){

Hash.clear();

Path_Hash.clear();

Ans=0;

int i,j;

for (i=1;i<=n;i++){

for (j=0;j

int x=i;

int y=G[i][j];

if (Hash.count(make_pair(x,y))) continue;

Hash.insert(make_pair(x,y));

Path.clear();

Path.push_back(x);

Path.push_back(y);

dfs(x,x,y,1);

}

int main(){

scanf("%d",&Tc);

while (Tc–){

scanf("%d",&n);

for (int i=0;i<=n;i++) G[i].clear();

for (int i=0;i

int x,num;

scanf("%d",&x);

scanf("%lf%lf%d",&P[x].x,&P[x].y,&num);

for (int j=0;j

int y;

scanf("%d",&y);

G[x].push_back(y);

}

scanf("%d",&Need);

solve();

printf("%dn",Ans);

}