当前位置:网站首页>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)
边栏推荐
- [EF core] mapping relationship between EF core and C data type
- 【NOI模拟赛】Anaid 的树(莫比乌斯反演,指数型生成函数,埃氏筛,虚树)
- After summarizing more than 800 kubectl aliases, I'm no longer afraid that I can't remember commands!
- There is no network after configuring the agent by capturing packets with Fiddler mobile phones
- wx. Getlocation (object object) application method, latest version
- [binary search tree] add, delete, modify and query function code implementation
- Mathematical model Lotka Volterra
- 14 MySQL view
- FFMPEG关键结构体——AVFormatContext
- 关于结构体所占内存大小知识
猜你喜欢
【二叉搜索树】增删改查功能代码实现
亲测可用fiddler手机抓包配置代理后没有网络
"14th five year plan": emphasis on the promotion of electronic contracts, electronic signatures and other applications
单商户V4.4,初心未变,实力依旧!
openssl-1.0.2k版本升级openssl-1.1.1p
[designmode] Decorator Pattern
FFT 学习笔记(自认为详细)
Upgrade openssl-1.1.1p for openssl-1.0.2k
My colleagues quietly told me that flying Book notification can still play like this
Choose to pay tribute to the spirit behind continuous struggle -- Dialogue will values [Issue 4]
随机推荐
Open3D 点云随机添加噪声
C # input how many cards are there in each of the four colors.
[gym 102832h] [template] combination lock (bipartite game)
wx.getLocation(Object object)申请方法,最新版
MySql——CRUD
FFT learning notes (I think it is detailed)
Zhuan: in the future, such an organization can withstand the risks
There is no network after configuring the agent by capturing packets with Fiddler mobile phones
15 MySQL stored procedures and functions
Global and Chinese market of valve institutions 2022-2028: Research Report on technology, participants, trends, market size and share
妙才周刊 - 8
Key structure of ffmpeg - avframe
PV static creation and dynamic creation
第16章 OAuth2AuthorizationRequestRedirectWebFilter源码解析
Gd32f4xx UIP protocol stack migration record
Wechat applet -- wxml template syntax (with notes)
提升工作效率工具:SQL批量生成工具思想
QT QPushButton details
What is information security? What is included? What is the difference with network security?
Permission problem: source bash_ profile permission denied