程序员进阶之算法练习(八)附两道搜狐笔试题

前言

前面讲了那么多算法的重要性。口说无凭,这次带上两道搜狐今年的笔试题。 这里先附上两道搜狐题目的大意: 题目一: 《宝石》 有一串宝石首尾相连,用一个大写字母表示一个宝石; 现在需要从这一串宝石中截取一段宝石,要求这一段宝石包含ABCDE这5种字母;求剩下最多有多少个宝石? 题目二: 《袋鼠》 有n个弹簧排成一列,袋鼠起始位置在第一个弹簧; 输入n个数字,代表n个弹簧的力量; 弹簧的力量为5表示可以往后跳最多5个弹簧; 问袋鼠到达第n个弹簧的最小弹跳次数? 答案看最后的附加题部分。

正文

这次正文有5道题,是CF707-DIV2的题目。

  • 为了不剧透,把对题目的总结放到最后面。

看完题目大意,先思考,再看解析;觉得题目大意不清晰,点击题目链接看原文。

文集: 程序员进阶之算法练习(一) 程序员进阶之算法练习(二) 程序员进阶之算法练习(三) 程序员进阶之算法练习(四) 程序员进阶之算法练习(五) 程序员进阶之算法练习(六) 程序员进阶之算法练习(七) 代码地址

A

题目链接 题目大意:输入n * m个字符,字符中存在C M Y为混色,否则为黑白,输出对应的描述。

 Examples
 input
 2 2
 C M
 Y Y
 output
 #Color
 
 input
 3 2
 W W
 W W
 B B
 output
 \ #Black&White
 

代码实现

    int n, m, ret = 1;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            char str[10];
            scanf("%s", str);
            if (str[0] == 'C' || str[0] == 'M' || str[0] == 'Y') {
                ret = 0;
            }
        }
    }
    if (!ret) {
        cout << "#Color";
    }
    else {
        cout << "#Black&White";
    }

题目解析: 难度在读题,黑白不仅仅是W B,还有G。

B

题目链接 题目大意:n个城市,其中k个城市提供面粉,城市中有m条路。 在n个城市中的选择一个不提供面粉的城市,要求这个城市能到达提供面粉的城市,如果有多个输出边长最小的一个。(没有输出-1) n, m and k (1 ≤ n, m ≤ 10^5, 0 ≤ k ≤ n)

 Examples
 input
 5 4 2
 1 2 5
 1 2 3
 2 3 4
 1 4 10
 1 5
 output
 3
 input
 3 1 1
 1 2 3
 3
 output
 -1
 

代码实现

    int n, m, k;
    cin >> n >> m >> k;
    
    for(int i = 0; i <= n; ++i) g[i].clear();
    
    for (int i = 0; i < m; ++i) {
        lld u, v, l;
        cin >> u >> v >> l;
        g[u].push_back(make_pair(v, l));
        g[v].push_back(make_pair(u, l));
    }
    
    for (int i = 0; i < k; ++i) {
        int tmp;
        scanf("%d", &tmp);
        f[tmp] = 1;
    }
    
    lld ret = -1;
    for (int i = 1; i <= n; ++i) {
        if (f[i]) {
            for (int j = 0; j < g[i].size(); ++j) {
                if (f[g[i][j].first] == 0) {
                    if (ret == -1) {
                        ret = g[i][j].second;
                    }
                    else {
                        ret = min(ret, g[i][j].second);
                    }
                }
            }
        }
    }
    cout << ret;

题目解析: n个点,m条边,k个关键点。在关键点外的集合n-k,中找到一点T,使得T与关键点中任意点连接,并且边长最小。 难度都在读题,容易知道,关键点只要存在一条边与非关键点相连,那就有解。 存下边,把点标记为关键点(f[i]=1)和非关键点(f[i]=0) 遍历查找边由f[i]=1到f[i]=0的最小边即可,无解输出-1。

C

