日期统计
小蓝现在有一个长度为 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 年的日期。
对于相同的日期你只需要统计一次即可。
本题的结果为一个整数，在提交答案时只输出这个整数，输出多余的内容将无法得分。
思路:
需要理解一下这个子序列的意思（按顺序找到的日期）
代码：
#include <bits/stdc++.h>
using namespace std;
int a[105];
bool vis[30000000];
int ans;
int mm[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int check(int i){
if (vis[i]!=0){
return false;
}
int x=i;
int d=x%100;
int m=x/100%100;
if (m>=1&&m<=12){
if (d>=1&&d<=mm[m]){
vis[i]++;
return true;
}
}
return false;
}
void dfs(int x,int pose,int date){
if (pose==8){
if (check(date)){
ans++;
}
return;
}
if (x==100){
return;
}
if ((pose==0&&a[x]==2)||
(pose==1&&a[x]==0)||
(pose==2&&a[x]==2)||
(pose==3&&a[x]==3)||
(pose==4&&a[x]>=0&&a[x]<=1)||
(pose==5&&a[x]>=0&&a[x]<=9)||
(pose==6&&a[x]<=3&&a[x]>=0)||
(pose==7&&a[x]>=0&&a[x]<=9)
){
dfs(x+1,pose+1,date*10+a[x]);
}
dfs(x+1,pose,date);
}
int main(){
for (int i=0;i<100;i++){
cin>>a[i];
}
dfs(0,0,0);
cout<<ans;
}
01 串的熵
题目描述
对于一个长度为 n 的 01 串 S = x1x2x3…xn.
香农信息熵的定义为：
。
其中 p(0), p(1) 表示在这个 01 串中 0 和 1 出现的占比。
比如，对于S = 100 来说，信息熵 H(S ) = - 1/3 log2(1/3) - 2/3 log2(2/3) - 2/3 log2(2/3) = 1.3083。
对于一个长度为23333333 的 01 串，如果其信息熵为 11625907.5798，且 0 出现次数比 1 少，那么这个01 串中 0 出现了多少次？
本题的结果为一个整数，在提交答案时只输出这个整数，输出多余的内容将无法得分。
思路：
得静下去慢慢理解题意，大致讲的就是一个串里只有0和1,0的个数*一个值+1的个数乘一个值等于其信息熵
代码：
#include<bits/stdc++.h>
using namespace std;
const double ans=11625907.5798;
int main(){
int n=23333333;
for (int u=0;u<=n/2;u++){
int v=n-u;
double res=-v*1.0*v/n*log2(1.0*v/n)-u*1.0*u/n*log2(1.0*u/n);
if (abs(res-ans)<=1e-4){
cout<<u;
}
}
return 0;
}
冶炼金属
题目描述
小蓝有一个神奇的炉子用于将普通金属 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
数据范围与提示
当 V = 20 时，有：⌊75 / 20⌋ = 3，⌊53 / 20⌋ = 2，⌊59 / 20⌋ = 2，可以看到符合所有冶炼记录。
当 V = 25 时，有：⌊75 / 25⌋ = 3，⌊53 / 25⌋ = 2，⌊59 / 25⌋ = 2，可以看到符合所有冶炼记录。
且再也找不到比 20 更小或者比 25 更大的符合条件的 V 值了。
思路：
求边界值，比如求最大的，那我们就看最大可以为多少，然后取公共的最小值，求最小的，就求公共的最大值，这样所有数都满足。
代码：
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int maxx=0x3f3f3f3f;
int minn=0;
for (int i=1;i<=n;i++){
int a,b;
cin>>a>>b;
int k;//找共同最大值
k=a/b;
while (a/k==b){
k++;
}
maxx=min(k-1,maxx);
k=a/b;//找共同最小值
while (a/k==b){
k--;
}
minn=max(k+1,minn);
}
cout<<minn<<" "<<maxx;
}
飞机降落
题目描述
N 架飞机准备降落到某个只有一条跑道的机场。
其中第 i 架飞机在 Ti 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 Di 个单位时间。
即它最早可以于 Ti 时刻开始降落，最晚可以于 Ti + Di 时刻开始降落。
降落过程需要Li个单位时间。
一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落。
但是不能在前一架飞机完成降落前开始降落。
请你判断 N 架飞机是否可以全部安全降落。
输入格式
输入包含多组数据。
第一行包含一个整数 T ，代表测试数据的组数。
对于每组数据，第一行包含一个整数 N 。
以下 N 行，每行包含三个整数：Ti，Di 和Li。
对于 30% 的数据，N ≤ 2。
对于 100% 的数据，1 ≤ T ≤ 10，1 ≤ N ≤ 10，0 ≤ Ti,Di,Li ≤ 100,000。
输出格式
对于每组数据，输出 YES 或者 NO，代表是否可以全部安全降落。
输入样例 复制
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
输出样例 复制
YES
NO
数据范围与提示
对于第一组数据:
安排第3 架飞机于0 时刻开始降落，20 时刻完成降落。
安排第2 架飞机于20 时刻开始降落，30 时刻完成降落。
安排第1 架飞机于30 时刻开始降落，40 时刻完成降落。
对于第二组数据，无论如何安排，都会有飞机不能及时降落。
思路：
DFS模拟所有可能就行，注意题目有一个最早发射时间和另一架飞机立即开始下降的区别
代码：
#include <bits/stdc++.h>
using namespace std;
int t[15],d[15],l[15];
bool vis[20];
int n;
int flag=0;
void dfs(int time,int dep){
if (dep==n){
flag=1;
return;
}
for (int i=1;i<=n;i++){
if (vis[i]==0){
if (time>t[i]+d[i]){
return;
}
vis[i]=1;
dfs(max(t[i],time)+l[i],dep+1);
if (flag==1){
return ;
}
vis[i]=0;
}
}
}
int main(){
int m;
cin>>m;
while (m--){
cin>>n;
flag=0;
for (int i=1;i<=15;i++){
vis[i]=0;
}
for (int i=1;i<=n;i++){
cin>>t[i]>>d[i]>>l[i];
}
dfs(0,0);
if (flag==1){
cout<<"YES"<<"\n";
}else{
cout<<"NO"<<"\n";
}
}
}
接龙数列
题目描述
对于一个长度为 K 的整数数列：A1, A2, … , AK，我们称之为接龙数列：
当且仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字(2 ≤ i ≤ K)。
例如：12, 23, 35, 56, 61, 11 是接龙数列；
12, 23, 34, 56 不是接龙数列，因为 56 的首位数字不等于 34 的末位数字。
所有长度为 1 的整数数列都是接龙数列。
现在给定一个长度为 N 的数列A1, A2, … , AN，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？
输入格式
第一行包含一个整数 N 。
第二行包含 N 个整数 A1, A2, … , AN。
对于 20% 的数据，1 ≤ N ≤ 20。
对于 50% 的数据，1 ≤ N ≤ 10000。
对于 100% 的数据，1 ≤ N ≤ 105，1 ≤ Ai ≤ 109。
所有 Ai 保证不包含前导0。
输出格式
一个整数代表答案。
输入样例 复制
5
11 121 22 12 2023
输出样例 复制
1
数据范围与提示
删除 22，剩余 11, 121, 12, 2023 是接龙数列。
思路：
dp，和最长上升序列做法很像
代码：
#include <bits/stdc++.h>
using namespace std;
string s;
int dp[15];
int main(){
int n;
cin>>n;
int maxx=0;
for (int i=1;i<=n;i++){
cin>>s;
int m=s.size();
int x=s[0],y=s[m-1];
dp[y]=max(dp[x]+1,dp[y]);
maxx=max(maxx,dp[y]);
}
cout<<n-maxx;
}
子串简写
题目描述
程序猿圈子里正在流行一种很新的简写方法：
对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。
例如internationalization简写成 i18n，Kubernetes 简写成 K8s, Lanqiao 简写成 L5o 等。
在本题中，我们规定长度大于等于 K 的字符串都可以采用这种简写方法。
长度小于 K 的字符串不允许使用这种简写。
给定一个字符串 S 和两个字符 c1 和 c2。
请你计算 S 有多少个以 c1 开头 c2 结尾的子串可以采用这种简写？
输入格式
第一行包含一个整数 K。
第二行包含一个字符串 S 和两个字符c1 和c2。
对于 20% 的数据，2 ≤ K ≤ |S| ≤ 10000。
对于 100% 的数据，2 ≤ K ≤ |S| ≤ 5 × 105。
S 只包含小写字母。c1 和 c2 都是小写字母。
|S| 代表字符串S 的长度。
输出格式
一个整数代表答案。
输入样例 复制
4
abababdb a b
输出样例 复制
6
数据范围与提示
符合条件的子串如下所示，中括号内是该子串：
[abab]abdb
[ababab]db
[abababdb]
ab[abab]db
ab[ababdb]
abab[abdb]
思路：
用前缀和把所有字母存下来，再用num[m-1]-num[i+n-2]就可以得到当前开头的总和
代码:
#include <bits/stdc++.h>
using namespace std;
string s;
int num[500005];
int main(){
int n;
cin>>n;
cin>>s;
char a,b;
cin>>a>>b;
int m=s.size();
for (int i=m-1;i>=0;i--){
if (s[i]==b){
num[i]++;
}
}
for (int i=0;i<m-1;i++){
num[i+1]=num[i]+num[i+1];
}
long long ans=0;
for (int i=0;i<m;i++){
if (s[i]==a&&i<m-n+1){
ans+=num[m-1]-num[i+n-2];
}
}
cout<<ans;
}
}
