当前位置:网站首页>AtCoder Beginner Contest 254【VP记录】
AtCoder Beginner Contest 254【VP记录】
2022-07-06 00:06:00 【瘾ิۣۖิۣۖิۣۖิꦿ】
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)
边栏推荐
- Key structure of ffmpeg - avformatcontext
- 微信小程序---WXML 模板语法(附带笔记文档)
- 妙才周刊 - 8
- 【luogu CF487E】Tourists(圆方树)(树链剖分)(线段树)
- Convert Chinese into pinyin
- 20220703 week race: number of people who know the secret - dynamic rules (problem solution)
- China Jinmao online electronic signature, accelerating the digitization of real estate business
- 15 MySQL stored procedures and functions
- XML配置文件(DTD详细讲解)
- 跟着CTF-wiki学pwn——ret2libc1
猜你喜欢
Single merchant v4.4 has the same original intention and strength!
Doppler effect (Doppler shift)
What are the functions of Yunna fixed assets management system?
上门预约服务类的App功能详解
MySql——CRUD
Key structure of ffmpeg - avformatcontext
Problem solving win10 quickly open ipynb file
【DesignMode】组合模式(composite mode)
Determinant learning notes (I)
单商户V4.4,初心未变,实力依旧!
随机推荐
选择致敬持续奋斗背后的精神——对话威尔价值观【第四期】
Ffmpeg learning - core module
FFMPEG关键结构体——AVFrame
如何解决ecology9.0执行导入流程流程产生的问题
数据库遇到的问题
N1 # if you work on a metauniverse product [metauniverse · interdisciplinary] Season 2 S2
VBA fast switching sheet
NSSA area where OSPF is configured for Huawei equipment
[gym 102832h] [template] combination lock (bipartite game)
[day39 literature extensive reading] a Bayesian perspective on magnetic estimation
How to rotate the synchronized / refreshed icon (EL icon refresh)
Single merchant v4.4 has the same original intention and strength!
DEJA_ Vu3d - cesium feature set 055 - summary description of map service addresses of domestic and foreign manufacturers
Yunna | what are the main operating processes of the fixed assets management system
Wechat applet -- wxml template syntax (with notes)
多普勒效应(多普勒频移)
Key structure of ffmpeg - avframe
Mysql - CRUD
Add noise randomly to open3d point cloud
云呐|固定资产管理系统主要操作流程有哪些