《牛客算法周周练10》题解
因为代码崩了，先给下代码链接吧。
A:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43962918
B:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43965176
D:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43965712
E:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43963495
F:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43963349
A:签到题
Code
void slove()
{
LL n;sld(n);
if(n == 1) printf("2\n");
else plr(n+n-1);
}
int main()
{
slove();
//system("pause");
return 0;
}B:
考虑i位贡献存在时的最大值。
统计连续的i位贡献存在时的最大值。
为什么是可行的？
首先对于答案满足两点：
1.连续区间.
2.某些位的与运算后的最终值为1.
那么很显然对于答案位为1的值
在这段区间的这些数的这些位的值肯定都是1.
那么显然我只需要统计连续的满足 i位 为1的值即可。
看这个例子。
1 0
1 1
1 1
当我们统计最高位时,因为我们是按从左往右统计(代码中体现).
所以我们一开始选定3个为最优。
但当我们统计最低位时,会选定后两个更优。因为后两个满足最低位都是1.
所以可以发现,这种统计会在一位位统计中统计出最大值且不会遗漏。
也就是说,最优解肯定包含在选择某个位有贡献的连续区间内
Code:
int a[N];
void slove()
{
int n;sd(n);
for(int i=1;i<=n;++i) sd(a[i]);
LL ans = 0;
for(int j=0;j<20;++j)
{
LL tmp = a[1],sum = 0;//tmp赋初值,不然&就都是0.
for(int i=1;i<=n;++i)
{
if((a[i]>>j)&1)//存在时,统计
{
tmp &= a[i];
sum += a[i];
ans = max(ans,tmp*sum);
}
else
{
tmp = a[i+1];//保证下一次&操作时,tmp &= a[i]是它自己,即结果不变.
sum = 0;
}
}
}
plr(ans);
}
int main()
{
slove();
// system("pause");
return 0;
}.
D:
暴搜：
注意题目的限制条件不能改动超过10.
显然这是他给的一个剪枝条件.
考虑对于一个团内的点。
他们都能够有直接相连的边。
那么当两个点有直接相连的边时。
我们假设他们在一个团里。那么显然和他们相连的点都要与两个点都直接相连。
所以我们就去找到某个点，和两个点中一个相连一个不相连。
那么假设这三个点为a,b,c.
显然我们就可以有一种操作：
将任意两点之间的连接状态改变。
那么也可以改变多个边的状态。
但因为一层dfs只算一次步数。所以下次改变要放在下一层搜索中。
所以每次搜完需要边还原。
Code:
int road[105][105],res,ans,n;
void dfs(int step)
{
if(step >= res) return ;
int a,b,c,f = 0;
for(int i=1;i<=n;++i)
{
if(f) continue;
for(int j=i+1;j<=n;++j)
{
if(f || road[i][j] == 0) continue;
for(int k=1;k<=n;++k)
{
if(f) break;
if(i == k || j == k) continue;
if(road[i][k]^road[j][k])
{
a = i,b = j,c = k;
f = 1;
}
}
}
}
if(!f)
{
ans = min(ans,step);
return ;
}
road[a][b] ^= 1,road[b][a] ^= 1;//a,b改动。连-断。断-连.
dfs(step+1);
road[a][b] ^= 1,road[b][a] ^= 1;//边还原
road[a][c] ^= 1,road[c][a] ^= 1;//a,c改动
dfs(step+1);
road[a][c] ^= 1,road[c][a] ^= 1;
road[b][c] ^= 1,road[c][b] ^= 1;//b,c改动.
dfs(step+1);
road[b][c] ^= 1,road[c][b] ^= 1;//这里也要还原,因为应该消除对上层搜索的影响.
}
void slove()
{
int t,cnt = 0;sd(t);
while(t--)
{
ans = INF;
sd(n);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) sd(road[i][j]);
res = 11;
dfs(0);
printf("Case #%d: %d\n",++cnt,ans == INF ? -1 : ans);
}
}
int main()
{
slove();
//system("pause");
return 0;
}E：
从题意可见要最大化最短跳跃距离.
那么考虑二分最短跳跃距离。
当距离 < 最短距离时就移去石头.
当移去的时候 <= m,说明满足。继续二分。
Code:
LL d[N];
int L,n,m;
bool check(LL x)
{
int pa = 0,pb = 1,num = 0;
while(pb <= n+1)
{
if(d[pb]-d[pa] >= x) pa = pb,pb++;
else num++,pb++;
}
return num <= m;
}
void slove()
{
sddd(L,n,m);
for(int i=1;i<=n;++i) sld(d[i]);
d[0] = 0,d[n+1] = L;
LL L = 0,r = INF,ans;
while(L < r)
{
LL mid = L+r>>1;
if(check(mid)) L = mid+1,ans = mid;
else r = mid;
}
plr(ans);
}
int main()
{
slove();
// system("pause");
return 0;
}F:
很显然如果我们知道每条边被覆盖几次就可以排序后贪心给值。
那么就有
第一种思路：直接枚举所有的链，树上差分统计每条边被覆盖几次。
但是这样复杂度N^2.显然会T。
第二种思路：
树形dp.
dp[i]表示i点下向存在的边数。
那么对于边u->v被覆盖的情况。
1.u->v为链的终边。
显然方案数为n-2+1.
因为任何一条其他边都可以到u->v,然后加上本身。
2.u->v为链的中间边。
显然方案数为v点下面的边数*其他的边数。
Code:
vector<int> G[N];
int dp[N],n;//i点向下的存在的边数.
vector<LL> T;
void dfs(int u,int fa)
{
for(auto v:G[u])
{
if(v == fa) continue;
dfs(v,u);
dp[u] += dp[v]+1;
LL t = n-1;//以u-v这条边为终点边.
t += (1LL*n-2-dp[v])*dp[v];//以u-v这条边为中间边
T.pb(t);
}
}
void slove()
{
sd(n);
for(int i=1;i<n;++i)
{
int u,v;sdd(u,v);
G[u].pb(v),G[v].pb(u);
}
dfs(1,0);
sort(T.begin(),T.end());
LL tmp = n-1,ans = 0;
for(int i = 0;i < T.size();++i)
{
ans += T[i]*tmp;
tmp--;
}
plr(ans);
}
int main()
{
slove();
// system("pause");
return 0;
}
查看9道真题和解析
