A
记 \(\displaystyle f(i)=\oplus_{d|i}d\)，求 \(\displaystyle \oplus_{i=1}^{n}f(i)\).
\(n\le 10^{14}\).
考虑一个数是否出现计数次，对 \(\lfloor\frac{n}{x}\rfloor\) 整除分块，查询区间异或和即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read(){
ll x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
ll pref(ll x){
if(!x)return 0;
ll ans=1;
if(((x-1)/2)&1)ans^=1;
if(!(x&1))ans^=x;
return ans;
}
ll calc(ll l,ll r){
return pref(r)^pref(l-1);
}
ll n,ans;
int main(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
n=read();
for(ll l=1,r;l<=n;l=r+1){
r=n/(n/l);
if((n/l)&1)ans^=calc(l,r);
}
printf("%lld\n",ans);
return 0;
}
B
GJOJ 不是很给力，\(O(kn\log n+mk^2)\) 只给了 80 分。
点击查看代码
#include<bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
#define ll long long
#define N 100010
#define M 200010
#define K 25
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n,m;
int head[N],ver[M<<1],nxt[M<<1],dist[M<<1],tot;
void add(int u,int v,int w){
nxt[++tot]=head[u];
ver[tot]=v,dist[tot]=w;
head[u]=tot;
}
int k,id[K];
ll dis[K][N];bool vis[N];
#define pii pair<ll,int>
#define se second
#define mp make_pair
void dijkstra(int s){
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)dis[s][i]=1e18;
priority_queue<pii>q;
dis[s][id[s]]=0,q.push(mp(0,id[s]));
while(!q.empty()){
int u=q.top().se;q.pop();
if(vis[u])continue;
vis[u]=true;
for(int i=head[u],v;i;i=nxt[i]){
if(dis[s][v=ver[i]]>dis[s][u]+dist[i]){
dis[s][v=ver[i]]=dis[s][u]+dist[i];
q.push(mp(-dis[s][v],v));
}
}
}
}
int main(){
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
n=read(),m=read();
for(int i=1,u,v,w;i<=m;i++){
u=read(),v=read(),w=read()*2;
add(u,v,w),add(v,u,w);
}
k=read();
id[0]=1,dijkstra(0);
for(int i=1;i<=k;i++)
id[i]=read(),dijkstra(i);
ll ans=1e18;
//meet on vertex
for(int i=1;i<=n;i++){
ll res=0;
for(int j=0;j<=k;j++)
res=max(res,dis[j][i]);
ans=min(ans,res);
}
//meet on edge
for(int u=1,v,w;u<=n;u++)
for(int i=head[u];i;i=nxt[i]){
v=ver[i],w=dist[i];
for(int j=0;j<=k;j++){
ll lt=0,rt=0;
for(int t=0;t<=k;t++){
if(dis[t][u]<=dis[j][u])lt=max(lt,dis[t][u]);
else rt=max(rt,dis[t][v]);
}
if(lt>rt)swap(lt,rt);
if(lt+w<=rt)ans=min(ans,rt);
else ans=min(ans,(lt+rt+w)/2);
}
}
printf("%lld\n",ans);
return 0;
}
C
一个 01 串，每次给出一个 \(k\)，至多可以 \(k\) 次将串的一个区间翻转，最大化其最长不降子序列的长度。
询问相互独立。
字符串由 \(n\) 个二元组 \((c_i,p_i)\) 组成，表示从左往右每一段分别有 \(p_i\) 个 \(c_i\).
\(n\le 2\times 10^5\)，\(p_i\le 10^9\)，\(q\le 2\times 10^5\)，\(0\le k\le n\)，\(c_i\in\{0,1\}\).
D
*3500？整这么逆天。
标签：ch,int,2023.10,while,le,define,dis From： https://www.cnblogs.com/SError0819/p/17744206.html