题目链接 题目大意:给出一个数字n,求一组勾股数中的另外两个,使得三个构成勾股数。 n (1 ≤ n ≤ 10^9)

 Examples
 input
 3
 output
 4 5
 input
 6
 output
 8 10
 input
 1
 output
 -1
 

代码实现

    lld k, b;
    cin >> k;
    lld mod = 2 - k % 2;
    b = (k * k / mod - mod) / 2;
    if (b == 0) {
        cout << -1;
    }
    else {
        cout << b << " " << b + mod << endl;
    }

题目解析: 容易知道,n=1,2无解。(最小的勾股数3、4、5) 假设在a2+b2=c^2 中 令a=n 那么有n * n=c * c-b * b=(c+b) * (c-b) 当n为奇数时,令c-b=1, 有n * n=(b+1+b) => b=(n * n-1)/2 当n为偶数时,令c-b=2, n * n=(b+2+b) * 2 => b=(n * n/2-2)/2 令mod=2-n%2,那么有b= (n * n/mod - mod)/2

D

题目链接 题目大意:n * m的格子,q个操作 (1 ≤ n, m ≤ 10^3, 1 ≤ q ≤ 10^5) 每次有4种操作: 1 i j, a[i][j] = 1 2 i j, a[i][j] = 0 3 i, for j in a[i], a[i][j] = !a[i][j] 4 k, 返回操作到第k次的状态,k=0表示起始状态。 每次操作后输出当前格子为1的数量。

 Examples
 input
 4 2 6
 3 2
 2 2 2
 3 3
 3 2
 2 2 2
 3 2
 output
 2
 1
 3
 3
 2
 4

代码实现

struct Node {
    int type, x, y, k;
}node[M];
int flag[N]; // 标志第i行是否翻转
int dfn[M]; // 第i个操作是否已经执行
int a[N][N]; // a[i][j]
int num[N], m; //第i行为1的数量
int sum;    // 当前数量
int ans[M]; // 第i个操作答案
vector<int> g[M]; // 顶点


void lookNext(int k) {
    dfn[k] = 1;
    for (int i = 0; i < g[k].size(); ++i) {
        int u = g[k][i];
        if (dfn[u] == 0) {
            if (node[u].type == 1) {
                if (a[node[u].x][node[u].y] == flag[node[u].x]) {
                    ++sum;
                    ++num[node[u].x];
                    ans[u] = sum;
                    a[node[u].x][node[u].y] = !flag[node[u].x];
                    lookNext(u);
                    a[node[u].x][node[u].y] = flag[node[u].x];
                    --num[node[u].x];
                    --sum;
                }
                else {
                    ans[u] = sum;
                    lookNext(u);
                }
            }
            else if (node[u].type == 2) {
                if (a[node[u].x][node[u].y] != flag[node[u].x]) {
                    --sum;
                    --num[node[u].x];
                    a[node[u].x][node[u].y] = flag[node[u].x];
                    ans[u] = sum;
                    lookNext(u);
                    a[node[u].x][node[u].y] = !flag[node[u].x];
                    ++num[node[u].x];
                    ++sum;
                }
                else {
                    ans[u] = sum;
                    lookNext(u);
                }
            }
            else if (node[u].type == 3) {
                sum = sum - num[node[u].x] + (m - num[node[u].x]);
                num[node[u].x] = m - num[node[u].x];
                flag[node[u].x] = !flag[node[u].x];
                ans[u] = sum;
                lookNext(u);
                flag[node[u].x] = !flag[node[u].x];
                num[node[u].x] = m - num[node[u].x];
                sum = sum + num[node[u].x] - (m - num[node[u].x]);
            }
            else if (node[u].type == 4) {
                ans[u] = sum;
                lookNext(u);
            }
        }
    }
}

题目解析: 操作1、2比较简单,操作3是组操作,设置flag[i]表示第i行在最终结算时是否翻转,那么有 操作1为a[i][j] = !flag[i]. 操作2为a[i][j] = flag[i]. 操作3为flag[i] = !flag[i].

