沧州贴吧,宁波seo优化公司排名,企业网站建设新闻发布,公司网页制作哪家强正题 AT1998 [AGC002D] Stamp Rally【Kruskal重构树,倍增】
https://www.luogu.com.cn/problem/AT1998
题目大意
给出nnn个点mmm条边的一张无向图#xff0c;qqq次询问两个人分别从x,yx,yx,y#xff0c;要求总共经过zzz个点的情况下经过边的最大编号的最小值。 1≤n,m,q≤…正题 AT1998 [AGC002D] Stamp Rally【Kruskal重构树,倍增】
https://www.luogu.com.cn/problem/AT1998
题目大意
给出nnn个点mmm条边的一张无向图qqq次询问两个人分别从x,yx,yx,y要求总共经过zzz个点的情况下经过边的最大编号的最小值。
1≤n,m,q≤1051\leq n,m,q\leq 10^51≤n,m,q≤105
解题思路
直接上KruskalKruskalKruskal重构树然后预处理倍增数组和子树大小。
然后二分答案倍增判断就好了这样写是两个log\loglog的直接倍增一个log\loglog也行但是比较麻烦。
时间复杂度O(nlog2n)O(n\log^2n )O(nlog2n) AT1999 [AGC002E] Candy Piles【博弈论】
https://www.luogu.com.cn/problem/AT1999
题目大意
nnn堆糖果第iii堆有aia_iai个有如下操作
取走糖果最多的那堆所有堆中各取走一个
1≤n≤105,1≤ai≤1091\leq n\leq 10^5,1\leq a_i\leq 10^91≤n≤105,1≤ai≤109
解题思路
考虑如果现在操作的那个人一直用第一个操作会输那么它肯定会用第二个操作而此时会转换胜负态那么下一个人也会继续这么做但是如果到最后一个且刚好是偶数那么使用第一个操作就更优。
所以肯定存在一个数iii满足比这个位置大的都是在第二个操作被取走的前的都是第一个位置被取走的。并且最后肯定是第二个操作。如果ai≤ia_i\leq iai≤i那么这个位置肯定是第一个操作被取走的因为在此之前第二个操作不可能多过第一个操作。所以找到第一个aiia_iiaii的位置然后判断即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn)
code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e510;
int n,a[N];
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]);sort(a1,a1n);reverse(a1,a1n);for(int i1;in;i)if(a[i1]i1){if((a[i]-i)1)return puts(First)0;int ri;while(a[r1]i)r;if((r-i)1)return puts(First)0;return puts(Second)0; }return 0;
}AT2000 [AGC002F] Leftmost Ball【dp,组合数学】
https://www.luogu.com.cn/problem/AT2000
题目大意
有nnn种颜色第iii种有kkk个把所有排列中每种颜色的第一个染成同一种新的颜色白色求不同的排列数。
1≤n,k≤20001\leq n,k\leq 20001≤n,k≤2000
解题思路
相当于前缀颜色数小于等于前缀白色数这个复杂度可以考虑平方的dpdpdp。
因为其实和第一个出现的颜色有关我们可以只保留每种颜色的前两个来dpdpdp然后剩下的都插入到它们后面就好了设fi,jf_{i,j}fi,j表示现在有iii个白色出现了jjj种颜色时的方案。
如果填白色就是直接fi−1,jf_{i-1,j}fi−1,j如果填颜色我们可以在剩下的n−j1n-j1n−j1个颜色中选出一个来第二个填在目前的最前面然后现在的空位是n−i−(j−1)×(k−1)−1n-i-(j-1)\times (k-1)-1n−i−(j−1)×(k−1)−1个再填k−2k-2k−2个就好了。
时间复杂度O(n2)O(n^2)O(n2)
code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2100,P1e97;
ll n,k,inv[N*N],fac[N*N],f[N][N];
ll C(ll n,ll m)
{return fac[n]*inv[m]%P*inv[n-m]%P;}
signed main()
{scanf(%lld%lld,n,k);if(k1)return puts(1)0;inv[0]fac[0]inv[1]1;for(ll i2;in*k;i)inv[i]P-inv[P%i]*(P/i)%P;for(ll i1;in*k;i)fac[i]fac[i-1]*i%P,inv[i]inv[i-1]*inv[i]%P;f[0][0]1;for(ll i1;in;i)for(ll j0;ji;j)f[i][j](f[i-1][j]f[i][j-1]*(n-j1)%P*C(n*k-i-(j-1)*(k-1)-1,k-2)%P)%P;printf(%lld\n,f[n][n]);return 0;
}
