A meeting
题意
给一棵树，以及树上的(k)个点，要求一个点使得这k个点到这个点的最大距离最小。
分析
简单的做法就是求出这(k)个点在树上的最远距离，类似于求树直径的做法，然后点肯定取在直径一半处。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int n,k,u,v,x,c[N],dis[N];
struct Edge{
int v,next;
}edge[N*2];
int cnt,head[N];
void init(){
cnt=0;
memset(head,-1,sizeof(head));
}
void add(int u,int v){
edge[cnt]=Edge{v,head[u]};
head[u]=cnt++;
edge[cnt]=Edge{u,head[v]};
head[v]=cnt++;
}
void dfs(int u,int f){
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(v==f){
continue;
}
dis[v]=dis[u]+1;
dfs(v,u);
}
}
int main(){
// freopen("in.txt","r",stdin);
scanf("%d%d",&n,&k);
init();
for(int i=0;i<n-1;i++){
scanf("%d%d",&u,&v);
add(u,v);
}
for(int i=1;i<=n;i++){
scanf("%d",&x);
c[x]=1;
}
int t=0;
for(int i=1;i<=n;i++){
if(c[i]){
dis[i]=0;
t=i;
dfs(i,0);
break;
}
}
for(int i=1;i<=n;i++){
if(c[i] && dis[i]>dis[t]){
t=i;
}
}
dis[t]=0;
dfs(t,0);
for(int i=1;i<=n;i++){
if(c[i] && dis[i]>dis[t]){
t=i;
}
}
printf("%d
",(dis[t]+1)/2);
}
C sequence
题意
给定序列(a)和(b)，求所有区间(min{a_l,a_{l+1}...a_r}*sum{b_l,b_{l+1}...b_r})。
分析
预处理出每个(a_i)作为最小值延伸的区间，然后线段树维护(b)序列，对于每个(a_i)，根据正负，求出包含(b_i)的最大子段和和最小子段和。
代码
#include <bits/stdc++.h>
using namespace std;
#define ls i<<1
#define rs i<<1|1
#define mid (l+r)/2
typedef long long ll;
const int N=3e6+15;
int n,a[N],b[N],le[N],ri[N],q[N];
struct node{
ll sum,lmx,rmx;
}tr[N*4];
void pushup(int i){
tr[i].sum=tr[ls].sum+tr[rs].sum;
tr[i].lmx=max(tr[ls].lmx,tr[ls].sum+tr[rs].lmx);
tr[i].rmx=max(tr[rs].rmx,tr[rs].sum+tr[ls].rmx);
}
void build(int i,int l,int r){
if(l==r){
tr[i].sum=tr[i].lmx=tr[i].rmx=b[l];
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(i);
}
node query(int i,int l,int r,int ql,int qr){
if(ql<=l && qr>=r){
return tr[i];
}
if(qr<=mid){
return query(ls,l,mid,ql,qr);
}
if(ql>mid){
return query(rs,mid+1,r,ql,qr);
}
node ll=query(ls,l,mid,ql,qr);
node rr=query(rs,mid+1,r,ql,qr);
node ans{};
ans.sum=ll.sum+rr.sum;
ans.lmx=max(ll.lmx,ll.sum+rr.lmx);
ans.rmx=max(rr.rmx,rr.sum+ll.rmx);
return ans;
}
int main(void){
// freopen("in.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
}
int l=1;
int l1=1,r1=0;
for(int r=1;r<=n;r++){
while(l1<=r1 && a[r]<a[q[r1]]){
ri[q[r1]]=r-1;
r1--;
}
q[++r1]=r;
l++;
}
while(l1<=r1){
ri[q[r1]]=n;
r1--;
}
l=1;
l1=1,r1=0;
for(int r=n;r>=1;r--){
while(l1<=r1 && a[r]<a[q[r1]]){
le[q[r1]]=r+1;
r1--;
}
q[++r1]=r;
l++;
}
while(l1<=r1){
le[q[r1]]=1;
r1--;
}
ll ans=0;
build(1,1,n);
for(int i=1;i<=n;i++){
if(a[i]<0){
continue;
}
node lt=query(1,1,n,le[i],i);
node rt=query(1,1,n,i,ri[i]);
ll t=max(max(lt.rmx,rt.lmx),max(1ll*b[i],lt.rmx+rt.lmx-b[i]));
ans=max(ans,t*a[i]);
}
for(int i=1;i<=n;i++){
b[i]=-b[i];
}
build(1,1,n);
for(int i=1;i<=n;i++){
if(a[i]>0){
continue;
}
node lt=query(1,1,n,le[i],i);
node rt=query(1,1,n,i,ri[i]);
ll t=max(max(lt.rmx,rt.lmx),max(1ll*b[i],lt.rmx+rt.lmx-b[i]));
ans=max(ans,-t*a[i]);
}
printf("%lld
",ans);
return 0;
}
I string
题意
给一个字符串，一个子串与其逆序子串算同一个，求子串个数。
分析
- 如果不考虑其他条件，不同子串个数可以用后缀数组求出。因为要涉及到翻转过来的子串，所以按照后缀数组常见套路，将字符串逆序拼接在后面，求出子串个数，因为跨越中间的不算，判断一下(sa[i])的大小即可。
- 对于上一步求出的所有子串，如果子串不是回文串，那么每两个子串其实就是一个子串，另一个是由字符串翻转之后得到的，而如果子串是回文串，那么就只求出一个。
- 因此我们用回文树求出所有本质不同的回文子串，加到上一步求出的所有子串当中，现在再除以二，就是满足题目要求的子串个数。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+50;
char str[N];
int s[N],sa[N],rk[N],h[N];
int t[N],t2[N],c[N];
void Sa(int n,int m=128){
n++;
int *x=t,*y=t2;
for(int i=0;i<m;i++){
c[i]=0;
}
for(int i=0;i<n;i++){
c[x[i]=s[i]]++;
}
for(int i=1;i<m;i++){
c[i]+=c[i-1];
}
for(int i=n-1;i>=0;i--){
sa[--c[x[i]]]=i;
}
for(int k=1;k<=n;k<<=1){
int p=0;
for(int i=n-k;i<n;i++){
y[p++]=i;
}
for(int i=0;i<n;i++){
if(sa[i]>=k){
y[p++]=sa[i]-k;
}
}
for(int i=0;i<m;i++){
c[i]=0;
}
for(int i=0;i<n;i++){
c[x[y[i]]]++;
}
for(int i=1;i<m;i++){
c[i]+=c[i-1];
}
for(int i=n-1;i>=0;i--){
sa[--c[x[y[i]]]]=y[i];
}
swap(x,y);
p=1;
x[sa[0]]=0;
for(int i=1;i<n;i++){
x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
}
if(p>=n){
break;
}
m=p;
}
n--;
for(int i=0;i<=n;i++){
rk[sa[i]]=i;
}
int k=0;
for(int i=0;i<n;i++){
if(k){
k--;
}
int j=sa[rk[i]-1];
while(s[i+k]==s[j+k]){
k++;
}
h[rk[i]]=k;
}
}
ll getP(int n){
ll ans=0;
int mid=n/2;
for(int i=1;i<=n;i++){
if(sa[i]>mid){
ans+=1ll*(n-sa[i]-h[i]);
}else if(sa[i]==mid){
continue;
}else{
ans+=max(0ll,1ll*(mid-sa[i]-h[i]));
}
}
return ans;
}
struct PT{
int next[N][26],fail[N],cnt[N],num[N],len[N];
int S[N],last,id[N],n,p;
int newnode(int l){
for(int i=0;i<26;i++){
next[p][i]=0;
}
cnt[p]=0;
num[p]=0;
len[p]=l;
return p++;
}
void init(){
p=0;
newnode(0);
newnode(-1);
last=0;
n=0;
S[n]=-1;
fail[0]=1;
}
int getFail(int x){
while(S[n-len[x]-1]!=S[n]){
x=fail[x];
}
return x;
}
void add(int c){
c-='a';
S[++n]=c;
int cur=getFail(last);
if(!next[cur][c]){
int now=newnode(len[cur]+2);
fail[now]=next[getFail(fail[cur])][c];
num[now]=num[cur]+1;
next[cur][c]=now;
}
last=next[cur][c];
cnt[last]++;
id[last]=n;
}
void count(){
for(int i=p-1;i>=0;i--){
cnt[fail[i]]+=cnt[i];
}
}
}ac;
int main(void){
// freopen("in.txt","r",stdin);
scanf("%s",str);
int n=strlen(str);
for(int i=0;i<n;i++){
s[i]=str[i]-'a'+2;
}
s[n]=1;
for(int i=0;i<n;i++){
s[n+1+i]=str[n-1-i]-'a'+2;
}
Sa(n*2+1);
ll p=getP(n*2+1);
ac.init();
for(int i=0;i<n;i++){
ac.add(str[i]);
}
ll q=ac.p-2;
ll ans=(p+q)/2;
printf("%lld
",ans);
return 0;
}
J free
题意
给一个带权图，有(k)次机会边权为0，求(s)到(t)的最小花费。
分析
分层图最短路模板题，bzoj2763
在普通Dijk的基础上，多定义了一个状态，定义(low[i][j])表示从(s)到(i)使用(j)条免费路的最小花费，然后松弛操作转移的时候判断一下即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=2e3+50;
const int INF=0x3f3f3f3f;
int s,t,n,m,k,u,v,w;
bool vis[N][N];
//dis[v][i]: 到v使用i条免费路的最短路
int dis[N][N];
struct Edge{
int v,w;
};
vector<Edge> g[N];
struct node{
int v,dis,lev;
bool operator <(const node& rhs)const{
return dis>rhs.dis;
}
};
int dijkstra(int s,int t){
for(int i=0;i<=n;i++){
for(int j=0;j<=k;j++){
vis[i][j]=false;
dis[i][j]=INF;
}
}
dis[s][0]=0;
priority_queue<node> pq;
pq.push(node{s,0,0});
while(!pq.empty()){
node t=pq.top();
pq.pop();
int u=t.v;
int lev=t.lev;
if(vis[u][lev]){
continue;
}
vis[u][lev]=true;
int siz=g[u].size();
for(int i=0;i<siz;i++){
int v=g[u][i].v;
int w=g[u][i].w;
if(dis[u][lev]+w<dis[v][lev]){
dis[v][lev]=dis[u][lev]+w;
pq.push(node{v,dis[v][lev],lev});
}
if(lev<k && dis[u][lev]<dis[v][lev+1]){
//使用一条免费路
dis[v][lev+1]=dis[u][lev];
pq.push(node{v,dis[v][lev+1],lev+1});
}
}
}
int ans=INF;
for(int i=0;i<=k;i++){
ans=min(ans,dis[t][i]);
}
return ans;
}
int main(void){
scanf("%d%d%d",&n,&m,&k);
scanf("%d%d",&s,&t);
for(int i=0;i<m;i++){
scanf("%d%d%d",&u,&v,&w);
g[u].push_back(Edge{v,w});
g[v].push_back(Edge{u,w});
}
int ans=dijkstra(s,t);
printf("%d
",ans);
return 0;
}
K number
题意
给一个数字串，求数值可以整除300的子串个数。
分析
定义(dp[i][j])表示以第(i)位数字结尾，模300余数为(j)的子串个数，(O(n*300))转移即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
char s[N];
//dp[i][j]表示到第i位，余数为j的子串数
ll dp[N][305];
int main(void){
scanf("%s",s+1);
int n=strlen(s+1);
ll ans=0;
for(int i=1;i<=n;i++){
int b=s[i]-'0';
dp[i][b]++;
for(int j=0;j<300;j++){
dp[i][(j*10+b)%300]+=dp[i-1][j];
}
ans+=dp[i][0];
}
printf("%lld
",ans);
return 0;
}