天元建设集团有限公司审计项目,烟台优化公司,网站建设费的会计分录,网络广告的形式有哪些文章目录考试复盘matrixsetstring考试复盘 首先先说T1T1T1#xff0c;嗯#xff0c;发现了列是相互独立的#xff0c;所以分开考虑了 但是实在没想到线性基#xff0c;就顺着自己的思路硬搞了505050跑路 老实说#xff0c;505050分的部分分写得都是迷迷糊糊的#xff0c;…
文章目录考试复盘matrixsetstring考试复盘 首先先说T1T1T1嗯发现了列是相互独立的所以分开考虑了 但是实在没想到线性基就顺着自己的思路硬搞了505050跑路 老实说505050分的部分分写得都是迷迷糊糊的重构了好几遍 幸好过了不然自己今天就是个圆溜的零光蛋了
没想到的点
线性基二进制的加法可以转化为异或bitset优化 再说T2T2T2嗯——怎么说呢 想到了枚举最小值然后线段树找符合的区间[val,val∗2)[val,val*2)[val,val∗2) 然后想到了三维的过原点立方体 就不会了—— 主要是之前没碰到过只做过二维的可以用setsetset整活 这次遇到了积累 幸好有202020的两种颜色数据 可是我还是没拿到 因为忘记减去(0,0,0)(0,0,0)(0,0,0)三元组情况
发生这种过失性丢分的唯一原因就是没有好好分析样例 给自己敲个警钟
没想到的点
扫描线线段树维护二维
注意的点
仔细分析样例 最后说一下T3T3T3 其实很长一段时间是没有看懂题面的 样例也想不懂 是中午吃饭的时候去操场逛了两圈才想懂了样例题面的意思 回来匆匆敲个暴力还没过样例害~
没想到的点
后缀数组同构字符串的转化——真的学到了
不过必须表扬自己认真磕出了样例 那为毛不磕一下T2T2T2的样例想穿越回去抽自己 说一下今天考试的自我感受
树立了自信心因为整体来看自己对这套题目的正确性应该是有50%50\%50%的省选并没有自己想象得那么恐怖可以说这一场考试是有史以来最认真的了从头到尾都在努力思考第一次写满了整整一张的思路推理验算也发现其实在自己一步步的推演下正解仿佛就只隔了一个教室而已hhhh真的跟着学长们一起会有那种学习认真的氛围而且今天确实学到了很多也觉得他们和自己同班的同学都很强自己也要继续努力 matrix 在二进制下加法等价于异或
∑k1nA[i][k]×C[k][j]\sum_{k1}^nA[i][k]\times C[k][j]∑k1nA[i][k]×C[k][j]
∑k∈SC[k][j]B[i][j]×C[i][j]\sum_{k∈S}C[k][j]B[i][j]\times C[i][j]∑k∈SC[k][j]B[i][j]×C[i][j]
都是第jjj列说明每列是相互独立的那么单独考虑每一列统计答案时把所有列的方案数乘起来即可
若B[i][j]0B[i][j]0B[i][j]0则等式右边为000
若B[i][j]1B[i][j]1B[i][j]1则等式右边为C[i][j]C[i][j]C[i][j]
因为是异或所以两边都可以再异或上C[i][j]C[i][j]C[i][j]
∑k∈S′C[k][j]0\sum_{k∈S}C[k][j]0∑k∈S′C[k][j]0 **这里尚有问题提醒自己一下
#include cstdio
#include bitset
using namespace std;
#define maxn 205
#define mod 998244353
int n, cnt, ans 1;
int A[maxn][maxn], B[maxn][maxn];
bitset maxn lib[maxn], t;int qkpow( int x, int y ) {int res 1;while( y ) {if( y 1 ) res 1ll * res * x % mod;x 1ll * x * x % mod;y 1;}return res;
}int main() {scanf( %d, n );for( int i 1;i n;i )for( int j 1;j n;j )scanf( %d, A[i][j] );for( int i 1;i n;i )for( int j 1;j n;j )scanf( %d, B[i][j] );for( int j 1;j n;j ) {for( int i 1;i n;i )lib[i].reset();cnt 0;for( int i 1;i n;i ) {t.reset();for( int k 1;k n;k )if( A[i][k] ) t.flip( k );if( B[i][j] ) t.flip( i );for( int k 1;k n;k )if( t[k] ) {if( lib[k].any() ) t ^ lib[k];else {lib[k] t;cnt;break;}}}ans n - cnt;}ans qkpow( 2, ans );printf( %lld\n, ans );return 0;
}set 枚举所选集合中最小的权值forforfor循环扫一遍求出[val,val∗2)[val,val*2)[val,val∗2) 里所有的物品这些都是可选的
对于求出的数量用三元组表示r,g,br,g,br,g,b 那么每一种颜色的选择都是[0,r],[0,g],[0,b][0,r],[0,g],[0,b][0,r],[0,g],[0,b]
放在三维坐标里就是求过原点的一个立方体的体积
考试的时候就只想到了立方体发现自己只会平面的所以这道题敲不来
用扫描线维护一维rrr
具体来说就是对于三元组(r,g,b)(r,g,b)(r,g,b) 在rrr时刻将(g,b)(g,b)(g,b)插进去
从大到小计算
因为在rrr时刻的(g,b)(g,b)(g,b)二元组一定在r−1r-1r−1时刻也是正确的
从小到大有的二元组会涉及到删除对于蒟蒻来说不好做因为我扫描线就很困难了好吧
剩下两维的平面直角坐标系计算围成的面积以前做过这种题
用setsetset或者线段树都可以做
#include cstdio
#include vector
#include iostream
#include algorithm
using namespace std;
#define maxn 500005
struct node {int val, c;node(){}node( int Val, int C ) {val Val, c C;}
}v[maxn];
vector pair int, int G[maxn];
int n;
int tot[3];
long long tree[maxn 2], tag[maxn 2], maxx[maxn 2];bool cmp( node x, node y ) {return x.val y.val;
} int id( char c ) {if( c R ) return 0;if( c G ) return 1;if( c B ) return 2;
}void pushdown( int num, int l, int r ) {if( tag[num] ) {maxx[num 1] tag[num 1] tag[num];maxx[num 1 |1] tag[num 1 | 1] tag[num];int mid ( l r ) 1;tree[num 1] tag[num] * ( mid - l 1 );tree[num 1 | 1] tag[num] * ( r - mid );tag[num] 0;}
}void modify( int num, int l, int r, int L, int R, int val ) {if( L l r R maxx[num] val ) {tree[num] 1ll * val * ( r - l 1 );maxx[num] tag[num] val;return;}if( l r ) return;int mid ( l r ) 1;pushdown( num, l, r );if( L mid maxx[num 1 | 1] val )//如果是被完全包含的面积是不进行计算的 这里可以多想想modify( num 1, l, mid, L, R, val );if( mid R )modify( num 1 | 1, mid 1, r, L, R, val );tree[num] tree[num 1] tree[num 1 | 1];maxx[num] max( maxx[num 1], maxx[num 1 | 1] );
}int main() {scanf( %d, n );int x; char color[3];for( int i 1;i n;i ) {scanf( %d %s, x, color );v[i] node( x, id( color[0] ) );}sort( v 1, v n 1, cmp );G[0].push_back( make_pair( 0, 0 ) );int j 1;for( int i 1;i n;i ) {while( j n v[j].val ( v[i].val 1 ) )tot[v[j].c] , j ;G[tot[0]].push_back( make_pair( tot[1], tot[2] ) );tot[v[i].c] --;}long long ans 0;for( int i n;~ i;i -- ) {//扫描线去掉一维 相当于切立方体的厚度 切成厚度为1的多个面状for( int j 0;j G[i].size();j )modify( 1, 0, n, 0, G[i][j].first, G[i][j].second 1 ); //加1是因为这个面积是和原点相围成的 画画图会发现其实需要列拔高一层ans tree[1];}printf( %lld, ans - 1 );//不算(0,0,0)return 0;
}string 对于一个字符串将第一次新出现的字符设为000其余位置赋值为该位置减去上一次字符出现的位置
这样的转化就将同构字符串改写成完全相同的数字串了
这里真的太巧妙了第一次遇到记下来
求本质不同的子串就是后缀数组的基础了
所有子串长度−-−heightheightheight数组之和
但是
题目是处理子串之间的问题
那么就有子串的改写会与原串的改写有出入的问题
就是说子串中第一次出现的某个字符不一定是原串整个串中第一次出现
那么子串该位置就需要修改为000
一共只有262626个字符所以子串最多只会有262626个位置与原串不一样
可以人为暴力排序
将一段根据修改的000划分成若干段
两个子串的cmpcmpcmp比较如果是相同的部分就用原串的后缀数组sasasa搞定更改过的地方就暴力比较
总结一下代码实现思路
对原串改写对原串后缀数组利用原串的后缀数组再次暴力排序后缀求出按照新规定下排好的后缀之间的lcplcplcp之和子串总长度减去lcplcplcp之和
#include cmath
#include cstdio
#include cstring
#include iostream
#include algorithm
using namespace std;
#define maxn 100005struct node {int n, m;int x[maxn], id[maxn], rnk[maxn 1], h[maxn], sa[maxn], tot[maxn];int st[maxn][20];void suffix( int N, int *s ) {n N, m N 1;for( int i 1;i n;i ) tot[x[i] s[i]] ;for( int i 1;i m;i ) tot[i] tot[i - 1];for( int i n;i;i -- ) sa[tot[x[i]] --] i;for( int k 1;k n;k 1 ) {int num 0;for( int i n - k 1;i n;i ) id[ num] i;for( int i 1;i n;i ) if( sa[i] k ) id[ num] sa[i] - k;memset( tot, 0, sizeof( tot ) );for( int i 1;i n;i ) tot[x[i]] ;for( int i 1;i m;i ) tot[i] tot[i - 1];for( int i n;i;i -- ) sa[tot[x[id[i]]] --] id[i];for( int i 1;i n;i ) rnk[i] x[i];x[sa[1]] num 1;for( int i 2;i n;i )x[sa[i]] ( rnk[sa[i]] rnk[sa[i - 1]] rnk[sa[i] k] rnk[sa[i - 1] k] ) ? num : num;if( n num ) break;m num;}for( int i 1;i n;i ) rnk[sa[i]] i;int k 0;for( int i 1;i n;i ) {if( rnk[i] 1 ) continue;if( k ) k --;int j sa[rnk[i] - 1];while( i k n j k n s[i k] s[j k] ) k ;h[rnk[i]] k;}for( int i 1;i n;i ) st[i][0] h[i];for( int j 1;j 20;j )for( int i 1;i n;i )if( i ( 1 j - 1 ) n ) break;else st[i][j] min( st[i][j - 1], st[i ( 1 j - 1 )][j - 1] );}int lcp( int l, int r ) {if( l 0 || r 0 || l n || r n ) return 0;if( l r ) return n - l 1;l rnk[l], r rnk[r];if( l r ) swap( l, r );l ;int i log( r - l 1 ) / log( 2 );return min( st[l][i], st[r - ( 1 i ) 1][i] );}}SA;
int n;
char s[maxn];
int last[maxn], idx[maxn], t[maxn];
int nxt[maxn][30];int LCP( int x, int y ) {int sx x, sy y;x --, y --;int len 0;for( int i 0;i 26 x 1 n y 1 n;i ) {int l SA.lcp( x 1, y 1 );if( x l 1 nxt[sx][i] y l 1 nxt[sy][i] ) return len l;if( nxt[sx][i] - sx nxt[sy][i] - sy ) {//如果一段都是相同 就一段段的跳len nxt[sx][i] - x;x nxt[sx][i], y nxt[sy][i];}else {if( nxt[sx][i] - sx nxt[sy][i] - sy )return len nxt[sx][i] - x - 1;elsereturn len nxt[sy][i] - y - 1;}}return len;
}bool cmp( int x, int y ) {int len LCP( x, y );if( x len n || y len n ) return x len n;int vx t[x len], vy t[y len];for( int i 0;i 26;i )if( nxt[x][i] x len ) { vx 0; break; }for( int i 0;i 26;i )if( nxt[y][i] y len ) { vy 0; break; }return vx vy;
}int main() {scanf( %d %s, n, s 1 );for( int i 1;i n;i ) {int j s[i] - a;if( ! last[j] ) t[i] n 1;else t[i] i - last[j];last[j] i, idx[i] i;}SA.suffix( n, t );for( int i 0;i 26;i ) nxt[n 1][i] n 2;for( int i n;i;i -- ) {for( int j 0;j 26;j )nxt[i][j] nxt[i 1][j];nxt[i][s[i] - a] i;}for( int i 1;i n;i )sort( nxt[i], nxt[i] 26 );sort( idx 1, idx n 1, cmp );long long ans 1ll * n * ( n 1 ) / 2;for( int i 1;i n;i )ans - LCP( idx[i], idx[i 1] );printf( %lld\n, ans );return 0;
}后记大概会在周末进行再次复盘重新消化吸收顺便看看到时候自己是否会将好不容易转操场想懂的地方又搞懵 走了回家睡觉现在时间2021/3/15 22:48
