差别

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

--- 2020-2021:teams:namespace:牛客多校第一场 [2020/07/16 09:31]
great_designer [J]
+++ 2020-2021:teams:namespace:牛客多校第一场 [2020/07/17 17:17] (当前版本)
serein [J]
@@ 行 170: / 行 170: @@
 后来得知的一个结论是，对于两个循环字符串字典序比较，s循环大于t循环，等价于st大于ts。这可真是有趣的结论，大概比这个暴力算法更优吧。
+没错，把字符串的循环类比为26进制的无限循环小数，很nice的解法。
 =====I=====
@@ 行 461: / 行 465: @@
 </code>
 </hidden>
+贴一下标程的做法。
+<code>
+static inline int inv(int a) {
+  return a == 1 ? 1 : MOD - 1LL * (MOD / a) * inv(MOD % a) % MOD;
+}
+//求数论倒数的函数并使用内联提高运行效率
+</code>
 =====A=====
 从这里以下是补题的部分。
+题目：定义字符串到字符串的映射F，第i位为字符串t第i位ti，到前面相同字符的距离，若没有则为0。
+给出两元素a,b组成的长为n的串t，要回答其所有后缀作用F后字典序的排列。
+标程定理：对于只有两元的串，这里的F和G等价。
+G仅将“到前面相同字符的距离，若没有则为0”改为“到后面相同字符的距离，若没有则为n，并且在末端补充n+1”。
+总之是神奇字符串结论。先记下来。
+<hidden>
+<code C>
+#include<stdio.h>
+char str[100010];
+int s[100010],sa[100010],rk[100010],t[100010],c[100010],height[100010];
+void getsa(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--)
+	{
+		--c[x[i]];
+		sa[c[x[i]]]=i;
+	}
+    for(k=1,num=1;num<n;k<<=1,m=num)
+    {
+    	num=0;
+        for(i=n-k;i<n;i++)
+		{
+			y[num]=i;
+			num++;
+		}
+        for(i=0;i<n;i++)
+		{
+			if(sa[i]>=k)
+			{
+				y[num]=sa[i]-k;
+				num++;
+			}
+		}
+        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--)
+		{
+			--c[x[y[i]]];
+			sa[c[x[y[i]]]]=y[i];
+		}
+		int *temp=x;
+		x=y;
+		y=temp;
+		x[sa[0]]=0;
+		num=1;
+        for(i=1;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 getheight(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)
+    {
+    	j=sa[rk[i]-1];
+    	k=k?k-1:k;
+    	while(s[i+k]==s[j+k])
+    	{
+    		k++;
+		}
+	}
+    return;
+}
+int main()
+{
+    int n;
+    while(~scanf("%d%s",&n,str))
+    {
+        s[n]=n+1;
+        int a=n+1,b=n+1;
+        int i;
+        for(i=n-1;i>=0;i--)
+        {
+            if(str[i]=='a')
+			{
+				s[i]=(a==n+1)?n:a-i;
+				a=i;
+			}
+            else
+			{
+				s[i]=(b==n+1)?n:b-i;
+				b=i;
+			}
+        }
+        getsa(n+1,n+2);
+		getheight(n+1);
+        for(i=n;i;i--)
+		{
+			printf("%d ",1+sa[i]);
+		}
+        puts("");
+    }
+    return 0;
+}
+</code>
+</hidden>
+=====H=====
+快速读入与费用流。
+每条边的费用已知，容量在每次询问时给出，每次询问求流出1单位的最小费用。
+可以先假设每条边容量为1，每次给出具体容量时再做调整。
+<hidden>
+<code C++>
+#include<stdio.h>
+#include<algorithm>
+#include<vector>
+#include<queue>
+using namespace std;
+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;
+}
+long long gcd(long long a,long long b)
+{
+	return b==0?a:gcd(b,a%b);
+}
+long long sum[2005];
+int n,m,q,num;
+int head[2005],dis[2005],h[2005],PrePoint[2005],PreEdge[2005];
+vector<int> mcost;
+struct node
+{
+    int u,v,f,w,nxt;
+};
+struct node edge[2005];
+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;
+    int i;
+    for(i=1;i<=n;i++)
+	{
+		h[i] = 0;
+	}
+    while(1)
+    {
+        priority_queue<pair<int,int> >q;
+        for(i=1;i<=n;i++)
+		{
+			dis[i] = 1<<30;
+		}
+        dis[s]=0;
+        q.push(make_pair(0,s));
+        while(q.size()!=0)
+        {
+            pair<int,int> p=q.top();
+			q.pop();
+            if(-p.first!=dis[p.second])
+			{
+				continue;
+			}
+            if(p.second==t)
+			{
+				break;
+			}
+            for(i=head[p.second];i!=-1;i=edge[i].nxt)
+            {
+                int nowcost=edge[i].w+h[p.second]-h[edge[i].v];
+                if(edge[i].f>0&&dis[edge[i].v]>dis[p.second]+nowcost)
+                {
+                    dis[edge[i].v]=dis[p.second]+nowcost;
+                    q.push(make_pair(-dis[edge[i].v],edge[i].v));
+                    PrePoint[edge[i].v]=p.second;
+                    PreEdge[edge[i].v]=i;
+                }
+            }
+        }
+        if(dis[t]==1<<30)
+		{
+			break;
+		}
+        for(i=1;i<=n;i++)
+		{
+			h[i]+=dis[i];
+		}
+        int nowflow=1<<30;
+        int now;
+        for(now=t;now!=s;now=PrePoint[now])
+        {
+        	nowflow=min(nowflow,edge[PreEdge[now]].f);
+		}
+        for(now=t;now!=s;now=PrePoint[now])
+        {
+        	edge[PreEdge[now]].f-=nowflow;
+            edge[PreEdge[now]^1].f+=nowflow;
+		}
+        ansflow+=nowflow;
+        mcost.push_back(h[t]);
+    }
+    return ansflow;
+}
+int main()
+{
+    long long u,v,c;
+    while(~scanf("%d%d",&n,&m))
+	{
+		int i;
+        for(i=1;i<=n;i++)
+		{
+			head[i] = -1;
+		}
+        num = 2;
+        mcost.clear();
+        int s = 1,t = n;
+        for(i=1;i<=m;i++)
+		{
+            u = read();
+            v = read();
+            c = read();
+            add(u,v,1,c);
+        }
+        int maxflow = MCMF(s,t);
+        sort(mcost.begin(),mcost.end());
+        int sz = mcost.size();
+        for(i=1;i<=sz;i++)
+		{
+			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;
+					}
+                }
+                long long a = u*sum[pos-1];
+                long long o = (v-u*(pos-1)) * (sum[pos] - sum[pos-1]);
+                a = a+o;
+                long long g = gcd(a,v);
+                a /= g;
+				v /= g;
+                printf("%lld/%lld\n",a,v);
+            }
+        }
+    }
+    return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具