A:::::::::::::::::::::::::::::::::::m计划（双指针，滑动窗口，倍增）
题目描述
小明是个鹅卵石收藏者，从小到大他一共收藏了 nn 块鹅卵石，编号分别为 1∼n，价值分别为 a1，a2，⋯,an。
这天他乘船准备去往蓝桥王国，然而天有不测风云，小明所在的海域下起了暴雨。
很快小明船上的积水越来越多，为了防止沉船，小明不得不选择若干块他收藏的鹅卵石丢弃。
小明制定了一套名为m计划的选择方案，其内容如下：
对于任意区间 [i,i + m - 1]丢弃价值最小的鹅卵石i∈[1,n−m+1]。
对于一块鹅卵石，它在 m 计划中是可以被丢弃多次的。
请你输出将被小明丢弃的鹅卵石的价值。
输入描述
输入第 1 行包含两个正整数 n,m。
接下来一行包含 n 个正整 a1,a2,⋯,an，表示鹅卵石的价值。
1≤m≤n≤5×10的5次方，0≤ai≤10的9次方。
输出描述
输出共 n−m+1 行，每行输出一个整数，第 i 行输出整数的含义为 ai,ai+1,⋯,ai+m−1 的最小值。
输入输出样例
示例 1
输入
5 3 5 3 2 4 1
输出
2 2 1
#include <iostream> using namespace std; int n,m; int a[500005]; struct node{ int xiabiao; int min1; }; node check1(int x,int y){ node ans1; ans1.xiabiao=0; ans1.min1=1000000; for(int i=x;i<=y;i++){ if(a[i]<=ans1.min1){ ans1.min1=a[i]; ans1.xiabiao=i; } } return ans1; } bool check2(int l,int r,int x){ return x>=l&&x<=r; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } node mm=check1(1,m); int l=2,r=m+1; cout<<mm.min1<<endl; while(r<=n){ if(check2(l,r,mm.xiabiao)){ if(mm.min1>=a[r]){ mm.min1=a[r]; mm.xiabiao=r; } }else{ mm=check1(l,r); } cout<<mm.min1<<endl; r++; l++; } return 0; }
B:::::::::::::::::::::::::::::::::::长草（BFS）
题目描述
小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。
小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。
这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，
这四小块空地都将变为有草的小块。请告诉小明，k 个月后空地上哪些地方有草。
输入描述
输入的第一行包含两个整数 n,m。
接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。
接下来包含一个整数 k。 其中，2≤n,m≤1000，1≤k≤1000。
输出描述
输出 n 行，每行包含 mm 个字母，表示 k 个月后空地的状态。如果为小数点，表示为空地，如果字母为 g，表示长了草。
输入输出样例
示例
输入
4 5 .g... ..... ..g.. ..... 2
输出
gggg. gggg. ggggg .ggg.
运行限制
最大运行时间：1s
最大运行内存: 256M
#include <iostream> #include <queue> using namespace std; int n,m,k; char a[1005][1005]; struct node{ int x,y; int su; node(int xx,int yy,int suu){ x=xx; y=yy; su=suu; } }; queue<node> h; bool check(int x,int y){ return x>=1&&x<=n&&y>=1&&y<=m; } int f[4][2]={{1,0},{-1,0},{0,-1},{0,1}}; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; if(a[i][j]=='g'){ h.push(node(i,j,0)); } } } cin>>k; while(!h.empty()){ node j=h.front(); h.pop(); for(int i=0;i<4;i++){ int tx=j.x+f[i][0]; int ty=j.y+f[i][1]; if(check(tx,ty) && a[tx][ty]=='.' && j.su+1<=k){ a[tx][ty]='g'; h.push(node(tx,ty,j.su+1)); } } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cout<<a[i][j]; } cout<<endl; } return 0; }
C:::::::::::::::::::::::::::::::::::带分数（全排列）
题目描述
100 可以表示为带分数的形式：100 = 3 + 69258 / 714
还可以表示为：100 = 82 + 3546 / 197
注意特征：带分数中，数字 1~9 分别出现且只出现一次（不包含 0 ）。
类似这样的带分数，100 有 11 种表示法。
输入描述
从标准输入读入一个正整数 (N<1000×1000)。
输出描述
程序输出该数字用数码 1~9 不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！
输入输出样例
示例
输入
100
输出
11
运行限制
最大运行时间：3s
最大运行内存: 64M
#include <iostream> #include <algorithm> using namespace std; int n; long long ans; int a[9]={1,2,3,4,5,6,7,8,9}; int he(int l,int r){ int ans1=0; for(int i=l;i<=r;i++){ ans1=ans1*10+a[i]; } return ans1; } int main(){ cin>>n; while(next_permutation(a,a+9)){ for(int i=0;i<7;i++){ for(int j=i+1;j<8;j++){ int a=he(0,i); int b=he(i+1,j); int c=he(j+1,8); if(a*c+b==n*c){ ans++; } } } } cout<<ans; return 0; }
