Java教程

有趣的算法题(四)

本文主要是介绍有趣的算法题(四),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Talk is cheap,show me the code
And Matching
div2C
泪目了,昨晚这个C我能很快做出来的,结果没看到k的取值,以为k能取任何值,推了一个多小时没出结果,回去看题发现k小于等于n-1

题意,给定两个数n和k(n一定是2的整数次幂而且n大于等于4,k小于等于n-1),在0到n-1中,要找n/2个做&运算的二元组,让这些个二元组加起来的和等于k

如果能组成,就输出你的方案中的二元组,如过不能,就输出-1

思路:
1.在二进制下观察后会发现,相邻的两项合并可以取得最大值,那么只有一种情况是-1,就是n为4,k为3,其他情况都是有解的。
2.0和n-1,1和n-2这样配对是0,所以用一个数组存0到n-1
3.当k不等于n-1时,只需要吧k和n-1作为一个二元组,剩下的让他们两两做&运算为0就行
4.当k等于n-1时,需要把n-2和0交换,再把1和2交换

5.首位向接输出数组中元素

#include <bits/stdc++.h>
using namespace std;
int a[20000000],t,n,k;
int main()
{
    for(cin>>t;t;t--)
    {
        cin>>n>>k;
        for(int i=0;i<=n-1;i++)
            a[i]=i;
        if(n==4&&k==3)
            cout<<-1<<endl;
        else
        {
             if(k<n-1)
                 swap(a[0],a[k]);
             else
             {
                 swap(a[k-1],a[0]);
                 swap(a[1],a[2]);
             }
        }
        for(int i=0;i<=n/2-1;i++)
            cout<<a[i]<<" "<<a[n-i-1]<<endl;
    }
    return 0;
}

Shifting Sort
题意自行去洛谷看

思路:这是选择排序的变型,我们每次从i到n确定最小值坐标,然后把最小值移动到i的位置就行了

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

int main() {
    int t;
    for(cin>>t;t;t--)
    {
        int n;
        cin >> n;
        vector<int> a(n);
        vector<pii> actions;
        for (int i = 0; i < n; i++)
            cin >> a[i];
        for (int i = 0; i < n - 1; i++) 
        {
            int min_pos = i;
            for (int j = i + 1; j < n; j++)
                if (a[j] < a[min_pos])
                    min_pos = j;//确定最小值下标

            if (min_pos > i)//小优化,如果min_pos==i那么就不用进行操作了
            {
                actions.push_back({i, min_pos});//从i到最小值这个区间
                int opt = a[min_pos];
                for (int j = min_pos; j > i; j--)
                    a[j] = a[j - 1];
                a[i] = opt;
            }
        }
        cout << actions.size() << '\n';
        for (auto &lr: actions) {
            cout << lr.first + 1 << ' ' << lr.second + 1 << ' ' << lr.second - lr.first << '\n';
        }
    }
}

Swaps
给出两个长度为 nn 的序列 aa, bb,序列 aa 中的元素是 [1,2n][1,2n] 中的 奇数,序列 bb 的元素是 [1,2n][1,2n] 中的 偶数。 现可对两个序列进行操作,每次操作的步骤如下:

选取任意一个序列 aa 或 bb
选取一个下标 i ;; (i \in [1, n-1])i(i∈[1,n−1])
将选定序列的下标为 ii 的元素与下标为 (i+1)(i+1) 的元素交换
问最少经过多少次操作,使得序列 aa 的字典序小于序列 bb ?

思路:我们用一个数组去存储,这个数组下表m处存储的是m是第几个被输入进去的。因为我们所要用的次数只和这个元素有关。

洛谷的题解都很繁琐,可以看着这段代码,还是很好懂的。

#include <iostream>
#include <algorithm>
using namespace std;
int n,t,a[300001],i,j;
int main()
{
cin>>t;
while(t--){
	cin>>n;
	for(i=0;i<n;i++)
	cin>>j,a[j]=i;
	for(i=0;i<n;i++)
	cin>>j,a[j]=i;
	n*=2,i=j=n;
	while(n)
		j=min(a[n],j),i=min(a[n-1]+j,i),n-=2;
	cout<<i<<'\n';
}
}

期中j代表的是目前偶数移动到第一个位置位置的花费,i代表了总花费因为i=min(a[n-1]+j,i)中的a[n-1]+j

而我们是从后往前遍历的,后方偶数一定比前方的大,所以能确保后面的花费少就一定可以不用前面的

Carrying Conundrum
这个,,结论题或者数位DP也能做,然后位运算的这个结论也不是很清楚,就这样记住吧,数位DP那个思路说实在的,,太难了我不会而且一个C题如果卡这种程度的数位DP我赛时也写不出来。
题意:小a算数的时候满10不进一位,而是进两位,所以小b想知道,对于小a的计算结果有多少种方案让两个数相加能得到

结论:我们知道进位的话奇数位只能进位到奇数位上,偶数位只能进位到偶数位上,那么我们把奇数位的数记为x,偶数位上的数记为y最终答案就是(x+1)*(y+1)又因为0不能进位所以最终答案还要在这个基础上-2

#include <iostream>

using namespace std;

int main()
{
    int t;
    for(cin>>t;t;t--)
    {
        string s;
        cin>>s;
        long long odd=0,even=0;
        for(int i=0;i<(int)s.size();i+=2)
            odd=odd*10+(int)(s[i]-'0');
        for(int i=1;i<(int)s.size();i+=2)
            even=even*10+(int)(s[i]-'0');
        cout<<(odd+1)*(even+1)-2<<endl;
    }
    return 0;
}

思维题天花板?

Rings

#include <cstdio>
int t, n;
char s[20003];
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%s", &n, s + 1);
        bool ok = 0;//0表示符合情况4
        for (int i = 1; i <= n; i++)
            if (s[i] == '0'){
                ok = 1;
                if (i > (n >> 1))//此时[1,i-1]长度大于等于[n/2]
                    printf("1 %d 1 %d\n", i, i - 1);
                else//否则[i+1,n]长度大于等于[n/2]
                    printf("%d %d %d %d\n", i, n, i + 1, n);
                break;
            }
        if (!ok)//此时两个子串[1,n-1],[2,n]长度相同,且数值一样
            printf("1 %d 2 %d\n", n - 1, n);
    }
    return 0;
}

Make a Power of Two
一道比较简单的思维题,不涉及算法暴力做就行。
思路:我们暴力的把2的0到63次方全部和给定的数去寻找最长公共子序列,对于2的0到63次幂每一个数都有:ans=目标串长度+给定串长度-2*最长公共子序列,最终答案就是所有ans中的最小值

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    for(cin>>t;t;t--)
    {
        string s,temp;
        int res=100000000;
        cin>>s;
        for(int i=0;i<=63;i++)
        {
            int cnt=0;
            temp=to_string(1ll<<i);
            for(int j=0;j<s.length();j++)
            {
                if(cnt<temp.length()&&temp[cnt]==s[j])
                    cnt++;
                res=min(res,(int)(temp.length()+s.length())-cnt*2);
            }
        }
         cout<<res<<endl;
    }
    return 0;
}

这篇关于有趣的算法题(四)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!