A. 日期统计
题目内容
小蓝现在有一个长度为 100 的数组，数组中的每个元素的值都在 0 到 9 的范围之内。
数组中的元素从左至右如下所示：
5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7
0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1
0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3
现在他想要从这个数组中寻找一些满足以下条件的子序列：
- 子序列的长度为 8；
- 这个子序列可以按照下标顺序组成一个 yyyymmdd 格式的日期，并且
要求这个日期是 2023 年中的某一天的日期，例如 20230902，20231223。
yyyy 表示年份，mm 表示月份，dd 表示天数，当月份或者天数的长度只有一位时需要一个前导零补充。
请你帮小蓝计算下按上述条件一共能找到多少个不同的 2023 年的日期。
对于相同的日期你只需要统计一次即可。
本题的结果为一个整数，在提交答案时只输出这个整数，输出多余的内容将无法得分。
思路
八重循环枚举日期+set去重即可
\(Tips:\) 前4重特判2023,否则程序会跑的很慢
代码
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n=100;
int num[N];
set<string>s;
bool check(string all)
{
int m=stoi(all.substr(0,2));
int d=stoi(all.substr(2,2));
int mon[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
if(m>=1&&m<=12)
{
if(d>=1&&d<=mon[m])
return true;
}
return false;
}
int main()
{
for(int i=0;i<n;i++)cin>>num[i];
for(int a=0;a<n;a++)
{
if(num[a]!=2)continue;
for(int b=a+1;b<n;b++)
{
if(num[b]!=0)continue;
for(int c=b+1;c<n;c++)
{
if(num[c]!=2)continue;
for(int d=c+1;d<n;d++)
{
if(num[d]!=3)continue;
for(int e=d+1;e<n;e++)
{
for(int f=e+1;f<n;f++)
{
for(int g=f+1;g<n;g++)
{
for(int h=g+1;h<n;h++)
{
string n1=to_string(num[e]);
string n2=to_string(num[f]);
string n3=to_string(num[g]);
string n4=to_string(num[h]);
string all=n1+n2+n3+n4;
if(check(all))s.insert(all);
}
}
}
}
}
}
}
}
cout<<s.size()<<endl;
return 0;
}
答案
235
B.01 串的熵
题目内容
对于一个长度 $ n $ 的 \(01\) 串 \(S = x_1x_2x_3...x_n\)。
香农信息熵的定义为：\(H(S)=-\sum_{i=1}^{n}p(x_i)log_2(p(x_i))\) ,其中 \(p(0)\), \(p(1)\) 表示在这个 \(01\) 串中 \(0\) 和 \(1\) 出现的占比。
比如，对于 \(S = 100\) 来说，信息熵 \(H(S) = - \frac{1}{3}log_2(\frac{1}{3}) - \frac{2}{3} log_2(\frac{2}{3}) = 1.3083\)。
对于一个长度为 \(23333333\) 的 \(01\) 串，如果其信息熵为 \(11625907.5798\) ，且 \(0\) 出现次数比 \(1\) 少，那么这个 \(01\) 串中 \(0\) 出现了多少次？
本题的结果为一个整数，在提交答案时只输出这个整数，输出多余的内容将无法得分。
思路
按题意模拟即可，由题意可得 \(H(S)\)的值只与 \(01\) 出现的次数有关，因为 \(0\) 出现次数比 \(1\) 少，所以可以从 \(\lfloor \frac{23333333}{2} \rfloor = 11666666\) 开始往下枚举0的个数，同时计算 \(p(0)，p(1)\) 的占比，带入公式验证是否相等，注意设置误差范围去判断浮点数是否相等
代码
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-4;
//#define double long double
int len;
int main()
{
int len=23333333;
for(int i=len/2;i>=1;i--)
{
double px0=1.0*i/len,px1=1.0*(len-i)/len;
double H=-(i*px0*log2(px0)+(len-i)*px1*log2(px1));
if(fabs(H-11625907.5798)<=eps)
{
cout<<i<<endl;
return 0;
}
}
return 0;
}
答案
11027421
C.冶炼金属
题目内容
小蓝有一个神奇的炉子用于将普通金属 \(O\) 冶炼成为一种特殊金属 \(X\) 。这个炉子有一个称作转换率的属性 \(V\) ，\(V\) 是一个正整数，这意味着消耗 \(V\) 个普通金属 \(O\) 恰好可以冶炼出一个特殊金属 \(X\)。当普通金属 \(O\) 的数目不足 \(V\) 时，无法继续冶炼。现在给出了 \(N\) 条冶炼记录，每条记录中包含两个整数 \(A\) 和 \(B\)，这表示本次投入了 \(A\) 个普通金属\(O\)，最终冶炼出了 \(B\) 个特殊金属 \(X\)。每条记录都是独立的，这意味着上一次没消耗完的普通金属 \(O\) 不会累加到下一次的冶炼当中。根据这 \(N\) 条冶炼记录，请你推测出转换率 \(V\) 的最小值和最大值分别可能是多少。题目保证评测数据不存在无解的情况。
输入格式
第一行一个整数 \(N\)，表示冶炼记录的数目。
接下来输入 \(N\) 行，每行两个整数 \(A、B\) ，含义如题目所述。
对于 30% 的评测用例，\(1 ≤ N ≤ 100\)
对于 60% 的评测用例，\(1 ≤ N ≤ 1000\)
对于 100% 的评测用例，\(1 ≤ N ≤ 10000，1 ≤ B ≤ A ≤ 1,000,000,000\)
输出格式
输出两个整数，分别表示 \(V\) 可能的最小值和最大值，中间用空格分开。
输入样例
3
75 3
53 2
59 2
输出样例
20 25
思路
求最小值和最大值问题，可以利用二分答案进行判断。
-
求最小值
- 假设最终答案为 \(S\)
- 因为 \(S\) 的最优性，若要求答案 \(<S\)，对于每组金属 \(A\) 至少有一个不能冶炼出 \(B\) 个特殊金属
- 若答案可以 \(>S\)，则一定存在一个属性 \(V\) ，使得每组金属 \(A\) 都能冶炼出对应的 \(B\) 个特殊金属，最优解就处于可行性的分界点上
- 假设最终答案为 \(S\)
-
求最大值与上面同理
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int a[N],b[N];
int n;
bool check_min(int x)
{
for(int i=0;i<n;i++)
if(a[i]/x>b[i])return false;
return true;
}
bool check_max(int x)
{
for(int i=0;i<n;i++)
if(a[i]/x<b[i])return false;
return true;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)cin>>a[i]>>b[i];
int l=0,r=1e9;
while(l<r)
{
int mid=l+r>>1;
if(check_min(mid))r=mid;
else l=mid+1;
}
cout<<l<<' ';
l=0,r=1e9;
while(l<r)
{
int mid=l+r+1>>1;
if(check_max(mid))l=mid;
else r=mid-1;
}
cout<<l<<endl;
return 0;
}