操作4较为复杂,回到操作k,k为之前的操作。 考虑到题目对k没有限制,那么k可以为之前的某个回退操作,从而产生递归回退的效果; 同时回退到操作i之后,下一步可以再回退到操作j,这样线性的操作不可取。 但是单个操作只会是一个线性的分支,整个操作序列可以形成多个线性的分支,汇总在一起就是一颗树的表现。 对于第i个操作,操作完毕后的状态为j,连一条边从i到j,表示从第i个操作完之后会进入操作j的状态。 那么对操作1、2、3,i会连上一条边到i+1;操作4,i会连上一条边到k。 对于某一个操作,先执行,然后dfs,最后撤销执行即可。

E

题目链接 题目大意:输入k条链,链上的节点在n * m的矩阵上; 每条链有len[i]个点,每个点的输入包括x、y、w表示在n * m矩阵上的坐标和权值。

q次操作,操作1把链上的点翻转(权值由w变成0,或者从0变成w);操作2,询问子矩阵内点的权值; 操作2最多2000次; n,m,k = 2000, q=10^6.

代码实现

#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long lld;
const int N = 2010, M = 1000100, inf = 10110110;

struct Node {
    int type, x, y, w;
    Node(int x, int y, int w):x(x), y(y), w(w){};
    Node(){};
};
vector<Node> g[N];
lld d[N][N]; // 前i条链对第j个矩阵的贡献
lld flag[N]; // 标志是否关闭

int n, m, k;

inline void fastRead(int &x){
    char t = getchar();
    bool sign = true;
    while(t < '0' || t > '9') {
        if(t == '-') {
            sign = false;
        }
        t = getchar();
    }
    for(x = 0; t >= '0' && t <= '9'; t = getchar()) {
        x = x * 10 + t - '0';
    }
    if(!sign) {
        x = -x;
    }
}

lld tree[N][N];

struct Ask {
    int x1, y1, x2, y2;
    Ask(int x1, int y1, int x2, int y2):x1(x1), y1(y1), x2(x2), y2(y2){};
};
vector<Ask> matrix;
int ask[M];


char ch[10];

inline int lowbit(int x) {
    return x & -x;
}

void tree_add(int x,int y,int w){
    for(int i = x;i <= n; i += lowbit(i))
        for(int j = y; j <= m; j += lowbit(j))
            tree[i][j] += w;
}
lld tree_sum(int x,int y){
    lld sum = 0;
    for(int i = x; i > 0;i -= lowbit(i))
        for(int j = y; j > 0; j -= lowbit(j))
            sum += tree[i][j];
    return sum;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    cin >> n >> m >> k;
    for (int i = 0; i < k; ++i) {
        int len;
        fastRead(len);
        while (len--) {
            int x, y, w;
            fastRead(x);
            fastRead(y);
            fastRead(w);
            g[i].push_back(Node(x, y, w));
        }
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        scanf("%s", ch);
        if (ch[0] == 'S') {
            fastRead(ask[i]);
        }
        else {
            int x1, y1, x2, y2;
            fastRead(x1);
            fastRead(y1);
            fastRead(x2);
            fastRead(y2);
            matrix.push_back(Ask(x1, y1, x2, y2));
        }
    }
    
    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < g[i].size(); ++j) {
            tree_add(g[i][j].x, g[i][j].y, g[i][j].w);
        }
        for (int j = 0; j < matrix.size(); ++j) {
            d[i][j] = tree_sum(matrix[j].x2, matrix[j].y2) + tree_sum(matrix[j].x1 - 1, matrix[j].y1 - 1) - tree_sum(matrix[j].x1 - 1, matrix[j].y2) - tree_sum(matrix[j].x2, matrix[j].y1 - 1);
        }
    }
    
    int ans = 0;
    for (int i = 0; i < q; ++i) {
        if (ask[i] == 0) {
            lld ret = 0;
            for (int j = 0; j < k; ++j) { // 枚举k条链
                if (flag[j] == 0) {
                    if (j == 0) {
                        ret += d[j][ans];
                    }
                    else {
                        ret += d[j][ans] - d[j - 1][ans];
                    }
                }
            }
            cout << ret << endl;
            ++ans;
        }
        else {
            flag[ask[i] - 1] ^= 1;
        }
    }
    
    return 0;
}

