前言:两道dp,好难哦。一道最短路径模板题,还行。货物摆放那题不优化电脑跑不出来,直线那题用斜率间接算b精度不达标答案一定错。杨辉三角也要想办法优化才能拿满分,暴力差不多拿一半吧。怎么说呢,混分还是可以,但是感觉编程题不好拿满分,填空题不优化也难拿到分,双向排序考场上感觉不大可能做出来,即使做出来性价比也不高,毕竟sort能混一半分。
题难度跨度有点大,难的很难,水的很水。
另外,水题是真的水,所以必须要拿到分才行,好好读题还是必不可少,不能杠难题,该混还是混。

能用搜索的越来越少了。

A空间

1.png

水题,  1MB0=1024KB=1024*1024B=1024*1024*8b
32位   也就是占4B

B卡片

2.png

水题:哈希+暴力emm~

C直线

3.png

这题有点意思儿

每次算出的直线斜率和直线的截距b都存起来,新的直线如果已经被存储过,那么就pass掉
如果没有存储过就存进去,最后输出count数量
这里不是关键,关键是求直线b截距的时候不能通过k来求,这样会造成精度影响,这里通过(c*b-a*d)/(c-a)公式来求

上代码


#include<bits/stdc++.h>
using namespace std;
float xielv(float a,float b,float c,float d)
{
	return (b-d)/(a-c);
}
float b(float a,float b,float c,float d)
{
	return (c*b-a*d)/(c-a);
}
int main()
{
	float i,j,k,f,posb,posk;
	long long m,n;
	float c[100000][2];
	long long s=0,sign;
	long long count=0; //斜率数量 
	for(i=0;i<20;i++)
	{
		for(j=0;j<21;j++)
		{
			for(k=0;k<20;k++)
			{
				for(f=0;f<21;f++)
				{
					if(i!=k)//如果x不相等   
					{
						sign=0;
						//先求出直线斜率 b
						posk=xielv(i,j,k,f);
						posb=b(i,j,k,f);
						//和count中所有元素进行比较
						for(m=0;m<count;m++)
						{
							if(posk==c[m][0]&&posb==c[m][1])
							{
								sign=1;break;//已经存在 
							}
						 } 
						if(sign==0)
						{
							c[count][0]=posk;
							c[count][1]=posb;
							count++;
						} 
					}
				}
			}
		}
	}
	cout<<count;
 } 
D货物摆放

4.png

long long类型约可以存储19位,存储n绰绰有余

这道题没有考到什么算法,一个模拟题,考验编程能力和思维

用3个箱子存放n能够整除的数,然后计算

这里为什么要分开存储,将箱子分成了两半,这样效率更快==

其实多等会也无妨,毕竟填空


#include<bits/stdc++.h>
using namespace std;
int main()
{
	vector<long long> p;
	vector<long long> a;
	vector<long long> b;
	long long n=2021041820210418;
	long long gen=sqrt(n);
	long long sum=0,i,j,k;
	for(i=1;i<=gen;i++)
	{
		if(n%i==0)//将n能够整除的数存起来 
		{
			p.push_back(i);
			a.push_back(i);
			b.push_back(i);
			if(i*i!=n)//然后存放另一边,也就是说,n能够整除的数,我们全部都存进去了,存到三个箱子里 
			{
				p.push_back(n/i);
				a.push_back(n/i);
				b.push_back(n/i);
			}
		}
	}
	for(i=0;i<p.size();i++)
	{
		cout<<a[i]<<' ';
	}
	for(i=0;i<p.size();i++)
	for(j=0;j<a.size();j++)
	for(k=0;k<b.size();k++)
	{
		if(p[i]*a[j]*b[k]==n)//将三个箱子里的东西拿出来计算 
		{
			cout<<"!";
			sum++;
		}
	}
	cout<<sum;
 } 


E路径

5.png

典型的迪杰斯特拉的模板题,熟记模板一次过没啥问题
弗洛伊德也能做出来,不过需要等很久。我用弗洛伊德没做出来==

另外注意这是个无向图,双向存储自然不必多说

上代码


