牛客周赛 Round 12题解，欢迎加QQ号2426751794交流 小美种果树# 二分法，果树的成长公式：day* x+((day+2)/3) * y。也可以直接算。 #include <cstdio> #include <cstring> #include <algorithm> #include <unordered_set> #include <vector> #include <set> #include <queue> #include <iostream> using namespa...

D题解 | #数树# 简单一点的代码，每一层节点数量为n，则这一层增加的完全二叉树的数量是sum = n+n/2+n/2/2+...n/2.../2。 #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <vector> #include <set> #include <queue> #include <iostream> using namespace std; void my_ans(...

A,B,C,D,E,F,G,K,L题解 A题解 | #唯物丁真遇上唯心王源：到了群星就要拿出真本事 贪心，先建立所有bi=1的联通块 1、连通块内的节点是可以互通的不需要传送门，总物质和节点的总和； 2、连通块之间需要传送门联通，贪心选择总物质最大的m个连通块。 O(NlgN)。 #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <unordered_set> #include <vector> #includ...

D题解 | #小美的树上染色# 经典的树形DP 1、以节点1为根节点建树（任何一个节点为根节点都行）； 2、dp[i][0] 表示以节点i为子树根节点时，节点i没有被染色时整个i节点子树可以被染色的最多节点数量；同样 dp[i][1] 表示以节点i为子树根节点时，节点i被染色时整个i节点子树可以被染色的最多节点数量； 3、dp[i][0] 为i节点的所有下级子节点j的最大值总和,为 dp[i][0]=∑max(dp[j][0],dp[j][1])（j为i的下级子节点）； dp[i][1] 为i节点与某一子节点j能够配对的最大值，dp[i][1] = max(dp[i][1], 2+dp[i][...

C题解 | #小美的排列构造# 贪心，可以证明数列n,1,n-1,2,n-2,3...时，权值最小为1（n=2时为0）,直接贪心生成。（PS:评测系统则有问题，需要倒叙输出） #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <unordered_set> #include <vector> #include <set> #include <queue> #include <ios...

B题解 | #小美的排列询问# 模拟，分别从两个方向算出x到y的距离，取最小值，O(n)。 #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <unordered_set> #include <vector> #include <set> #include <queue> #include <iostream> using namespace std; void my_an...

A题解 | #小美的排列询问#扫描一遍数组，判断a[i-1]和a[i]是否为x,y或y,x #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <unordered_set> #include <vector> #include <set> #include <queue> #include <iostream> using namespace std; void my_an...

F题解 | #IUPC# dp题，p = 1<<k, a[t]表示在t时刻可以提交的总题目数。dp[i][j][ij] 表示在时间i时解决j题，在[i-k+1,i]时间内的提交题目的二进制标志是ij。则有 1、ij1 = (ij<<1) % p; 2、 a[i+1] >0 , dp[i][0][0] =1; 3、dp[i+1][j][ij1] = dp[i+1][j][ij1] + dp[i][j][ij]; 4、dp[i+1][j+1][ij1+1] = dp[i+1][j+1][ij1+1] + dp[i][j][ij] * (a[i+1]-j)。 时间复...

1、计算每个数ai分别被2，5整除的次数x,y,则a[x][y]+1； 2、枚举x,y(x,y<32),计算最小值大于等于目标值。 #include <cstdio> #include <cstring> #include <algorithm> #include <unordered_map> #include <vector> #include <set> #include <iostream> using namespace std; void my_ans(){ long long i,j...

#include <cstdio> #include <cstring> #include <algorithm> #include <set> #include <map> #include <vector> #include <iostream> using namespace std; void my_ans(){ long long i,j,n,m,q,aj,t,k,x=-1,y=-1,w,mi,ma,mid, ans = 0; cin>>n; long long b...

L题测试点肯定少了ai =0的情况，发现有些通过的代码，在全0的情况下输出-1.

C题-悲伤的RT，双向队列deque+dp #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <vector> #include <iostream> using namespace std; void my_ans(){ long long i,n,m; cin>>n>>m; long long a[n+1], ans[n+1]; for(i=1;i...

L-最长连续相同字符,分段统计 #include <cstdio> #include <cstring> #include <algorithm> #include <set> #include <vector> #include <iostream> using namespace std; int a[400][400]; int b[400], c[400], a1[400]; int n,n1,last,ans,ansi,ans1=0,ansi1=0; char str[101000]; void count(in...

C题解 |根据连续0或1进行分段，分别枚举1，2，3，4段的情况。 #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <iostream> using namespace std; void my_ans(){ int i,j,n,k; cin>>n>>k; string str; string ans; cin>>str; vect...