当前位置:网站首页>Atcoder beginer contest 254 "e BFS" f st table maintenance differential array GCD "
Atcoder beginer contest 254 "e BFS" f st table maintenance differential array GCD "
2022-07-05 10:18:00 【Chels.】
AtCoder Beginner Contest 254
E - Small d and k
Title Description :
Here's an undirected graph , The degree of each point is at most 3, Conduct Q Time to ask , Give it every time you ask
x,k
, Means to ask withx
As a starting point , Distance less than or equal tok
Step by stepid
Andamong
k<=3
Ideas :
Because the degree is at most 3, And
k<=3
, So each inquiry involves at most 27 A little bit ,27 * Q Only then 4e6, Complexity makes sense , We run violently bfs Just go
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m, k, x, y;
vector<int>G[MAX];
bool vis[MAX];
void work(){
cin >> n >> m;
for(int i = 1; i <= m; ++i){
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
cin >> m;
while(m--){
cin >> x >> k;
if(k == 0){
cout << x << endl;
continue;
}
vector<int>v;
queue<pii>q;
q.push(m_p(x, k));
vis[x] = 1;
while(!q.empty()){
auto [u, d] = q.front();q.pop();
v.push_back(u);
// cout << u << ' ' << d << endl;
for(auto v : G[u]){
if(!vis[v] && d){
q.push(m_p(v, d - 1));
vis[v] = 1;
}
}
}
int ans = 0;
for(auto x : v){
ans += x;
vis[x] = 0;
}
cout << ans << endl;
}
}
int main(){
io;
work();
return 0;
}
F - Rectangle GCD
Title Description :
Here are two arrays
ar,br
, All the lengths aren
, Order one by onen*n
Matrix C, amongC[i][j] = ar[i] + br[j]
, Now here you areQ
Time to ask , Each time you ask, I will give you the upper left and lower right corners of a small rectangle , Ask all the elements of this small rectangle gcd
Ideas :
First of all, it should be clear that the maximum common divisor of all elements of a sequence is equal to the maximum common divisor of the difference group , namely g c d ( a [ 1 ] , a [ 2 ] , . . . , a [ n ] ) = g c d ( a [ 1 ] , a [ 2 ] − a [ 1 ] , a [ 3 ] − a [ 2 ] , . . . , a [ n ] − a [ n − 1 ] ) gcd(a[1], a[2], ...,a[n]) = gcd(a[1], a[2] - a[1], a[3] - a[2], ... ,a[n] - a[n - 1]) gcd(a[1],a[2],...,a[n])=gcd(a[1],a[2]−a[1],a[3]−a[2],...,a[n]−a[n−1])
So let's consider the first
i
That's okg c d ( a [ i ] + b [ j ] , a [ i + 1 ] + b [ j ] , a [ i + 2 ] + b [ j ] , . . . . ) = g c d ( a [ i ] + b [ j ] , a [ i + 1 ] − a [ i ] , a [ i + 2 ] − a [ i + 1 ] . . . ) gcd(a[i]+b[j], a[i + 1]+b[j], a[i + 2]+b[j],....) = gcd(a[i] + b[j], a[i + 1]-a[i], a[i + 2] - a[i + 1]...) gcd(a[i]+b[j],a[i+1]+b[j],a[i+2]+b[j],....)=gcd(a[i]+b[j],a[i+1]−a[i],a[i+2]−a[i+1]...) Let's not watch first
a[i]+b[j]
, According to the following paragraph gcd, We can do this by askinggcd(a[i+1]-a[i], a[i+2]-a[i+1]...)
Get all the numbers in the purple part of the figure below gcdEmpathy , We can use
gcd(br[i+1]-br[i], br[i+2]-br[i+1]....)
Get all the numbers in the blue part below gcdWhat we need is from
C[h1][w1]
ToC[h2][w2]
Of all numbers gcd, By synthesizing the pattern, we can find that the number in the upper left corner has not been calculated , So we only need to divide the difference between the above two partitions gcd andC[h1][w2]
That is to sayA[h1]+B[w1]
Ask for one gcd that will doSo we can use st Table to maintain the interval of the difference group gcd
To be honest, I didn't think so deeply when I wrote , I think of it.
gcd(x, y)
It can be converted intogcd(x-y, x)
, I think it's the difference groupgcd
, In addition, it is not enough to calculate the difference fraction Group , There has to be ax
, Just add the elements in the upper left corner, and the three find a gcd, Recite one st I didn't expect it to be over
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m, k, x;
ll ar[MAX];
ll br[MAX];
ll gcd(ll a, ll b){
if(b) return gcd(b, a % b);
else return a;
}
ll lg[MAX];
ll g1[MAX][22];
ll g2[MAX][22];
void init(){
for(int i = 2; i <= n; ++i){
lg[i] = lg[i / 2] + 1;
}
for(int i = 2; i <= n; ++i){
g1[i][0] = ar[i] - ar[i - 1];
g2[i][0] = br[i] - br[i - 1];
}
for(int j = 1; j <= lg[n]; ++j){
for(int i = 2; i + (1 << j) - 1 <= n; ++i){
g1[i][j] = gcd(g1[i][j - 1], g1[i + (1 << (j - 1))][j - 1]);
g2[i][j] = gcd(g2[i][j - 1], g2[i + (1 << (j - 1))][j - 1]);
}
}
}
ll get_gcd(int l, int r, int op){
ll d = lg[r - l + 1];
if(op)return abs(gcd(g1[l][d], g1[r - (1 << d) + 1][d]));
else return abs(gcd(g2[l][d], g2[r - (1 << d) + 1][d]));
}
void work(){
cin >> n >> m;
for(int i = 1; i <= n; ++i)cin >> ar[i];
for(int j = 1; j <= n; ++j)cin >> br[j];
init();
int h1, h2, w1, w2;
while(m--){
cin >> h1 >> h2 >> w1 >> w2;
ll a = 0, b = 0;
if(h1 == h2)a = 0;
else a = get_gcd(h1 + 1, h2, 1);
if(w1 == w2)b = 0;
else b = get_gcd(w1 + 1, w2, 0);
cout << gcd(a, gcd(b, ar[h1] + br[w1])) << endl;
}
}
int main(){
io;
work();
return 0;
}
边栏推荐
- Energy momentum: how to achieve carbon neutralization in the power industry?
- Zblogphp breadcrumb navigation code
- A high density 256 channel electrode cap for dry EEG
- 面试:Bitmap像素内存分配在堆内存还是在native中
- (1) Complete the new construction of station in Niagara vykon N4 supervisor 4.8 software
- 【小技巧】获取matlab中cdfplot函数的x轴,y轴的数值
- 小程序中自定义行内左滑按钮,类似于qq和wx消息界面那种
- 历史上的今天:第一本电子书问世;磁条卡的发明者出生;掌上电脑先驱诞生...
- 橫向滾動的RecycleView一屏顯示五個半,低於五個平均分布
- MySQL digital type learning notes
猜你喜欢
Redis如何实现多可用区?
宝塔面板MySQL无法启动
isEmpty 和 isBlank 的用法区别
如何写出高质量的代码?
ConstraintLayout官方提供圆角ImageFilterView
Meitu lost 300 million yuan in currency speculation for half a year. Huawei was exposed to expand its enrollment in Russia. Alphago's peers have made another breakthrough in chess. Today, more big new
uniapp + uniCloud+unipay 实现微信小程序支付功能
IDEA新建sprintboot项目
Advanced opencv:bgr pixel intensity map
一个程序员的职业生涯到底该怎么规划?
随机推荐
Singleton mode encapsulates activity management class
Unity particle special effects series - the poison spray preform is ready, and the unitypackage package is directly used - on
Design of stepping motor controller based on single chip microcomputer (forward rotation and reverse rotation indicator gear)
RMS to EAP is simply implemented through mqtt
Have you learned to make money in Dingding, enterprise micro and Feishu?
Cerebral Cortex:有向脑连接识别帕金森病中广泛存在的功能网络异常
WorkManager的学习二
面试:Bitmap像素内存分配在堆内存还是在native中
> Could not create task ‘:app:MyTest. main()‘. > SourceSet with name ‘main‘ not found. Problem repair
学习笔记5--高精地图解决方案
Personal website construction tutorial | local website environment construction | website production tutorial
如何判断线程池已经执行完所有任务了?
Fluent generates icon prompt logo widget
面试:List 如何根据对象的属性去重?
Detailed explanation of the use of staticlayout
DDOS攻击原理,被ddos攻击的现象
字节跳动面试官:一张图片占据的内存大小是如何计算
宝塔面板MySQL无法启动
官网给的这个依赖是不是应该为flink-sql-connector-mysql-cdc啊,加了依赖调
Swift saves an array of class objects with userdefaults and nssecurecoding