题目解析: 先看最暴力的做法,对于每个switch,把点的值Switch;对于每个ask,遍历所有的链得出结果。 优化部分,添加flag,标志每次switch,询问时再进行计算。 每条链复杂度为O(Len),k条链的修改为O(n) * O(m),询问的时间为O(n) * O(m)。 总的复杂度为O(n * m * 2000) * 2=16 * 1e9。( * 2是因为每次询问都要修改一次、求和一次)

接着使用数据结构来优化。 易知,子矩阵求和使用树状数组即可。求和操作可以优化为O(logN) * O(logM)。 同样在询问的时候再来修改权值,那么有修改复杂度为O(logN) * O(logM) * O(N) * O(M)。 求和复杂度可以忽略,总得复杂度为2000 * log2000 * log2000 * 2000 * 2000 = 8 * 10e10。 (虽然理论上q=10e6限制了当矩阵数为2000时,每次询问前的switch操作有限,但是一条链可以很长,对很长的链进行操作即可,所以最后的修改次数我们还是按N * M来计算) 为什么变大了?

因为每次询问前的修改操作变成耗时操作,如果题目每次在询问前都修改所有的值,复杂度会很高。 继续优化。 每次修改的都是同一个值(整条链为0,整条链恢复),那么可以预处理出这个值d[i][j],表示第i条链对第j个子矩阵的贡献。 这样就可以避免每次询问前修改值,使用之前预处理的计算值即可。 复杂度为5 * 2000 * 2000 * log2000 * log2000 = 2billion; 全部为加法,并且题目给出的时限为3s,可行。

总结

  • A题是简单题;
  • B题是简单题;
  • C题是构造题;
  • D题是DFS;
  • E题是数据结构+离线处理;

只要DIV2没有数论题都能AC,做CF算是赶上大学时候的水平。虽然目前的工作用到的机会比较少,但是做做算法训练还是挺好玩的。 只是喜欢玩,就花点时间在上面;因为对未来可能有用,所以希望自己坚持下去。

附加题

题目一:《宝石》

有一串宝石首尾相连,用一个大写字母表示一个宝石; 现在需要从这一串宝石中截取一段宝石,要求这一段宝石包含ABCDE这5种字母;求剩下最多有多少个宝石? input AFBCFFDE output 2 样例解释: 因为宝石是收尾相连的,所以AFBC和DE是相连的,可以截取这一段下来,剩下FF两个宝石,所以答案为2。

容易知道,我们想要截取一段最短的宝石,包含ABCDE5种宝石; 首先解决首尾相连的问题:把字符串复制一遍放在最后,这样就可以表示循环; 问题变成在字符串str中,找到一个最短的,包含ABCDE 5种字符的子串。 因为对ABCDE的顺序没有要求,故而可以用贪心来解决这个问题: 我们对每一种宝石都设置一个Right数组,Right[i]表示第i种宝石最右边的位置; 假设我们找到了这个最短子串,设最左边的节点为i,最右边的节点为j,有[i, j],那么有 i = min_element(Right, Right + 5)。 然后遍历 N*2的字符串,不断更新Right数组和ans即可。

题目二:《袋鼠》

有n个弹簧排成一列,袋鼠起始位置在第一个弹簧; 输入n个数字,代表n个弹簧的力量; 弹簧的力量为5表示可以往后跳最多5个弹簧; 问袋鼠到达第n个弹簧的最小弹跳次数?

