当前位置:网站首页>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)
边栏推荐
- Permission problem: source bash_ profile permission denied
- 微信小程序---WXML 模板语法(附带笔记文档)
- 提升工作效率工具:SQL批量生成工具思想
- China Jinmao online electronic signature, accelerating the digitization of real estate business
- 【luogu P3295】萌萌哒(并查集)(倍增)
- My colleagues quietly told me that flying Book notification can still play like this
- 云呐|固定资产管理系统功能包括哪些?
- Senparc.Weixin.Sample.MP源码剖析
- PADS ROUTER 使用技巧小记
- FFMPEG关键结构体——AVFrame
猜你喜欢
How to get all the values stored in localstorage
MySQL之函数
Knowledge about the memory size occupied by the structure
20220703 week race: number of people who know the secret - dynamic rules (problem solution)
C reflection and type
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
数据库遇到的问题
【DesignMode】组合模式(composite mode)
MySql——CRUD
China Jinmao online electronic signature, accelerating the digitization of real estate business
随机推荐
亲测可用fiddler手机抓包配置代理后没有网络
Key structure of ffmpeg - avformatcontext
QT--线程
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
用列錶初始化你的vector&&initializer_list簡介
多普勒效應(多普勒頻移)
15 MySQL stored procedures and functions
Huawei equipment is configured with OSPF and BFD linkage
【二叉搜索树】增删改查功能代码实现
Effet Doppler (déplacement de fréquence Doppler)
Configuring OSPF GR features for Huawei devices
2022.7.5-----leetcode. seven hundred and twenty-nine
Priority queue (heap)
Recognize the small experiment of extracting and displaying Mel spectrum (observe the difference between different y_axis and x_axis)
MySql——CRUD
Hardware and interface learning summary
[SQL] SQL expansion languages of mainstream databases (T-SQL, pl/sql, pl/pgsql)
14 MySQL view
Qt QPushButton详解
软件测试工程师必会的银行存款业务,你了解多少?