DZY 's BLOG

10000个数。有些数空着给你填。每个数的范围都在1~K内。求出填满后的逆序对的最小值。

很明显这几个填的数是递增的。不然自己就产生逆序对了。（没证明过

先处理出da[i][j]表示i~n中比j大的数，xi[i][j]表示1~i中比j小的数。

f[i][j]表示填到第i个数了，这位填了j所产生的逆序对。

则f[i][j]=min{f[i][k]+da[pos[i]][j]+xi[pos[i]][j]}。然后再加上数列本身的逆序对数就行了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=1061109567;
int a[10005],da[10005][105],xi[10005][105],p[10005],f[10005][100],n,k,m=0,An=0;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(!~a[i]) p[++m]=i;
    }for(int i=2;i<=n;i++){
        for(int j=1;j<=k;j++) da[i][j]=da[i-1][j];
        if(~a[i-1]) for(int j=1;j<a[i-1];j++) da[i][j]++;
    }for(int i=n-1;i;i--){
        for(int j=1;j<=k;j++) xi[i][j]=xi[i+1][j];
        if(~a[i+1]) for(int j=a[i+1]+1;j<=k;j++) xi[i][j]++;
    }for(int i=1;i<=n;i++) if(~a[i]) An+=da[i][a[i]];
    memset(f,63,sizeof(f));
    for(int i=1;i<=k;i++) f[1][i]=da[p[1]][i]+xi[p[1]][i];
    for(int i=2;i<=m;i++) for(int j=1;j<=k;j++) for(int o=1;o<=j;o++)
        f[i][j]=min(f[i][j],f[i-1][o]+da[p[i]][j]+xi[p[i]][j]);
    int An2=inf;  for(int i=1;i<=k;i++) An2=min(An2,f[m][i]);
    An2=(An2==inf)?0:An2;
    printf("%d\n",An+An2); return 0;
}

设dp[i][j]表示第i个数变为j的最小代价。

则dp[i][j]=min{dp[i-1][k]+c*abs(j-k)+(j-h[i])^2}（k是第i-1位上的数，j是当前位上的数）

100000*100*100。。哗~萎掉了。。

把abs(j-k)拆开试试？

j>k时：dp[i][j]=min{dp[i-1][k]+c*j-c*k+(j-h[i])^2}=min{dp[i-1][k]-c*k}+c*j+(j-h[i])^2

j<k时：dp[i][j]=min{dp[i-1][k]+c*k-c*j+(j-h[i])^2}=min{dp[i-1][k]+c*k}-c*j+(j-h[i])^2

那么我们只要在每次转移的时候记录f数组表示min{dp[i-1][k]-c*k}，g数组表示min{dp[i-1][k]+c*k}。这样转移的时候就是O(10w*100)了~

至于空间的话，第一维好像一点用都没有。那就不要了！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define abs(x) (((x)<0)?(-(x)):(x))
#define sqr(x) ((x)*(x))
int dp[105],f[105],g[105],h[100005],n,c;
const int inf=1061109567;
char buf[2000000],*p=buf;
inline int getint(){
    int r=0;while(*p<48||*p>57)p++;while(*p>47&&*p<58)r=r*10+*p++-'0';return r;
}int main(){
    fread(buf,1,2000000,stdin); n=getint(),c=getint();
    for(int i=1;i<=n;i++) h[i]=getint();
    memset(dp,63,sizeof(dp));
    for(int i=h[1];i<=100;i++) dp[i]=sqr(i-h[1]);
    for(int i=2;i<=n;i++){
        f[101]=inf; for(int j=100;j>=1;j--) f[j]=min(dp[j]+j*c,f[j+1]);
        g[0]=inf;   for(int j=1;j<=100;j++) g[j]=min(dp[j]-j*c,g[j-1]);
        memset(dp,63,sizeof(dp));
        for(int j=h[i];j<=100;j++) dp[j]=sqr(j-h[i])+min(g[j]+j*c,f[j]-j*c);
    }int An=inf;
    for(int i=1;i<=100;i++) An=min(An,dp[i]);
    printf("%d\n",An);  return 0;
}

模拟一下发现答案与取球的顺序其实是无关的。

然后去膜拜题解发现的确这样。至于证明蒟蒻看不懂。

但是既然这样就是高精度模拟了？

