每日一题5.28

Fengyj

2024 ICPC EC-Final

榜单地址

3题铁-铜 4题铜-银 6题银-金
A I签到
E G 铜
F H 银
L 金

E题链接

F题链接

L题（稳金题，真有人能做吗）

XinyuLin

[C++] 纯文本查看 复制代码

i题签到
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    int n;
    cin >> n;
    n = n * 2;

    vector<vector<int>> g(n + 1);
    vector<int> du(n + 1);

    for(int i = 1; i <= n - 1; i++) {
        int from, to;
        cin >> from >> to;
        g[from].push_back(to);
        g[to].push_back(from);
        du[from]++, du[to]++;
    }

    if(n == 2) {
        cout << "0 1" << endl;
        return;
    }

    vector<int> ye;
    int rt = -1;
    for(int i = 1; i <= n; i++) {
        if(du[i] == 1) {
            ye.push_back(i);
        }
        if(du[i] > 1 && rt == -1) {
            rt = i;
        }
    }     

    vector<int> ans(n + 1);
    vector<bool> visd(n + 1);
    vector<int> dep(n + 1, 0);

    function<void(int, int)> dfs = [&](int cur, int fath) -> void {
        if(visd[cur]) return;
        visd[cur] = true;
        dep[cur] = dep[fath] + 1;
        for(int to : g[cur]) {
            if(to != fath)
            dfs(to, cur);
        }
    };

    dfs(rt, 0);
    int cnt = 0;

    for(int i = 1; i <= n; i++) {
        if(dep[i] % 2 == 1) {
            ans[i] = 1;
            cnt++;
        }
    }

    int ncnt = 0;
    if(cnt < n / 2) {
        ncnt = n / 2 - cnt;
        for(int to : ye) {
            if(dep[to] % 2 == 0) {
                ans[to] = 1;
                ncnt--;
                if(ncnt == 0) {
                    break;
                }
            }
        }
    }else if(cnt > n / 2) {
        ncnt = cnt - n / 2;
        for(int to : ye) {
            if(dep[to] % 2 == 1) {
                ans[to] = 0;
                ncnt--;
                if(ncnt == 0) {
                    break;
                }
            }
        }
    }
    if(ncnt != 0) {
        cout << -1 << endl;
        return;
    }
    // cerr << rt << endl;
    for(int i = 1; i <= n; i++) {
        cout << ans[i] << "\n "[i != n];
    }

}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }

    return 0;
}

XinyuLin

[C++] 纯文本查看 复制代码

A题签到
#include<bits/stdc++.h>
#include<array>
using namespace std;
using ll = long long;
using info = array<ll, 2>;

struct Tree{
    int l, r, id;
    ll val;
};

struct segTree {
    int n;
    vector<Tree> tree;
    segTree(int size, const vector<array<ll, 3>>& b): n(size), tree(size << 2){
        build(b, 1, size, 1);
    }
    void push_up(int i) {
        if(tree[i << 1].val < tree[i << 1 | 1].val) {
            tree[i].val = tree[i << 1 | 1].val;
            tree[i].id = tree[i << 1 | 1].id;
        }else {
            tree[i].val = tree[i << 1].val;
            tree[i].id = tree[i << 1].id;
        }
    }
    void build(const vector<array<ll, 3>>& b, int l, int r, int x) {
        tree[x].l = l;
        tree[x].r = r;
        if(l == r) {
            tree[x].val = b[l][1];
            tree[x].id = b[l][2];
            return;
        }
        int mid = (l + r) >> 1;
        build(b, l, mid, x << 1);
        build(b, mid + 1, r, x << 1 | 1);
        push_up(x);
    }

    // 重置mu的值
    void update(int mu, int x) {
        if(tree[x].l == tree[x].r) {
            tree[x].val = 0;
            tree[x].id = -1;
            return;
        }

        if(mu <= tree[x << 1].r) {
            update(mu, x << 1);
        }else {
            update(mu, x << 1 | 1);
        }
        push_up(x);
    }

    
    info get_max(int l, int r, int x) {
        if(l <= tree[x].l && tree[x].r <= r) {
            return {tree[x].val, tree[x].id};
        } 

        info ans = {0, -1};
        if(l <= tree[x << 1].r) {
            info a = get_max(l, r, x << 1);
            ans = max(ans, a);
        }

        if(r >= tree[x << 1 | 1].l) {
            info b = get_max(l, r, x << 1 | 1);
            ans = max(ans, b);
        }
        return ans;
    }
};

void solve() {
    int n, total;
    cin >> n;
    total = 3 * n;
    vector<info> a(total + 1);
    vector<array<ll, 3>> b(total + 1);
    
    int cnt = 0;
    for(int i = 1; i <= total; i++) {
        cin >> a[i][0] >> b[i][0];
        a[i][1] = i;

        b[i][1] = a[i][0];
        b[i][2] = i;
    }

    sort(a.begin() + 1, a.end());
    sort(b.begin() + 1, b.end());

    // 更据b排序后建线段树
    segTree Tree(total, b);

    vector<bool> visd(total + 1);
    vector<array<ll, 3>> ans;

    vector<int> id_b(total + 1);
    for(int i = 1; i <= total; i++) {
        id_b[b[i][2]] = i;
    }
    
    int cur = total;
    for(int i = total; i >= 1; i--) {
        if(visd[a[i][1]]) continue;
        ll fi = a[i][0];
        visd[a[i][1]] = true;

        Tree.update(id_b[a[i][1]], 1);

        int find = 2;
        array<ll, 3> temp{a[i][1], 0, 0};

        while(find) {
            ll l = lower_bound(b.begin() + 1, b.end(), array<ll, 3>{fi, 0, 0}) - b.begin();
            if (l == b.size()) {
                // 没有可以在一起的了
                cout << "No" << endl;
                return;
            }    

            info it = Tree.get_max(l, total, 1);
            if(it[1] == -1) {
                cout << "No" << endl;
                return;
            }

            visd[it[1]] = true;
            Tree.update(id_b[it[1]], 1);
            temp[find] = it[1];

            find--;
        }

        if(find != 0) {
            cout << "No" << endl;
            return;
        }
        ans.push_back(temp);

    }
    cout << "Yes" << endl;
    for(auto [x, y, z] : ans) {
        cout << x << ' ' << y << ' ' << z << endl;
    }

}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }

    return 0;
}