dp[i] 表示到达第i个的最小步数; dp[1]=1; 对于第i个数字是a[i],那么有枚举j, 1<= j <= a[i] d[i+j]=min(d[i+j], d[i]+1); 表示到达i+j的最优解; 复杂度最多可以到O(N*N)。

优先队列优化: 对dp[i], 打包成pair(i, a[i]) 放入优先队列; 这样每次取出来的都是最小步数,然后判断i+a[j]是否大于等于当前位置,是则更新,不是则丢弃这个解,重新在队列里面取;

扩展

《宝石二》

有一串宝石首尾相连,用一个大写字母表示一个宝石,每个宝石有相应价值; 现在需要从这一串宝石中截取一段宝石,要求这一段宝石包含ABCDE这5种字母;求剩下最大价值数?

input
 8
 AFBCFFDE
 1 2 3 4 5 6 7 8
output
 11

《袋鼠二》

袋鼠喜欢在弹簧上弹跳; 有n个弹簧排成一列,每个弹簧可以弹到下一个弹簧; 输入n个数字,代表袋鼠对n个弹簧的喜欢值; 袋鼠只喜欢跳到喜欢值大于等于起始位置喜欢值的弹簧; 袋鼠可以在任意弹簧位置起跳; 袋鼠的开心值=起始点的喜欢值*经过的弹簧数; 求袋鼠最大的开心值。

input
 5
 1 2 3 4 5
output
 9

袋鼠在位置1,2,3,4,5起跳的开心值分别为5,8,9,8, 5。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏牛客网

知识总结:那些年在编程题中踩过的坑循环输入输出处理常见问题对于各种语言的一些基本知识关于输出格式关于时间复杂度分析:最后关于 "我本地能通过,交上去就是不对"

循环输入输出处理常见问题 1、为什么需要循环输入输出:通常来说OJ对于每道题里面有.in和.out文件,分别表示测试数据的输入和输出。如果某些编程题的所有数据都...

42580
来自专栏大史住在大前端

野生前端的数据结构基础练习(8)——图

图是由边的集合和点的集合组成的。如果图的边有方向(或者说图中的顶点对是有序的)则成为有向图,如果边没有方向则称为无向图。

10830
来自专栏逸鹏说道

临时处理小记:把Numpy的narray二进制文件转换成json文件

临时处理一个Numpy的二进制文件,分析知道里面是dict类型,简单小记一下,如果Numpy和Python基础不熟悉可以看我之前写的文章(贴一下Numpy的)

14230
来自专栏数说工作室

统计师的Python日记【第七天:数据清洗(1)】

本文是【统计师的Python日记】第7天的日记 回顾一下: 第1天学习了Python的基本页面、操作,以及几种主要的容器类型。 第2天学习了python的函数、...

586100
来自专栏数据结构与算法

42:出书最多

42:出书最多 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 假定图书馆新进了m(10 ≤ m ≤ 999)本图书,它们...

29250
来自专栏HansBug's Lab

1647: [Usaco2007 Open]Fliptile 翻格子游戏

1647: [Usaco2007 Open]Fliptile 翻格子游戏 Time Limit: 5 Sec  Memory Limit: 64 MB Subm...

29560
来自专栏机器学习算法与Python学习

机器学习(31)之频繁集挖掘FP Tree详解

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 明早7:22推送第2期免费送书活动 ...

44260
来自专栏潇涧技术专栏

Python Algorithms - C5 Traversal

Traversal就是遍历,主要是对图的遍历,也就是遍历图中的每个节点。对一个节点的遍历有两个阶段,首先是发现(discover),然后是访问(visit)。遍...

10410
来自专栏灯塔大数据

解密 | 一文总结学习 Python 的 14 张思维导图

前言 本文主要涵盖了 Python 编程的核心知识(暂不包括标准库及第三方库,后续会发布相应专题的文章)。 首先,按顺序依次展示了以下内容的一系列思维导图:基础...

36970
来自专栏owent

PKU POJ 1724 ROADS 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1724

7320

扫码关注云+社区

领取腾讯云代金券