^-^
日常练习
  1. Codeforces
    1. Round 920
      1. A
      2. B
      3. C
      4. D
      5. E
    2. Round 929
      1. A
      2. B
      3. C
      4. D
      5. E
  2. LOJ
    1. LOJ 10011
    2. LOJ 10012
    3. LOJ 10014
    4. LOJ 10015
    5. LOJ 10016
    6. LOJ 10017
    7. LOJ 10020
    8. LOJ 10022
  3. Luogu
    1. P1135
    2. P1352
    3. P3478
  4. 校赛初赛
    1. G
    2. I
    3. Q
    4. P
    5. N
    6. M
    7. D
  5. 校赛决赛
    1. K
    2. I
    3. D
    4. C
    5. E

Codeforces

Round 920

A

题意: 给定乱序的正方形的四个顶点坐标, 保证边平行于坐标轴, 求面积.

解: 边长求平方.

B

题意: 给定两个二进制串 , 通过替换和交换两种操作, 以最少的操作次数将第一个串变成第二个串.

解: 优先交换, 交换后剩下的再替换即可. 设 , , 答案为 .

C

题意: 给定信息发送的时刻 , 时刻 0 剩下 , 电话开着的每一个时刻花费 , 开关一次花费 , 电话关着时花费为 0, 判断能否将所有信息发送出去.

解: 显然每两个时刻之间的最小花费为 , 判断 与 的大小关系即可.

D

给定两个序列 , 从 中取出 个数以任意方式排列得到序列 , 求 .

解: 首先两个长度相同的序列 之间距离 的最大值在 且 时取到(和排序不等式类似, 可以通过调整法证明), 因此先排序.

取出的 中的数一定分布在 个个 中, 因此只需要计算 即可, 其中 . 如果每一个 都直接加的话需要 , 事实上只需要先计算 , 接下来根据 的位置每个循环 , 即可, 这样可以 地求出最大值.

E

题意: Alice 和 Bob , Alice 只能向下面的三个方向移动, Bob 只能向上面三个的方向移动, 当其中一个选手能落到对方棋子上时该选手赢, 双方互相吃不到对方棋子则平局. Alice 先手, 双方都采用最优策略.

解: 决胜点在双方棋子还隔有一行时, 此时轮到谁谁就会处于被动方(也就是不可能吃掉对方), 这通过初始状态两个棋子之间的距离的奇偶性来判断. 当 时 Alice 处于被动, 反之 Bob. 被动方的最优策略是逃离主动方, 主动方的最优策略是追击被动方. 根据两者碰面(也就是 Bob 恰在 Alice 的下一行)时棋子所能覆盖的范围来判断即可, 当 时(主动方所覆盖的范围包括了被动方覆盖的范围), 主动方赢. 注意边界以及初始条件 的特判.

Round 929

A

每一项绝对值加起来.

B

不管何种情况至多操作 2 次, 记和为 ,

  • 无需操作
  • , 若序列中有模 余 的删去该数即可(操作 1 次), 反之操作 2 次 (每次 )
  • 操作 1 次

C

给定整数 , 求有多少个 使得 .

解: 根据范围, , 有 , 直接暴力枚举 即可, 用一个 set 存 .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
while(t--){
    s.clear();
    cin>>a>>b>>l;
    for(int x=0;x<24;x++){
        long long ax=pow(a,x);
        if(ax>l)break;
        for(int y=0;y<24;y++){
            long long by=pow(b,y);
            if(by>l)break;
            long long div=ax*by;
            if(l%div==0){
                s.insert(l/div);
            }
        }
    }
    cout<<s.size()<<'\n';
}

D

给定序列 , 判断是否有一种重排方式得到 使得 .

解: 先排序, 设为 ,

  • 若 则存在, 排序后的序列即为所求.

  • 若 , 且存在 满足 , 则存在, 把 作为首项即可.

  • 其余情况都不存在

1
2
3
4
5
6
7
8
9
inline bool judge(){
    if(a[1]!=a[0])return true;
    for(int i=0;i<n;i++){
        if(a[i]!=a[0]&&a[i]%a[0]!=0){
            return true;
        }
    }
    return false;
}

E

题意: 给定 , 确定最小的 , 以最大化 解: 这是个二次函数 , 极值点在 , 因此找到距离 最近的 即可, 预处理出前缀和 , 相当于在递增的序列 中找到距离 最近的数的下标, 二分即可.

LOJ

LOJ 10011

题意: 给定 , 求 .

