您的位置: 首页  >  文章  >  qbxt第三天测试

qbxt第三天测试

分类: 文章 • 2024-12-12 12:16:34

不开心的测试!三个小时的考试时间花费两个小时在第一个模拟上面，有点难受，吸取经验教训，开始解题

第一题：

qbxt第三天测试

思路

思路一：单调性：

通过单调性的变化次数来判断，如果变化次数>2,则可视作为NO
注意！！！！本人因为这小小的一个问题被困2个小时
需要判断这一段（降序）的之后的一个元素大于这一段的首元素！！如果没有判断这个会导致很严重的问题，不开森

代码附上：

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=10000010;
int a[maxn],n,dy=1,tt=0,mm=-1,nn=1;
int main(){
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	cin >> n;
	scanf("%d",&a[1]);
	for(int i=2;i<=n;i++){
		scanf("%d",&a[i]);
		if(tt>3) continue;
		
		if(dy&&a[i-1]>a[i]){
			mm=i-1;
			tt++;
			dy=0;	
		}
		if(!dy&&a[i-1]<a[i]){
			if(a[mm]>a[i]){
				nn++;
			}
			dy=1;
			tt++;
		}
	}
	if(nn!=1){
		cout << "NO";
		return 0;
	}
	if(tt<3){
		cout << "YES";
		return 0;
	}
	else{
		cout << "NO";
		return 0;
	}
}

思路二：

本蒟蒻当时没有想到，其实这个更简单

通过找到这一个区间之后直接反转，通过判断这个被反转后的区间是否满足单调，如果不满足则GG
啊啊啊啊，为什么这个如此简单不需要判断前后关系
被单调性冲昏了头脑的我

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 10000070
using namespace std;
int a[maxn],n,L,r;

int main(){
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	cin >> n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=2;i<=n;i++){
		if(a[i-1]>a[i]){
			L=i-1;
			r=i;
			while(++i<=n&&a[i-1]>a[i]){
				r++;
			}
		//	cout << L << "	"<<r; 
			break;
		}
	}
	
	reverse(a+L,a+r+1);
	
	for(int i=2;i<=n;i++){
		if(a[i-1]>a[i]){
			cout << "NO";
			return 0;
		}
	}
	cout << "YES";
	return 0;
}

第二题：

第二题基本是数论知识，之后得慢慢体悟目前不会。。。

qbxt第三天测试

标准答案：高级的很
回去再总结提高吧，这里把那位大犇的答案贴上

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int p=1e9+7;
LL gcd(LL a,LL b){
    return b?gcd(b,a%b):a;
}
LL pow(LL a,LL b,LL p){
    LL ret=1%p;
    while(b){
        if(b&1) ret=ret*a%p;
        b>>=1;
        a=a*a%p;
    }
    return ret;
}
LL solve(LL a,LL b,LL c,LL d){
    LL e=min(b,d);
    LL g=gcd(a,c);
    if(g==1){
        return 1;
    }
    LL part1=pow(g,e,p);
    LL part2=1;
    if(b<d){
        part2=solve(a/g,b,c,d-b);
    }
    if(b>d){
        part2=solve(a,b-d,c/g,d);
    }
    return part1*part2%p;
}
int main(){
    freopen("gcd.in","r",stdin);
    freopen("gcd.out","w",stdout);
    int a,b,c,d;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    printf("%d\n",(int)solve(a,b,c,d));


    return 0;
}

第三题：

qbxt第三天测试

终于到了本蒟蒻会的题（看来我好像还是很聪明的样子），整场比赛花了15min撸完的。但很可惜只拿了40分，其他全部TLE。原因很简单，DFS效率太低了，这道题对于本人而言已是尽力全力。。高级做法回头体悟，现在把代码贴上

#include<iostream>
#include<algorithm>
#define maxn 1000000
using namespace std;
long long n,k,b[50],a[maxn],sum=0,tt=0;

