一、前言
先把代码丢上来，后续再补上思路
二、题目总览
三、具体题目
3.1 问题 A: 成绩排序1
参考代码
简单排序
#include <bits/stdc++.h>
using i64 = long long;int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;std::cin >> t;while(t--) {int n;std::cin >> n;std::vector<int> v(n);for(auto &vi:v) std::cin >> vi;std::sort(v.begin(),v.end(),[&](const int &num1,const int &num2) {return num1>num2;});for(int i = 0;i<n;i++) std::cout << v[i] << " \n"[i==n-1];}return 0;
}
3.2 问题 B: 数字和排序
参考代码
简单排序
#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int n = 1;while(std::cin >> n) {if(n==0) break;std::vector<pii> v(n);for(int i = 0;i<n;i++) {int num;std::cin >> num;int tmp = num,sum = 0;while(tmp!=0) {sum+=tmp%10;tmp/=10;}v.emplace_back(sum,num);}std::sort(v.begin(),v.end(),[&](const pii& p1,const pii& p2) {if(p1.first!=p2.first) return p1.first>p2.first;return p1.second > p2.second;});for(int i = 0;i<n;i++) {std::cout << v[i].second << " \n"[i==n-1];}}return 0;
}
3.3 问题 C: 帆帆的挂件
参考代码
简单模拟
#include <bits/stdc++.h>
using i64 = long long;int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int n,x_0;std::cin >> n >> x_0;std::vector<int> a(n),b(n);for(auto &ai:a) std::cin >> ai;for(auto &bi:b) std::cin >> bi;int ans = 0;for(int i = 0;i<n;i++) {if(x_0>=a[i]) {x_0+=b[i];++ans;}}std::cout << ans << '\n';return 0;
}
3.4 问题 D: 文件名排序
参考代码
stringstream很好处理这种读入情况
#include <bits/stdc++.h>
using i64 = long long;
using pss = std::pair<std::string,std::string>;int main() {std::cin.tie(nullptr)->sync_with_stdio(false);std::string line;std::vector<pss> v;while(std::getline(std::cin,line)) {std::stringstream ss(line);std::string tmp1,tmp2;while(ss >> tmp1 >> tmp2) v.emplace_back(tmp2,tmp1);}std::sort(v.begin(),v.end());for(const auto &vi:v) {std::cout << vi.second << ' ' << vi.first << '\n';}return 0;
}
3.5 问题 E: 火星数排序
参考代码
可以用哈希表映射过去，写题的时候脑子犯昏，写了好多if
#include <bits/stdc++.h>
using namespace std;
struct number{int en;int mn;
}a[1000];int earth(int n){int temp=n;int total = 0;int sum[20];int index = 0;while(temp != 0){if(temp%10==0){sum[index] = 0;}else if(temp%10==8){sum[index] = 1;}else if(temp%10==1){sum[index] = 2;}else if(temp%10==5){sum[index] = 3;}else if(temp%10==2){sum[index] = 4;}else if(temp%10==3){sum[index] = 5;}else if(temp%10==9){sum[index] = 6;}else if(temp%10==4){sum[index] = 7;}else if(temp%10==7){sum[index] = 8;}else if(temp%10==6){sum[index] = 9;}index++;temp /= 10;}for(int i = index-1;i>=0;i--) total = total*10+sum[i];return total;
}bool cmp1(number a,number b){return a.en<b.en;
}
int main(){cin.tie(nullptr)->sync_with_stdio(false);int Case;cin>>Case;for(int i=0;i<Case;i++){int j=0;int n;cin >> n;for(int j = 0;j<n;j++) cin >> a[j].mn;for(int j = 0;j<n;j++) a[j].en = earth(a[j].mn);sort(a,a+n,cmp1);for(int j = 0;j<n;j++){if(j==0) cout << a[j].mn;else cout << ' ' << a[j].mn;}cout << '\n';}return 0;
}3.6 问题 F: 帆帆的数位计算
参考代码
写个循环模拟就行，我当时想复杂了
#include <bits/stdc++.h>
using i64 = long long;void dfs(std::string num,int step) {if(num.size()==1) {std::cout << step << '\n';return;}int sum = 0;for(const auto &c:num) {sum+=c^48;}dfs(std::to_string(sum),step+1);
}
int main() {std::cin.tie(nullptr)->sync_with_stdio(false);std::string num;std::cin >> num;dfs(num,0);return 0;
}
3.7 问题 G: 帆帆的数列
参考代码
前缀和+贪心
#include <bits/stdc++.h>
using i64 = long long;int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;std::cin >> t;while(t--) {int n,m;std::cin >> n;std::vector<int> a(n+1,0),preA(n+1,0);for(int i = 1;i<=n;i++) {std::cin >> a[i];preA[i] = preA[i-1]+a[i];}std::cin >> m;std::vector<int> b(m+1,0),preB(m+1,0);for(int i = 1;i<=m;i++) {std::cin >> b[i];preB[i] = preB[i-1]+b[i];}int ans = 0;for(int i = 0;i<=n;i++) {for(int j = 0;j<=m;j++) {ans = std::max(ans,preA[i]+preB[j]);}}std::cout << ans << '\n';}return 0;
}
3.8 问题 H: 帆帆的糖
参考代码
一开始当成dfs写了，没看到范围，真是蠢了。可以直接二分枚举答案，不能直接暴力，会TLE
#include <bits/stdc++.h>
using i64 = long long;int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int n,k;std::cin >> n >> k;int ans = 0;int low = 1,high = n;while(low<high) {int mid = (low+high)>>1;if(1LL*(1+mid)*mid/2-(n-mid)>=k) {high = mid;}else {low = mid+1;}}std::cout << n-low << '\n';return 0;
}
3.9 问题 I: Determine the Photo Position
参考代码
前缀和
#include <bits/stdc++.h>
using i64 = long long;int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int n,m;std::cin >> n >> m;std::vector<std::vector<char>> g(n+5,std::vector<char>(n+5));std::vector<std::vector<int>> pre(n+5,std::vector<int>(n+5,0));for(int i = 1;i<=n;i++) {for(int j = 1;j<=n;j++) {std::cin >> g[i][j];pre[i][j]=pre[i][j-1]+(g[i][j]^48);}}std::string t;std::cin >> t;int ans = 0;for(int i = 1;i<=n;i++) {for(int j = m;j<=n;j++) {if(pre[i][j]-pre[i][j-m]==0) {++ans;}}}std::cout << ans << '\n';return 0;
}
3.10 问题 J: Ball Dropping
参考代码
初中数学计算
#include <bits/stdc++.h>
using i64 = long long;int main() {std::cin.tie(nullptr)->sync_with_stdio(false);double r,a,b,h;std::cin >> r >> a >> b >> h;if(2*r<=b) {std::cout << "Drop\n";return 0;}double h0 = std::sqrt(h*h+((a-b)/2)*((a-b)/2));double sin = ((a-b)/2)/h0;double cos = h/h0;double tan = ((a-b)/2)/h;double x1 = r*sin,x2 = (r*cos-b/2)/tan;std::cout << "Stuck\n";std::cout << std::fixed << std::setprecision(10) << x1+x2 << '\n';return 0;
}
3.11 问题 K: Cut the Tree
参考代码
套了别人的两个模板，链式前向星和带权的线段树+dfs找树上LIS，注意数组不能开太大也不能开太小
#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = N,INF = 0x3f3f3f3f;//链式前向星
int head[N];
int val[N];
int n;
int ans;struct edge{int next, to, w;
}e[N << 1];
int cnt;void init(){for(int i = 0; i <= n; i++)head[i] = -1;cnt = 0;
}void add(int u, int v, int w = 0){e[cnt].w = w;e[cnt].to = v;e[cnt].next = head[u];head[u] = cnt++;
}//带权线段树+dfs找LIS
int tot;
struct Tree{int l, r;int lis, lds;
}tree[N * 100];
int rt[N];
int sz[N];
int root, maxPart;
int res;
int vis[N];
void getrt(int S, int u, int f){sz[u] = 1;int maxx = 0;for(int i = head[u]; ~i; i = e[i].next){int v = e[i].to;if(vis[v] || f == v)continue;getrt(S, v, u);sz[u] += sz[v];maxx = std::max(maxx, sz[v]);}maxx = std::max(maxx, S - sz[u]);if(maxx < maxPart){maxPart = maxx;root = u;}
}
int build(){tot++;tree[tot].l = tree[tot].r = tree[tot].lis = tree[tot].lds = 0;return tot;
}
void update(int &p, int l, int r, int pos, int vlis, int vlds){if(p == 0)p = build();tree[p].lis = std::max(tree[p].lis, vlis);tree[p].lds = std::max(tree[p].lds, vlds);if(l == r)return ;int m = (l + r) >> 1;if(pos <= m)update(tree[p].l, l, m, pos, vlis, vlds);elseupdate(tree[p].r, m+1, r, pos, vlis, vlds);
}
int merge(int p, int q){if(!p || !q)return p + q;tree[p].lis = std::max(tree[p].lis, tree[q].lis);tree[p].lds = std::max(tree[p].lds, tree[q].lds);// 最大上升子序列长度res = std::max(res, std::max(tree[tree[p].l].lis + tree[tree[q].r].lds,tree[tree[p].r].lds + tree[tree[q].l].lis));tree[p].l = merge(tree[p].l, tree[q].l);tree[p].r = merge(tree[p].r, tree[q].r);return p;
}
pii query(int p, int l, int r, int L, int R){ // L R 询问if(!p || l > r)return {0, 0};if(L <= l && r <= R)return {tree[p].lis, tree[p].lds};int m = (l + r) >> 1;pii ret = {-INF, -INF};pii tr, tl;if(L <= m)tl = query(tree[p].l, l, m, L, R);if(m < R)tr = query(tree[p].r, m+1, r, L, R);ret.first = std::max(tl.first, tr.first);ret.second = std::max(tl.second, tr.second);return ret;
}
void dfs(int u, int f){rt[u] = 0;for(int i = head[u]; ~i; i = e[i].next){int v = e[i].to;if(v == f)continue;dfs(v, u);}int nlis = 0, nlds = 0;for(int i = head[u]; ~i; i = e[i].next){int v = e[i].to;if(v == f)continue;int lis = query(rt[v], 1, n, 1, val[u]-1).first;int lds = query(rt[v], 1, n, val[u]+1, n).second;rt[u] = merge(rt[u], rt[v]);res = std::max(res, lis + 1 + nlds);res = std::max(res, nlis + 1 + lds);nlis = std::max(nlis, lis);nlds = std::max(nlds, lds);}update(rt[u], 1, n, val[u], nlis + 1, nlds + 1);
}
void calc(int S, int u){maxPart = S;getrt(S, u, 0);vis[root] = 1;int maxx = 0, pos = -1;for(int i = head[root]; ~i; i = e[i].next){int v = e[i].to;res = 0;dfs(v, root);if(res > maxx){maxx = res;pos = v;}}ans = std::min(ans, maxx);if(pos == -1 || vis[pos])return ;calc(sz[pos], pos);
}
void solve(){std::cin >> n;init();for(int i = 1; i < n; i++){int u, v;std::cin >> u >> v;add(u, v);add(v, u);}for(int i = 1; i <= n; i++)std::cin >> val[i];ans = INF;calc(n, 1);std::cout << ans << '\n';
}int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int T;// std::cin >> T;T = 1;while(T--){solve();}return 0;
}