退役了，很久没有写题了，打了一场cf，结果还把题意看错了，耻辱掉分。
Hello_2019_C. Yuhao and a Parenthesis
题目链接：http://codeforces.com/contest/1097
题意
给了一些由括号组成的字符串（只包含’(’ 和‘)’ 这两种括号），现在你可以将任意两个字符串按照任意的顺序拼接，使得新的括号表达式是正确的，即所有括号都能匹配，每次字符串只能使用一次，问最多能组成多少个匹配的括号表达式。
思路
答案由两部分组成，第一部分是本身就是匹配的括号表达式，它们对答案的贡献是数量的一半，因为每次都要拿两个来匹配。
第二部分是新形成的匹配的括号表示，我们知道只能由那些把表达式中已经匹配的括号删去之后最后只剩下一种括号的字符串才可能对答案造成贡献。
那么我们只需要统计删去匹配的括号后剩下的长度为 i 的字符串的数量即可。
代码
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
|
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;
int a[maxn], b[maxn];
stack<char> st;
int main(){
int n;
cin >> n;
string s;
int ans = 0;
while(n--){
cin >> s;
for(char &x : s){
if(st.empty()) st.push(x);
else if(x == ')' && st.top() == '('){
st.pop();
}else st.push(x);
}int x=0, y=0;
while(!st.empty()){
if(st.top() == '(') x++;
else y++;
st.pop();
}if(x+y==0) ans++;
else if(!x||!y) a[x]++,b[y]++;
}ans /= 2;
for(int i = 1; i < maxn; ++i)
ans += min(a[i], b[i]);
cout << ans << endl;
}
|
Hello_2019_D. Makoto and a Blackboard
题目链接：http://codeforces.com/contest/1097
题意
给定两个数n和k，每一次你可以将n替换成n的任意一个因子，包括1和n，问k轮之后答案的期望是多少
思路
n的范围很大，有1e15，所以一般都需要数学知识。
我们可以发现n的每一个质因子对不受其他因子的影响，所以我们可以考虑每一次质因子对答案的贡献。
假设质因子x出现了m次，那么我们可以算在k轮之后，x出现次数为0 ～ m次的概率，最后再算期望。
对于求概率，我们考虑递推，我们知道高次的可以转到低次。
我们令dp[i][j]表示在第 i 轮. x 出现 次数为 j 的概率
那么dp[i][j]=∑k=jmdp[i−1][k]∗k+11
代码
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
|
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
const int maxn = 100;
LL inv[maxn];
LL qpow(LL x, LL n){
LL ans = 1;
while(n){
if(n&1) ans = ans * x % mod;
x = x * x % mod;
n >>= 1;
}return ans;
}
LL dp[maxn*maxn+10][maxn];
LL solve(LL x, int k, int m){
memset(dp, 0, sizeof(dp));
dp[0][m] = 1;
for(int i = 1; i <= k; ++i)
for(int j = 0; j <= m; ++j)
if(dp[i-1][j]){
for(int l = 0; l <= j; ++l) dp[i][l] = (dp[i][l] + dp[i-1][j] * inv[j+1] % mod) % mod;
}
LL ans = 0, res = 1;
for(int i = 0; i <= m; ++i){
ans = (ans + res * dp[k][i] % mod) % mod;
res = res * x % mod;
}return ans;
}
int main(){
LL n;
int k;
inv[1] = 1;
for(int i = 2; i < maxn; ++i) inv[i] = (mod-mod/i)*inv[mod%i] % mod;
cin >> n >> k;
LL ans = 1;
for(LL x = 2; x * x <= n; ++x)if(n%x == 0){
int num = 0;
while(n%x == 0) num++, n /= x;
ans = ans * solve(x, k, num) % mod;
}if(n > 1) ans = ans * solve(n, k, 1) % mod;
cout << ans << endl;
return 0;
}
|