用户工具

站点工具


2020-2021:teams:wangzai_milk:20200712比赛记录

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版
前一修订版
2020-2021:teams:wangzai_milk:20200712比赛记录 [2020/07/15 00:27]
zars19 [F - Infinite String Comparision]
2020-2021:teams:wangzai_milk:20200712比赛记录 [2020/07/16 15:15] (当前版本)
wzx27
行 77: 行 77:
         get_sa(n+1,​n+2),​get_height(n+1);​         get_sa(n+1,​n+2),​get_height(n+1);​
         for(int i=n;​i;​i--)printf("​%d ",​1+sa[i]);​         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(""​);​         puts(""​);​
     }     }
行 93: 行 169:
  
 {{:​2020-2021:​teams:​wangzai_milk:​循环小数法比较字符串.png?​450|}} {{:​2020-2021:​teams:​wangzai_milk:​循环小数法比较字符串.png?​450|}}
 +==== I - 1 or 2 ====
 +我居然会过带花树.jpg
 +
 +题意:给定一个无向图,给定点的度数限制,想要你选择其中一些边使得度数限制被满足。度数只可能是1或2。
 +
 +如果度数是1的话那么就是普通的一般图匹配,那么自然的想到对度数是2的拆点,普通的拆点可能会导致某条边被重复使用,那么解决方案就是对一条边新建两个新点,然后原来普通的拆点分别向这个边的两个新点连边,就可以保证这条边只被使用一次。
 +
 +<​hidden><​code cpp>
 +#include <​stdio.h>​
 +#include <​queue>​
 +#include <​string.h>​
 +#include <​stdlib.h>​
 +#include <​algorithm>​
 +using namespace std;
 +const int N = 305;
 +const int M = 90005;
 +struct E
 +{int next,​to;​}e[M];​
 +int head[N],​tot;​
 +void add(int x,int y)
 +{
 +    e[++tot].to = y;​e[tot].next = head[x];​head[x]=tot;​
 +    e[++tot].to = x;​e[tot].next = head[y];​head[y]=tot;​
 +}
 +int nxt[N],​pre[N],​fa[N],​v[N],​s[N],​n,​m;​
 +int getfa(int x)
 +{
 +    if(fa[x]==x)return fa[x];
 +    else return fa[x]=getfa(fa[x]);​
 +}
 +queue<​int>​Q;​
 +int getlca(int x,int y)
 +{
 +    static int times=0;
 +    ++times;
 +    x = getfa(x),​y=getfa(y);​
 +    for(;;​swap(x,​y))
 +    if(x)
 +    {
 +        if(v[x]==times)
 +            return x;
 +        v[x] = times;
 +        x = getfa(pre[nxt[x]]);​
 +    }
 +}
 +void blossom(int x,int y,int lca)
 +{
 +    while(getfa(x)!=lca)
 +    {
 +        pre[x]=y;
 +        y=nxt[x];
 +        if(s[y]==1)
 +            Q.push(y),​s[y]=0;​
 +        if(fa[x]==x)
 +            fa[x]=lca;
 +        if(fa[y]==y)
 +            fa[y]=lca;
 +        x=pre[y];
 +    }
 +}
 +bool get_partner(int x)
 +{
 +    for(int i=0;​i<​=n;​i++)
 +        fa[i]=i,​s[i]=-1;​
 +    while(!Q.empty())
 +        Q.pop();
 +    Q.push(x);
 +    s[x] = 0;
 +    while(!Q.empty())
 +    {
 +        int x= Q.front();
 +        Q.pop();
 +        for(int i = head[x];​i;​i=e[i].next)
 +        {
 +            if(s[e[i].to]==-1)
 +            {
 +                s[e[i].to]=1;​
 +                pre[e[i].to]=x;​
 +                if(!nxt[e[i].to])
 +                {
 +                    for(int u=e[i].to,v = x,​last;​v;​u=last,​v=pre[u])
 +                        last = nxt[v],​nxt[v]=u,​nxt[u]=v;​
 +                    return true;
 +                }
 +                Q.push(nxt[e[i].to]);​
 +                s[nxt[e[i].to]]=0;​
 +            }else if(s[e[i].to]==0&&​getfa(e[i].to)!=getfa(x))
 +            {
 +                int l = getlca(e[i].to,​x);​
 +                blossom(x,​e[i].to,​l);​
 +                blossom(e[i].to,​x,​l);​
 +            }
 +        }
 +    }
 +    return false;
 +}
 +int d[N];
 +int x[N],y[N];
 +int no[N][3];
 +int main()
 +{
 +    while (scanf("​%d%d",&​n,&​m)!=EOF) {
 +        for (int i = 1;i<= n;i++)
 +            scanf("​%d",&​d[i]);​
 +        for(int i = 1;i<= m;i++)
 +            scanf("​%d%d",&​x[i],&​y[i]);​
 +        int nn = 0;
 +        for (int i = 1;i<= n;i++)
 +            for (int j = 1;j<= d[i];j++)
 +                no[i][j] = ++nn;
 +        for (int i = 1;i<= m;i++)
 +        {
 +            for (int j = 1;j<= d[x[i]];​j++)
 +                add(nn+1,​no[x[i]][j]);​
 +            for (int j = 1;j<= d[y[i]];​j++)
 +                add(nn+2,​no[y[i]][j]);​
 +            add(nn+1,​nn+2);​
 +            nn+=2;
 +        }
 +        n = nn;
 +        for (int i = 1;i<= n;i++)
 +            nxt[i] = 0;
 +        for(int i = n;i;i--)
 +            if(!nxt[i])
 +                get_partner(i);​
 +        int cnt = 0;
 +        for (int i = 1;i<= n;i++)
 +            if (nxt[i])
 +                cnt++;
 +        /​*printf("​%d\n",​ans);​
 +        for(int i = 1;i<= n;i++)
 +            printf("​%d ",​next[i]);​
 +        printf("​\n"​);​*/​
 +        if (cnt == n)
 +            printf("​Yes\n"​);​
 +        else printf("​No\n"​);​
 +        for (int i = 0;i< N;i++)
 +        {
 +            pre[i] = fa[i] = nxt[i] = head[i] = v[i] = s[i] = 0;
 +            d[i] = x[i] = y[i] = no[i][1] = no[i][2] = 0;
 +        }
 +        tot = 0;
 +    }
 +    return 0;
 +}
 +</​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 ==== ==== J - Easy Integration ====
  
- ​$\int_0^1(x−x^2)^ndx=\frac{(n!)^2}{(2n+1)!}$ 。可以~~oeis/​wolframalpha~~分部积分。+ ​$\int_0^1(x−x^2)^ndx=\frac{(n!)^2}{(2n+1)!}$ 。可以//oeis/​wolframalpha/分部积分//
  
 <​hidden><​code cpp> <​hidden><​code cpp>
2020-2021/teams/wangzai_milk/20200712比赛记录.1594744058.txt.gz · 最后更改: 2020/07/15 00:27 由 zars19