Lvat_s Blog

今天晚上ygp讲了一下单调队列，所以就写了这道题。

建立一个单调队列(升序)，然后维持该升序后利用二分查找符合标准的值作为ans。

据说线段树和单调栈也可以搞这题，那我也得到以后再写了(我现在不会线段树啊QAQ)

单调队列：

#include<cstdio>

int n,d,rear=1,lastans=0,counted=0;
char x;

struct Node{
int i,v;
}q[200005];

int main(){
freopen("1012.in","r",stdin);
freopen("1012.out","w",stdout);
scanf("%d %d",&n,&d);
while(n--){
    int w;
    scanf("%s %d",&x,&w);
    if(x=='Q'){
        int l=1,r=rear,mid,ans=-1;
        while(l<=r){
            mid=(l+r)/2;
            if(counted-q[mid].i+1>w){
                l=mid+1;
            }
            else {
                ans=mid;
                r=mid-1;
            }
        }
        printf("%d\n",q[ans].v);
        lastans=q[ans].v;
    }
    else {
        w=(w+lastans)%d;
        while(rear>0 && q[rear].v<w)rear--;
        q[++rear].i=++counted;
        q[rear].v=w;
    }
}
return 0;
}

01背包模版题。

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

int n,v,a[5005],f[50005];

int main(){
freopen("1606.in","r",stdin);
freopen("1606.out","w",stdout);
scanf("%d %d",&v,&n);
for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
    for(int j=v;j>=a[i];j--){
        f[j]=max(f[j],f[j-a[i]]+a[i]);
    }
}
printf("%d\n",f[v]);
return 0;
}

加上一个点跑最小生成树即可。

#include<cstdio>
#include<cstdlib>

int en,f[305],n,a[305][305];

struct Edge{
int a,b,v;
}e[90005];

int cmp(const void *a,const void *b){
return (*(Edge *)a).v-(*(Edge *)b).v;
}

void add(int sa,int sb,int sc){
e[++en].a=sa;
e[en].b=sb;
e[en].v=sc;
}

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

void Union(int sa,int sb){
if(sa>sb)f[sa]=sb;
else f[sb]=sa;
}

int main(){
freopen("1601.in","r",stdin);
freopen("1601.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    int w;
    f[i]=i;
    scanf("%d",&w);
    add(n+1,i,w);
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        scanf("%d",&a[i][j]);
        add(i,j,a[i][j]);
    }
}
qsort(e+1,en,sizeof(Edge),cmp);
int num=0,cost=0;
for(int i=1;i<=en;i++){
if(num==n)break;
if(Find(e[i].a)!=Find(e[i].b)){num++;e[i].a=Find(e[i].a);e[i].b=Find(e[i].b);Union(e[i].a,e[i].b);cost+=e[i].v;}
}
printf("%d\n",cost);
return 0;
}

这题是一个水dp。

用类似最长不下降子序列的方法来写。

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

int n,m,f[10005];

struct Node{
int time,a,b;
}a[10005];

int absd(int x){return x>0?x:-x;}

int main(){
freopen("1207.in","r",stdin);
freopen("1207.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
    scanf("%d %d %d",&a[i].time,&a[i].a,&a[i].b);
}
f[1]=1;
for(int i=2;i<=m;i++){
    f[i]=1;
    for(int j=1;j<i;j++){
        if(absd(a[j].a-a[i].a)+absd(a[j].b-a[i].b)<=a[i].time-a[j].time && f[j]+1>f[i])f[i]=f[j]+1;
    }
    f[0]=max(f[i],f[0]);
}
printf("%d\n",f[0]);
return 0;
}

颓废了2个晚上，总算水掉了这道题……

这题我们使用倍增LCA可以解决。

每次三个点找两点间LCA，相同的LCA取另一个就可以了。

我没有使用读入优化，如果用了速度会更快吧……

#include<cstdio>

int n,m,h[500005],en,fa[500005][20],deep[500005],flg[500005];

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

void add(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

void Yuchuli(int u){
flg[u]=1;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(!flg[v]){
        deep[v]=deep[u]+1;
        fa[v][0]=u;
        Yuchuli(v);
    }
}
}

void Move(int &u,int H){
for(int i=18;i>=0;i--){
    if(deep[fa[u][i]]>=H){
        u=fa[u][i];
    }
}
}

