欢迎您访问365答案网,请分享给你的朋友!
生活常识 学习资料

USACO1月2022-2022JanuaryContestSilver银组题解

时间:2023-07-09

你好啊我又又又来了
要准备usaco的铁铁们可以参考这个文章哦!

想刷好USACO——看这篇文章就够了_GeekAlice的博客-CSDN博客我最近是发现了一个很好用的网站https://blog.csdn.net/GeekAlice/article/details/122291933?spm=1001.2014.3001.5501
这次是银组的题解,

如果你想看铜组的话,传送门在这里:

USACO 1月 2021-2022 Contest Bronze 题解_GeekAlice的博客-CSDN博客USACO 2021-22 January Contest Bronze 完整版题解https://blog.csdn.net/GeekAlice/article/details/122798286?spm=1001.2014.3001.5502

:))

话不多说,上题解:


————————————————
版权声明:本文为CSDN博主「GeekAlice」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。

题解:

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class SearchingForSoulmates { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringBuilder out = new StringBuilder(); for (int t = Integer.parseInt(in.readLine()); t > 0; t--) { StringTokenizer tokenizer = new StringTokenizer(in.readLine()); long cow1 = Long.parseLong(tokenizer.nextToken()); long cow2 = Long.parseLong(tokenizer.nextToken()); long answer = Long.MAX_VALUE; for (int removed = 0; cow2 >> removed > 0; removed++) { long here = 0; long prefix = cow2 >> removed; long cow = cow1; while (cow > prefix) { if (cow % 2L == 1L) { cow++; here++; } cow /= 2L; here++; } here += prefix - cow; here += removed; here += Long.bitCount(cow2 & ((1L << removed) - 1L)); answer = Math.min(answer, here); } out.append(answer).append('n'); } System.out.print(out); }}

 

#include using namespace std;int64_t ans = 0;int N; void add_contribution(const vector& h) {vector with_h(N+1);for (int i = 0; i < N; ++i) with_h[h[i]] = i;set present;for (int cur_h = N; cur_h; --cur_h) {auto it = present.insert(with_h[cur_h]).first;if (next(it) != end(present)) ans += *next(it)-*it+1;} }void add_contribution_ll(const vector& h) {vector with_h(N+1);for (int i = 0; i < N; ++i) with_h[h[i]] = i;vector pre(N), nex(N);for (int i = 0; i < N; ++i) {pre[i] = i-1;nex[i] = i+1;}for (int cur_h = 1; cur_h <= N; ++cur_h) {int pos = with_h[cur_h];int p = pre[pos], n = nex[pos];if (n != N) ans += n-pos+1, pre[n] = p;if (p != -1) nex[p] = n;}} void add_contribution_alt(const vector& h) {stack stk;for (int i = N-1; i >= 0; --i) {while (!stk.empty() && h[stk.top()] < h[i]) stk.pop();if (!stk.empty()) ans += stk.top()-i+1;stk.push(i);}}int main() { cin >> N;vector h(N); for (int& i: h) cin >> i;add_contribution(h);reverse(begin(h), end(h));add_contribution(h);cout << ans;}

 

#include using namespace std;struct edge { int cow; int to; bool is_first; edge() {}; edge(int cow, int to, bool is_first) : cow(cow), to(to), is_first(is_first) {};};vector adj[100001];bool visited_cycle[100001]; bool visited[100001]; bool gets_cereal[100001]; int hungry_cows = 0;queue order;int ignore_edge = -1,N,M,first_cereal = -1; void find_cycle(int cur, int prev = -1) { visited_cycle[cur] = true; for (edge next : adj[cur]) { if (visited_cycle[next.to]) { if (first_cereal == -1 && next.to != prev) { if (next.is_first) { first_cereal = next.to; } else { first_cereal = cur; } ignore_edge = next.cow; order.push(next.cow); gets_cereal[next.cow] = true; } } else { find_cycle(next.to, cur); } }} void dfs(int cur) { visited[cur] = true; for (edge next : adj[cur]) { if (!visited[next.to] && next.cow != ignore_edge) { gets_cereal[next.cow] = true; order.push(next.cow); dfs(next.to); } }} int main() { cin >> N >> M; for (int i = 0; i < N; ++i) { int a, b; cin >> a >> b; adj[a].push_back(edge(i+1, b, false)); adj[b].push_back(edge(i+1, a, true)); } for (int i = 1; i <= M; ++i) { first_cereal = -1; ignore_edge = -1; if (!visited[i]) { find_cycle(i); if (first_cereal > 0) { dfs(first_cereal); } else { dfs(i); } } } for (int i = 1; i <= N; ++i) { if (!gets_cereal[i]) { ++hungry_cows; order.push(i); } } cout << hungry_cows << endl; while (!order.empty()) { cout << order.front() << endl; order.pop(); } return 0;}

Copyright © 2016-2020 www.365daan.com All Rights Reserved. 365答案网 版权所有 备案号:

部分内容来自互联网,版权归原作者所有,如有冒犯请联系我们,我们将在三个工作时内妥善处理。