So I'll Max Out My Constructive Algor...

2022-04-12

题目大意

给定一个$n*n$的数字矩阵，代表每个点的高度，每个数各不相同，求一条遍历所有的点的路径，要求只能上下左右移动，且高度下降的次数不小于高度上升次数。

more >>

展开全文 >>

LOJ6678 礼物

2022-04-06

题目链接

思路

题目要求在树上求最短路，我们很容易想到LCA来解决。

但问题我们需要同时计算能获得的最大值，所以我们需要额外的倍增数组来维护一些值。

那么具体是什么呢？

假设我们从$x$点出发，到达$LCA(x,y)$的时候，进行了买入操作，在$LCA(x,y)$到$y$的路上，进行了卖出操作，那么我们就需要直到$x-LCA(x,y)$上的最大值，$LCA(x,y)-y$上的最小值。所以我们需要两个倍增数组，一个$maxF$维护最大值，一个位置最小值$minF$(比如$maxF[x][i]$表示从$x$到它的$i$级祖先上最大值是多少)
假如我们直接在$x-LCA(x,y)$进行了买入卖出操作，那么我们需要直接计算这个最大值，设$up[x][i]$表示从$x$到它的$i$祖先进行了先买后卖操作所能获得最大值。那么我们怎么维护更新它呢？
设$y = f[x][i-1]$,那么最大值可能由以下三种情况中产生:
- 在$x-y$中先卖后买，即$up[x][i-1]$
- 在$y - f[x][i]$中先买后卖，即$up[y][i-1]$
- 在$x-y$中买入，在$y - f[y][i-1]$中卖出，即$maxF[x][i-1] - minF[x][i-1]$
在$LCA(x,y) - y$中进行先买后卖操作，我们新开一个$down[x][i]$数组，含义与$up$类似，但注意，顺序不一样，这个表示从$x$的$i$级祖先到它本身，进行先买后卖操作。

一些细节

在求答案的过程中，使用了这种方式遍历倍增数组。
比如$9 = 2^3 + 2^0$,那么就会先执行$x’ = f[x][3]$,后执行$x’’ = f[x’][0]$

for(int i = 20; i >= 0; --i)
    if(dep & (1 << i)) { 
        ans = max(ans, max(up[x][i], maxF[x][i] - minNum));
        minNum = min(minNum, minF[x][i]);
        x = f[x][i];
    }

代码

#include <cstdio>
#include <iostream>
using namespace std;

const int maxN = 3e5 + 7;

struct Edge {
    int from, to;
}e[maxN << 1];

int n, m, head[maxN], cnt, val[maxN], f[maxN][31], d[maxN], minF[maxN][31], maxF[maxN][31], up[maxN][31], down[maxN][31];

inline void add(int u, int v)
{
    e[++cnt].from = head[u];
    e[cnt].to = v; 
    head[u] = cnt;
}

void dfs(int x, int fa)
{
    d[x] = d[fa] + 1; f[x][0] = fa;
    maxF[x][0] = max(val[x], val[fa]); minF[x][0] = min(val[x], val[fa]);
    up[x][0] = max(0, val[fa] - val[x]); down[x][0] = max(0, val[x] - val[fa]);
    for(int i = 1; i <= 20; ++i) {
        f[x][i] = f[f[x][i - 1]][i - 1];
        if(!f[x][i])
            break;
        int y = f[x][i - 1];
        maxF[x][i] = max(maxF[x][i - 1], maxF[y][i - 1]);
        minF[x][i] = min(minF[x][i - 1], minF[y][i - 1]);
        up[x][i] = max(max(up[x][i - 1], up[y][i - 1]), maxF[y][i - 1] - minF[x][i - 1]);
        down[x][i] = max(max(down[x][i - 1], down[y][i - 1]), maxF[x][i - 1] - minF[y][i -1]);
    }
    for(int i = head[x]; i; i = e[i].from) {
        int y = e[i].to;
        if(y == fa)
            continue;
        dfs(y, x);
    }
}

