8.17DAY1

Posted on Edited on In

上午

讲二分与分治 总体感觉收获不大，他讲比较慢，我走一会思再回来继续听，发现还是在讲同一道题.....

讲的倒也不是不好，很透彻清晰，估计是对那些初中生有些关照吧

给出几道可做不太难但是需要一些前置技能和一些细节的普及组的题目

书的复制

click

二分答案，考虑如果正着搞的话，显然是前边分的书多，后边少

题目要求后边多，前边尽可能少，也就是要你倒着去搞

函数

click

考虑对两边同时开log，然后魔改

\(x^x =10^{n-1}\)，同时对两边去个\(log\)，先别管底数是谁

\(log(x^x) = log(10^{n-1}) -->x\times log(x) = (n-1)\times log(10)\)

去底数为10，此时式子转化为：\(x\times log(x) = n - 1\)

所以\(n = floor(x \times log(x) + 1)\)，然后二分在实数域求值即可

小车

click

显然是A先坐车到达某个地方，然后A往终点走，车掉头回去接B，然后一起到达终点

二分车把A送到哪里最合适即可

平面最近点对

click

分治

考虑已经在左边有了答案\(d1\),右边有了答案\(d2\),取\(d = Min(d1, d2)\)

考虑一个点与另一个点的连线跨越中间边的情况，是否可能会更新答案

考虑可能影响到答案的情况，显然，对于中间边两边水平距离为\(d\)，显然都有可能

但是这样还是不够优化，还需要继续优化

考虑\(y\)轴，对于每一个处于左边的点，还要通过\(y\)轴去判断他是否可能更新答案

我感觉我说的也不是太透彻，感觉这里挺好

传送带

click

显然最优路线是\(A-E-F-D\),其中EF均属于AB，CD

然后我就不太透彻了

影子

没有给出链接

大致就是一道数学的分类讨论题，一个人站在一个灯底下，人可以左右移动，问影子最长是多少？

1.影子不在墙上，可以通过一个典型的相似三角形求出来

2.影子一部分落到了墙上，显然不在墙上的部分等于身高，在墙上的部分可以通过两个相似三角形也能求出比例关系

下午

考试

序列

有1到n这n个整数，把这n个整数排成一行使其满足一定的条件

  • 1最长上升子序列的长度为x

  • 2最长下降子序列的长度为y

如果有多个满足要求的排列，输出字典序最小的一个

给出七十分代码

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
92
93
94
95
96
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠�
const int M = 1e5+66;

int f[M], a[M], d[M], v[M], c[M];

int n, X, Y, N, flag;

inline void dfs(int x, int k)
{
    if (flag) return;
    if (k == N)
    {
        memset(f, 0, sizeof f);
        memset(d, 0, sizeof d);
        int res1(0), res2(0), i, j;
        for (i = 1; i <= n; ++ i)
        {
            f[i] = d[i] = 1;;
            for (j = 1; j < i; ++ j) 
            {
                if (a[j] < a[i]) f[i] = max(f[j]+1, f[i]);
                if (a[j] > a[i]) d[i] = max(d[j]+1, d[i]);
            }
        }
        for (i = 1; i <= n; ++ i) 
        {
            res1 = max(res1, f[i]);
            res2 = max(res2, d[i]);
        }
        if (res1 == X && res2 == Y)
        {
            for (i = 1; i <= n; ++ i) c[i] = a[i];
            flag = 1;
            return ;
        }
        return;
    }
    for (int i = 1; i <= n; ++ i)
    {
        if (v[i]) continue;
        v[i] = 1;
        a[++ k] = i;
        dfs(i + 1, k);
        v[i] = 0;
        -- k;
    }
}

inline void work()
{
    dfs(1, 0);
    if (flag) {
        puts("YES");
        for (int i = 1; i <= n; ++ i) cout << c[i] << ' ';
    } else puts("NO");
}

