西安网站建设外包,福州网站开发系列,2880元网站建设,深圳市做网站知名公司有哪些文章目录T1#xff1a;单峰排列题目题解codeT2#xff1a;历史研究题目题解codeT3#xff1a;大魔法师题目题解code我可能这辈子都更不出来狂欢赛5了#xff0c;先咕咕
T1#xff1a;单峰排列
题目
一个n的全排列A[i]是单峰的#xff0c;当且仅当存在某个x使得A[1]单峰排列题目题解codeT2历史研究题目题解codeT3大魔法师题目题解code我可能这辈子都更不出来狂欢赛5了先咕咕
T1单峰排列
题目
一个n的全排列A[i]是单峰的当且仅当存在某个x使得A[1]A[2]…A[x]A[x1]… A[n] 例如对于9的全排列125798643是一个单峰排列123456789也是一个单峰排列但356298741就不是 试求n的单峰全排列的个数
输入格式 输入一个数n 输出格式 输出n的全排列中单峰排列的个数。 由于这个数可能很大因此你只需要输出它mod 1234567的值。
样例 输入样例: 3 输出样例: 4 样例说明 共有以下4种方案 123 132 231 321 数据范围与提示 n2 000 000 000
题解
暴力打表找到规律2n−12^{n-1}2n−1 简单证明一下 我们把最大值即最高峰固定后剩下的n−1n-1n−1个数会有两种选法在最大值左边或右边2n−12^{n-1}2n−1 理论上还要乘以一个阶乘但是我们发现要成为单峰的话同在最大值左边的数相对位置是固定的是不能进行乱排的证毕
code
#include cstdio
#define mod 1234567
#define LL long long
int n;
LL qkpow ( LL x, LL y ) {LL ans 1;while ( y ) {if ( y 1 )ans ans * x % mod;x x * x % mod;y 1;}return ans;
}
int main() {scanf ( %d, n );LL ans qkpow ( 2, n - 1 );printf ( %lld, ans % mod );return 0;
}T2历史研究
题目
IOI国历史研究的第一人——JOI教授最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活开始着手调查日记中记载的事件。
日记中记录了连续N天发生的时间大约每天发生一件 事件有种类之分,第i天(1iN)发生的事件的种类用一个整数XiX_iXi表示XiX_iXi 越大事件的规模就越大。
JOIJOI教授决定用如下的方法分析这些日记 选择日记中连续的一些天作为分析的时间段 事件种类t的重要度为t*(这段时间内重要度为t的事件数) 计算出所有事件种类的重要度输出其中的最大值 现在你被要求制作一个帮助教授分析的程序每次给出分析的区间你需要输出重要度的最大值。
输入输出格式 输入格式 第一行两个空格分隔的整数N和Q表示日记一共记录了N天询问有Q次 接下来一行N个空格分隔的整数X1...XNX_1...X_NX1...XN表示第i天发生的事件的种类 接下来Q行第i行(1iQ)有两个空格分隔整数AiA_iAi 和BiB_iBi表示第i次询问的区间为[Ai,Bi][A_i,B_i][Ai,Bi]
输出格式 输出Q行第i行(1iQ)一个整数表示第i次询问的最大重要度
输入输出样例 输入 5 5 9 8 7 8 9 1 2 3 4 4 4 1 4 2 4 输出 9 8 8 16 16 数据范围 1N105,1Q105,1Xi109(1iN)1N10^5,1Q10^5, 1X_i10^9 (1iN)1N105,1Q105,1Xi109(1iN)
题解
这道题首先肯定能反应是莫队但是答案告诉你TTT了所以我们要学习一个新的回滚莫队 假设要查询[l,r][l,r][l,r]区间按照平时我们要移动curl,currcurl,currcurl,curr但是我们转变想法对于lll同在一个分块的查询每一次都把curlcurlcurl回拨到这一区域的最后处然后移动到lll 但是这张图是错的你看出来了吗因为同在一个块的操作rrr一定是递增的所以上图中的第二根红线应该在最后一个竖黑线的右边
具体操作细节在code中有体现
code
#include cmath
#include cstdio
#include cstring
#include iostream
#include algorithm
using namespace std;
#define LL long long
#define maxn 100005
struct node {int l, r, id;
}query[maxn];
int n, q, T;
int block[maxn];
LL result;
LL a[maxn], val[maxn], cnt[maxn], tot[maxn], ans[maxn]; bool cmp ( node x, node y ) {//以块为第一关键字右端点为第二关键字 return block[x.l] block[y.l] ? x.r y.r : block[x.l] block[y.l];
}void add ( int x ) {cnt[a[x]] ;result max ( result, cnt[a[x]] * val[a[x]] );//当规模为i的时间多了一件重要度就多了i
}
void remove ( int x ) {cnt[a[x]] --;
}int main() {scanf ( %d %d, n, q );T sqrt ( n );for ( int i 1;i n;i ) {scanf ( %lld, a[i] );block[i] ( i - 1 ) / T 1;val[i] a[i];}int num block[n];//离散化1e9最多只会变成1e5但是规模在计算时要用原来的所以不能直接替代 sort ( val 1, val n 1 );int len unique ( val 1, val n 1 ) - val - 1;for ( int i 1;i n;i )a[i] lower_bound ( val 1, val len 1, a[i] ) - val; for ( int i 1;i q;i ) {scanf ( %d %d, query[i].l, query[i].r );query[i].id i;}sort ( query 1, query q 1, cmp );int i 1;//已经处理到哪一个query操作了 for ( int id 1;id num;id ) {//依次处理每一块int tail min ( n, id * T );//有可能块数乘以大小反而炸了n int curl tail 1, curr tail;result 0;memset ( cnt, 0, sizeof ( cnt ) );//每一个块都重新开始与其他块无瓜for ( ;block[query[i].l] id;i ) {//属于同一块的每个操作一定是右端点递增的 int l query[i].l, r query[i].r;if ( block[query[i].l] block[query[i].r] ) {//整一个询问都在该块中暴力求解 LL sum 0;//不能用result该次询问根本没用到块以外的元素 for ( int k l;k r;k )tot[a[k]] 0;//注意不是对tot[k]清零 for ( int k l;k r;k ) {tot[a[k]] ;sum max ( sum, tot[a[k]] * val[a[k]] );}ans[query[i].id] sum;continue;}while ( curr r )add ( curr );//curr贡献已经算过所以先加后算curl同理 LL tmp result;//r一定是递增的记录下此时块的末尾到n的ans方便下面的还原 while ( curl l )add ( -- curl );ans[query[i].id] result;while ( curl tail )//把curl拨回到下一个块的开头表示没有一个元素等到下一次移动到新的l remove ( curl );result tmp;//重置起始值}}for ( int i 1;i q;i )printf ( %lld\n, ans[i] );return 0;
} T3大魔法师
题目
中二病患者 大魔法师小 L 制作了nnn个魔力水晶球每个水晶球有水、火、土三个属性的能量值。小 L 把这 个水晶球在地上从前向后排成一行然后开始今天的魔法表演。
我们用Ai,Bi,CiA_i,B_i,C_iAi,Bi,Ci分别表示从前向后第iii个水晶球下标从 开始的水、火、土的能量值。
小 L 计划施展mmm次魔法。每次他会选择一个区间[l,r][l,r][l,r]然后施展以下3大类、7种魔法之一
魔力激发令区间里每个水晶球中特定属性的能量爆发从而使另一个特定属性的能量增强。具体来说有以下三种可能的表现形式 火元素激发水元素能量令AiAiBiA_iA_iB_iAiAiBi 。 土元素激发火元素能量令BiBiCiB_iB_iC_iBiBiCi 。 水元素激发土元素能量令CiCiAiC_iC_iA_iCiCiAi 。 需要注意的是增强一种属性的能量并不会改变另一种属性的能量例如AiAiBiA_iA_iB_iAiAiBi并不会使BiB_iBi增加或减少。
魔力增强小 L 挥舞法杖消耗自身vvv点法力值来改变区间里每个水晶球的特定属性的能量。具体来说有以下三种可能的表现形式
火元素能量定值增强令AiAivA_iA_ivAiAiv。 水元素能量翻倍增强令BiBi∗vB_iB_i*vBiBi∗v 。 土元素能量吸收融合令CivC_ivCiv 。 魔力释放小L将区间里所有水晶球的能量聚集在一起融合成一个新的水晶球然后送给场外观众。生成的水晶球每种属性的能量值等于区间内所有水晶球对应能量值的代数和。需要注意的是魔力释放的过程不会真正改变区间内水晶球的能量。
值得一提的是小 L 制造和融合的水晶球的原材料都是定制版的 OI 工厂水晶所以这些水晶球有一个能量阈值998244353998244353998244353 。当水晶球中某种属性的能量值大于等于这个阈值时能量值会自动对阈值取模从而避免水晶球爆炸。
小 W 为小 L唯一的观众围观了整个表演并且收到了小 L 在表演中融合的每个水晶球。小 W 想知道这些水晶球蕴涵的三种属性的能量值分别是多少
题解
首先大家都能想到线段树我当时直接暴力线段树开搞后来操作时写崩了这个更改太给力 况且因为有懒标记的介入a,b,ca,b,ca,b,c都会改了后再彼此影响我们根本不知道先后顺序 那咱不用懒标记呗 那么怎么能将懒标记按顺序叠加呢矩阵 对于操作1即乘上 (100110001)\begin{pmatrix} 100\\ 110\\ 001\\ \end{pmatrix} ⎝⎛110010001⎠⎞ 操作2乘上 (100010011)\begin{pmatrix} 100\\ 010\\ 011\\ \end{pmatrix} ⎝⎛100011001⎠⎞ 操作3乘上 (101010001)\begin{pmatrix} 101\\ 010\\ 001\\ \end{pmatrix} ⎝⎛100010101⎠⎞ 操作4我们发现怎么加常数多给矩阵开一位上面就不再次多余重复乘上 (100001000010v001)\begin{pmatrix} 1000\\ 0100\\ 0010\\ v001\\ \end{pmatrix} ⎝⎜⎜⎛100v010000100001⎠⎟⎟⎞ 操作5乘上 (10000v0000100001)\begin{pmatrix} 1000\\ 0v00\\ 0010\\ 0001\\ \end{pmatrix} ⎝⎜⎜⎛10000v0000100001⎠⎟⎟⎞ 操作6乘上 (10000100000000v1)\begin{pmatrix} 1000\\ 0100\\ 0000\\ 00v1\\ \end{pmatrix} ⎝⎜⎜⎛10000100000v0001⎠⎟⎟⎞ 然后矩阵的懒标记就可以直接叠加了最后送大家五句忠告 1、此做法常数大写的不好看会100–45 2、矩阵从0开始别从1某朋友MLE 3、矩阵逼着4开多开1亲测TLE 4、longlong比int取模会慢一倍所以你懂的 5、取模本身也很慢能不取模就不取模 code
#include cstdio
#include cstring
#define maxn 250005
const int mod 998244353;
struct Matrix {int c[4][4];
//开成c[5][5]就T了一个点因为我们每次都用了memset多清了一行浪费时间 Matrix () {memset ( c, 0, sizeof ( c ) );}
}unit, ret, A[maxn], tag[maxn 2], tree[maxn 2];
//unit是单位矩阵 void read ( int x ) {x 0;char s getchar();while ( s 0 || s 9 )s getchar();while ( 0 s s 9 ) {x ( x 1 ) ( x 3 ) ( s - 0 );s getchar();}
}int add ( int x, int y ) {x 1ll * x y;return x mod ? x - mod : x;
}Matrix operator ( Matrix x, Matrix y ) {Matrix ans;for ( int i 0;i 4;i )ans.c[0][i] add ( x.c[0][i], y.c[0][i] );return ans;
}void build ( int t, int l, int r ) {tag[t] unit;if ( l r ) {tree[t] A[l];return;}int mid ( l r ) 1;build ( t 1, l, mid );build ( t 1 | 1, mid 1, r );tree[t] tree[t 1] tree[t 1 | 1];
}void MakeMark ( int t, Matrix f ) {Matrix ans;for ( int i 0;i 4;i )for ( int j 0;j 4;j )if ( f.c[i][j] )ans.c[0][j] add ( ans.c[0][j], 1ll * tree[t].c[0][i] * f.c[i][j] % mod );tree[t] ans;ans Matrix();for ( int i 0;i 4;i )for ( int j 0;j 4;j )if ( tag[t].c[i][j] ) //稀疏矩阵优化 for ( int k 0;k 4;k )if ( f.c[j][k] )ans.c[i][k] add ( ans.c[i][k], 1ll * tag[t].c[i][j] * f.c[j][k] % mod );tag[t] ans;
}void pushdown ( int t ) {MakeMark ( t 1, tag[t] );MakeMark ( t 1 | 1, tag[t] );tag[t] unit;//注意清除标记就是变成单位矩阵不是0
}void modify ( int t, int l, int r, int L, int R, Matrix f ) {if ( L l r R ) {MakeMark ( t, f );return;}int mid ( l r ) 1;pushdown ( t );if ( L mid )modify ( t 1, l, mid, L, R, f );if ( mid R )modify ( t 1 | 1, mid 1, r, L, R, f );tree[t] tree[t 1] tree[t 1 | 1];
}Matrix query ( int t, int l, int r, int L, int R ) {if ( L l r R )return tree[t];pushdown ( t );int mid ( l r ) 1;if ( R mid )return query ( t 1, l, mid, L, R );else if ( mid L )return query ( t 1 | 1, mid 1, r, L, R );elsereturn query ( t 1, l, mid, L, R ) query ( t 1 | 1, mid 1, r, L, R );
}int main() {int n, m;read ( n );for ( int i 1;i n;i ) {for ( int j 0;j 3;j )read ( A[i].c[0][j] );A[i].c[0][3] 1;}for( int i 0;i 4;i )unit.c[i][i] 1;build ( 1, 1, n );read ( m );int opt, l, r, v;for ( int i 1;i m;i ) {read ( opt );read ( l );read ( r );if ( 4 opt opt 6 )read ( v );if ( opt 7 ) {Matrix ans query ( 1, 1, n, l, r );printf ( %d %d %d\n, ans.c[0][0], ans.c[0][1], ans.c[0][2] );continue;}ret unit;//重置成单位矩阵再进行修改操作 switch ( opt ) {case 1 : ret.c[1][0] 1;break;case 2 : ret.c[2][1] 1;break;case 3 : ret.c[0][2] 1;break;case 4 : ret.c[3][0] v;break;case 5 : ret.c[1][1] v;break;case 6 : ret.c[2][2] 0, ret.c[3][2] v;break;}modify ( 1, 1, n, l, r, ret );}return 0;
}
