2022牛客寒假算法基础集训营（四）全部题解
A R 模拟
题意：
给一个包含只包含大写字母的字符串，找有多少个子串包含 k 个 R 字符且不包含 P 字符
题解：
不包括 P 就分段来计算
至少包含 k 个 R
贡献就等于这个位置 第前 k 个 R 位置
|
B 进制 线段树
题意：
题解：
所能表示的某进制的最小值的某进制就是该串里的最大的数字+1,不然那个数不可能出现
题目要求单点修改和区间查询
那就是最简单的求最大值和求和的线段树板子
求和的线段树是存了2-10进制棵每一位的数字 该位权值
比如10进制树 123存的是1 10 10 ———- 210 ———-3
求和出来还要除与多的权值 取[1,2] ，答案等于120/10
这个求和的bug真的找了一万年呜呜呜
|
C 蓝彗星 前缀和
题意：
题解：
前缀和求覆盖次数
using namespace std;
const int N=2e5+5;
int a[N], b[N], c[N];
signed main() {
int n, t;
cin>>n>>t;
string s;
cin>>s;
s='.'+s;
for(int i=1; i<=n; i++) {
int x; cin>>x;
if(s[i]=='B') b[x]++, b[x+t]--;//x和x+t-1+1
else c[x]++, c[x+t]--;
}
for(int i=1; i<=N; i++) {
b[i]+=b[i-1];
c[i]+=c[i-1];
//cout<<i<<" "<<b[i]<<" "<<c[i]<<endl;输出就可以看到这个时间 彗星亮了没
}
int ans=0;
for(int i=1; i<=N; i++) {
if(b[i]&&!c[i]) ans++;
}
cout<<ans<<endl;
return 0;
}
D 雪色光晕 计算几何
题意：
题解：
求点到线段的最短距离板子
using namespace std;
const int N=2e5+5;
const int M=1e9+7;
double dis(double xx, double yy, double x1, double y2) {
return sqrt((xx-x1)*(xx-x1)+(yy-y2)*(yy-y2));
}
double Pd(double x, double y, double x1, double y1, double x2, double y2){
double cross = (x2 - x1) * (x - x1) + (y2 - y1) * (y - y1);
if (cross <= 0) return sqrt((x - x1) * (x - x1) + (y - y1) * (y - y1));
double d2 = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
if (cross >= d2) return sqrt((x - x2) * (x - x2) + (y - y2) * (y - y2));
double r = cross / d2;
double px = x1 + (x2 - x1) * r;
double py = y1 + (y2 - y1) * r;
return sqrt((x - px) * (x - px) + (py - y) * (py - y));
}
signed main() {
int n;
cin>>n;
double x0, y0, X, Y;
cin>>x0>>y0>>X>>Y;
double minn=dis(x0,y0,X,Y);
for(int i=1; i<=n; i++) {
double x, y;
cin>>x>>y;
minn=min(minn, Pd(X, Y, x0,y0, x0+x, y0+y));
x0+=x;
y0+=y;
}
cout<<fixed<<setprecision(8)<<minn<<endl;
return 0;
}
E 真假签到题 签到
题意：
那个函数就是求本身
题解：
要开longlong
using namespace std;
const int N=2e5+5;
signed main() {
int x;
cin>>x;
cout<<x<<endl;
return 0;
}
F 小红的记谱法 模拟
题意：
模拟
题解：
模拟
using namespace std;
const int N=2e5+5;
int a[N], b[N], c[N];
map<char, int> mp;
signed main() {
string pp="CDEFGAB";
for(int i=0; i<pp.size(); i++) mp[pp[i]]=i+1;
string s;
cin>>s;
int n=s.size();
int p=0;//呜呜在里面定义忘记赋值 找了好久bug
for(int i=0; i<n; i++) {
if(s[i]=='<') p++;
else if(s[i]=='>') p--;
else {
cout<<mp[s[i]];
if(p==0) continue;
else if(p>0) {
for(int j=1; j<=p; j++) cout<<'.';
}else for(int j=1; j<=-p; j++) cout<<'*';
}
}
cout<<endl;
return 0;
}
G 子序列权值乘积 数学
题意：
求这个数组的所有 非空子序列 的最大值*最小值的乘积是多少？
1e5
题解：
先排序
若它作为一个字序列的最小值，后面的 n-i 个数随意，也就是有 2的n-i 次方 个机会作为最小值，同样的，有 2的 i-1 次方 个机会作为最小值，那这个数产生的贡献就是
幂次取模的话取 Mod-1
|
H 真真真真真签到题 签到
题意：
题解：
就是把距离当成体对角线来算体积
因为小紫肯定在正方体中间
using namespace std;
const int N=2e5+5;
signed main() {
double x;
cin>>x;
cout<<fixed<<setprecision(7)<<x/sqrt(3)*2*x/sqrt(3)*2*x/sqrt(3)*2<<endl;
return 0;
}
I 爆炸的符卡洋洋洒洒 背包dp
题意
题解
dp[i][j] 代表轮到第 i 张卡时候的质量% k==j 的最大值
转移方程
int p=(j-a[i]+k) %k
dp[j][i]=max(dp[j][i-1], dp[j][i]); 不取当前牌
dp[j][i]=max(dp[p][i-1]+b[i], dp[j][i]); 取当前牌
using namespace std;
const int N=2e5+5;
const int M=1e9+7;
int a[N], b[N];
int dp[1005][1005];
signed main() {
int n, k;
cin>>n>>k;
for(int i=1; i<=n; i++) {
cin>>a[i]>>b[i];
a[i]%=k;
}
for（int i=0; i<=n; i++）for(int j=0; j<=k; j++) dp[i][j]=-1e18;
dp[0][0]=0;
for(int i=1; i<=n; i++) {
for(int j=k-1; j>=0; j--) {
int p=(j-a[i]+k)%k;
dp[j][i]=max(dp[j][i-1], dp[j][i]);
dp[j][i]=max(dp[p][i-1]+b[i], dp[j][i]);
}
}
int maxx=dp[0][n];
if(maxx<=0) cout<<-1<<endl;
else cout<<maxx<<endl;
return 0;
}
J 区间合数的最小公倍数 数学
题意：
题解：
|
K 小红的真真假假签到题题 签到
题意：
题解：
101变成101101
就等于乘（2的幂次+1）一定是倍数且1的个数不同
using namespace std;
const int N=2e5+5;
signed main() {
int x;
cin>>x;
string s;
while(x) {
s=char('0'+x%2)+s;
x/=2;
}
s=s+s;
int ans=0;
int p=1;
for(int i=0; i<s.size(); i++) {
ans=ans*2+(s[i]-'0');
}
cout<<ans<<endl;
return 0;
}
