上海网站建设 网页做,长乐区建设局网站,公众平台登录官网,wordpress权限管理C - Folia
不难想到自底向上确定树的形态。可能要多尝试一下
一开始想错了好几个地方#xff0c;服了
假设某一层有XXX个节点#xff0c;那么上一层可能有⌈X2⌉,⌈X2⌉1,...,X\lceil\frac{X}{2}\rceil,\lceil\frac{X}{2}\rceil1,...,X⌈2X⌉,⌈2X⌉1,...,X个节点服了
假设某一层有XXX个节点那么上一层可能有⌈X2⌉,⌈X2⌉1,...,X\lceil\frac{X}{2}\rceil,\lceil\frac{X}{2}\rceil1,...,X⌈2X⌉,⌈2X⌉1,...,X个节点不包括叶子节点那么我们可以很容易的递推求出每一层的[li,ri][l_i,r_i][li,ri]表示这一层点数的取值范围。但是并不是每一层的rir_iri都是能取到的因为ri≤2ir_i\le 2^iri≤2i而且2i2^i2i比较大不太好处理。
基于上述两个理由我们考虑自顶向下确定每一层点的取值每一层贪心取最大点数即可。并且可以证明答案不会超过long long
#includebits/stdc.h
#define ll long long
#define pb push_back
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
int n,a[100005];
ll l[100005],r[100005],res1;
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinn;for(int i0;in;i)cina[i];if(na[0]){cout-1;return 0;}l[n]r[n]a[n];for(int in-1;i0;i--){l[i]a[i](l[i1]1)/2;r[i]a[i]r[i1];}if(l[0]1){cout-1;return 0;} ll X1;for(int i1;in;i){Xmin(r[i],2*(X-a[i-1]));if(Xl[i]){cout-1;return 0;}resX;}coutres;
}D - Urban Planning
对于给定的{pi}\{p_i\}{pi}贡献就是nnn减去连通块的个数。
笑死然而还是不会做
注意到{pi}\{p_i\}{pi}对应导出的图是一个基环树森林因此环的数目等于连通块的数目要算所有情况下环数目的和可以对于每个环单独考虑它出现次数的方案数。该死为什么我这一步都没转化出来就像计数了啊
然后先考虑pi−1p_i-1pi−1的情形。不过这道题的突破口好像不在这里因为随便用组合数算算没啥难度
还是要考虑题目给定的{pi}\{p_i\}{pi}长什么样子。奇怪啊竟然要对这一点特别提出来考虑 我们发现其给出的图一定是由若干内向基环树和内向树构成 刚开始把内向树想成链了真是奇怪。假设有MMM个基环树那么对答案造成的贡献是固定的M(N−1)KM(N-1)^KM(N−1)K假设有K′KK′个内向树那么只有根节点指向的边不是固定的注意我们的目标还是数环。
为什么题解的式子这么简洁
定义环上的关键点为内向树的根节点以及pi−1p_i-1pi−1的那些点。记这些点为{ai}\{a_i\}{ai}子树大小为{bi}\{b_i\}{bi}那么方案数为(n−1)!(N−1)K−n∏bi(n-1)!(N-1)^{K-n}\prod b_{i}(n−1)!(N−1)K−n∏bi其中nnn表示环上的点数。不难证明这个计数方式不重不漏。
复杂度O(n2)O(n^2)O(n2)。代码非常简单只需要一个简单的背包即可。
#includebits/stdc.h
#define ll long long
using namespace std;
const int mod1e97;
int n,m,K,fa[5005],p[5005],sz[5005],vs[5005];
ll fac[5005],F[5005],dp[5005],res;
int find(int x){return fa[x]x?x:fa[x]find(fa[x]);
}
int main(){cinn;for(int i1;in;i)fa[i]i,sz[i]1;fac[0]F[0]1;for(int i1;in;i)fac[i]fac[i-1]*i%mod,F[i]F[i-1]*(n-1)%mod;for(int i1;in;i){cinp[i];K(p[i]-1);if(~p[i]){int ufind(i),vfind(p[i]);if(u!v){fa[u]v,sz[v]sz[u];}else{vs[u]1,m;}}}dp[0]1;for(int i1;in;i){if(fa[i]i){if(!vs[i]){res(res(sz[i]-1)*F[K-1])%mod;for(int jn;j1;j--){dp[j](dp[j]dp[j-1]*sz[i])%mod;}}else{res(resF[K])%mod;}}}for(int i2;iK;i){if(dp[i]){res(resfac[i-1]*dp[i]%mod*F[K-i])%mod;}}cout(F[K]*n-resmod)%mod;
}E - Binary Programming
姑且先把这套题做着吧其他的题也没精力翻了
考虑倒着做然后贪心 这个过程中可能会产生一堆假做法但是不要慌张 。
我企图直接贪心然而产生了错误我是joker这里数据删除了
从何贪起呢我们观察到111一定是放在最后删的事实上这也是一个非常显然的结论。另一个观察我没有注意到那就是无论怎么操作相邻两个111对答案的贡献都是一样的因此我们考虑把相邻的111删去这样就不存在相邻的111了 。
然后就非常好搞了。设某个111前面000的个数为xxx后面000的个数为yyy那么对于奇数位上的111贡献最大是⌊x2⌋1y\lfloor\frac{x}{2}\rfloor1y⌊2x⌋1y对于偶数位上的111贡献最大是⌊x−12⌋1y\lfloor\frac{x-1}{2}\rfloor1y⌊2x−1⌋1y显然这是可以取到的。
复杂度O(n)O(n)O(n)。
做这种题比较爽的地方是只要有了正确的思路就很好搞不然就会有很多种情况
#includebits/stdc.h
#define ll long long
using namespace std;
int n;
ll res,zero,one,sum;
char s[200005];
int main(){scanf(%s,s1),nstrlen(s1);for(int i1;in;i)sum(s[i]0);for(int i1;in;i){if(s[i]0){zero;}else{one;if(i1ns[i1]1){ressum1;one;i;}else{if(one1)reszero/21sum-zero;else res(zero-1)/21sum-zero;}}}for(int i1;ione;i){resi/2;}coutres;
}F - Sorting Game
该死看到后面把前面的操作忘了直接把Snuke\text{Snuke}Snuke的操作搞忘了怪不得做不出来先数据删除一波
一看到这个邻值交换就感到非常亲切序列{ai}\{a_i\}{ai}合法等价于对于任意ijijij从高往低位找到第一个ci1,cj0c_i1,c_j0ci1,cj0时其后面数位上的数完全相同。
嗯读错题过后少考虑了一些因素反而有帮助
但是这个限制显然不能拿来直接计数。因为是平时训练题所以也懒得打表
到这里能发散的点还是挺多的直接猜结论可能不一定会导向正确的方向
这题好做的原因可能还是在于没有什么特殊的限制因此大胆猜测最终dpdpdp式子并不复杂
观察这个限制有点像数位dpdpdp。那么最基础的想法就是从高到低位考虑打个表观察一下于是不难发现这个想法的动机 然而这不是我最初的思路。。。 对于ijijijaia_iai和aja_jaj的最高位分别是111,000那么其剩余的数位一定完全相同。首先我们要知道对于不存在子串101010的情况其方案数等价于dpn,m−1dp_{n,m-1}dpn,m−1。其中dpn,mdp_{n,m}dpn,m表示nnn个数mmm个数位的方案数。
另一方面如果存在这样的i,ji,ji,j我们猜测可以把i,ji,ji,j以及它之间的东西一起压缩掉变成同一个数假设中间有KKK个位置最高位不确定那么剩下的方案数就是dpn−K−1,m−1dp_{n-K-1,m-1}dpn−K−1,m−1 。中间KKK个数最高位可以任取方案数2K2^K2K。于是留给了我们一个艰巨的任务证明这样的方案数是等价的。
至于这么压缩为什么是等价的可以先写代码验证一番 或者更严谨地因为后面数位的数都是复制粘贴所以可以只保留i,ji,ji,j两个数因为不存在101010所以都只能比后j−1j-1j−1位于是就是等价的。
综上所述dpn,m(n1)×dpn,m−1∑k0n−2dpn−k−1,m−1×2k×(n−k−1)dp_{n,m}(n1)\times dp_{n,m-1}\sum_{k0}^{n-2}dp_{n-k-1,m-1}\times 2^k\times (n-k-1)dpn,m(n1)×dpn,m−1∑k0n−2dpn−k−1,m−1×2k×(n−k−1)。
利用换元把式子写成dpn,m(n1)×dpn,m−1∑k1n−1dpk,m−1×2n−1−k×kdp_{n,m}(n1)\times dp_{n,m-1}\sum_{k1}^{n-1}dp_{k,m-1}\times 2^{n-1-k}\times kdpn,m(n1)×dpn,m−1∑k1n−1dpk,m−1×2n−1−k×k 就可以O(1)O(1)O(1)转移了。
复杂度O(nm)O(nm)O(nm)。
#includebits/stdc.h
#define ll long long
using namespace std;
const int mod1e97;
int n,m;
ll dp[5005][5005],sum[5005][5005],F[5005],F2[5005];
int main(){cinmn;F[0]1;for(int i1;in;i)F[i]F[i-1]*2%mod;F2[0]1;for(int i1;in;i)F2[i]F2[i-1]*(mod1)/2%mod;for(int j1;jm;j){dp[0][j]1;for(int i1;in;i){if(j1){dp[i][j]((i1)*dp[i][j-1]sum[i-1][j-1]*F[i-1])%mod;}else{dp[i][j]F[i];}sum[i][j](sum[i-1][j]dp[i][j]*F2[i]%mod*i)%mod;}}coutdp[n][m];
}