双倍经验（1416 && 1498）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
struct Hugeint{int len,num[10000];  Hugeint(){  len=1;  memset(num,0,sizeof(num));}}An1,An2;
int num[1005],A[10000]={0},B[10000]={0},flag[20005]={0},prime[10000],cnt=0,sum=0;
inline int pre(int n){
    for(int i=2;i<=n;i++){
        if(!flag[i]) prime[cnt++]=i;
        for(int j=0;j<cnt&&prime[j]*i<=n;j++){
            flag[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}inline Hugeint Mul(Hugeint a,Hugeint b){
    Hugeint c;  c.len=a.len+b.len+1;
    for(int i=1;i<=a.len;i++) for(int j=1;j<=b.len;j++)  c.num[i+j-1]+=a.num[i]*b.num[j];
    for(int i=1;i<c.len;i++)  if(c.num[i]>9999) c.num[i+1]+=c.num[i]/10000,c.num[i]%=10000;
    while(c.num[c.len]>9999) c.len++,c.num[c.len]+=c.num[c.len-1]/10000,c.num[c.len-1]%=10000;
    while(c.num[c.len]==0&&c.len>1) c.len--;   return c;
}inline Hugeint pow(int b,int p){
    Hugeint ans,bb; ans.len=bb.len=ans.num[1]=1ll;  bb.num[1]=b;
    while(p){if(p&1ll)ans=Mul(ans,bb);p>>=1ll;bb=Mul(bb,bb);}   return ans;
}void print(Hugeint a){
    printf("%d",a.num[a.len]); for(int i=a.len-1;i;i--)printf("%04d",a.num[i]);
}inline void pushA(int k){
    for(int i=0;k>1&&i<cnt&&prime[i]<=k;i++) while(k%prime[i]==0)A[i]++,k/=prime[i];
}inline void pushB(int k){
    for(int i=0;k>1&&i<cnt&&prime[i]<=k;i++) while(k%prime[i]==0)B[i]++,k/=prime[i];
}int main(){
    int n,m,d,x,y;  pre(20000);
    scanf("%d%d%d",&n,&m,&d); for(int i=1;i<=n;i++)scanf("%d",&num[i]),sum+=num[i];
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        if(num[y]==0){ printf("0/1\n");return 0;}
        pushA(num[y]);  pushB(sum);
        num[y]+=d;      sum+=d;
    }for(int i=0;i<cnt;i++) if(A[i]&&B[i]){
        if(A[i]>B[i])   A[i]-=B[i], B[i]=0;
        else            B[i]-=A[i], A[i]=0;
    }An1.num[1]=An2.num[1]=1;
    for(int i=0;i<cnt;i++)  if(A[i])    An1=Mul(An1,pow(prime[i],A[i]));
    for(int i=0;i<cnt;i++)  if(B[i])    An2=Mul(An2,pow(prime[i],B[i]));
    print(An1);putchar('/');print(An2);putchar('\n');return 0;
}

给你一颗无根树。每条边的路径长是1。

每次询问给你三个点。要求你找到一个点。使其它三个点到这个点的路径和最小。

看到这种题就很快联想到LCA了。然后看看样例然后随便手造几组数据，发现求的点一定在其中两个点的LCA。

那么就好了。每次求出3个LCA。然后枚举。算出距离和。

介于倍增比rmq好写的多。就没写rmq。不过倍增的话每次求lca是logn的。每次询问差不多要做6次LCA。那么6logn。

如果是rmq的话每次询问时O(1)。预处理都是nlogn。那么常数一下就跪了。刷rank1也没戏了、不过还有个rank2= =还是玩不过seter、、跪烂、、

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char buf[21000000],*pt=buf,*o=buf;
int p[1000005],n1[1000005],h[500005]={0},q[500005],d[500005],v[500005]={0};
int lg[500005],a[500005][20],n,m,tot=1;
inline int getint(){    int r=0; while(*pt<48||*pt>57)pt++;
    while(*pt>47&&*pt<58)r=r*10+*pt++-48; return r;
}inline void print(int x){
    char str[11],*p=str; if(!x)*o++=48;
    else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;}
}inline void ae(int a,int b){
    p[tot]=b; n1[tot]=h[a]; h[a]=tot++; p[tot]=a; n1[tot]=h[b]; h[b]=tot++;
}inline void pre(){
    int s=0,e=1; q[0]=1; d[1]=1; v[1]=1;
    while(s<e){
        for(int i=h[q[s++]];i;i=n1[i]) if(!v[p[i]])
            v[p[i]]=1,q[e++]=p[i],d[p[i]]=d[q[s-1]]+1,a[p[i]][0]=q[s-1];
    }for(int j=1;j<20;j++) for(int i=1;i<=n;i++) a[i][j]=a[a[i][j-1]][j-1];
}inline int lca(int u,int v){
    if(d[u]>d[v]){ u^=v; v^=u; u^=v;}
    int k=d[v]-d[u],j=0; while(k){ if(k&1)v=a[v][j]; j++; k>>=1;}
    if(u==v)return u;
    for(int i=lg[d[u]-1];~i;i--)
        if(a[u][i]!=a[v][i]) u=a[u][i],v=a[v][i];
    return a[u][0]; 
}int main(){
    fread(pt,1,21000000,stdin);  
    n=getint();m=getint();
    for(int i=0;(1<<i)<=n;i++)
        for(int j=(1<<i);j<(1<<i+1)&&j<=n;j++)lg[j]=i;
    int u,v,w,a1,a2,a3,a4,a5,An1,An2;
    for(int i=1;i<n;i++) u=getint(),v=getint(),ae(u,v); 
    pre();
    for(int i=1;i<=m;i++){
        u=getint(),v=getint(),w=getint();
        a1=lca(u,v),a2=lca(u,w),a3=lca(v,w),a4=d[u]+d[v]+d[w];
        An1=a1,An2=a4-d[a1]-(d[lca(w,a1)]<<1);
        if((a5=a4-d[a2]-(d[lca(v,a2)]<<1))<An2) An2=a5,An1=a2;
        if((a5=a4-d[a3]-(d[lca(u,a3)]<<1))<An2) An2=a5,An1=a3;
        print(An1);*o++=' ';print(An2);*o++='\n';
    }return fwrite(buf,1,o-buf,stdout),0;
}

第i头牛，可以使用第j个防晒霜的，从j到i连一条容量1的边。

每个防晒霜从S给它连容量为cover[i]的边。

求一遍最大流就好了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10000,maxm=5000000,inf=1000000009;
int p[maxm],c[maxm],n1[maxm],q[maxn],h1[maxn],d[maxn],h[maxn],g[maxn];
int l[3000],r[3000],S,T,n,m,k,tot=0,cnt=0,N=0;  char buf[2000000],*pt=buf;
inline int getint(){    int r=0; while(*pt<48||*pt>57)pt++; 
    while(*pt>47&&*pt<58)r=r*10+*pt++-48; return r;
}inline void ae(int x,int y,int z){
    p[tot]=y;   c[tot]=z;   n1[tot]=h[x];   h[x]=tot++;
    p[tot]=x;   c[tot]=0;   n1[tot]=h[y];   h[y]=tot++;
}inline int bfs(){
    memset(d,0xff,sizeof(d));   int r=d[q[0]=S]=0;
    for(int l=0;l<=r;l++)
        for(int k=h[q[l]];~k;k=n1[k])
            if(c[k] && !~d[p[k]])   d[q[++r]=p[k]]=d[q[l]]+1;
    return ~d[T];
}int dfs(int x=S,int lmt=inf){
    if(x==T)    return lmt; int flow;
    for(int &k=g[x];~k;k=n1[k]){
        if(c[k] && d[p[k]]==d[x]+1 && (flow=dfs(p[k],min(lmt,c[k])))){
            c[k]-=flow; c[k^1]+=flow;   return flow;
        }
    }return 0;
}int main(){
    memset(h,-1,sizeof(h));
    fread(pt,1,2000000,stdin);  n=getint(); m=getint(); S=0; T=n+m+1;
    for(int i=1;i<=n;i++)   l[i]=getint(),r[i]=getint(),ae(m+i,T,1);
    for(int i=1;i<=m;i++){
        int u,v; u=getint(),v=getint();  ae(S,i,v);
        for(int j=1;j<=n;j++) if(l[j]<=u&&u<=r[j]) ae(i,m+j,1);
    }int An=0,f=0;   while(bfs()){   memcpy(g,h,sizeof(h));  while(f=dfs())  An+=f;}
    printf("%d\n",An);    return 0;
} 

观察到n的范围极小，m的范围也才1000000。那就可以枚举答案了。

枚举答案M。满足对于任何(i,j)，都满足C[i]+x*P[i]=C[j]+x*P[j](mod M)的最小正整数解x大于min(L[i],L[j])，或者不存在x。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;ll An=0,c[20],p[20],l[20]; int n;
ll ext_gcd(ll a,ll b,ll&x,ll&y){
    if(!b){ x=1; y=0; return a;}
    ll xx,yy,d=ext_gcd(b,a%b,xx,yy);
    x=yy; y=xx-a/b*yy; return d;
}ll equ(ll a,ll b,ll c){
    ll x,y,d=ext_gcd(a,c,x,y); if(b%d) return -1;
    x*=b/d; while(x>c/d)x-=c/d;
    while(x<0) x+=c/d; return x;
}int check(ll m){
    for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++){
        ll d; if(p[i]>=p[j])d=equ(p[i]-p[j],c[j]-c[i],m);
        else d=equ(p[j]-p[i],c[i]-c[j],m);
        if(d!=-1&&d<=min(l[i],l[j]))return 1;
    }return 0;
}int main(){
    scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&c[i],&p[i],&l[i]),An=max(An,c[i]);
    for(;check(An);An++); printf("%lld\n",An); return 0;
}

