寒假训练题单

T_1  「土」巨石滚滚 (贪心) 

大致题意 : 有一块巨石和n个障碍物,  巨石的初始稳定性为m, 每个障碍物会损失ai的稳定性, 提供bi的稳定性, 当巨石的稳定性m<0时, 巨石便会粉碎, 给障碍物排序, 判断巨石是否能顺利滚下.

分析 : 此题的关键就是给障碍物排序, 通过这个排序来判断巨石能不能存活(bushi), 可分类讨论

一、 当bi>=ai时

巨石撞完障碍是会回复稳定性(0也算), 这类障碍需要优先撞 来提高巨石的攻击力(稳定性hh) 如果这类回复性的障碍都撞不掉, 遇到后面损失性的障碍就跟撞不掉了, 所以得把回复性的障碍放最前面, 即用c来表示回复性(bi - ai), 以c的降序排序

对于都是回复性的障碍要以能撞掉为前提, 从小撞到大, 比如: 一开始是100 撞 101 102 和 1 2这两个先撞了小的才能撞大的, 先撞大的就直接毁灭了, 所以回复性障碍以ai的升序排序

二、 当ai>bi时

巨石装完会损失稳定值, 这类障碍要最后撞 一开始没有思绪, 尝试 以a,c的升降序排序都不行

如 : 75 撞 50 45 和 70 40 这时是先撞a小的 而  70 撞 50 45 和 70 50 这是要先撞a大的

而这两个样例在撞完后, 是按撞后的m来判断, 而与之相关的只有b , c. 又因为m要和下一个障碍物的a比, 而m又是基于上一块的b, 所以 要以b来分析

通过对b的发现, 前提是损失性障碍, a一定大于b 所以 m撞完后一定比b大而不是a这是与回复性障碍刚好相反的性质, 所以损失性障碍要以b来排序, 要求每次装完m尽量大, 所以b尽量大, 以b的降序排序

综上:   排序就出来了: 先按c(b - a)的降序排序   c>=0时按a的升序   c<0按b的降序排

ac代码如下:

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e5+100;

struct node{
    int a,b,c;
//    void dif()
//        {
//            c=b-a;
//        }
//    bool operator<(const node& t)const // 重载运算符式排序
//        {
//            if(c*t.c<=0)
//                return c>t.c;
//            else if(c>0)
//                return a<t.a;
//            else
//                return b>t.b;
//        }
}s[N];

bool cmp(node &a, node &b){         // cmp式排序
    if(a.c*b.c<=0){
        return a.c>b.c;
    }else if(a.c>=0 && b.c>=0){
        return a.a<b.a;
    }else{
        return a.b>b.b;
    }
}


