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;
}