闲扯
今天 (T1) 做的简直麻瓜，莫名其妙的开了 (10^6) 个 (string) ，直接爆炸，之前写的 (hash) 把它删了？？？？
(T2) 写完发现自己好像出锅了，但是懒得改了，准备看运气，还是有个 (10) 分，还不错吧。。
(T3) 打暴力都弄错了，真是不用混了呀。。
题面
(T1)
Solution
我们可以发现所有可以和源头基因匹配的子串一定是以字符串的第一个字符开头的，所以我们只用找到对于每一个和 (s_1) 相同的位置为开头，一共能拓展多少子串，然后求和即可。
显然，它能拓展的子串个数一定是等于它向后拓展的最大长度，所以我们只需要找到这个值即可。
先将字符串 (hash) 一下，对于每一个合法点，我们用二分法找出拓展的长度，直接累加答案即可。
Code
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
int f=1;char k=getchar();x=0;
for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
x*=f;
}
template<class T>il print(T x){
if(x/10) print(x/10);
putchar(x%10+'0');
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
int res=1,bas=x%mod;
while(m){
if(m&1) res=(res*bas)%mod;
bas=(bas*bas)%mod,m>>=1;
}
return res%mod;
}
const int MAXN = 1e6+5,mod = 131;
ll ans,len;
unsigned ll H[MAXN],p[MAXN];
char s[MAXN];
it solve(int pos){
int l=1,r=len-pos+1;
while(l<=r){
if(H[pos-1]*p[mid]+H[mid]==H[pos+mid-1]) l=mid+1;
else r=mid-1;
}
return mid;
}
int main()
{
freopen("gene.in","r",stdin);
freopen("gene.out","w",stdout);
scanf("%s",s+1),len=strlen(s+1),ans=len,p[0]=1;
for(ri i=1;i<=len;++i) H[i]=H[i-1]*mod+(s[i]-'a'+1),p[i]=p[i-1]*mod;
for(ri i=2;i<=len;++i) if(s[i]==s[1]) ans+=solve(i);
print(ans);
return 0;
}
T2
Solution
这道题相当于选一个点然后沿着所给的方向一直找，找到一条经过点最多的路径。
我们可以先变换一下坐标系，令 (x) 轴为其中一条向量 ((x_1,y_1)) ， (y) 轴为另外一条向量 ((x_2,y_2)) 。
然后用这两个向量去合成原题中所给出的点 ((x,y)) ，列出方程 (x^{'}*(x_1,y_1)+y^{'}*(x_2,y_2)=(x,y)) 。
则有 (x^{'}*x_1+y^{'}*x_2=x,x^{'}*y_1+y^{'}*y_2=y) 。
所以我们可以解出 ((x^{'},y^{'})) ，这就是变换坐标系之后的坐标。
这是我们可以认为“所给方向”这个限制条件已经没有了，变成了向右上角方向找一条最长的路径，也就是说我们要找一个最长的序列，使序列中所有点的 (x^{'}) 和 (y^{'}) 单调不降。
这一步可以用树状数组解决。
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define N 200010
using namespace std;
long long X[N],Y[N];
struct ppp{int x,y;}b[N];
bool cmp(ppp x,ppp y)
{
if(x.x!=y.x) return x.x<y.x;
return x.y<y.y;
}
long long ax[N],ay[N];
int ans[N];
int nx,ny;
long long X1,X2,Y1,Y2;
int c[N],n;
void change(int x,int v)
{
for(;x<=n;x+=x&-x)
c[x]=max(c[x],v);
}
int check(int x)
{
int ret=0;
for(;x;x-=x&-x)
ret=max(ret,c[x]);
return ret;
}
int main()
{
freopen("sheild.in","r",stdin);
freopen("sheild.out","w",stdout);
scanf("%d%lld%lld%lld%lld",&n,&X1,&Y1,&X2,&Y2);
long long x,y;
long long tmp=1;
//if(X1*Y2-Y1*X2==0) puts("QAQ");
if(X1*Y2-Y1*X2<0) tmp=-1;
int i,j;
for(i=1;i<=n;i++)
{
scanf("%lld%lld",&x,&y);
ax[i]=X[i]=tmp*(x*Y2-y*X2);
ay[i]=Y[i]=tmp*(y*X1-x*Y1);
}
sort(ax+1,ax+n+1);
sort(ay+1,ay+n+1);
int sx=unique(ax+1,ax+n+1)-ax;
int sy=unique(ay+1,ay+n+1)-ay;
for (int i = 1; i <= n; i ++)
{
int u=lower_bound(ax+1,ax+sx,X[i])-ax;
int v=lower_bound(ay+1,ay+sy,Y[i])-ay;
b[i].x=u,b[i].y=v;
}
sort(b+1,b+n+1,cmp);
for(i=1;i<=n;i++)
change(b[i].y,check(b[i].y)+1);
printf("%d",check(n));
}
(T3)
Solution
首先可以建出源汇点 (S,T) ,源点向所有点连边,所有点向汇点连边.
问题转化为最小化删去一个点后 (S→T) 的最长路长度.
拓扑排序 + (dp) 处理出 (f(i),g(i)) 分别表示 (S→i) 的最长链与 (i→T) 的最长链经过的点数.
那么对于一条边 (u→v) ,它的的贡献就是 (f(u)+g(v)−1) .
若有一个 (S→T) 的割,那么所有 (S→T) 路径一定会经过至少一条割集中的边,只需要考虑割集中的边贡献.
一开始让 (s) 集只有 (S) , (T) 集包含剩余的所有点,这是一个合法的割.
按照拓扑序枚举删掉 (x) 后的答案,依次进行如下操作,以将点 (x) 从 (T) 集合中取出,放入 (S) 集中.
-
将 (x) 的所有入边从割集中删掉.
-
所有割集的边的最大贡献就是删掉点 (x) 的答案.
-
将 (x) 的所有出边加入割集.
正确性可以利用数学归纳法证明.
执行第 (1) 步之前,割是整张图的一个割,假设它不含从 (x) 出发能到的任何边.
所以删掉 (x) 的入边后,割就是去掉 (x) 的图的一个合法割,此时可以更新答案.
若将 (x) 放回图中, (S→T) 的路径就一定经过 (x) ,所以割掉 (x) 的所有出边,又成了一个合法割.
因为是按照拓扑序依次处理的,所以加入的 (x) 的入边在之后一定不能被到达,满足了先前的假设.
而初始状态也是满足假设的,所以可以归纳证得以上算法的正确性.
割集只需要记录边的贡献,不记录边的编号,所以可以用一棵权值线段树进行维护,时间复杂度 (O(mlogm)) .
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define N 2000010
using namespace std;
int du[N];
int q[N],h,t;
int w[N];
struct ljb
{
int fr[N],to[N],nxt[N],pre[N>>2],dis[N>>2],du[N>>2],cnt;
void ae(int ff,int tt)
{
cnt++;
fr[cnt]=ff;
to[cnt]=tt;
nxt[cnt]=pre[ff];
pre[ff]=cnt;
}
void solve(int s)
{
memset(dis,0,sizeof(dis));
h=1;t=1;
q[1]=s;dis[s]=0;
int i,j,x,y;
while(h<=t)
{
x=q[h];h++;
for(i=pre[x];i;i=nxt[i])
{
j=to[i];
dis[j]=max(dis[j],dis[x]+1);
du[j]--;
if(!du[j]) t++,q[t]=j;
}
}
}
}z,f;
struct heap
{
priority_queue<int>p,q;
void del(int x)
{
q.push(x);
while(!p.empty()&&!q.empty()&&q.top()==p.top())
{
q.pop();
p.pop();
}
}
void add(int x){p.push(x);}
int max(){return p.top();}
};
int main()
{
freopen("chronosphere.in","r",stdin);
freopen("chronosphere.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
int i,j,x,y;
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
du[y]++;z.du[y]++;f.du[x]++;
z.ae(x,y);f.ae(y,x);
}
for(i=1;i<=n;i++)
{
du[i]++;du[n+1]++;
z.du[i]++;z.du[n+1]++;
f.du[i]++;f.du[0]++;
z.ae(0,i);f.ae(i,0);
z.ae(i,n+1);f.ae(n+1,i);
}
z.solve(0);
f.solve(n+1);
for(i=1;i<=m+2*n;i++)
w[i]=z.dis[z.fr[i]]+f.dis[z.to[i]]-1;
heap p;
h=t=1;q[1]=0;
int minn=707185547,ans;
while(h<=t)
{
x=q[h];h++;
for(i=f.pre[x];i;i=f.nxt[i])
p.del(w[i]);
if(x!=0&&x!=n+1)
{
y=p.max();
if(y<minn) minn=y,ans=x;
else if(y==minn&&ans>x) ans=x;
}
for(i=z.pre[x];i;i=z.nxt[i])
{
j=z.to[i];
p.add(w[i]);
du[j]--;
if(!du[j]) t++,q[t]=j;
}
}
printf("%d %d",ans,minn);
}
总结
字符串还是我的弱项之一啊虽然我好像有一摩尔弱项，还有对问题的转换不太精通，需要加强。