【LGR-298-Div.2】洛谷 8 月月赛 III & IXOI Round 2
A
#include<iostream> #include<cstring> #include<vector> #include<cmath> #include<map> #include<algorithm> using namespace std; long long n; int main() { ios::sync_with_stdio(0); cin.tie(0); cin>>n; cout<<n/2; return 0; }显然，∀ a ≤ ⌊ n ⌋ 即 2 a < n , a = g c d ( a , 2 a ) , 所以可以产生 \forall a\le\lfloor n \rfloor 即 2a<n ,a=gcd(a,2a),所以可以产生∀a≤⌊n⌋即2a<n,a=gcd(a,2a),所以可以产生，
∀ a > ⌊ n ⌋ , 在 1 ∼ n 中只有一个它的倍数 , 所以无法产生 \forall a>\lfloor n \rfloor,在1∼n中只有一个它的倍数,所以无法产生∀a>⌊n⌋,在1∼n中只有一个它的倍数,所以无法产生。
最终数量即为⌊ n ⌋ \lfloor n \rfloor⌊n⌋。
B
#include<iostream> #include<cstring> #include<vector> #include<cmath> #include<map> #include<algorithm> 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(b==0) return a; return gcd(b,a%b); } int main() { ios::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; f[1]=(node){1ll*a[1],1ll}; for(int i=2;i<=n;i++) { if(1ll*a[i]*(f[i-1].y+1)<f[i-1].x+a[i]) f[i]=(node){a[i],1}; else f[i]=(node){f[i-1].x+a[i],f[i-1].y+1}; } for(int i=2;i<=n;i++) { if(f[i].x==0) f[i]=(node){f[i-1].x+a[i],f[i-1].y+1}; } ansa=1; for(int i=1;i<=n;i++) { if(f[i].x!=0&&f[i].x*ansb<ansa*f[i].y) ansa=f[i].x,ansb=f[i].y; // cout<<ansa<<" "<<ansb<<"\n"; } long long tmp=gcd(ansa,ansb); cout<<ansa/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] \not=0),\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
#include<iostream> #include<cstring> #include<vector> #include<cmath> #include<map> #include<algorithm> using namespace std; int n,q,r; vector<int> 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(v==fa) 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); cin>>n>>q>>r; for(int i=1,u,v;i<n;i++) { cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } dfs(r,-1); for(int i=0;i<n;i++) f[i]=maxs[i]+n-siz[i]; for(int i=1;i<n;i++) f[i]=max(f[i-1],f[i]); f[n]=n; while(q--) { int x; cin>>x; cout<<lower_bound(f,f+n,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
#include<iostream> #include<cstring> #include<vector> #include<cmath> #include<map> #include<algorithm> using namespace std; int n; int ans; const int mod=1000000007; int a[8008]; int f[2][8005][3]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; f[0][0][0]=1; int nw=1; for(int i=1;i<=n;i++,nw=1-nw) { for(int j=0;j<=n;j++) { f[nw][j][0]=(0ll+f[1-nw][j][0]+f[1-nw][j][1]+f[1-nw][j][2])%mod; if(j>0) f[nw][j][1]=(0ll+f[1-nw][j-1][0]+(i==j)*f[1-nw][j-1][1])%mod*1ll*a[i]%mod; // for(int k=2,x=1ll*a[i]*a[i]%mod;k<=j;k++,x=1ll*x*a[i]%mod) // { // f[i][j][2]=(0ll+f[i][j][2]+1ll*f[i-1][j-k][0]*x%mod)%mod; // } if(j>=2) f[nw][j][2]=(1ll*f[nw][j-1][2]*a[i]%mod+1ll*f[1-nw][j-2][0]*a[i]%mod*a[i]%mod)%mod; } } nw=1-nw; ans=(0ll+f[nw][n][0]+f[nw][n][1]+f[nw][n][2])%mod; cout<<ans; return 0; }注意力不够惊人
注意到一个序列为愚蠢的序列的充要条件为：
- 所有数之和为n;
- 任意大于1的数的左右必须是0;
- 两个连续的1一定没有被操作过⟺ \iff⟺∀ p i = p i + 1 = 1 , ∑ j = 1 i p [ i ] = i \forall p_i=p_{i+1}=1,\displaystyle\sum^{i}_{j=1} p[i]=i∀pi=pi+1=1,j=1∑ip[i]=i。 （
没注意到）
定义f [ i ] [ j ] [ 3 ] f[i][j][3]f[i][j][3]为前i ii个数，和为j jj,第i ii个数等于0（f [ i ] [ j ] [ 0 ] f[i][j][0]f[i][j][0]）,等于1（f [ i ] [ j ] [ 1 ] f[i][j][1]f[i][j][1]），或大于1（f [ 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 }i=j\\0&\text{if }i\not =j\end{cases}\Bigg)\times x[i]\newline f[i][j][2]=\displaystyle\sum^{j}_{k=2} 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]0ifi=jifi=j)×x[i]f[i][j][2]=k=2∑jf[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}_{k=2} f[i-1][j-k][0] \times x[i]^k = f[i-1][j-2][0]\times k^2+k\displaystyle\sum^{j}_{k=3} f[i-1][j-k][0] \times x[i]^{k-1}=f[i-1][j-2][0]\times k^2+kf[i][j-1][2]f[i][j][2]=k=2∑jf[i−1][j−k][0]×x[i]k=f[i−1][j−2][0]×k2+kk=3∑jf[i−1][j−k][0]×x[i]k−1=f[i−1][j−2][0]×k2+kf[i][j−1][2]
这样就可以优化到O ( n 2 ) \Omicron(n^2)O(n2)。
然后发现空间会爆，所以把第一维滚动掉即可。