二分图。赤果果的费用流。其实是KM。但是不会写。只好写费用流替代了。

先O(n^2)判哪些数对(x,y)可行。然后连边，做最大费用流。

因为每个数只能取一次。那么我把(x,y)和(y,x)都连了一遍。那么结果除以二。

判断选了几对，只要看T点的流量有多少不是从TT流过来的就行了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxm=5000000,inf=1061109567;
int h[10005],p[maxm],c[maxm],cost[maxm],n1[maxm],q[maxm],sp[10005],inq[10005];
int sq[1000005]={0},S,T,TT,An=0,path[maxm],pre[10005],tot=0;
inline void ae(int a,int b,int cc,int co){
    p[tot]=b; c[tot]=cc; cost[tot]=co;  n1[tot]=h[a]; h[a]=tot++;
    p[tot]=a; c[tot]=0;  cost[tot]=-co; n1[tot]=h[b]; h[b]=tot++;
}inline int spfa(){
    memset(sp,63,sizeof(sp));   memset(inq,0,sizeof(inq));
    int head=0,tail=1; sp[S]=0; q[0]=S; inq[S]=1; pre[S]=-1;
    while(head!=tail){
        int u=q[head++]; if(head>=maxm) head-=maxm; inq[u]=0;
        for(int i=h[u];~i;i=n1[i])
            if(c[i]>0&&sp[p[i]]>sp[u]+cost[i]){
                path[p[i]]=i, pre[p[i]]=u, sp[p[i]]=sp[u]+cost[i];
                if(!inq[p[i]]){ inq[p[i]]=1, q[tail++]=p[i]; if(tail>=maxm) tail-=maxm;}
            }
    }return sp[T]!=inf;
}inline int aug(){
    int delta=inf,  flow=0;
    for(int i=T;pre[i]!=-1;i=pre[i]) delta=min(delta,c[path[i]]);
    for(int i=T;pre[i]!=-1;i=pre[i]){
        c[path[i]]-=delta, c[path[i]^1]+=delta;
        flow+=cost[path[i]]*delta;
    }return flow;
}inline int cf(){
    int ret=0; while(spfa()) ret+=aug(); return ret;
}int gcd(int a,int b){
    return (!b)?a:gcd(b,a%b);
}int main(){
    int a,b;    scanf("%d%d",&a,&b);    memset(h,-1,sizeof(h));
    for(int i=1;i<=1000;i++) sq[i*i]=i; S=0;TT=(b-a+1)<<1|1;T=TT+1;
    for(int i=a;i<=b;i++) for(int j=i+1;j<=b;j++)
        if(sq[j*j-i*i]&&gcd(sq[j*j-i*i],i)==1){
            ae(j-a+1,b-a+1+i-a+1,1,-i-j);
            ae(i-a+1,b-a+1+j-a+1,1,-i-j);
        }ae(TT,T,inf,0);
    for(int i=1;i<=b-a+1;i++) ae(S,i,1,0), ae(i,TT,1,0), ae(b-a+1+i,T,1,0);
    int An1,An2=-cf();
    for(int i=h[T];~i;i=n1[i]) if(p[i]==TT)An=b-a+1-c[i];
    printf("%d %d\n",An>>1,An2>>1);  return 0;    
}

