首页 > 其他分享 >AtCoder Beginner Contest 148

AtCoder Beginner Contest 148

时间:2023-03-28 12:45:15浏览次数:55  
标签:AtCoder Beginner int vi 148 dep ans dis mxdep

AtCoder Beginner Contest 148

https://atcoder.jp/contests/abc148
这场比较简单

D - Brick Break

二分 or LIS

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 200005;
int a[N], n, ans = 1, f[N]; //f[i]:以i结尾
map<int, int> mp;
bool suc;
set<int> s[N];

int main () {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == 1)  suc = true;
        s[a[i]].insert (i);
    }
    if (!suc) {
        cout << -1;
        return 0;
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] != i)  break;
        cnt ++;
    }
    if (cnt == n) {
        cout << 0;
        return 0;
    }

    for (int i = 1; i <= n; i++) {
        if (a[i] != 1)  continue;
        int st = i;
        for (int j = 2; j <= n; j++) {
            auto it = s[j].upper_bound (st);
            if (it == s[j].end ()) {
                ans = max (ans, j - 1);
                break;
            }
            st = *it;
            // cout << j  << ' ' << st << endl;
        }
        //cout << endl;
        break;
    }
    
    cout << n - ans;
}

//只需要第一个1

E - Double Factorial

首先如果是奇数就为 \(0\)。因为,奇数没有 \(2\) 的因子(每次转移的距离是 \(2\) ,奇数永远都是奇数)
统计 \(2\) 和 \(5\) 的因子个数,答案为 \(min(cnt2_n,cnt5_n)\)
又 \(2\) 的增长速度比 \(5\) 快,所以只需统计含 \(5\) 的因子个数。
5,25,125,...这样统计即可。
最开始除2是因为,以2为间隔,除去一个数先。

#include <bits/stdc++.h>
#define ll long long

using namespace std;
typedef pair<int, int> pii;
ll n, ans, p = 5;

int main () {
    cin >> n;
    if (n & 1) {
        cout << 0;
        return 0;
    }
    n /= 2;
    while (p <= n) {
        ans += n / p;
        p *= 5;
    }
    cout << ans;
}

//统计2和5的个数
//打表发现2一定必5多(除非不是偶数)
//统计n/2中5,25,125的数量

F - Playing Tag on Tree

偷洛谷题解的图:

注意 \(dep\) 从0开始

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int n, u, v;
vector<int> vi[N];
int dep[N], ans;
int mxdep[N]; //mxdep[i]: i往下能到的最深深度

void dfs (int u, int fa) {
    dep[u] = dep[fa] + 1;
    for (auto v : vi[u]) {
        if (v == fa)    continue;
        dfs (v, u);
        mxdep[u] = max(mxdep[u], mxdep[v] + 1);
    }
}

void dfs2 (int x, int dis) { //dis是x与u的距离
    if (dis < dep[x])   ans = max (ans, dep[x] + mxdep[x] - 1);
    for (auto j : vi[x]) {
        if (dep[j] > dep[x])    continue;
        dfs2 (j, dis + 1);
    }
}

int main () {
    cin >> n >> u >> v;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        vi[a].push_back (b), vi[b].push_back (a);
    }
    dep[0] = -1;
    dfs (v, 0);
    dfs2 (u, 0);
    cout << ans;
}

//v为根
//u所有能到的点的最大深度
//枚举u到根这条路径上的所有满足dis{x,u}<dis{x,v}的点t
//t往下能到达的最远

标签:AtCoder,Beginner,int,vi,148,dep,ans,dis,mxdep
From: https://www.cnblogs.com/CTing/p/17264716.html

相关文章

  • 【题解】Atcoder ABC295 A-G
    A.ProbablyEnglish题目分析:直接每一个单词判一下就好了。代码:点击查看代码#include<bits/stdc++.h>usingnamespacestd;intmain(){ intn;scanf("%d",&n); bo......
  • AtCoder Beginner Contest 248 F(连通性状压dp)
    F连通性状压dp思路看了dls的讲解后才明白一点点。状态\(dp[i][j][k]\)表示到表示到i列,删除了j条边,点i和n-1+i是否联通,对于下一列点,若当前i和n-1+i连通,则多出来的三条......
  • AtCoder Educational DP Contest
    1.A没什么难度,直接算就可以了。点击查看代码#include<bits/stdc++.h>#defineintlonglong#defineYesprintf("Yes\n")#defineNoprintf("No\n")#defineYESpr......
  • leetcode-1480-easy
    RunningSumof1dArrayGivenanarraynums.WedefinearunningsumofanarrayasrunningSum[i]=sum(nums[0]…nums[i]).Returntherunningsumofnums.Ex......
  • AtCoder Grand Contest 019 F Yes or No
    洛谷传送门AtCoder传送门首先容易发现最优策略是回答剩余多的选项。设\(n\)为剩余Yes的数量,\(m\)为剩余No的数量,考虑将\((n,m)\)放到平面上,若\(n>m\)则回......
  • AtCoder Grand Contest 008 F Black Radius
    洛谷传送门AtCoder传送门神题!!!!111考虑如何不重不漏地计数。先考虑全为1的情况,令\(f(u,d)\)为与\(u\)的距离\(\led\)的点集。首先单独算全集,那么对于不是全集......
  • AtCoder Beginner Contest 246
    AtCoderBeginnerContest246D题意求一个\(x\geqn\)使得\(x=a^3+a^2b+ab^2+b^3\)且\(n\leq10^{18}\)思路变形\(x=(a+b)(a^2+b^2)\),那么a、b的范围在1e6从大到小......
  • AtCoder Beginner Contest 141
    AtCoderBeginnerContest141D-PowerfulDiscountTickets贪心+堆#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintN=1e5+5;......
  • [AtCoder] B - Counting Grids
      Thekeyobservationisthatthereisalwaysatmost1cellthatviolatesbothconditions. Proof: ifxviolatesbothconditions,thatmeansallothe......
  • AtCoder Beginner Contest 294
    题解报告基本的一些理解和问题都在注释中A:Filter//水题#include<cstdio>#include<algorithm>#include<cstring>#include<iostream>usingnamespacestd;intm......