Fengyj

i题签到：

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

void solve(){
    int n;
    cin >> n;
    n *= 2;
    int m = n - 1;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m;i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
   
    vector<int> color(n + 1, -1);
    color[1] = 0;
    int zeros = 1;
    auto dfs = [&](auto self, int u, int fa)->void
    {
       
        for(auto v:adj[u]){
            if(v==fa)
                continue;

            color[v] = color[u] ^ 1;
            if(color[v]==0)
                zeros++;
            self(self, v, u);

            
        }

       
    };
    dfs(dfs, 1, -1);
    int ones =n - zeros;
    for (int i = 1; i <= n;i++){
        if(adj[i].size()==1){
            if(ones>zeros&&color[i]==1){
                ones--;
                zeros++;
                color[i] ^= 1;
            }
            else if(ones<zeros&&color[i]==0){
                zeros--;
                ones++;
                color[i] ^= 1;
            }
        }
    }
    for (int i = 1; i <= n;i++){
        cout << color[i] << " \n"[i == n];
    }
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

Fengyj

A题签到题：

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
//1 2
//1 3 5 7
void solve(){

    int n;
    cin>>n;
    vector<array<int,3>>a(3*n);
    for(int i=0;i<3*n;i++){
        int x,y;
        cin>>x>>y;
        a[i]={x,y,i+1};
        
    }
    sort(a.begin(),a.end());
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>>q;
    vector<array<int,3>>ans;
    for(int i=0;i<3*n;i++){
        while(!q.empty()&&a[i][0]>q.top().first){
            if(q.size()<3){
                cout<<"No\n";
                return;
            }
            array<int,3>ar;
            {
             auto [x,y] = q.top(); q.pop();
             ar[0] = y;
            }
            {
                auto [x,y] = q.top(); q.pop();
                ar[1] = y;
            }
            {
             auto [x,y] = q.top(); q.pop();
             ar[2] = y;
              }
              ans.push_back(ar);
        }
        q.push({a[i][1],a[i][2]});
    }
     while(!q.empty()){
            if(q.size()<3){
                cout<<"No\n";
                return;
            }
            array<int,3>ar;
            auto [x1,y1]=q.top();
            q.pop();
            ar[0]=y1;
            auto [x2,y2]=q.top();
            q.pop();
            ar[1]=y2;
            auto [x3,y3]=q.top();
            q.pop();
            ar[2]=y3;
             ans.push_back(ar);
        }
    cout<<"Yes\n";
    for(auto [x,y,z]:ans) cout<<x<<' '<<y<<' '<<z<<endl;
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t=1;
    cin>>t;

    while(t--){
        solve();
    }


    return 0;
}

495684945

[C++] 纯文本查看 复制代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> PII;

void solve() {
	int n;                   
	cin >> n;
	n *=2;
	vector g(n + 1, vector<int>());
	for (int i = 1, u, v; i < n; ++i) {
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int root = 1;
	vector<int> lay(n + 1, 0);     
	vector<int> match(n + 1, 0);    
	auto dfs = [&](auto dfs, int u, int fa) -> void {
		for (int v : g[u]) if (v != fa) {
			lay[v] = lay[u] + 1;
			dfs(dfs, v, u);
		}
		for (int v : g[u]) if (v != fa) {
			if (!match[u] && !match[v]) {
				match[u] = v;
				match[v] = u;
			}
		}
	};
	dfs(dfs, root, 0);
	queue<int> q;
	for (int i = 1; i <= n; ++i)
		if (!match[i] && g[i].size() > 1) q.push(i);
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		if (match[cur] || g[cur].size() == 1) continue; 
		int prev = -1;
		while (true) {
			int nxt = -1;                              
			for (int v : g[cur])
				if (v != prev && match[v] && match[v] != cur) { nxt = v; break; }	
			if (nxt == -1) break;                   
			int w = match[nxt];                        
			match[cur] = nxt; match[nxt] = cur;         
			match[w]   = 0;                              
			if (g[w].size() > 1) {                      
				prev = nxt;
				cur  = w;
			} else break;                               
		}
		if (!match[cur] && g[cur].size() > 1) q.push(cur);
	}
	for (int i = 1; i <= n; ++i)
		if (!match[i] && g[i].size() != 1) {           
			cout << -1 << '\n';
			return;
		}
	vector<int> ans(n + 1, -1);
	int color = 0;                                   
	for (int i = 1; i <= n; ++i) {
		int p = match[i];
		if (p && i < p) {                               
			ans[i] = lay[i] & 1;                         
			ans[p] = ans[i] ^ 1;
			color++;
		}
	}
	int cnt = n/2 - color;          
	for (int i = 1; i <= n; ++i)
		if (!match[i]) {                              
			if (cnt > 0) ans[i] = 0,--cnt; 
			else  ans[i] = 1;
		}
	
	for (int i = 1; i <= n; ++i)
		cout << ans[i] << " \n"[i == n];
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int T;  cin >> T;
	while (T--) solve();
	return 0;
}