#include<bits/stdc++.h>
using namespace std;
const int N=2200;
int a[N][N],n,m,r,c,x,y;
int o,ans[N][N];
struct node{
int i,j,x,y;
};
deque<node>q;
int vis[N][N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>r>>c>>x>>y;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char c;
cin>>c;
if(c=='*')a[i][j]=1;
}
}
q.push_back({r,c,x,y});
while(q.size()){
auto t=q.front();
q.pop_front();
int i=t.i;
int j=t.j;
if(vis[i][j])continue;
int x=t.x;
int y=t.y;
ans[i][j]=1;
vis[i][j]=1;
//cout<<"i="<<i<<" j="<<j<<'\n';
//上下左右
if(i-1>=1&&!a[i-1][j]&&!vis[i-1][j])q.push_front({i-1,j,x,y});
if(i+1<=n&&!a[i+1][j]&&!vis[i+1][j])q.push_front({i+1,j,x,y});
if(j-1>=1&&x&&!a[i][j-1]&&!vis[i][j-1])q.push_back({i,j-1,x-1,y});
if(j+1<=m&&y&&!a[i][j+1]&&!vis[i][j+1])q.push_back({i,j+1,x,y-1});
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
o+=ans[i][j];
}
}
if(a[r][c])o--;
cout<<o;
}
给定三个整数 p,q,b，请你计算十进制表示下的 p/q 的结果在 b 进制下是否为有限小数。
结论就是如果约分处理之后，q有的质因数如果b都有的话则YES
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,b,x,T;
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
cin>>a>>b>>x;
int d=__gcd(a,b);
a/=d,b/=d;
while(1){
int t=__gcd(b,x);
if(t==1){
if(b!=1)cout<<"NO"<<'\n';
if(b==1)cout<<"YES"<<'\n';
break;
}
b/=t;
}
}
}
ACM2的作业题目
ZOJ真的烦，也看不到错误信息
自己写了个bfs居然在acwing上过了
#include<bits/stdc++.h>
using namespace std;
// map<string,int>mp;
unordered_map<string,string>op;
int xx[]={1,-1,0,0};
int yy[]={0,0,1,-1};
// char zz[]={'d','u','r','l'};
char zz[]={'u','d','l','r'};
string S;
string T="12345678x";
string f(char a[3][3]){
string ans;
for(int i=0;i<9;i++)ans+=a[i/3][i%3];
return ans;
}
char a[3][3];
void bfs(string S){
op[S]="";
queue<string>q;
q.push(S);
int d=1000000;
while(q.size()){
string s=q.front();
q.pop();
//if(s==T)break;
if(--d==0)break;
int x,y,id;
for(int i=0;i<9;i++){
a[i/3][i%3]=s[i];
if(s[i]=='x')x=i/3,y=i%3,id=i;
}
for(int k=3;k>=0;k--){
int i=(k+2)%4;
int tx=x+xx[i];
int ty=y+yy[i];
char tz=zz[i];
int ti=tx*3+ty;
if(tx<0||tx>=3||ty<0||ty>=3)continue;
string t=s;
swap(t[id],t[ti]);
if(op.count(t))continue;
op[t]=op[s]+tz;
q.push(t);
}
}
}
signed main(){
bfs(T);
char j;
while(cin>>j){
S+=j;
for(int i=1;i<9;i++){
cin>>j;
S+=j;
}
//cout<<"S="<<S<<endl;
if(op.count(S)){
string ans=op[S];
reverse(ans.begin(),ans.end());
cout<<ans;
}
else cout<<"unsolvable";
//cout<<'\n';
S="";
}
}
线段树合并
对每个点开一个权值线段树
插在颜色上，维护max和sum这两个变量
不要直接#define int long long
要把需要的才开long long
不然还是会MLE
#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int N=1e5+10,M=2*N;
int h[N],e[M],ne[M],idx;
int n,m,c[N],root[N],cnt;
long long ans[N];
struct node{
int l,r;
long long sum;//主要颜色的编号和
int max;//出现最多颜色的次数
#define ls tr[u].l
#define rs tr[u].r
}tr[N*100];
void add(int a,int b){
e[++idx]=b,ne[idx]=h[a],h[a]=idx;
}
void pushup(int u){
tr[u].max=max(tr[ls].max,tr[rs].max);
if(tr[ls].max==tr[rs].max)tr[u].sum=tr[ls].sum+tr[rs].sum;
if(tr[ls].max >tr[rs].max)tr[u].sum=tr[ls].sum;
if(tr[ls].max <tr[rs].max)tr[u].sum=tr[rs].sum;
}
void pushdown(int u){
}
void modify(int &o,int l,int r,int i,int k){
if(!o)o=++cnt;
if(l==r){
tr[o].max=1;
tr[o].sum=k;
return;
}
int mid=l+r>>1;
if(i<=mid)modify(tr[o].l,l,mid,i,k);
else modify(tr[o].r,mid+1,r,i,k);
pushup(o);
}
int merge(int a,int b,int l,int r){//线段树合并
if(!a)return b;
if(!b)return a;//哪个没有就返回另一个点的编号
if(l==r){
tr[a].max+=tr[b].max;
return a;
}
int mid=l+r>>1;
tr[a].l=merge(tr[a].l,tr[b].l,l,mid);//合并a，b的左儿子
tr[a].r=merge(tr[a].r,tr[b].r,mid+1,r);//合并a，b的右儿子
pushup(a);
return a;
}
void cal(int u,int fa=0){
for(int i=h[u];i;i=ne[i]){
int j=e[i];
if(j==fa)continue;
cal(j,u);
root[u]=merge(root[u],root[j],1,n);
}
ans[u]=tr[root[u]].sum;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>c[i];
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
for(int i=1;i<=n;i++)modify(root[i],1,n,c[i],c[i]);
cal(1);
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}
活动打卡代码
AcWing 4280. 序列查询
#include<bits/stdc++.h>
using namespace std;
int n,k,x,ans;
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>k;
int pre;
cin>>pre;
for(int i=1;i<n;i++){
cin>>x;
ans+=(x-pre)*i;
pre=x;
}
ans+=(k-pre)*n;
cout<<ans;
}
将每一条边按照a从小到大枚举
化边为点
进而动态加边删边
如果1号点和n号点联通就更新答案
你要维护的是区间最大值还是最大值的编号？
答案是编号，因为只有这样，你才能split之后拿出来删边
注意一下删边时的编号映射，没了这道题就这样
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,p[N],stk[N];
int find(int x){
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
struct Edge{
int x,y,a,b;
bool operator<(const Edge&t)const{
return a<t.a;
}
}e[N];
struct node{
int s[2],p,v;
int mx,rev;
#define ls tr[u].s[0]
#define rs tr[u].s[1]
#define lx tr[x].s[0]
#define rx tr[x].s[1]
}tr[N];
void pushrev(int u){
swap(ls,rs);
tr[u].rev^=1;
}
void pushup(int u){
tr[u].mx=u;
int lmaxid=tr[ls].mx;
int rmaxid=tr[rs].mx;
if(tr[lmaxid].v>tr[tr[u].mx].v)tr[u].mx=lmaxid;
if(tr[rmaxid].v>tr[tr[u].mx].v)tr[u].mx=rmaxid;
}
void pushdown(int u){
if(tr[u].rev){
pushrev(ls);
pushrev(rs);
tr[u].rev=0;
}
}
bool isroot(int u){
return tr[tr[u].p].s[0]!=u&&tr[tr[u].p].s[1]!=u;
}
void rotate(int x){
int y=tr[x].p,z=tr[y].p;
int k=tr[y].s[1]==x;
if(!isroot(y))tr[z].s[tr[z].s[1]==y]=x;
tr[x].p=z;
tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
tr[x].s[k^1]=y,tr[y].p=x;
pushup(y),pushup(x);
}
void splay(int x){
int top=0,r=x;
stk[++top]=r;
while(!isroot(r))stk[++top]=r=tr[r].p;
while(top)pushdown(stk[top--]);
while(!isroot(x)){
int y=tr[x].p,z=tr[y].p;
if(!isroot(y)){
if((tr[z].s[1]==y)^(tr[y].s[1]==x))rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x){
int z=x;
for(int y=0;x;y=x,x=tr[y].p){
splay(x);
tr[x].s[1]=y,pushup(x);
}
splay(z);
}
void makeroot(int x){
access(x);
pushrev(x);
}
int findroot(int x){
access(x);
while(lx)pushdown(x),x=lx;
splay(x);
return x;
}
void split(int x,int y){
makeroot(x);
access(y);
}
void link(int x,int y){
makeroot(x);
if(findroot(y)!=x)tr[x].p=y;
}
void cut(int x,int y){
makeroot(x);
if(findroot(y)==x&&rx==y&&!tr[y].s[0]){
tr[y].p=rx=0;
pushup(x);
}
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y,a,b;
cin>>x>>y>>a>>b;
e[i]={x,y,a,b};
}
sort(e+1,e+1+m);
for(int i=1;i<=n+m;i++){
p[i]=i;
if(i>n)tr[i].v=e[i-n].b;
tr[i].mx=i;
}
int ans=1e9;
for(int i=1;i<=m;i++){
int x=e[i].x,y=e[i].y,a=e[i].a,b=e[i].b;
if(find(x)==find(y)){
split(x,y);
int t=tr[y].mx;
if(tr[t].v>b){
cut(t,e[t-n].x),cut(t,e[t-n].y);
link(i+n,x),link(i+n,y);
}
}
else{
p[find(x)]=find(y);
link(i+n,x),link(i+n,y);
}
if(find(1)==find(n)){
split(1,n);
ans=min(ans,a+tr[tr[n].mx].v);
}
}
cout<<(ans==1e9?-1:ans);
}
因为A的要求所以这道题被要求强制在线
同时，因为会查询之前的节点信息，所以我们不能真的删掉节点
那么如何找到真正的节点编号呢
我们发现每一个增加的节点一定会被放在某一层里，而这某一层就是排名
而且查询和更新的链路径信息一定是第i名到第j名
至此，找什么链找哪条链就知道了
如何找到第s天第x名选手的节点编号呢
我们可以插入的时候把{第i天，节点编号}push_back进一个容器rank里面
找的时候就是去rank[x]里面找到符合条件的第一个，也就是第一个小于等于{s，0}的节点，也就是前驱
你二分也可以，lower_bound也可以
lct裸题
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rank _rank
const int N=1e6+10;
int m,p,T,A,cur,idx,op,s,l,r,x,dep[N],fa[N],y;
typedef pair<int,int>PII;
vector<PII>rank[N];
struct node{
int s[2],p,v;
int sum,rev,mul;
#define ls tr[u].s[0]
#define rs tr[u].s[1]
#define lx tr[x].s[0]
#define rx tr[x].s[1]
}tr[N];
bool isroot(int u){
return tr[tr[u].p].s[0]!=u && tr[tr[u].p].s[1]!=u;
}
void pushup(int u){
tr[u].sum=tr[u].v;
if(ls)tr[u].sum+=tr[ls].sum;
if(rs)tr[u].sum+=tr[rs].sum;
tr[u].sum%=p;
}
void pushrev(int u){
swap(ls,rs);
tr[u].rev^=1;
}
void pushdown(int u){
if(tr[u].rev){
pushrev(ls);
pushrev(rs);
tr[u].rev=0;
}
if(tr[u].mul!=1){
tr[ls].mul=tr[ls].mul*tr[u].mul %p;
tr[ls].sum=tr[ls].sum*tr[u].mul %p;
tr[ls].v=tr[ls].v*tr[u].mul %p;
tr[rs].mul=tr[rs].mul*tr[u].mul %p;
tr[rs].sum=tr[rs].sum*tr[u].mul %p;
tr[rs].v=tr[rs].v*tr[u].mul %p;
tr[u].mul=1;
}
}
void rotate(int x){
int y=tr[x].p,z=tr[y].p;
int k=tr[y].s[1]==x;
if(!isroot(y))tr[z].s[tr[z].s[1]==y]=x;
tr[x].p=z;
tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
tr[x].s[k^1]=y,tr[y].p=x;
pushup(y),pushup(x);
}
void splay(int x){
static int stk[N];
int tt=0,t=x;
stk[++tt]=t;
while(!isroot(t))stk[++tt]=t=tr[t].p;
while(tt)pushdown(stk[tt--]);
while(!isroot(x)){
int y=tr[x].p,z=tr[y].p;
if(!isroot(y)){
if((tr[z].s[1]==y)^(tr[y].s[1]==x))rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x){ // 建立一条从根到x的路径，同时将x变成splay的根节点
int z=x;
for(int y=0;x;y=x,x=tr[x].p){
splay(x);
tr[x].s[1]=y,pushup(x);
}
splay(z);
}
void makeroot(int x){
access(x);
pushrev(x);
}
int findroot(int x){// 找到x所在原树的根节点, 再将原树的根节点旋转到splay的根节点
access(x);
while(lx)pushdown(x),x=lx;
splay(x);
return x;
}
void split(int x,int y){
makeroot(x);
access(y);
}
void link(int x,int y){
makeroot(x);
if(findroot(y)!=x)tr[x].p=y;
}
void cut(int x,int y){
makeroot(x);
if(findroot(y)==x&&rx==y&&!tr[y].s[0]){
tr[y].p=rx=0;
pushup(x);
}
}
int find(int s,int x){
//去排名为x的节点里面找第一个小于等于s的节点编号
int l=0,r=rank[x].size()-1;
while(l<r){
int mid=l+r+1>>1;
if(rank[x][mid].first<=s)l=mid;
else r=mid-1;
}
return rank[x][l].second;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>m>>p>>T;
for(int i=1;i<=m;i++){
cin>>op;
if(op==1){
cin>>x;
if(T)x^=A;
if(x>0){
++idx;
tr[idx].v=tr[idx].sum=x;
tr[idx].mul=1;
if(cur)link(cur,idx);
fa[idx]=cur,dep[idx]=dep[cur]+1;
rank[dep[idx]].push_back({i,idx});
cur=idx;
}
else cur=fa[cur];
}
else if(op==2){
cin>>s>>l>>r>>y;
if(T)y^=A;
l=find(s,l);
r=find(s,r);
split(l,r);
tr[r].v=tr[r].v*y%p;
tr[r].sum=tr[r].sum*y%p;
tr[r].mul=tr[r].mul*y%p;
}
else{
cin>>s>>l>>r;
l=find(s,l);
r=find(s,r);
split(l,r);
cout<<tr[r].sum<<'\n';
if(T)A=tr[r].sum;
}
}
}
活动打卡代码
AcWing 4010. 箱根山岳险天下
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rank _rank
const int N=1e6+10;
int m,p,T,A,cur,idx,op,s,l,r,x,dep[N],fa[N],y;
typedef pair<int,int>PII;
vector<PII>rank[N];
struct node{
int s[2],p,v;
int sum,rev,mul;
#define ls tr[u].s[0]
#define rs tr[u].s[1]
#define lx tr[x].s[0]
#define rx tr[x].s[1]
}tr[N];
bool isroot(int u){
return tr[tr[u].p].s[0]!=u && tr[tr[u].p].s[1]!=u;
}
void pushup(int u){
tr[u].sum=tr[u].v;
if(ls)tr[u].sum+=tr[ls].sum;
if(rs)tr[u].sum+=tr[rs].sum;
tr[u].sum%=p;
}
void pushrev(int u){
swap(ls,rs);
tr[u].rev^=1;
}
void pushdown(int u){
if(tr[u].rev){
pushrev(ls);
pushrev(rs);
tr[u].rev=0;
}
if(tr[u].mul!=1){
tr[ls].mul=tr[ls].mul*tr[u].mul %p;
tr[ls].sum=tr[ls].sum*tr[u].mul %p;
tr[ls].v=tr[ls].v*tr[u].mul %p;
tr[rs].mul=tr[rs].mul*tr[u].mul %p;
tr[rs].sum=tr[rs].sum*tr[u].mul %p;
tr[rs].v=tr[rs].v*tr[u].mul %p;
tr[u].mul=1;
}
}
void rotate(int x){
int y=tr[x].p,z=tr[y].p;
int k=tr[y].s[1]==x;
if(!isroot(y))tr[z].s[tr[z].s[1]==y]=x;
tr[x].p=z;
tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
tr[x].s[k^1]=y,tr[y].p=x;
pushup(y),pushup(x);
}
void splay(int x){
static int stk[N];
int tt=0,t=x;
stk[++tt]=t;
while(!isroot(t))stk[++tt]=t=tr[t].p;
while(tt)pushdown(stk[tt--]);
while(!isroot(x)){
int y=tr[x].p,z=tr[y].p;
if(!isroot(y)){
if((tr[z].s[1]==y)^(tr[y].s[1]==x))rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x){ // 建立一条从根到x的路径，同时将x变成splay的根节点
int z=x;
for(int y=0;x;y=x,x=tr[x].p){
splay(x);
tr[x].s[1]=y,pushup(x);
}
splay(z);
}
void makeroot(int x){
access(x);
pushrev(x);
}
int findroot(int x){// 找到x所在原树的根节点, 再将原树的根节点旋转到splay的根节点
access(x);
while(lx)pushdown(x),x=lx;
splay(x);
return x;
}
void split(int x,int y){
makeroot(x);
access(y);
}
void link(int x,int y){
makeroot(x);
if(findroot(y)!=x)tr[x].p=y;
}
void cut(int x,int y){
makeroot(x);
if(findroot(y)==x&&rx==y&&!tr[y].s[0]){
tr[y].p=rx=0;
pushup(x);
}
}
int find(int s,int x){
//去排名为x的节点里面找第一个小于等于s的节点编号
int l=0,r=rank[x].size()-1;
while(l<r){
int mid=l+r+1>>1;
if(rank[x][mid].first<=s)l=mid;
else r=mid-1;
}
return rank[x][l].second;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>m>>p>>T;
for(int i=1;i<=m;i++){
cin>>op;
if(op==1){
cin>>x;
if(T)x^=A;
if(x>0){
++idx;
tr[idx].v=tr[idx].sum=x;
tr[idx].mul=1;
if(cur)link(cur,idx);
fa[idx]=cur,dep[idx]=dep[cur]+1;
rank[dep[idx]].push_back({i,idx});
cur=idx;
}
else cur=fa[cur];
}
else if(op==2){
cin>>s>>l>>r>>y;
if(T)y^=A;
l=find(s,l);
r=find(s,r);
split(l,r);
tr[r].v=tr[r].v*y%p;
tr[r].sum=tr[r].sum*y%p;
tr[r].mul=tr[r].mul*y%p;
}
else{
cin>>s>>l>>r;
l=find(s,l);
r=find(s,r);
split(l,r);
cout<<tr[r].sum<<'\n';
if(T)A=tr[r].sum;
}
}
}
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int f[N][N],n,V,M;
int v,m,w;
signed main(){
cin>>n>>V>>M;
while(n--){
cin>>v>>m>>w;
for(int i=V;i>=v;i--){
for(int j=M;j>=m;j--){
f[i][j]=max(f[i][j],f[i-v][j-m]+w);
}
}
}
cout<<f[V][M];
}
关于动态树是什么？怎么实现？，铅笔大佬已经写的很nice了
这里简单记一下笔记
动态树难点
理解前驱后继与原树之间的关系
通过不断旋转，变换实链虚链来维护信息
赛场上，如何将问题转化成动态树，如何建树，如何将删边加边与要求一一等价对应才是难点
lct时间复杂度logn，树链剖分logn2
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{
int s[2],p,v;
int sum,rev;
#define ls tr[u].s[0]
#define lx tr[x].s[0]
#define rs tr[u].s[1]
#define rx tr[x].s[1]
}tr[N];
int n,m,op,x,y;
bool inline isroot(int u){
return tr[tr[u].p].s[0]!=u&&tr[tr[u].p].s[1]!=u;
}
void inline pushup(int u){
tr[u].sum=tr[ls].sum^tr[u].v^tr[rs].sum;
}
void inline pushrev(int u){
swap(ls,rs);
tr[u].rev^=1;
}
void inline pushdown(int u){
if(tr[u].rev){
pushrev(ls),pushrev(rs);
tr[u].rev=0;
}
}
void inline rotate(int x){
int y=tr[x].p,z=tr[y].p;
int k=tr[y].s[1]==x;
if(!isroot(y))tr[z].s[tr[z].s[1]==y]=x;
tr[x].p=z;
tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
tr[x].s[k^1]=y,tr[y].p=x;
pushup(y),pushup(x);
}
void inline splay(int x){
static int stk[N];
int tt=0,t=x;
stk[++tt]=t;
while(!isroot(t))stk[++tt]=t=tr[t].p;
while(tt)pushdown(stk[tt--]);
while(!isroot(x)){
int y=tr[x].p,z=tr[y].p;
if(!isroot(y)){
if( (tr[z].s[1]==y)^(tr[y].s[1]==x) )rotate(x);
else rotate(y);
}rotate(x);
}
}
void inline access(int x){
int z=x;
for(int y=0;x;y=x,x=tr[x].p){
splay(x);
rx=y;
pushup(x);
}
splay(z);
}
void inline makeroot(int x){
access(x);
pushrev(x);
}
int inline findroot(int u){
access(u);
while(ls)pushdown(u),u=ls;
splay(u);
return u;
}
void inline split(int x,int y){
makeroot(x);
access(y);
}
void inline link(int x,int y){
makeroot(x);
if(findroot(y)!=x)tr[x].p=y;
}
void inline cut(int x,int y){
makeroot(x);
if(findroot(y)==x&&rx==y&&!tr[y].s[0]){
tr[y].p=rx=0;
pushup(x);
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>tr[i].v;
while(m--){
cin>>op>>x>>y;
if(op==0){
split(x,y);
cout<<tr[y].sum<<'\n';
}
if(op==1)link(x,y);
if(op==2)cut(x,y);
if(op==3){
splay(x);
tr[x].v=y;
pushup(x);
}
}
}
