A::::::::::::::::::小数第n位
题目描述
我们知道,整数做除法时,有时得到有限小数,有时得到无限循环小数。
如果我们把有限小数的末尾加上无限多个 0,它们就有了统一的形式。
本题的任务是:在上面的约定下,求整数除法小数点后的第 n 位开始的 3 位数。
输入描述
输入一行三个整数:a b n,用空格分开。a 是被除数,b 是除数,n是所求的小数后位置(0<a,b,n<109)
输出描述
输出一行 3 位数字,表示:a 除以 b,小数后第 n 位开始的 3 位数字。
输入输出样例
示例
输入
1 8 1
输出
125
#include <iostream>
using namespace std;
long long a,b,c;
int main(){
cin>>a>>b>>c;
a=a%b; //求小数所以不影响,现在a<b,a*10/b就是第一个小数位
while(c-10>0){
a=a*1e10; //每次移动10位,一位乘以10,10位乘以1e10。
a=a%b;
c-=10;
}
for(int i=1;i<=c+2;i++){
if(i>=c){
cout<<a*10/b; //这一位的小数值
}
a=a*10%b; //剩下的
}
return 0;
}
B::::::::::::::::::卡片换位(BFS)
题目描述
你玩过华容道的游戏吗?
这是个类似的,但更简单的游戏。
看下面 3 x 2 的格子
+---+---+---+
| A | * | * |
+---+---+---+
| B | | * |
+---+---+---+
在其中放 5 张牌,其中 A 代表关羽,B 代表张飞,* 代表士兵。
还有个格子是空着的。
你可以把一张牌移动到相邻的空格中去(对角不算相邻)。
游戏的目标是:关羽和张飞交换位置,其它的牌随便在哪里都可以。
输入描述
输入两行 6 个字符表示当前的局面
输出描述
一个整数,表示最少多少步,才能把 A B 换位(其它牌位置随意)
输入输出样例
示例
输入
* A
**B
输出
17
运行限制
- 最大运行时间:1s
- 最大运行内存: 256M
#include <iostream>
#include <queue>
#include <map>
using namespace std;
string chushi[2];
int x,y,ax,ay,bx,by;
struct node{
int x,y;
int ax,ay;
int bx,by;
int ans;
string lu[2];
};
node one;
queue<node> q;
int g[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
bool check(int x,int y){
return x>=0&&x<2&&y>=0&&y<3;
}
map<string,bool> pan;
int main(){
getline(cin,chushi[0]);
getline(cin,chushi[1]);
for(int i=0;i<2;i++){
for(int j=0;j<3;j++){
if(chushi[i][j]==' '){
x=i,y=j;
}
if(chushi[i][j]=='A'){
ax=i,ay=j;
}
if(chushi[i][j]=='B'){
bx=i,by=j;
}
}
}
one.x=x,one.y=y,one.ax=ax,one.ay=ay,one.bx=bx,one.ans=0;
one.by=by,one.lu[0]=chushi[0],one.lu[1]=chushi[1];
string mm=chushi[0]+chushi[1];
pan[mm]=1;
q.push(one);
while(!q.empty()){
node f=q.front();
q.pop();
if(f.ax==bx && f.ay==by && f.bx==ax && f.by==ay){
cout<<f.ans;
break;
}
for(int i=0;i<4;i++){
int tx=f.x+g[i][0];
int ty=f.y+g[i][1];
if(check(tx,ty)){
string h[2];
h[0]=f.lu[0];
h[1]=f.lu[1];
h[tx][ty]=' ';
h[f.x][f.y]=f.lu[tx][ty];
string mm=h[0]+h[1];
if(!pan[mm]){
pan[mm]=1;
int xx,yy,axx,ayy,bxx,byy;
for(int i=0;i<2;i++){
for(int j=0;j<3;j++){
if(h[i][j]==' '){
xx=i,yy=j;
}
if(h[i][j]=='A'){
axx=i,ayy=j;
}
if(h[i][j]=='B'){
bxx=i,byy=j;
}
}
}
node two;
two.x=xx,two.y=yy,two.ax=axx,two.ay=ayy,two.bx=bxx,two.ans=f.ans+1;
two.by=byy,two.lu[0]=h[0],two.lu[1]=h[1];
q.push(two);
}
}
}
}
return 0;
}
C::::::::::::::::::左移右移(双向链表,双指针)
问题描述
小蓝有一个长度为 N 的数组, 初始时从左到右依次是1,2,3,…N 。
之后小蓝对这个数组进行了 M 次操作, 每次操作可能是以下 2 种之一:
-
左移 x, 即把 x 移动到最左边。
-
右移 x, 即把 x 移动到最右边。
请你回答经过 M 次操作之后, 数组从左到右每个数是多少?
输入格式
第一行包含 2 个整数, N 和 M 。
以下 M 行每行一个操作, 其中 “L x "表示左移 x, R x "表示右移 x 。
输出格式
输出 NN 个数, 代表操作后的数组。
样例输入
5 3
L 3
L 2
R 1
样例输出
2 3 4 5 1
样例说明
样例中的数组变化如下:
[1,2,3,4,5]→[3,1,2,4,5]→[2,3,1,4,5]→[2,3,4,5,1]
评测用例规模与约定
对于 50% 的评测用例1≤N,M≤10000.
对于 100% 的评测用例, 1≤N,M≤200000,1≤x≤N.
运行限制
- 最大运行时间:3s
- 最大运行内存: 512M
双向链表:
#include <iostream>
#include <list>
using namespace std;
list<int> l;
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
l.push_back(i);
}
for(int i=0;i<m;i++){
char a;
int v;
cin>>a>>v;
if(a=='L'){
l.remove(v);
l.push_front(v);
}
if(a=='R'){
l.remove(v);
l.push_back(v);
}
}
for(list<int>::iterator it=l.begin();it!=l.end();it++){
cout<<*it<<' ';
}
return 0;
}
能过50%
双指针:
#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
int a[200005];
struct node{
long long zuobiao;
int zhi;
bool operator<(const node &rhs)const{
return zuobiao<rhs.zuobiao;
}
};
node b[1000000];
int main(){
cin>>n>>m;
long long l=-100;
long long r=1e6;
for(int i=1;i<=n;i++){
b[i].zhi=i;
b[i].zuobiao=i;
}
for(int i=0;i<m;i++){
char a;
int v;
cin>>a>>v;
if(a=='L'){
b[v].zuobiao=l;
l--;
}else{
b[v].zuobiao=r;
r++;
}
}
sort(b+1,b+n+1);
for(int i=1;i<=n;i++){
cout<<b[i].zhi<<' ';
}
return 0;
}
D::::::::::::::::::数数(思维)
问题描述
任何一个大于 1 的正整数都能被分解为若干个质数相乘, 比如 28=2×2×7 被分解为了三个质数相乘。请问在区间 [2333333, 23333333] 中有多少个正整数 可以被分解为 12 个质数相乘?
答案提交
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。
运行限制
- 最大运行时间:1s
- 最大运行内存: 512M
上千万的数据量,不可能12个循环吧
#include <iostream>
#include <vector>
using namespace std;
int ans;
bool sushu(int x){
if(x==1){
return false;
}
if(x==2){
return true;
}
for(int i=2;i*i<=x;i++){
if(x%i==0){
return false;
}
}
return true;
}
int su[23333339];
vector<int> p;
int main(){
long long a=2333333;
long long b=23333333;
for(int i=2;i<=b;i++){
if(!su[i]&&sushu(i)){
su[i]=1; //su[i]=1,代表i由一个数的值
p.push_back(i); //素数压入动态数组
}
if(i>=a&&su[i]==12){ //判断是否是12个数的乘积
ans++;
} //当i==a时,p中是2到a的所有素数
for(vector<int>::iterator it=p.begin();it!=p.end();it++){
if(i* *it>b){
break;
}else{
su[i* *it]=su[i]+1; //i* *it两个乘积,再i的基础上乘以*it,所以值加一;
}
}
}
cout<<ans;
return 0;
}
半分钟出答案,还是慢点,填空题无所谓了
E::::::::::::::::::约瑟夫杯(队列,循环列表)
题目描述
设有 nn 个人围坐在圆桌周围,现从某个位置 kk 上的人开始报数,报数到 m 的人就站出来。下一个人,即原来的第 m+1 个位置上的人,又从 11 开始报数,再报数到 m 的人站出来。依次重复下去,直到全部的人都站出来为止。试设计一个程序求出这 n 个人的出列顺序。
要求一:采用循环链表解决。
要求二:可以使用模拟法,模拟循环链表。
要求三:可以不使用循环链表类的定义使用方式。
输入描述
输入只有一行且为用空格隔开的三个正整数 n,k,m,其含义如上所述。
输出描述
共 n 行,表示这 n 个人的出列顺序。
输入输出样例
示例 1
输入
3 5 8
输出
3
2
1
队列方法:
#include <iostream>
#include <queue>
using namespace std;
queue<int> q;
int n,k,m; //n个人,k开始,m出
int main(){
cin>>n>>k>>m;
k=k%n;
for(int i=k;i<=n;i++){
q.push(i);
}
for(int i=1;i<k;i++){
q.push(i);
}
while(!q.empty()){
for(int i=1;i<m;i++){
int c=q.front();
q.pop();
q.push(c);
}
int c=q.front();
cout<<c<<endl;
q.pop();
}
return 0;
}
循环链表方法:
#include <iostream>
using namespace std;
typedef struct node
{
int data;
struct node* next;
}LNode, *Linklist;
void initlink(Linklist &head, int n)
{
head = new LNode;
LNode * p = head;
p->data = 1;
for (int i = 2; i <= n; i++)
{
p->next = new LNode;
p = p->next;
p->data = i;
}
p->next = head;
}
void baoshu(Linklist &head, int k, int m)
{
LNode *p = head;
for (int i = 1; i < k; i++)
p = p->next;
while (p->next != p)
{
for (int j = 1; j < m - 1; j++) p = p->next;
cout << p->next->data << endl;
p->next = p->next->next;
p = p->next;
}
cout << p->data;
}
int main()
{
int n, k, m;
cin >> n >> k >> m;
Linklist head;
initlink(head, n);
baoshu(head, k, m);
}
F::::::::::::::::::移动字母(DFS,BFS)
题目描述
2x3=6 个方格中放入 ABCDE 五个字母,右下角的那个格空着。如下图所示。
和空格子相邻的格子中的字母可以移动到空格中,比如,图中的 C 和 E 就可以移动,移动后的局面分别是:
A B
D E C
A B C
D E
为了表示方便,我们把 6 个格子中字母配置用一个串表示出来,比如上边的两种局面分别表示为:
AB*DEC
ABCD*E
题目的要求是:请编写程序,由用户输入若干表示局面的串,程序通过计算,输出是否能通过对初始状态经过若干次移动到达该状态。可以实现输出 1,否则输出 0。初始状态为:ABCDE*。
输入描述
先是一个整数 nn,表示接下来有 nn 行状态。
输出描述
程序输出 nn 行 1 或 0。
输入输出样例
示例
输入
7 BCDEA* DAECB* ECABD* BCDAE* DAEBC* ECADB* EDCAB*
输出
1 1 1 0 0 0 0
#include <iostream>
#include <map>
using namespace std;
int n;
string a[2];
string b[2];
int bb[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
bool res;
map<string,bool> vis;
bool check1(){
for(int i=0;i<2;i++){
for(int j=0;j<3;j++){
if(a[i][j]!=b[i][j]){
return false;
}
}
}
return true;
}
bool check2(int x,int y){
return x>=0&&x<2&&y>=0&&y<3;
}
void dfs(int x,int y){
if(res){
return;
}
if(check1()){
res=true;
return;
}
for(int i=0;i<4;i++){
int tx=x+bb[i][0];
int ty=y+bb[i][1];
if(check2(tx,ty) ){
char c=a[x][y];
a[x][y]=a[tx][ty];
a[tx][ty]=c;
if(!vis[a[0]+a[1]]) {
vis[a[0]+a[1]]=1;
dfs(tx,ty);
}
c=a[x][y];
a[x][y]=a[tx][ty];
a[tx][ty]=c;
}
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
a[0]="ABC";
a[1]="DE*";
for(int i=0;i<2;i++){
for(int j=0;j<3;j++){
cin>>b[i][j];
}
}
res=false;
vis.clear();
dfs(1,2);
if(res){
cout<<1<<endl;
}else{
cout<<0<<endl;
}
}
return 0;
}
G::::::::::::::::::路径之迷(DFS)
题目描述
小明冒充 XX 星球的骑士,进入了一个奇怪的城堡。
城堡里边什么都没有,只有方形石头铺成的地面。
假设城堡地面是 n×n 个方格。如下图所示。
按习俗,骑士要从西北角走到东南角。可以横向或纵向移动,但不能斜着走,也不能跳跃。每走到一个新方格,就要向正北方和正西方各射一箭。(城堡的西墙和北墙内各有 n 个靶子)同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目,你能推断出骑士的行走路线吗?有时是可以的,比如上图中的例子。
本题的要求就是已知箭靶数字,求骑士的行走路径(测试数据保证路径唯一)
输入描述
第一行一个整数 N (0≤N≤20),表示地面有N×N 个方格。
第二行 N 个整数,空格分开,表示北边的箭靶上的数字(自西向东)
第三行 N 个整数,空格分开,表示西边的箭靶上的数字(自北向南)
输出描述
输出一行若干个整数,表示骑士路径。
为了方便表示,我们约定每个小格子用一个数字代表,从西北角开始编号: 0,1,2,3 ⋯
比如,上图中的方块编号为:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
输入输出样例
示例
输入
4
2 4 3 4
4 3 3 3
输出
0 4 5 1 2 3 7 11 10 9 13 14 15
#include <iostream>
using namespace std;
int n;
int g[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int shang[25];
int zuo[25];
int shang1[25];
int zuo1[25];
bool falge;
struct node{
int x,y;
};
node lu[405];
bool vis[25][25];
int m=1;
bool check1(){
for(int i=0;i<n;i++){
if(shang[i]!=shang1[i] || zuo[i]!=zuo1[i]){
return false;
}
}
return true;
}
bool check2(int x,int y){
return x>=0&&y>=0&&x<n&&y<n;
}
bool check3(){
for(int i=0;i<n;i++){
if(shang1[i]>shang[i] || zuo1[i]>zuo[i]){
return false;
}
}
return true;
}
void dfs(int x,int y){
if(!check3()|| falge){ //剪枝
return;
}
if(x==n-1&&y==n-1 && check1()){
for(int i=0;i<m;i++){
cout<<lu[i].x*n+lu[i].y<<' ';
}
falge=1;
return;
}
for(int i=0;i<4;i++){
int tx=x+g[i][0];
int ty=y+g[i][1];
if(check2(tx,ty) && !vis[tx][ty]){
vis[tx][ty]=1;
lu[m].x=tx;
lu[m].y=ty;
shang1[ty]+=1;
zuo1[tx]+=1;
m++;
dfs(tx,ty);
lu[m].x=0;
lu[m].y=0;
shang1[ty]-=1;
zuo1[tx]-=1;
m--;
vis[tx][ty]=0;
}
}
}
int main(){
zuo1[0]=1;
shang1[0]=1;
lu[0].x=0;
lu[0].y=0;
vis[0][0]=1;
cin>>n;
for(int i=0;i<n;i++){
cin>>shang[i];
}
for(int i=0;i<n;i++){
cin>>zuo[i];
}
dfs(0,0);
return 0;
}
H::::::::::::::::::分考场(DFS)
题目描述
n 个人参加某项特殊考试。
为了公平,要求任何两个认识的人不能分在同一个考场。
求最少需要分几个考场才能满足条件。
输入描述
输入格式:
第一行,一个整数 n (1≤n≤100),表示参加考试的人数。
第二行,一个整数 m,表示接下来有 m 行数据。
以下 m 行每行的格式为:两个整数 a,b,用空格分开 ( 1≤a,b≤n )表示第 a 个人与第 b 个人认识。
输出描述
输出一行一个整数,表示最少分几个考场。
输入输出样例
示例
输入
5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
输出
4
#include <iostream>
using namespace std;
int n,m;
bool xi[105][105];
int ans=1e8;
int cher[105][105];
void dfs(int p,int room){
if(room>=ans){
return;
}
if(p>n){
ans=min(ans,room);
return;
}
for(int i=1;i<=room;i++){
int j=0;
while(cher[i][j] && !xi[cher[i][j]][p]) j++;
if(!cher[i][j]){
cher[i][j]=p;
dfs(p+1,room);
cher[i][j]=0;
}
}
cher[room+1][0]=p;
dfs(p+1,room+1);
cher[room+1][0]=0;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
xi[a][b]=xi[b][a]=1;
}
dfs(1,1); //第一个人,1个教室;
cout<<ans;
return 0;
}
I::::::::::::::::::质数拆分(DP,01背包)
题目描述
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
将 2019 拆分为若干个两两不同的质数之和,一共有多少种不同的方法?
注意交换顺序视为同一种方法,例如 2+2017=2019 与 2017+2=2019 视为同一种方法。
运行限制
- 最大运行时间:1s
- 最大运行内存: 128M
#include <iostream>
using namespace std;
long long f[2020][2020]; //前i个数组成j的方案数
bool check(int x){
if(x==1){
return false;
}
if(x==2){
return true;
}
for(int i=2;i*i<=x;i++){
if(x%i==0){
return false;
}
}
return true;
}
int zhi[2020];
int main(){
int len=1;
for(int i=1;i<2019;i++){
if(check(i)){
zhi[len++]=i;
}
}
f[0][0]=1;
for(int i=1;i<len;i++){
for(int j=0;j<=2019;j++){
f[i][j]=f[i-1][j];
if(j>=zhi[i]){
f[i][j]+=f[i-1][j-zhi[i]];
}
}
}
cout<<f[len-1][2019];
return 0;
}
for(int i=1;i<len;i++){
for(int j=0;j<=2019;j++){
f[i][j]=f[i-1][j];
if(j>=zhi[i]){
f[i][j]+=f[i-1][j-zhi[i]];
}
}
}状态1:目标:值小于该质数时 f[i][j]=f[i-1][j];
状态2:目标:值不小于该质数时 要加上前i-1质数构成该指数的方案数f[i][j]+=f[i-1][j-zhi[i]];
J::::::::::::::::::修改数组(并查集)
题目描述
给定一个长度为 N 的数组 A=[A1,A2,⋅⋅⋅,AN],数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A2,A3,⋅⋅⋅,AN。
当修改 Ai 时,小明会检查 Ai 是否在 A1 ∼ Ai−1 中出现过。如果出现过,则小明会给 Ai 加上 1 ;如果新的 Ai 仍在之前出现过,小明会持续给 Ai 加 1 ,直 到 Ai 没有在 A1 ∼ Ai−1 中出现过。
当 AN 也经过上述修改之后,显然 A 数组中就没有重复的整数了。
现在给定初始的 A 数组,请你计算出最终的 A 数组。
输入描述
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN。
其中,1≤N≤105,1≤Ai≤106。
输出描述
输出 N 个整数,依次是最终的 A1,A2,⋅⋅⋅,AN。
输入输出样例
示例
输入
5
2 1 1 3 4
输出文章来源:https://www.toymoban.com/news/detail-402374.html
2 1 3 4 5
建立一个并查集,初始化根节点都是自己,当第一次出现时,返回根节点也就是自己,然后根节点加一,下次再次查找该数时,发现自己不是大boss,然后找boss,若是下一个boss也不是大boss,就继续找,直到找到大boss。文章来源地址https://www.toymoban.com/news/detail-402374.html
#include <iostream>
using namespace std;
int a[10000005];
int find(int x){
if(a[x]!=x) a[x]=find(a[x]);
return a[x]; //不是大boss去找大boss
}
void jiaru(int x,int y){
int tx=find(x);
int ty=find(y);
if(tx!=ty){ //不是一个大boss建立新的树
a[x]=y;
}
}
int n;
int main(){
cin>>n;
for(int i=1;i<=10000005;i++){
a[i]=i; //初始化根节点都是自己
}
for(int i=1;i<=n;i++){
int x;
cin>>x;
x=find(x);
cout<<x<<' ';
a[x]=x+1;
}
return 0;
}
到了这里,关于蓝桥杯带刷题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!