CodeForce 774 div2 A-C,E题解

news/2024/11/8 3:34:40/

E. Power Board

  • 思路
    • 重复的数是从哪里来的?比如4 = 2 2 2^2 22, 那么 4 2 4^2 42 就会跟 ( 2 2 ) 2 (2^2)^2 (222 = 2 4 2^4 24 重复,所以可以看出,所有的重复,都是因为底数可以划分为某个数的k次幂造成的。所以我们以不可再分的底数作为分类标准,预处理出所有的最小底数的k次幂(如果某一行的m次幂写成 ( i t ) m (i^t)^m (it)m的形式,则k=t*m)(由于 2 20 > 1 e 6 2^{20} >1e6 220>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

  • 思路
    • 如果完全由2n组成,那么直接枚举二进制即可,但是多了阶乘。可以很容易知道15!已经超过1012,所以阶乘个数不可以能超过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的数不可能凑出n2,所以有s/(n2)个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();}}

http://www.ppmy.cn/news/357488.html

相关文章

【平头哥蓝牙Mesh网关开发套件试用体验】PHY6220 蓝牙键盘

作者&#xff1a;robe PHY6220 开发板烧录此程序后会变成蓝牙键盘。 此程序是demo程序&#xff0c;跑通此工程的意义在于熟悉PHY6220开发流程&#xff0c;为后续项目开发做准备。 PHY6220 蓝牙键盘工程方法步骤&#xff1a; 打开剑池CDK开发环境创建工作目录创建工程&#xff…

Error: L6200E: Symbol xxx multiply defined (by adc_1.o and adc.o)的解决办法

问题&#xff1a; Keil MDK-ARM V5的工程&#xff0c;使用HAL库搭建的。 HAL库从STM32Cube FW_F1 V1.6.1升级到STM32Cube FW_F1 V1.7.0&#xff0c; 重新编译工程后提示有102条错误&#xff0c; 而原来的工程是能正确运行的。解决办法&#xff1a; 错误信息提示如下&#xff1…

Flutter网络请求框架Dio源码分析以及封装(二)--Cookie管理分析

Flutter网络请求框架Dio源码分析以及封装--Cookie管理分析 前言问题如何使用CookieJarCookieManagerPersistCookieJar总结 前言 上一篇文章我们简单分析了一下Dio发出请求时的大致工作流程&#xff0c;这个只是Dio最基本的功能&#xff0c;而且我们还没有分析走到httpClientA…

DI卡件/3503E/TRICONEX

本特利bently3300XL NSv振动和位移前置器常用型号&#xff1a; 330980-50-00 330980-50-CN 330980-51-00 330980-51-CN 330980-70-00 330980-70-CN 330980-71-00 330980-71-CN 常用匹配传感器振动探头和延伸电缆型号如下&#xff1a; 330903-00-03-10-02-00 330903-…

Error: L6220E: Execution region ER_IROM5 size (31436 bytes) exceeds limit (31424 bytes).

kei4.73编译过程中提示错误&#xff1a; ..\..\..\scatterfiles\scatterfile_common.sct: Error: L6220E: Execution region ER_IROM5 size (31436 bytes) exceeds limit (31424 bytes). Region contains 13 bytes of padding and 1260 bytes of veneers (total 1273 bytes of…

keil 下连接错误 Error: L6220E

在keil4下编译程序&#xff0c;提示以下错误&#xff1a; linking... .\rvmdk\xxx.axf: Error: L6220E: Load region LR_IROM size (94576 bytes) exceeds limit (92160 bytes). .\rvmdk\xxx.axf: Error: L6220E: Execution region ER_IROM size (94232 bytes) exceeds limit …

关于 keil 报错:Error: L6220E: Load region LR_IROM1 size.....等解决方式

关于 keil 报错&#xff1a;Error: L6220E: Load region LR_IROM1 size.....等解决方式 简单叙述解决方式最后效果后来测试 后续改正 简单叙述 这两天用keil调试代码&#xff0c;可能是打印printf用得多了&#xff0c;结果报了一个错误。便查了查&#xff0c;调试了一下。 报错…

在DELL笔记本上E6220安装fedora16(1)——分区的陷阱

机器型号&#xff1a;DELL E6220 4GRAM 300GHD 机器是公司的&#xff0c;领来的时候&#xff0c;装的是windows7&#xff0c;没有光驱&#xff0c;因为公司的服务器都是centos系列&#xff0c;所以我选择了fedora16的64位版本进行安装。 噩梦开始&#xff1a; 用easybcd进行硬…