【LGR-298-Div.2】洛谷 8 月月赛 III IXOI Round 2 记录

【LGR-298-Div.2】洛谷 8 月月赛 III IXOI Round 2A#includeiostream #includecstring #includevector #includecmath #includemap #includealgorithm using namespace std; long long n; int main() { ios::sync_with_stdio(0); cin.tie(0); cinn; coutn/2; return 0; }显然∀ a ≤ ⌊ n ⌋ 即 2 a n , a g c d ( a , 2 a ) , 所以可以产生 \forall a\le\lfloor n \rfloor 即 2an ,agcd(a,2a),所以可以产生∀a≤⌊n⌋即2an,agcd(a,2a),所以可以产生∀ a ⌊ n ⌋ , 在 1 ∼ n 中只有一个它的倍数 , 所以无法产生 \forall a\lfloor n \rfloor,在1∼n中只有一个它的倍数,所以无法产生∀a⌊n⌋,在1∼n中只有一个它的倍数,所以无法产生。最终数量即为⌊ n ⌋ \lfloor n \rfloor⌊n⌋。B#includeiostream #includecstring #includevector #includecmath #includemap #includealgorithm using namespace std; int n; long long ansa,ansb; long long a[1000005]; struct node{long long x,y;} f[1000005]; long long gcd(long long a,long long b) { if(b0) return a; return gcd(b,a%b); } int main() { ios::sync_with_stdio(0); cin.tie(0); cinn; for(int i1;in;i) cina[i]; f[1](node){1ll*a[1],1ll}; for(int i2;in;i) { if(1ll*a[i]*(f[i-1].y1)f[i-1].xa[i]) f[i](node){a[i],1}; else f[i](node){f[i-1].xa[i],f[i-1].y1}; } for(int i2;in;i) { if(f[i].x0) f[i](node){f[i-1].xa[i],f[i-1].y1}; } ansa1; for(int i1;in;i) { if(f[i].x!0f[i].x*ansbansa*f[i].y) ansaf[i].x,ansbf[i].y; // coutansa ansb\n; } long long tmpgcd(ansa,ansb); coutansa/tmp ansb/tmp; return 0; }正经做法注意到这个区间只包含一个非零数所以只要对每一个数向两边拓展即可。不正经做法定义f[i]为以i为末尾信息密度最低区间g[i]为以i为末尾信息密度不为零的最低区间。f [ i ] m i n ( a [ i ] , f [ i − 1 ] a [ i ] l e n [ i − 1 ] 1 ) f[i]min(a[i],\frac{f[i-1]a[i]}{len[i-1]1})f[i]min(a[i],len[i−1]1f[i−1]a[i]​)g [ i ] m i n ( a [ i ] ( a [ i ] ̸ 0 ) , f [ i − 1 ] a [ i ] l e n [ i − 1 ] 1 ) g[i]min(a[i](a[i] \not0),\frac{f[i-1]a[i]}{len[i-1]1})g[i]min(a[i](a[i]0),len[i−1]1f[i−1]a[i]​)最后只需要统计g中非0最小值即可。C#includeiostream #includecstring #includevector #includecmath #includemap #includealgorithm using namespace std; int n,q,r; vectorint g[1000005]; int siz[1000005]; int f[1000005]; int maxs[1000005]; void dfs(int u,int fa) { siz[u]1; for(int v:g[u]) { if(vfa) continue; dfs(v,u); siz[u]siz[v]; maxs[u]max(maxs[u],siz[v]); } } int main() { ios::sync_with_stdio(0); cin.tie(0); cinnqr; for(int i1,u,v;in;i) { cinuv; g[u].push_back(v); g[v].push_back(u); } dfs(r,-1); for(int i0;in;i) f[i]maxs[i]n-siz[i]; for(int i1;in;i) f[i]max(f[i-1],f[i]); f[n]n; while(q--) { int x; cinx; coutlower_bound(f,fn,x)-f\n; } return 0; }考虑若使数i不在数组T里H最多能容纳多少个点。显然i不能选不在它子树中的点的公共祖先不会是i如果在它子树中必定得在同一子树中否则存在两点公共祖先为i。所以最多容纳s i z [ i ] s i z [ s o n [ i ] ] siz[i]siz[son[i]]siz[i]siz[son[i]]个点。s o n sonson为重儿子把它记录到数组中在做前缀max然后对每次询问二分查找即可。D#includeiostream #includecstring #includevector #includecmath #includemap #includealgorithm using namespace std; int n; int ans; const int mod1000000007; int a[8008]; int f[2][8005][3]; int main() { ios::sync_with_stdio(0); cin.tie(0); cinn; for(int i1;in;i) cina[i]; f[0][0][0]1; int nw1; for(int i1;in;i,nw1-nw) { for(int j0;jn;j) { f[nw][j][0](0llf[1-nw][j][0]f[1-nw][j][1]f[1-nw][j][2])%mod; if(j0) f[nw][j][1](0llf[1-nw][j-1][0](ij)*f[1-nw][j-1][1])%mod*1ll*a[i]%mod; // for(int k2,x1ll*a[i]*a[i]%mod;kj;k,x1ll*x*a[i]%mod) // { // f[i][j][2](0llf[i][j][2]1ll*f[i-1][j-k][0]*x%mod)%mod; // } if(j2) f[nw][j][2](1ll*f[nw][j-1][2]*a[i]%mod1ll*f[1-nw][j-2][0]*a[i]%mod*a[i]%mod)%mod; } } nw1-nw; ans(0llf[nw][n][0]f[nw][n][1]f[nw][n][2])%mod; coutans; return 0; }注意力不够惊人注意到一个序列为愚蠢的序列的充要条件为所有数之和为n;任意大于1的数的左右必须是0;两个连续的1一定没有被操作过⟺ \iff⟺∀ p i p i 1 1 , ∑ j 1 i p [ i ] i \forall p_ip_{i1}1,\displaystyle\sum^{i}_{j1} p[i]i∀pi​pi1​1,j1∑i​p[i]i。 没注意到定义f [ i ] [ j ] [ 3 ] f[i][j][3]f[i][j][3]为前i ii个数和为j jj,第i ii个数等于0f [ i ] [ j ] [ 0 ] f[i][j][0]f[i][j][0],等于1f [ i ] [ j ] [ 1 ] f[i][j][1]f[i][j][1]或大于1f [ i ] [ j ] [ 2 ] f[i][j][2]f[i][j][2]可以得到的本质不同的愚蠢序列的权值和。可以得到转移方程f [ i ] [ j ] [ 0 ] f [ i − 1 ] [ j ] [ 0 ] f [ i − 1 ] [ j ] [ 1 ] f [ i − 1 ] [ j ] [ 2 ] f [ i ] [ j ] [ 1 ] ( f [ i − 1 ] [ j − 1 ] [ 0 ] { f [ i − 1 ] [ j − 1 ] [ 1 ] if i j 0 if i ̸ j ) × x [ i ] f [ i ] [ j ] [ 2 ] ∑ k 2 j f [ i − 1 ] [ j − k ] [ 0 ] × x [ i ] k f[i][j][0]f[i-1][j][0]f[i-1][j][1]f[i-1][j][2] \newline f[i][j][1]\Bigg(f[i-1][j-1][0]\begin{cases}f[i-1][j-1][1]\text{if }ij\\0\text{if }i\not j\end{cases}\Bigg)\times x[i]\newline f[i][j][2]\displaystyle\sum^{j}_{k2} f[i-1][j-k][0] \times x[i]^kf[i][j][0]f[i−1][j][0]f[i−1][j][1]f[i−1][j][2]f[i][j][1](f[i−1][j−1][0]{f[i−1][j−1][1]0​ifijifij​)×x[i]f[i][j][2]k2∑j​f[i−1][j−k][0]×x[i]k现在可以用一个三重循环解决问题要达到O ( n 2 ) \Omicron(n^2)O(n2)需要优化f [ i ] [ j ] [ 2 ] f[i][j][2]f[i][j][2]。可以发现在i ii相同j jj只增加1时 f [ i ] [ j ] [ 2 ] f[i][j][2]f[i][j][2]非常类似。具体来说f [ i ] [ j ] [ 2 ] ∑ k 2 j f [ i − 1 ] [ j − k ] [ 0 ] × x [ i ] k f [ i − 1 ] [ j − 2 ] [ 0 ] × k 2 k ∑ k 3 j f [ i − 1 ] [ j − k ] [ 0 ] × x [ i ] k − 1 f [ i − 1 ] [ j − 2 ] [ 0 ] × k 2 k f [ i ] [ j − 1 ] [ 2 ] f[i][j][2]\displaystyle\sum^{j}_{k2} f[i-1][j-k][0] \times x[i]^k f[i-1][j-2][0]\times k^2k\displaystyle\sum^{j}_{k3} f[i-1][j-k][0] \times x[i]^{k-1}f[i-1][j-2][0]\times k^2kf[i][j-1][2]f[i][j][2]k2∑j​f[i−1][j−k][0]×x[i]kf[i−1][j−2][0]×k2kk3∑j​f[i−1][j−k][0]×x[i]k−1f[i−1][j−2][0]×k2kf[i][j−1][2]这样就可以优化到O ( n 2 ) \Omicron(n^2)O(n2)。然后发现空间会爆所以把第一维滚动掉即可。