首页 > 其他分享 >Atcoder ABC169

Atcoder ABC169

时间:2022-08-15 15:07:29浏览次数:116  
标签:std Atcoder int cin 中位数 ABC169 vector dp

A

  直接输出\(a × b\)即可

    int a, b;
    std::cin >> a >> b;
    std::cout << a * b << "\n";

B

  将所有的\(N\)个数乘起来看是不是大于\(10 ^ {18}\),很明显会爆\(long\ long\)而用高精度的话也太麻烦了,所以可以考虑用\(\_\_ int128\_ t\),但也有可能会出现最后一个数是\(0\),前面所有数乘起来大于\(10 ^ {18}\)的情况,所以将所有的数先排序,排完序之后再乘起来.

	int n;
	std::cin >> n;
	std::vector<int64_t> a(n);
	for (int i = 0; i < n; i++ ) 
		std::cin >> a[i];
	std::sort(all(a));
	i128 ANS = 1;
	for (int i = 0; i < n; i++ ) {
		if (ANS * a[i] > INF || ANS * a[i] < 0) return std::cout << "-1\n", 0;
		ANS *= a[i];
	}
	std::cout << ANS << "\n";

C

  看起来是一个可以直接乘起来的题,但是会因为\(double\)丢精度,所以我们要把\(double\)先转化成\(int\)再做乘法.

	i64 a;
	std::string b;
	std::cin >> a >> b;
	int B = 0;
	for (auto c : b) {
		if (c == '.') continue;
		B = B * 10 + (c - '0');
	}
	std::cout << a * B / 100 << "\n";

D

  我们要将\(N\)尽可能多的执行操作,而\(N\ =\ p_1 ^ {k1} * p_2 ^ {k_2} * \dots * p_m ^ {k_m}\),一定是让最小的尽可能的用,所以从\(2\)开始枚举,让\(N\)每次除以它的倍数,这样我们就可以做到\(O\left(\sqrt{N}\right)\)的复杂度

    signed main() {
        std::cin.tie(nullptr) -> sync_with_stdio(false);
  	  i64 N;
  	  std::cin >> N;
  	  i64 ans = 0;
  	  for (int i = 2; i * 1ll * i <= N; i++ ) {
  	  	  for (i64 j = i; N % j == 0; j *= i) ans ++, N /= j;
  		  while(N % i == 0) N /= i;
  	  }
  	  std::cout << ans + (N != 1) << "\n";
        return 0 ^ 0;
    }

E

  结论题,我们可以取得最小中位数和最大中位数之间的所有中位数,都可以被取到.所以,我们按照这个写一个程序,先算出最小取到的中位数和最大取到的中位数,然后用分类讨论,等差数列求项数公式求出即可。(偶数的情况公差是0.5,奇数的情况公差是1)。

    signed main() {
        std::cin.tie(nullptr) -> sync_with_stdio(false);
  	  int N;
  	  std::cin >> N;
  	  std::vector<int> A(N), B(N);
  	  rep(i,0,N) {
  		  std::cin >> A[i] >> B[i];
  	  }
  	  std::sort(all(A));
  	  std::sort(all(B));
  	  std::cout << (N & 1 ? B[N / 2] - A[N / 2] + 1 : B[N / 2] + B[N / 2 - 1] - A[N / 2] - A[N / 2 - 1] + 1) << "\n";
        return 0 ^ 0;
    }

F

  我们要求出在\(2 ^ {N-1}\)个集合中\(A_{k_1} + A_{k_2} + \dots + A_{k_m} =s\)的个数,很容易想到要用\(dp\)来求解,我们设状态\(dp\left[i\right]\left[j\right]\)来表示选到第\(i\)个数的时候和为\(j\)的方案有多少个,就相当于转化成了一个背包问题。

    signed main() {
          std::cin.tie(nullptr) -> sync_with_stdio(false);
    	int N, s;
    	std::cin >> N >> s;
    	std::vector<int> a(N + 1);
    	rep(i,1,N + 1) std::cin >> a[i];
    	
    	std::vector<std::vector<Z>> dp(N + 1, std::vector<Z> (s + 1));
    	dp[0][0] = 1;
    	for (int i = 1; i <= N; i++ ) {
    		for (int j = s; j >= 0; j -- ) {
    			dp[i][j] += dp[i - 1][j] * 2; // 当前这个数加不加进来 两种方案
    			if (j + a[i] <= s) dp[i][j + a[i]] += dp[i - 1][j];
    		}
    	}
    	std::cout << dp[N][s] << "\n";
          return 0 ^ 0;
    }

标签:std,Atcoder,int,cin,中位数,ABC169,vector,dp
From: https://www.cnblogs.com/Haven-/p/16588273.html

相关文章

  • AtCoder Beginner Contest 264部分题解(a~d)
    A题题目大意:打印“atcoder"中从第l个到第r个字母参考代码:#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineIOSios_base::sync_with_std......
  • Atcoder Grand Contest 025 E - Walking on a Tree(欧拉回路)
    Atcoder题面传送门打个表发现答案等于每条边被覆盖的次数与\(2\)取min之和,考虑如何构造这个上界。首先考虑树是以\(1\)为中心的菊花图,且任意\(A_i,B_i\ne1\)的......
  • 【杂题乱写】AtCoder dp 26题
    AtCoderdp26题原比赛链接洛谷题单链接A-Frog1题目已然给出了转移方程,设\(dp_i\)为到第\(i\)块石头的最小代价。转移方程:\[dp_i=\min(dp_{i-1}+|h_i-h_{i-1}......
  • freee Programming Contest 2022(AtCoder Beginner Contest 264)A-E
    freeeProgrammingContest2022(AtCoderBeginnerContest264)https://atcoder.jp/contests/abc264FG待补A-"atcoder".substr()输出atcoder第L位和第R位上的字符#in......
  • AtCoder Beginner Contest 264
    比赛链接AtCoderBeginnerContest264E.Blackout2给出很多点(\(n+m\leq2\times10^5\)),有发电站和城市,以及很多边(\(e\leq5\times10^5\)),有\(q\)次删边操作,求每次......
  • AtCoder Beginner Contest 264
    E-Blackout2离线+并查集。注意到只有删边操作,而删边操作其实不是很好维护。由于没有强制在线,所以可以离线一下然后逆序考虑,这样删边就变成了加边,这就用并查集就足以维......