今天又来水博客了(雾)
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("");}
}
D.Slime and Biscuits
神秘鞅与停时定理与势能函数法,还是黑,也不知道这辈子会不会学这个(逃)
E.Slime and Hats
神秘经典游戏,挺有意思的 但策略没看懂...
挖个坑以后填
F2.Slime and Sequences (Hard Version)
(F1和F2只差数据范围与时限)
前置芝士:
- 分式域
- (扩展)拉格朗日反演
- 欧拉数
- 二元 GF
让我做这个?别闹了(再逃)
完结撒花
我怎么还是这么菜
被黑题爆杀了呜呜呜