codeforces hello 2019
tags:
- codeforces
- dp
- acm
- ACM
好久没玩cf了，竟然还能涨分（虽然我用的小号Orz)
三题，D应该是数学+DP…数学实在是忘干净了。。。
前面三题大体还好，都是1A,不过因为没有提前配置环境。。耽误了一些时间。。。
A:给出一个扑克牌x，和另一个包含5个扑克牌的集合。问扑克牌x是否和扑克牌集合中至少一张扑克牌的花色或者数字相同。
不多说了。
B:一块钟表（只有一个指针），初始指向12点，需要拨动指针恰好n次(n<=15)，每次可能顺时针，也可能逆时针，拨动的角度范围在[1,180],问是否有一种方案，使得拨动n次后，指针回到12点。
思路：观察下数据范围,n最大才15，最多也不过2^15的情况…既然如此，不如暴力。
枚举的话我记得有三种方法来着。。。但是已经不记得怎么写了。。所以用了最朴素的办法。。。
1#include <bits/stdc++.h>
2using namespace std;
3const int inf = 0x3f3f3f3f;
4#define ms(a,x) memset(a,x,sizeof(a))
5typedef long long LL;
6int n;
7int a[30];
8vector<int>bin;
9void cal( int x)
10{
11 bin.clear();
12 while (x>0)
13 {
14 bin.push_back(x%2);
15 x/=2;
16 }
17 while (bin.size()<n)
18 {
19 bin.push_back(0);
20 }
21}
22int main()
23{
24 cin>>n;
25 for ( int i = 1 ; i <= n ; i++) cin>>a[i];
26 if (n==1)
27 {
28 puts("NO");
29 return 0;
30 }
31 int total = 1 << n;
32 for ( int i = 0 ; i < total ; i++)
33 {
34 cal(i);
35 int ang = 0;
36 // for ( auto x : bin) cout<<x;
37 // cout<<"bin size:"<<bin.size()<<endl;
38 for ( int j = 0 ; j < bin.size() ; j++ )
39 {
40 int x = bin[j];
41 // cout<<"x:"<<x;
42 if (x==0) ang = ang + a[j+1];
43 else ang = ang - a[j+1];
44 }
45 // cout<<endl;
46 if (ang0==0)
47 {
48 puts("YES");
49 return 0;
50 }
51 // cout<<endl;
52 }
53 puts("NO");
54
55
56
57
58
59
60 return 0;
61}
C: 给出n(n<=1E5)个括号序列,括号序列可能不合法，现在要从这n个括号序列中，组成尽可能多的有序二元组，使得有序二元组的括号序列合法，并且每个括号序列只能出现在一个有序二元组中，现在问最多能组成多少这样的有序二元组。
思路：我们先考虑一下怎样的两个括号序列组成的有序二元组才是合法的有序序列。容易想到的是，如果两个括号序列本身都是合法的，那么组合在一起也一定是合法的。进一步，对于本身不合法的括号序列，容易知道，其必须只有一种没有完成匹配的括号方向，且该括号方向的数量与相反括号方向的数量相同，才能完成匹配。
因此做法是，对于括号序列预处理，得到该括号序列的状态（本身匹配为0，正数代表’(‘的个数，负数代表’)‘的个数，如果有两个方向同时存在，则直接舍弃掉，因为这种括号序列不可能组成合法的括号序列。预处理之后，用multiset搞一下。
代码写得比较乱…flag存的时候其实没必要存index…
1#include <bits/stdc++.h>
2using namespace std;
3const int inf = 0x3f3f3f3f;
4#define ms(a,x) memset(a,x,sizeof(a))
5typedef long long LL;
6const int N=1E5+7;
7int n;
8string st[N];
9// 0 for just ok, '-' for num of ), '+' for num of (
10vector< pair<int,int> >flag; // <id,state>
11
12
13void solve(int index,string str)
14{
15 stack<char>S;
16 for ( auto ch : str)
17 {
18 if (S.empty())
19 {
20 S.push(ch);
21 continue;
22 }
23 if (S.top()=='('&&ch==')')
24 {
25 S.pop();
26 continue;
27 }
28 S.push(ch);
29 // cout<<"S.size():"<<S.size()<<endl;
30
31 }
32 if (S.empty()) //自己匹配
33 {
34 flag.push_back(make_pair(0,index));
35 // cout<<"empty stack here . just match"<<endl;
36 return;
37 }
38 int state = 0;
39 // cout<<"S.size():"<<S.size()<<endl;
40 int siz = S.size();
41 while (!S.empty())
42 {
43 char x = S.top();
44 // cout<<"x:"<<x<<endl;
45 S.pop();
46 if (state==0)
47 {
48 if (x=='(') state = 1;
49 else state = -1;
50 }
51 else
52 {
53 if (state==1&&x==')') return ;
54 if (state==-1&&x=='(') return;
55 }
56 }
57 state = state*siz;
58 // cout<<"state in function"<<state<<endl;
59 flag.push_back(make_pair(state,index));
60}
61int main()
62{
63 cin>>n;
64 for ( int i = 1; i <= n ; i++) cin>>st[i];
65
66 for ( int i = 1; i <= n ; i++)
67 {
68 solve(i,st[i]);
69 }
70 if (flag.size()==0)
71 {
72 puts("0");
73 return 0;
74 }
75 int ans = 0 ;
76 int cnt = 0;
77 // cout<<"flag size:"<<flag.size()<<endl;
78 for ( auto pi:flag)
79 {
80 // cout<<"state:"<<pi.first<<endl;
81 if (pi.first==0) cnt++;
82 }
83 ans = ans + cnt/2;
84 multiset<int>posi,nega;
85 set<int>setposi;
86 for (auto pi:flag)
87 {
88 if (pi.first>0) {
89 posi.insert(pi.first);
90 setposi.insert(pi.first);
91 }
92 else if (pi.first<0) nega.insert(pi.first);
93 }
94 for ( auto x:setposi)
95 {
96 int tmp = min(posi.count(x),nega.count(-x));
97 if (tmp==0) continue;
98 // coutcoutcout<<"x:"<<x<<" "<<posi.count(x)<<" "<<nega.count(-x)<<endl;
99 ans = ans + tmp;
100 }
101 cout<<ans<<endl;
102
103
104
105 return 0;
106}
D:初始一个数n(n<=1E15)，k次操作，每次操作等概率将当前的数变为其因子中的一个。问k次操作之后，结果的期望是多少。
在@适牛的指导下，以及参考了官方题解。。写了出来。。
dp还是太弱了。。。。
比较重要的一点是，不需要考虑所有因子，只需要考虑质因子。
质因子的个数不超过50个（因为 2^50 > 1E15）
另外一个重要的是，对于每一个质因子的概率是积性函数，可以乘在一起。
因此问题变成了，对于一个质因子唯一的n，如何算所求的期望。
我们考虑dp[i][j]表示第i次操作后，质因子还剩j个的概率。
显然dp[0][tot]=1，其中 p^tot = n,p为某个质因子。
转移方程为：
dp[i][j] = sum(dp[i-1][jj]) (j=<jj<=tot)
然后最后结果的期望就是：sum(dp[k][j]*p^j) (0=<j<=tot)
还有一点，由于题目的输出要求，需要用到费马小定理求个逆元。。。
逆元相关的参考 acdreamer的博客。。。
1#include <bits/stdc++.h>
2using namespace std;
3typedef long long LL;
4const int mod = 1E9 + 7;
5
6LL n;
7int k;
8vector<pair<LL, int>> fac; //分解质因数
9
10int mul(LL a, LL b)
11{
12 // cout<<"a:"<<a <<" b:"<<b<<" a*b "<< (int)((LL)a * b % mod)<<endl;
13 return (int)((LL)a * b % mod);
14}
15void add (int &a,int b)
16{
17 // cout<<"a:"<<a<<" b:"<<b<<endl;
18 a = a + b;
19 if (a>=mod) a-=mod;
20}
21
22int ksm(int a, LL b)
23{
24 int ret = 1;
25 while (b > 0)
26 {
27 if (b & 1)
28 ret = mul(ret, a);
29 a = mul(a, a);
30 b = b >> 1;
31 }
32 return ret;
33}
34int inv(int a)
35{
36 return ksm(a, mod - 2);
37}
38
39int main()
40{
41 cin >> n >> k;
42 for (LL i = 2; i * i <= n; i++)
43 {
44 int cnt = 0;
45 if (n % i == 0)
46 {
47 while (n % i == 0)
48 {
49 n /= i;
50 cnt++;
51 }
52 fac.push_back(make_pair(i, cnt));
53 }
54 }
55 if (n > 1)
56 {
57 fac.push_back(make_pair(n, 1));
58 }
59 // check
60 // for ( auto & p:fac) cout<<p.first<<" "<<p.second<<endl;
61 int ans = 1;
62 for (auto &p : fac)
63 {
64 int tot = p.second;
65 vector<vector<int>> dp(k + 1, vector<int>(tot + 1, 0));
66 dp[0][tot] = 1;
67 for (int i = 0; i < k; i++)
68 {
69 for (int j = 0; j <= tot; j++)
70 {
71 int cur = mul(dp[i][j], inv(j + 1));
72 // cout<<"cur:"<<cur<<endl
73 for (int t = 0; t <= j; t++)
74 {
75 add(dp[i+1][t],cur);
76 }
77 }
78 }
79 int sum = 0;
80 int P = 1;
81 for (int j = 0; j <= tot; j++)
82 {
83 add(sum,mul(P, dp[k][j]));
84 P = mul(P, int(p.first % mod));
85 }
86 // cout<<"sum:"<<sum<<endl;
87 ans = mul(ans, sum);
88 }
89
90 cout << ans << endl;
91 return 0;
92}