牛客周赛 Round 78

A 时间表查询！

看看比赛时间就过了

B 一起做很甜的梦！

我们需要构造一个长n的序列，满足任意一个长度小于n的连续子序列都不能构成一个排序。换句话说，当且仅当连续子序列长度为n时才能构成一个排序。发现任何一个长度小于n的连续子序列都不可能同时包含位置1和n上的数。而构成一个序列又需要同时包含1和2这两个数，所以我们只需要将1和2放在位置1和n上就构造出了满足条件的序列。

int solve()
{
  int n; cin >> n;
  for(int i=1;i<=n;i++) a[i] = i;
  swap(a[n],a[2]);
  for(int i=1;i<=n;i++) cout << a[i] << ' ';
}

C 翻之

让我们求最多能得到多少全为1的列。我们先单独拎出两列来看，如果他们要同时满足全为1，就必须满足这两列一模一样。如果有一行上的元素不同：1和0，我们对这一行操作是不可能将其同时变为1的。所以题目就变成求出最多相同的列有几个了。对于比较列是否相同有很多种方法，我采用的是将每一列都转化为字符串再进行比较。

int a[N][N];
int c[N];
unordered_map<int,int> mp;

void solve()
{
	int n, m; cin >> n >> m;
	for(int i=1;i<=n;i++)
	{
		string s; cin >> s;
		for(int j=1;j<=m;j++) a[i][j] = s[j-1] - '0';
	}
	for(int i=1;i<=m;i++)
	{
		int x = 0;
		for(int j=1;j<=n;j++)
		{
			x *= 2;
			x += a[j][i];
		}
		c[i] = x;
	}
	for(int i=1;i<=m;i++) mp[c[i]] ++;
	int maxx = 0;
	for(auto &e : mp) maxx = max(maxx, e.second);
	cout << maxx << '\n';
}

D 乘之

这题非常有意思~~赛时是真的没想到~~。对于一个已选区间[L,R],如果其左边区间的元素之和是大于（或等于）0的，那么小龙会选，否则小蛇会选。右边同理。所以我们惊奇地发现，无论如何都会选到全部区间。

void solve()
{
    // woc 这么短就做出来了
	int n, k; cin >> n >> k;
	for(int i=1;i<=n;i++) cin >> a[i];
    int res = 0;
    for(int i=1;i<=n;i++) res += a[i];
    cout << res * k << '\n';
}

E 在树上游玩

开始以为很难，其实好好读题目会发现这就是一道dfs，而且并不复杂。统计一下有多少个连通块，输出这些连通块连接的白色节点数的乘积就好了(mod 1e9+7)。

int dfs(int u)
{
    int res = 0;
    st[u] = 1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j = e[i];
        if(a[j] && !st[j]) res += dfs(j);
        else if (!a[j]) res ++;
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int res = 1;
    int n, k; cin >> n >> k;
    memset(h, -1, sizeof h);
    for(int i=1;i<=k;i++)
    {
        int t; cin >> t;
        a[t] = 1;
    }
    for(int i=1;i<n;i++)
    {
        int u, v; cin >> u >> v;
        add(u, v), add(v, u);
    }
    for(int i=1;i<=n;i++)
    {
        if(!st[i] && a[i])
        {
            int t = dfs(i);
            res = (long long)res * t % mod;
            cnt ++;
        }
    }
    if(res == 0) cnt = 0;
    cout << cnt << ' ' << res;
}