3
22
2016
0

[BZOJ3876] [Ahoi2014]支线剧情

BZOJ 100AC啦!

我选择了这道题。

这题是一个裸的下界最小费用流

对于每条边(sa,sb)费用sc

可以连接S->sb,费用sc容量1表示至少走一次

sa->sb,费用sc,容量INF表示可以走多次

对于每个点i

可以连接i->T费用0容量nk表示可以从这里离开(此时已经看完了全部剧情)

i->1费用0容量INF表示可以在i号点退出游戏重新开始一局新游戏

看不懂请看代码

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

int n,en,S,T,link[2005],h[2005],D[2005],flag[2005];

struct Edge{
int b,c,f,back,next;
}e[1000005];

void AddEdge(int sa,int sb,int sc,int sd){
e[++en].b=sb;
e[en].f=sc;
e[en].c=sd;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].c=-sd;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}

int SPFA(){
queue<int> Q;
memset(D,127,sizeof(D));
Q.push(S);
D[S]=0;
flag[S]=1;
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	flag[u]=0;
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		if(e[i].f && D[v]>D[u]+e[i].c){
			D[v]=D[u]+e[i].c;
			link[v]=i;
			if(!flag[v]){
				flag[v]=1;
				Q.push(v);
			}
		}
	}
}
return D[T]<2000000000;
}

int Cost(){
int Tow=link[T],flow=2100000000,cost=0;
while(Tow!=link[S]){
	flow=min(flow,e[Tow].f);
	Tow=link[e[e[Tow].back].b];
}
Tow=link[T];
while(Tow!=link[S]){
    e[Tow].f-=flow;
    e[e[Tow].back].f+=flow;
    cost+=flow*e[Tow].c;
    Tow=link[e[e[Tow].back].b];
}
return cost;
}

int Flow(){
int ans=0;
while(SPFA())ans+=Cost();
return ans;
}

