牛客练习赛89题解
A题
题意：n个格子，每个格子都有2^(n-1)个米粒，有些格子坏掉了，问从（n-k）个格子中选择一些格子能否正好凑成s。
解：二进制考虑，如果当然s的某一位是1，那么表示对应的格子应该选择，0表示不应该被选择，模拟一遍即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
set<ll>se;
ll n,k,s,a[100];
void solve()
{
scanf("%lld%lld%lld",&n,&k,&s);
ll t = 1;
while(s)
{
if(s & 1) se.insert(t);
s /= 2,t++;
}
for(int i = 1;i <= k; ++i)
{
ll x;
scanf("%lld",&x);
if(se.find(x) != se.end())
{
printf("NO\n");
return;
}
}
printf("YES\n");
}
int main()
{
solve();
return 0;
}
B题
题意：给出cocacola的一个同构异序词，问最少交换多少次字母位置可以得到cocacola
解：因为字符串很小，并且是一定有解的，直接暴力搜索方案即可，枚举当前位置是否符合，不符合的话从后面找一个符合的字符交换。
#include<bits/stdc++.h>
using namespace std;
struct node
{
string y;
int ct;
};
queue<node> q;
unordered_map<string,int> mp;
void solve()
{
node s;
s.ct = 0;
cin >> s.y;
++mp[s.y];
q.push(s);
while(1)
{
s = q.front();q.pop();
if(s.y == "cocacola")
{
cout << s.ct << '\n';
return;
}
for(int i = 0; i < 8; ++i)
for(int j = i + 1; j < 8; ++j )
{
node ss = s;
swap(ss.y[i],ss.y[j]);
ss.ct++;
if(mp.find(ss.y) == mp.end()) q.push(ss), ++ mp[ss.y];
}
}
}
int main()
{
solve();
return 0;
}
C题
题意：
解：题目可以理解为“从起点到终点是否有两条不重合格子的路径”，可以用2次搜索解决。
但是由于只有3列，可以讨论一下无解的情况有哪些， 显然第一步路径1走到（1，2），路径2走到（2，1），最后一步路径1一定是从（n-1，3）走到了 （n，3），路径2一定是从（n，2）走到（n，3） 所以对于路径1，一定是从第一列往下走，然后在合适的位置向右走一步向下走到底，同时，在路径1往右走的时候，路径2一定已经转移到了第3列，否则就会有重复格子出现。
代码：l1、l2分别记录路径1、2向右走的时间（即第1、2列的第一堵墙），r1、r2表示第2、3列的最后一堵墙，保证l1-r1>=2,l2-r2>=2即可保证路径12都可正常通过。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m, x, y;
int l1, r1, l2, r2;
bool in[N];
void solve()
{
scanf("%d %d", &n, &m);
l1 = n; r1 = 1;
l2 = n; r2 = 1;
while(m--)
{
scanf("%d %d", &x, &y);
if (x == 1) l1 = min(l1, y);
if (x == 2) r1 = max(r1, y), l2 = min(l2, y);
if (x == 3) r2 = max(r2, y);
}
if (l1 - r1 >= 2 && l2 - r2 >= 2) printf("YES");
else printf("NO");
}
int main()
{
solve();
return 0;
}
D题
题意：给你n个点，f函数的值，构造一棵树，一个度数为k的点有f(k)点贡献，求最大贡献。
解：每个节点的度数是1/0（除了根以外都有1个父亲结点）+儿子结点个数
先构造一颗所有点都连向1的数（1为根节点），先不计算根节点的贡献，答案就是(n-1)*f(1)
之后考虑把一些点移到其他点的儿子中，设为1的儿子有i个时的最大贡献，那么每次可以以x的代价制造f(x+1)-f(1)点贡献（x<i，将1的x个儿子移到某个点的儿子中，该点度数从1变为了x+1，贡献为f(x+1)-f(1)）
从小到大枚举可以做到每种贡献可以选无限个（完全背包）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 10100
int n;
ll ans,f[N],a[N];
int main()
{
cin>>n;
for(int i=1;i<n;++i) cin>>a[i];
memset(f,0,sizeof(f));
f[n - 1] = a[1] * (n - 1);
for(int i = 1;i < n - 1;++i)
for(int j = n - 1 - i;j > 0;--j)
f[j] = max(f[j],f[j + i] + a[i + 1] - a[1]);
for(int i = 1;i <= n - 1;++i)
ans = max(ans,f[i] + a[i]);
cout<<ans<<'\n';
return 0;
}
远景公司福利 157人发布