网易笔试 0923

记错了开考时间导致三点10分才开始答题。时间不够了，就AC了前三道，第四题全输出1骗了14.29%。

第一题给定一个长度为n的数组下标从0到n-1，然后第 i 和第(i+2)%n可以交换，问任意次交换后，能否使得数组不严格单调递增。

方法是先判n是否是奇数，是奇数那所有位置之间都可以交换，为Yes，为偶数就是分奇数位和偶数位排序然后比较是否后一位大于前一位。

#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
const int N = 1e5 + 20;

int n;
int a[N], b[N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		cin >> n;
		for (int i = 0; i < n; ++i)
			cin >> ((i + 1) % 2 ? a[i / 2] : b[i / 2]);
		if (n % 2)
		{
			puts("YES");
			continue;
		}
		sort(a, a + n / 2);
		sort(b, b + n / 2);
		int flag = 1;
		for (int i = 0; i < n / 2 - 1; ++i)
			if (a[i] > b[i] || a[i + 1] < b[i])
			{
				flag = 0;
				break;
			}
		if (a[n / 2 - 1] > b[n / 2 - 1])
			flag = 0;
		puts(flag ? "YES" : "NO");
	}
	return 0;
}

第二题给n个字符串，问有多少组字符串是类似的。“类似的”的定义是各个字母出现个数相同。比如aabbd和abadb

方法是哈希，然后在处理第i个字符串时，统计之前有多少字符串是与其类似的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 19260817;
const ll INF = 1e18 + 7;

int n;
ll ans;
string s;
map<ll, int> mp;
int a[30];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	while (n--)
	{
		cin >> s;
		for (auto p : s)
			++a[p - 'a'];

		ll tot = 0;
		for (int i = 0; i <= 25; ++i)
			tot = (tot * MOD + a[i]) % INF;
		if (mp.count(tot))
			ans += mp[tot], ++mp[tot];
		else
			mp.insert({tot, 1});

		for (auto p : s)
			--a[p - 'a'];
	}
	cout << ans << endl;
}

第三题问给定数组的所有子序列平均数之和。

方式是算每个数字对结果的贡献，比如[1,2,3,4]。1贡献为1的有一个,[1]。1贡献为1/2的有三个，[1,2],[1,3],[1,4]。1贡献为1/3的有3个，贡献为1/4的有1个。就是C^{i}_{n-1} / i+1，其中 i 从1遍历到n-1。然后 p / q 要转变成 p * q ^ {MOD - 2} 。

#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;
const int N = 1e5 + 20;

int n;
int a[N];

ll qpow(ll x, ll y)
{
    ll res = 1;
    while(y)
    {
        if(y&1) res=res*x%INF;
        x=x*x%INF;
        y>>=1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    ll tot = 0;
    for(int i=1;i<=n;++i)
    {
        cin >> a[i];
        tot += a[i];
    }
    tot %= INF;
    ll val = 1, sum = 1, up = n - 1, down = 1;
    for(int i=2;i<=n;++i)
    {
        sum = sum * up % INF;
        sum = sum * qpow(down, INF - 2) % INF;
        up--;
        down++;
        // cout << sum << ' ' << sum * 1.0 / i << endl;
        val = (val + sum * qpow(i, INF - 2) % INF) % INF;
    }
    cout << val * tot % INF << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

第四题是给定一棵n个节点的树，q次询问。每次询问一个点集，问多少个简单路径可以覆盖该点集。

受HDU5758启发。每次询问的时候构建一个虚树，答案为(虚树叶子数目+1)/2。如果根只有一个儿子时，也视为一个叶子。因为叶子不可能被不为它为端点的简单路径覆盖，所以叶子必定要是简单路径端点之一。