解: 先排序, 设最大的最小距离为 , 首先一定有 , 而对于每一个 , 都可以在 的时间内进行模拟以判断该 是否合法(即能否以至少 的距离安排所有的牛), 显然可以二分地枚举 , 因此一定可以在 的时间内找到最小的 .

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int x[maxn];
int n,m;
inline bool check(int d){
    int cnt=1,pos=x[0]+d; // 第二头牛的位置
    for(int i=1;i<n;i++){
        if(x[i]>pos){
            cnt++; // 可以将牛放在x[i]处
            pos=x[i]+d;
        }
    }
    return cnt>=m;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>x[i];
    sort(x,x+n);
    int l=1,r=x[n-1]-x[0];
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)){
            l=mid+1; // 当前距离合法, 寻找可能的更大距离
        }
        else r=mid-1;
    }
    cout<<l;
    return 0;
}

错误思路: 先排序, 先安排两头牛在 处, 然后对于 , 若 分别有一头牛, 则下一头牛应该安排在满足距离 最近的 处.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int bfind(int l,int r){
    float pos=(x[l]+x[r])/2;
    while(l<=r){
        int mid=(l+r)/2;
        if(l==r) return l;
        else if(l+1==r){
            return (pos-x[l])<(x[r]-pos)?l:r;
        }
        if(pos<x[mid])r=mid;
        if(pos>x[mid])l=mid;
        else if(pos==x[mid]){
            return mid;
        }
    }
}

错误是因为当有多个区间可安排牛时没有一个标准来确定最优区间, 一个可能的想法是按照区间长度, 这样不仅要用优先队列维护, 很容易就能构造一个过不去的样例:

1
2
6 4
1 3 5 6 9 10

LOJ 10012

题意: 给定一个长度为 的非负整数序列 ，求一个平均数最大的，长度不小于 的子段。

解: 的范围比较小 , 因此直接在答案的范围内二分, 和上一题一样. 设答案为 , 然后为了方便可令 , 这样问题转化成求 中长度至少为 的和最大的子序列, 并判断其是否大于零. 预处理出 的前缀和 , 相当于求 其中 .

但事实上没有必要求出这个最大值, 只要有和为正的子序列就意味着 偏大.

然后不会做, 不太懂下面为什么是对的?

1
2
3
4
5
6
7
8
9
10
11
12
int check(double d) {
    sum[0] = mn = 99999999999999;
    for (i = 1; i <= n; ++i) {
        sum[i] = (i == 1 ? double(0) : sum[i - 1]) + a[i] - d;
        mn = min(mn, sum[max(0, i - len)]);
        if (sum[i] - mn > 0)
            return 1;
    }
    if (sum[n] > 0)
        return 1;
    return 0;
}

下面按照类似的写法WA了几个点:

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
inline bool check(double d){
    S[0]=a[0]-d;
    double ms=S[0];
    for(int i=1;i<n;i++){
        S[i]=S[i-1]+a[i]-d;
        ms=min(ms,S[max(0,i-L)]);
        if(S[i]-ms>0)return true;
    }
    if(S[n-1]>0)return true;
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>L;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    double l=-1,r=2001,eps=1e-5;
    while(r-l>=eps){
        double mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    cout<<int(r*1000);
    return 0;
}

先这样吧.

LOJ 10014

题意: 给定长度为 的正整数序列 以及 , 将 划分成 段 , 求 所有的划分方式, 保证 .

思路: 还是在答案中二分. 设答案为 , 从头开始进行划分保证每段和不超过 , 如果总段数大于 则说明 偏小, 反之偏大.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline bool check(int d){
    int i=0,cnt=0;
    while(i<n){
        int tmp=0;
        while(1){
            tmp+=a[i];
            if(tmp>d||i>=n)break;
            i++;
        }
        cnt++;
        if(cnt>m)return false;
    }
    return true;
}

LOJ 10015

题意: 上给定 个点的坐标, 每个时刻每个点会向四个方向扩散一个单位长度, 覆盖一定的区域, 当两个点覆盖相同的区域时两点连通, 若干个连通的点可形成连通块, 求 个点形成连通块的时刻.

思路: 记点为 , 表示 之间的 Manhattan 距离, 显然 最早在时刻 时直接相连, 构建图 表示时刻 这 个点形成的 graph, 因此 当且仅当 .

二分时间, 对每一个时间用 bfs 判断图是否连通.

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
#include<bits/stdc++.h>
using namespace std;
int p[55][2],n;
int dis(int i,int j){
    return abs(p[i][0]-p[j][0])+abs(p[i][1]-p[j][1]);
}
int g[55][55],isv[55];
queue<int>Q;
bool is_conn(int t){
    memset(g,0,sizeof(g));
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(t>=ceil(dis(i,j)/2.))g[i][j]=g[j][i]=1;
        }
    }
    memset(isv,0,sizeof(isv));
    Q.push(0);
    while(!Q.empty()){
        int v=Q.front();
        Q.pop();
        for(int i=0;i<n;i++){
            if(!isv[i]&&g[v][i]){
                isv[i]=1;
                Q.push(i);
            }
        }
    }
    for(int i=0;i<n;i++){
        if(!isv[i])return false;
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)cin>>p[i][0]>>p[i][1];
    int l=1,r=1000000000;
    while(l<=r){
        int mid=(l+r)/2;
        if(is_conn(mid))r=mid-1; // 若mid时刻已经连通, 找更小的时间
        else l=mid+1; // 否则需要更长的时间
    }
    cout<<l;
    return 0;
}

