10.1 noip 模拟赛
目录\(\to \rm link \leftarrow\)
\(\rm T1\) 猜道路
先想到看能不能继续进行松弛，如果可以就输出 \(\rm -1\)，这个跑一遍 \(\rm floyd\)。
然后就想到如果已经松弛完了那么 \(\rm A_{i,j}\) 要么是一条直接从 \(\rm i\to j\) 的边，要么是一条经过 \(\rm floyd\) 中转的边，那么就跑一遍 \(\rm floyd\) 看看每条边能不能被中转即可。
时间复杂度 \(\rm O(n^3)\)。
#include<bits/stdc++.h>
using namespace std;
const int N=305;
#define emp emplace_back
#define ll long long
struct E{
int x,y,d;
E(int a,int b,int c){x=a,y=b,d=c;}
inline bool operator <(const E a) const{
return d<a.d;
}
};
int n;
int f[N][N],A[N][N],B[N][N];
bool mp[N][N];
ll ans;
vector <E> p;
signed main(){
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
scanf("%d",&A[i][j]),B[i][j]=A[i][j];
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
if(i==j||i==k||j==k) continue;
B[i][j]=min(B[i][j],B[i][k]+B[k][j]);
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(A[i][j]!=B[i][j]){
puts("-1");
return 0;
}
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
if(i==j||i==k||j==k) continue;
if(A[i][j]==A[i][k]+A[k][j]) mp[i][j]=1;
}
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
if(!mp[i][j])
ans+=A[i][j];
printf("%lld\n",ans);
}
\(\rm T2\) 简单环
\(\rm CF\) 原题，但是数据锅了，差评。
很容易想到 \(\rm tarjan\)，但究竟要用哪种呢？
由于每个点只能过一次，所以是点双。
跑完点双之后对每个点双内的边数进行统计，容易发现当点双内边数 \(\rm =\) 点数时，里面的边才是可行的，因为少了就构成不了环，多了就会构成至少 \(3\) 个环导致每边都至少被遍历两次。
时间复杂度 \(\rm O(n+m\log m)\)。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
#define emp emplace_back
struct E{
int x,y;
E(int a,int b){x=a,y=b;}
};
int n,m,cnt,col,tot,cnm;
bool flag=0;
int dfn[N],low[N],c[N],d[N],cut[N];
stack <int> st;
set <int> q[N];
vector <E> G[N];
vector <int> dcc[N];
bool vis[N];
set <int> s;
inline void tarjan(int x,int fa){
dfn[x]=low[x]=++cnt;
st.push(x);
for(E y:G[x]){
//if(x==2) cout<<x<<" "<<y<<" "<<fa<<endl;
if(!dfn[y.x]){
tarjan(y.x,fa);
low[x]=min(low[x],low[y.x]);
if(low[y.x]>=dfn[x]){
++cnm;
if(x!=fa||cnm>1) cut[x]=1;
++col;
int t;
do{
t=st.top();
st.pop();
dcc[col].push_back(t);
}while(st.size()&&t!=y.x);
dcc[col].push_back(x);
}
}
else low[x]=min(low[x],dfn[y.x]);
}
}
inline void calc(int i){
set <int> qwq;
qwq.clear();
int res=0;
for(int x:dcc[i]){
for(auto y:G[x]){
if(c[y.x]!=i) continue;
qwq.insert(y.y);
}
}
//cout<<i<<" "<<qwq.size()<<endl;
if(qwq.size()==dcc[i].size()) s.insert(qwq.begin(),qwq.end());
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
for(int i=1,x,y;i<=m;++i){
scanf("%d%d",&x,&y);
G[x].emp(y,i);
G[y].emp(x,i);
}
for(int i=1;i<=n;++i){
if(!dfn[i]) tarjan(i,i);
//cout<<i<<" "<<dfn[i]<<" "<<low[i]<<endl;
}
#if 0
for(int i=1;i<=n;++i)
if(cut[i]) cout<<i<<" qwq"<<endl;
#endif
#if 1
for(int i=1;i<=col;++i){
for(int x:dcc[i]) c[x]=i;
calc(i);
}
#endif
printf("%d\n",s.size());
for(int x:s) printf("%d ",x);
return 0;
}
\(\rm T3\) 汉明距离
暴力 \(\rm 65pts\)，听说有的人暴力拿了 \(\rm 75pts\)。
考虑将 \(\rm A,B\) 看成两个多项式的系数，把 \(\rm B\) 缺的位都补上 \(0\)。
根据卷积的性质，若 \(\rm C(x)=A(x)*B(x)\)，则有 $$\rm C_i=\sum_{j=0}^i A_j\cdot B_{i-j}$$
那么若是把 \(\rm B(x)\) 这个多项式翻转一下，这个 \(\rm B_{i-j}\) 就 变成了 \(\rm B_j\)，那么只有当 \(\rm A_i=1\) 且 \(\rm B_i=1\) 时 \(\rm C_i=1\)，也就是能够通过卷积算出 \(\rm C_i\)，即有多少个 \(\rm A_i=B_i=1\)。
同理，我们把 \(\rm B(x)\) 这个多项式 \(\rm 0/1\) 翻转一下，再卷一遍就可以得到有多少个 \(\rm A_i=B_i=0\)。
设第一遍卷的结果为 \(\rm C_{0,i}\)，第二遍卷的结果为 \(\rm C_{1,i}\)，那么最终的答案就是：
\[\rm\min \left \{ res-C_{0,i}-C_{1,i} \right \} \]时间复杂度 \(\rm O(|A|\log|A|)\)。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct Complex{
double x,y;
Complex(double a=0,double b=0){x=a,y=b;}
}f[N*4],g[N*4];
Complex operator + (Complex A,Complex B){return Complex(A.x+B.x,A.y+B.y);}
Complex operator - (Complex A,Complex B){return Complex(A.x-B.x,A.y-B.y);}
Complex operator * (Complex A,Complex B){return Complex(A.x*B.x-A.y*B.y,A.x*B.y+A.y*B.x);}
int n,m;
int res[N];
char A[N],B[N];
struct FFT{
const double pi=acos(-1);
int lim,l,r[N*4],p[N*4];
inline void fft(Complex *x,int op){
for(int i=0;i<lim;++i)
if(i<r[i]) swap(x[i],x[r[i]]);
for(int mid=1;mid<lim;mid<<=1){
Complex W(cos(pi/mid),op*sin(pi/mid));
int R=mid<<1;
for(int j=0;j<lim;j+=R){
Complex w(1,0);
for(int k=0;k<mid;++k,w=W*w){
Complex _x=x[j+k],_y=w*x[j+mid+k];
x[j+k]=_x+_y;
x[j+mid+k]=_x-_y;
}
}
}
}
inline void roll_mul(){
fft(f,1),fft(g,1);
for(int i=0;i<lim;++i)
f[i]=f[i]*g[i];
fft(f,-1);
}
inline void solve(int k){
for(l=0,lim=1;lim<=n+m;lim<<=1,++l);
for(int i=0;i<lim;++i)
r[i]=(r[i>>1]>>1|((i&1)<<(l-1)));
for(int i=0;i<n;++i)
f[i]=Complex(A[i]==('0'+k),0);
for(int i=n;i<lim;++i)
f[i]=Complex(0,0);
for(int i=0;i<m;++i)
g[m-1-i]=Complex(B[i]==('0'+k),0);
for(int i=m;i<lim;++i)
g[i]=Complex(0,0);
roll_mul();
for(int i=0;i<=n-m;++i){
res[i]+=(int)(f[i+m-1].x/lim+0.5);
}
}
}t;
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
scanf("%s\n%s",A,B);
n=strlen(A),m=strlen(B);
if(m==1){
for(int i=0;i<n;++i)
if(B[0]==A[i]){
puts("0");
return 0;
}
puts("1");
return 0;
}
t.solve(0),t.solve(1);
int ans=m;
for(int i=0;i<=n-m;++i)
ans=min(ans,m-res[i]);
printf("%d",ans);
}
\(\rm T4\) 勇者的后缀
后缀数组加主席树维护前驱后继加二分 \(\rm ST\) 表。
调吐了。
时间复杂度 \(\rm O((n+m)\log n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m;
int sa[N<<1],rk[N<<1],ht[N<<1];
char A[N];
struct SA{
int x[N<<1],y[N<<1],cnt[N<<1];
inline void get_sa(){//后缀数组
m=122;
for(int i=1;i<=n;++i) ++cnt[x[i]=A[i]];
for(int i=2;i<=m;++i) cnt[i]+=cnt[i-1];
for(int i=n;i;--i) sa[cnt[x[i]]--]=i;
for(int k=1;k<=n;k*=2){
int t=0;
for(int i=n-k+1;i<=n;++i) y[++t]=i;
for(int i=1;i<=n;++i)
if(sa[i]>k)
y[++t]=sa[i]-k;
for(int i=1;i<=m;++i) cnt[i]=0;
for(int i=1;i<=n;++i) ++cnt[x[i]];
for(int i=2;i<=m;++i) cnt[i]+=cnt[i-1];
for(int i=n;i;--i) sa[cnt[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y);
x[sa[1]]=1,t=1;
for(int i=2;i<=n;++i)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?t:++t;
if(t==n) break;
m=t;
}
}
inline void get_ht(){//求 height 数组
int t=0;
for(int i=1;i<=n;++i) rk[sa[i]]=i;
for(int i=1;i<=n;++i){
if(rk[i]==1){
continue;
}
if(t) --t;
int j=sa[rk[i]-1];
while(j+t<=n&&i+t<=n&&A[i+t]==A[j+t])
++t;
ht[rk[i]]=t;
}
}
}t1;
struct standard_table{
int st[20][N],lg[N];
inline void init(){//st 初始化
for(register int i = 2;i <= n;++i)
lg[i] = lg[i >> 1] + 1;
for(int i=1;i<=n;++i)
st[0][i]=ht[i];
for(int i=1;i<=19;++i)
for(int j=1;j+(1<<i)-1<=n;++j)
st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
}
inline int Q(int l,int r){//询问 [l,r] 最小
if(l==r)
return n-sa[l]+1;
++l;
int k=lg[r-l+1];
return min(st[k][l],st[k][r-(1<<k)+1]);
}
}t2;
struct node{
int l,r;
int sum;
}t[N<<5];
int cnt,rt[N];
struct chair_tree{
inline void insert(int &p,int pre,int l,int r,int x){//插入
p=++cnt;
t[p]=t[pre];
++t[p].sum;
if(l==r) return;
int mid=l+r>>1;
if(x<=mid) insert(t[p].l,t[pre].l,l,mid,x);
else insert(t[p].r,t[pre].r,mid+1,r,x);
}
inline void init(){//ct 预处理
for(int i=1;i<=n;++i)
insert(rt[i],rt[i-1],1,n,rk[i]);
}
inline int Q1(int p,int q,int l,int r,int L,int R){//区间 [p,q] 和
if(L>R) return 0;
if(L<=l&&r<=R)
return t[q].sum-t[p].sum;
int mid=l+r>>1;
int res=0;
if(L<=mid) res+=Q1(t[p].l,t[q].l,l,mid,L,R);
if(mid<R) res+=Q1(t[p].r,t[q].r,mid+1,r,L,R);
return res;
}
inline int Q2(int p,int q,int l,int r,int k){//区间 [p,q] 第 k 大
if(l==r)
return l;
int mid=l+r>>1;
int sum=t[t[q].l].sum-t[t[p].l].sum;
return k<=sum?Q2(t[p].l,t[q].l,l,mid,k):Q2(t[p].r,t[q].r,mid+1,r,k-sum);
}
}t3;
signed main(){
#ifndef ONLINE_JUDGE
freopen("18.in","r",stdin);
freopen("2.out","w",stdout);
#endif
scanf("%s",A+1);
n=strlen(A+1);
t1.get_sa(),t1.get_ht(),t2.init(),t3.init();
scanf("%d",&m);
while(m--){
int i,l,r;
scanf("%d%d%d",&i,&l,&r);
i=rk[i];
int sum=t3.Q1(rt[l-1],rt[r],1,n,1,i),L,R,LS,RS;
if(sum<t[rt[r]].sum-t[rt[l-1]].sum)
R=t3.Q2(rt[l-1],rt[r],1,n,sum+1),RS=t2.Q(i,R);
else RS=-1;
if(sum>0)
L=t3.Q2(rt[l-1],rt[r],1,n,sum),LS=t2.Q(L,i);
else LS=-1;
if(LS>=RS){
L = 1,R = i - 1;
int ans = i,mid;
while(L <= R)
mid = L + R >> 1,t2.Q(mid,i) >= LS ? (R = mid - 1,ans = mid) : (L = mid + 1);
printf("%d %d\n",LS,sa[t3.Q2(rt[l-1],rt[r],1,n,t3.Q1(rt[l-1],rt[r],1,n,1,ans-1)+1)]);
}
else
printf("%d %d\n",RS,sa[R]);
}
}