Blackops

初心易得，始终难守

0%

CF #465 Div.2 A B C D E

发表于 分类于 ，

A.Fafa and his Company

题意就是给让你把$n$个人划分成$m$个同等大小的组，每个组内的人员大于$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
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);

int main(void)
{
    register int n, i;
    while (cin >> n)
    {
        int ans = 0;
        for (i = 1; i <= n - 1; ++i)
            if ((n - i) % i == 0)
                ++ans;
        cout << ans << endl;
    }
    return 0;
}

B.Fafa and the Gates

题意就是让你在第一象限走，直线$y=x$是分界线（不属于任何一国），如果从一国穿过分界线到另一个国，要付一块钱，问你会按照给定的路线走的话要付多少钱，模拟一遍，维护一下自己最后属于哪个国家，穿过的时候跟属于的国家比较一下看是否要花钱。

代码：

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
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
char s[N];
int dir[4][2] = {0, 1, 0, -1, -1, 0, 1, 0};
int id[210];

int main(void)
{
    id['U'] = 0, id['D'] = 1, id['L'] = 2, id['R'] = 3;
    register int n, i, j;
    while (cin >> n >> s)
    {
        int ans = 0;
        int belong = -1;
        int px = 0, py = 0;
        for (i = 0; i < n; ++i)
        {
            int q = id[s[i]];
            int vx = px + dir[q][0], vy = py + dir[q][1];;
            if (vx != vy)
            {
                int vbelong = vx > vy;
                if (belong != -1 && vbelong != belong)
                    ++ans;
                belong = vbelong;
            }
            px = vx, py = vy;
        }
        cout << ans << endl;
    }
    return 0;
}

C.Fifa and Fafa

题意似乎不是很好懂，看样例才弄懂，简单地说就是给你一个平面，上面有一个圆心为$(x1,y1)$（记为点$M$）半径为$R$的圆，还有一个点$(x2,y2)$（记为点$A$），让你再构造一个圆使得跟前面那个圆的面积交最大且不能包含$(x2,y2)$，输出构造的圆心$(x3,y3)$（记为点$B$）和半径$r$。

实际上只要简单地分类讨论就行了

  1. 如果点在圆外，那么肯定可以取到最优情况直接覆盖整个圆，
  2. 如果点和圆心重合，那么最优方案是构造一个半径为$R \over 2$的圆，圆心直接取$((x1+x1+R) / 2,y1)$即可，
  3. 如果点在圆内且不与圆心重合，那么只要延长圆心和该点的连线，与圆交于另一点$(x4,y4)$，那么$(x2,y2)$和$(x4,y4)$就是在圆上的两个点，相加除二得到圆心坐标，再计算其距离，除二得到半径。如何算出延长线和圆的交点呢，由于都在一条直线上，将$\vec{AM}$扩大一定倍数得到$\vec{MB}$，然后加起来就得到了$\vec{AB}$。$B$坐标就得到了

代码：

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
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 110;
const double eps = 1e-8;

double x[N], y[N], R;

inline double sqr(double x)
{
    return x * x;
}
inline double dis(double _x1, double _y1, double _x2, double _y2)
{
    return sqrt(sqr(_x1 - _x2) + sqr(_y1 - _y2));
}
int main(void)
{
    while (cin >> R >> x[1] >> y[1] >> x[2] >> y[2])
    {
        double disfa = dis(x[1], y[1], x[2], y[2]);
        if (x[1] == x[2] && y[1] == y[2])
            printf("%.16f %.16f %.16f\n", (2.0 * x[1] + R) / 2.0, y[1], R / 2);
        else if (disfa > R)
            printf("%.16f %.16f %.16f\n", x[1], y[1], R);
        else
        {
            double r = (R + disfa) / 2;
            double xa = x[1] - x[2], ya = y[1] - y[2];
            double rat = R / disfa;
            double xb = x[1] + rat * xa, yb = y[1] + rat * ya;
            printf("%.16f %.16f %.16f\n", (x[2] + xb) / 2.0, (y[2] + yb) / 2.0, fabs(r));
        }
    }
    return 0;
}

D.Fafa and Ancient Alphabet

题意就是给你字符集大小为$m$，长为$n$的两个字符串$S1$和$S2$，某一些位置不能确定，求假设把所有位置都确定之后$S1$字典序大于$S2$的概率，用逆元表示。这题实际上跟数位$DP$很像，第$i$位的贡献就是考虑前缀$S[1,i-1]$相同时，$S1$的第$i$位大于$S2$的第$i$位的几率，然后求和加起来即可。即：$ans = ans + P_p*P_g$

显然分四种情况讨论

  1. 当两者都是确定的时候，若$S1[i]>S2[i]$，$P_g=1$，否则$P_g=0$，
  2. 当$S1[i]$不确定而$S2[i]$确定时，$P_g=(m-S2[i])/m$，
  3. 当$S1[i]$确定而$S2[i]$不确定时，$P_g=(S1[i]-1)/m$，
  4. 当两个都不确定时，概率就相当于在$m$个数里先后抽两次，后者比前者大的概率，那么就是$P_g=sum_{i=0}^{m-1}(1/m)*(i/m)$，用求和公式化简一下就是$P_g=(m-1)/(2m)$