int LCA(int u,int v){
int now=0;
if(deep[u]!=deep[v]){if(deep[u]>deep[v])Move(u,deep[v]);else Move(v,deep[u]);}
if(u==v){return u;}
for(int i=18;i>=0;i--){
    if(fa[u][i]!=fa[v][i]){
        u=fa[u][i];
        v=fa[v][i];
    }
}
return fa[u][0];
}

int GetCost(int u,int v){
int w=LCA(u,v);
return deep[u]+deep[v]-2*deep[w];
}

int main(){
freopen("1787.in","r",stdin);
freopen("1787.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<n;i++){
    int sa,sb;
    scanf("%d %d",&sa,&sb);
    add(sa,sb);
    add(sb,sa);
}
Yuchuli(1);
fa[1][0]=1;
for(int j=1;j<=18;j++){
    for(int i=1;i<=n;i++){
        fa[i][j]=fa[fa[i][j-1]][j-1];
    }
}
while(m--){
    int sa,sb,sc;
    scanf("%d %d %d",&sa,&sb,&sc);
    int FineLCA,LCA1=LCA(sa,sb),LCA2=LCA(sa,sc),LCA3=LCA(sb,sc);
    if(LCA1==LCA2)FineLCA=LCA3;
    else if(LCA3==LCA2)FineLCA=LCA1;
    else FineLCA=LCA2;
    printf("%d %d\n",FineLCA,GetCost(FineLCA,sa)+GetCost(FineLCA,sb)+GetCost(FineLCA,sc));
}
return 0;
}

upd 2016.6.2

今天学习了Tarjan求LCA，用这个题练习一下

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

const int N=500005,INF=2100000000;

int n,m,h[N],en,f[N],vis[N],dep[N],anc[N];

struct Edge{
int b,next;
}e[N<<1];

struct List{
int v,par;
List *next;
List(){next=NULL;par=0;}
List(int _v,List *_next){v=_v;next=_next;par=0;}
}*Lis[N];

List *AddList(int u,int v){
List *node=new List(v,Lis[u]);
Lis[u]=node;
return node;
}

struct Query{
int u,v,w;
List *id11,*id12,*id21,*id22,*id31,*id32;
Query(){}
Query(int _u,int _v,int _w){u=_u;v=_v;w=_w;}
}Que[N];

void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
int Abs(int x){return x>0?x:-x;}
int GetCost(int u,int v,int w){return dep[u]+dep[v]-2*dep[w];}

void Tarjan(int u,int fa){
f[u]=u;
dep[u]=dep[fa]+1;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(!f[v]){Tarjan(v,u);f[v]=u;}
}
for(List *I=Lis[u];I;I=I->next){
    int v=I->v;
    if(f[v])I->par=Find(v);
}
}

int main(){
freopen("1787.in","r",stdin);
freopen("1787.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<n;i++){
	int u,v;
	scanf("%d %d",&u,&v);
	AddEdge(u,v);AddEdge(v,u);
}
for(int i=1;i<=m;i++){
	scanf("%d %d %d",&Que[i].u,&Que[i].v,&Que[i].w);
	Que[i].id11=AddList(Que[i].u,Que[i].v);
	Que[i].id21=AddList(Que[i].u,Que[i].w);
	Que[i].id31=AddList(Que[i].v,Que[i].w);
	Que[i].id12=AddList(Que[i].v,Que[i].u);
	Que[i].id22=AddList(Que[i].w,Que[i].u);
	Que[i].id32=AddList(Que[i].w,Que[i].v);
}
Tarjan(1,1);
for(int i=1;i<=m;i++){
    int LCA1=max(Que[i].id11->par,Que[i].id12->par);
    int LCA2=max(Que[i].id21->par,Que[i].id22->par);
    int LCA3=max(Que[i].id31->par,Que[i].id32->par);
    int Cost=GetCost(LCA1,Que[i].u,LCA1)+GetCost(LCA1,Que[i].v,LCA1)+GetCost(LCA1,Que[i].w,LCA2);
    if(LCA1==LCA2){Cost=GetCost(LCA3,Que[i].u,LCA2)+GetCost(LCA3,Que[i].v,LCA3)+GetCost(LCA3,Que[i].w,LCA3);LCA1=LCA3;}
    else if(LCA1==LCA3){Cost=GetCost(LCA2,Que[i].u,LCA2)+GetCost(LCA2,Que[i].v,LCA1)+GetCost(LCA2,Que[i].w,LCA2);LCA1=LCA2;}
	printf("%d %d\n",LCA1,Cost);
}
return 0;
}

