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; }
