呃...心态崩了。
A 又是斐波那契数列？？
时间限制 1s 内存限制 128Mb
大家都知道斐波那契数列吧？斐波那契数列的定义是这样的： f0 = 0, f1 = 1, fi = fi−1 + fi−2
现在给你一个数x，聪明的你一定知道这是斐波那契数列中的第几项。
(数据保证x一定有对应的项y，且 2 ≤ y < 1e4)
输入
第一行一个整数T，表示测试组数。
之后的T行，每行一个数x
输出
对于每个测试数据，输出一行表示数x是第几项。
输入样例
2
2
5
输出样例
3
5
思路：题意很明显，就是求斐波那契的前1e4项。但是斐波那契的增长速度很快，即使用double的1e308也只能存下很少的一部分，所以这个题的一般思路就是用数组进行大数加法。
另一种思路（从强大的学长那偷来的），由于斐波那契除了前面的几十项，其他的的每一项都很大，而且每一项的值也都不一样，因此我们可以用unsign long long来储存每一个斐波那契的值，当然，这个值肯定不是准确的斐波那契数列的值，在这个题里面，我们可以把它当作每一项的特征值（从1e18里面找到1e4个值，重复的概率微乎其微，从结果来看，确实没有重复的值）。
输入时，我们把输入的没一个数当做字符串，然后计算这个字符串（数）的值，输出对应的项数即可。
标准代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = (int) 100000 + 11;
const int M = (int) 1e6 + 11;
const int MOD = (int) 1e9 + 7;
const int INF = (int) 0x3f3f3f3f;
ull f[N]={0,1};
map<ull, int> mp;
int main(){
mp[1] = 1; mp[0] = 0;
for(int i = 2; i < N; i++){
f[i] = f[i-1] + f[i-2];
mp[f[i]] = i;
}
int T; cin>>T;
while(T--){
string s; cin>>s;
ull ans=0;
for(int i = 0; s[i]; i++)
ans = (ans * 10 + s[i] - '0');
//cout<<mp[ans]<<"\n";
}
return 0;
}B Monotonic interval
时间限制 1s 内存限制 128Mb
设 f : P → Q 是在两个带有偏序 ≤ 的集合 P 和 Q 之间的函数。在微积分中，它们是带有平常 次序的实数集的子集之间的函数，但是定义仍保持同更一般的序理论定义一样。
函数 f 是单调的，如果只要 x ≤ y，则 f(x) ≤ f(y)。因此单调函数保持次序关系。
Neo 在研究某个一元函数 f(x) 的单调性，由于该函数太复杂了，没办法直接求导。但是能很容 易的知道 f(x) 在 x1, x2, . . . , xk 的取值为 f(x1), f(x2), . . . , f(xk) 。现在需要判断 f(x) 在区间 [l, r] 是否单调。
若 f(x) 在区间 [l, r] 可能单调，请输出“Possible”
若 f(x) 在区间 [l, r] 不可能单调，请输出“Impossible”
输入
第一行两个整数 k, q
第二行 k 个整数，第 i 个值代表 xi
第三行 k 个整数，第 i 个值代表 f(xi)
接下来 q 行，每行两个整数 l, r
对于所有的输入 0 < k, q ≤ 105，其他值的绝对值均不超过 109
数据保证： ∀i 6= j 都有 xi 6= xj
输出
请输出 q 行答案。
输入样例
5 3
1 2 3 4 5
5 4 3 4 5
1 3
2 4
3 5
输出样例
Possible
Impossible
Possible
思路：很明显，这个题&#*%*@……%&*%即可。
标准代码：
#include<bits/stdc++.h>
using namespace std;
#define rep(i, j, n) for(int i=j;i<n;i++)
#define per(i, j, n) for(int i=n;i>j;--i)
const int MAXN = (int)1e5+ 5;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
map<int, int> mp;
pii dat[MAXN];
int u[MAXN], d[MAXN], ip[MAXN];
int main() {
int k, q;
while(scanf("%d%d", &k, &q) != EOF) {
memset(u, 0x00, sizeof(u));
memset(d, 0x00, sizeof(d));
for(int i = 1; i <= k; ++i) {
scanf("%d", &dat[i].first);
}
for(int i = 1; i <= k; ++i) {
scanf("%d", &dat[i].second);
}
sort(dat + 1, dat + k + 1);
for(int i = 2; i <= k; ++i) {
u[i] += u[i - 1];
d[i] += d[i - 1];
if(dat[i].second < dat[i - 1].second) ++u[i];
if(dat[i].second > dat[i - 1].second) ++d[i];
}
for(int i = 1; i <= k; ++i) ip[i] = dat[i].first;
u[k + 1] = u[k];
d[k + 1] = d[k];
for(int i = 0; i < q; ++i) {
int l, r;
scanf("%d%d", &l, &r);
int ll = lower_bound(ip + 1, ip + 1 + k, l) - ip;
int rr = upper_bound(ip + 1, ip + 1 + k, r) - ip - 1;
puts(rr <= ll || u[rr] == u[ll] || d[rr] == d[ll] ? "Possible" : "Impossible");
}
}
return 0;
}C Simplest
时间限制 1s 内存限制 128Mb
给你一段由数字0 − 9组成的字符串，请你输出它的最简自然数形式.
输入
第一行一个T，表示T组测试数据.(1 ≤ T ≤ 100)
每一组数据占一行，每一行一串字符 S. (1 ≤ strlen(S) ≤ 100000)
输出
输出字符串对应的最简自然数形式.
输入样例
2
2018722
02018722
输出样例
2018722
2018722
思路：obviously，这个题就是去除输入个字符串的前导0，然后输出字符串即可，这是一道签到题。
代码如下：
#include<stdio.h>
#include<string.h>
int main()
{
char str[100010];
int t,len,i;
scanf("%d",&t);
while(t--){
scanf("%s",str);
len=strlen(str);
for(i=0;i<len;i++){
if(str[i]!='0')
break;
}
if(i==len){
printf("0");
}
for(;i<len;i++){
printf("%c",str[i]);
}
printf("\n");
}
return 0;
}
D zz’s math problem Ⅰ
时间限制 1s 内存限制 32768kB
zz很喜欢数学，但是他又是一个数学渣，我们称这种生物叫做学渣.
zz又碰到了一个数学小问题，定义一个函数P(x) ,例如：P(123) = 1! ∗ 2! ∗ 3!
求在满足P(z) = P(x)的情况下，最大化z (x ≤ z, z 6= 1, z 6= 0)
输入
第1行输入T(1 ≤ T ≤ 20)组数据
第2行输入n(1 ≤ n ≤ 100)，表示x数字的长度
第3行输入正整数x
输出
输出最大的z（数据保证x内含大于1的数，所以z必定有解）
输入样例
2
4
1234
3
555
输出样例
33222
555
HINT
第一个样例f(1234) = 1! ∗ 2! ∗ 3! ∗ 4! = 288 = f(33222)
思路：当时看的第一眼没什么思路，以为需要求每一个质数的个数啥的，后来发现想错了。
对于每个数，我们总是希望拆成更多的数字相乘，这样会保证最后的结果最长，也就是最后的结果最大。
对于1 2 3 5 7 ，这些数的阶乘没有办法分成更小的数字的阶乘了。
对于4！，我们可以分成2！*2！*3！，这样我们就把一个数字拆成了三个数字。
对于6！，我们可以拆成3！*5！；
对于8！，我们可以拆成2！*2！*2！*7！；
对于9！，我们可以拆成2！*3！*3！*7！。
这样，这个题基本上就解决了。
代码如下：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
int p[10],len,i,j,t;
char str[110];
scanf("%d",&t);
while(t--){
memset(p,0,sizeof(p));
scanf("%d",&len);
scanf("%s",str);
for(i=0;i<len;i++){
p[str[i]-'0']++;
}
for(i=4;i<10;i++){
if(i==4){
p[2]+=p[4]*2;
p[3]+=p[4];
p[4]=0;
}
if(i==6){
p[3]+=p[6];
p[5]+=p[6];
p[6]=0;
}
if(i==8){
p[7]+=p[8];
p[2]+=3*p[8];
p[8]=0;
}
if(i==9){
p[7]+=p[9];
p[3]+=2*p[9];
p[2]+=p[9];
p[9]=0;
}
}
for(i=7;i>1;i--){
for(j=0;j<p[i];j++){
printf("%d",i);
}
}
printf("\n");
}
return 0;
}E zz’s math problem Ⅱ
时间限制 1s 内存限制 32768kB
zz作为一个数学盲也认为这个数学题真的很简单，学弟学妹们终于可以顺利签到了qwq
给出N个正整数a1, a2, ..., aN , 我们寻找一个这个表达式的最大的值
f(m) = (m mod a1) + (m mod a2) + ... + (m mod aN )
mo的意思即为A/B的余数
输入
第1行输入T(1 ≤ T ≤ 20)组数据
第2行输入N(1 ≤ N ≤ 1e3)
第3行输入n个数字ai(1 ≤ ai ≤ 1e5)
输出
输出 f 的最大值
输入样例
1
3
3 4 6
输出样例
10
HINT
f(11) = (11 mod 3) + (11 mod 4) + (11 mod 6)的值10就是函数的最大值
思路：这个题也算是一到比较简单的签到题。
对于m mod a1,他的最大值为a1-1，以此类推。
因此，f(m)的最大值 (a1-1) + (a2-1) +...+(an-1)，此时，m+1为a1,a2,...,an的公倍数。
代码如下：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
int sum,t,n,a;
scanf("%d",&t);
while(t--){
sum=0;
scanf("%d",&n);
while(n--){
scanf("%d",&a);
sum+=a-1;
}
printf("%d\n",sum);
}
return 0;
}
F Operation on sequence
时间限制 1s 内存限制 512Mb
井底之蛙，偶见圆月，便欣然忘忧。
—《剑来》
为什么总是要为难学弟学妹呢，zz并不想这样，zz决定把出一道简单的题来福利学弟学妹们。
一组下标从1开始的数组s，进行q次操作：考虑两种操作：
1 r，将子序列a[1] 到 a[r] 从小到大排序
2 r，将子序列a[1] 到 a[r] 从大到小排序
输入
第一行输入T组数据 T(1 ≤ T ≤ 10)
第一行输入两个数字 n, q(1 ≤ n, q ≤ 1e4)
第二行包含n个整数 ai(−1e9 ≤ ai ≤ 1e9) — 初始序列
然后q行表示m个操作. 第i行包含两个整数 op(1 ≤ op ≤ 2), r(1 ≤ r ≤ n)
输出
输出n个数字，即数组被操作q次改变后的数组
注意，我们要输出的是最终改变后的结果
输入样例
2
3 1
1 2 3
2 2
4 2
1 2 4 3
2 3
1 2
输出样例
2 1 3
2 4 1 3
HINT
在第二组样例中初始序列是: 1 2 4 3.
执行第一次操作后的序列是: 4 2 1 3. 执行第二次操作后的序列是: 2 4 1 3
思路：题意很明显，就是排序，但是如果暴力排序的话，我们就会TLE了。因此，我们需要找到更简单的办法。
通过观察发现，对于下图
最大的r值对应的n值为7，因此，对于其前面的操作，我们可以不进行操作，因为7前面的操作都会被第七次操作覆盖。
然后继续对7后面的操作进行查询，最后我们会找到第11次操作，所以我们直接进行第11次操作，然后依次进行12,14,15次操作。
这样，我们可以将时间复杂度降到很低的程度。如果数据水的话，我们一次排序就可以直接出结果，当然，除非是出题人非常变态，卡你的数据，那就没有办法了。
代码如下：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct name
{
int op;
int r;
int pos;
}a[10010];
int cmp1(name i,name j){
if(i.r==j.r){
return i.pos>j.pos;
}
return i.r>j.r;
}
int cmp2(int a,int b){
return a>b;
}
int main()
{
int t,n,q,i,num[10010];
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&q);
for(i=0;i<n;i++){
scanf("%d",&num[i]);
}
for(i=0;i<q;i++){
scanf("%d %d",&a[i].op,&a[i].r);
a[i].pos=i;
}
sort(a,a+q,cmp1);
int max=0;
for(i=0;i<q;i++){
if(max<=a[i].pos){
if(a[i].op==1) sort(num,num+a[i].r);
else sort(num,num+a[i].r,cmp2);
max=a[i].pos;
}
}
for(i=0;i<n;i++){
if(i==0)
printf("%d",num[i]);
else
printf(" %d",num[i]);
}
printf("\n");
}
return 0;
}
G Operation on sequence
时间限制 1s 内存限制 512Mb
真·签到题
输入一个表达式A op B op操作为0+0 , 0 −0 , 0 ∗ 0 ,A, B为整数
输入
第一行输入T 组数据T(1 ≤ T ≤ 1e2)
第二行输入A op B (−1e9 ≤ A, B ≤ 1e9) — 初始序列
输出
输出表达式结果并换行即可
输入样例
1
1 + 1
输出样例
2
思路：真·签到题
代码如下：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
char op;
int t;
long long a,b;
scanf("%d",&t);
while(t--){
scanf("%lld %c %lld",&a,&op,&b);
if(op=='+'){
printf("%lld\n",a+b);
}
else if(op=='-'){
printf("%lld\n",a-b);
}
else
printf("%lld\n",a*b);
}
return 0;
}H 又是划分问题
时间限制 1s 内存限制 512Mb
给你一个正整数n，将其划分，要求划分成的数必须是2的幂，有多少种划分方法？？
结果可能很大，我们输出对1e9+7取模的结果
输入
一个正整数n,代表要划分的数；
1 <= n <= 1e7
输入处理到文件结束
输出
输出可划分的方法数
输入样例
15
67
输出样例
26
2030
提示
当n=6时，我们可以将其划分为
1 1 1 1 1 1
1 1 1 1 2
1 1 2 2
2 2 2
1 1 4
2 4
这6种划分方法
思路：这个题是一道比较明显的dp题目，因此我们直接进行dp即可。
代码如下：
#include<cstdio>
const int N=1e7+10;
const int mod=1e9+7;
int s[N];
void solve()
{
s[1]=1;
for(int i=2;i<=N;i++)
{
if(i%2) s[i]=s[i-1];
else
s[i]=(s[i-1]+s[i/2])%mod;
}
}
int main()
{
int n;
solve();
while(~scanf("%d",&n))
printf("%d\n",s[n]);
return 0;
}
I 凸包与椭圆
时间限制 1s 内存限制 128Mb
在数学中，椭圆是围绕两个焦点的平面中的曲线，使得对于曲线上的每个点，到两个焦点的距 离之和是恒定的。因此，它是圆的概括，其是具有两个焦点在相同位置处的特殊类型的椭圆。 椭圆的形状（如何“伸长”）由其偏心度表示，对于椭圆可以是从0（圆的极限情况）到任意接 近但小于1的任何数字。
判断多个点组成的凸包是否与椭圆(x−x0) 2 a 2 + (y−y0) 2 b 2 = 1相交；若是，则输出Yes，否则输出No。 凸包就是把给定点包围在内部的、面积最小的凸多边形。
Figure 1: 示意图
输入
包含T组测试数据，对于每组测试数据，先输入一个整数n；接下来一行输入x0, y0, a, b；接下 来一行输入n个整数，代表n个点的横坐标；接下来一行输入n个整数，代表n个点的纵坐标； (x0, y0)代表椭圆的中心点。(a, b！=0),(3 ≤ n ≤ 1e5 )
输出
如果多个点组成的凸包与椭圆相交(误差保证在10−10)，则输出Yes，否则输出No
思路：这个题目涉及的知识面非常广，凸包的求法，椭圆的性质，点到直线的距离等等。
由于这个题目太过复杂，我就不做深究了。
标准代码：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
struct Point{
double x,y;
Point(double x=0,double y=0):x(x),y(y){ }
};
typedef Point Vector;
Vector operator + (Vector A,Vector B){
return Vector(A.x+B.x,A.y+B.y);
}
Vector operator - (Vector A,Vector B){
return Vector(A.x-B.x,A.y-B.y);
}
const double eps=1e-10;
int dcmp(double x){
if(fabs(x)<eps) return 0;
else return x<0?-1:1;
}
Point p[100005],ch[100005];
bool cmp(Point A,Point B){
if(A.x==B.x) return A.y<B.y;
else return A.x<B.x;
}
double det(Point A,Point B){
return A.x*B.y-A.y*B.x;
}
int ConvexHull(Point* p,int n,Point* ch){
sort(p,p+n,cmp);
int m=0;
for(int i=0;i<n;i++){
while(m>1&&det(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-2;i>=0;i--){
while(m>k&&det(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
if(n>1) m--;
return m;
}
double xx,yy,a,b;
bool check(Point A, Point B) {
if(dcmp(A.x - B.x) == 0) {
double delta = b * b - b * b * A.x * A.x / a / a;
if(delta < -eps) return false;
double y_1 = -sqrt(fabs(delta));
double y_2 = sqrt(fabs(delta));
return (dcmp(max(A.y, B.y) - y_2) >= 0 && dcmp(min(A.y, B.y) - y_2) <= 0 || (dcmp(min(A.y, B.y) - y_1) <= 0 && dcmp(max(A.y, B.y) - y_1) >= 0));
}
double k = (A.x - B.x) ? (A.y - B.y) / (A.x - B.x) : 1e100;
double g = -k * A.x + A.y;
double _a = b * b + a * a * k * k;
double _b = 2 * a * a * g * k;
double _c = a * a * (g * g - b * b);
double delta = _b * _b - 4 * _a * _c;
if(delta < -eps) return false;
double x_1 = (-_b - sqrt(fabs(delta))) / _a / 2.0;
double x_2 = (-_b + sqrt(fabs(delta))) / _a / 2.0;
return (dcmp(max(A.x, B.x) - x_2) >= 0 && dcmp(min(A.x, B.x) - x_2) <= 0 || (dcmp(min(A.x, B.x) - x_1) <= 0 && dcmp(max(A.x, B.x) - x_1) >= 0));
}
int main()
{
int T,n;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
scanf("%lf%lf%lf%lf",&xx,&yy,&a,&b);
for(int i=0;i<n;i++){
scanf("%lf",&p[i].x);
p[i].x-=xx;
}
for(int i=0;i<n;i++){
scanf("%lf",&p[i].y);
p[i].y-=yy;
}
int m=ConvexHull(p,n,ch);
int flag=0;
for(int i=0;i<m;i++){
if(check(ch[i],ch[(i+1)%m])){
flag=1;
break;
}
}
if(flag) printf("Yes\n");
else printf("No\n");
}
return 0;
}
J 台阶问题
时间限制 1s 内存限制 128Mb
有 N 级的台阶，你一开始在底部，每次可以向上迈最多 K 级台阶（最少 1 级），问到达第 N 级 台阶有多少种不同方式。
输入
多组输入,两个正整数N(N ≤ 1000)，K(K ≤ 100)。
输出 一个正整数，为不同方式数，由于答案可能很大，你需要输出 ans mod 100003 后的结果。
输入样例
5 2
输出样例
8
思路：这也是一道很典型的dp题目，我们也是直接dp即可。
代码如下：
#include<cstdio>
#include<cstring>
int a[1000+10];
int main()
{
int n,k;
while(~scanf("%d%d",&n,&k)){
memset(a,0,sizeof(a));
a[0]=1;
for(int i=1;i<=1000;i++){
for(int j=1;j<=k&&(i-j)>=0;j++){
a[i]+=a[i-j];
a[i]%=100003;
}
}
printf("%d\n",a[n]);
}
return 0;
}K 括号括号
时间限制 1s 内存限制 128Mb
小明今年上大学，在大学里发现有很多同学都女朋友，两人整天都在一起腻歪，小明看到后感 觉很孤单，现在，给你一行括号序列，你来判断一下其中的括号是否配对。
第一行输入一个数N（0<n<=100),表示有N组测试数据。后面的N行输入多组输入数据，每组 输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保 证S中只含有”[”, ”]”, ”(”, ”)” 四种字符 ,输入以“EOF”结束。
输出
每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则 输出No。
输入样例
3
[(])
(])
([[]()])
输出样例
No
No
Yes
思路：这个题目字符串长度为1e4，因此我们直接暴力求解即可。
当我们找到一对[]或()时，我们用一些特殊符号标记一下，代表之后遍历的时候就不不需要再考虑这些字符。然后一直遍历到没有括号为止。或者使用栈进行操作。
代码如下：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
using namespace std;
int main()
{
char str[10010];
int len,t,i,j,n;
scanf("%d",&t);
while(t--){
stack<char>sta;
scanf("%s",str);
len=strlen(str);
sta.push(str[0]);
for(i=1;i<len;i++){
if(sta.top()=='(' && str[i]==')'){
sta.pop();
}
else if(sta.top()=='[' && str[i]==']'){
sta.pop();
}
else sta.push(str[i]);
}
if(sta.empty()){
printf("Yes\n");
}
else printf("No\n");
}
return 0;
}
京公网安备 11010502036488号