美文网首页
程序员进阶之算法练习(八十六)

程序员进阶之算法练习(八十六)

作者: 落影loyinglin | 来源:发表于2023-09-23 09:59 被阅读0次

    题目1

    题目链接
    题目大意:
    给出n个整数,已知这n个整数是按照下面的规则生成。
    1、初始化的时候,数组中有2个整数,每次从数组中选择任意两个整数,计算得到他们差值的绝对值,重新放回数组;
    2、重复n-2次操作1,得到n个元素的数组。

    现在已知n个整数的数组,想知道最开始的两个元素中,会存在哪个数字?

    输入:
    第一行,整数𝑡 表示t个样例 𝑡 (1≤𝑡≤200)
    每个样例2行
    第一行,整数𝑛 (1≤𝑛≤100)
    第二行,n个整数𝑎1,𝑎2,…𝑎𝑛 (−1e9≤𝑎𝑖≤1e9 )

    输出:
    每个样例一行,输出初始整数中的一个,题目保证有解;

    Examples
    input
    9
    3
    9 2 7
    3
    15 -4 11
    4
    -9 1 11 -10
    5
    3 0 0 0 3
    7
    8 16 8 0 8 16 8
    4
    0 0 0 0
    10
    27 1 24 28 2 -1 26 25 28 27
    6
    600000000 800000000 0 -200000000 1000000000 800000000
    3
    0 -1000000000 1000000000

    output
    9
    11
    -9
    3
    8
    0
    -1
    600000000
    0

    题目解析:
    由题目的定义可以知道,|A-B|是无法产生负数,那么如果数字中存在负数,则必然负数是初始数字;
    同理假设x是数组中的最大元素,并且此时数组中并没有负数,那么x必然也是初始元素,因为|A-B|在全为正数的情况下,无法产生更大的数值。

    #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;
     
    class Solution {
        static const int N = 201010;
        int a[N];
    public:
        void solve() {
            int t;
            cin >> t;
            while (t--) {
                int n;
                cin >> n;
                for (int i = 0; i < n; ++i) cin >> a[i];
                sort(a, a + n);
                if (a[0] < 0) cout << a[0] << endl;
                else cout << a[n - 1] << endl;
            }
        }
    }
    ac;
     
    int main(int argc, const char * argv[]) {
        // insert code here...
        
        ac.solve();
        
        return 0;
    }
    

    题目2

    题目链接
    题目大意:
    给出n个整数的排列,现在可以选择排列中的2个位置,交换位置上的元素。
    要求,交换之后所有子数组形成的排列尽可能的少。

    输入:
    第一行,整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
    每个样例2行
    第一行,整数𝑛 (3≤𝑛≤2e5)
    第二行,n个整数𝑎1,𝑎2,…𝑎𝑛

    输出:
    每个样例一行,输出交换的两个整数的位置;
    如果有多个答案,可以输出其中一个;(两个位置可以是相同的)

    Examples
    input
    8
    3
    1 2 3
    3
    1 3 2
    5
    1 3 2 5 4
    6
    4 5 6 1 2 3
    9
    8 7 6 3 2 1 4 5 9
    10
    7 10 5 1 9 8 3 2 6 4
    10
    8 5 10 9 2 1 3 4 6 7
    10
    2 3 5 7 10 1 8 6 4 9

    output
    2 3
    1 1
    5 2
    1 4
    9 5
    8 8
    6 10
    5 4

    题目解析:
    对于排列来说,最终的整数就是1,因为所有的排列都要从1开始;
    其次就是整数2,因为排列除了1,第二位是2;
    根据题目的要求,如果想要无法组成排列,那么最大数n也很重要,因为一旦1和2被n隔开,那么就无法形成排列(除非整个数组一起参与排列);
    那么我们用 x,y,z来表示1,2,n这三个整数的位置。
    容易知道,只要我们形成x<z<y或者y<z<x这样的位置顺序,那么所有子数组只有2个排列(1和n);
    只考虑x,y,z三个位置,我们知道交换一个位置,必然可以把z交换到中间去。

    为了简单实现,我们将x,y,z三个整数排序,然后将z与排序中间的位置交换即可。

    #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;
     
    class Solution {
        static const int N = 201010;
        int a[N];
    public:
        void solve() {
            int t;
            cin >> t;
            while (t--) {
                int n;
                cin >> n;
                int x, y, z;
                for (int i = 1; i <= n; ++i)  {
                    cin >> a[i];
                    if (a[i] == 1) x = i;
                    if (a[i] == 2) y = i;
                    if (a[i] == n) z = i;
                }
                int tmp[] = {x, y, z};
                sort(tmp, tmp + 3);
                cout << tmp[1] << " " << z << endl;
            }
        }
    }
    ac;
     
    int main(int argc, const char * argv[]) {
        // insert code here...
        
        ac.solve();
        
        return 0;
    }
    

    题目3

    题目链接
    题目大意:
    将1、2、3、、、、n x m个整数,填入到n x m的网格中;
    要求任何两个相邻的格子,格子上数字差的绝对值不是素数。
    现在求其中一个填充结果。

    输入:
    第一行,整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000)
    每个样例一行,整数𝑛, m (4≤𝑛, m≤1000)

    输出:
    每个样例输出n行,每行m个整数;(题目保证有解)

    Examples
    input
    3
    4 4
    5 7
    6 4

    output
    16 7 1 9
    12 8 2 3
    13 4 10 11
    14 5 6 15

    29 23 17 9 5 6 2
    33 27 21 15 11 7 1
    32 31 25 19 20 16 10
    26 30 24 18 14 8 4
    35 34 28 22 13 12 3

    2 3 7 11
    8 9 1 10
    17 13 5 4
    18 14 6 12
    19 23 15 21
    20 24 16 22

    题目解析:
    当n/m偶数时,从左到右,从上到小填写即可。例如n=4:
    1 2 3 4
    5 6 7 8
    9 10 11 12
    13 14 15 16
    ...

    每个数字和左右相邻都是1,上下相邻是2的倍数。

    当n/m是奇数时,比如说k=2时,n=(2k + 1)=5;
    如果还是采用原来解决方案,1和6的差距就是n=5,此时两数之差是质数;
    1 2 3 4 5
    6 7 8 9 10
    11 12 13 14 15
    ....
    但是知道,1和11的差是2 * n,不是质数;
    那么这个整数矩阵可以做一些简化,只考虑每行第一个整数:
    1
    n + 1
    2n + 1
    3n + 1
    4n + 1
    ...

    做一些调整
    1
    2n + 1
    4n + 1
    n + 1
    3n + 1
    ...

    这样上下整数的差就变成2n、2n、3n、2n,都是n的倍数,也即是都是合数。(注意,至少n>4才能用着这种方式)

    #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;
     
    class Solution {
        static const int N = 1010;
        int a[N][N];
    public:
        void solve() {
            int t;
            cin >> t;
            while (t--) {
                int n, m;
                cin >> n >> m;
                if (n % 2 == 0) {
                    for (int i = 1; i <= n; ++i)
                        for (int j = 1; j <= m; ++j)
                            a[i][j] = (j - 1) * n + i;
                }
                else {
                    for (int i = 1; i <= (n + 1)/2; ++i) {
                        for (int j = 1; j <= m; ++j) {
                            a[i][j] = (i - 1) * 2 * m + j;
                        }
                    }
                    
                    for (int i = 1; i <= n/2; ++i) {
                        for (int j = 1; j <= m; ++j) {
                            a[i + (n+1)/2][j] = (i - 1) * 2 * m + j + m;
                        }
                    }
                }
                
                for (int i = 1; i <= n; ++i) {
                    for (int j = 1; j <= m; ++j){
                        cout << a[i][j] << " ";
                    }
                    cout << endl;
                }
            }
        }
    }
    ac;
     
    int main(int argc, const char * argv[]) {
        // insert code here...
        
        ac.solve();
        
        return 0;
    }
     
    

    题目4

    题目链接
    题目大意:
    有n个节点的树,节点序号为1、2、3、、、n,现在小明开始用下面的方式开始绘制整棵树:
    1、先绘制节点1;
    2、按照边输入的顺序遍历,对于每一条边,如果存在一个节点已经绘制且另外一个节点没绘制,则绘制未存在的节点;
    3、遍历完成后,检查是否所有节点已经绘制完成,否则重新操作2;

    现在想知道,需要遍历多少次,才能绘制完所有节点;

    输入:
    第一行,整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
    每个样例第一行整数𝑛 (1≤𝑛≤2⋅1e5)
    接下来n-1行,每行有整数𝑢𝑖 and 𝑣𝑖 (1≤𝑢𝑖,𝑣𝑖≤𝑛 , 𝑢𝑖≠𝑣𝑖 )

    输出:
    对于每个样例,输出需要遍历的次数;

    Examples
    input
    2
    6
    4 5
    1 3
    1 2
    3 4
    1 6
    7
    5 6
    2 4
    2 7
    1 3
    1 2
    4 5

    output
    2
    3

    题目解析:
    先考虑简单的情况,假设4个节点,假如边顺序是:
    1 2
    2 3
    3 4
    那么结果,只要遍历一次即可;

    如果边顺序是:
    3 4
    2 3
    1 2
    则结果需要3次,因为每次遍历完都只能绘制1个节点;

    如果边顺序是:
    1 2
    3 4
    2 3
    则结果需要2次,第一次遍历可以产生1、2、3节点,第二次遍历则产生节点4;

    观察这个过程,就是从节点1开始遍历,当遇到下一个节点就有两个抉择:
    1、下个节点可以直接绘制,因为连接下一个节点的边,比当前节点要更晚;
    2、下个节点需要等下一次遍历,因为连接下一个节点的边,比当前节点要更早;

    通过上面这个方式,我们只需要遍历一次,就可以快速知道一条链路上,需要遍历多少次才能绘制完成;

    当我们知道一条链路的解法之后,对于一个棵树,其实就是不断重复根节点到叶子节点的dfs过程。

    #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;
     
    class Solution {
        static const int N = 201010;
        vector<int> g[N];
        map<pair<int, int>, int> h;
        int dfs(int u, int father) {
            int ret = 1;
            for (int i = 0; i < g[u].size(); ++i) {
                int v = g[u][i];
                if (v != father) {
                    ret = max(ret, dfs(v, u) + (h[make_pair(u, father)] > h[make_pair(u, v)]));
                }
            }
            return ret;
        }
        
    public:
        void solve() {
            int t;
            cin >> t;
            while (t--) {
                int n;
                cin >> n;
                h.clear();
                for (int i = 1; i <= n; ++i) g[i].clear();
                for (int i = 1; i < n; ++i) {
                    int u, v;
                    cin >> u >> v;
                    g[u].push_back(v);
                    g[v].push_back(u);
                    h[make_pair(u, v)] = i;
                    h[make_pair(v, u)] = i;
                }
                int ans = 0;
                for (int i = 0; i < g[1].size(); ++i) {
                    ans = max(ans, dfs(g[1][i], 1));
                }
                cout << ans << endl;
            }
        }
    }
    ac;
     
    int main(int argc, const char * argv[]) {
        // insert code here...
        
        ac.solve();
        
        return 0;
    }
     
    

    题目5

    题目链接
    题目大意:
    有两个长度为n的整数数组a和b;
    现在想要找到所有的(i, j)组合,满足 1≤𝑖<𝑗≤𝑛 且 𝑎𝑖⋅𝑎𝑗=𝑏𝑖+𝑏𝑗 .

    输入:
    第一行,整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
    每个样例2行
    第一行整数𝑎1,𝑎2,…,𝑎𝑛(1≤𝑎𝑖≤𝑛)
    第二行整数𝑏1,𝑏2,…,𝑏𝑛 (1≤𝑏𝑖≤𝑛 )

    输出:
    对于每个样例,输出存在的组合数量。

    Examples
    input
    3
    3
    2 3 2
    3 3 1
    8
    4 2 8 2 1 2 7 5
    3 5 8 8 1 1 6 5
    8
    4 4 8 8 8 8 8 8
    8 8 8 8 8 8 8 8

    output
    2
    7
    1

    题目解析:
    最直接做法,只需要枚举所有的i和j,计算是否满足要求,但是复杂度O(N^2),明显超过题目要求;
    分析题目的要求,组合数量对原有位置没有要求,那么可以对数组进行排序;
    但是不管数组a排序还是数组b排序,都无法满足快速求解;

    继续分析题目给出的条件,发现a和b的范围比较小,那么bi+bj应该小于2n;
    对于组合(i,j),我们假设ai<bi,那么ai作为乘法的较小值可以满足ai <= sqrt(2n)=633,这样ai的枚举范围就缩小很多,这似乎是一个突破口。

    那么是不是直接按照数组a的大小排序,然后遍历数组a,直到ai <= sqrt(2n)即可?
    这样当数组所有元素ai都<= sqrt(2n)时,复杂度依然超标。

    所以枚举的应该是ai所取的值。
    对于组合(i, j),有数字a[i]和a[j],以及b[i]和b[j],一共四个未知数;(注意这里我们假设了a[i] < a[j])
    我们枚举a[i]的值,先假设ai=x,那么对于数字a[j]和b[j]我们同样去枚举j∈[0, n]的情况,这样我们就知道了3个未知数,根据a[i]*a[j] = b[i] + b[j],我们可以推出 b[i] = y = a[i] * a[j] - b[j] = x * a[j] - b[j];
    此时我们只要知道在枚举到j时,前面出现过所有的a[i] = x并且 b[i]的值为y的数字即可;

    我们在遍历数组过程,要统计前面出现过的值为y的整数,可以用哈希来解决,用h[value]++的方式来记录,然后统计前面value出现次数就是h[value];

    注意:数组要按照a从小到大排序。
    因为,我们假设了a[i] < a[j],为了保证这个要求,我们需要对数组排序,并且在枚举到位置j时,另外一个位置i只能考虑[1, j - 1]这个区间。

    #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;
     
    class Solution {
        static const int N = 202010;
        pair<int, int> a[N];
    
    public:
        void solve() {
            int t;
            cin >> t;
            while (t--) {
                int n;
                cin >> n;
                for (int i = 0; i < n; ++i) {
                    scanf("%d", &a[i].first);
                }
                for (int i = 0; i < n; ++i) {
                    scanf("%d", &a[i].second);
                }
    //            sort(a, a + n);
                int m = sqrt(n * 2) + 1;
                lld ans = 0;
                for (int i = 1; i <= m; ++i) {
    //                map<int, int> h;
                    vector<int> h(n+1);
                    for (int j = 0; j < n; ++j) {
                        int y = i * a[j].first - a[j].second; // x = i时, second应该等于y
                        if (1 <= y && y <= n) {
                            ans += h[y];
                            if (h[y]) cout << i << "*" << a[j].first << "=" << y << "+" << a[j].second << endl;
                        }
                        if (a[j].first == i) {
                            h[a[j].second]++;
                        }
                    }
                }
                cout << ans << endl;
            }
        }
    }
    ac;
     
    int main(int argc, const char * argv[]) {
        // insert code here...
        
        ac.solve();
        
        return 0;
    }
     
    

    相关文章

      网友评论

          本文标题:程序员进阶之算法练习(八十六)

          本文链接:https://www.haomeiwen.com/subject/wrwbvdtx.html