新泰网站制作公司,东莞网络营销策划,源码网站开发,上海的最新新闻大二考核题解
题号题目考察知识点A有意思的监考二分答案B海绵宝宝的数独DFSC走楼梯递推D碱基配对kmpE好简单的题啊#xff0c;写它#xff01;最短路
写在前面#xff1a; 整体难度不大#xff0c;代码能力需要一些#xff0c;正常来说至少要会3题以上
A 有意思的监考 …大二考核题解
题号题目考察知识点A有意思的监考二分答案B海绵宝宝的数独DFSC走楼梯递推D碱基配对kmpE好简单的题啊写它最短路
写在前面 整体难度不大代码能力需要一些正常来说至少要会3题以上
A 有意思的监考
找最小值的最大标准的二分答案的模板只需要重新写一下check函数
#includebits/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(a1,an1);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::vectorstd::vectorint 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::vectorstd::vectorint 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::vectorstd::vectorint board(9, std::vectorint(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]) 即是我们想要的结果
* tipsmin 函数为 C 自带的库函数C语言并没有这个库函数可以自己写一个
*/#include iostream
#include cstringusing 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;
}另解
#includebits/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 碱基配对
思路 K M P KMP KMP算法遍历每一个子串 K M P KMP KMP基本思想发生不匹配时主串S的i不回溯子串 T T T的j回溯到 n e x t [ j ] next[j] next[j]对应位置的 k k k上。 ①用字符串数组存储每一组的碱基序列数组的元素是一串碱基序列 ②从第一串碱基序列字符串数组的第一个元素入手从最长的子串碱基序列本身开始与其他序列进行比对直到找到共有的子串为止 ③暴力列举每一个子串进行比对采用 K M P KMP KMP算法进行比较。
#includebits/stdc.h
using namespace std;void getNext(string S,int* next) //得到子串下面的数组
{int j,k;j0;k-1;next[0]-1; //子串0号元素下面数为-1while(j(S.size()-1)) //对子串所有元素下面赋值{if(k-1||S[j]S[k]) //如果k回到了第一个元素或者第j个元素等于第k个元素{j;k; //jknext[j]k; //子串第j个元素下面的数为k}elseknext[k]; //k为第子串第k个元素下面的数}
}bool Compare(string T,string *S,int n) //返回该子串是否是每一个序列的子串
{int aT.size(); //得到子串T的长度int next[a]; //建立子串的数组下标getNext(T,next); //给子串数组赋值int results[n]; //建立一个大小为n的数组判断子串是不是n-1个主串的公共子串for(int i0;in;i){results[i]0; //给数组hhh全赋初值0}for(int l1;ln;l){int aaS[l].size(); //得到主串的长度int i0,j0;while(iaa) //当主串下标没到达尾部时{if(j-1||S[l][i]T[j]){i;j;}elsejnext[j];if(ja){results[l]1;break;}}}for(int i1;in;i) //查看该子串是否为每一个主串下面的子串{if(results[i]!1)return false; //不是则返回false}return true; //反之是则返回true
}void Deal(string *aar,int n)
{string keyZ; //假定最长公共序列keystring try1; //第一个碱基序列的每一个字串int w0;for(int i60;i3;i--) //从最长字符串长度开始作为子串长度{if(w!0iw){coutkeyendl;return ;}for(int k0;k60-i;k) //开始位置{try1aar[0].substr(k,i); //第一个碱基序列的一个字串//couttry1endl;if(Compare(try1,aar,n)) //查看是否为公共字串{wi;if((try1.size()key.size())(try1key))keytry1;}}}if(key.size()3)coutno significant commonalitiesendl;elsecoutkeyendl;
}int main()
{int N;cinN; //输入数据集合的数目Nfor(int z0;zN;z) //输入集合的每一组元素{int n;cinn; //输入数据集合中碱基序列的数目nstring jjsz[n]; //建立jjsz[n]数组存放每一组碱基序列for(int x0;xn;x){cinjjsz[x]; //存放每一个碱基序列}Deal(jjsz,n); //开始处理}return 0;
}E 好简单的题啊写它 d i j k s t r a dijkstra dijkstra的模板但需要注意路径长度可能会爆 i n t int int需要开 l o n g l o n g long long longlong
#includebits/stdc.h
#define ll long long
const int MaxN 100010, MaxM 500010;
const ll inf0x3f3f3f3f3f;
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_queuenode 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;
}