inline int Lca(int x, int y)
{
    if(d[x] > d[y])
        swap(x, y);
    for(int i = 21; i >= 0; --i)
        if(d[f[y][i]] >= d[x])
            y = f[y][i];
    if(x == y)
        return x;
    for(int i = 21; i >= 0; --i)
        if(f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}

inline int query(int x, int y)
{
    int lca = Lca(x, y), ans = 0, maxNum = 0, minNum = 0x3f3f3f3f;
    int dep = d[x] - d[lca];
    if(dep) { // 如果x不是lca(x,y)
        for(int i = 20; i >= 0; --i)
            if(dep & (1 << i)) { 
                ans = max(ans, max(up[x][i], maxF[x][i] - minNum));
                minNum = min(minNum, minF[x][i]);
                x = f[x][i];
            }
    }
    dep = d[y] - d[lca];
    if(dep) {
        for(int i = 20; i >= 0; --i)
            if(dep & (1 << i)) {
                ans = max(ans, max(down[y][i], maxNum - minF[y][i]));
                maxNum = max(maxNum, maxF[y][i]);
                y = f[y][i];
            }        
    }
    return max(ans, maxNum - minNum);
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &val[i]);
    for(int i = 1; i < n; ++i) {
        int x, y; scanf("%d%d", &x, &y);
        add(x, y); add(y, x);
    }
    dfs(1, 0);
    scanf("%d", &m);
    for(int i = 1; i <= m; ++i) {
        int x, y; scanf("%d%d", &x, &y);
        printf("%d\n", query(x, y));
    }
    return 0;
}

展开全文 >>

atCoder137C

2022-04-04

题目大意

给定一个$n$个数的集合，Alice和Bob轮流操作,Alice先操作，每次选最大的数，将其减少任意值，再放回集合(需一直满足集合中元素互不相同的规定)，集合中的数$a_i \ge 0$。谁先不能操作，谁就会输掉游戏输掉。

给定$n, a_i$,问谁会获胜。

原题链接

思路

这是一道相当妙的博弈论，这个游戏是个$ICG$，也就是说，存在必胜策略。我们把数都从小到大排序(每次执行操作后也排序)。

我们假设:

先手把$a_n$减少到比$a_{n-1}$小，是必胜策略，那么我们就直接这么做
如果先手把$a_n$减少到比$a_{n-1}$小不是必胜策略(也就是必败策略)，且假设$a_n > a_{n-1} + 1$，那我们先手让$a_n = a_{n-1} + 1$,那么后手就只能把$a_n$减少到小于$a_{n-1}$,然而这是个必败策略，也就是说，可以把必败情况给后手，即也是先手必胜。

那么假如$a_n = a_{n-1} + 1$,那么双方的策略就一直是维持$a_n = a_{n-1}$,直到无法操作,因为一旦不满足这个条件，那么另外一方就能利用$a_n > a_{n-1} + 1$这个条件取胜。

那么一直这么做的话，执行最后一步的人会取胜，而执行到最后集合一定是$0,1,2,…,n-1$。且我们发现操作次数其实就是$a_n - (n-1)$，是的，很神奇和其它数无关，因为我们每次减少数，不能和其它数重合，且满足$a_n = a_{n-1}$,也就是说$[0,a_n]$中每个数都会被遍历到，所以其它数在哪都没关系。

那么可执行次数为奇数，先手必胜，否则后手必胜。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxN = 3e5 + 7;

int n, a[maxN];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n);
    if(a[n] - a[n - 1] > 1)
        printf("Alice\n");
    else {
        if((a[n] - (n - 1)) % 2)
            printf("Alice\n");
        else
            printf("Bob\n");
    }
    return 0;
}

展开全文 >>

cf1658D2

2022-03-31

题目大意

给定两个数$l, r$,将$[l, l + 1,…, r-1, r]$的一个任意排列，全部异或$x$，得到一个新的数组$a$。

给定$l, r$和$a$数组，求$x$。

其中$0 < l \le r \le 2^{17}$

more >>

展开全文 >>

cf1658D1 388535 (Easy Version) 题解

2022-03-31

题目大意

给定两个数$l, r$,将$[l, l + 1,..., r-1, r]$的一个任意排列，全部异或$x$，得到一个新的数组$a$。

给定$l, r$和$a$数组，求$x$。

其中$0 = l \le r \le 2^{17}$ more >>

展开全文 >>

cf1658C Shinju and the Lost Permutation 题解

2022-03-31

题目大意

