大二考核题解

大二考核题解

题号	题目	考察知识点
A	有意思的监考	二分答案
B	海绵宝宝的数独	DFS
C	走楼梯	递推
D	碱基配对	kmp
E	好简单的题啊，写它！	最短路

写在前面： 整体难度不大，代码能力需要一些，正常来说至少要会3题以上

A 有意思的监考

找最小值的最大，标准的二分答案的模板，只需要重新写一下check函数

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 100;
int a[N];
int n;
bool check(int mid)
{int t = a[1] + mid, cnt = 1;for(int i = 2 ; i <= n ; i ++){if(a[i] - t > mid){cnt ++;t = a[i] + mid;}}return cnt <= 3;
}int main()
{int t;cin >> t;while(t--){cin >> n;//cout << "n:"<<n << endl;for(int i = 1 ; i <= n ; i ++) cin >> a[i];//cout << a[n] << "an\n";sort(a+1,a+n+1);int l = 0 , r = a[n];while(l < r){int mid = (l + r) >> 1;if(check(mid)) r = mid;else l = mid + 1;}cout << l << endl;}	
}

B 海绵宝宝的数独

#include <iostream>
#include <vector>
// 检查当前填入的数字是否符合数独规则
bool isValid(std::vector<std::vector<int>>& board, int row, int col, int num) {
// 检查行和列for (int i = 0; i < 9; ++i) {if (board[row][i] == num || board[i][col] == num) {return false;}}
// 检查 3x3 区域int startRow = row - row % 3;int startCol = col - col % 3;for (int i = 0; i < 3; ++i) {for (int j = 0; j < 3; ++j) {if (board[i + startRow][j + startCol] == num) {return false;}}}return true;
}
// 使用回溯算法填充数独空格
bool solveSudoku(std::vector<std::vector<int>>& board) {for (int row = 0; row < 9; ++row) {for (int col = 0; col < 9; ++col) {if (board[row][col] == 0) {for (int num = 1; num <= 9; ++num) {if (isValid(board, row, col, num)) {board[row][col] = num;if (solveSudoku(board)) {return true;}board[row][col] = 0; // 回溯}}return false;}}}return true;
}
int main() {std::vector<std::vector<int>> board(9, std::vector<int>(9));
// 读取数独矩阵for (int i = 0; i < 9; ++i) {std::string row;std::cin >> row;for (int j = 0; j < 9; ++j) {board[i][j] = row[j] - '0'; // 将字符转换为对应的整数}}
// 解决数独solveSudoku(board);
// 输出填好的数独矩阵for (int i = 0; i < 9; ++i) {for (int j = 0; j < 9; ++j) {std::cout << board[i][j];}std::cout << "\n";}return 0;
}

C 走楼梯

/*
* 本题主要考察递推的思想
* 题目中想要求的是走楼梯的最小花费，起始位置为 0 或 1 你可以选择向上走一步或者两步
* 实际我们可以从后往前进行分析， 假设我们是从下标为 n - 1 的位置开始，最小花费为 cost[n - 1]
* 如果从下标为 n - 2 的位置开始，最小花费为 cost[n - 2]
* 如果从下标为 n - 3 的位置开始，最小花费为 cost[n - 3] + min(cost[n - 2], cost[n - 1])
* 如果从下标为 n - 4 的位置开始，最小花费为 cost[n - 4] + min((cost[n - 3] + min(cost[n - 2], cost[n - 1])), cost[n - 2])
* 假设我们用数组 dp 来记录从下标为 i 的位置开始的最小花费值，很容易可以得到递推公式
* dp[i] = cost[i] + min(dp[i + 1], dp[i + 2])
* 得到递推公式之后，我们可以从后往前遍历数组 cost[i]，从而倒推出 dp[0] 和 dp[1] 的值
* dp 数组的含义：从下标为 i 的位置开始的最小花费值，因此 min(dp[0], dp[1]) 即是我们想要的结果
* tips：min 函数为 C++ 自带的库函数，C语言并没有这个库函数，可以自己写一个 
*/#include <iostream>
#include <cstring>using namespace std;const int N = 1e5 + 10;
int cost[N];			///< 题目中给的cost数组 
int dp[N];				///< 从第 i 个位置开始走需要花费的最小值 
int n;
// ---- min函数写法 ------ 
/*
int min(int a, int b)
{if (a > b) return b;return a;
}
*/ 
int main()
{ memset(dp, 0, sizeof dp);		/// 将 dp 数组整体置 0 等同于 for(int i = 0; i < n; i ++ ) dp[i] = 0; cin >> n;for (int i = 0; i < n; i ++ ) {cin >> cost[i];}// 初始化递推数组 dp[n - 1] = cost[n - 1];dp[n - 2] = cost[n - 2];// 根据递公式进行计算for (int i = n - 3; i >= 0; i -- ) {dp[i] = cost[i] + min(dp[i + 1] , dp[i + 2]);}cout << min(dp[0], dp[1]) << endl;return 0;
}

另解

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
int cost[N], f[N]; 
int main()
{int n;cin >> n;memset(f,0x3f,sizeof f);for(int i = 0 ; i < n ; i++) cin >> cost[i];f[0] = 0, f[1] = 0;for(int i = 2 ; i <= n ; i ++)f[i] = min(f[i-1]+cost[i-1],f[i-2]+cost[i-2]);cout << f[n];return 0;
}

D 碱基配对

思路：$KMP$算法遍历每一个子串
$KMP$基本思想：发生不匹配时，主串S的i不回溯，子串$T$的j回溯到$next[j]$对应位置的$k$上。
①用字符串数组存储每一组的碱基序列，数组的元素是一串碱基序列；
②从第一串碱基序列（字符串数组的第一个元素）入手，从最长的子串（碱基序列本身）开始与其他序列进行比对，直到找到共有的子串为止；
③暴力列举每一个子串进行比对，采用$KMP$算法进行比较。

#include<bits/stdc++.h>
using namespace std;void getNext(string S,int* next)  //得到子串下面的数组
{int j,k;j=0;k=-1;next[0]=-1;  //子串0号元素下面数为-1while(j<(S.size()-1))  //对子串所有元素下面赋值{if(k==-1||S[j]==S[k])  //如果k回到了第一个元素或者第j个元素等于第k个元素{j++;k++;  //j++；k++；next[j]=k;  //子串第j个元素下面的数为k}elsek=next[k];  //k为第子串第k个元素下面的数}
}bool Compare(string T,string *S,int n)  //返回该子串是否是每一个序列的子串
{int a=T.size();  //得到子串T的长度int next[a];  //建立子串的数组下标getNext(T,next);  //给子串数组赋值int results[n];  //建立一个大小为n的数组判断子串是不是n-1个主串的公共子串for(int i=0;i<n;i++){results[i]=0;  //给数组hhh全赋初值0}for(int l=1;l<n;l++){int aa=S[l].size();  //得到主串的长度int i=0,j=0;while(i<aa)  //当主串下标没到达尾部时{if(j==-1||S[l][i]==T[j]){++i;++j;}elsej=next[j];if(j==a){results[l]=1;break;}}}for(int i=1;i<n;i++)  //查看该子串是否为每一个主串下面的子串{if(results[i]!=1)return false;  //不是则返回false}return true;  //反之是则返回true
}void Deal(string *aar,int n)
{string key="Z";  //假定最长公共序列keystring try1;  //第一个碱基序列的每一个字串int w=0;for(int i=60;i>=3;i--)  //从最长字符串长度开始作为子串长度{if(w!=0&&i<w){cout<<key<<endl;return ;}for(int k=0;k<=60-i;k++)  //开始位置{try1=aar[0].substr(k,i);  //第一个碱基序列的一个字串//cout<<try1<<endl;if(Compare(try1,aar,n))  //查看是否为公共字串{w=i;if((try1.size()>=key.size())&&(try1<key))key=try1;}}}if(key.size()<3)cout<<"no significant commonalities"<<endl;elsecout<<key<<endl;
}int main()
{int N;cin>>N; //输入数据集合的数目Nfor(int z=0;z<N;z++)  //输入集合的每一组元素{int n;cin>>n;  //输入数据集合中碱基序列的数目nstring jjsz[n];  //建立jjsz[n]数组存放每一组碱基序列for(int x=0;x<n;x++){cin>>jjsz[x];  //存放每一个碱基序列}Deal(jjsz,n);  //开始处理}return 0;
}

E 好简单的题啊，写它！

$dijkstra$的模板，但需要注意路径长度可能会爆$int$，需要开$longlong$

#include<bits/stdc++.h>
#define ll long long
const int MaxN = 100010, MaxM = 500010;
const ll inf=0x3f3f3f3f3f;
struct edge
{int to, dis, next;
};edge e[MaxM];
ll head[MaxN], dis[MaxN], cnt;
bool vis[MaxN];
int n, m, s;inline void add_edge( int u, int v, int d )
{cnt++;e[cnt].dis = d;e[cnt].to = v;e[cnt].next = head[u];head[u] = cnt;
}struct node
{ll dis;ll pos;bool operator <( const node &x )const{return x.dis < dis;}
};std::priority_queue<node> q;inline void dijkstra()
{dis[s] = 0;q.push( ( node ){0, s} );while( !q.empty() ){node tmp = q.top();q.pop();int x = tmp.pos, d = tmp.dis;if( vis[x] )continue;vis[x] = 1;for( int i = head[x]; i; i = e[i].next ){int y = e[i].to;if( dis[y] > dis[x] + e[i].dis ){dis[y] = dis[x] + e[i].dis;if( !vis[y] ){q.push( ( node ){dis[y], y} );}}}}
}int main()
{scanf( "%d%d%d", &n, &m, &s );for(int i = 1; i <= n; ++i)dis[i] = inf;for( register int i = 0; i < m; ++i ){register int u, v, d;scanf( "%d%d%d", &u, &v, &d );add_edge( u, v, d );}dijkstra();for( int i = 1; i <= n; i++ )if(dis[i]!=inf) printf( "%lld ", dis[i] );else printf("inf ");return 0;
}