P1009 求概率
求该字符在单词中出现的概率。
分析 简单字符串模拟题目，需要注意的是先统一大小写，以及保留小数。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n; string s; char c; cin>>n;
while(n--){
cin>>c>>s;
int p=0;
if(c<97) c+=32; // 统一小写
for(int i=0; i<s.size(); i++) {
if(s[i] < 97) s[i] += 32;
if(c==s[i]) p++; // 计数
}
cout<<fixed<<setprecision(5)<<1.0*p/s.size()<<endl;
}
return 0;
}
P533 【基础】小 X 与小和尚(sum)
\(1～n，n～1， 1～n，n～1，...，\) 一直这么循环地敲下去。
敲完第 \(m\) 次的时候，他一共敲了多少下？
分析 由于 \(n\) 次可以看作一个周期 （\(2n\)看作一个也可以），那么可以计算出 有 \(k=\lfloor \frac{m}{n} \rfloor\) 个完整周期，有 \(t=m\%n\) 个剩余天数。
如果 \(k\) 是偶数，那么剩余 \(t\) 天敲击次数应当是 \(1,2,3,...,t\)
如果 \(k\) 是奇数，那么剩余 \(t\) 天敲击次数应当是 \(n,n-1,n-2,...,n-t+1\)
所以总共敲击次数为：完整周期内的敲击次数 \(k*(1+n)*n/2\) + 剩余 \(t\) 天敲击次数。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL; // 注意开 long long
int main(){
LL n,m; cin>>n>>m;
LL k=m/n, t = m%n;
LL res = k*(1+n)*n/2;
if(k&1) res += (n+n-t+1)*t/2;
else res += (1+t)*t/2;
cout<<res;
return 0;
}
P276 【基础】小X与缩写
读入一行英文句子，将用括号括出的词组替换为首字母缩写再输出。
分析 注意一些细节，通过分类讨论的方式将每种情况罗列出来。
#include<bits/stdc++.h>
using namespace std;
int main(){
string s; int f=0;
while(cin>> s){
if(f){ // find 如果没有查询到会返回 string::npos，等同 int类型的 -1
if(s.find(')') != string::npos) f = 0;
cout<<char(s[0]-32);
if(s.back()==',' ||s.back()=='.') cout<<s.back();
if(f==0) cout<<" ";
}else {
if(s.find('(') != string::npos) f = 1;
if(f) {
cout<<char(s[1]-32);
if(s.back()==',' ||s.back()=='.') cout<<s.back();
}else cout<<s<<" ";
}
}
return 0;
}
P402 【基础】小丽找潜在的素数
题意 哪些二进制数转为十进制后，是素数，计算出这样的数有多少个？
分析 纯纯模拟题，如果不会进制转换，那就要好好推导一下过程
进制转换
- k进制转十进制：按权展开求和
- 十进制转k进制：短除法
- 快速拼凑法
- 取三合一法
- 取四合一法
素数判定
素数，又名质数，指大于 1 的自然数中，因子只有 1 和其本身的数。
所以可以通过枚举 \([2,n-1]\) 这个区间查看是否有 \(n\) 的因子存在，如果存在，那么 \(n\) 不是质数。
但是仔细想想，\(a*b=n \ (a≤b)\) ，可以只枚举 \(n\) 的小因子 \(a\)，而 \(a ≤ \sqrt{n}\)，即 \(a*a≤n\)。
但是 \(a*a\) 容易爆 \(int\)，所以在程序中常写作： \(a<=n/a\).
#include<bits/stdc++.h>
using namespace std;
bool isp(int n){
for(int i=2; i<=n/i; i++) if(n%i==0) return 0;
return n>1;
}
int main(){
int n,m=0; cin>>n; string s;
while(n--){
cin>>s; int t=0;
for(int i=0; i<s.size(); i++)
t = t*2 + s[i]-'0'; // 2进制转十进制
if(isp(t)) m ++;
}
cout<<m;
return 0;
}
P277 【基础】小 X 与位运算(bignum)
题意 求二进制位运算结果。
分析 注意，实际 and,or 这是针对逻辑运算的，只是在此题中可以这样使用。
理一下逻辑步骤
- 给定两个二进制字符串 a,b
- 进行位运算是低位对齐，高位补0，所以先补齐
- 进行位运算，可以同步输出运算结果，也可以保存起来，不输出前导0，可以开个标记 f.
- 如果结果就是 0，特殊处理.
#include <bits/stdc++.h>
using namespace std;
int main() {
string a, b, c; cin >> a >> b >> c;
int n = a.size(), m = b.size();
if (n < m) swap(a, b), swap(n,m); // a>=b, n>=m
string t( n-m, '0'); b = t + b;
bool f = 0;
for (int i = 0; i < n; i++) {
int A = a[i] == '1', B = b[i] == '1', C;
if (c == "and") C = A and B;
if (c == "or") C = A or B;
if (c == "xor") C = A ^ B;
if (C || f) { cout << C; f = 1; }
}
if(f==0) cout<<0;
return 0;
}