题目大意

阅读更多……

题目大意

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

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

阅读更多……

【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;
}

题目大意

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

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

问是否有这样的方案

阅读更多……

题目大意

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

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

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

阅读更多……

题目大意

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

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

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

阅读更多……

题目大意

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

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

阅读更多……

题目大意

YT市是一个规划良好的城市，城市被东西向和南北向的主干道划分为$n\times n$个区域。YT城市中包括$(n+1)\times (n+1)$个交叉路口和$2\times n\times(n+1)$条双向道路，每条双向 道路连接主干道上两个相邻的交叉路口。

小Z作为市长统计到了每条道路的人流量$w_i$，然而每个点都有一定的海拔$h_i(0\leqslant h_i\leqslant 1)$，那么经过一条道路需要耗费的体力值为$w_i\times max(0,h_{终点}-h_{起点})$

已知起点为右上角，海拔为0，终点为左下角，海拔为1，求最少耗费多少体力值。

顺便给出样例的图

阅读更多……