定义$b_i为$一个排列$a$中前$i$个数的最大值。定义操作:把排列$a$向后移动一位，即，原本最后一个数成为第一个数，原本第一个数成为第二个... 定义$c_i$为向后移动$i-1$位后，每次生成的$b_i$数组中，不同的数的个数。

现在给定$c$数组，判断是否存在对应的排列$a$ more >>

展开全文 >>

cf526C

2022-03-27

题目大意

有两类糖果，重量与美味值分别为$w_1, h_1, w_2, h_2$。求: 拿取重量不超过$C$的糖果，美味值最大为多少？ $(1 \le w_1, h_1, w_2, h_2, C \le 10^9)$ more >>

展开全文 >>

Python 字典 dict 教程

2022-03-05

创建

# 1
keys = ['a', 'b', 'c', 'd']
values = [1, 2, 3, 4]
dic = dict(zip(keys, values))

# 2
dic = {'name':'Miku', 'number': 39}

# 3
dic = dict()

# 4 创建指定key的空字典
aDict = dict.fromkeys(['name', 'age', 'sex'])

访问及修改

1 2	aDict['name'] # 如果存在则返回值，如果不存在则报错 aDict['name'] = 'Miku' # 如果不存在则创建，存在则修改value

item() : 返回dict的(key,value)对
keys() : 返回dict的key

values : 返回dict的value

1 2	aDict.get(key, val) # 如果存在key则返回值，否则返回指定的val aDict.update({'a':97, 'age':39}) # 存在的修改，不存在的添加

## 删除

1
2
3

del aDict['age'] # 删除
aDict.popitem() # 弹出并返回最后一个元素的value
aDict.pop('age') # 弹出并返回指定key的value

遍历

for key in dict.keys () # 遍历key
for values in dict.values () # 遍历value
for item in dict.items (): # 遍历value-key对
    key = item[0]
    value = item[1]
for key, value in dict.items (): # 遍历value-key对

展开全文 >>

Python tuple元组生成器推导式教程

2022-03-05

tuple 元组

创建

1 2	x = (5,) # 仅有一个元素时，需要在结尾加逗号 x = tuple()

访问

与list完全一致

生成器推导式

与列表推导式完全一致

1
2
3

g = ((i + 2) ** 2 for i in range(10))
tuple(g) # 想要查看值需要用tuple
(4, 9, 16, 25, 36, 49, 64, 81, 100, 121)

循环访问时，可以用for遍历，也可用next()函数，但需要注意，访问是单向的，访问一个元素后，该元素就会从生成器中消失

g = ((i + 2) ** 2 for i in range(10))
tuple(g)
(4, 9, 16, 25, 36, 49, 64, 81, 100, 121)
list(g)
[]

g = ((i + 2) ** 2 for i in range(10))
g.__next__()
4
next(g)
9

展开全文 >>

Python列表推导式教程

2022-03-05

示例1

1 2	aList = [x * x for x in range(10)] [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

这个分为两部分:

1 2	x * x for x in range(10) # 1

每当 #1循环一次，就把一个$x*x$放入到list中

示例2

1
2
3

freshfruit = [' banana', ' loganberry', ' passion fruit']
aList = [w.strip() for w in freshfruit] #1
['banana', 'loganberry', 'passion fruit']

每当 #1循环一次，就把一个w.strip()放入到list中 .strip()函数会去掉字符串的前导空格

示例3

1
2
3

vec = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
[num for elem in vec for num in elem]  # 1
[1, 2, 3, 4, 5, 6, 7, 8, 9]

#1相当于一个两重循环

ans = []
for elem in vec:
    for num in elem:
        ans.append(num)

示例4

1
2
3

aList = [-1, -4, 6, 7.5, -2.3, 9, -11]
[i for i in aList if i > 0]
[6, 7.5, 9]

示例5

from random import randint
x = [randint(1, 10) for i in range(20)]
[8, 10, 9, 1, 10, 5, 1, 10, 6, 2, 3, 10, 2, 2, 7, 4, 10, 7, 7, 7]
m = max(x)
[index for index, value in enumerate(x) if value == m] # 1
[1, 4, 7, 11, 16]

#1相当于:

ans = []
for index, value in enumerate(x):
    if value == m:
        ans.append(index)

示例6

1 2	[(x, y) for x in [1, 2, 3] for y in [3, 1, 4] if x != y] [(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

展开全文 >>