当前位置:网站首页>Atcoder beginer contest 254 [VP record]
Atcoder beginer contest 254 [VP record]
2022-07-06 00:12:00 【Addiction ۣۖ ิ ۣۖ ิ ۣۖ ิꦿ】
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)
边栏推荐
- 多普勒效应(多普勒频移)
- 软件测试工程师必会的银行存款业务,你了解多少?
- Transport layer protocol ----- UDP protocol
- QT a simple word document editor
- mysql-全局锁和表锁
- How much do you know about the bank deposit business that software test engineers must know?
- Global and Chinese markets for hinged watertight doors 2022-2028: Research Report on technology, participants, trends, market size and share
- About the slmgr command
- What is information security? What is included? What is the difference with network security?
- 7.5 decorator
猜你喜欢
Detailed explanation of APP functions of door-to-door appointment service
云呐|固定资产管理系统主要操作流程有哪些
FFMPEG关键结构体——AVCodecContext
Determinant learning notes (I)
Huawei equipment configuration ospf-bgp linkage
Gd32f4xx UIP protocol stack migration record
行列式学习笔记(一)
FFmpeg学习——核心模块
Hudi of data Lake (1): introduction to Hudi
"14th five year plan": emphasis on the promotion of electronic contracts, electronic signatures and other applications
随机推荐
传输层协议------UDP协议
Global and Chinese market of valve institutions 2022-2028: Research Report on technology, participants, trends, market size and share
7.5模拟赛总结
openssl-1.0.2k版本升级openssl-1.1.1p
【luogu CF487E】Tourists(圆方树)(树链剖分)(线段树)
Global and Chinese market of digital serial inverter 2022-2028: Research Report on technology, participants, trends, market size and share
[designmode] composite mode
Initialize your vector & initializer with a list_ List introduction
Miaochai Weekly - 8
Recognize the small experiment of extracting and displaying Mel spectrum (observe the difference between different y_axis and x_axis)
Tips for using pads router
软件测试工程师必会的银行存款业务,你了解多少?
云呐|固定资产管理系统功能包括哪些?
MySql——CRUD
The difference of time zone and the time library of go language
微信小程序---WXML 模板语法(附带笔记文档)
[binary search tree] add, delete, modify and query function code implementation
[Luogu p3295] mengmengda (parallel search) (double)
Global and Chinese markets for hinged watertight doors 2022-2028: Research Report on technology, participants, trends, market size and share
Knowledge about the memory size occupied by the structure