LOJ 10016

注意影子全在地上和影子有一部分在墙上讨论一下.

影子全在地上: 影子有一部分在墙上: 可以直接求极值点, 也可以用三分. 懒得写了.

LOJ 10017

设从 沿传送带 走到 , 再走到传送带 上的点 , 再走到点 , 那么总时间为 是 的函数, 且 . 这是个二元函数. 形如 , 两次三分. 懒得写了.

LOJ 10020

首先最小可能长度 .

好像可以二分最小可能长度, 然后对于每一个最小可能长度, 用 dfs 判断存不存在合法解.

构建一个完全图, 每个点有点权. 从每一个点开始进行深搜, 如果存在一条路径 使得 , 就把这条路径上的点给删了, 对剩下的图重复操作.

LOJ 10022

最好的表达方式.

分数 的最好表达方式是 ,

遍历 , 寻找 的最好表达方式, 记录最好表达方式的长度, 长度最短且 最小的是 的最好表达方式.

从小于 的第一个数开始遍历

, .

1
2
3
4
5
6
7
8
def find(x): // 返回 x 的最好表达方式
    if x本身是形如 1/y 的分数:
        return [x]
    for y in [1/x,1e7]:
        tmp=find(x-1/y)
        if tmp好于res:
            res=tmp
    return [res,y]

Luogu

P1135

题意: 给定 层楼, 楼层数 , 序列 , 每一个楼层 可以按一次按钮坐电梯上 层或者下 层 (在 或 合法的前提下), 求从 到 需要按按钮的最少次数.

设 表示从 到 最少要按钮的次数, 设 表示从 可以到达的楼层, 那么 当然 是固定的, 只需要用一维的 即可.

为什么不对?

P1352

树形 DP.

题意: 给定一棵带点权有根树 , , 计算最大权独立集的权值(一个点选入当且仅当它的父亲未被选入, 同时它的儿子都不会再被选入, 显然是独立集).

解:

设 表示以 为根节点的树的最大权独立集的权值, 那么

即有两个分支, 根节点选或不选. 但是这样会 TLE, 考虑到树的特殊性质, 有的分支是没有必要的:

  • 若 , 则 , 否则是下面的情况:
  • 若 仅仅是因为权值小于 0 没有选入, 那么结果为
  • 若 是因为 被选入而删去的, 那么 .
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
int happy(int root,int flag){
    if(son[root].empty())return max(0,w[root]);
    int res=0,res1=0,res2=0;
    if(w[root]<=0){
        for(auto v:son[root]){
            res+=happy(v,1);
        }
        return res;
    }
    else{
        if(flag){
            for(auto v:son[root]){
                res1+=happy(v,0);
            }
            res2=w[root];
            for(auto v:son[root]){
                if(!son[v].empty()){
                    for(auto u:son[v]){ 
                        res2+=happy(u,0);
                    }
                }
            }
            return max(res1,res2);
        }
        else{
            res2=w[root];
            for(auto v:son[root]){ 
                if(!son[v].empty()){ 
                    for(auto u:son[v]){ 
                        res2+=happy(u,0);
                    }
                }
            }
            return res2;
        }
    }
}

