5
24
2016
0

[BZOJ2396] 神奇的矩阵

暴力矩阵乘法显然会TLE。

那么我们随机一个1*n的矩阵D,然后利用矩阵运算的结合律$A*B*D=A*(B*D)$,然后就可以快速判断了。

这样操作完错误率是很低的。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
   
const int N=1005;
   
struct Matrix{
int Mt[N][N];
}A,B,C;
   
int n,Tp1[N],Tp2[N];
   
void Mul(int *r,Matrix T){
int Tp[N];
for(int i=1;i<=n;i++){
    Tp[i]=0;
    for(int j=1;j<=n;j++){
        Tp[i]+=r[j]*T.Mt[j][i];
    }
}
for(int i=1;i<=n;i++)r[i]=Tp[i];
}
   
int main(){
freopen("2396.in","r",stdin);
freopen("2396.out","w",stdout);
srand(233);
while(scanf("%d",&n)!=EOF){
    for(int i=1;i<=n;i++)Tp1[i]=Tp2[i]=rand();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&A.Mt[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&B.Mt[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&C.Mt[i][j]);
        }
    }
    Mul(Tp1,A);
    Mul(Tp1,B);
    Mul(Tp2,C);
    int flag=1;
    for(int i=1;i<=n;i++)if(Tp1[i]!=Tp2[i]){flag=0;break;}
    puts(flag?"Yes":"No");
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
5
18
2016
0

[BZOJ2054] 疯狂的馒头

并查集的应用

我居然去查了题解

水平太低了

每次往右边连边,因为只有最后一次染色有用,倒着做就没了

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

const int N=1000005;

int n,m,p,q,f[N],a[N];

int Find(int x){return !f[x]?x:f[x]=Find(f[x]);}

int main(){
freopen("2054.in","r",stdin);
freopen("2054.out","w",stdout);
scanf("%d %d %d %d",&n,&m,&p,&q);
for(int i=m;i;i--){
	int l=(i*p+q)%n+1,r=(i*q+p)%n+1;
    if(l>r)swap(l,r);
    for(int j=Find(l);j<=r;j=Find(j)){
		if(!a[j])a[j]=i;
		f[j]=j+1;
    }
}
for(int i=1;i<=n;i++)printf("%d\n",a[i]);
return 0;
}
Category: BZOJ | Tags: OI bzoj
5
18
2016
0

[BZOJ3781] 小B的询问

莫队算法模版题

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
 
const int N=50005;
 
int n,m,k,a[N],block_size,ans[N],c[N];
 
struct Query{
int l,r,block,id;
friend bool operator<(Query A,Query B){return A.block<B.block||(A.block==B.block && A.r<B.r);}
}q[N];
 
void Solve(){
int L=1,R=0,Ans=0;
for(int i=1;i<=m;i++){
    while(L<q[i].l){if(a[L])Ans-=2*c[a[L]]-1;c[a[L]]--;L++;}
    while(L>q[i].l){L--;c[a[L]]++;if(a[L])Ans+=2*c[a[L]]-1;}
    while(R<q[i].r){R++;c[a[R]]++;if(a[R])Ans+=2*c[a[R]]-1;}
    while(R>q[i].r){if(a[R])Ans-=2*c[a[R]]-1;c[a[R]]--;R--;}
    ans[q[i].id]=Ans;
}
}
 
int main(){
freopen("3781.in","r",stdin);
freopen("3781.out","w",stdout);
scanf("%d %d %d",&n,&m,&k);
block_size=(int)sqrt(m);
if(block_size<50)block_size=50;
for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]>k)a[i]=0;}
for(int i=1;i<=m;i++){
    scanf("%d %d",&q[i].l,&q[i].r);
    q[i].block=(q[i].l+1)/block_size;
    q[i].id=i;
}
sort(q+1,q+m+1);
Solve();
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}
Category: BZOJ | Tags: OI bzoj
5
18
2016
0

[BZOJ3998] [TJOI2015]弦论

第一次写SAM,遵循nixy大爷的教导来写这道题

据说是一个裸的SAM,然后我仔细观(抄)察(写)了这道题目的代码

感觉SAM很难理解啊,熟练运用就更难了

觉得fhq博客里面对于SAM的理解写的非常好,推荐一下

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

const int N=1000005;

int t,k,len,root,cnt,last,a[N],b[N];
char s[N];

struct SAM{
int next[26],fa,mx,sum,val;
}sam[N];

