CodeForce 774 div2 A-C,E题解_综合

E. Power Board

思路
- 重复的数是从哪里来的？比如4 = $2^2$ , 那么 $4^2$ 就会跟 $2^2）^2$ = $2^4$ 重复,所以可以看出，所有的重复，都是因为底数可以划分为某个数的k次幂造成的。所以我们以不可再分的底数作为分类标准，预处理出所有的最小底数的k次幂（如果某一行的m次幂写成 $i^t)^m$ 的形式，则k=t*m）（由于 $2^{20} >1e6$ ,所以t最大到20）有多少个数。这样子我们在真正进行操作的时候，一次可以处理完所有具有相同最小底数的行
经验教训
- 无
AC代码

#include <iostream>
#include <string>
#include <iomanip>
#include <vector>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstring>
#include <list>
#include <numeric>
#include <bitset>#define int long long
using namespace std;
typedef long long ll;const int maxn = 2e7 + 5;
int ans[25]; // 存放某个最小数的i次幂对应的不重复数字数量
int vis[1000005];
int power[maxn] = {
    0};
void solve() {
    int n, m;cin >> n >> m;
// map<int, int> power;int ret = 1;int tot = 0;for (int i = 1; i <= 20; ++i) {
    for (int j = 1; j <= m; ++j) {
    if (!power[i * j]) tot++;power[i * j] = 1;}ans[i] = tot;}for (int i = 2, j; i <= n; ++i) {
     // 最小底数if (vis[i]) continue;for (j = 1; (int) pow(i, j) <= n; ++j) {
     // 最小底数的j次幂vis[(int) pow(i, j)] = 1;}ret += ans[j - 1];}cout << ret << '\n';
}signed main() {
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);solve();}

C. Factorials and Powers of Two

思路
- 如果完全由2^{n组成，那么直接枚举二进制即可，但是多了阶乘。可以很容易知道15！已经超过10}12，所以阶乘个数不可以能超过15个，可以枚举阶乘。
经验教训
- 一个数以二进制形式表示，其中1的个数就是分解为2^i(i=0,1,2…n)的个数
- bitset x(i),表示x为用num位的二进制表示i，x.count（）表示该二进制串中1的个数
- 二进制枚举是一种很有用的技巧，比如该题中要枚举阶乘是否存在，就用了二进制，0表示该位对应的阶乘不选择，1表示该位对应的阶乘选择
- 1<<n === 2^n
AC代码

#include <iostream>
#include <string>
#include <iomanip>
#include <vector>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstring>
#include <list>
#include <numeric>
#include <bitset>#define int long long
using namespace std;
typedef long long ll;const int maxn = 2e5+5;
int row_z[maxn];
int col_z[maxn];
int a[maxn];
int fac[16];
char martix[405][405];
int dp[405][405];
void set_fac(){
    fac[0] = 0;fac[1] = 1;for (int i = 2; i <= 16; ++i) {
    fac[i] = fac[i-1]*i;}
// for (int i = 0; i < 16; ++i) {
    
// cout<<fac[i]<<" ";
// }
}void solve() {
    set_fac();int n;cin>>n;bitset<40> init(n);int ans = (int) init.count();for (int i = 0; i <= (1<<15) ; ++i) {
    int nn = n;bitset<16> facn(i);for (int j = 0; j < 16; ++j) {
    if (facn[j]==1) nn-=fac[j];}if (nn>=0) {
    bitset<40> binn(nn);ans = min(ans,(int)(binn.count()+facn.count()));}}cout<<ans<<'\n';
}signed main() {
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int t;cin >> t;for (int i = 0; i < t; ++i) {
    solve();}}

B. Quality vs Quantity

思路
- 贪心即可，排序完，最大的一个染红色，最小的两个染蓝色，如果不满足就每次红蓝各自多染一个，直到没有可以染的（no），或者满足（yes）
经验教训
- 无
AC代码

#include <iostream>
#include <string>
#include <iomanip>
#include <vector>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstring>
#include <list>
#include <numeric>
#include <bitset>#define int long long
using namespace std;
typedef long long ll;const int maxn = 2e5+5;
int row_z[maxn];
int col_z[maxn];
int a[maxn];char martix[405][405];
int dp[405][405];
void solve() {
    int n;cin>>n;for (int i = 0; i < n; ++i) {
    cin>>a[i];}sort(a,a+n);int suma = a[n-1];int sumb = a[0]+a[1];int left = 2,right = n-2;while (left<right && suma<=sumb){
    suma+=a[right];sumb+=a[left];left++;right--;}if (suma>sumb) cout<<"yes"<<'\n';else cout<<"no"<<'\n';signed main() {
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int t;cin >> t;for (int i = 0; i < t; ++i) {
    solve();}}

A. Square Counting

思路
- n个小于n的数不可能凑出n^{2,所以有s/（n}2）个n^2
经验教训
- 无
AC代码

#include <iostream>
#include <string>
#include <iomanip>
#include <vector>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstring>
#include <list>
#include <numeric>
#include <bitset>#define int long long
using namespace std;
typedef long long ll;const int maxn = 2e5+5;
int row_z[maxn];
int col_z[maxn];char martix[405][405];
int dp[405][405];
void solve() {
    int n,s;cin>>n>>s;int xx = n*n;cout<<s/xx<<'\n';}signed main() {
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int t;cin >> t;for (int i = 0; i < t; ++i) {
    solve();}}