Atcoder beginer contest 254 [VP record]

ABC A little

D - Together Square

When it comes to this kind of problem , No idea , First of all, I want to make a watch .

Observation shows that there is no rule , Then look at the difference .

  Can be found ： When N  When itself is square , The difference with the previous item is 【1,3,5,7...】 , Obviously, it can be observed that there is an equal deviation of 2  Equal difference sequence of .

When N When it's not square , The difference from the previous item is essentially N The contribution corresponding to the maximum square factor of . Such as 8  The maximum square factor of is   , and 4   The contribution of is corresponding to the contribution of the arithmetic sequence, that is 3 .

Find the rules , Recursive to n , We can work out the answer .

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
const int Max=2e5+5;
int vis[Max];
int mp[Max];
int cnt=0;
void init(ll n){
	int sum=1;
	for(int i=1;i<=n;i++){
		ll num=sqrt(i);
		if(num*num==i){
			vis[cnt++]=i,mp[i]=sum,sum+=2;
		}
	}
}
int main(){
	int n;sc(n);
	init(n);
	ll ans=0;
	for(int i=1;i<=n;i++){
		for(int j=cnt-1;j>=0;j--){
			if(i%vis[j]==0&&mp[vis[j]]){
				// cout<<j/i<<' '<<mp[j/i]<<endl;
				ans+=mp[vis[j]];break;
			}
		}
	}
	cout<<ans<<endl;
}

E - Small d and k

        E The question is easy to find , The degree of each point is at most 3, Therefore, the results of all nodes can be preprocessed directly before the query , use BFS perhaps DFS Just enumerate the violence , At most, each point is the operation 10 Time , Time complexity allows . Below BFS Code for ：

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
const int Max=2e5+5;
vector<int>mp[Max];
bool vis[Max];
int low[Max];
ll sum[Max][4];
vector<int>ve;
void bfs(int fa){
    ve.pb(fa);
    vis[fa]=true;
    sum[fa][0]=fa;
    low[fa]=0;
    queue<int>q;
    int start,next;
    start=fa;
    q.push(fa);
    while(!q.empty()){
        start=q.front();
        q.pop();
        for(auto v:mp[start]){
            if(low[start]+1>3||vis[v]) continue;
            ve.pb(v);
            vis[v]=true;
            sum[fa][low[start]+1]+=v;
            low[v]=low[start]+1;
            q.push(v);
        }
    }
}
int main(){
    int n;sc(n);int m;sc(m);
    for(int i=0;i<=n;i++) low[i]=1e9+5;
    for(int i=1;i<=m;i++){
        int u,v;
        sc(u);sc(v);
        mp[u].pb(v);
        mp[v].pb(u);
    }
    // bfs(2);
    for(int i=1;i<=n;i++){
        for(auto v:ve) vis[v]=false;
        ve.clear();
        bfs(i);
    }
    int q;sc(q);
    while(q--){
        int x,k;
        sc(x);sc(k);
        ll ans=0;
        for(int i=0;i<=k;i++) ans+=sum[x][i];
        printf("%lld\n",ans);
    }
}

F - Rectangle GCD

To do this problem, you need to prepare a knowledge .

gcd(a1,a2,a3,a4,a5...an) = gcd(a1,a2-a1,a3-a2,a4-a3...an-an-1)

 

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
const int Max=2e6+5;
const int mod=1e9+7;
ll tree[Max];
ll suma[Max],sumb[Max];
ll a[Max],b[Max];
void build(int node,int l,int r){
    // if(l>r) return ;
    // cout<<l<<' '<<r<<endl;
    if(l==r){
        // cout<<suma[l]<<"---\n";
        tree[node]=suma[l];return ;
    }
    int mid=(l+r)>>1;
    build(node*2,l,mid);
    build(node*2+1,mid+1,r);
    tree[node]=__gcd(tree[node*2],tree[node*2+1]);
    return;
}
ll query(int node,int l,int r,int left,int right){
    ll ret;
    if(l>=left&&r<=right) ret=tree[node];
    else{
        int mid=(l+r)>>1;
        if(right<=mid) ret=query(node*2,l,mid,left,right);
        else if(left>mid) ret=query(node*2+1,mid+1,r,left,right);
        else {
            ret=query(node*2,l,mid,left,right);
            ret=__gcd(ret,query(node*2+1,mid+1,r,left,right));
        }
    }
    return ret;
}
ll treeb[Max];
void build_b(int node,int l,int r){
    // if(l>r) return ;
    // cout<<l<<' '<<r<<endl;
    if(l==r){
        // cout<<suma[l]<<"---\n";
        treeb[node]=sumb[l];return ;
    }
    int mid=(l+r)>>1;
    build_b(node*2,l,mid);
    build_b(node*2+1,mid+1,r);
    treeb[node]=__gcd(treeb[node*2],treeb[node*2+1]);
    return;
}
ll query_b(int node,int l,int r,int left,int right){
    ll ret;
    if(l>=left&&r<=right) ret=treeb[node];
    else{
        int mid=(l+r)>>1;
        if(right<=mid) ret=query_b(node*2,l,mid,left,right);
        else if(left>mid) ret=query_b(node*2+1,mid+1,r,left,right);
        else {
            ret=query_b(node*2,l,mid,left,right);
            ret=__gcd(ret,query_b(node*2+1,mid+1,r,left,right));
        }
    }
    return ret;
}
int main(){
    int n;sc(n);int q;sc(q);
    for(int i=1;i<=n;i++){
        sl(a[i]);
        if(i!=1) suma[i-1]=a[i]-a[i-1];
    }
    if(n!=1) build(1,1,n-1);
    for(int i=1;i<=n;i++){
        sl(b[i]);
        if(i!=1) sumb[i-1]=b[i]-b[i-1];
    }
    if(n!=1) build_b(1,1,n-1);
    while(q--){
        int h1,h2,w1,w2;
        sc(h1);sc(h2);sc(w1);sc(w2);
        ll ret=a[h1]+b[w1];
        if(h1!=h2) ret=__gcd(ret,query(1,1,n-1,h1,h2-1));
        if(w1!=w2) ret=__gcd(ret,query_b(1,1,n-1,w1,w2-1));
        printf("%lld\n",abs(ret));
    }
}
/*
1
3 
3 3 1
*/

 Ex - Multiply or Divide by 2

 

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
const int Max=2e5+5;
const int Mod=998244353;
int main(){
	int n;sc(n);
	priority_queue<int>qa,qb;
	for(int i=1;i<=n;i++){
		int k;sc(k);
		qa.push(k);
	}
	for(int i=1;i<=n;i++){
		int k;sc(k);
		qb.push(k);
	}
	ll ans=0;
	bool flag=true;
	while(!qa.empty()){
		int nx=qa.top();
		int ny=qb.top();
		qa.pop(),qb.pop();
		if(nx==ny) ;
		else if(nx>ny) ans++,qa.push(nx/2),qb.push(ny);
		else{
			if(ny%2==1){
				flag=false;break;
			}else ans++,qa.push(nx),qb.push(ny/2);
		}
	}
	if(!flag) printf("-1\n");
	else printf("%lld\n",ans);
}

D,F,EX Problem solving for ：AtCoder Beginner Contest 254 A-Ex - You know (zhihu.com)