当前位置:网站首页>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)
边栏推荐
- 如何解决ecology9.0执行导入流程流程产生的问题
- How to get all the values stored in localstorage
- JS can really prohibit constant modification this time!
- The use of El cascader and the solution of error reporting
- 亲测可用fiddler手机抓包配置代理后没有网络
- FFMPEG关键结构体——AVFormatContext
- Laser slam learning record
- 时区的区别及go语言的time库
- Open3D 点云随机添加噪声
- [EF core] mapping relationship between EF core and C data type
猜你喜欢
云呐|固定资产管理系统主要操作流程有哪些
Tools to improve work efficiency: the idea of SQL batch generation tools
N1 # if you work on a metauniverse product [metauniverse · interdisciplinary] Season 2 S2
AtCoder Beginner Contest 254【VP记录】
Initialize your vector & initializer with a list_ List introduction
剖面测量之提取剖面数据
Upgrade openssl-1.1.1p for openssl-1.0.2k
There is no network after configuring the agent by capturing packets with Fiddler mobile phones
多普勒效應(多普勒頻移)
wx.getLocation(Object object)申请方法,最新版
随机推荐
What are the functions of Yunna fixed assets management system?
Laser slam learning record
MySQL之函数
Zero rhino technology joined hands with the intelligence Club: the "causal faction" forum was successfully held, and the "causal revolution" brought the next generation of trusted AI
15 MySQL stored procedures and functions
Open3D 点云随机添加噪声
[Luogu cf487e] tours (square tree) (tree chain dissection) (line segment tree)
【luogu CF487E】Tourists(圆方树)(树链剖分)(线段树)
XML配置文件(DTD详细讲解)
Problem solving win10 quickly open ipynb file
Asynchronous task Whenall timeout - Async task WhenAll with timeout
【QT】Qt使用QJson生成json文件并保存
FFMPEG关键结构体——AVCodecContext
Determinant learning notes (I)
Key structure of ffmpeg - avformatcontext
What is a humble but profitable sideline?
从底层结构开始学习FPGA----FIFO IP核及其关键参数介绍
Teach you to run uni app with simulator on hbuilderx, conscience teaching!!!
Global and Chinese markets of POM plastic gears 2022-2028: Research Report on technology, participants, trends, market size and share
What if the C disk is not enough? Let's see how I can clean up 25g of temp disk space after I haven't redone the system for 4 years?