【题解】牛客练习赛57

C 题有个输入文件不小心删除了最后一行导致奇怪的问题,向大家道歉,请大力喷我.jpg

有问题请提,我会尽力解答= =

A

模拟。

每组数据时间复杂度
42651533

B

范围较大无法模拟,需要优化。

先忽略玩家血量,怪物被打死时必然是:玩家攻击 次,玩家被怪物攻击 次,怪物回血 次。

找到最小的 判断玩家血量是否足够,注意取整。

每组数据时间复杂度

42651620

C

经典 NPC 问题

状态压缩 DP ,有一个较显然的 做法, 表示装下 这个集合最小需要多少箱子, ,最后判断是否满足 ,但无法通过。

优化:令 分别表示装下 这个集合最少需要多少箱子、最后一个箱子的剩余承重量(可以将 pair<dp1[S],dp2[S]> 理解成 TSP 问题的"距离",by 验题人)。

每组数据时间复杂度

42651549

D

求出每个前缀/后缀的最长回文串长度,枚举分隔点,左边前缀+右边后缀取 max 。

回文自动机:加入每个字符之后,last 结点的 len 即为以当前字符为末尾的最长回文子串长度,正反串各求一次即可。时间复杂度 为字符集大小。

manacher 做法类似但细节较多。

42651553

E

  • 只有子树异或和为 的点才可能对答案产生贡献,其他的点可以不用考虑。

表示以 为根的树删掉偶数/奇数条连向 子树 xor 和为 的儿子 的边,从而划分成奇数/偶数个符合条件的连通块的方案数,转移代码如下:

    ll dpu0 = dp[u][0], dpu1 = dp[u][1];
    dp[u][0] = (dpu0 * dp[v][0] + dpu1 * dp[v][1]) % mod;
    dp[u][1] = (dpu0 * dp[v][1] + dpu1 * dp[v][0]) % mod;

这个做法要额外考虑向父亲的边。应该有更好理解的做法。

每次转移 ,总时间复杂度

42651557

F

易知

可推得

可以分块(设块大小为 ,为了方便计算复杂度假设 )求出不同区间长度的 函数取值,再结合组合数系数得到 的真实值。

具体过程为:预处理出长度是 的倍数的 值,利用 FFT 优化该过程,该部分复杂度 ;查询时结合组合数系数依照 即可 回答单个询问。

最优,时间复杂度

42651646

全部评论
https://www.luogu.com.cn/problem/P3052 为什么原创比赛的题目不是原创题?
4 回复
分享
发布于 2020-04-04 02:49
C题优化前的算法转移方程没懂. 复杂度3^n ,那么就是对于1..n每个集合S都列举了他的子集,但是空集也包含在里面呀,这样取子集中的最小值不是恒等于0了么. 求解大佬
点赞 回复
分享
发布于 2020-01-11 10:52
英特尔
校招火热招聘中
官网直投
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=100; int n,c; ll w; ll a[maxn],b[maxn]; bool dfs( int u ) { if( u==n ) return true; for( int i=0;i<min(c,u+1);i++ ) { if( b[i]+a[u]<=w ) { b[i]+=a[u]; if( dfs(u+1) ) return true; b[i]-=a[u]; } } return false; }  void solve() { cin>>n>>c>>w; memset(b,0,sizeof(b)); for( int i=0;i<n;i++ ) cin>>a[i]; if( dfs(0) ) puts("Yes"); else puts("No"); } int main() { int t; cin>>t; while( t-- ) solve(); return 0; } C题dfs搜 能过 是数据的锅吗
点赞 回复
分享
发布于 2020-01-11 13:48
#include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> #include <queue> #include <map> #include <math.h> #include <set> #include <vector> #include <stack> #define ll long long #define mod 1000000007 const int maxn=1e6+5; const int INF = 0x3f3f3f3f; const int NINF = -INF - 1; using namespace std; int num[100]; int vor[100];//装箱 ll n,m,x,w; ll dfs(ll y) {     if(y==n+1) return 1;     for(ll i=1;i<=min(y,x);i++)     {         if(vor[i]+num[y]<=w)         {          vor[i]=vor[i]+num[y];          if(dfs(y+1)) return 1;          vor[i]=vor[i]-num[y];         }     }     return 0; } int main() {     ll t;     cin>>t;     while(t--)     {         cin>>n>>x>>w;         for(ll i=1;i<=n;i++)         {             cin>>num[i];             if(num[i]>w)             {                printf("No\n");                goto mmp;             }         }         for(ll i=1;i<=x;i++) vor[i]=0;         if(dfs(1)) printf("Yes\n");         else       printf("No\n");         mmp:continue;     }     return 0; } 大佬这个代码和你的一样了,为啥有问题啊..
点赞 回复
分享
发布于 2020-01-16 19:07
C题的T组样例是不是为了卡掉 退火邪教 
点赞 回复
分享
发布于 2020-07-07 10:54

相关推荐

6 收藏 评论
分享
牛客网
牛客企业服务