A. 可以发现如果 m≤n! m \le n!m≤n!则取模结果一定为000。剩下的暴力处理即可 #include<bits/stdc++.h> using namespace std; #define int long long int dp[1000005]; int t,m; signed main() { cin>>t>>m; dp[0] = 1; int now = 1; int z = 0; for(int i = 1;i<=1000000;++i) { dp[i] = dp[...

关于 FFF 题exgcdexgcdexgcd过37.5%37.5\%37.5%的情况。如果你的 exgcdexgcdexgcd 模板中带有 ceilceilceil 函数，由于 ceilceilceil 函数返回值为 doubledoubledouble 在本题中可能会爆，所以建议手写 ceilceilceil 函数。否则就会一直 wawawa。 本人 debugdebugdebug 一个多小时血的教训

F. 先考虑第 222 到 n−1n-1n−1 个人 容易发现，到第 iii 个人选择时总共就只有 222 个位置选择，且其中一个是 i+1i+1i+1。 且位置 iii 仅能被 第i−1i-1i−1个人占据，且第i−1i-1i−1个人占据第 iii 个位置的概率为 12\frac{1}{2}21​，而若该位置未被占据第 iii 个人选择这个位置的概率为12\frac{1}{2}21​，则对于任意 2≤i≤n−12\le i \le n-12≤i≤n−1，选择到第 iii 个位置的概率均为14\frac{1}{4}41​。 由于第一个位置不会被人占据，最后一个人仅有 111 个位置可选。则在 ...

G. 设 dpi,jdp_{i,j}dpi,j​ 为考虑前 iii 个 111 交换到第 jjj 个时前iii个 111 均互不相邻的最小操作数。 枚举 jjj 的同时从 j−2j-2j−2 开始往低位转移即可。 时间复杂度 O(n3)O(n^3)O(n3)。 #include<bits/stdc++.h> using namespace std; int dp[505][505]; string s; int a[505]; int b[505]; int n; int main() { cin>>n; cin>>s; s = " ...

A. 按照题意模拟即可 #include<bits/stdc++.h> #define int long long using namespace std; int n,m,k,aa,b; int a[3005]; int t; void solve() { cin>>n; for(int i = 1;i<=n;++i) cin>>a[i]; cin>>aa>>k>>b>>m; for(int i = 1;i<m;++i) for(in...

A. 显然小竹的年龄为  直接输出即可。 #include<bits/stdc++.h> using namespace std; int a,b,x; int main() {     cin>>a>>b>>x;     cout<<(x-b)/a<<'\n';     return 0;   &nbs...

A. 显然小竹的年龄为 直接输出即可。 #include<bits/stdc++.h> using namespace std; int a,b,x; int main() { cin>>a>>b>>x; cout<<(x-b)/a<<'\n'; return 0; } B. 记录每个房间有多少个出口连接记为,每次询问输出即可。 #include<bits/stdc++.h> using namespace std; int cnt[100005]; int n,m,q; int main() {...

C. 考虑贪心,把所有区间丢到优先队列里。左端点小的放在最前面,左端点相同的优先右端点小的。每次从优先队列里取出一个区间,将 xxx赋值给a[l]a[l]a[l],若已经被赋值过了就直接缩小左端点,否则缩小左端点的同时将 x−1x-1x−1,如果左端点大于右端点了,且数量还不能达到要求是输出-1 #include<bits/stdc++.h> using namespace std; int n,m; struct temp{ int l,r,x,y; }; struct node{ int l,r,x,y; bool operator<(const ...

本场由于出题人并没有经验给大家带来了不怎么好的体验，非常抱歉！ A.多米诺骨牌 签到,预处理出从每个位置向左推和向右推能不能推到底 #include<bits/stdc++.h> using namespace std; int f1[200005]; int f2[200005]; int n,a[200005],b[200005]; void solve() { cin>>n; for(int i = 1;i<=n;++i) cin>>a[i]; for(int i = 1;i<=n;++i) cin>&...

E.筑巢 树形dp板子(实际是dfsQAQ) 我实际上是写复杂了只需要1维的树形dp t[now][1]可以用ans = max(ans,t[now][0])替代 t[now][0]以now为根的子树最大舒适度(包含now) t[now][1]以now为根的子树最大舒适度(不包含now) 设son为now的某个子树,若t[now][0]+(now和son边的舒适度)对t[now][0]为正收益则加上,如果是负收益就不加 t[now][0],t[now][1]初始化为a[now](以单结点为联通块的舒适度 t[now][1] = max(t[now][0],t[son][1],t[now][1]...

F.线段树平衡树？太麻烦了,并查集！ 观察可以发现,用乘号连在一起的可以连一条边,加号会分开一个又一个区间使他们互不影响,那就使用乘号连起来的结点合并,将所有数相乘的结果存储在父亲结点,用now[i]表示以i作为父亲结点时该联通块相乘的结果,当改变数x的结果时可以明显发现,改变的值将会被放大now[i]/a[x]倍,那就将所有结果先算出来放在sum里,然后将结果+放大后改变的值就是改变后的sum了 除以用乘法逆元解决,其次注意取余后的sum可能比原值小,需要先+mod%mod否则可能出负数 Code: #include<bits/stdc++.h> #define int long...

F. 使用二分图进行分类讨论 1.如果不是二分图,那么一定是可以通过走染色不了的位置最终到一个结点 2.如果是二分图,那么就需要所有的结点都在一个同一个颜色的结点才有可能走到同一个结点,因为假设有一个人在黑色结点,那么下一步一定会是白色结点.那么他们永远不可能走到同一个色的结点 赛中没想到二分图QAQ,这么明显没想到 Code: #include<bits/stdc++.h> using namespace std; vector<int> edge[200005]; int color[200005]; int n,m,k; int num[200005]; bool...

D. 注意到按位或的特性可以发现,二进制位变成1的位置永远不会变成0,所以可以考虑到,只需要区间内有1个奇数,那么一定就是有趣的奇数 那此时如何统计区间呢 我们之从当前数出发,统计以当前数为左区间的有趣区间数有多少,然后以每个数的奇偶性进行分类讨论 如果当前数为奇数,那么右边所有数以该数为左区间的数一定是有趣的区间 ans+=n-i+1 如果当前数为偶数呢？他只需要包含右边第一个奇数开始就是有趣的区间,先预处理出所有偶数右边的第一个奇数的下标,遇到偶数就加上右边第一个奇数为左区间的区间数 ans+=n-nxt[i]+1 Code: #include<bits/stdc++.h> #...