难说
T1
暴力可以写dp
只要你学过线性基那么你就会想怎么用线性基做，显然是要套点数据结构维护的。你要知道两个线性基可以在 \(O(\log^2 n)\) 的时间内合并，得到的线性基是原来两个的交。可以用线段树维护，复杂度 \(O((n+q)\log n\log^2 a)\)，难说能不能过。
没有修改，所以考虑用常熟小一点的数据结构，可以用ST表维护最值，复杂度 \(O(n\log n\log^2 a+q\log^2 a)\)，小了一点。
发现瓶颈在于 \(\log^2 a\) 的合并，看能不能优化成一个老哥。一个简单的思路是分治，把询问离线下来，处理跨过中点的询问，就只会对线性基产生 \(O(n\log n)\) 次的修改，复杂度被优化成 \(O(n\log n\log a+q\log^2 a)\)，好像能过了。
然后是正解，看不懂：
啥都能扫描线（
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define in inline
const ll N=1145140,M=1919810,inf=2e9,V=29;
ll n,Q,a[N],f[N],p[N],x;
ll ans[N];
struct xx{
ll l,r,d,id;
}q[N];
bool cmp(xx x,xx y){
return x.r<y.r;
}
bool flag;
void insert(ll x,ll id){
for(ll i=V;i>=0;--i)
if(x&(1ll<<i)){
if(!f[i]){
f[i]=x,p[i]=id;
return;
}
else{
if(id>p[i]){
swap(id,p[i]);
swap(x,f[i]);
}
x^=f[i];
}
}
flag=1;
}
ll qmax(ll d,ll l){
for(int i=V;i>=0;--i)
if(p[i]>=l) d=max(d,d^f[i]);
return d;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
n=read();
for(int i=1;i<=n;++i) a[i]=read();
Q=read();
for(int i=1;i<=Q;++i) q[i].l=read(),q[i].r=read(),q[i].d=read(),q[i].id=i;
//cin>>q[i].l>>q[i].r>>q[i].d,q[i].id=i;
sort(q+1,q+Q+1,cmp);
for(int i=1,j=1;i<=Q;++i){
while(j<=q[i].r){
insert(a[j],j);
++j;
}
ans[q[i].id]=qmax(q[i].d,q[i].l);
}
for(int i=1;i<=Q;++i) write(ans[i]),putchar('\n');
return 0;
}
T2
应该冲正解的，这个题其实真的挺简单的，就是建图。你会发现一个点能早到就尽量早到，不会因为可能错开车而使得时间不优。注意不需要在不同线路之间建边。
对每条线路把这个环建出来，每天边要记录 \(u\) 在线路中的下标（从 \(0\) 开始）和线路的长度用于计算到达时间。用 dij和SPFA 都行，但松弛过程中边权是根据 \(u\) 在线路中的位置和 \(dis[u]\) 确定的，具体看代码，很容易手推出来。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
#define pi pair<ll,ll>
const ll N=2*114514,M=1919810,inf=1e18;
ll n,m,t[N];
struct xx{
ll v,t,le;
};
ll dis[N];
bool vis[N];
vector <xx> g[N];
priority_queue <pi,vector<pi>,greater<pi>> q;
void dij(){
memset(dis,63,sizeof(dis));
dis[1]=0,q.push({dis[1],1});
while(!q.empty()){
ll u=q.top().second; q.pop();
if(vis[u]) continue;
vis[u]=1;
for(xx x:g[u]){
ll v=x.v,t=x.t,le=x.le,w=0;
if(dis[u]%le<=t) w=t-dis[u]%le+1;
else w=le-dis[u]%le+t+1;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push({dis[v],v});
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;++i){
cin>>t[i];
vector <ll> a;
for(int j=1,x;j<=t[i];++j) cin>>x,a.eb(x);
for(int j=0;j<t[i];++j) g[a[j]].eb((xx){a[(j+1)%t[i]],j,t[i]});
}
dij();
for(int i=2;i<=n;++i)
if(dis[i]==dis[0]) cout<<"-1 ";
else cout<<dis[i]<<" ";
return 0;
}
T3
智慧题。但是本来是把结论都推出来了，39pts的代码也打出来了，但是连犯两个最低级的错误，然后就没了。
不会。
标签：log,省选,ll,20240917,int,xx,define,模拟,dis From： https://www.cnblogs.com/heshuwan/p/18417858