正在纠结这类水题有没有写题解的必要？

暴露智商了。囧。我智商-∞岂会轻易告诉你们？

把所有1的点放进队列。bfs。没了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define mp make_pair 
#define qsize 2000000
typedef pair<int,int> pii; pii q[qsize];
int head=0,tail=0,n,m,d[1005][1005];    char s[1005];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int main(){
    scanf("%d%d",&n,&m);    memset(d,63,sizeof(d));
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=m;j++) if(s[j]-'0') q[tail++]=mp(i,j), d[i][j]=0;
    }while(head!=tail){
        pii u=q[head++]; if(head>=qsize) head-=qsize;
        for(int k=0;k<4;k++){
            int xx=u.first+dx[k],yy=u.second+dy[k];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&d[u.first][u.second]+1<d[xx][yy]){
                d[xx][yy]=d[u.first][u.second]+1;
                q[tail++]=mp(xx,yy); if(tail>=qsize) tail-=qsize;
            }
        }
    }for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) printf("%d ",d[i][j]);
        printf("\n");
    }return 0;
}

题意：给一个字符串。输出在原串中出现次数大于1的子串的出现次数。这些本质不同的子串按字典序大小排序输出次数。

一眼题？嗯。、后缀数组就行了、根据sa数组和height数组扫一遍。前后扫height数组。