int Newnode(int x){
sam[++cnt].mx=x;
return cnt;
}

void Extend(int x){
int np=Newnode(sam[last].mx+1),p=last;
sam[np].val=1;last=np;
for(;p && !sam[p].next[x];p=sam[p].fa)sam[p].next[x]=np;
if(!p){sam[np].fa=root;return;}
int q=sam[p].next[x];
if(sam[q].mx==sam[p].mx+1){sam[np].fa=q;return;}
int nq=Newnode(sam[p].mx+1);
sam[nq].fa=sam[q].fa;
sam[q].fa=sam[np].fa=nq;
memcpy(sam[nq].next,sam[q].next,sizeof(sam[q].next));
for(;p && sam[p].next[x]==q;p=sam[p].fa)sam[p].next[x]=nq;
}

void Toposort(){
for(int i=1;i<=len;i++)b[i]=0;
for(int i=1;i<=cnt;i++)b[sam[i].mx]++;
for(int i=1;i<=len;i++)b[i]+=b[i-1];
for(int i=cnt;i;i--)a[b[sam[i].mx]--]=i;
if(t==1)for(int i=cnt;i;i--)sam[sam[a[i]].fa].val+=sam[a[i]].val;
else for(int i=cnt;i;i--)sam[sam[a[i]].fa].val=1;
sam[root].val=0;
for(int i=cnt;i;i--){
	sam[a[i]].sum=sam[a[i]].val;
	for(int j=0;j<26;j++)sam[a[i]].sum+=sam[sam[a[i]].next[j]].sum;
}
}

void dfs(int rt,int k){
if(k<=sam[rt].val)return;
k-=sam[rt].val;
for(int i=0;i<26;i++){
	if(k<=sam[sam[rt].next[i]].sum){putchar(i+'a');dfs(sam[rt].next[i],k);return;}
	k-=sam[sam[rt].next[i]].sum;
}
}

int main(){
freopen("3998.in","r",stdin);
freopen("3998.out","w",stdout);
scanf("%s %d %d",s,&t,&k);
len=strlen(s);
last=root=Newnode(0);
for(int i=0;i<len;i++)Extend(s[i]-'a');
Toposort();
if(k>sam[root].sum)puts("-1");
else dfs(root,k);
return 0;
}
Category: BZOJ | Tags: OI bzoj
5
17
2016
0

[BZOJ3174] [Tjoi2013]拯救小矮人

首先我们按照逃跑能力($a+b$)排序,然后把逃跑能力强的放后面

然后dp,设$f[i]$表示在$i$个人逃跑后剩下的人梯最高高度

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

const int N=2005;

int n,h,f[N],ans=0;

struct Data{
int a,b;
friend bool operator<(Data A,Data B){return A.a+A.b<B.a+B.b;}
}man[N];