inline int thestars()
{
    int i, j, k, n, x, y, m, res(0);
    scanf ("%d%d%d", &n, &x, &y);
    if (n <= 7) 
    {
        N = n, X = x, Y = y;
        work();
        return 0;		
    }
    m = n, k = (n - y + 1);
    for (i = k; i <= n; ++ i) a[i] = (m --);
    if (k == x)
    {
        puts("YES");
        for (i = 1; i < k; ++ i) cout << i << ' ';
        for (i = k; i <= n; ++ i) cout << a[i] << ' ';
        return 0;
    }
    if (k < x) {puts("NO");return 0;}
    int maxh = k - 1; j = maxh;
    int cha = k - x;
    int yhm = cha + 1;
    if (yhm > y) {puts("NO");return 0;}
    j -= cha;
    puts("YES");
    for (i = 1; i < j; ++ i) cout << i << ' ';
    for (i = maxh; i >= j; -- i) cout << i << ' ';
    for (i = k; i <= n; ++ i) cout << a[i] << ' ';
    return 0;
}

int youngore = thestars();

signed main() {;}

链接

​ 小王来到了一片森林，森林中有一些树和连接两棵树的无向道路。

​ 小王对这片森林做了一些考察，有了两个奇怪的发现：

​ 1）森林中的树总共分为两种，不妨记为0型树和1型树。

​ 2）这些道路的长度都是2的整数次幂且互不相同，第ii条道路的长度为\(2^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
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
92
93
94
95
96
97
#include <bits/stdc++.h>
#define LL long long
// #define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 1e5+66, mod = 1e9+7;

typedef pair<LL, int> pr;

int head[N], to[N], nex[N], cnt; LL len[N];

inline void add(int x, int y, LL z)
{
    to[++ cnt] = y;
    len[cnt] = z;
    nex[cnt] = head[x];
    head[x] = cnt;
}

inline LL ksm(LL a, LL b)
{
    LL res(1);
    for (; b; b >>= 1)
    {
        if (b&1) res = res * a;
        a = a * a;
    }
    return res;
}

priority_queue<pr, vector<pr>, greater<pr> >q;
int v[N]; LL dis[N];

inline void dij(int s)
{
    int i, x, y;
    LL z;
    memset(v, 0, sizeof v);
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0, q.push(make_pair(0, s));
    while (q.size())
    {
        z = q.top().first, x = q.top().second; q.pop();
        if (v[x]) continue;
        v[x] = 1;
        for (i = head[x]; i; i = nex[i])
        {
            y = to[i];
            if (dis[y] > z + len[i])
            {
                dis[y] = z + len[i];
                if (! v[y])
                {
                    q.push(pr(dis[y], y));
                }
            }
        }
    }
}

int a[N];

inline LL thestars()
{
    int i, x, y, n, m;
    LL z, res(0);
    scanf ("%d%d", &n, &m);
    for (i = 1; i <= n; ++ i) scanf ("%d", a + i);
    for (i = 1; i <= m; ++ i)
    {
        scanf ("%d%d", &x, &y);
        z = ksm(2, i);
        add(x, y, z);
        add(y, x, z);
    }
    for (x = 1; x <= n; ++ x)
    {
        dij(x);
        for (i = x + 1; i <= n; ++ i)
        {
            // if (i == x) continue;
            // if (x == 2 && y == 3) cout << "herre\n";
            // if (i < x || a[x] == a[i]) continue;
            if (a[x] == a[i]) continue;
            res = (res + dis[i])%mod;
#ifdef debug
cout << "x===>" <<x << " i---->" << i << " len[i]---->" << dis[i] << '\n';
#endif
        }
    }
    cout << res%mod;
    return 0;
}

LL youngore = thestars();

signed main() {;}

游戏

小王和小杨在二维平面上玩一个石头游戏。平面上共有nn个点供他们放置石头。当然，放石头会有一些规则限制：

​ 1）游戏开始前，石头在第一个点处

​ 2）小王和小杨交替放置石头，小王先放

​ 3）第一次放置，可以把石头放在除了第一个点之外的任何一个点处

​ 4）从第二次放置开始，假设石头当前在x号点处并且上一次石头移动的距离为d，玩家可以把石头移到y点当且仅当\(distance(x,y)>d\)并且yy点从未被放置过，注意，这里的\(distance(x,y)\)就是x,y两位置的间距，本题中的距离都采用欧几里得距离

​ 5）当一个玩家无处可放时，他输了

​ 小王和小杨都采取最优策略，请你告诉他们谁将获得胜利。

晚上

练习