22-07-12 personal training match 1 competition experience

The new individual race has begun , The difference is that there is no dalao 了 qwq

 

 A: Water problem

B: Two points

C:( For me, ） A little complicated thinking problem

D: Water problem

E: It's hard for no one to cry

F: greedy

G: Deformed BFS

H: Analog graphics

I: The meter

J: Difference card I space complexity

K: Forget it can be used unorder_map Then the bucket saves the subscript and adds a large number to prevent negative numbers , Reduce complexity by subtracting judgment

L: The line segment tree I just learned yesterday maintains prefixes and suffixes, but I still can't think of it without a board

L:Teacher Deng is Gazing U +

 DDP Partial board subtitle （ But it's difficult for me ）

pushup It's thinking , Fancy , The hard part is query A variant of , Because it uses structure return（ This is the sticking point of the game ）.

#include <bits/stdc++.h>
#define int long long
#define CIO std::ios::sync_with_stdio(false)
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
#define pii pair<int,int>
using namespace std;
const int N=2e5+5;
int a[N];
struct tree{
	int l,r,mxl,mxr,ans;
}t[4*N];
void pushup(int p){
	if (t[2*p].r-t[2*p].l+1==t[2*p].mxl)
		t[p].mxl=t[2*p].ans+t[2*p+1].mxl;
	else 
		t[p].mxl=t[2*p].mxl;
	
	if (t[2*p+1].r-t[2*p+1].l+1==t[2*p+1].mxr)
		t[p].mxr=t[2*p].mxr+t[2*p+1].ans;
	else 
		t[p].mxr=t[2*p+1].mxr;
	
	t[p].ans=max(max(t[2*p].ans,t[2*p+1].ans),t[2*p].mxr+t[2*p+1].mxl);
}
void build(int p,int l,int r){
	t[p].l=l;t[p].r=r;
    if (l==r){
        if (a[l]==1){
        	t[p].mxl=t[p].mxr=1;
        	t[p].ans=1;
		}
		else{
			t[p].mxl=t[p].mxr=0;
        	t[p].ans=0;
		}
        return;
    }
    int mid=l+r>>1;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    pushup(p);
}
tree query(int p,int x,int y){
	if (x<=t[p].l&&t[p].r<=y){
		return t[p];
	}
	int mid=(t[p].l+t[p].r)>>1;
	tree T,a,b;
	if (x>mid) return query(2*p+1,x,y);	
	else if (y<=mid) return query(2*p,x,y);
	else{
		a=query(2*p,x,y);
		b=query(2*p+1,x,y);
		if (a.r-a.l+1==a.ans) T.mxl=a.ans+b.mxl;
		else	T.mxl=a.mxl;
		if (b.r-b.l+1==b.ans) T.mxr=a.mxr+b.ans;
		else T.mxr=b.mxr;
		T.ans=max(max(a.ans,b.ans),a.mxr+b.mxl);
		return T;
	}
}
void update(int p,int x){
    if (t[p].l==t[p].r){
        t[p].ans=t[p].mxl=t[p].mxr=1-t[p].mxr;
        return ;
    }
    int mid=(t[p].l+t[p].r)>>1;
    if (x<=mid)update(2*p,x);
    else update(2*p+1,x);
    pushup(p);
}
void work(){
	int n;cin>>n;
	rep(i,1,n){
		cin>>a[i];
	}
	int m;cin>>m;
	int op,x,y;
	build(1,1,n);
	rep(i,1,m){
		cin>>op;
		if (op==1){
			cin>>x;
			update(1,x);
		}	
		else{
			cin>>x>>y;
			cout<<query(1,x,y).ans<<endl;
		}
	}
}
signed main(){
	CIO;
	work();
	return 0;
}

G:HIPERCIJEVI 

 

#include <bits/stdc++.h>
#define CIO std::ios::sync_with_stdio(false)
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
#define pii pair<int,int>
using namespace std;
struct edge{
	int to,nxt,val;
}e[M];
int cnt=0;
int head[N];
int a[N];
void add(int u,int v){
	cnt++;
	e[cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
queue<int> q;
int dis[N];
void work(){
	int n,k,m;
	cin>>n>>k>>m;
	int u,v,w;
	for (int i=1;i<=m;i++){
		for (int j=1;j<=k;j++){
			cin>>a[i];
			add(a[i],i+n);
			add(i+n,a[i]);
		}
	}
	memset(dis,-1,sizeof dis);
	q.push(1);
	dis[1]=1;
	while (!q.empty()){
		int sec=q.front();q.pop();
		for (int i=head[sec];i;i=e[i].nxt){
			int v=e[i].to;
			if (dis[v]==-1){
				dis[v]=dis[sec]+1;
				q.push(v);
			}
		}
	}
	if (dis[n]==-1){
		cout<<-1<<endl;
	}
	else{
		cout<<dis[n]/2+1<<endl;
	}
}

signed main(){
	CIO;
	work();
	return 0;
}