int main()
{
    int t;
    cin>>t;
    while(t--){
        long long n,m;             // 加和数据较大, ll防止数据溢出
        int flag=1;
        cin>>n>>m;
        for(int i = 0; i<n; i++){
            scanf("%d %d",&s[i].a, &s[i].b);
//            s[i].dif();
            s[i].c = s[i].b - s[i].a;
        }
//        sort(s,s+n);
        sort(s,s+n,cmp);
        for(int i = 0; i<n; i++){
            m-=s[i].a;
            if(m<0){
                flag = 0;
                break;
            }
            m+=s[i].b;
        }
        if(flag) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}

T_2  毒瘤xor (贪心+位运算+前缀和)

大致题意 : 有n个数a1,a2,a3...an, 给定区间l,r, 找到一个数X, 使得X在  区间l,r   内异或ai 的 和最大

分析 : 此题要求的是异或和最大, 就要使X异或每一位尽量大, 即每次异或结果尽量为1,  

可以判断l,r内每个数ai从第1位到末位1的数量(0的数量与1的数量在该区间长度内互补), 1的数量多就让那一位去异或0, 反之异或1, 如果数量相同就异或0(多组结果取最小值)

以下为暴力做法, 结果TLE了 :

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
const int N = 1e5+10;

int a[N];
int s0[32],s1[32]; // 分别即每一位0 1 的数量

void read(int c){

    int i=0;
    while(c){
        int ans;
        ans = c % 2; 
        if(ans) s1[++i]++; // 十转二的过程来计0 1 数量
        else s0[++i]++;
        c/=2;
    }
}
void mymemset(int s[]){
    for(int i = 1; i<=31; i++) s[i] = 0; // 初始化
}

int main()
{
    int n,q;
    cin>>n;
    for(int i = 0; i<n; i++) scanf("%d",&a[i]);
    cin>>q;
    while(q--)
    {
        mymemset(s1);
        mymemset(s0);  // 每组数组算完要初始化
        int l,r;
        long long res = 0;
        cin>>l>>r;
        int x = r - l + 1;
        for(int i = l-1; i<r; i++) read(a[i]);  // 每个数都读一遍, 结果显然是超时的
        for(int i = 31; i>=1; i--){
            if(s1[i]+s0[i]<x) s0[i]+=(x-(s1[i]+s0[i])); // 补0的数量
            if(s1[i]<s0[i]) res+=pow(2,i);     // 异或1的取值为改为上2的幂次, 0的还是0, 加和二转十
        }
        cout<<res/2<<endl; // 最后多乘了次2(不知道为啥) 除掉就行
    }
}

优化一下, 就是通过二维数组直接记每个数的该位的0 1 数量, 最后直接算前缀和就行, 即一波带走

ac代码如下 :

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
const int N = 1e5+10;

int s[N][35];

int main()
{
    int n,q,a;
    cin>>n;
    for(int i = 1; i<=n; i++){
        scanf("%d",&a);
        for(int j = 0; j<31; j++){
            s[i][j] = s[i-1][j]; // 预处理前缀和
            if((a>>j) & 1) s[i][j]++; // 第j位就右移j位, 将第j位移到最后, 再& 1判断是否为1
        }
    }
    cin>>q;
    while(q--)
    {
        int l,r;
        long long res = 0;
        cin>>l>>r;
        int x = r - l + 1;
        for(int i = 0; i<=30; i++){
                if(2*(s[r][i]-s[l-1][i])<x) res+=pow(2,i); // 判断0 1谁数量多
        }
        cout<<res<<endl; 
    }
}

T_3 兔子的区间密码 (思维+位运算)

大致题意 :  给定区间l,r , 在该区间内找到任意两数, 使他们异或的值最大

分析:  这个题可以用贪心写, 就是使两个数异或的值尽量为1, 但代码较为复杂, 所以换了种思维, 

观察样例, 不难得出要在1 10这个区间找到异或的最大值, 就先找二进制位数最大的第一个数, 即8(1000) 与他的下一位异或 7(0111) 这样就能得到位数更高且在那个位数下最大的值, 即8^7 = 15,同样, 其他样例也是如此

代码如下: 

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
const int N = 1e5+10;

int main()
{
    int t;
    cin>>t;
    while(t--){
        long long l,r;
        scanf("%lld %lld",&l,&r);
        if(l==r){             // 区间只有一个数时特判
            cout<<0<<endl;
        }else{
            long long n;
            for(int i = 62; i>=0; i--){
                long long  x = (long long)pow(2,i);
                if(r >= x){   // 循环找位数最大的第一个值
                    n = x;
                    break;
                }
            }
            long long res = n^(n-1);
            cout<<res<<endl;
        }
    }
}

显然, 结果wa了(笑哭)

因为寻找n的时候只考虑了右端, 而没考虑左端, 可能存在n不在区间内, 这是要先确定区间位数, 若这个区间内所有数都是一样的位数, 显然是找不到正确的n的, 若位数相等, 则这些数的首位都为1, 将端点异或即能得到位数 , 即 l^r. 如 1 ^ 10 = 11(1011) 二进制位有四位, 而 2 ^ 3 = 1( 1) 二进制位只有一位,再综合上面分析, 结果值是最高位的最大值, 如 1 10区间内 最高位有4位其最大值是 1111即15, 2 3 是 1(1), 3 4最高位是3 最大值是7(111)

ac代码如下 :

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
const int N = 1e5+10;

int main()
{
    int t;
    cin>>t;
    while(t--){
        long long l,r;
        scanf("%lld %lld",&l,&r);
        long long bit = l^r; // 区间只有1个数的情况结果为0 , 不需特判
        long long res=0;
        int i=0;
        while(bit){
            i++;       // 确定最高位数
            bit>>=1;
        }
        res = (long long)pow(2,i)-1;
        cout<<res<<endl;
    }
}

T_4 [NOIP1998]拼数 (思维)

大致题意 : 给n个数, 将这 n 个数拼成一个数, 使这个数最大, 如n=3时,3个整数13,312,343联接成的最大整数为:34331213

分析 : 首先想到的是要怎么拼, 肯定是让头位更大的去拼, 如 343 312 先让343排前面, 观察不难发现这个比较的原理就是字符串比较,  所以思路是用字符串数组去存每个数, 再用sort排序即可

代码如下 : 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const int N = 21;

string s[N];

bool cmp(string a, string b)
{
    return a>b;  // 按照字符串比较排序
}

int main()
{
    int n;
    cin>>n;
    for(int i = 0; i < n; i++) cin >> s[i];
    sort(s, s + n, cmp);
    for(int i = 0; i < n; i++) cout << s[i];
}

显然, 是wa的(不然我就不会在这写笔记2333)

因为没有考虑到特殊样例, 如220 22 这种 实际上是220 > 22, 220在前 结果就是22022<22220的,所以不能单纯的按a>b, 需要这种有相同的只需判断下a+b > b+a就行, 

ac代码如下 : 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const int N = 21;

string s[N];

bool cmp(string a, string b)
{
    return (a + b > b + a);
}

int main()
{
    int n;
    cin>>n;
    for(int i = 0; i < n; i++) cin >> s[i];
    sort(s, s + n, cmp);
    for(int i = 0; i < n; i++) cout << s[i];
}

T_5 字符串 (枚举区间)

大致题意 : 给定一个字符串, 一个字符串内包含26个字母就算合法, 要求找到最短的合法子串

分析 : 找最短的合法子串, 我们可以看做是找到一个最短的区间使得 区间内26个字母至少得有一个 

ac代码如下 : 

#include <iostream>
#include <string>
using namespace std;
const int N = 1e6+10;

int a[200];
string s;

bool Isok(){
    for(int i = 'a'; i<='z'; i++)
        if(!a[i]) return false;
    return true;
}

int main()
{ 
    cin>>s;
    int res = 1000010, l , r;
    for(r = 0; r<s.size(); r++){     // 遍历字符串寻找最短区间
        a[s[r]]++;                   
        while(Isok()){
            res = min(res,r-l+1);    // r遍历到第一次出现合法子串后, 开始维护区间
            a[s[l++]]--;
        }
    }
    cout<<res;
}

T_6 加减 (二分+前缀和)

大致题意 : 对长度为n的数组进行操作, 每次操作可使区间中任意一个数+1 - 1, 操作次数不超过k, 找到操作后重复数字最多的数量

分析 : 可以枚举区间, 先排序 , 在区间内操作, 使其全部变为中位数(假如全部变为首位, 则后四位都要往首位变, 且越末位, 变得次数越多, 容易超过k, 全部变末位同理, 所以要全部变为中位数), 再维护寻找最大值

以下是暴力做法 :

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
const int N = 1e5+10;

int a[N],n,k,res,s[N];

bool check(int l, int r){
    int mid = l+r>>1;
    int x = s[r]-s[mid-1] - (r-mid+1)*a[mid] + (mid-l+1)*a[mid] - s[mid] + s[l-1];
    if(x<=k) return true;
    else  return false;
}

int main()
{
    cin>>n>>k;
    for(int i = 1; i<=n; i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i = 1; i<=n; i++) s[i] = s[i-1] + a[i];
    int res = 0;
    for (int i = 1; i < n; i++){
        int l = i, r = n;
        while(!check(l,r) && r>(l+1)) r--;
        res = max(res, r-l+1);
    }
    cout<<res;
}

因为数据较大, 暴力是会超时的, 所以要用二分查找来优化代码(同理双指针也行)

以下为ac代码 : 

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
const int N = 1e5+10;

long long a[N],s[N];
int n,k;

bool check(int l, int r){
    long long mid = l+r>>1;
    long long x = s[r]-s[mid-1] - (r-mid+1)*a[mid] + (mid-l+1)*a[mid] - s[mid] + s[l-1];
    if(x<=k) return true;
    else  return false;
}

int main()
{
    cin>>n>>k;
    for(int i = 1; i<=n; i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i = 1; i<=n; i++) s[i] = s[i-1] + a[i];
    int res = 1;
    for (int i = 1; i < n; i++){
        int l = i, r = n;
        while (l < r) {
            int mid = r+l+1 >> 1;
            if (check(i, mid)) l = mid; //若不成立 让mid区间尽量靠近i越靠近越能实现 如1 3 6 8 20 mid = 6 不成立, mid减小所需操作会越来越小
            else r = mid - 1;
        }
        res = max(res, r - i + 1);
    }
    cout<<res;
}

上一篇:微信公众号开发入门教程第一篇


下一篇:第五篇、微信小程序-swiper组件