CF第一rated教育场

A：水题，暴力模拟即可

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define N 10010
int n,a[N],tt,t;
int t1=1,t2=2,t3=3;
int main(){
	cin>>n;
	int flag=0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(a[i]!=t1&&a[i]!=t2){
			cout<<"NO"<<endl;
			flag=1;
             break;
		}
		else if(a[i]==t1){
			tt=t2;
			t2=t3;
			t3=tt;
		}
		else if(a[i]==t2){
			tt=t1;
			t1=t3;
			t3=tt;
		}
	}
	if(flag==0)cout<<"YES"<<endl;
	return 0;
}

B:数很小可以打表判断即可 (看错题 WA了一发

#include <bits/stdc++.h>
long long a[20];
long long ans[20];
long long power(int t){
    long long sum=1;
    for(int i=1;i<=t;i++){
        sum*=2;
    }
    return sum;
}
using namespace std;
int main(){
    a[0]=1;
    for(int i=1;i<=17;i++){
        a[i]=power(i);
    }
    for(int i=0;i<=8;i++){
        long long sum=0;
        for(int j=i+1;j<=2*i+1;j++){
            sum+=a[j-1];
        }
        ans[i]=sum;
    }
    int n;cin>>n;
    for(int i=8;i>=0;i--){
        if(n%ans[i]==0){
            printf("%d
",ans[i]);
            break;
        }
    }
    return 0;
}

C:并查集把具有朋友关系划为一类最后不同类的最小值相加就是解（并查集写戳了 233333

#include <bits/stdc++.h>
#define N 100005
#define ll long long
#define INF 1000000010
using namespace std;
ll a[N];
int fa[N];ll rnd[N];ll ans[N];
void csh(int n){
    for(int i=1;i<=n;i++){
        fa[i]=i;rnd[i]=1;
    }
}
int find1(int x){
    if(x!=fa[x]) return fa[x]=find1(fa[x]);
    else return x;
}
void hebin(int x,int y){
    if(rnd[x]<rnd[y]) fa[x]=y;
    else{
        fa[y]=x;
        if(rnd[x]==rnd[y]) rnd[x]++;
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    csh(n);
    for(int i=1;i<=n;i++) ans[i]=INF;
    long long sum=0;
    int t1,t2;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++){
        cin>>t1>>t2;
        int tt1=find1(t1);int tt2=find1(t2);
        if(tt1!=tt2){
            hebin(tt1,tt2);
        }
    }
    for(int i=1;i<=n;i++){
        int tt=find1(i);
        ans[tt]=min(ans[tt],a[i]);
    }
    for(int i=1;i<=n;i++){
        if(ans[i]!=INF) sum+=ans[i];
    }
    cout<<sum<<endl;
    return 0;
}

F:一直没看题昨晚队友告诉我可能是线段树早上爬起来一看 ....裸主席树就是对一个颗树按照先序遍历的方式编号对于不同点按照深度排序并对于深度建主席树最后查询即可（可能姿势不太对跑的有点慢2333

#include <bits/stdc++.h>
#define N 100005
#define INF 1000000010
using namespace std;
int a[N];
vector<int>vec[N];
int dep[N];int L[N];int R[N];
int od[N];int id=0;int cnt;
int rot[N];
void dfs(int v,int pre,int d){
    od[v]=v;dep[v]=d;L[v]=++id;
    for(int i=0;i<vec[v].size();i++){
        int u=vec[v][i];
        if(u!=pre){
            dfs(u,v,d+1);
        }
    }
    R[v]=id;
}
typedef struct node{
    int l;int r;int date;
}node;
bool cmp(int x,int y){
    return dep[x]<dep[y];
}
node d[N*20];
void built(int &x,int y,int l,int r,int t,int e){
    d[++cnt]=d[y];x=cnt;
    if(l==r){
        d[x].date=min(d[x].date,e);
        return ;
    }
    int mid=(l+r)>>1;
    if(t<=mid) built(d[x].l,d[y].l,l,mid,t,e);
    else if(t>mid)  built(d[x].r,d[y].r,mid+1,r,t,e);
    d[x].date=min(d[d[x].l].date,d[d[x].r].date);
}
int ans;
void querty(int x,int l,int r,int l1,int r1){
    if(l1<=l&&r<=r1){
        ans=min(d[x].date,ans);
        return ;
    }
    int mid=(l+r)>>1;
    if(l1<=mid) querty(d[x].l,l,mid,l1,r1);
    if(r1>mid) querty(d[x].r,mid+1,r,l1,r1);
}
int main(){
    int n,root;cin>>n>>root;
    d[0].date=INF;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
        int t1,t2;cin>>t1>>t2;
        vec[t1].push_back(t2);
        vec[t2].push_back(t1);
    }
    dfs(root,-1,1);
    sort(od+1,od+1+n,cmp);
    int maxx=-1;
    for(int i=1;i<=n;i++){
        maxx=max(maxx,dep[od[i]]);
        if(i==1) {built(rot[1],rot[0],1,n,L[od[i]],a[od[i]]);
     //   cout<<rot[1]<<" "<<d[rot[1]].date<<endl;
        continue;
        }
        built(rot[dep[od[i]]],rot[dep[od[i-1]]],1,n,L[od[i]],a[od[i]]);
       // cout<<L[od[i]]<<"====="<<a[od[i]]<<endl;
    }
    for(int i=maxx+1;i<=n;i++){
        rot[i]=rot[maxx];
    }
    int q;cin>>q;
    int last=0;int x1,k1;
    for(int i=1;i<=q;i++){
        cin>>x1>>k1;
        x1=((x1+last)%n)+1;k1=(k1+last)%n;
        int t=min(n,dep[x1]+k1);
        ans=INF;
        querty(rot[t],1,n,L[x1],R[x1]);
       // cout<<L[x1]<<" "<<R[x1]<<endl;
        last=ans;
        cout<<ans<<endl;
    }
    return 0;
}