int main(){
freopen("3174.in","r",stdin);
freopen("3174.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d %d",&man[i].a,&man[i].b);
scanf("%d",&h);
sort(man+1,man+n+1);
memset(f,-1,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++)f[0]+=man[i].a;
for(int i=1;i<=n;i++){
	for(int j=ans;j>=0;j--){
		if(f[j]+man[i].b>=h)f[j+1]=max(f[j+1],f[j]-man[i].a);
		if(f[ans+1]>=0)ans++;
	}
}
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
5
16
2016
0

[BZOJ3874] [Ahoi2014]宅男计划

三分送外卖次数,然后贪心的买外卖就好了

过程:首先我们要每次买最便宜的外卖一份,这样保证我们可以过送外卖次数的天数

然后还有剩下的钱我们就优先选择便宜的来填满这些食物的保质期,填满了之后我们再选择次便宜的填满保质期,以此类推

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

const int N=205;

int n,Top;
long long m,f;

struct Food{
long long p,s;
friend bool operator<(Food A,Food B){return A.p<B.p;}
}food[N],Q[N];

long long Get(long long x){
long long mo=m-x*f,day=0,ans=0,last;
if(mo<0)return 0;
for(int i=1;i<=Top;i++){
	if(day<=Q[i].s){
		last=min(Q[i].s-day+1,mo/Q[i].p/x);
		ans+=last*x;
		mo-=last*Q[i].p*x;
		day+=last;
	}
	if(day<=Q[i].s){
		last=min(x,mo/Q[i].p);
		ans+=last;
		mo-=Q[i].p*last;
		day++;
	}
}
return ans;
}

long long Solve(){
long long l=1,r=m/(f+Q[1].p),ans1=0,ans2=0,ans=max(Get(l),Get(r));
while(l<=r){
    long long mid1=l+(r-l)/3,mid2=r-(r-l)/3;
    ans1=Get(mid1);ans2=Get(mid2);
    ans=max(ans,max(ans1,ans2));
    if(ans1<ans2)l=mid1+1;
    else r=mid2-1;
}
return ans;
}

int main(){
freopen("3874.in","r",stdin);
freopen("3874.out","w",stdout);
scanf("%lld %lld %d",&m,&f,&n);
for(int i=1;i<=n;i++)scanf("%lld %lld",&food[i].p,&food[i].s);
sort(food+1,food+n+1);
Q[++Top]=food[1];
for(int i=2;i<=n;i++){
	if(food[i].s>Q[Top].s)Q[++Top]=food[i];
}
printf("%lld\n",Solve());
return 0;
}
Category: BZOJ | Tags: OI bzoj
5
16
2016
0

[BZOJ3330] [BeiJing2013]分数

感觉自己三分姿势一直是错的所以来补这题

注意输出就好了

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

const int N=25;
const double eps=1e-12,INF=1e200;

int n,p,Bit[N*4];
double a[N],b[N];

void Print(double x){
long long ans=(long long)x;
int dig=0;
while(ans){dig++;Bit[dig]=ans%10;ans/=10;}
ans=(long long)x;
if(dig>=p){
	for(int i=dig;i>=dig-p+1;i--)putchar(Bit[i]+'0');
	for(int i=dig-p;i>=1;i--)putchar('0');
}
else {
	printf("%lld.",ans);
	x-=ans;
	p-=dig;
	while(p--){x*=10;putchar(((long long)x)%10+'0');}
}
putchar('\n');
}

double Score(int x,double diff,double disc){
return 100.0/(1.0+exp(diff-disc*a[x]));
}

double Dec(double diff,double disc){
double ans=0.0;
for(int i=1;i<=n;i++){
    double Sc=Score(i,diff,disc);
    if(Sc<eps || Sc+eps>=100.0)return INF;
    ans+=b[i]*log(100.0/Sc)+(100.0-b[i])*log(100.0/(100.0-Sc));
}
return ans;
}

double Div3_2(double diff){
double l=0.0,r=1.0;
while(r-l>eps){
	double mid1=(l+r)/2,mid2=(mid1+r)/2;
	if(Dec(diff,mid1)>Dec(diff,mid2))l=mid1;
	else r=mid2;
}
return Dec(diff,(l+r)/2);
}

void Div3(){
double l=0.0,r=10.0;
while(r-l>eps){
	double mid1=(l+r)/2,mid2=(mid1+r)/2;
	if(Div3_2(mid1)>Div3_2(mid2))l=mid1;
	else r=mid2;
}
Print(Div3_2((l+r)/2));
}

int main(){
freopen("3330.in","r",stdin);
freopen("3330.out","w",stdout);
scanf("%d %d",&n,&p);
for(int i=1;i<=n;i++)scanf("%lf",&a[i]);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)b[i]=100.0*(i-1)/(n-1);
Div3();
return 0;
}
Category: BZOJ | Tags: OI bzoj
5
10
2016
0

[BZOJ3064] Tyvj 1518 CPU监控

恶心的线段树

维护6个标记

最后调不出来找来标程

原来标记的先后顺序也有关系

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

const int N=100005,INF=2100000000;

int T,E,a[N];

struct SegTree{
int add,mx,cov,l,r;
}tree[4*N],histree[4*N];

void CheckMax(int rt,int val){histree[rt].mx=max(histree[rt].mx,val);}

void HisAdd(int rt,int val){
CheckMax(rt,tree[rt].mx+val);
if(tree[rt].cov>-INF)histree[rt].cov=max(histree[rt].cov,tree[rt].cov+val);
else histree[rt].add=max(histree[rt].add,tree[rt].add+val);
}

void HisCover(int rt,int val){
CheckMax(rt,val);
histree[rt].cov=max(histree[rt].cov,val);
}

void Add(int rt,int val){
CheckMax(rt,tree[rt].mx+=val);
if(tree[rt].cov>-INF)histree[rt].cov=max(histree[rt].cov,tree[rt].cov+=val);
else histree[rt].add=max(histree[rt].add,tree[rt].add+=val);
}

