• Codeforces Round #835 (Div. 4)


    A:三个数找中间大

    1. void solve() {
    2. vector<int> a(3);
    3. rep(i, 0, 3) cin >> a[i];
    4. sort(all(a));
    5. cout << a[1] << endl;
    6. }

    B:问你字符串中最大的字母对应编号

    1. void solve() {
    2. int n; cin >> n;
    3. string s; cin >> s;
    4. char c = 'a';
    5. for (auto x : s) c = max(c, x);
    6. cout << c - 'a' + 1 << endl;
    7. }

    C:问你每个数与最大值的差, 最大值则与第二大的特判

    1. void solve() {
    2. int n; cin >> n;
    3. int mx1 = -1e8, mx2 = -1e8;
    4. for (int i = 1; i <= n; i ++ ) {
    5. cin >> a[i];
    6. if(a[i] > mx1) mx2 = mx1, mx1 = a[i];
    7. else if(a[i] > mx2) mx2 = a[i];
    8. }
    9. for (int i = 1; i <= n; i ++ ) {
    10. if(a[i] != mx1) cout << a[i] - mx1 << ' ';
    11. else cout << mx1 - mx2 << ' ';
    12. }
    13. cout << endl;
    14. }

    D:问你当前这个数组是不是有谷

    1. void solve() {
    2. int n; cin >> n;
    3. repn(i, 1, n) cin >> a[i];
    4. bool fg = false;
    5. for (int i = 2; i <= n; i ++ ) {
    6. if(a[i] == a[i - 1]) continue;
    7. if(fg) {
    8. if(a[i] < a[i - 1]) {cout << "NO" << endl; return;}
    9. }
    10. if(a[i] > a[i - 1]) fg = true;
    11. }
    12. cout << "YES" << endl;
    13. }

    E:给你一个01串,你最多可以修改一个位置,将0->1, 1->0,问你最大的逆序对数量。

    思路:先处理出原始的逆序对数量。然后分分别枚举每一个位置

    1->0:ans减去后缀0的数量,加上前缀1的数量

    0->1:ans加上后缀0的数量,减去前缀1的数量。 

     

    1. void solve() {
    2. int n; cin >> n;
    3. for (int i = 0; i <= n + 20; i ++ ) pre1[i] = pre0[i] = end0[i] = end1[i] = 0;
    4. map<int, int> mp;
    5. ll ans = 0;
    6. for (int i = 1; i <= n; i ++ ) {
    7. cin >> a[i];
    8. mp[a[i]] ++;
    9. if(a[i] == 0) ans += mp[1];
    10. }
    11. if(a[1] == 0) pre0[1] = 1;
    12. else pre1[1] = 1;
    13. for (int i = 2; i <= n; i ++ ) {
    14. pre0[i] = pre0[i - 1] + (a[i] == 0);
    15. pre1[i] = pre1[i - 1] + (a[i] == 1);
    16. }
    17. if(a[n] == 0) end0[n] = 1;
    18. else end1[n] = 1;
    19. for (int i = n - 1; i >= 0; i -- ) {
    20. end0[i] = end0[i + 1] + (a[i] == 0);
    21. end1[i] = end1[i + 1] + (a[i] == 1);
    22. }
    23. ll tmp = ans;
    24. for (int i = 1; i <= n; i ++ ) {
    25. if(a[i] == 1) {
    26. ans = max(ans, tmp - end0[i + 1] + pre1[i - 1]);
    27. }
    28. else ans = max(ans, tmp + end0[i + 1] - pre1[i]);
    29. //cout << ans << endl;
    30. }
    31. cout << ans << endl;
    32. }

    F:你有n个工作,每个工作对应ai的收益。你还有一个c和一个d,d是deadline。现在,完成了一个工作会有一个约束,即k天内无法再次做这个工作。现在问你d天内,我们是否可以最大化k,使得收益达到c。

    思路:很明显的二分答案。我们可以二分这个答案k。贪心的考虑,我们每次肯定都是先做收益ai最大的工作。所以排个序,取模随便搞一搞就行了。注意一下define int long long

    1. void solve() {
    2. cin >> n >> c >> d;
    3. for (int i = 1;i <= n; i++ ) cin >> a[i];
    4. int sum = 0, mx = 0;
    5. for (int i = 1; i <= n; i++ ) sum += a[i], mx = max(mx, a[i]);
    6. if(mx * d < c) {cout << "Impossible" << endl; return;}
    7. sort(a + 1, a + n + 1);
    8. int l = 0, r = INF;
    9. auto check = [&](int mid) {
    10. int res = 0;
    11. for (int i = n; i >= max(n - mid, 1ll); i --) res += a[i];
    12. int sum = 0;
    13. for (int i = n, j = d % (mid + 1); j >= 1 && i >= max(n - mid, 1ll); i --, j -- ) sum += a[i];
    14. return d / (mid + 1) * res + sum >= c;
    15. };
    16. while(l < r) {
    17. int mid = l + r + 1 >> 1;
    18. if(check(mid)) l = mid;
    19. else r = mid - 1;
    20. }
    21. if(r < INF) cout << r << endl;
    22. else cout << "Infinity" << endl;
    23. }

     G:有一棵树,每条树边有一个权值w,问你从a走到b,是否能使得边的权值异或是0,但是中间你可以随便跳一次。也是在路上随便位移到另外一个点。

    思路:从a开始不到b跑一边前缀异或值,放入set或者map。然后从b再出发随便跑一遍,记录异或值。如果异或值已经出现了,说明我们直接瞬移到这个点然后走回去就是0了。

    1. vectorint, 2>> e[N];
    2. int ans;
    3. bool fg;
    4. map<int, int> mp;
    5. void solve() {
    6. cin >> n >> a >> b;
    7. mp.clear();
    8. for (int i = 0; i <= n + 10; i ++ ) e[i].clear();
    9. for (int i = 1; i < n; i ++ ) {
    10. int a, b, c; cin >> a >> b >> c;
    11. e[a].pb({b, c});
    12. e[b].pb({a, c});
    13. }
    14. auto dfs = [&](auto&& self, int u, int fa, int cur) -> void {
    15. mp[cur] = 1;
    16. for (auto [to, v]: e[u]) {
    17. if(to == fa) continue;
    18. if(to == b) continue;
    19. self(self, to, u, cur ^ v);
    20. }
    21. };
    22. auto dfs2 = [&](auto&& self, int u, int fa, int cur) -> void {
    23. for (auto [to, v] : e[u]) {
    24. if(to == fa) continue;
    25. self(self, to, u, cur ^ v);
    26. if(fg) return ;
    27. if(mp[cur ^ v]) {
    28. fg = true;
    29. cout << "YES" << endl;
    30. }
    31. }
    32. };
    33. dfs(dfs, a, 0, 0);
    34. fg = false;
    35. dfs2(dfs2, b, 0, 0);
    36. if(!fg) {cout << "NO" << endl; return;};
    37. }

  • 相关阅读:
    JAVA的异常处理
    BSP Day50
    一文带你读懂 Hbase 的架构组成
    AUTOSAR实战篇:手把手带你搞定Watchdog协议栈
    HarmonyOS应用开发-常用组件与布局
    java-net-php-python-springboot区校企大型仪器智慧共享平台计算机毕业设计程序
    6个团队建设管理游戏
    CsvHelper:一个轻便高性能的Csv文件读写操作开源库!
    查找和排序算法
    nginx(五十三)nginx中使用的PCRE正则
  • 原文地址:https://blog.csdn.net/m0_61837058/article/details/128003979