当前位置:网站首页>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)
边栏推荐
- mysql-全局锁和表锁
- C file and folder operation
- Redis high availability - master-slave replication, sentinel mode, cluster
- 微信小程序---WXML 模板语法(附带笔记文档)
- 云呐|固定资产管理系统主要操作流程有哪些
- How to rotate the synchronized / refreshed icon (EL icon refresh)
- 第16章 OAuth2AuthorizationRequestRedirectWebFilter源码解析
- Effet Doppler (déplacement de fréquence Doppler)
- Global and Chinese market of water heater expansion tank 2022-2028: Research Report on technology, participants, trends, market size and share
- Detailed explanation of APP functions of door-to-door appointment service
猜你喜欢
Redis high availability - master-slave replication, sentinel mode, cluster
18. (ArcGIS API for JS) ArcGIS API for JS point collection (sketchviewmodel)
What are the functions of Yunna fixed assets management system?
剖面测量之提取剖面数据
[noi simulation] Anaid's tree (Mobius inversion, exponential generating function, Ehrlich sieve, virtual tree)
Hudi of data Lake (1): introduction to Hudi
Key structure of ffmpeg - avformatcontext
openssl-1.0.2k版本升级openssl-1.1.1p
[day39 literature extensive reading] a Bayesian perspective on magnetic estimation
Doppler effect (Doppler shift)
随机推荐
7.5 simulation summary
Open source CRM customer relationship system management system source code, free sharing
MySql——CRUD
[EF core] mapping relationship between EF core and C data type
mysql-全局锁和表锁
N1 # if you work on a metauniverse product [metauniverse · interdisciplinary] Season 2 S2
数据库遇到的问题
QT QPushButton details
Effet Doppler (déplacement de fréquence Doppler)
14 MySQL view
Knowledge about the memory size occupied by the structure
PV静态创建和动态创建
Problems encountered in the database
时区的区别及go语言的time库
How to rotate the synchronized / refreshed icon (EL icon refresh)
openssl-1.0.2k版本升级openssl-1.1.1p
20220703 week race: number of people who know the secret - dynamic rules (problem solution)
Choose to pay tribute to the spirit behind continuous struggle -- Dialogue will values [Issue 4]
Priority queue (heap)
FFT learning notes (I think it is detailed)