#include<bits/stdc++.h>
#define INF 9999999999
#define ll long long 
using namespace std;
long long begint=1,endt=2021,n=2021,m; 
long long low[3000],mapt[3000][3000];
bool visit[3000];
ll gongbei(int a,int b)
{
	ll r,i=a,j=b;
	do{
		r=i%j;
		i=j;
		j=r;
	}while(j);
	return a*b/i;
}
//模板
void dijkstra()
{ 
	int m_len,index,i,j,step_len;
	for(i=1;i<=n;i++){
		low[i]=mapt[begint][i];//初始化low
	}
	for(i=1;i<=n;i++){
		m_len=INF;
		index=i;
		for(j=1;j<=n;j++){//查找最短未访问距离
			if(low[j]<m_len && !visit[j]){
				m_len=low[j];
				index=j;
			}
		}
		visit[index]=true;
		for(j=1;j<=n;j++){
			step_len=m_len+mapt[index][j];
			if(step_len<low[j]){//是否更新距离
				low[j]=step_len;
				visit[j]=false;
			}
		}
	}
	cout<<low[endt]<<endl;
}
int main()
{
	begint=1,endt=2021;
	int i,j;
	fill(mapt[0],mapt[0]+3000*3000,INF);
	for(i=1;i<=2021;i++)
	{
		for(j=i;j<=i+21;j++)
		{
			if(i!=j)
			{
				ll f=gongbei(i,j);
				mapt[i][j]=f;
				mapt[j][i]=f;
			}
		}
	}
	dijkstra();
}


F时间显示

水题模拟题,15分=.=

只能说多注意细节吧


6.png

代码


#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ll n;
	cin>>n;
	n=n/1000;
	n=n%(24*60*60);
	if(n/60/60<10)
		cout<<0;
	cout<<n/60/60<<':';
	if(n/60%60<10)
		cout<<0; 
	cout<<n/60%60<<':';
	if(n%60<10)
		cout<<0;
	cout<<n%60; 
}
G砝码称重



【问题描述】
你有一架天平和 N 个砝码,这 N 个砝码重量依次是 W1, W2, · · · , WN。
请你计算一共可以称出多少种不同的重量?
注意砝码可以放在天平两边。
【输入格式】
输入的第一行包含一个整数 N。
第二行包含 N 个整数:W1, W2, W3, · · · , WN。
【输出格式】
输出一个整数代表答案。
【样例输入】
3
1 4 6
【样例输出】
10
【样例说明】
能称出的 10 种重量是:1、2、3、4、5、6、7、9、10、11。
1 = 1;
2 = 6 − 4 (天平一边放 6,另一边放 4);
3 = 4 − 1;
4 = 4;
5 = 6 − 1;
6 = 6;
7 = 1 + 6;
9 = 4 + 6 − 1;
10 = 4 + 6;
11 = 1 + 4 + 6。
【评测用例规模与约定】
对于 50% 的评测用例,1 ≤ N ≤ 15。
对于所有评测用例,1 ≤ N ≤ 100,N 个砝码总重不超过 100000。
dp题== 看见就头疼  这里建议采用手动做表的方式推导状态转移方程



