UOJ Logo zgjkt的博客

博客

【hoj2634】How to earn more

2015-09-11 13:01:11 By zgjkt

题目大意

有$m$个项目和$n$个员工

做项目$i$可以获得$A_i$元,但是必须雇用若干个指定的员工。雇用员工$j$需要花费$B_j$元,且一旦雇用,员工$j$可以参加多个项目的开发

问经过合理的项目取舍,最多能挣多少钱

阅读更多……

【bzoj1179】Atm

2015-09-09 13:43:43 By zgjkt

【poj2762】Going from u to v or from v to u?

2015-09-06 13:46:16 By zgjkt

题目大意

给一个有n个点m条边的有向图,对于图中任意两个点u,v,如果从u能到v,或者从v能到u,则这对顶点是可行的

如果图中任意一对顶点都是可行的,可以输出Yes,否则输出No

阅读更多……

莫比乌斯函数的一些证明

2015-06-19 13:43:46 By zgjkt

【bzoj1101】Zap【bzoj2301】Problem b

2015-06-14 22:16:19 By zgjkt

【bzoj1101】Zap

题目大意

对于给出的n个询问,每次求有多少个数对$(x,y)$

满足$1\leqslant x\leqslant a,1\leqslant y\leqslant b$,且$gcd(x,y)=c$

数据范围

$1\leqslant n\leqslant 50000,1\leqslant c\leqslant a,b\leqslant 50000$


题解

原题是求$\sum^{a}_{i=1}\sum^{b}_{j=1}1{(gcd(i,j)=c)}$

设$A=\left\lfloor\frac{a}{c}\right\rfloor,B=\left\lfloor\frac{b}{c}\right\rfloor$

则原式=$\sum^{A}_{i=1}\sum^{B}_{j=1}1{(gcd(i,j)=1)}$

根据莫比乌斯函数的性质,$\sum_{c|n}\mu(c)=1\{n=1\}0\{n\neq 1\}$

因此原式=$\sum^{A}_{i=1}\sum^{B}_{j=1}\sum_{c|gcd(i,j)}\mu(c)$

容易发现,$\mu(c)$加了的次数是$\sum^{A}_{i=1}\sum^{B}_{j=1}1{(c|i,c|j)}$

所以原式可以再次化简为$\sum\mu(c)\left\lfloor\frac{A}{c}\right\rfloor\left\lfloor\frac{B}{c}\right\rfloor$

由于$\left\lfloor\frac{A}{c}\right\rfloor$是$\sqrt{A}$数量级的,所以分段处理



【bzoj2301】Problem b

题目大意

对于给出的$n$个询问,每次求有多少个数对$(x,y)$

满足$a\leqslant x\leqslant b,c\leqslant y\leqslant d$,且$gcd(x,y)=k$

数据范围

$1\leqslant n\leqslant 50000,1\leqslant a\leqslant b\leqslant 50000,1\leqslant c\leqslant d\leqslant 50000,1\leqslant k\leqslant 50000$


题解

这道题其实和上题一样,只是要利用容斥原理处理信息


程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define inf 0x7fffffff
using namespace std;

int sum[50050],mu[50050],prime[50050],flag[50050];
int tot,ans,a,b,c,d,k,t;

inline void getmu(){
    mu[1]=1;
    For(i,2,50000){
        if (!flag[i]) {prime[++tot]=i;mu[i]=-1;}
        For(j,1,tot){
            if (i*prime[j]>50000) break;
            flag[i*prime[j]]=1;
            if (i%prime[j]==0) {mu[i*prime[j]]=0;break;}
            else mu[i*prime[j]]=-mu[i];
        }
    }
}
inline int count(int x,int y){
    if (x>y) swap(x,y);
    int result=0,pos;
    for(int i=1;i<=x;i=pos+1){
        pos=min(x/(x/i),y/(y/i));
        result+=(sum[pos]-sum[i-1])*(x/i)*(y/i);
    }
    return result;
}
int main(){
    getmu();
    For(i,1,50000) sum[i]=sum[i-1]+mu[i];
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        a--;c--;a/=k;b/=k;c/=k;d/=k;
        ans=count(a,c)+count(b,d)-count(a,d)-count(b,c);
        printf("%d\n",ans);
    }
    return 0;
}

【bzoj1823】满汉全席

2015-06-05 14:03:08 By zgjkt

题目大意

有$n$种材料,$m$个评委,每种材料有两种不同的做法只能选择一种

然而每个评委有两个要求,做出来的菜必须满足每一个评委至少一个要求

问是否有这样的方案

阅读更多……

【bzoj1059】矩阵游戏

2015-06-05 13:37:12 By zgjkt

题目大意

给出一个$n\times n$的矩阵,矩阵节点可以是白色或是黑色

现在有两种操作,一种是交换任意两行,一种是交换任意两列

求是否有可能由原图通过操作得到一个左上角与右下角的连线上的点均为黑色的图

阅读更多……

【poj3683】Priest John's Busiest Day

2015-06-04 14:11:15 By zgjkt

题目大意

有$n$对新人要举行仪式,每对都有两个时间段可以选择

问:输出是否可以所有新人的仪式时间不重叠

如果可以满足楼上的条件,还需输出方案

阅读更多……

【bzoj1878】HH的项链

2015-06-04 13:53:12 By zgjkt

题目大意

给出$n$个数的数列,提出$m$次询问,每次询问区间$[l,r]$中有多少种数字

比如在数列$“1 2 3 4 3 5”$,在区间$[3,5]$中有两种数字$“3,4”$

阅读更多……

欧拉函数的一些证明

2015-05-21 14:04:56 By zgjkt
共 63 篇博客