比赛链接 / 官方题解链接
A. Orac and Factors
Solution
$n+f(n)$ 一定是偶数，所以在第一次操作后，后面的操作都是加 $2$.
Code
>folded1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
int T, n, k;
int main(){
for(read(T); T; T--){
read(n, k);
int i = 0;
for(i = 2; i * i <= n; i++)
if(n % i == 0)
break;
if(n % i != 0) i = n;
printf("%lld\n", 1ll * n + i + 2 * (k - 1));
}
return 0;
}
|
B. Orac and Models
Solution
设 $dp[i]$ 为考虑前 $i$ 个数且选了第 $i$ 个数的最大长度，转移很简单。
Code
>folded1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 100005;
int T, n, s[N], dp[N];
int main(){
for(read(T); T; T--){
read(n);
for(int i = 1; i <= n; i++)
read(s[i]), dp[i] = 0;
int ans = 0;
for(int i = 1; i <= n; i++){
dp[i] = 1;
for(int j = 1; j * j <= i; j++)
if(i % j == 0){
if(s[i] > s[j])
dp[i] = max(dp[i], dp[j] + 1);
if(s[i] > s[i/j])
dp[i] = max(dp[i], dp[i/j] + 1);
}
ans = max(ans, dp[i]);
}
printf("%d\n", ans);
}
return 0;
}
|
C. Orac and LCM
Solution
把所有数分解质因数，对于质因子 $x$，设 $a$ 是含有 $x$ 最小次数的数，次数为 $r$（$r\geq0$）；$b$ 是含有 $x$ 次小次数的数，次数为 $s$（$s\geq0$），即 $x^r|a,x^s|b$. 那么 $x$ 对答案的贡献为 $x^s$.
因为 $a$ 和 $b$ 的 $\mathrm{lcm}$ 含有 $x$ 的次数是 $s$，而其他数对含有 $x$ 的次数一定更大，所以最后求出的 $\gcd$ 含有 $x$ 的次数就是 $s$.
Code
>folded1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 100005;
int n, a, mx;
multiset<int> s[200005];
LL ans = 1;
LL fpow(LL bs, LL idx){
LL res = 1;
while(idx){
if(idx & 1) res *= bs;
bs *= bs;
idx >>= 1;
}
return res;
}
int main(){
read(n);
for(int i = 1; i <= n; i++){
read(a);
mx = max(mx, a);
for(int j = 2; j * j <= a; j++){
if(a % j == 0){
int c = 0;
while(a % j == 0){
c++;
a /= j;
}
s[j].insert(c);
}
}
if(a != 1) s[a].insert(1);
}
for(int i = 2; i <= mx; i++){
if(s[i].size() < n - 1) continue;
else if(s[i].size() == n - 1)
ans *= fpow(i, *s[i].begin());
else{
s[i].erase(s[i].begin());
ans *= fpow(i, *s[i].begin());
}
}
printf("%lld\n", ans);
return 0;
}
|
Solution
首先，如果没有 $k$ 这个数，肯定是 no。
然后有一个结论：答案存在的充要条件是存在两个下标相差不超过 $2$ 的数均大于等于 $k$。手玩一下发现应该是对的。
特判一下 $n=1$.
Code
>folded1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 100005;
int T, n, k, a[N];
int main(){
for(read(T); T; T--){
bool ok = false;
read(n, k);
for(int i = 1; i <= n; i++){
read(a[i]);
if(a[i] == k) ok = true;
}
if(!ok){ puts("no"); continue; }
ok = false;
if(n == 1){ puts("yes"); continue; }
for(int i = 1; i <= n; i++){
if(a[i] >= k){
if(i > 1 && a[i-1] >= k){
ok = true;
break;
}
if(i > 2 && a[i-2] >= k){
ok = true;
break;
}
}
}
puts(ok ? "yes" : "no");
}
return 0;
}
|
E. Orac and Game of Life
Solution
如果一个位置在某时刻变色了，那么它在之后的每一秒一定都会变色（比较显然）。所以我们只需要找到每一个位置第一次变色是什么时候。
如果一个位置没有变色，说明此时它周围都是异色，那么它变色的时刻就是它周围的异色方块中最小的变色时刻+1。所以说，以第一秒就会变色的点为源跑一个 $bfs$ 即可得到所有点的第一次变色时刻。
对每一个询问，如果 $p$ 小于它的变色时刻，那么颜色还是原来的原色；否则，奇偶性判断一下颜色即可。
特判一下没有会变色的点的情况。
Code
>folded1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 1005;
int n, m, t, dis[N][N];
char g[N][N];
bool tag[N][N];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
inline bool valid(int x, int y){
return x >= 1 && x <= n && y >= 1 && y <= m;
}
int main(){
read(n, m, t);
for(int i = 1; i <= n; i++) scanf("%s", g[i]+1);
queue<pii> q;
bool allbad = true;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
tag[i][j] = 0;
if(i > 1 && g[i-1][j] == g[i][j]) tag[i][j] = 1;
if(i < n && g[i+1][j] == g[i][j]) tag[i][j] = 1;
if(j > 1 && g[i][j-1] == g[i][j]) tag[i][j] = 1;
if(j < m && g[i][j+1] == g[i][j]) tag[i][j] = 1;
if(tag[i][j]) q.push(mp(i, j)), allbad = false;
}
}
while(!q.empty()){
pii cur = q.front(); q.pop();
for(int i = 0; i < 4; i++){
int tx = cur.first + dx[i], ty = cur.second + dy[i];
if(valid(tx, ty) && !dis[tx][ty] && !tag[tx][ty]){
dis[tx][ty] = dis[cur.first][cur.second] + 1;
q.push(mp(tx, ty));
}
}
}
while(t--){
int i, j; LL p; read(i, j, p);
if(allbad || p < dis[i][j]) putchar(g[i][j]);
else{
if((dis[i][j] - p) % 2 == 0) putchar(g[i][j]);
else putchar(((g[i][j] - '0') ^ 1) + '0');
}
puts("");
}
return 0;
}
|