#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int w[10005];
int dp[105][200005];
int m; 
int main() {
    int n;
    cin >> n;
    for (int k = 1; k <= n; k++) {
         scanf("%d", &w[k]);
        m += w[k];
    }
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
             dp[i][j] = dp[i - 1][j] + dp[i - 1][j + w[i]] + dp[i - 1][abs(j - w[i])];
        }
    }
    int count = 0;
    for (int i = 1; i <= m; i++) {
        if (dp[n][i]) {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

 H杨辉三角形

下面的图形是著名的杨辉三角形:
如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下
数列:
7.png

给定一个正整数 N,请你输出数列中第一次出现 N 是在第几个数?
【输入格式】
输入一个整数 N。
【输出格式】
输出一个整数代表答案。
【样例输入】
6
【样例输出】
13

这个题好像可以暴力打表混分,但是过不了所有测试点

我的想法是一边计算,一边判断,一边计数

如果判断到输入的这个数,cnt加后直接break

还是不行,标准答案是计算一半,然后维护一半=.=

好好学习下大佬的代码


#include <iostream>
using namespace std;
long long a[100010],b[100010];//开两个数组,一个保存上一行那一半的数,一个保存目的行那一半的数
int main()
{
  a[0]=1;
  b[0]=1;
  long long n;
  cin>>n;
  if(n==1){
    cout<<1;
    return 0;
  }
  for(int i=3;i<=44723;i++){//这个是最高循环次数,你可以自己找
    int m=i/2;//只要一半
    for(int j=1;j<=m;j++){
        if(j==m&&i%2==1){//如果行数为奇数那么就有个中间数,就是上一行前面数的两倍
            b[j]=a[j-1]*2;
        }
        else{
            b[j]=a[j-1]+a[j];//杨辉三角
        }
        a[j-1]=b[j-1];//更新a数组
        if(b[j]==n){
            cout<<i*(i-1)/2+j+1;//输出
            return 0;
        }
    }
    a[m]=b[m];//更新a数组
    if(b[1]>n){//快速判断,我们想想,在没找到目的数之前,如果有一行的第二个数比目的数还要大,那么肯定就不会再次出现,直接快速判断输出结果为n行的第二个数。
        cout<<n*(n+1)/2+2;
        return 0;
    }
  }
  cout<<n*(n+1)/2+2;//防止溢出
  return 0;
}


J括号序列

试题 J: 括号序列
时间限制: 5.0s 内存限制: 512.0MB 本题总分:25 分
【问题描述】
给定一个括号序列,要求尽可能少地添加若干括号使得括号序列变得合法,
当添加完成后,会产生不同的添加结果,请问有多少种本质不同的添加结果。
两个结果是本质不同的是指存在某个位置一个结果是左括号,而另一个是右括
号。
例如,对于括号序列 (((),只需要添加两个括号就能让其合法,有以下几
种不同的添加结果:()()()、()(())、(())()、(()()) 和 ((()))。
【输入格式】
输入一行包含一个字符串 s,表示给定的括号序列,序列中只有左括号和
右括号。
【输出格式】
输出一个整数表示答案,答案可能很大,请输出答案除以 1000000007 (即
10 9 + 7) 的余数。
【样例输入】
((()
【样例输出】
5

一道dp的题,很难看出来也很难推出来。属实压轴题了

这里给出大佬链接
https://blog.csdn.net/qq_35577488/article/details/117756909?spm=1001.2101.3001.6650.1&utm_medium=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-1.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-1.pc_relevant_default&utm_relevant_index=2


————————————————————————

漏了一道双向排序

应该是倒数第二道题

双向.png

有很多性质,难度挺大,因为很难看出来,用sort大概能过一半的测试点。

这里给出yxc的代码


#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n, m;
PII stk[N];
int ans[N];

int main()
{
    scanf("%d%d", &n, &m);
    int top = 0;
    while (m -- )
    {
        int p, q;
        scanf("%d%d", &p, &q);
        if (!p)
        {
            while (top && stk[top].x == 0) q = max(q, stk[top -- ].y);
            while (top >= 2 && stk[top - 1].y <= q) top -= 2;
            stk[ ++ top] = {0, q};
        }
        else if (top)
        {
            while (top && stk[top].x == 1) q = min(q, stk[top -- ].y);
            while (top >= 2 && stk[top - 1].y >= q) top -= 2;
            stk[ ++ top] = {1, q};
        }
    }
    int k = n, l = 1, r = n;
    for (int i = 1; i <= top; i ++ )
    {
        if (stk[i].x == 0)
            while (r > stk[i].y && l <= r) ans[r -- ] = k -- ;
        else
            while (l < stk[i].y && l <= r) ans[l ++ ] = k -- ;
        if (l > r) break;
    }
    if (top % 2)
        while (l <= r) ans[l ++ ] = k -- ;
    else
        while (l <= r) ans[r -- ] = k -- ;

    for (int i = 1; i <= n; i ++ )
        printf("%d ", ans[i]);
    return 0;
}