问题A 幸运数
Description
我们将一个正整数分解成若干个质因数（质数因子）的乘积，若得到的质因数的个数也为质数，则称这个整数为幸运数。例如 12 = 2 × 2 × 3，它有 3 个质因数，分别是 2、2、3，而 3 也是质数，所以 12 是一个幸运数；210 不是一个幸运数，因为 210 = 2 × 3 × 5 × 7，它有 4 个质因数，分别是 2、3、5、7，而 4 不是质数。
现在，请你编程求：不大于 n 的所有幸运数。
Format
Input
输入一行一个整数 n。
Output
若干行，每行一个幸运数。要求按照从小到大的顺序输出。
Samples
Sample Input 1
12
Sample Output 1
4
6
8
9
10
12
Limitation
对于 50% 的数据，n ≤ 1000；
对于 80% 的数据，n ≤ 10000；
对于 100% 的数据，2 ≤ n ≤ 100000。
#include<bits/stdc++.h>
using namespace std;
const int maxx=1e5+15;
long long n,a[100005],b;
int main()
{
a[0]=1;
a[1]=1;
for(register int i=2;i<=sqrt(maxx);++i)
{
for(register int j=i+i;j<=maxx;j+=i)
{
a[j]=1;
}
}
cin>>n;
for(register int i=4;i<=n;++i)
{
if(a[i]==1)
{
int num=i,num2=0;
for(int j=2;num!=1;)
{
if(num%j==0) num/=j,num2++;
else
{
while(num%j!=0) j++;
}
}
if(a[num2]==0) cout<<i<<endl;
}
}
return 0;
}问题B 字符串展开
Description
对于一个字符串，如果其中含有类似于“d - h”或者“4 - 8”的字符子串，我们就把它当作一种简写。还原输出此字符串时，用连续递增的字母或数字串替代其中的减号。上面两个子串分别输出为“defgh” 和 “45678”。具体约定如下：
（1）遇到下面的情况需要对字符串进行展开：在输入的字符串中，出现了减号 “-”，减号两侧同为小写字母或同为数字，且按照 ASCII 码的顺序，减号右边的字符严格大于左边的字符。
（2）如果减号右边的字符恰好是左边字符的后继，只删除中间的减号，例如：“d - e” 应输出为 “de”，“3 - 4”应输出为 “34”。如果减号右边的字符按照 ASCII码的顺序小于或等于左边字符，输出时，要保留中间的减号，例如：“d - d” 应输出为 “d - d”，“3 - 1” 应输出为“3 - 1”。
现在，输入一个字符串，请将此字符串展开输出。
Format
Input
输入一行一个字符串，长度不超过 200，仅由数字、小写字母和减号 “-” 组成。行首和行末均无多余空格。
Output
输出一行一个字符串，为展开后的字符串。
Samples
Sample Input 1
abcs-w-y1234-9s-4zz
Sample Output 1
abcstuvwxy123456789s-4zz
#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
cin>>s;
for(int i=0;i<s.size();i++)
{
if(s[i]!='-')
{
cout<<s[i];
}
if(s[i]=='-')
{
if(s[i-1]>='a'&&s[i-1]<='z'&&s[i+1]>='a'&&s[i+1]<='z'&&int(s[i-1])<int(s[i+1]))
{
for(int j=int(s[i-1])+1;j<int(s[i+1]);j++)
{
cout<<char(j);
}
}
else if(s[i-1]>='A'&&s[i-1]<='Z'&&s[i+1]>='A'&&s[i+1]<='Z'&&int(s[i-1])<int(s[i+1]))
{
for(int j=int(s[i-1])+1;j<int(s[i+1]);j++)
{
cout<<char(j);
}
}
else if(s[i-1]>='0'&&s[i-1]<='9'&&s[i+1]>='0'&&s[i+1]<='9'&&int(s[i-1])<int(s[i+1]))
{
for(int j=int(s[i-1])+1;j<int(s[i+1]);j++)
{
cout<<char(j);
}
}
else cout<<"-";
}
}
return 0;
}问题C 懒羊羊吃草
Description
众所周知，懒羊羊是所有小羊里最贪吃的一只。然而，鲜为人知的是，懒羊羊也有存储粮食的习惯。而更让大家吃惊的事实是，我们的懒羊羊做事很有条理，每当他存储一份粮食时，他会专门拿出一个筐来存放。因此，他的仓库里有很多很多筐的青草。而我们的懒羊羊又是一个经常馋嘴的小羊，每当他想吃草时，就会从仓库里找出数量最少的一筐草，把它吃掉。可是懒羊羊因为草吃得太多了导致大脑运转缓慢，所以他不得不向你请求支援，帮他找出他应该吃数量为多少的青草。
Format
Input
第 1 行有 1 个正整数 n，表示懒羊羊一共进行了 n 次操作。
第 2 行至第 n+1 行，每行表示一个懒羊羊的操作：当这行形式为单独一个字符 “q” 时，表示懒羊羊肚子饿了，要吃掉仓库里当前数量最少的那份青草；当这行形式为一个字符 “i” 和一个整数 k 时，表示懒羊羊将一份数量为 k 的青草存入了仓库，“i” 和 k 之间用 1 个空格隔开。
保证每次询问时，仓库里都有草可吃，且所有操作中懒羊羊至少会吃一次草。
Output
输出若干行。每当输入为 “q” 时，输出一行一个数，表示懒羊羊当前吃掉的那份青草的数量是多少。
Samples
Sample Input 1
5
i 5
i 2
q
i 9
q
Sample Output 1
2
5
Explanation
样例一说明：
共有 5 次操作，分别为懒羊羊存入数量为 5 的青草，存入数量为 2 的青草，吃掉当前数量最少的青草（2），存入数量为 9 的青草，吃掉当前数量最少的青草（5）。
Limitation
对于 30% 的数据，1 ≤ n ≤ 3000；
对于 60% 的数据，1 ≤ n ≤ 40000；
对于 100% 的数据，1 ≤ n ≤ 1000000，1 ≤ k ≤ 2147483647。
#include<bits/stdc++.h>
using namespace std;
int n;
char c;
priority_queue<int,vector<int>,greater<int> > b;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",&c);
if(c=='i')
{
int k;
scanf("%d",&k);
b.push(k);
}
else
{
printf("%d\n",b.top());
b.pop();
}
}
return 0;
}问题D 方格稿纸
Description
小 y 终于在小学学会了一些字、词、句子，会写一点作文了。某一天，小 y买了一张方格稿纸来写作文，稿纸是 n 行 m 列的，形状如下所示（图中 n = m = 5）：
某天小 y 的邻居小小 x 来小 y 家玩，无聊地用黑墨水笔把小 y 新买的方格稿纸涂黑了很多格子。每个格子不是完全黑色就是完全白色，如下图所示。
小 y 不能责怪小 x。作文写不成了，他也觉得很无聊，就开始数里面有多少“魔幻方阵”。如果稿纸中一个 k × k 的正方形区域满足以下两个条件，那么它就是魔幻方阵：
（1）黑白格子的数量差不能超过 1；
（2）k 不能小于 2。
上图染色后的方格稿纸共有 9 个魔幻方阵（6 个 2 × 2 的魔幻方阵，3 个 3 × 3 的魔幻方阵）。
现在，请你帮助小 y 编程计算被染色的稿纸里面有多少个魔幻方阵。
Format
Input
第一行有 2 个正整数 n 和 m（之间以一个空格分隔），表示 n 行 m 列的稿纸。
接下来 n 行，每行有 m 个 0 或 1 的整数（之间以一个空格分隔），代表这一行中每一个格子的颜色。如果这个数是 1 则为黑色，是 0 则为白色。
Output
输出一行一个整数，表示稿纸中魔幻方阵的个数。
Samples
Sample Input 1
5 5
1 0 1 1 1
1 0 1 0 1
1 1 0 1 1
1 0 0 1 1
1 1 1 1 1
Sample Output 1
9
Limitation
对于 50% 的数据，1 ≤ n ≤ 10，1 ≤ m ≤ 10；
对于 75% 的数据，1 ≤ n ≤ 180，1 ≤ m ≤ 180；
对于 100% 的数据，1 ≤ n ≤ 300，1 ≤ m ≤ 300。
#include<bits/stdc++.h>
using namespace std;
int n,m,a[305][305],b[305][305],sum=0;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
}
}
int black=0,white=0;
for(int k=2;k<=n;k++)
{
black=0;
white=0;
for (int i=1;i<=n-k+1;i++)
{
for (int j=1;j<=m-k+1;j++)
{
int x=i+k-1;
int y=j+k-1;
black=b[x][y]-b[i-1][y]-b[x][j-1]+b[i-1][j-1];
white=k*k-black;
if(abs(black-white)<=1) sum++;
}
}
}
cout<<sum;
return 0;
}问题E 二项式展开
Description
JSOI2017 夏令营后，小 y 就在学习林老师的《数学一本通》。在《组合数学》那一章发现这样一个问题，在整式的乘法中，有：（a + b）^1（a+b）1 = a + b ，（a + b）^2（a+b）2 = a^2a2 + 2ab + b^2b2，...等等，这些都可以用简单的手算求得。但是他想如果要求 （a + b）^n（a+b）n 的展开式，就不容易很快手算了。
现在，他需要你和他一起编程解决这个问题。
Format
Input
输入一行一个整数 n。
Output
输出一行一个完整的表达式。
格式为：（a + b）^n（a+b）n = ?a^n?an + ?a^(n-1)?a(n−1)b + ?a^(n-2)?a(n−2)b^2b2 + ... + ?b^n?bn
其中：“?” 为系数，如果系数为 1，则需要省略系数；如果次数为 1，则需要省略次数；如果次数为 0，则需要省略；如果系数为 0，则需要省略这一项。
注意：前面 （a + b）^n（a+b）n 的次数是必有的，表达式的任何地方都不能有多余空格。
Samples
Sample Input 1
5
Sample Output 1
(a+b)^5=a^5+5a^4b+10a^3b^2+10a^2b^3+5ab^4+b^5
Limitation
对于 30% 的数据,n ≤ 18；
对于 60% 的数据,n ≤ 34；
对于 100% 的数据,1 ≤ n ≤ 67。
#include<bits/stdc++.h>
using namespace std;
unsigned long long n,atou,btou,jia,a[70][70];
int main()
{
cin>>n;
if(n==1)
{
cout<<"(a+b)^1=a+b";
return 0;
}
atou=n-1;
btou=1;
a[1][1]=1;
a[1][2]=1;
jia=2;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=jia;j++)
{
if(j==1) a[i][1]=1;
else if(j==jia) a[i][jia]=1;
else
{
a[i][j]=a[i-1][j]+a[i-1][j-1];
}
}
jia++;
}
cout<<"(a+b)^"<<n<<"=";
for(int i=1;i<=n+1;i++)
{
if(i==1) cout<<"a^"<<n<<"+";
else if(i==n+1) cout<<"b^"<<n;
else
{
cout<<a[n][i]<<"a";
if(atou==1) cout<<"b^"<<btou<<"+";
else if(btou==1) cout<<"^"<<atou<<"b"<<"+";
else cout<<"^"<<atou<<"b"<<"^"<<btou<<"+";
atou--;
btou++;
}
}
return 0;
}
/*
(a+b)^5=a^5+5a^4b+10a^3b^2+10a^2b^3+5ab^4+b^5
1 1
1 2 1
1 3 3 1
1 4 6 4 1
*/问题F 布丁
Description
Farmer John建立了一个布丁工厂。在接下来的 N（1 ≤ N ≤ 40000）个星期里，原料牛奶和劳动力的价格会有很大波动。Farmer John希望能够在满足消费者需求的前提下尽量减小花费。
Farmer John预计接下来每个星期会需要 Ci（1 ≤ Ci ≤ 5000）元钱来生产一单位布丁，且消费者会需要 Pi（0 ≤ Pi ≤ 10000）单位布丁。
Farmer John每星期即可以生产布丁，也可以储存布丁供以后使用。它的仓库存储一星期一单位布丁需要 S（1 ≤ S ≤ 100）元钱。但是由于布丁有保质期，所以最多只能保存 T（0 ≤ T ≤ 40000）星期。也就是说 x 星期生产的布丁可以在（x + T）星期销售，但是不能在（x + T + 1）星期销售。
请帮助Farmer John安排生产与存储的方案使得在满足消费者需求的前提下尽量减小花费。
Format
Input
第一行为 N，S 与 T。
第二行到第 N + 1 行：每一行两个数，即 Ci 与 Pi。
Output
仅一个数，即满足顾客需求前提下的最小花费。
Samples
Sample Input 1
5 10 3
12 1
21 2
27 4
45 5
52 3
Sample Output 1
488
Limitation
对于 50% 的数据，满足 1 ≤ N ≤ 5000，1 ≤ T ≤ 5000；
对于 100% 的数据，见题目描述。
#include<bits/stdc++.h>
using namespace std;
long long n,s,tim,ans=0,a[40005],b[40005],q[40005],h=1,t=0;
int main()
{
cin>>n>>s>>tim;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
}
for(int i=1;i<=n;i++)
{
while(h<=t&&q[h]<=i-tim) h++;
while(h<=t&&a[q[t]]+s*(i-q[t])>a[i]) t--;
q[++t]=i;
ans+=(a[q[h]]+s*(i-q[h]))*b[i];
}
cout<<ans;
return 0;
}问题G 滑动窗口（单调队列）
Description
给你一个长度为N的数组，一个长为K的滑动的窗体从最左移至最右端，你只能见到窗口的K个数，每次窗体向右移动一位，如下表：
你的任务是找出窗口在各位置时的 max value 以及 min value。
Format
Input
第一行，两个整数 n 和 k；
第二行为长度为 n 的数组。
Output
两行：
第一行每个位置的 min value；
第二行每个位置的 max value。
Samples
Sample Input 1
8 3
1 3 -1 -3 5 3 6 7
Sample Output 1
-1 -3 -3 -3 3 3
3 3 5 5 6 7
Limitation
对于 20% 的数据，n ≤ 500；
对于 50% 的数据，n ≤ 100000；
对于 100% 的数据，n ≤ 1000000。
#include<bits/stdc++.h>
using namespace std;
long long n,k,a[1000005];
deque<int> q,s;
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
while(!s.empty()&&s.front()<=i-k) s.pop_front();
while(!s.empty()&&a[s.back()]>=a[i]) s.pop_back();
s.push_back(i);
if(i>=k) cout<<a[s.front()]<<" ";
}
cout<<endl;
for(int i=1;i<=n;i++)
{
while(!q.empty()&&q.front()<=i-k) q.pop_front();
while(!q.empty()&&a[q.back()]<=a[i]) q.pop_back();
q.push_back(i);
if(i>=k) cout<<a[q.front()]<<" ";
}
return 0;
}