牛客练习赛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题

题意： alt 如图，在一个n3的图，图里有m个墙(保证三列都至少有一个墙)，且墙不能穿过。起点终点没有豆子且没有墙，其余地方均只有一个豆子。他们只能往下走或者往右走，问牛牛和他的小伙伴是否能吃到2n个豆，起点在左上角，终点在右下角。

解：题目可以理解为“从起点到终点是否有两条不重合格子的路径”，可以用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;
}