int main(){
freopen("3876.in","r",stdin);
freopen("3876.out","w",stdout);
scanf("%d",&n);
S=n+1;T=n+2;
for(int i=1;i<=n;i++){
	int nk;
	scanf("%d",&nk);
	for(int j=1;j<=nk;j++){
		int sa,sb;
		scanf("%d %d",&sa,&sb);
		AddEdge(S,sa,1,sb);
		AddEdge(i,sa,2100000000,sb);
	}
	AddEdge(i,T,nk,0);
	if(i!=1)AddEdge(i,1,2100000000,0);
}
printf("%d\n",Flow());
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
21
2016
0

[BZOJ2820] YY的GCD

第二道莫比乌斯反演!

这题和HAOI2011的Problem b很像,但是改成了质数……

懒得写题解了:传送门

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int mu[10000005],g[10000005],T,n,m,pri[1000005],cnt,tab[10000005];

void Pre(int n){
mu[1]=1;
for(int i=2;i<=n;i++){
	if(!tab[i]){g[i]=1;mu[i]=-1;pri[++cnt]=i;}
	for(int j=1;j<=cnt && pri[j]*i<=n;j++){
		tab[i*pri[j]]=1;
		if(i%pri[j]){mu[i*pri[j]]=-mu[i];g[i*pri[j]]=mu[i]-g[i];}
		else {mu[i*pri[j]]=0;g[i*pri[j]]=mu[i];break;}
	}
}
for(int i=1;i<=n;i++)tab[i]=tab[i-1]+g[i];
}

long long Solve(long long n,long long m){
if(n>m)swap(n,m);
long long ans=0;
for(int i=1,last;i<=n;i=last+1){
	last=min(n/(n/i),m/(m/i));
	ans+=(n/i)*(m/i)*(tab[last]-tab[i-1]);
}
return ans;
}

int main(){
freopen("2820.in","r",stdin);
freopen("2820.out","w",stdout);
Pre(10000000);
scanf("%d",&T);
while(T--){
	scanf("%d %d",&n,&m);
	printf("%lld\n",Solve(n,m));
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
21
2016
0

[UOJ35] 后缀排序

SA模版,然后我发现我写的SA其实有问题……

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

char s[500005];
int n,rank[500005],rank2[500005],height[500005],sa[500005],rmq[500005][20],ws[500005],wv[500005],er[20],log2[500005];

int cmp(int *r,int a,int b,int l){return (r[a]==r[b])&(r[a+l]==r[b+l]);}

void GetSA(char *r,int *sa,int n,int m){
int i,j,p,*x=rank,*y=rank2,*t;
for(i=0;i<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[x[i]=r[i]]++;
for(i=1;i<m;i++)ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--){sa[--ws[x[i]]]=i;}
for(j=p=1;p<n;j*=2,m=p){
	for(p=0,i=n-j;i<n;i++)y[p++]=i;
	for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
	for(i=0;i<m;i++)ws[i]=0;
	for(i=0;i<n;i++)ws[wv[i]=x[y[i]]]++;
	for(i=1;i<m;i++)ws[i]+=ws[i-1];
	for(i=n-1;i>=0;i--)sa[--ws[wv[i]]]=y[i];
	for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}

void CalHeight(char *r,int *sa,int n){
int i,j,k=0;
for(i=1;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k)for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}

void RMQ(){
int i,j;
er[0]=1;
for(i=1;i<20;i++)er[i]=er[i-1]<<1;
log2[0]=-1;
for(i=1;i<=n;i++)log2[i]=(i&(i-1))?log2[i-1]:log2[i-1]+1;
for(i=1;i<=n;i++)rmq[i][0]=height[i];
for(j=1;j<20;j++)for(i=1;i+er[j-1]-1<=n;i++)rmq[i][j]=min(rmq[i][j-1],rmq[i+er[j-1]][j-1]);
}

int LCP(int a,int b){
int x=rank[a],y=rank[b],t;
if(x>y)t=x,x=y,y=t;
x++;
int k=log2[y-x+1];
return min(rmq[x][k],rmq[y-er[k]+1][k]);
}

int main(){
scanf("%s",s);
n=strlen(s);
s[n]=0;
GetSA(s,sa,n+1,128);
CalHeight(s,sa,n);
//RMQ();
for(int i=1;i<=n;i++)printf("%d ",sa[i]+1);
putchar('\n');
for(int i=2;i<=n;i++)printf("%d ",height[i]);
return 0;
}
Category: 其他OJ | Tags: OI uoj
3
20
2016
0

[BZOJ1031] [JSOI2007]字符加密Cipher

老年颓废选手表示不能再颓了,毕竟2天没做题了虽然还是学习了一下后缀数组

第一道后缀数组!

裸题,因为后缀本来就排好序了,然后直接输出就行了

需要把串复制一遍

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

char s[200005];
int log2[200005],rmq[200005][20],n,sa[200005],rank[200005],rank2[200005],ws[200005],wv[200005],tot;

int cmp(int *r,int a,int b,int len){return (r[a]==r[b])&(r[a+len]==r[b+len]);}

void GetSA(char *r,int *sa,int n,int m){
int i,j,p,*x=rank,*y=rank2,*t;
for(i=0;i<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[x[i]=r[i]]++;
for(i=1;i<m;i++)ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--)sa[--ws[x[i]]]=i;
for(j=p=1;p<n;j*=2,m=p){
	for(p=0,i=n-j;i<n;i++)y[p++]=i;
	for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
	for(i=0;i<m;i++)ws[i]=0;
	for(i=0;i<n;i++)ws[wv[i]=x[y[i]]]++;
	for(i=1;i<m;i++)ws[i]+=ws[i-1];
	for(i=n-1;i>=0;i--)sa[--ws[wv[i]]]=y[i];
	for(t=x,x=y,y=t,x[sa[0]]=0,i=p=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}

int main(){
freopen("1031.in","r",stdin);
freopen("1031.out","w",stdout);
scanf("%s",s);
n=strlen(s);
for(int i=n;i<2*n;i++)s[i]=s[i-n];
n*=2;
s[n]=0;
GetSA(s,sa,n+1,128);
for(int i=1;i<=n && tot<n/2;i++)if(sa[i]<n/2)printf("%c",s[sa[i]+n/2-1]),tot++;
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
17
2016
0

AHOI2016停课笔记

3.17

先开一坑……

计划3.27正式开始停课专心竞赛。

这到时候就用来记录一下每天被虐的经历吧。

毕竟AH不是强省,这个时候停课也够了吧。

今年我进省队希望=0

(NOIP作弊的都去死吧!你们自己作弊就算了,还让AH丢了一个名额)

预计省队名单,到时候看看估算的对不对

wzf(Newnode) lzz(C_Sunshine) cjy(YJC) wlp(JOHNKRAM) lyf(shpgy)(女队) wyx(Thaddeus) xdm(flea)

其实wyx大爷很强的……但是因为坑·卡名额估计要买C类了……

高一其他大爷也存在卡进省队的可能……但是估计希望不太大。。

我这个sb就更不用说了,进省队期望=0

NOI2017再见了。。。反正已经弃疗所以3.27再停课咯

(当然wyx大爷和shpgy两位高一之神已经停课了)

----------------------------------------------------------

3.23

大爷们去ZJOI2016了,我还在wh月考……

已经考挂了,智商不够只能拼OI了……

wyx大爷当然不用月考啦

----------------------------------------------------------

3.26

月考完挂

明天就要集训了呢。。alpq654321来讲dp。。好激动啊

----------------------------------------------------------

Day1

今天是alpq654321讲DP和BZOJ选讲。。十分资瓷啊

下午xdm成为最佳口胡选手。

“这位橙衣小哥,你来回答一下这个问题”

今天见到了bzoj上神乎其神的神犇——yyhslyz本人

当然我也在下面口胡啊……不过我当然不会作死上去讲的

----------------------------------------------------------

Day2

今天考试。

先开T1,感觉是一道数据结构好题啊,前两天看的点分治好像有点像

T2感觉是一道DP好题啊……应该和昨天上课有些关系吧

T3感觉是一道打表好题

不管了先码暴力。

T1码到9:30

T2码到10:40

T3写了一个打表程序开着跑(此时11:30)

在11:30前想了一下T1的正解,似乎树链剖分能乱搞不少分?(此时11:40)

然后开始码码码。

然后就没码完。

最后交了两暴力一个表

然后GG喽

lyz:今天感觉三题中两题要被卡常

太神了居然会正解

slx:我第一题按位树剖黑白点的

好像大家都会T1。。

中午吔饭归来,发现我好像是rank27?不过好多同分啊……还有几个同分在我上面……

wyx大爷A掉了T1太神了

gqy100 lyz140 rky120

仔细一看我T1暴力写挂了然后爆零

果然人太弱

cyd和slx没考好只有70。。默哀

下午讲题,T1是点分治好题

lzz和wyx大爷T1就用lyz乱搞做法卡常数卡过了卡常小法坏

T2果然神奇DP

T3是一个最短路+DP

感觉要好好学习一下点分治了

orz wzf 300虐场

lzz 260 故意取模不AK

wyx 160同样虐场

都好神啊orzorz

今晚的订正工作似乎比较艰辛……毕竟要学习点分治啊……

----------------------------------------------------------

Day3

今天是lh大爷讲课,被xdm大D一通

以后要换个位子了

下午的题目好难啊……我只会口胡暴力乱搞

明天考试不会考这些东西吧……(立flag)

----------------------------------------------------------

Day4

lh大爷的题目

滚粗爆炸了(0+10+0)

T1T3暴力写残

T2其实我不会凸包直接输出n有10分

高一垫底

----------------------------------------------------------

Day5

接着爆炸

看到题目就浑身不想写

最讨厌找规律了

然后t1写了暴力,但是好像忘掉了逆元怎么求?

t2打表输出

t3写了一个鬼畜贪心直接爆0(你不是在Noi Openjudge上做过这个DP吗)

然后0+10+0滚粗了

lyz T2搞了50太神了%%%

cyd T3直接AC也是很神%%%

其他人好像都考的比我好。。。

----------------------------------------------------------

Day6

wzf讲课,极其资瓷!

基本一揽子解决了数论。(但是现在又忘掉了)

----------------------------------------------------------

Day7

nxy讲课

上午可以接受,但下午太快了吧

感觉很神。。。

----------------------------------------------------------

Day8

nxy考试

15+0+30滚粗

T3居然是仙人掌

T1 T2都是找规律/乱搞

蒟蒻表示乱搞能力太差不敢做

----------------------------------------------------------

Day9-Day12

天天爆炸,上课梦游

太颓废了

(其实是懒得写了。。)

Category: 随笔 | Tags: 随笔
3
16
2016
0

[BZOJ2440] [中山市选2011]完全平方数

这题我居然挂了6次……简直是耻辱啊!

dead*4:二分上界打错

dead*1:二分判断条件打错

没救了……

好了,现在说一下题解

首先我们利用二分将其转化为判定[1,x]有多少个数不是完全平方数的正整数倍

------------------------以下为懒癌发作的Lvat_s复制的PoPoQQQ的题解

然后利用容斥原理,

x以内的无平方因子数
=0个质数乘积的平方的倍数的数的数量(1的倍数)
-每个质数的平方的倍数的数的数量(9的倍数,25的倍数,...)
+每2个质数乘积的平方的倍数的数的数量(36的倍数,100的倍数,...)-...
 
容易发现每个乘积a前面的符号恰好是mu(a)
x以内i^2的倍数有[x/i^2]个,故有
这题和莫比乌斯反演没关系,算是莫比乌斯函数的一个应用吧。。。
-------------------------------------------------------------
详情请看代码
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

long long T,k,tab[1000005],prime[1000005],mu[1000005],cnt;

void Prepare(long long Num){
mu[1]=1;
for(long long i=2;i<=Num;i++){
	if(!tab[i]){
		prime[++cnt]=i;
		mu[i]=-1;
	}
	for(long long j=1;j<=cnt && i*prime[j]<=Num;j++){
		tab[i*prime[j]]=1;
		if(i%prime[j])mu[i*prime[j]]=-mu[i];
		else {mu[i*prime[j]]=0;break;}
	}
}
}

long long Test(long long x){
long long sq=(int)sqrt(x),ans=0;
for(long long i=1;i<=sq;i++){
	ans+=mu[i]*(x/(i*i));
}
return ans;
}

long long Solve(long long k){
long long l=1ll,r=10000000000ll,ans=210000000000000ll;
while(l<=r){
	long long mid=l+r>>1,tmp=Test(mid);
	if(tmp<k){l=mid+1;}
	else {ans=mid;r=mid-1;}
}
return ans;
}

int main(){
freopen("2440.in","r",stdin);
freopen("2440.out","w",stdout);
scanf("%lld",&T);
Prepare(1000000);
while(T--){
	scanf("%lld",&k);
	printf("%lld\n",Solve(k));
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
14
2016
0

[BZOJ4408] [Fjoi 2016]神秘数

这是今年的福建省选原题……按说不是很难但我却卡了很长时间……

我的写法十分诡异难以调试……以后得换一种写法了

题解直接抄一下懒得写了

------------------------------

这个模型还是比较常见的。对于给定序列,我们要求的是最小的x,使所有<=x的数的和比x小。
设不同权值个数为t,我们用可持久化建出t棵线段树,每棵线段树均以下标为关键字,以支持查询小于等于某一权值的数在给定区间的和为多少。
那么在区间[L, R]中,假设答案为x0。我们可在线段树中查询[L, R]区间内所有不超过x0的数的和S。假如S小于x0,x0就是答案;否则答案一定至少为S + 1。迭代即可。
复杂度O(nlogn + kmlogn),k为迭代次数,不超过45(最坏情况由斐波那契数列卡到)

------------------------------

我真的是严格按照这个题解写的!但是其他人的写法都和题解不一样……所以我很诧异……UPD:其实是一样的!只是细节有点区别!我真是太弱了!

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

int n,siz,a[100005],b[100005],root[100005],bn,m;
vector<int> V[100005];

struct SegTree{
int nl,nr,l,r,sum,cre;
}tree[4000005];

void Add(int &rt,int lastrt,int l,int r,int pos,int val,int Rev){
if(Rev!=tree[rt].cre){rt=++siz;tree[rt].nl=tree[lastrt].nl;tree[rt].nr=tree[lastrt].nr;tree[rt].l=l;tree[rt].r=r;tree[rt].cre=Rev;}
if(l==r){tree[rt].sum+=val;return;}
int mid=l+r>>1;
if(pos<=mid)Add(tree[rt].nl,tree[lastrt].nl,l,mid,pos,val,Rev);
if(pos>mid)Add(tree[rt].nr,tree[lastrt].nr,mid+1,r,pos,val,Rev);
tree[rt].sum=tree[tree[rt].nl].sum+tree[tree[rt].nr].sum;
}

int Sum(int rt,int l,int r){
if(rt==0)return 0;
if(l<=tree[rt].l && tree[rt].r<=r){
	return tree[rt].sum;
}
int mid=tree[rt].l+tree[rt].r>>1,ans=0;
if(l<=mid)ans+=Sum(tree[rt].nl,l,r);
if(r>mid)ans+=Sum(tree[rt].nr,l,r);
return ans;
}

int main(){
freopen("4408.in","r",stdin);
freopen("4408.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i];}
sort(b+1,b+n+1);
bn=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++){a[i]=lower_bound(b+1,b+bn+1,a[i])-b;V[a[i]].push_back(i);}
for(int i=1;i<=bn;i++){for(int j=0;j<V[i].size();j++)Add(root[i],root[i-1],1,n,V[i][j],b[a[V[i][j]]],i);}
scanf("%d",&m);
for(int i=1;i<=m;i++){
    int l,r;
	scanf("%d %d",&l,&r);
    int ans=0,tmp=-1;
    while(tmp<=ans){
		tmp=ans+1;
		ans=Sum(root[upper_bound(b+1,b+bn+1,tmp)-b-1],l,r);
    }
    printf("%d\n",ans+1);
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
12
2016
0

[BZOJ3110] [Zjoi2013]K大数查询

这题我在学校的OJ上A掉了,在BZOJ上WA了……很神奇

但是还是发一下代码吧,如果有什么错误欢迎各位老司机们指出

是一个树套树,外围像区间K大一样维护一个权值线段树,内部维护一个线段树记录这个值出现在哪些区间上

#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,cnt,root[500005];

struct SegTree{
int nl,nr,l,r,sum,tag;
}tree[20000005];

void Pushdown(int rt){
if(tree[rt].tag && tree[rt].l!=tree[rt].r){
	int mid=tree[rt].l+tree[rt].r>>1;
	if(!tree[rt].nl){tree[rt].nl=++cnt;tree[tree[rt].nl].l=tree[rt].l;tree[tree[rt].nl].r=mid;}
	if(!tree[rt].nr){tree[rt].nr=++cnt;tree[tree[rt].nr].l=mid+1;tree[tree[rt].nr].r=tree[rt].r;}
	tree[tree[rt].nl].tag+=tree[rt].tag;
	tree[tree[rt].nr].tag+=tree[rt].tag;
	tree[tree[rt].nl].sum+=(tree[tree[rt].nl].r-tree[tree[rt].nl].l+1)*tree[rt].tag;
	tree[tree[rt].nr].sum+=(tree[tree[rt].nr].r-tree[tree[rt].nr].l+1)*tree[rt].tag;
	tree[rt].tag=0;
}
}

void Pushup(int rt){
tree[rt].sum=tree[tree[rt].nl].sum+tree[tree[rt].nr].sum;
}

void Modify(int &rt,int l,int r,int L,int R){
if(!rt){rt=++cnt;tree[rt].l=l;tree[rt].r=r;}
Pushdown(rt);
if(L<=tree[rt].l && tree[rt].r<=R){
	tree[rt].sum+=tree[rt].r-tree[rt].l+1;
    tree[rt].tag++;
    return;
}
int mid=tree[rt].l+tree[rt].r>>1;
if(L<=mid)Modify(tree[rt].nl,l,mid,L,R);
if(R>mid)Modify(tree[rt].nr,mid+1,r,L,R);
Pushup(rt);
}

int Query(int rt,int l,int r){
if(!rt)return 0;
Pushdown(rt);
if(l<=tree[rt].l && tree[rt].r<=r){return tree[rt].sum;}
int mid=tree[rt].l+tree[rt].r>>1,ans=0;
if(l<=mid)ans+=Query(tree[rt].nl,l,r);
if(r>mid)ans+=Query(tree[rt].nr,l,r);
Pushup(rt);
return ans;
}

void Insert(int l,int r,int v){
int L=1,R=n,rt=1;
while(L!=R){
	int mid=L+R>>1;
	Modify(root[rt],1,n,l,r);
	if(v<=mid){R=mid;rt*=2;}
	else {L=mid+1;rt=rt*2+1;}
}
Modify(root[rt],1,n,l,r);
}

int Ask(int l,int r,int k){
int L=1,R=n,rt=1;
while(L!=R){
	int mid=L+R>>1;
	int ans=Query(root[rt*2],l,r);
	if(ans>=k){R=mid;rt*=2;}
	else {L=mid+1;rt=rt*2+1;k-=ans;}
}
return L;
}

int main(){
freopen("3110.in","r",stdin);
freopen("3110.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
    int opt,a,b,c;
    scanf("%d %d %d %d",&opt,&a,&b,&c);
    if(opt==1)Insert(a,b,n-c+1);
    if(opt==2)printf("%d\n",n-Ask(a,b,c)+1);
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
10
2016
0

[BZOJ1774] [Usaco2009 Dec]Toll 过路费

这题其实一开始看的时候我是不会做的……

考虑Floyd,f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

那么我们考虑k的转移顺序,如果让k的点权严格上升,那么转移时增加的点权必定为v[i],v[j]或者v[k]。

那么直接Floyd就可以了。

以后想问题时一定要弄明白算法的本质,不然就会困难重重……

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m,K,v[255],dis[255][255],ans[255][255];

struct Point{
int x,y;
friend bool operator<(Point x,Point y){return x.y<y.y;}
}p[255];

int main(){
freopen("1774.in","r",stdin);
freopen("1774.out","w",stdout);
scanf("%d %d %d",&n,&m,&K);
memset(dis,127/3,sizeof(dis));
memset(ans,127/3,sizeof(ans));
for(int i=1;i<=n;i++){
	scanf("%d",&p[i].y);
	p[i].x=i;
	v[i]=p[i].y;
}
for(int i=1;i<=m;i++){
	int x,y,z;
	scanf("%d %d %d",&x,&y,&z);
	dis[x][y]=min(dis[x][y],z);
	dis[y][x]=min(dis[y][x],z);
}
sort(p+1,p+n+1);
for(int k=1;k<=n;k++){
	int l=p[k].x;
    for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dis[i][j]=min(dis[i][j],dis[i][l]+dis[l][j]);
			ans[i][j]=min(ans[i][j],dis[i][j]+max(max(v[i],v[j]),v[l]));
		}
    }
}
for(int i=1;i<=K;i++){
	int x,y;
	scanf("%d %d",&x,&y);
	printf("%d\n",ans[x][y]);
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
10
2016
0

[BZOJ2301] [HAOI2011]Problem b

我做的第一道莫比乌斯反演!

照模版写的……题解复制自ACDreamer

-----------------------------------------------------------

我们知道莫比乌斯反演的一般描述为:

其实它还有另一种描述,本题也是用到这种。那就是:

好了,到了这里,我们开始进入正题。。。

对于本题,我们设

为满足的对数

为满足的对数

那么,很显然

反演后得到

--------------------------------------

然后我们对于莫比乌斯函数统计前缀和然后加一加就好了啦!

详细请看代码

#include<cstdio>
#include<algorithm>
using namespace std;
 
int n,a,b,c,d,k,tab[50005],cnt,prime[50005],mu[50005],sum[50005];
 
void Mobius(int num){
mu[1]=1;
for(int i=2;i<=num;i++){
    if(!tab[i]){
        prime[++cnt]=i;
        mu[i]=-1;
    }
    for(int j=1;j<=cnt && i*prime[j]<=num;j++){
        tab[i*prime[j]]=1;
        if(i%prime[j])mu[i*prime[j]]=-mu[i];
        else {mu[i*prime[j]]=0;break;}
    }
}
}
 
int Solve(int x,int y){
int ans=0,cs=0;
if(x>y)swap(x,y);
for(int i=1;i<=x;i=cs+1){
    cs=min(x/(x/i),y/(y/i));
    ans+=(sum[cs]-sum[i-1])*(x/i)*(y/i);
}
return ans;
}
 
int main(){
freopen("2301.in","r",stdin);
freopen("2301.out","w",stdout);
scanf("%d",&n);
Mobius(50000);
for(int i=1;i<=50000;i++)sum[i]=sum[i-1]+mu[i];
while(n--){
    scanf("%d %d %d %d %d",&a,&b,&c,&d,&k);
    printf("%d\n",Solve(b/k,d/k)-Solve((a-1)/k,d/k)-Solve(b/k,(c-1)/k)+Solve((a-1)/k,(c-1)/k));
}
return 0;
}
Category: BZOJ | Tags: OI bzoj

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com