前言:两道dp,好难哦。一道最短路径模板题,还行。货物摆放那题不优化电脑跑不出来,直线那题用斜率间接算b精度不达标答案一定错。杨辉三角也要想办法优化才能拿满分,暴力差不多拿一半吧。怎么说呢,混分还是可以,但是感觉编程题不好拿满分,填空题不优化也难拿到分,双向排序考场上感觉不大可能做出来,即使做出来性价比也不高,毕竟sort能混一半分。
题难度跨度有点大,难的很难,水的很水。
另外,水题是真的水,所以必须要拿到分才行,好好读题还是必不可少,不能杠难题,该混还是混。
能用搜索的越来越少了。
A空间
水题, 1MB0=1024KB=1024*1024B=1024*1024*8b
32位 也就是占4B
B卡片
水题:哈希+暴力emm~
C直线
这题有点意思儿
每次算出的直线斜率和直线的截距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货物摆放
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路径
典型的迪杰斯特拉的模板题,熟记模板一次过没啥问题
弗洛伊德也能做出来,不过需要等很久。我用弗洛伊德没做出来==
另外注意这是个无向图,双向存储自然不必多说
上代码
#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分=.=
只能说多注意细节吧
代码
#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杨辉三角形
下面的图形是著名的杨辉三角形:
如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下
数列:
给定一个正整数 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
————————————————————————
漏了一道双向排序
应该是倒数第二道题
有很多性质,难度挺大,因为很难看出来,用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; }