这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
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> |