还有一种做法是, 考虑到所有权值小于等于 0 的点一定不会被选入, 那么删去这些点, 得到森林 , 每个根节点为 , 那么对于正点权树, 只在每棵树的根结点处做分支 即可, 因为当父节点不选入时, 其子节点一定要选入, 这样就相当于确定了所有节点的选取情况, 结果即为 .

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
int happy_positive(int root, int flag){
    if(son[root].empty())return max(0,w[root]);
    int res1=0,res2=w[root];
    if(flag){
        for(auto v:son[root]){
            res1+=happy_positive(v,0);
        }
    }
    for(auto v:son[root]){
        if(!son[v].empty()){
            for(auto u:son[v]){
                res2+=happy_positive(u,0);
            }
        }
    }
    return max(res1,res2);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=0;i<n-1;i++){
        int f,s;
        cin>>s>>f;
        if(w[s]>0&&w[f]>0){
            fa[s]=f;
            son[f].push_back(s);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(fa[i]==0){
            ans+=happy_positive(i,1);
        }
    }
    cout<<ans;
    return 0;
}

性能略劣于第一种做法.

P3478

换根 DP.

题意: 给定无根树 , 确定根节点 以最大化 .

解: 需要快速处理出任意两点之间的距离.

校赛初赛

.

G

注意到二分图的两边只需要分别各自有两个点一共是四个点有大于 1 的公约数即可. 考虑用素数筛, 用每个素数 筛时, 分别维护两个计数器 cnt1, cnt2 计数左右两遍是 的倍数的数, 若筛到的数在左边或者右边则对应的计数器加一并记录被筛到的数, 一旦 cnt1>=2 且 cnt2>=2 则终止并且输出长度为 4 的环; 如果给定范围内的素数都筛完了则表明不存在这样的环.

I

暴搜, 枚举任意两个电阻按照串联和并联重组, 得到 个新电阻, 对新电阻实施相同的操作. 注意电阻标签的维护.

Q

模拟 26 进制加法, 每次加 1, 注意进位即可.

没做出来在这重新思考的题目: D, M, N, P.

P

题意: 给定一棵树, 随机选择两个不同且没有边相连的点(均以 的概率)连一条边, 这会出现一个环, 求环长度的期望.

解: 求出来满足条件的点对数为 (需要用到握手定理), 然后所有情况的环的长度和为 , 减去的部分是有边相连的点对的边数和. 然后需要快速计算出树上每个点到其他点的距离和. 要用换根 DP.

N

题意: 给定随机变量 , 满足 , 计算第 个随机变量排名的期望, 排名的定义是大于 的随机变量的个数加 1.

解: 设 的排名为 , 显然 .

好像其实也没有那么显然, 严格推导一下. 朴素方法就是 的排名为

现在有两个问题:

  • 计算 , 这要小心地分类讨论.

  • , 直接计算无法通过, 考虑用线段树或差分.

但是不会呀 ?!

M

题意: 给定 的格点, 计数面积在 上的格点三角形的数目.

解: 通过 Pick 定理知只有边上的格点只能为 , 内部不能有格点.

D

题意: 给定两个正整数序列 , 计算

校赛决赛

和队友开出四道签到题. 剩下的一道不会做, 坐牢两个多小时. 难度梯度略大(

还是很好玩的.

K

题意: 给定序列 , 求最大的 , 进行不限次的操作: 选择 个不同的数均乘以相同的正整数, 使得最终整个序列每个数都相同.

解: 如果序列只有一种数, 那么 ; 反之进行 轮操作, 第 轮选择除了 以外的 个数, 每个数都乘 即可, 这就意味着答案是 .

I

题意: Alice 和 Bob 进行游戏: 给定 , 每个人可以进行两种操作: 选择一个数作为自己的得分, 剩下的数的和作为对方的得分, 游戏结束; 选择两个数合并. Alice 先手, 判断其是否有必胜策略, 保证 为奇数.

解: 决胜局在序列长度为 的时候, 设为 , 若 , 那么轮到谁谁就一定会赢; 若 , 那么轮到谁谁就一定会输. 当 为奇数时 Alice 序列长度为 3 时轮到 Alice, 反之轮到 Bob; 而在前面的过程中, 双方都必然要选择最小的两个数合并, 那么 的奇偶性就决定了胜负; 特判 与 的关系, 如果前者大于后者, 则第一轮就可以结束比赛.

D

题意: 构造 01 序列, 满足存在长度为 的且包含 个 1 的子串, 这样的条件有 个, 并给出满足条件 的子串位置.

解: 显然构造形如 的串即可. 记 , 那么 , 且满足第 个条件的子串的起始位置为 .

C

解: 猜答案为 .

E

E 有思路但是没调出来.

2024-01-25 该篇文章被 Baoduo Xu 归为分类: 杂项

以上
©
Too Young Too Naive 本站由Hexo驱动｜使用Hexo-theme-A4主题