学校的老师让我出题,我出的题目是这样的:
四、小P的假期(vacation)
题目描述
从前面的题目我们就可以得知:小P放假总是无规律的。随着科技的发展,小P知道了N天时间内的天气情况。小P当然要选择一个天气最好的一天出去玩。但因为学校的假期总是无规律的,小P只好冒着风险试一下可能出现的假期。他想知道每次他想到的可能会出现的假期当中,出去玩的那天,天气指数是多少?(不是AQI或API)
输入格式
第一行,两个整数N,M,表示共N天,小P有M个猜测。
接着输入N个数,代表每天的天气指数,天气指数越高,天气越好。
然后依次输入M个猜测,每个猜测先输入假期的区间数K[i],
然后输入K[i]行,每行两个整数,表示这个区间是假期。
输入样例
7 3
1 3 6 4 2 6 4
1
1 4
2
1 2
4 5
2
1 3
5 7
输出格式
输出M行,每行一整数,表示每个猜测中的最佳天气。
输出样例
6
4
6
注意事项
数据保证每个区间左边的数小于或等于右边的数。
保证每个猜测中的区间不重合,但是不一定按顺序。
对于此题,我的程序(C++)(此题的答案)是这样的:
#include <stdio.h>
#include <string.h>
#include <math.h>
#define LOG(x) (floor(log2(x)))
#define POW(x) (1<<x)
int n,m;
int a[1000001];
int f[1000001][21];
int max(int a,int b) {return (a>b)?a:b;}
int ask(int l,int r);
int main()
{
FILE *IN=freopen("vacation.in","r",stdin);
FILE *OUT=freopen("vacation.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",a+i);
for(int i=1;i<=n;i++) f[i][0]=a[i];
for(int j=1;j<=LOG(n);j++)
{
for(int i=1;i<=n+1-POW(j);i++)
{
f[i][j]=max(f[i][j-1],f[i+POW(j-1)][j-1]);
}
}
for(int i=1;i<=m;i++)
{
int k,ans=0;
scanf("%d",&k);
for(int j=1;j<=k;j++)
{
int x,y;
scanf("%d%d",&x,&y);
ans=max(ans,ask(x,y));
}
printf("%d\n",ans);
}
fclose(IN);
fclose(OUT);
return 0;
}
int ask(int l,int r)
{
int x=LOG(r-l+1);
return max(f[l][x],f[r-POW(x)+1][x]);
}
现在我只需要10个数据,包括输入和输出,要保证数据正确。
或者也可以给我出数据的程序代码(C++)。
后天就要上学了,谁来帮我一下?这题的数据有一点难出。
pascal的快速幂的矩阵乘法,求详解和具体实现。
题目大意:顺次给出m个置换,反复使用这m个置换对初始序列进行操作,问k次置换后的序列。m<=10, k<2^31。 首先将这m个置换“合并”起来(算出这m个置换的乘积),然后接下来我们需要执行这个置换k\/m次(取整,若有余数则剩下几步模拟即可)。注意任意一个置换都可以表示成矩阵的形式。例如,将1 2 3 4置换为3 ...