这一题是一个很裸的二分图。每次以当前的问题编号连接两个锦囊的编号，跑一遍二分图就可以了。

#include<cstdio>
#include<cstring>
  
int link[1005],n,m,h[1005],en,b[1005],ans;
  
struct Edge{
    int b,next; 
}e[1005];
  
void Add(int sa,int sb){
    e[++en].b=sb;
    e[en].next=h[sa];
    h[sa]=en;
}
  
int Find(int u){
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(b[v])continue;
    b[v]=1;
    if(!link[v] || Find(link[v])){
        link[v]=u;
        return 1;
    }
}
return 0;
}
  
int main(){
    freopen("1191.in","r",stdin);
    freopen("1191.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        int sa,sb;
        scanf("%d %d",&sa,&sb);
        Add(i,sb+1);
        Add(i,sa+1);
    }
    for(int i=1;i<=m;i++){
        memset(b,0,sizeof(b));
        if(Find(i))ans++;
        else break;
    }
    printf("%d\n",ans);
    return 0;
}

水题不想多说了……

#include<cstdio>
#include<cmath>

int s;

int main(){
scanf("%d",&s);
int i,w=1;
for(i=1;;i++){
w*=2;
if(w>s)break;
}
printf("%d\n",i);
return 0;
}

想了一下，又看看黄大神的blog，然后就水掉了这题……

具体请看hzwer's blog:点击此处

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

int n,flg[50005],ST;

struct Node{
double a,b;
int i;
}a[50005],s[50005];

int cmp(Node sa,Node sb){
if(fabs(sa.a-sb.a)<=0.0000001)return sa.b<sb.b;
return sa.a<sb.a;
}

double SetX(Node x,Node y){
return (y.b-x.b)/(x.a-y.a);
}

void Insert(int x){
while(ST){
    if(fabs(s[ST].a-a[x].a)<=0.0000001)ST--;
    else if(ST>1 && SetX(a[x],s[ST-1])<=SetX(s[ST],s[ST-1])){
        ST--;
    }
    else break;
}
s[++ST]=a[x];
}

int main(){
freopen("1007.in","r",stdin);
freopen("1007.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%lf %lf",&a[i].a,&a[i].b);
    a[i].i=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)Insert(i);
for(int i=1;i<=ST;i++)flg[s[i].i]=1;
for(int i=1;i<=n;i++)if(flg[i])printf("%d ",i);
return 0;
}

喜闻乐见的良心大水题……(这种题居然放在bzoj上)

以下是代码，不用解释了吧

#include<cstdio>

int n,ans=0;
int main(){
freopen("1968.in","r",stdin);
freopen("1968.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)ans+=n/i;
printf("%d\n",ans);
return 0;
}

嗯……这题是做两遍dp,设f[i][j]为前i个点的路面当高度为j(已经离散化)后所能付出的最小代价，则状态转移方程为：

f[i][j]=min(f[i][j-1],f[i-1][j]+abs(j-a[i]))

我作死用了滚动数组……

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

int n,a[2005],f[2][2005],g[2][2005],b[2005];

int absd(int h){
return h>0?h:-h;
}

int cmp(int sa,int sb){
return sa>sb;
}

int main(){
freopen("1592.in","r",stdin);
freopen("1592.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);
f[1][0]=f[0][0]=2147483647;
for(int i=1;i<=n;i++){
    int now=i%2,pre;
    pre=now^1;
    for(int j=1;j<=n;j++){
        f[now][j]=min(f[now][j-1],f[pre][j]+absd(b[j]-a[i]));
    }
}
g[0][0]=g[1][0]=2147483647;
for(int i=1;i<=n;i++){
    int now=i%2,pre;
    pre=now^1;
    for(int j=1;j<=n;j++){
        g[now][j]=min(g[now][j-1],g[pre][j]+absd(b[n+1-j]-a[i]));
    }
}
printf("%d\n",min(g[n%2][n],f[n%2][n]));
return 0;
}