void Cover(int rt,int val){
CheckMax(rt,tree[rt].mx=val);
histree[rt].cov=max(histree[rt].cov,tree[rt].cov=val);
tree[rt].add=0;
}

void Pushdown(int rt){
if(histree[rt].add){
	HisAdd(rt<<1,histree[rt].add);
	HisAdd(rt<<1|1,histree[rt].add);
	histree[rt].add=0;
}
if(histree[rt].cov!=-INF){
	HisCover(rt<<1,histree[rt].cov);
	HisCover(rt<<1|1,histree[rt].cov);
	histree[rt].cov=-INF;
}
if(tree[rt].add){
    Add(rt<<1,tree[rt].add);
	Add(rt<<1|1,tree[rt].add);
	tree[rt].add=0;
}
if(tree[rt].cov!=-INF){
	Cover(rt<<1,tree[rt].cov);
	Cover(rt<<1|1,tree[rt].cov);
	tree[rt].cov=-INF;
}
}

void Pushup(int rt){
histree[rt].mx=max(histree[rt].mx,max(histree[rt<<1].mx,histree[rt<<1|1].mx));
tree[rt].mx=max(tree[rt<<1].mx,tree[rt<<1|1].mx);
}

void Build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
tree[rt].add=0;
tree[rt].mx=-INF;
tree[rt].cov=-INF;
histree[rt].l=l;
histree[rt].r=r;
histree[rt].add=0;
histree[rt].mx=-INF;
histree[rt].cov=-INF;
if(l==r){tree[rt].mx=histree[rt].mx=a[l];return;}
int mid=l+r>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
Pushup(rt);
}

