刷题刷题刷题

P1123 取数游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

从1,1开始dfs，若行数x>n则立马刷新最大值退出搜索，若y>m则进入下一行从第一列开始搜索即x+=1,y=1，对当前的搜索点x,y的八个方向进行+1,因为不能相邻

AC:

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
inline int read()
{int k = 0, f = 1; char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){k = k * 10 + ch - '0';ch = getchar();}return k * f;
}
int n, m, t, ans;
int a[110][110];
int u[110][110];
void dfs(int x, int y, int z)
{int tx, ty;if (x > n){ans = max(ans, z);return;}tx = x, ty = y + 1;if (ty > m){tx = x + 1;ty = 1;}if (!u[x - 1][y - 1] && !u[x - 1][y] && !u[x - 1][y + 1] && !u[x][y - 1] && !u[x][y + 1] && !u[x + 1][y - 1] && !u[x + 1][y] && !u[x + 1][y + 1]){u[x][y] = 1;dfs(tx, ty, z + a[x][y]);u[x][y] = 0;}dfs(tx, ty, z);
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> t;while (t--){ans = 0;memset(a, 0, sizeof(a));memset(u, 0, sizeof(u));cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++)cin >> a[i][j];}dfs(1, 1, 0);cout << ans;}return 0;
}

P1294 高手去散步 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

利用vector进行建边，从第一个点开始搜索，每搜完一个点要进行回溯（因为要分别以每个点作为出发点进行搜索得到最大的 长度），从每个出发点开始进行递归搜索得到最大长度（也要回溯）

AC：

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
inline int read()
{int k = 0, f = 1; char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){k = k * 10 + ch - '0';ch = getchar();}return k * f;
}
int n, m;
vector<int>s[10010], l[10010];
int vis[10010];
int ans = 0;
void dfs(int x, int y)
{ans = max(ans, y);for (int i = 0; i < s[x].size(); i++){if (!vis[s[x][i]]){vis[s[x][i]] = 1;dfs(s[x][i], y + l[x][i]);vis[s[x][i]] = 0;}}
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;for (int i = 1; i <= m; i++){int a, b, c;cin >> a >> b >> c;s[a].push_back(b);s[b].push_back(a);l[a].push_back(c);l[b].push_back(c);}for (int i = 1; i <= n; i++){vis[i] = 1;dfs(i, 0);vis[i] = 0;}cout << ans;return 0;
}

P6140 [USACO07NOV] Best Cow Line S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

贪心题，将逆序的字符串和正序的从头开始对比，谁小就输出谁就行了（一定要记录输出的次数，每输出80次换一下行，我就是忘记看了导致一直卡样例）

AC:

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
inline int read()
{int k = 0, f = 1; char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){k = k * 10 + ch - '0';ch = getchar();}return k * f;
}
int n, m;
char s[500005];
char q[10010];
void solve()
{int l = 1, r = n;int cnt = 1;while (l <= r){int flag = 0;for (int i = 0; l + i <= n; i++){if (s[l + i] < s[r - i]){flag = 1;break;}else if (s[l + i] > s[r - i]){flag = 0;break;}}if (flag){q[cnt] = s[l];l++;cnt++;}else{q[cnt] = s[r];r--;cnt++;}}for (int i = 1; i <= cnt; i++){cout << q[i];if (i % 80 == 0){cout << endl;}}
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n;for (int i = 1; i <=  n; i++){cin >> s[i];}solve();return 0;
}

P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

贪心一道

思路：
我们可以把它看成一颗二叉树，就是每次把最小的两颗字数加起来一直循环直到长度<=1（直到没有两棵 最小子树）

AC：

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
using namespace std;
typedef long long ll;
inline int read()
{int k = 0, f = 1; char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){k = k * 10 + ch - '0';ch = getchar();}return k * f;
}
priority_queue<int, vector<int>, greater<int>> pq;
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;while (n--){int l;cin >> l;pq.push(l);}int ans = 0;if (pq.size() == 1){ans += pq.top();}while (pq.size() > 1){int a = pq.top();pq.pop();int b = pq.top();pq.pop();ans += (a + b);pq.push(a + b);}cout << ans;return 0;
}