题面：http://codeforces.com/contest/785/problems
A. Anton and Polyhedrons
题意：签到题。
解法：读入字符串加权值即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
const int maxn = 2e5 + 10;
int q[100];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
q['T' - 'A'] = 4;
q['C' - 'A'] = 6;
q['O' - 'A'] = 8;
q['D' - 'A'] = 12;
q['I' - 'A'] = 20;
int ans = 0;
while(n--)
{
string s; cin >> s;
ans += q[s[0] -'A'];
}
cout << ans << endl;
}
B. Anton and Classes
题意：Anton需要上一节围棋课和一节程序设计课，选其中两节课使得下课时长最长。
解法：分别保存两种课的最早下课和最晚上课时间。减一减取个最大值就好了。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
using namespace std;
int n, m;
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
scanf("%d", &n);
int a = 0, b = INT_MAX, c = 0, d = INT_MAX;
for (int i = 0; i < n; i++)
{
int x, y;
scanf("%d%d", &x, &y);
a = max(a, x);
b = min(b, y);
}
scanf("%d", &m);
for (int i = 0; i < m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
c = max(c, x);
d = min(d, y);
}
int ans = 0;
ans = max(max(a - d, c - b), ans);
printf("%d\n", ans);
}
C. Anton and Fairy Tale
题意：有一张网能存放n粒谷物，每天早上会有人来补充m粒谷物，第i天晚上会有麻雀叼走i粒谷物。求第几天这张网的谷物会被叼完。
解法：二分答案。
如果m>=n，直接输出n。
else
显然前m天是没有用的，因为叼走的粮食第二天又会被补充满。到了第m+1天，早上补充满，晚上会被叼走m+1粒，第二天补充m粒相当于少了一粒。
故对于第m天后的第j天，谷物少的量是$\sum_{i=1}^{j - 1}i$然后这一天麻雀又回叼走m+j粒谷物，所以只要比较两者的和n的大小就可以了。
但由于数据范围较大达到1e18，所以直接求和会爆long long
这里提供两种解决方案。
第一种，由于右边的值一定不会爆int，所以只需要用这个值去除以看结果是不是大于即可。
第二种，先讲n减掉m，二分上界取2e9即可。
这题虽然思路不难，但是实现起来不是很顺手。想着python不会爆精度，但好像还是因为精读问题写了好久。给出python和cpp两种代码。
‘//‘是正确的python整数除法emmmm我太naive了1
2
3
4
5
6
7
8
9
10
11
12
13n, m = map(int, input().split())
if m>=n:
print(n)
else:
l = 1
r = 2000000000
for i in range(100):
mid = (l + r) // 2
if(((mid) * (mid + 1)) // 2 + m >= n):
r = mid
else:
l = mid
print(m + r)
1 |
|
D. Anton and School - 2
题意：给你一个由括号组成的字符串，问你其中有多少个合法的RSBS子串。左右侧有相等个数个括号的表达式。由于结果较大，输出模$10^9+7$后的结果。
解法：枚举左括号，很显然只需要左边选$i$个左括号，右边选$i+1$个右扩号，即可构成一个符合条件的RSBS字符。
设当前字符左边有A个左括号，B个右括号。
则对于当前字符有$\sum_{i=0}^{} (C_{A}^{i} + C_{B}^{i + 1}) = \sum_{i=0}^{} (C_{A}^{i} + C_{B}^{B - i - 1})$
这里涉及一个组合数学的公式。
范德蒙德恒等式：$\sum_{i=0}^{k} C_{n}^{i} + C_{m}^{k - i} = C_{n + m}^{k}$
理解起来也比较容易，要从A班n个人取i个，B班m个人取j个，i和j之和为k，等价于从两个班中取k个人。
从而我们就将问题转换为求组合数$C_{A+B}^{B-1}$
学习一个由费马小定理来的乘法逆元求组合数。预处理出阶乘，然后将除法转换为乘法取模。
除法取模转换为求(a∗(b的逆元)%p)。那么就可以转换为求一个数的逆元的问题，利用费马小定理，b的逆元是b^(p-2)，那么利用快速幂定理就可以求解。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
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
using namespace std;
const int maxn = 2e5 + 10;
const int MOD = 1e9 + 7;
int l[maxn], r[maxn];//l[i]表示左侧的左括号个数，r[i]表示右侧的右括号个数
ll fac[maxn];
ll quickmod(ll a, ll b)//快速幂
{
ll res = 1;
while(b)
{
if(b & 1)
res *= a;
a = a * a % MOD;
b >>= 1;
res %= MOD;
}
return res;
}
ll C(ll a, ll b)
{
if(b > a || b < 0) return 0;
ll s1 = fac[a], s2 = fac[a - b] * fac[b] % MOD;
return s1 * quickmod(s2, MOD - 2) % MOD;//乘法逆元求组合数取模
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
string s;
cin >> s;
int len = s.length();
for(int i = 1; i < len; i++)
{
if(s[i - 1] == '(')
l[i]++;
l[i] += l[i - 1];
}
for(int i = len - 2; i >= 0; i--)
{
if(s[i + 1] == ')')
r[i]++;
r[i] += r[i + 1];
}//预处理出括号个数
fac[0] = fac[1] = 1;
for(int i = 2; i <= len; i++)
fac[i] = fac[i - 1] * i % MOD;
ll ans = 0;
for(int i = 0; i < len; i++)
{
if(s[i] == ')') continue;
ans += C(l[i] + r[i], r[i] - 1);
ans %= MOD;
}
cout << ans << endl;
return 0;
}
E. Bear and Company
题意：初始是一个从1-n的n个数排列，现进行q次操作，每次操作交换序列中的两个元素。
对于每次操作后的序列，输出逆序对的个数。
解法：分块
学习一种新的姿势分块，对于区间的奇怪的查询修改可以使用分块的策略。
顾名思义，就是将序列分成若干块，对于每次需要进行的修改，如果是一整块的就整块处理，对于其他部分暴力修改即可。这样的复杂度可以由n下降到$log(n)$
对于本题，为了知道每次修改后逆序对的变化。我们发现只有在这两个位置之间的数才会对逆序对的个数产生影响。如果小于左边的数，那么交换后逆序对减1，大于则加一。右边的数亦然。所以我们就把问题转化为快速求得区间内小于和大于左右边界的数的个数。
首先分块，对于块内的元素我们始终确保其有序，这样对于完整的块，可以二分进行查找。
对于块外的元素，直接暴力。复杂度为$O(q \cdot log(n) \cdot sqrt(n))$
每次修改的时候也是用二分进行插入排序。具体细节见代码。很巧妙的实现。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
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
ll ans;
int n, q;
int loc[maxn];
int L[maxn], R[maxn];//第i块的左边界和右边界
vector<int> blo[maxn];//每一块的各个元素
void init()
{
int len = sqrt(n);
int num = n / len;
if(n % len) num++;
for(int i = 1; i <= n; i++)
loc[i] = (i - 1) / len + 1;
for(int i = 1; i <= num; i++)
{
L[i] = (i - 1) * len + 1;
R[i] = i * len;
}
for(int i = 1; i <= num; i++)
for(int j = L[i]; j <= R[i]; j++)
blo[i].push_back(j);
}
int query(int l, int r, int key)//查询[l, r]内小于key的元素个数
{
if(l > r) return 0;
int res = 0;
if(loc[l] == loc[r])//如果在同一块内
{
for(int i = l; i <= r; i++)
if(a[i] < key)
res++;
return res;
}
for(int i = l; i <= R[loc[l]]; i++)//左侧部分块内小于key的元素
if(a[i] < key)
res++;
for(int i = L[loc[r]]; i <= r; i++)//右侧部分块内小于key的元素
if(a[i] < key)
res++;
for(int i = loc[l] + 1; i < loc[r]; i++)//整块处理部分
res += upper_bound(blo[i].begin(), blo[i].end(), key) - blo[i].begin();
return res;
}
void update(int l, int r)
{
int u = a[l], v = a[r];
int id = loc[l];
swap(a[l], a[r]);
blo[id].erase(lower_bound(blo[id].begin(), blo[id].end(), u));
blo[id].insert(upper_bound(blo[id].begin(), blo[id].end(), v), v);
id = loc[r];
blo[id].erase(lower_bound(blo[id].begin(), blo[id].end(), v));
blo[id].insert(upper_bound(blo[id].begin(), blo[id].end(), u), u);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
init();
for(int i = 1; i <= n; i++)
a[i] = i;
while(q--)
{
int l, r;
cin >> l >> r;
if(l == r)
{
cout << ans << endl;
continue;
}
if(l > r)
swap(l, r);
int t1 = query(l + 1, r - 1, a[l]);//区间内比a[l]小的数
int t2 = r - 1 - l - t1;
ans = ans - t1 + t2;
t1 = query(l + 1, r - 1, a[r]);//区间内比a[r]小的数
t2 = r - 1 - l - t1;
ans = ans - t2 + t1;
if(a[l] < a[r]) ans++;//判断两侧是否能形成逆序对
else ans--;
cout << ans << endl;
update(l, r);
}
return 0;
}