然后是如何求前缀相同的几率$P_p$呢，假设前面有$c$个不能比较的位置，那么$P_p={(1/m)}^c$，一旦出现某个位置使得这两个串包含这个前缀之后关系可以被直接确定，也就是说从这个位置开始的前缀不会再相等了，就应该直接$break$

代码：

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
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
const LL mod = 1e9 + 7;
int s1[N], s2[N];

LL qpow(LL a, LL b)
{
    LL r = 1;
    while (b)
    {
        if (b & 1)
            r = r * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return r;
}
int main(void)
{
    register int n, m, i;
    while (~scanf("%d%d", &n, &m))
    {
        for (i = 1; i <= n; ++i)
            scanf("%d", &s1[i]);
        for (i = 1; i <= n; ++i)
            scanf("%d", &s2[i]);
        register LL invm = qpow(m, mod - 2);
        register LL invsig2 = 1LL * (m - 1) * qpow(2LL * m, mod - 2) % mod;
        register LL P_p = 1;
        register LL Ans = 0;
        for (i = 1; i <= n; ++i)
        {
            LL P_g = 0;
            if (s1[i] && s2[i])
            {
                P_g = (s1[i] > s2[i]);
            }
            else if (!s1[i] && s2[i])
            {
                P_g = (P_g + 1LL * (m - s2[i]) * invm % mod);
            }
            else if (s1[i] && !s2[i])
            {
                P_g = (P_g + 1LL * (s1[i] - 1) * invm) % mod;
            }
            else
            {
                P_g = (P_g + invsig2) % mod;
            }
            Ans += P_p * P_g;
            Ans %= mod;
            if (!s1[i] || !s2[i])
                P_p = P_p * invm % mod;
            if (s1[i] && s2[i] && (s1[i] != s2[i]))
                break;
        }
        printf("%I64d\n", Ans);
    }
    return 0;
}

E.Fafa and Ancient Mathematics

题意就是给你一串含有括号和数字，未知运算符的表达式，数字的范围是$[0,9]$，求用$P$个加号，$M$个减号补全这些未知运算符之后最大的表达式的值。

很显然可以看出来是树形$DP$，而且跟表达式树有关，但是并不知道怎写，参考了一下别人的代码，用递归做的，每次找到左右两个部分，处理完左边再处理右边，设在表达式树上的结点为$k$，枚举当前子树用的符号个数，枚举左子树用的符号个数，就可以在树上$DP$，转移方程：

由于字符个数比较多，第二维就只记录比较少的那个。

代码：

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
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e4 + 7;
const int M = 105;
char s[N];
int Min[N][M], Max[N][M], sz, bpos[N], cnt, flag;

stack<int>st;

void init()
{
    sz = 0;
    CLR(Min, INF);
    CLR(Max, -INF);
    while (!st.empty())
        st.pop();
}
int solve(int l, int r)
{
    int k = ++sz;
    if (l == r)
        Max[k][0] = Min[k][0] = s[l] - '0';
    else
    {
        int rpos = (s[l + 1] == '(') ? bpos[l + 1] + 1 : l + 2;
        int ls = solve(l + 1, rpos - 1), rs = solve(rpos + 1, r - 1);
        //加号
        for (int j = flag; j <= cnt; ++j)//用了j个
        {
            for (int lj = 0; lj + flag <= j; ++lj)//左边用了lj个
            {
                Max[k][j] = max(Max[k][j], Max[ls][lj] + Max[rs][j - flag - lj]);
                Min[k][j] = min(Min[k][j], Min[ls][lj] + Min[rs][j - flag - lj]);
            }
        }
        //减号
        for (int j = flag ^ 1; j <= cnt; ++j)//用了j个
        {
            for (int lj = 0; lj + (flag ^ 1) <= j; ++lj)//左边用了lj个
            {
                Max[k][j] = max(Max[k][j], Max[ls][lj] - Min[rs][j - (flag ^ 1) - lj]);
                Min[k][j] = min(Min[k][j], Min[ls][lj] - Max[rs][j - (flag ^ 1) - lj]);
            }
        }
    }
    return k;
}
int main(void)
{
    int cdel, cadd, i;
    while (~scanf("%s%d%d", s + 1, &cadd, &cdel))
    {
        init();
        int len = strlen(s + 1);
        flag = cadd < cdel;//用加号为1，减号为0
        for (i = 1; i <= len; ++i)
        {
            if (s[i] == '(')
                st.push(i);
            else if (s[i] == ')')
                bpos[st.top()] = i, st.pop();
        }
        cnt = min(cdel, cadd);
        int rt = solve(1, len);
        printf("%d\n", Max[rt][cnt]);
    }
    return 0;
}