|
A：一二五八
题目描述
X星球有一个部落一直沿用着一套古老的货币。这套货币一共有四种面值，分别是1星、2星、5星和8星。X星人决定携带总金额为N星的货币来进行一次环球旅行，因为需要携带的物品实在太多太多，他希望携带的货币数量能够最少。
你能否编写一个程序帮助X星人计算出需要携带的最少货币数量？
输入
单组输入。每组一个正整数N，表示X星人携带的总金额。(N<=10^3)
输出
输出X星人最少需要携带的货币数量。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
int main(){
int n;
scanf("%d",&n);
int ans=n/8;
n%=8;
if(n==1||n==2||n==5)ans++;
else if(n)ans+=2;
printf("%d\n",ans);
return 0;
}
B：和为1
题目描述
给出n个正整数，这n个正整数中可能存在一些相同的数。现在从这n个数中选取m个正整数，分别记为X1、X2、…、Xm，使得这m个数满足如下公式：
1/X1 + 1/X2 + … + 1/Xm = 1
请问存在多少种不同的数字组合可以使得上述公式得以成立？
输入
单组输入。
第1行输入一个正整数n，表示输入的正整数个数。(n<=100)
第2行输入n个正整数，两两之间用空格隔开。
输出
输出满足要求的组合个数。如果一个组合都不存在，则输出“No solution!”。
- 搜索
- 找到一组和为1的数很容易，直接搜索，但是答案很多重复的组，所以要加判重
- 搜索：分为分子，分母，每次选的数与当前选的分母求出最小公倍数组成新的分母，再求出分子，继续搜索
- 判重：先对数组从小到大排序，每一组选的数用字符串s连接，在记录答案时，只记录第一次出现的答案字符串
最后一发AC91%，改了好久的判重
#include<bits/stdc++.h>
using namespace std;
int a[105];
int ans,n;
map<string,bool>vis;
int gcd(int x,int y){
return y==0 ? x:gcd(y,x%y);
}
int lcm(int x,int y){
return x*y/gcd(x,y);
}
void dfs(int fz,int fm,string s,int pos){
if(fz==fm&&fz){
if(!vis[s])
ans++;
vis[s]=1;
return ;
}
if(pos>n)return ;
if(fz==0)dfs(1,a[pos],s+to_string(a[pos]),pos+1);
else {
int m=lcm(a[pos],fm);
int z=(m/a[pos])+(m/fm)*fz;
int g=gcd(m,z);
dfs(z/g,m/g,s+to_string(a[pos]),pos+1);
}
dfs(fz,fm,s,pos+1);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n);
dfs(0,0,"",1);
if(ans)printf("%d\n",ans);
else printf("No solution!\n");
return 0;
}
C:素数拆分
题目描述
如果将一个n（n>=2）位的素数拆分成两部分，其中高m位是一个素数，低(n-m)位也是一个素数，那么这个数称为可拆分素数。
例如113，它可以拆成两部分，高两位11是一个素数，低一位3也是一个素数，因此113是一个可拆分素数。
现在输入两个正整数M和N(M<N)，请编写一个程序计算M到N之间有多少个可拆分素数（可以包含M和N）。
输入
单组输入。
输入两个正整数M和N（10<=M<N<=10^6）。
输出
输出M和N之间可拆分素数的个数（包含M和N）。
- 枚举
- 先筛法求出2~m之间的素数，然后枚举n-m之间的数，判断是否是可拆分素数
- 判断素数是否可拆分也是枚举，枚举前后各多少个数
代码可能比我说的容易看懂
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
int n,m;
bool isprime[1000005];
void prime(){
int i,j;
isprime[0] = false;
isprime[1] = false;
isprime[2] = true;
for(i=3; i<=m; i++) {
isprime[i++] = true;
isprime[i] = false;
}
int ma = sqrt(m);
for(i=3; i<=ma; i++){
if(isprime[i]) {
for(j=i+i; j <= m; j+=i)
isprime[j] = false;
}
}
}
bool check(int i){
int x=10;
while(x<=i){
if(isprime[i/x]&&isprime[i%x])
return 1;
x*=10;
}
return 0;
}
void cnt(){
int ans=0;
for(int i=n;i<=m;i++){
if(isprime[i]&&check(i)){
ans++;
}
}
printf("%d\n",ans);
}
int main(){
scanf("%d%d",&n,&m);
prime();
cnt();
return 0;
}
D：空心圆柱
题目描述
小米同学用薄纸片卷了N个空心的小圆柱，他想把一些小的空心圆柱嵌到大的空心圆柱里面。
已知每一个空心圆柱的底面半径，在不考虑薄纸片本身厚度的情况下，请问这些空心圆柱最多可以嵌套多少层？
输入
单组输入。
第1行输入一个正整数N表示空心小圆柱的总数量。（N<=10^3）
第2行输入N个正数（有整数也有小数，最多不超过八位小数），表示N个空心小圆柱底面半径。
输出
输出最多可以嵌套的空心圆柱的数量。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
int n;
double a[1005];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf",&a[i]);
}
sort(a+1,a+1+n);
int ans=0;
for(int i=1;i<=n;i++){
if(a[i]!=a[i-1])ans++;
}
printf("%d\n",ans);
return 0;
}
E:营救行动
题目描述
X星卫士接到了一个紧急任务。大BOSS被困Y星的地狱迷宫，X星卫士必须携带“时空转移丸”尽快前往营救。
Y星的地狱迷宫是一个有M*N个小房间构成的矩形结构，迷宫中的小房间一共有M行，每一行有N列。
迷宫的入口为第1行第1列，标记为“S”，大BOSS被困的位置标记为“B”。
X星卫士通过每个普通小房间的时间均为1分钟。但是在这个迷宫中，有一些房间中设置了机关，一共包含三类不同的机关，分别是：死亡陷阱、延时陷阱和定向陷阱。死亡陷阱是不能进入的房间，一旦进入将万劫不复，营救失败；延时陷阱中布满死亡光线，需要3分钟时间才能够顺利通过；定向陷阱中设有一个定向诱导装置，进入该房间者将丧失转向功能（只在该房间中丧失），只能沿着直线行进，例如从左边进入只能从右边出来，从上面进入只能从下面出来，不过通过时间还是1分钟。
对于一个给定的地狱迷宫地图，请问最少需要多少时间（分钟）才能够营救到大BOSS（进入BOSS房间不消耗步数）？
输入
单组输入。
第1行输入两个正整数M和N，分别表示迷宫矩阵的行和列。（M<=103，N<=103）
第2行到第M+1行，每行N列，对应一个二维字符矩阵，用于表示地狱迷宫。
在字符矩阵中，“S”表示迷宫入口，“B”表示大BOSS被困的位置，“0”表示可以正常通过的房间（通过时间为1分钟），“#”表示死亡陷阱，“*”表示延时陷阱，“@”表示定向陷阱。
输出
X星卫士营救到大BOSS所需最少时间（单位：分钟）；如果不能营救成功，则输出“Failure"。
- 搜索
- 在矩阵上的搜索，关于搜索
强推我这篇博客 搜索专题：DFS - 这里是最短路模板，所以用bfs快一点，唯一要注意的就是@情况，是要延同一个方向一直走，直到走到一个不为@的地方
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
int d[][2]={0,1,1,0,0,-1,-1,0};
int dis[1005][1005];
char a[1005][1005];
struct node{
int x,y;
int ans;
bool operator <(const node &q)const{
return ans>q.ans;
}
};
int ans;
bool check(int x,int y){
if(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]!='#')
return 1;
return 0;
}
void bfs(){
priority_queue<node>q;
q.push({1,1,0});
while(!q.empty()){
node k=q.top();
q.pop();
if(a[k.x][k.y]=='B'){
ans=k.ans-1;
return ;
}
if(dis[k.x][k.y])continue;
dis[k.x][k.y]=1;
for(int i=0;i<4;i++){
int x=k.x+d[i][0];
int y=k.y+d[i][1];
if(check(x,y)){
if(a[x][y]=='0'||a[x][y]=='B')q.push({x,y,k.ans+1});
else if(a[x][y]=='*')q.push({x,y,k.ans+3});
else if(a[x][y]=='@'){
int res=k.ans;
while(check(x,y)&&a[x][y]=='@'){
dis[x][y]=1;
x+=d[i][0];
y+=d[i][1];
res++;
}
if(check(x,y)){
if(a[x][y]=='0'||a[x][y]=='B')
q.push({x,y,res+1});
else if(a[x][y]=='*')
q.push({x,y,res+3});
}
}
}
}
}
return ;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",a[i]+1);
}
bfs();
if(ans)printf("%d\n",ans);
else puts("Failure");
return 0;
}
F：a碟的微机
题目描述
a碟最近刚考完微机，他觉得这门课学的太痛苦了，于是想出了一些好(wu)玩(liao)的题目，有一段数据在地址线上串行传送（将数据分解成二进制位用一条信号线，一位一位顺序传送的方式）。a碟突发奇想（乱想），将二进制位的0当作“(”，1当作“)”，如果一串数据中的"01"完全匹配（例如01, 0011, 001011），则输出“Good”，若不是完全匹配（例如001,10,0111），则输出"Bad" 。
现在给你一段数据长度为n的串s(n<=1e5)，请你判断这段数据是否满足上述定义？
输入
输入一串数据串s，其长度<=1e5
输出
如果该数据串中的"01"完全匹配，则输出"Good"，否则输出"Bad"
- 模拟
- 就是一个括号匹配，堆栈模拟一下就好了，也比较水
#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool cmp(string s){
stack<char>st;
for(int i=0;i<s.size();i++){
if(s[i]=='1'){
if(!st.empty())
st.pop();
else return 0;
}else{
st.push(s[i]);
}
}
if(st.empty())return 1;
else return 0;
}
int main(){
string s;
cin>>s;
if(cmp(s))puts("Good");
else puts("Bad");
return 0;
}
G：a碟的备忘录
题目描述
a碟本学期学习了安卓开发，他的同学ph经常忘记事情，于是他想做一个简单的备忘录帮助ph。
他希望他的备忘录包含以下功能：
1、向备忘录插入字符串 s（英文字符）
2、删除备忘录最后k个字符（保证不为空串）
3、输出备忘录第k个字符（保证不为空串）
4、撤销最近的1或2操作，使备忘录回到1（或者2）操作之前的状态
可是a碟琢磨了半天还是做不来，聪明的你能解决a碟的问题，帮助ph吗？
输入
第一行输入一个整数t，代表总的操作数量
以下t行每行描述了一个操作，每行以一个整数n开始（1 <= n <= 4）。
n表示上述问题陈述中定义的操作类型。 如果操作需要参数，则后跟空格分隔的参数。
题目保证所有操作均合法
1 <= t <= 10^6
1 <= k <= |记事本内容长度|
每个测试数据中s的总长度 <= 10^6
输出
只有操作3需要输出结果，每行以换行符结束。
- 模拟
- 直接用字符串模拟（
这个不难啊，为啥没啥人做，难道是我的开题顺序影响了大家做题 ）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
string s2[1000005];
int main(){
int n;
cin>>n;
int d,k;
string s1,str="";
int pos=1;
for(int i=1;i<=n;i++){
cin>>d;
if(d==1){
cin>>s1;
s2[pos++]=str;
str+=s1;
}
else if(d==2){
cin>>k;
s2[pos++]=str;
str=str.substr(0,str.size()-k);
}
else if(d==3){
cin>>k;
cout<<str[k-1]<<endl;
}
else {
str=s2[--pos];
}
}
return 0;
}
H：X星人的密码
题目描述
聪明的X星人决定向在外太空的同伴发送一封非常非常重要的文件，该文件需要输入一个特殊的密码才能够打开。
这个特殊的密码是一串数字，这串数字密码需要通过解析一个包含很多正整数的文件才能够得到。
数字密码由三部分组成，这三部分对应三个正整数：第1部分是文件中所包含的最大正整数，第2部分是文件的正整数序列中所包含的最长单调递减子序列的长度，第3部分是文件中所包含的最小正整数。如果你得到了这三个部分，它们连接而成得到的数字字符串就是破解文件所需的密码。
X星人正在寻求你的帮助，你需要编写一个程序帮助他提取文件中蕴含的密码。
输入
单组输入。
第1行输入一个正整数N，表示文件中的正整数个数。(N<=1000)
第2行输入N个正整数，两两之间用空格隔开。最大正整数不超过10^6。
输出
输出文件中蕴含的数字密码。
- 最长单调递减子序列的长度，将数组倒序就相当于最长上升子序列长度
- 堆栈模拟，因为这个好记
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
int a[1005];
int n;
int lis(){
reverse(a+1,a+1+n);
vector<int>stk;
stk.push_back(a[1]);
for (int i = 2; i<=n; ++i) {
if (a[i] > stk.back())
stk.push_back(a[i]);
else
*lower_bound(stk.begin(), stk.end(), a[i]) = a[i];
}
return stk.size();
}
int main(){
while(~scanf("%d",&n)){
int ma=-INF,mi=INF;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>ma)ma=a[i];
if(a[i]<mi)mi=a[i];
}
printf("%d%d%d\n",ma,lis(),mi);
}
return 0;
}
I：重复DNA子片段
题目描述
给定一段由A、G、C和T这四种字符组成的DNA片段。
请编写一个程序计算该DNA片段中所包含的最长且不重叠的重复DNA子片段的长度。
例如：如果输入是“AAAAA”，则最长且不重叠的重复DNA子片段的长度为2，因为对应的不重叠最长重复子片段是“AA”。
输入
单组输入。
输入一段由A、G、C和T这四种字符组成的DNA片段。（1<=长度<=3000）
输出
输出最长且不重叠的重复DNA子片段的长度。
#include<bits/stdc++.h>
using namespace std;
int dp[3005][3005];
int main(){
string s;
int ans=0;
cin>>s;
for(int i=1;i<=s.size();i++){
for(int j=1;j<=s.size();j++){
if(i!=j&&s[i-1]==s[j-1]){
dp[i][j] = dp[i-1][j-1]+1;
if(dp[i][j]>ans&&ans<abs(i-j))
ans=dp[i][j];
}
}
}
cout<<ans<<endl;
return 0;
}
|