void Plus(int rt,int l,int r,int val){
if(l<=tree[rt].l && tree[rt].r<=r){
	Add(rt,val);
	return;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Plus(rt<<1,l,r,val);
if(r>mid)Plus(rt<<1|1,l,r,val);
Pushup(rt);
}

void Change(int rt,int l,int r,int val){
if(l<=tree[rt].l && tree[rt].r<=r){
	Cover(rt,val);
	return;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Change(rt<<1,l,r,val);
if(r>mid)Change(rt<<1|1,l,r,val);
Pushup(rt);
}

int Query(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r)return tree[rt].mx;
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1,ans=-INF;
if(l<=mid)ans=max(ans,Query(rt<<1,l,r));
if(r>mid)ans=max(ans,Query(rt<<1|1,l,r));
return ans;
}

int Ask(int rt,int l,int r){
if(l<=histree[rt].l && histree[rt].r<=r)return histree[rt].mx;
Pushdown(rt);
int mid=histree[rt].l+histree[rt].r>>1,ans=-INF;
if(l<=mid)ans=max(ans,Ask(rt<<1,l,r));
if(r>mid)ans=max(ans,Ask(rt<<1|1,l,r));
return ans;
}

int main(){
freopen("3064.in","r",stdin);
freopen("3064.out","w",stdout);
scanf("%d",&T);
for(int i=1;i<=T;i++)scanf("%d",&a[i]);
Build(1,1,T);
scanf("%d",&E);
for(int i=1;i<=E;i++){
    char s[10];
    int x,y,z;
    scanf("%s",s);
    if(s[0]=='Q'){scanf("%d %d",&x,&y);printf("%d\n",Query(1,x,y));}
    if(s[0]=='A'){scanf("%d %d",&x,&y);printf("%d\n",Ask(1,x,y));}
    if(s[0]=='P'){scanf("%d %d %d",&x,&y,&z);Plus(1,x,y,z);}
    if(s[0]=='C'){scanf("%d %d %d",&x,&y,&z);Change(1,x,y,z);}
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
5
10
2016
0

[BZOJ2697] 特技飞行

贪心的做

因为只做一次特技显然没用

我们要把价值最大的特技安排在两端

然后贪心的做特技就好了

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
int n,k,c[1005],ans;
 
int main(){
freopen("2697.in","r",stdin);
freopen("2697.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=1;i<=k;i++)scanf("%d",&c[i]);
sort(c+1,c+k+1);
for(int i=k;i>=1 && n>1;i--,n-=2){ans+=c[i]*(n-1);}
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
5
10
2016
0

[BZOJ2626] JZPFAR

KD-Tree直接上

维护一个关于点对距离的数组

每次询问直接在KD-Tree里面贪心的找就可以了

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const int N=100005;
 
int Sort_Tag,n,m,root,Ask_k,id[25];
long long Ask_x,Ask_y,ans[25];
 
struct KDTree{
long long d[2],mx[2],mn[2];
int l,r,id;
friend bool operator<(KDTree A,KDTree B){
return (A.d[Sort_Tag]<B.d[Sort_Tag])||(A.d[Sort_Tag]==B.d[Sort_Tag] && A.d[!Sort_Tag]<B.d[!Sort_Tag]);
}
}tree[N],Tp;
 
void Pushup(int rt){
if(tree[rt].l){
    if(tree[rt].mn[0]>tree[tree[rt].l].mn[0])tree[rt].mn[0]=tree[tree[rt].l].mn[0];
    if(tree[rt].mn[1]>tree[tree[rt].l].mn[1])tree[rt].mn[1]=tree[tree[rt].l].mn[1];
    if(tree[rt].mx[0]<tree[tree[rt].l].mx[0])tree[rt].mx[0]=tree[tree[rt].l].mx[0];
    if(tree[rt].mx[1]<tree[tree[rt].l].mx[1])tree[rt].mx[1]=tree[tree[rt].l].mx[1];
}
if(tree[rt].r){
    if(tree[rt].mn[0]>tree[tree[rt].r].mn[0])tree[rt].mn[0]=tree[tree[rt].r].mn[0];
    if(tree[rt].mn[1]>tree[tree[rt].r].mn[1])tree[rt].mn[1]=tree[tree[rt].r].mn[1];
    if(tree[rt].mx[0]<tree[tree[rt].r].mx[0])tree[rt].mx[0]=tree[tree[rt].r].mx[0];
    if(tree[rt].mx[1]<tree[tree[rt].r].mx[1])tree[rt].mx[1]=tree[tree[rt].r].mx[1];
}
}
 
int Build(int l,int r,int D){
int mid=l+r>>1;
Sort_Tag=D;
nth_element(tree+l+1,tree+mid+1,tree+r+1);
tree[mid].mx[0]=tree[mid].mn[0]=tree[mid].d[0];
tree[mid].mx[1]=tree[mid].mn[1]=tree[mid].d[1];
if(l<mid)tree[mid].l=Build(l,mid-1,!D);
if(r>mid)tree[mid].r=Build(mid+1,r,!D);
Pushup(mid);
return mid;
}
 
long long Sqr(long long x){return x*x;}
 
long long MxDist(int p,long long x,long long y){
return max(Sqr(tree[p].mx[0]-x),Sqr(tree[p].mn[0]-x))+max(Sqr(tree[p].mx[1]-y),Sqr(tree[p].mn[1]-y));
}
 
void Query(int rt){
long long Dl,Dr,Dm=Sqr(tree[rt].d[0]-Ask_x)+Sqr(tree[rt].d[1]-Ask_y);
int Kt=Ask_k;
while(Kt && ((ans[Kt]<Dm)||(ans[Kt]==Dm && id[Kt]>tree[rt].id)))Kt--;
if(Kt!=Ask_k){
    for(int i=Ask_k;i>=Kt+2;i--){
        ans[i]=ans[i-1];
        id[i]=id[i-1];
    }
    ans[Kt+1]=Dm;id[Kt+1]=tree[rt].id;
}
if(tree[rt].l)Dl=MxDist(tree[rt].l,Ask_x,Ask_y);else Dl=-1;
if(tree[rt].r)Dr=MxDist(tree[rt].r,Ask_x,Ask_y);else Dr=-1;
if(Dl<Dr){
    if(Dr>=ans[Ask_k])Query(tree[rt].r);
    if(Dl>=ans[Ask_k])Query(tree[rt].l);
}
else {
    if(Dl>=ans[Ask_k])Query(tree[rt].l);
    if(Dr>=ans[Ask_k])Query(tree[rt].r);
}
}
 
int main(){
freopen("2626.in","r",stdin);
freopen("2626.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%lld %lld",&tree[i].d[0],&tree[i].d[1]);tree[i].id=i;}
root=Build(1,n,0);
scanf("%d",&m);
for(int i=1;i<=m;i++){
    scanf("%lld %lld %lld",&Ask_x,&Ask_y,&Ask_k);
    memset(ans,0,sizeof(ans));
    memset(id,127,sizeof(id));
    Query(root);
    printf("%d\n",id[Ask_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