差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:wangzai_milk:20200712比赛记录 [2020/07/15 00:42]
infinity37
+++ 2020-2021:teams:wangzai_milk:20200712比赛记录 [2020/07/16 15:15] (当前版本)
wzx27
@@ 行 77: / 行 77: @@
         get_sa(n+1,n+2),get_height(n+1);
         for(int i=n;i;i--)printf("%d ",1+sa[i]);
+        puts("");
+    }
+    return 0;
+}
+</code></hidden>
+\\
+但我感觉这岂不是很难想到吗，，，？于是再给一个我觉得更有迹可循的做法qaq
+手玩一下就可以发现每个 $B$ 串可以分为 $AD$ 两部分， $A=011\ldots 110$ ，即从第一个字符到另一个字符第一次出现，而其余的是 $D$ 部分，不会随着所取的后缀位置改变。为得到 $D$ 的排名对整个字符串的 $B$ 求后缀数组， $A$ 部分长度越长字典序越大。sort一下，先比较 $|A_i|$ 再比较 $rk[i+|A_i|]$ 即可。
+<hidden><code cpp>
+#include<bits/stdc++.h>
+#define INF 0x3f3f3f3f
+#define ll long long
+using namespace std;
+const int N=1e5+10;
+char str[N];
+int s[N],sa[N],rk[N],t[N],c[N],height[N],A[N],p[N];
+void get_sa(int n,int m)
+{
+    s[n++]=0;
+    int *x=rk,*y=t,i,k,num;
+    for(i=0;i<m;i++)c[i]=0;
+    for(i=0;i<n;i++)c[x[i]=s[i]]++;
+    for(i=0;i<m;i++)c[i]+=c[i-1];
+    for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
+    for(k=1,num=1;num<n;k<<=1,m=num)
+    {
+        for(num=0,i=n-k;i<n;i++)y[num++]=i;
+        for(i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
+        for(i=0;i<m;i++)c[i]=0;
+        for(i=0;i<n;i++)c[x[y[i]]]++;
+        for(i=0;i<m;i++)c[i]+=c[i-1];
+        for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
+        for(swap(x,y),i=num=1,x[sa[0]]=0;i<n;i++)
+        x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num-1:num++;
+    }
+}
+void get_height(int n)
+{
+    int i,j,k=0;
+    for(i=1;i<=n;i++)rk[sa[i]]=i;
+    for(i=0;i<n;height[rk[i++]]=k)
+    for(k=k?k-1:k,j=sa[rk[i]-1];s[i+k]==s[j+k];k++);
+    return;
+}
+bool cmp(int x,int y)
+{
+    if(A[x]==A[y])return rk[x+A[x]]<rk[y+A[y]];
+    else return A[x]<A[y];
+}
+int main()
+{
+    int n;
+    while(~scanf("%d%s",&n,str))
+    {
+        int a=-1,b=-1;
+        for(int i=0;str[i];i++)
+        {
+            if(str[i]=='a')s[i]=(a==-1)?0:i-a,a=i;
+            else s[i]=(b==-1)?0:i-b,b=i;
+        }
+        get_sa(n,n+1),get_height(n);
+        a=n,b=n;
+        for(int i=n-1;i>=0;i--)
+        {
+            if(str[i]=='a')a=i;else b=i;
+            int la=a,lb=b;
+            if(la>lb)swap(la,lb);
+            A[i]=lb-la+1;
+        }
+        for(int i=0;i<n;i++)p[i]=i;
+        rk[n]=-1,rk[n+1]=-2;
+        sort(p,p+n,cmp);
+        for(int i=0;i<n;i++)printf("%d ",p[i]+1);
         puts("");
     }
@@ 行 94: / 行 170: @@
 {{:2020-2021:teams:wangzai_milk:循环小数法比较字符串.png?450|}}
 ==== I - 1 or 2 ====
+我居然会过带花树.jpg
+题意：给定一个无向图，给定点的度数限制，想要你选择其中一些边使得度数限制被满足。度数只可能是1或2。
+如果度数是1的话那么就是普通的一般图匹配，那么自然的想到对度数是2的拆点，普通的拆点可能会导致某条边被重复使用，那么解决方案就是对一条边新建两个新点，然后原来普通的拆点分别向这个边的两个新点连边，就可以保证这条边只被使用一次。
 <hidden><code cpp>
 #include <stdio.h>
@@ 行 234: / 行 316: @@
 </code></hidden>
 \\
+==== H - Minimum-cost Flow ====
+费用流建图，每条边的费用已知，容量在每次询问时给出，每次询问求流出 $1$ 单位的最小费用。
+可以先假设每条边容量为 $1$ ，每次给出具体容量时再做调整。
+具体做的时候不知道哪里被卡了一直 $t$ ，改了很久才过(快读+dij费用流)。
+<hidden code> <code cpp>
+#pragma GCC optimize(3,"Ofast","inline")
+#include<bits/stdc++.h>
+#define ALL(x) (x).begin(),(x).end()
+#define ll long long
+#define ull unsigned long long
+#define pii_ pair<int,int>
+#define mp_ make_pair
+#define pb push_back
+#define fi first
+#define se second
+#define rep(i,a,b) for(int i=(a);i<=(b);i++)
+#define per(i,a,b) for(int i=(a);i>=(b);i--)
+#define show1(a) cout<<#a<<" = "<<a<<endl
+#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
+using namespace std;
+const ll INF = 1LL<<60;
+const int inf = 1<<30;
+const int maxn = 2005;
+inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
+inline int read(){
+   int s=0,w=1;
+   char ch=getchar();
+   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
+   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
+   return s*w;
+}
+ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
+ll sum[maxn];
+int n,m,q,num;
+int head[maxn],dis[maxn],h[maxn],PrePoint[maxn],PreEdge[maxn];
+vector<int> mcost;
+struct node
+{
+    int u,v,f,w,nxt;
+}edge[maxn];
+inline void addedge(int x,int y,int f,int z)
+{
+    edge[num].u=x;
+    edge[num].v=y;
+    edge[num].f=f;
+    edge[num].w=z;
+    edge[num].nxt=head[x];
+    head[x]=num++;
+}
+void add(int u,int v,int w,int c)
+{
+    addedge(u,v,w,c);
+    addedge(v,u,0,-c);
+}
+int MCMF(int s,int t)
+{
+    int ansflow=0;
+    rep(i,1,n) h[i] = 0;
+    while(1)
+    {
+        priority_queue<pii_>q;
+        rep(i,1,n) dis[i] = inf;
+        dis[s]=0;
+        q.push(make_pair(0,s));
+        while(q.size()!=0)
+        {
+            pii_ p=q.top();q.pop();
+            if(-p.fi!=dis[p.se]) continue;
+            if(p.se==t) break;
+            for(int i=head[p.se];i!=-1;i=edge[i].nxt)
+            {
+                int nowcost=edge[i].w+h[p.se]-h[edge[i].v];
+                if(edge[i].f>0&&dis[edge[i].v]>dis[p.se]+nowcost)
+                {
+                    dis[edge[i].v]=dis[p.se]+nowcost;
+                    q.push(make_pair(-dis[edge[i].v],edge[i].v));
+                    PrePoint[edge[i].v]=p.se;
+                    PreEdge[edge[i].v]=i;
+                }
+            }
+        }
+        if(dis[t]==inf) break;
+        for(int i=1;i<=n;i++) h[i]+=dis[i];
+        int nowflow=inf;
+        for(int now=t;now!=s;now=PrePoint[now])
+            nowflow=min(nowflow,edge[PreEdge[now]].f);
+        for(int now=t;now!=s;now=PrePoint[now])
+            edge[PreEdge[now]].f-=nowflow,
+            edge[PreEdge[now]^1].f+=nowflow;
+        ansflow+=nowflow;
+        mcost.pb(h[t]);
+    }
+    return ansflow;;
+}
+int main()
+{
+    //fastio();
+    ll u,v,c;
+    while(~scanf("%d%d",&n,&m)){
+        rep(i,1,n) head[i] = -1;
+        num = 2;
+        mcost.clear();
+        int s = 1,t = n;
+        rep(i,1,m){
+            u = read();
+            v = read();
+            c = read();
+            add(u,v,1,c);
+        }
+        int maxflow = MCMF(s,t);
+        sort(ALL(mcost));
+        //for(int x:mcost) show1(x);
+        int sz = mcost.size();
+        rep(i,1,sz) sum[i] = sum[i-1] + mcost[i-1];
+        int q = read();
+        while(q--){
+            u = read();v = read();
+            if(u*maxflow<v) printf("NaN\n");
+            else{
+                int L = 1,R = sz,pos;
+                while(L<=R){
+                    int mid = (L+R)>>1;
+                    if(u*mid >= v) pos = mid,R=mid-1;
+                    else L = mid+1;
+                } //show1(pos);
+                ll a = u*sum[pos-1];
+                ll o = (v-u*(pos-1)) * (sum[pos] - sum[pos-1]); //show2(a,o);
+                a = a+o;
+                ll g = gcd(a,v);
+                a /= g, v /= g;
+                printf("%lld/%lld\n",a,v);
+            }
+        }
+    }
+    return 0;
+}
+</code> <hidden>
+\\
 ==== J - Easy Integration ====

CVBB ACM Team

用户工具

站点工具

差别

页面工具