反正n≤3000，没必要二分了。还要写rmq啥的多麻烦啊是吧、、然后就行了、感觉跑的蛮快的？

第一次加了fread和fwrite还变慢了、、

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=2000005;
int tmp1[maxn],tmp2[maxn],cs[maxn],cv[maxn],rank[maxn],height[maxn],sa[maxn];
char s[maxn],str[maxn];
inline bool cmp(int *r,int a,int b,int l){
    return  r[a]==r[b] && r[a+l]==r[b+l];
}inline void da(char *r,int *sa,int n,int m){
    int i,j,p,*x=tmp1,*y=tmp2,*t;
    for(i=0;i<m;i++)cs[i]=0;
    for(i=0;i<n;i++)cs[x[i]=r[i]]++;
    for(i=1;i<m;i++)cs[i]+=cs[i-1];
    for(i=n-1;i>=0;i--)sa[--cs[x[i]]]=i;
    for(j=1,p=1;p<n;j<<=1,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<n;i++)cv[i]=x[y[i]];
        for(i=0;i<m;i++)cs[i]=0;
        for(i=0;i<n;i++)cs[cv[i]]++;
        for(i=1;i<m;i++)cs[i]+=cs[i-1];
        for(i=n-1;i>=0;i--)sa[--cs[cv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
}inline void ch(char *r,int n){
    int i,j,k=0;
    for(i=0;i<n;i++)rank[sa[i]]=i;
    for(i=0;i<n;height[rank[i++]]=k)
        for(k=max(k-1,0),j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}int main(){
    int n;  scanf("%d%s",&n,str);
    for(int i=0;i<n;i++)str[i]++;   str[n++]=0;
    da(str,sa,n,256);   ch(str,n);
    for(int i=1;i<n;i++){
        for(int j=height[i]+1;sa[i]+j<n;j++){
            int l,r;
            for(l=i;l>=0 && height[l]>=j;l--);
            for(r=i+1;r<=n && height[r]>=j;r++);
            if(r-l<=1)continue;
            printf("%d\n",r-l);
        }
    }return 0;
}

煞笔的煞笔又来发水题题解了！

二分答案。先判一级公路然后判二级公路。没了。

1A什么的不必多说。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct E{ int u,v,c1,c2;}e[20005];
inline bool C(E a,E b){ return a.c1<b.c1;}
int F[10005],n,k,m; char buf[2000000],*pt=buf;
int GF(int x){  return x==F[x]?x:F[x]=GF(F[x]);}
inline int getint(){ 
    int r=0;while(*pt<'0'||*pt>'9')pt++;while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline int ok(int lmt){
    int ck=0,ca=0;
    for(int i=1;i<=n;i++) F[i]=i;
    for(int i=1;i<=m;i++){
        if(e[i].c1<=lmt){
            int u=GF(e[i].u),v=GF(e[i].v);
            if(u!=v) F[u]=v,ck++,ca++;
            if(ca==n-1) return 1;
        }else{
            if(ck<k) return 0;
            if(min(e[i].c1,e[i].c2)>lmt) continue;
            int u=GF(e[i].u),v=GF(e[i].v);
            if(u!=v) F[u]=v,ca++;
            if(ca==n-1) return 1;
        }
    }return 0;
}int main(){
    fread(pt,1,2000000,stdin);  int i;
    for(n=getint(),k=getint(),m=getint(),i=1;i<m;i++)
        e[i].u=getint(),e[i].v=getint(),e[i].c1=getint(),e[i].c2=getint();
    sort(e+1,e+m+1,C);  int l=0,r=1000000009,mid;
    while(l<=r){
        mid=l+r>>1;
        if(ok(mid)) r=mid-1;    else    l=mid+1;
    }printf("%d\n",l);return 0;
}