ZISUOJ 2024算法基础公选课练习二

一、前言

先把代码丢上来，后续再补上思路

二、题目总览

三、具体题目

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);
	else
		update(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;
}