本场总结：
题目类型:
A.dfs找直径
B.线段树上 维护 线性基交
C.单调栈找min边界和线段树z维护区间最值
D.分类讨论构造
E.F.G.H 留坑没想法
I.后缀数组找不同子串个数和回文树找回文串个数
J.最短路k次免费
K.签到
小结:
---学习 线段树上 维护 线性基交
---找固定区间最小值求区间左右边界可以用单调栈维护O(n)
---按位或的知识小讨论
---复习了一下后缀数组和回文树
A.meeting
题意：有n个城市，编号从1到n,然后只有n-1条连线，不会成环。从第一个地方到另一个地方只需要1秒，现在有k个人，分别分布
在不同的城市，现在问他们相聚最短所需的时间，。
分析:就是k个人相聚，走的路最长的那个人的用时就是答案时间,那么其实就是求图的直径，并且直径的两端必须是人所在的位置。答案就是直径的一半(上取整).
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
vector<int> g[maxn];
int tmp,s;
bool vis[maxn];
void dfs( int x,int dep,int f )
{
if( vis[x] )
{
if( dep>tmp ) tmp=dep,s=x;
}
for( int i=0;i<g[x].size();i++ )
{
int v=g[x][i];
if( v==f ) continue;
dfs(v,dep+1,x);
}
}
int main()
{
int n,k;
cin>>n>>k;
for( int i=1;i<n;i++ )
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for( int i=1;i<=k;i++ )
{
int x;cin>>x;vis[x]=1;
}
dfs(1,0,0);
tmp=0;
dfs(s,0,0);
cout<<(tmp+1)/2<<endl;
}B.xor
题目大意：
给你n个集合，每个集合中都有不超过32个数，总共询问m次，每次询问区间 [L, R] 中的所有集合，是否都有一个异或和等于X的子集。
分析：
这个题很明显，要求线性基的交，也就是说假设有A，B两个线性基，要求出一个线性基C，使得C表示的线性空间既包含于A所表示的线性空间，也包含于B所表示的线性空间。再用线段树维护一下.线性交看
https://ac.nowcoder.com/discuss/213230?type=101&order=0&pos=2&page=1
#include<bits/stdc++.h>
#define ls ( cur<<1 )
#define rs ( cur<<1 |1 )
typedef unsigned int uint;
using namespace std;
const int maxn=5e4+10;
struct SGT
{
int n;
uint a[maxn<<2][32]; // 记录每个节点上的线性基
void insert(uint x,int cur )
{
for( int i=31;i>=0;i-- )
{
if( x>>i )
{
if( !a[cur][i] )
{
a[cur][i]=x;
break;
}
x^=a[cur][i];
}
}
}
void push_up( int cur ) // 非叶节点上的线性基等于它的子节点的交线性基
{
uint t1[32],t2[32];
for( int i=0;i<32;i++ ) t1[i]=t2[i]=a[ls][i];
for( int i=0;i<32;i++ )
{
if( a[rs][i] )
{
uint x=a[rs][i],tmp=0;
for( int j=31;j>=0;j-- )
{
if( x>>j )
{
if( !t1[j] )
{
t1[j]=x;
t2[j]=tmp;
break;
}
x^=t1[j];
tmp^=t2[j];
}
}
if( !x ) insert(tmp,cur);
}
}
}
void build( int cur,int l,int r )
{
if( l==r ) // 叶节点上的线性基等于对应集合的线性基
{
int sz;
scanf("%d",&sz);
uint tmp;
for( int i=0;i<sz;i++ )
{
scanf("%u",&tmp);
insert(tmp,cur);
}
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
push_up(cur);
}
int query( int cur, int l,int r,int L,int R ,uint val )
{
if( l>=L && r<=R ) // 直接在子区间对应的节点上的线性基中检查
{
for( int i=31;i>=0;i-- )
{
if( val>>i ) val^=a[cur][i];
}
return val==0 ;
}
int mid=(l+r)>>1;
int res=1;
if( L<=mid ) res &= query(ls,l,mid,L,R,val);
if( R>mid ) res &= query(rs,mid+1,r,L,R,val);
return res; //只有左右边界同时满足才返回 1 --->1&1&1=1 其他情况返回 0
}
}s;
int main()
{
int n,m;
scanf("%d %d",&n,&m);
s.build(1,1,n);
for( int i=0;i<m;i++ )
{
int x,y;
uint val;
scanf("%d %d %u",&x,&y,&val);
if( s.query(1,1,n,x,y,val) ) puts("YES");
else puts("NO");
}
return 0;
}
C.sequence
题目大意:给定数组a[1...n]、b[1....n],找一段区间 使得 { min( a[l..r] )*sum( b[l...r] ) }值最大.
此题只能线段树去区间最大最小值,st表空间会T,笛卡尔树我也不会
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e6+10;
const ll inf=0x7f7f7f7f;
int a[maxn],b[maxn];
ll sum[maxn];
struct node{
int l;
int r;
ll Max;
ll Min;
}t[maxn<<2];
void read( int &x )
{
int f=1;x=0;char s=getchar();
for( ;!isdigit(s);s=='-' && (f=-1),s=getchar());
for( ;isdigit(s);x=x*10+s-48,s=getchar());
x*=f;
}
void pushup( int n )
{
t[n].Max=max(t[n<<1].Max,t[n<<1|1].Max);
t[n].Min=min(t[n<<1].Min,t[n<<1|1].Min);
}
void build( int n ,int l,int r )
{
t[n].l=l;
t[n].r=r;
if( l == r )
{
t[n].Min=t[n].Max=sum[l];
return;
}
int mid=(l+r)>>1;
build(n<<1,l,mid);
build(n<<1|1,mid+1,r);
pushup( n );
}
ll get_Max( int n,int L,int R )
{
int l=t[n].l,r=t[n].r;
if( L<=l && r<=R ) return t[n].Max;
int mid=(l+r)>>1;
ll max1=-inf;
if( L<=mid ) max1=max(max1,get_Max(n<<1,L,R));
if( R>mid ) max1=max(max1,get_Max(n<<1|1,L,R));
return max1;
}
ll get_Min( int n,int L,int R )
{
int l=t[n].l,r=t[n].r;
if( L<=l && r<=R ) return t[n].Min;
ll min1=inf;
int mid=(l+r)>>1;
if( L<=mid ) min1=min(min1,get_Min(n<<1,L,R));
if( R>mid ) min1=min(min1,get_Min(n<<1|1,L,R));
return min1;
}
int s[maxn];
int L[maxn],R[maxn];
int main()
{
int n;
read(n);
for( int i=1;i<=n;i++ ) read(a[i]);
for( int i=1;i<=n;i++ )
{
read(b[i]);
sum[i]=sum[i-1]+b[i];
}
build(1,1,n+1);
int top=0;
for( int i=1;i<=n;i++ ) // find l
{
while( top && a[s[top]]>=a[i] ) --top;
L[i]=( top==0 ? 1 : s[top]+1 );
s[++top]=i;
}
top=0;
for( int i=n;i>=1;i-- ) // find r
{
while( top && a[s[top]]>=a[i] ) --top;
R[i]=( top==0 ? n : s[top]-1 );
s[++top]=i;
}
ll ans=-inf;
for( int i=1;i<=n;i++ )
{
ll tmp;
if( a[i]>0 )
{
if( L[i]==1 )
{
tmp=get_Max(1,i,R[i])-min( get_Min(1,L[i],i-1),0ll );
}
else tmp=get_Max(1,i,R[i])-get_Min(1,L[i]-1,i-1);
}
else if( a[i]<0 )
{
if( L[i]==1 )
{
tmp=get_Min(1,i,R[i])-max( get_Max(1,L[i],i-1),0ll );
}
else tmp=get_Min(1,i,R[i])-get_Max(1,L[i]-1,i-1);
}
else tmp=0;
tmp*=a[i];
ans=max(ans,tmp);
}
printf("%lld\n",ans);
}D.triples I
题目大意:给定一个数n,求尽可能少的数按位或运算等于n并且这些数是3的倍数
分析如图
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
ll a,x,y;
void solve()
{
cin>>a;
vector<ll> b[2];
for( int i=0;i<=60;i++ )
{
if( a>>i & 1 ) b[ i&1 ].push_back( 1ll<<i );
}
if( a%3==0 )
{
cout<<1<<" "<<a<<endl;
return;
}
int s=( a%3==2 );
if( b[s].size() )
{
x=a-b[s][0];
if( b[s^1].size() ) y=b[s][0]+b[s^1][0];
else y=a-b[s][1];
}
else
{
x=a-b[s^1][0]-b[s^1][1];
y=b[s^1][0]+b[s^1][1]+b[s^1][2];
}
cout<<2<<" "<<x<<" "<<y<<endl;
}
int main()
{
cin>>t;
while( t-- )
{
solve();
}
}I.string
大致题意:给定一个字符串，求该字符串的子串个数。子串s满足 任意其他子串t s!=t and s!=rev(t) .
分析:就是求原串和翻转原串的不同子串个数.显然后缀数组就能搞.广义后缀自动机我也不会
#include<bits/stdc++.h>
#define ms(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn = 4e5+10 ;
const int N = 26;
const int mod=1e9+7;
struct DA{
int wa[maxn],wb[maxn],wsf[maxn],wv[maxn],sa[maxn];
int Rank[maxn],height[maxn];
int cmp(int *r,int a,int b,int k)
{
return r[a]==r[b]&&r[a+k]==r[b+k];
}
void getsa(int *r,int *sa,int n,int m)//n为添加0后的总长
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=0; i<m; i++) wsf[i]=0;
for(i=0; i<=n; i++) wsf[x[i]=r[i]]++;
for(i=1; i<m; i++) wsf[i]+=wsf[i-1];
for(i=n; i>=0; i--) sa[--wsf[x[i]]]=i;
p=1;
j=1;
for(; p<=n; j*=2,m=p) //倍增的算法
{
for(p=0,i=n+1-j; i<=n; i++) y[p++]=i;
for(i=0; i<=n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=0; i<=n; i++) wv[i]=x[y[i]];
for(i=0; i<m; i++) wsf[i]=0;
for(i=0; i<=n; i++) wsf[wv[i]]++;
for(i=1; i<m; i++) wsf[i]+=wsf[i-1];
for(i=n; i>=0; i--) sa[--wsf[wv[i]]]=y[i];
t=x;
x=y;
y=t;
x[sa[0]]=0;
for(p=1,i=1; i<=n; i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)? p-1:p++;
}
}
void getheight(int *r,int n) // n 为添加0后的总长
{
int i,j,k=0;
for(i=1; i<=n; i++) Rank[sa[i]]=i;
for(i=0; i<n; i++)
{
if(k)
k--;
else
k=0;
j=sa[Rank[i]-1];
while(r[i+k]==r[j+k])
k++;
height[Rank[i]]=k;
}
}
void clear()
{
ms(sa);ms(Rank);ms(height);
ms(wv),ms(wsf),ms(wa),ms(wb);
}
}da;
struct PAM {
int next[maxn][N] ;//表示编号为i的节点表示的回文串在两边添加字符c以后变成的回文串的编号（和字典树类似）
int fail[maxn] ;//fail[i]表示
int cnt[maxn] ; //表示节点i代表的字符串出节点i失配以后跳转到长度小于该串且以该节点表示回文串的最后一个字符结尾的最长回文串表示的节点出 现次数 ，最后count()函数跑一遍以后才是正确的）
int num[maxn] ;//num[i]表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数(即本质不同且包括本身)
int len[maxn] ;//len[i]表示节点i表示的回文串的长度（一个节点表示一个回文串)
int S[maxn] ;//存放添加的字符
int last ;//指向新添加一个字母后所形成的最长回文串表示的节点。
int n ;//表示添加的字符个数。
int p ;//表示添加的节点个数(本质不同的字符串总数)
int newnode ( int l ) {//新建节点
for ( int i = 0 ; i < N ; ++ 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 get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ;
return x ;
}
void add ( int c ) {
c -= 'a' ;
S[++ n] = c ;
int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
if ( !next[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
int now = newnode ( len[cur] + 2 ) ;//新建节点
fail[now] = next[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
next[cur][c] = now ;
num[now] = num[fail[now]] + 1 ;
}
last = next[cur][c] ;
cnt[last] ++ ;
}
void count () {
for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
//父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
}
}pam;
char str1[maxn];
int s[maxn];
int main()
{
scanf("%s",str1);
int len = strlen(str1);
pam.init(); // 回文树初始化
for( int i=0;i<len;i++ ) pam.add(str1[i]); //加入 回文树
ll ans=pam.p-2; //计算回文串个数
str1[len]='#';
for( int i=1;i<=len;i++ ) str1[len+i]=str1[len-i]; // 加上倒置字符串
str1[len*2+1]='\0';
// -----后缀数组初始化
int n=strlen(str1);
for( int i=0;i<n;i++ ) s[i]=str1[i];
da.getsa(s,da.sa,n,2510);
da.getheight(s,n);
// -----
for( int i=1;i<=n;i++ )
{
if( da.sa[i]==len ) continue;
if( da.sa[i]>len ) ans+=(n-da.sa[i]-da.height[i]);
else ans+=(len-da.sa[i]-da.height[i]);
}
printf("%lld\n",ans/2);
return 0;
}J.free
题目大意:n个点，m条带权边，问从S点到T点最短路是多少，路上可以使用K次让边权为0.
分析:跑一遍bfs就可以了
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
bool vis[maxn][maxn];
int n,m,s,ed,k;
struct node{
int v,w;
};
struct qnode{
int u,d,k;
bool operator < ( qnode t ) const {
return d>t.d;
}
}t;
priority_queue<qnode> q;
vector<node> g[maxn];
int bfs()
{
q.push( {s,0,k} );
while( !q.empty() )
{
t=q.top();q.pop();
if( vis[t.u][t.k] ) continue;
vis[t.u][t.k]=1;
if( t.u==ed ) return t.d;
for( auto p:g[t.u] )
{
if( t.k ) q.push( {p.v,t.d,t.k-1} );
q.push( {p.v,t.d+p.w,t.k} );
}
}
}
int main()
{
cin>>n>>m>>s>>ed>>k;
for( int i=1;i<=m;i++ )
{
int a,b,c;
cin>>a>>b>>c;
g[a].push_back( {b,c} );
g[b].push_back( {a,c} );
}
int ans=bfs();
cout<<ans<<endl;
} K.number
题目大意:给定一个数字字符串，问字符串中有多少子串转化成十进制是300的倍数.前导00和0算做两种，并且相同的子串出现在不同的地方可以被计数多次。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
char s[maxn];
int w[maxn],cn[3]; // w[i] 前缀和 mod 3 cn[i] 前缀和为 i 的个数
int main()
{
scanf("%s",s+1);
int n=strlen(s+1);
for( int i=1;i<=n;i++ ) w[i]=(w[i-1]+s[i]-'0')%3;
ll ans=0;
for( int i=1;i<=n;i++ )
{
if( s[i]=='0' )
{
++ans; // 有效区间长度为 1 ---> 0
if( s[i-1]=='0' ) ans+=cn[w[i]]; // (w[r]-w[l-1])%3==0 ---> w[r]=w[l-1] ans+=cn( w[r] )
}
cn[w[i-1]]++; //有效区间长度为 2 ---> ?00
}
printf("%lld\n",ans);
} 
京公网安备 11010502036488号