东莞做网站公司首选!免费库存管理软件哪个好

当前位置： 首页 > news >正文

东莞做网站公司首选!,免费库存管理软件哪个好,太原做手机网站设计,网站建设厂家复盘 7#xff1a;30 开题 想到几天前被普及组难度模拟赛支配的恐惧#xff0c;下意识觉得题目很难 先看 T1#xff0c;好像不是很难#xff0c;魔改 Kruskal 应该就行 看 T2 #xff0c;感觉很神奇#xff0c;看到多串匹配想到 AC 自动机#xff0c;又想了想 NOIP …复盘 730 开题 想到几天前被普及组难度模拟赛支配的恐惧下意识觉得题目很难 先看 T1好像不是很难魔改 Kruskal 应该就行 看 T2 感觉很神奇看到多串匹配想到 AC 自动机又想了想 NOIP 模拟赛 T2 考 AC 自动机奇奇怪怪 T3 神奇构造先放 T4 想到以前做过的一道很像的题记得是转化成二维平面中的点会很好做但仔细想想发现不对 回来准备码 T1推了推细节感觉问题不大毕竟纯模拟 Kruskal 过程大概 7:50 开始码 8:20 码完测大样例发现跑 1.7s时间限制 1.2s 仔细分析了一下感觉这个思路很像正解应该是哪个细节没处理好 尝试一行一行删代码看那个地方跑得慢发现竟然是 s o r t sort sort 逆天想了想改成桶排大样例极限跑 1.1s 以为能过就扔了 看 T2 首先看出有性质包含别人的串没用。那么枚举左端点找右端点最小的能匹配的串就行这个 AC 自动机可以解决 接下来唐氏了一会一直想把这 n n n 个串转化成若干个矩形然后平面内扫描线 去了个厕所突然发现直接 for 一遍就做完了回忆了一下 AC 自动机的细节 10:10 码完过了大样例 接下来看 T3 想到一个很显然但巨难写的做法感觉很不对决定放弃先看 T4 发现 40 40 40 是送的 枚举 x x x 即可快速码 接下来看式子 h i ⌈ a i x ⌉ h_i\left \lceil \frac{a_i}{x} \right \rceil hi​⌈xai​​⌉意识到 后半部分得到变化是 s q r t sqrt sqrt 级的想到对于 n ≤ 2000 n\leq 2000 n≤2000 可以把这些变化的点存起来 然发现数论分块会不了一点不会找这些变化点 最后就在反复打表、猜性质竟发现按 a i × h i a_i\times h_i ai​×hi​ 排序后 x x x 有决策单调性寄完了 最终 60 100 0 20 180 rk_10086 总结一下T1 应该再去拍一下的或许能意识到时间上跑不过去的问题赛后稍微卡一下常 vectornode - vectorint ) 就过了 T3 构造实际上没那么难应该多想想 T4 想的有点偏对于 h i ⌈ a i x ⌉ h_i\left \lceil \frac{a_i}{x} \right \rceil hi​⌈xai​​⌉ 结构应该优先考虑枚举 取整号内部的部分这样是 O ( n l o g n ) O(nlogn) O(nlogn) 的而不是数论分块的 n \sqrt n n ​ 题解 T1 先说 K r u s k a l Kruskal Kruskal 做法 考虑暴力的情况把所有边建出来按权值从小到大排序 会发现枚举时会连着处理 一段本质上相同的边连接同色点考虑优化这个过程直接 O ( 1 ) O(1) O(1) 算代价同时需要注意标记 某颜色点内部是否连通 写的时候注意一下常数问题可以通过 接下来正解 考虑最终状态一定是每种颜色的连通块都至少往外连了一条边 那么对于每种颜色取出一个点钦定这个点是往外连的直接跑最小生成树 由于是完全图考虑 P r i m Prim Prim跑完后对于剩下的所有点只需选择一个代价最小的颜色连上去即可这一步可以直接把 P r i m Prim Prim 的 w w w 数组拿来用 #includebits/stdc.h using namespace std ;typedef long long LL ; const int N 5050 ; int n , a[N] ; int x , y , l , h ; // 完全图 prim
int c[N] , e[N][N] ; bool vis[N] ;int main() {scanf(%d , n ) ;for(int i 1 ; i n ; i ) {scanf(%d , a[i] ) ;}scanf(%d%d%d%d , x , y , l , h ) ;int C 0 , A 1 , B 1 ;for(int i 1 ; i n*n ; i ) {C (1LL*x*Cy)%h ;if( A B ) {e[A][B] e[B][A] C ;}B ;if( B n1 ) {A ;B 1 ;}}LL ans 0 ;for(int i 1 ; i n ; i ) c[i] e[1][i] ;vis[1] 1 ;for(int i 1 ; i n ; i ) {int Min 1e9 , id ;for(int j 1 ; j n ; j ) {if( !vis[j] Min c[j] ) {Min c[j] ;id j ;}}vis[id] 1 ;ans Min ;for(int j 1 ; j n ; j ) c[j] min( c[j] , e[id][j] ) ;}for(int i 1 ; i n ; i ) ans 1LLc[i](a[i]-1) ;printf(%lld , ans ) ;return 0 ; }T2 比较简单放一个 AC 自动机的板子回忆一下 char s[N] ;int tr[N*5][26] , tot , fail[N*5] , V[N5] ;void Insert(){int p 0 , len strlen( s1 ) ;for(int i 1 ; i len ; i ) {int c s[i]-a ;if( !tr[p][c] ) tr[p][c] tot , V[tot] 1e9 ;p tr[p][c] ;} V[p] len ;}void AC_build(){queueint q ;for(int i 0 ; i 26 ; i ) {if( tr[0][i] ) q.push( tr[0][i] ) ;}while( !q.empty() ) {int x q.front() ; q.pop() ;for(int i 0 ; i 26 ; i ) {if( tr[x][i] ) fail[tr[x][i]] tr[fail[x]][i] , q.push( tr[x][i] ) , V[tr[x][i]] min( V[tr[x][i]] , V[fail[tr[x][i]]] ) ;else tr[x][i] tr[fail[x]][i] ;}}}T3 T4 比较套路的题应该会的 考虑 x x x 已知时每个人的局数显然是 h i ⌈ a i x ⌉ h_i\left \lceil \frac{a_i}{x} \right \rceil hi​⌈xai​​⌉ 枚举 x x x 后再 check n n n 个人需要 n 2 n^2 n2 的复杂度不可接受 ( 赛时一直在想优化枚举 x x x 过程但是 gg 考虑优化后半过程在 x x x 一定时 排好序后对于一段 a i a_i ai​ ⌈ a i x ⌉ \left \lceil \frac{a_i}{x} \right \rceil ⌈xai​​⌉ 的值是一定的那么只维护段内最大与次大的 h i h_i hi​ 枚举 j ⌈ a i x ⌉ j\left \lceil \frac{a_i}{x} \right \rceil j⌈xai​​⌉合法的 a i a_i ai​ 范围可以算出来 [ x × ( j − 1 ) 1 , x × j ] [x\times (j-1)1,x\times j] [x×(j−1)1,x×j] 而且这样总复杂度是 O ( n l n ) O(nln) O(nln) 的 对于 h i h_i hi​ 简单的想法是 st 表维护但有更好 (?) 的做法直接维护 [ x × ( j − 1 ) 1 , I N F ] [x\times (j-1)1,INF] [x×(j−1)1,INF] 后缀最大值这样显然是对的但要注意不要重算 这样加速了对于每个 x x x 找最大\次大值 的过程可以通过本题 #includebits/stdc.h using namespace std ;typedef long long LL ; const int N 2e5100 ; int T , n , a[N] , h[N] , Max ; int Sm[N] , Sc[N] , id[N] ; LL ans[N] ;int main() {scanf(%d , T ) ;while( T – ) {scanf(%d , n ) ;for(int i 1 ; i n ; i ) {scanf(%d , h[i] ) ;}int Max 0 ;memset( Sm , 0 , sizeof Sm ) ;memset( Sc , 0 , sizeof Sc ) ;for(int i 1 ; i n ; i ) {scanf(%d , a[i] ) ;Max max( Max , a[i] ) ;if( h[i] Sm[a[i]] ) {Sc[a[i]] Sm[a[i]] ;Sm[a[i]] h[i] ;id[a[i]] i ;}else Sc[a[i]] max( Sc[a[i]] , h[i] ) ;}for(int i Max ; i 1 ; i – ) {if( Sm[i1] Sm[i] ) {Sc[i] Sm[i] ;Sm[i] Sm[i1] ;id[i] id[i1] ;}else Sc[i] max( Sc[i] , Sm[i1] ) ;Sc[i] max( Sc[i] , Sc[i1] ) ;}memset( ans , 0 , sizeof ans ) ;for(int x 1 ; x Max ; x ) {LL Mx 0 , Cx 0 ; int ID1 ;for(int j 1 ; x(j-1)1 Max ; j ) { // 每一段内找 h 最大/次大 即可 if( Mx 1LLSm[x(j-1)1]j ) {if( id[x(j-1)1] ! ID1 ) Cx Mx ;Mx 1LLSm[x(j-1)1]j ;ID1 id[x(j-1)1] ;}else if( ID1 ! id[x*(j-1)1] ) {Cx max( Cx , 1LLSm[x(j-1)1]*j ) ;}Cx max( Cx , 1LLSc[x(j-1)1]*j ) ;}ans[ID1] max( ans[ID1] , Mx-Cx ) ;}for(int i 1 ; i n ; i ) printf(%lld , ans[i] ) ;printf(\n) ;}return 0 ; }