AtCoder Beginner Contest 254【VP记录】

ABC 略

D - Together Square

遇到这种题，没思路，首先想到打表。

观察发现没啥规律，然后看差值。

 可发现：当N 本身为平方数时，与前一项的差值分别为【1，3，5，7...】 ,很明显可以观察到是一个等差为 2 的等差数列。

当 N 不是平方数时，与前一项的差值实质上是 N 的最大平方数因子对应的贡献。如 8 的最大平方数因子为  ，而 4  的贡献对应是等差数列的贡献也就是 3 。

找到规律，递推到 n ,我们就可以算出答案了。

#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题很容易发现，每个点的度数至多为3，故可在查询之前直接将所有结点的结果预处理，用BFS或者DFS暴力枚举即可，每个点最多也就是操作10次，时间复杂度允许。下面时BFS的代码：

#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

做这题需要预备一个知识。

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题解引用于：AtCoder Beginner Contest 254 A-Ex - 知乎 (zhihu.com)