大抵是没有挂分。
简单题+博弈+图论+树论，典。
xor
一个 \(n\times n\) 的空矩阵 \(A\)，进行如下操作：
给定 \(r,c,l,s\)，对于 \(x\in[r,r+l)\)，\(y\in[c,x-r+c]\)，给 \(A_{x,y}\) 加上 \(s\)，也就是以 \((r,c)\) 为左上角的下三角区域。
最后问整个矩形的异或和。
\(n\le 1000\)，\(q\le 3\times 10^5\)，\(s\le 10^9\).
肯定是先求出每个位置的值。
容易想到每行差分，所以维护差分的列差分和斜线差分即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define N 1010
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
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,q,dlt;
ll a[N][N];
ll b[N][N],c[N<<1][N];
pii getpos(int i,int j){
i-=dlt;
if(i==0)return mp(j,j);
if(i<0)return mp(1+(j-(1-i)),j);
return mp((i+1)+(j-1),j);
}
bool check(pii x){
return x.fi>0&&x.fi<=n&&x.se>0&&x.se<=n;
}
int main(){
freopen("xor.in","r",stdin);
freopen("xor.out","w",stdout);
n=dlt=read(),q=read();
for(int x,y,l,s;q;q--){
x=read(),y=read(),l=read(),s=read();
b[x][y]+=s,b[min(n+1,x+l)][y]-=s;
c[x-(y+1)+dlt][y+1]-=s,c[x-(y+1)+dlt][min(n+1,y+l+1)]+=s;
}
pii tp;
for(int i=0;i<=dlt*2;i++)
for(int j=1;j<=n;j++){
c[i][j]+=c[i][j-1];
tp=getpos(i,j);
if(check(tp))a[tp.fi][tp.se]=c[i][j];
}
for(int j=1;j<=n;j++)
for(int i=1;i<=n;i++)
b[i][j]+=b[i-1][j],a[i][j]+=b[i][j];
ll ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]+=a[i][j-1],ans^=a[i][j];
printf("%lld\n",ans);
return 0;
}
game
两人博弈。初始有一个集合 \(S=\{a_n\}\).
第 \(i\in[1,m]\) 轮 有一个参数 \(b_i\)，操作者仅能只留下或全部舍弃 \(S\) 中所有 \(b_i\) 的倍数。
令操作结束后 \(S\)（可空）中的元素和为 \(x\)，先手欲最小化 \(x\)，后手欲最大化 \(x\).
问最后的 \(x\).
\(n\le 2\times 10^4\)，\(m\le 2\times 10^5\)，\(|a_i|\le 4\times 10^{14}\)，\(1\le b_i\le 4\times 10^{14}\).
部分分刷爽的一集。没什么必要写就不写了。
结论
对于先手，若每次选择集合大小更小的一侧，\(\log n\) 次可使答案为 \(0\)，后手同理。
也就是说当 \(m> 2\log n\) 时答案必为 \(0\)，接下来考虑一个有时间复杂度保证的算法。
使用二叉树构建整个博弈过程。
- insert
若当前节点不存在，创建一个新节点。当其为 \(b_{dep}\) 的倍数时，插入右子树，反之插入左子树。
- query
查询当前轮数下的最大/最小权值。在左右子树中查询，并按照先后手决策计算答案。
每次决策会将集合划分为两个不交集合，故时间复杂度 \(O(nm)\).
总时间复杂度 \(O(n\log n)\).
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define N 20010
#define M 200010
#define L 30
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;
}
int n,m;
ll a[N],b[M];
struct Tree{
ll s[N*L];
int lc[N*L],rc[N*L],tot;
void insert(int &p,int dep,ll val){
if(!p)p=++tot;
if(dep>m)return s[p]+=val,void();
if(val%b[dep])insert(lc[p],dep+1,val);
else insert(rc[p],dep+1,val);
}
ll query(int p,int dep){
if(!p)return 0;
if(dep>m)return s[p];
ll r1=query(lc[p],dep+1),r2=query(rc[p],dep+1);
return (dep&1)?min(r1,r2):max(r1,r2);
}
}T;
int rt;
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=m;i++)b[i]=read();
if(m>28)return puts("0"),0;
for(int i=1;i<=n;i++)
T.insert(rt,1,a[i]);
printf("%lld\n",T.query(rt,1));
return 0;
}
connect
无边的图，对于 \(1\le i<j\le n\)，若 \(\gcd(i,j)\) 为合数则在 \(i,j\) 间连无向边。
试删除一个节点，最小化最大的连通块大小。多测。
\(T\le 10\)，\(n\le 10^5\)，\(a_i\le 10^7\).
有意义的删点显然在割点上。对于较大的 \(n\) 考虑优化建边。
令单位合数为可以表示为 \(2\) 个质数的乘积的数。
对于存在边的两点，将它们与 \(\gcd\) 的一个是单位合数的因子连边。
每个数的单位合数因子是 \(O(\log V^2)\) 的，也就是新图总边数 \(O(n\log V^2)\).
直接在原图最大的连通块里 tarjan.
遇到返祖边时，可以在栈里不断跳回去，把 \(siz\) 加回 \(u\) 里。
不训图论导致的。
点击查看代码
#include<bits/stdc++.h>
#define N 100010
#define M 2005010
#define E 6000010
#define R 10000001
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 p[R>>3],minp[R],id[R],cnt,P;bool vis[R];
int fa[M],sz[M],siz[M];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int u,int v){
u=find(u),v=find(v);
if(u==v)return;
fa[u]=v,sz[v]+=sz[u];
}
int dfn[M],low[M],st[M],top,tim;
void init(){
for(int i=2;i<R;i++){
if(!vis[i])p[++cnt]=minp[i]=i;
for(int j=1;j<=cnt&&i*p[j]<R;j++){
vis[i*p[j]]=true,minp[i*p[j]]=p[j];
if(i%p[j]==0)break;
}
}
for(int i=2;i<R;i++)
if(vis[i]&&!vis[i/minp[i]])id[i]=++P;
}
int head[M],nxt[E],ver[E],tot;
void add(int u,int v){
nxt[++tot]=head[u];
ver[tot]=v;
head[u]=tot;
}
int ans,node;
int n;
void tarjan(int u,int edge){
dfn[u]=low[u]=++tim;
st[++top]=u,siz[u]=0;
int mx=0,scc=0;
for(int i=head[u],v;i;i=nxt[i]){
if(i==(edge^1))continue;
if(!dfn[v=ver[i]]){
tarjan(v,i),low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
int sum=0;
for(int x=0;x!=v;)
x=st[top--],siz[u]+=siz[x],sum+=siz[x];
scc++,mx=max(mx,sum);
}
}
else low[u]=min(low[u],dfn[v]);
}
if(u<=n){
siz[u]++;
if((edge&&scc)||(!edge&&scc>1))
ans=min(ans,max(mx,node-siz[u]));
else ans=min(ans,node-1);
}
}
void solve(){
memset(head,0,sizeof(head)),tot=1,tim=top=0;
n=read();
for(int i=1;i<=n+P;i++)
fa[i]=i,sz[i]=dfn[i]=low[i]=0;
int pr[10],c[10];
for(int i=1,x,t;i<=n;i++){
x=read(),sz[i]=1;
for(int j=0;j<10;j++)pr[j]=c[j]=0;
while(x>1){
t=minp[x],pr[++pr[0]]=t;
while(x%t==0)x/=t,c[pr[0]]++;
}
for(int j=1;j<=pr[0];j++)
for(int k=j+(c[j]<=1);k<=pr[0];k++)
if(1ll*pr[j]*pr[k]<R){
int tp=id[pr[j]*pr[k]]+n;
add(i,tp),add(tp,i);
merge(tp,i);
}
}
int mx=0,se=0,pos=0;
for(int i=1;i<=n+P;i++){
if(fa[i]!=i||!sz[i])continue;
if(sz[i]>mx)se=mx,mx=sz[i],pos=i;
else if(sz[i]>se)se=sz[i];
}
ans=node=mx;
tarjan(pos,0);
printf("%d\n",max(ans,se));
}
int main(){
freopen("connect.in","r",stdin);
freopen("connect.out","w",stdout);
init();
int T=read();
while(T--)solve();
return 0;
}
route
留给想做的同学。
100 + 60 + 15 + 0 = 175.
标签：10,le,int,2023.10,dep,ch,12,define From： https://www.cnblogs.com/SError0819/p/17760486.html