脑子快快长!
1. 数组变身大变形 - 蓝桥云课 (lanqiao.cn)
做事要抓住事情的本质,要抓住根本,不要被外面所迷惑了
这道题的本质就是:在数组a中数值相同的下标,在字符串s中也要相同也要是同样的字母
哎呀哎呀,为什么我看不到本质啊啊啊啊啊啊.....
嗦一下:循环中 i 指向迁前一个元素,j 指向后一个元素,所以 i 最后指向的是倒数第二个元素,因为最后一个是 j 指向的。它们要进行两两比较,所以for循环括号中的表达式是这么写
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, t;
int a[55];
cin >> t;
while(t--){
cin >> n;
string s;
for(int i = 0; i < n; i++){
cin >> a[i];
}
cin >> s;
int flag = 1;
for(int i = 0; i < n-1; ++i){
for(int j = i; j < n; ++j){
if(a[i] == a[j] && s[i] != s[j]){
flag = 0;
break;
}
}
if(flag == 0){
break;
}
}
if(flag == 1)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
2. 字符串切分 - 蓝桥云课 (lanqiao.cn)
虽然这道题不难,但是它是我经过挣扎思考做出来的~~
首先看到这个我就想遍历把它分割,然后就在想怎么分割,按照n/k个份数分隔,可是题目没说要分成相等的长度,然后我又想模拟,想着怎么生成,七想八想。。。后面我就看到至少一个
我就想遍历这个字符串,哪个字母最多就可以构成几个啊。。。这么简单的事情。。。。。。
当时还觉得自己可棒 不知道在干吗不知道不知道TT
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, max = 0;
int cal[1000010] = {0};
string s;
cin >> n;
cin >> s;
for(int i = 0; i < s.length(); i++){
cal[s[i]]++;
if(cal[s[i]] > max){
max = cal[s[i]];
}
}
// if(max % 2 == 0)
cout << max;
// else
// cout << max - 1;
return 0;
}
但是小姐姐你当时为什么后面要判断一下奇偶
3. 最优修改 - 蓝桥云课 (lanqiao.cn)
我天呢!!这是今天最Dior的问题,我看题解看了挺久的
这是一个最短路径问题,用迪杰斯特拉算法和邻接矩阵解决的
首先要明白字母1修改成字母2你不能直接改,你要先把字母1改成字母3再改成字母2,这个代价才会最小,这是题目的要求。我发现有时候我半天读不懂题
然后题干中给出两个字符串和邻接矩阵
接着你就要根据给的字符串,把当前的字母看成一个个节点
本题中
- map[i][j]数组是题目中给出的邻接矩阵
- dist[i][j]数组是表示从字母 i 转换到字母 j 所需要的最小代价
- flag[i]数组是标记字母i 已经知晓当时最短路径
- p数组记录前驱节点 如p[i] = j 代表 i 的前驱节点是 j 本题中无意义 因为每个字母都可以转换
// 迪杰斯特拉操作
首先初始化当前字母 u 到其他所有字母的初始代价(就是根据题干中所给出的邻接矩阵所得
标记此时已经知晓当前字母u的到各个字母的最短路径(设置flag数组为true)
接着是核心操作:
找字母每个字母到其他字母的最短路径,只要路径最短
外层循环,遍历每个字母,确保都进行找其最小路径的操作
初始化临时变量temp无穷大,表示还没有找到新的最短距离
内层循环,遍历所有字母节点,看哪个节点与外层循环的字母节点路径最短:
如果节点 j 还没被处理过,即flag[j] == false 而且 dist[u][j] < temp;说明此时的字母u还没有与字母 j 建立联系,还不知道他们两个之间的最短路径,然后就把 u 和 j 建立联系,更新临时变量temp 为当前字母 u 到字母 j 的更短距离,然后内循环遍历每个字母,做的事情就是为了找到字母 u 与 哪个字母有它的最短路径
如果t == u的话说明,每个字母的最短路径都找完了,我说为什么,通义千问说:当找到字母 t 与源节点 u 相同时,说明在当前状态下,源节点 u 到自身的最短距离是已知的,且这个距离固定为0,由于我们知道源节点到自身的最短距离不会再发生变化,代表在当前迭代中没有找到新的、未处理过的节点(至少在当前已知的最短路径成本下)因此没有必要在此基础上继续执行更新操作,直接跳出循环并不会影响其它节点的处理,因为在后续循环迭代中还会继续查找和处理其他未处理过的节点。(这里我现在真的不理解啊 先再往下面看看)
继续第二个内部循环,遍历所有字母,检查是否存在一条更短的路径到达此时的字母节点 j 。即从当前已知的源节点 u 到节点 t 的代价加上从 t 到 j 的代价(dis[u][t] + map[t][j])是否小于源节点 u 到节点 j 的代价(dist[u][j])。上面第一个内循环找的就是这个t,喔~~~ 原来是这样遇到自身节点就直接返回就好,反正也是0
写了自己粗浅的见解,去把模板题做了!!弄清本质!!熟练一下!!!!!!!!!!!!!
#include <iostream>
using namespace std;
const int N = 27;
const int M = 2000005;
const int INF = 0x3fffffff;
bool flag[N];
long long map[N][N], p[N], dist[N][N], n, m;
char s1[M];
char s2[M];
void f(int u){
int i;
for(int j = 1; j <= 26; j++){
// 记录这个字母是否加入最短路径树
flag[j] = false;
//将当前字母u到其他所有字母的初始代价设为矩阵map中的相应值,并记录前驱节点信息再数组p[]中
dist[u][j] = map[u][j];
// if(dist[u][j] == INF)
// //说明这个字母到不了另一个字母
// p[j] = -1;
// else
// p[j] = u;
}
//该字母到自身的代价是0
dist[u][u] = 0;
// 未知最短路径变为已知最短路径
flag[u] = true;
//更新与u相连的所有未加入最短路径树节点的距离值,
//如果通过t作为中间节点到达某个节点j的代价更小,
//则更新dis[u][j]及其前驱节点信息。
for(i = 1; i <= n; i++){
int temp = INF, t = u; // t还是一个接盘侠,每次迭代替换的时候接一下
for(int j = 1; j <= n; j++){
if(flag[j] == false && dist[u][j] < temp){
temp = dist[u][j];
t = j;
}
}
if(t == u)
return;
flag[t] = true;
for(int j = 1; j <= n; j++){
if(flag[j] == false && map[t][j] <INF){
// 上面的循环找的就是这个t
if(dist[u][j] > dist[u][t] + map[t][j]){
dist[u][j] = dist[u][t] + map[t][j];
p[j] = t;
}
}
}
}
}
int main()
{
long long res = 0;
int i, j, x, u, v, w;
n = 26;
//输入两个字符串的长度
cin >> m;
for(i = 1; i <= m; i++){
cin >> s1[i];
}
for(i = 1; i <= m; i++){
cin >> s2[i];
}
//初始化邻接矩阵 矩阵中的每个元素map[i][j]表示将字母表中第i个字母替换为第j个字母的代价
for(i = 1; i <= n; i++){
for(j = 1; j <= n; j++){
map[i][j] = INF;
}
}
for(i = 1; i <= n; i++){
for(j = 1; j <= n; j++){
cin >> map[i][j];
}
}
//以字符状态u为目标状态时,从其他任意字符转到字符u的最小代价
//遍历字母表中26个字母,从其他字母转到当前字母的最小代价
for(i = 1; i <= n; i++){
f(i);
}
for(i = 1; i <= m; i++){
x = dist[s1[i] - 'a' + 1][s2[i]-'a'+1];
res += x;
}
cout << res;
return 0;
}
4.找零2:找零硬币数 - 蓝桥云课 (lanqiao.cn)
这个就是第7个脑子里面的银行找钱,就是换了数字,虽然我写的时候还是直接对代码抄的,我很抱歉,私密马赛,但是写完题解后,我觉得我能够自己写出了。
#include <iostream>
using namespace std;
int main()
{
int a[13] = {1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};
int n;
cin >> n;
int dp[n+1];
for(int i = 0; i <= n; i++){
dp[i] = 10e5;
}
dp[0] = 0;
for(int i = 0; i <= n; i++){
for(int j = 0; j < 13; j++){
if(i - a[j] >= 0){
dp[i] = min(dp[i], dp[i - a[j]] + 1);
}
}
}
cout << dp[n] << endl;
return 0;
}
5. 最少步数【省模拟赛】 - 蓝桥云课 (lanqiao.cn)
一道磨蹭了半天的水题,小姐姐你可以变厉害一点吗。。。
主要是n的迭代和条件的判断那里当时扯了一下
#include <iostream>
using namespace std;
int main()
{
int a[3] = {3, 2, 1};
int n, count = 0;
cin >> n;
for(int i = 0; i < 3; i++){
if(n >= a[i]){
count = count + n/a[i];
n = n - count * a[i];
}
else if(n < a[i] || n != 0){
continue;
}
else
break;
}
cout << count;
return 0;
}