void dp(int pos){
	if(pos>n) return;	sum=sum+b[pos];
	a[++tt]=sum;
	dp(pos+1);
	sum-=b[pos]; 	
	dp(pos+1);
}


int main(){
	freopen("subset.in","r",stdin);
	freopen("subset.out","w",stdout);
	cin >> n >> k;
	for(int i=1;i<=n;i++) cin >> b[i];
	dp(1);
	sort(a,a+tt+1);	
	cout << a[k-1];
	fclose(stdout);
	return 0;
}

大犇的暴力解法（太厉害了。。本人）：充分运用计算机中的二进制存储方式来表达每一个集合的情况

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
// by zrt
using namespace std;

typedef long long LL;

int n,k;
LL a[105];
LL b[(1<<30)+5];
int lowbit(int x){
	return x&-x;
}
int main(){
	cin >> n>>k;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<n;i++) b[1<<i] = a[i];
	for(int i=1;i<(1<<n);i++){
		b[i]=b[i^lowbit(i)]+b[lowbit(i)];
	}
	nth_element(b,b+k-1,b+(1<<n));
	cout<<b[k-1]<<endl;
	return 0;
}

大犇的最巨思想：不仅仅只优化到表达集合状态上面，而且使用了一系列本人囫囵吞也吞不下的骚操作：代码奉上：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
// by zrt
using namespace std;

typedef long long LL;

LL n,k;
int n1,n2;

LL a[105];
LL b1[(1<<18)+5];
LL b2[(1<<18)+5];

int lowbit(int x){
	return x&-x;
}
void prepare(LL a[],LL b[],LL n){
	for(int i=0;i<n;i++) b[1<<i] = a[i];
	for(int i=1;i<(1<<n);i++){
		b[i]=b[i^lowbit(i)]+b[lowbit(i)];
	}
}

bool judge(LL x){
	int p1=0,p2=0;
	while(p2+1<(1<<n2) && b1[p1]+b2[p2+1]<=x)  p2++;
	LL cnt = 0;
	while(p1<(1<<n1)){
		while(p2>=0&&b1[p1]+b2[p2]>x) p2--;
		if(p2<0) break;
		cnt+=p2+1;
		p1++;
	}
	return cnt>=k;
}
int main(){
	freopen("subset.in","r",stdin);
	freopen("subset.out","w",stdout);
	cin >> n>>k;
	for(int i=0;i<n;i++) cin>>a[i];
	n1= n/2,n2 = n-n1;
	prepare(a,b1,n1);
	prepare(a+n1,b2,n2);
	sort(b1,b1+(1<<n1));
	sort(b2,b2+(1<<n2));
	LL l=-1,r=35*1LL*int(1e9);
	while(r-l>1){
		LL mid=(l+r)/2;
		if(judge(mid)) r=mid;
		else l=mid;
	}
	cout<<r<<endl;
	return 0;
}

这一次的考试虽然以本人巨难受结尾，但是给予本人不少经验

  • 确定了自己的目标：省一 250分左右！

  • 初赛考试内容不会涉及太多数据结构，这次学习的足以，再加上提高篇的部分足够应付

  • 回去后要多多加强基础的四大操作的练习，在之后的操作中不能犯下这些小问题： 贪心、枚举、BFS&DFS、模拟；这四大语法的拿下足以应对复赛前两道题

  • 要开始准备数论部分，主要以一本通上的内容集中通关！！

  • 以后每天背诵模板

对上述的总结

那么每天的事情：

  • 默写三个数据结构模板
  • 贪心、枚举、模拟、搜索各一道题
  • 数论公式推导，背诵两个基于数论的操作，并实际运用一道题
  • 运用数据结构模板完成两道题
  • 每周自己测验两次来模拟考试时候的感觉，不能再想这次一样了。一次做网上的模拟题，一次做从2012年开始的提高题
  • 复习错题
  • 每周集中解决问题
  • 找个老师
  • 学英语

相关推荐