当前位置：首页 > news >正文

CF1349

news 2025/9/25 19:35:17

今天又来水博客了（雾）

A.Orac and LCM

计算给定序列中所有元素两两最小公倍数组成的集合的最大公约数。

处理一下式子就可以得到

\(\dfrac {\gcd(\lbrace a_i*a_j \space \vert \space i<j\rbrace)} {\gcd(a_1,a_2\ldotp\ldotp\ldotp a_n)}\)

下面的直接求，上面的枚举一维，剩下一维前缀 \(\gcd\) 即可

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200005],sum[200005],ans;
signed main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];sum[i]=__gcd(sum[i-1],a[i]);}for(int i=1;i<=n;i++){ans=__gcd(ans,a[i]*sum[i-1]);}cout<<ans/sum[n];
}

B.Orac and Medians

给你一个序列，你每次可以选择一个区间，让这个区间内的所有数全部变成这个区间的中位数，你需要回答最后是否能够将整个序列全部变为 k 。

发现两条性质：

如果有两个相邻的同样大小的数，那么就可以不断向两边拓展，如果有两个相隔一个的同样大小的也是
如果两个数去中位数，最后都会变成较小的数

那我们直接让任意一个k左边或右面是比它大的数字即可，那就判断一下是否可以让大于它的数不断拓展就做完了

还有个特判具体看代码

code:

#include<bits/stdc++.h>
using namespace std;
int T,n,k,a[100005];
int main(){cin>>T;while(T--){cin>>n>>k;bool flag=1;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]==k)flag=false;}a[n+1]=0;if(flag){cout<<"no"<<endl;continue;}if(n==1){cout<<"yes"<<endl;continue;}for(int i=2;i<=n;i++){if(a[i-1]>=k&&a[i+1]>=k||a[i]>=k&&a[i-1]>=k){cout<<"yes"<<endl;break;}if(i==n)cout<<"no"<<endl;}}
}

C.Orac and Game of Life

每个格子在每一时间如果周围有相同颜色的话就会取反，每次询问一个格子在某一时间的颜色

发现每一联通块都会振动，并连带着周围的落单的格子一起加入

bfs出联通块，然后找出一个格子被并入哪个联通块，什么时候并入的，连通块初始颜色为什么就好了

code:

int n, m, q;
char s[1010][1010];
int bel[1010][1010];
int tim[1010][1010];
struct Node {int x, y;Node() {}Node(int x, int y):x(x), y(y) {}
};
queue<Node>Q;
inline int chk(Node x) {return 1 <= x.x && x.x <= n && 1 <= x.y && x.y <= m;
}
int main() {memset(bel, -1, sizeof(bel));scanf("%d%d%d", &n, &m, &q);for(int i = 1; i <= n; i++)scanf("%s", s[i] + 1);for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) {int tmp = 0;tmp |= s[i][j] == s[i - 1][j];tmp |= s[i][j] == s[i + 1][j];tmp |= s[i][j] == s[i][j - 1];tmp |= s[i][j] == s[i][j + 1];if(tmp) {bel[i][j] = s[i][j] - 48;Q.push(Node(i, j));}}while(!Q.empty()) {Node x = Q.front(); Q.pop();Node t;t = Node(x.x + 1, x.y);if(chk(t) && bel[t.x][t.y] == -1) Q.push(t), bel[t.x][t.y] = bel[x.x][x.y], tim[t.x][t.y] = tim[x.x][x.y] + 1;t = Node(x.x - 1, x.y);if(chk(t) && bel[t.x][t.y] == -1) Q.push(t), bel[t.x][t.y] = bel[x.x][x.y], tim[t.x][t.y] = tim[x.x][x.y] + 1;t = Node(x.x, x.y + 1);if(chk(t) && bel[t.x][t.y] == -1) Q.push(t), bel[t.x][t.y] = bel[x.x][x.y], tim[t.x][t.y] = tim[x.x][x.y] + 1;t = Node(x.x, x.y - 1);if(chk(t) && bel[t.x][t.y] == -1) Q.push(t), bel[t.x][t.y] = bel[x.x][x.y], tim[t.x][t.y] = tim[x.x][x.y] + 1;}while(q--) {int x = ri, y = ri;ll k = rl;if(bel[x][y] == -1 || k < tim[x][y]) putchar(s[x][y]);else putchar(48 | (bel[x][y] ^ (k & 1)));puts("");}
}