ARC#137 题解

First Post:

Last Update:

ARC#137 A#

给定 , 求 .

考察到答案看上去就不大, 可以暴力枚举答案再枚举左端点判定.

时间复杂度 , 可以通过.

1
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
#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define uf(i,x,y) for(int i=x, i##end=y; i<i##end; ++i)
#define ll long long
#define pir pair<int, int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back 
char ch;
int rd() {
  int f=1, x=0; ch=getchar();
  while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
  while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
  return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
ll gcd(ll x, ll y) {
  return x==0?y:gcd(y%x, x);
}
ll L, R, ans;
int main() {
  cin >> L >> R;
  // cerr << gcd(L, R) << endl;
  ans = R-L;
  for(; ans; --ans) {
    for(ll x=L; x<=R-ans; ++x) { ll y=x+ans; if(gcd(x, y) == 1) { cout << ans << endl; return 0; }}v
  }
  return 0;
}

ARC#137 B#

令 .

那么对 做操作减少的 1 的个数就是

也即求有多少种不同的 . 使用你喜欢的算法即可.

1
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
#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define uf(i,x,y) for(int i=x, i##end=y; i<i##end; ++i)
#define ll long long
#define pir pair<int, int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back 
char ch;
int rd() {
  int f=1, x=0; ch=getchar();
  while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
  while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
  return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
#define _ 300005
int mn, mx, sufmin, sufmax, a[_], s[_], n;
int main() {
  rd(n); f(i,1,n) { rd(a[i]); s[i]=s[i-1]+2*a[i]-1; }
  f(i,1,n) {
    sufmin=min(s[i], sufmin);
    sufmax=max(s[i], sufmax);
    mx = max(mx, s[i] - sufmin);
    mn = min(mn, s[i] - sufmax);
  }
  // cerr << mn << ' ' << mx << endl;
  cout << mx - mn + 1 << endl;
  return 0;
}

ARC#137 C#

给定长度为 的序列 , Alice, Bob 轮流在这个序列上操作, 一次操作是把 中最大的数替换成一个小于它且没有在 中出现过的非负整数. 不能行动者输, 问先手是否有必胜策略.

不妨先考察 时的情况. 有以下结论:

  • 若 , 则先手必胜(考虑到 时可以把 变为 ).
  • 否则若 , 则后手必胜当且仅当 . (由 的情况猜测得到)

对 施数学归纳法, 的情况是易于验证的. 接下来考察 时的情况.

如果 , 那么一次操作可以令 , 这样无论 的奇偶性如何, 这次操作后的最大数的奇偶性是任选的. 由归纳假设可知此时命题正确.

否则有 , 那么由归纳假设可以推知下次操作必然是令 . 由归纳假设知命题在此时仍然成立.

我们推测对于 更大时候的情况, 有以下结论:

  • 若 , 则先手必胜.

  • 若 , 则后手必胜当且仅当 (由 的情况可知).

我们再次对 施数学归纳法. 的情况是易于验证的. 接下来考察 时的情况.

如果 , 那么一次操作可以令 , 这样无论 的奇偶性如何, 这次操作后的最大数的奇偶性是任选的. 由归纳假设可知此时命题正确.

否则有 , 由归纳假设可知这次操作后序列中必然存在 . (要么原本序列中不存在 而这次操作令 , 要么原本序列中已经存在 , 这次操作令 变为多少不重要) 由归纳假设知命题在此时仍然成立.

1
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
#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define uf(i,x,y) for(int i=x, i##end=y; i<i##end; ++i)
#define ll long long
#define pir pair<int, int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back 
char ch;
int rd() {
  int f=1, x=0; ch=getchar();
  while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
  while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
  return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
#define _ 300005
int a[_], n;
int main() {
  rd(n); f(i,1,n) rd(a[i]);
  sort(a+1, a+n+1); a[0]=-1;
  if(a[n-1] + 2 <= a[n]) puts("Alice");
  else {
    puts(((a[n-1] + n)&1) ? "Alice" : "Bob");
  } 
  return 0;
}

ARC#137 D#

给定 , 长度为 的序列 . 一次操作是对于所有 , 同时令 . , 求出 次操作后的 .

不妨令 为最小的形如 的数中, 大于 和 者.

记 次操作后的序列是 , 显然有 .

记 . 考查到 , 有 .

.

做一遍类似 FWT 的高维前缀和即可.

ARC#137 F#

给定 , 在一个 的区间上有 次操作. 一次操作是独立均匀随机的选择两个 , 然后让区间 被覆盖一次.

我们称这 次操作是好的, 当且仅当不存在任何一个点被覆盖了不少于 次.

求这 次操作是好的的概率.

考察这 个区间的 个端点, 我们可以将问题转换为:

求长度为 的合法排列 的数量, 其中一个排列合法当且仅当不存在一个数 满足 .

对于每个 , 考察其在排列中作为左端点还是右端点. 把左端点当成左括号, 右端点当做右括号, 有一个 dp:

记 代表当前到第 位, 还有 个未关闭的左括号的答案. 直接 dp 即可获得一个 的做法.

考虑记 为第 个右括号左边的未关闭的左括号数. 一个右括号序列显然是唯一对应一个 的.