I A B E M 题解

I 逃离虫洞

题意: 对字符串按给定变换规则进行重排, 问周期是多长? 即从给定串开始, 重排几次会回到给定串?

我们发现从给定位置$qq$出发, 进行若干次变换后必定回到原来的位置(试试证明这一点?), 那么从$qq$出发到回到$qq$所经过的这些位置构成一个"环", 整个串必定会被分解为若干个不相交的环. 计算每个环的回归周期, 求最小公倍数即为原问题的解. 环的周期即为最小循环节的长度, 例如

abbabb ->
babbab ->
bbabba ->
abbabb (回归) 周期 = 3 = len(abb) (循环节长度)

求循环节长度我能想到的办法就是从小到大枚举每个可能的长度, 然后取前缀进行kmp匹配, 再检验, 可以只对环长的因子长度的前缀进行匹配, 这样每个测例总的复杂度是$O(n\sqrt{n})O(n\; \backslash sqrt\; n)$. 代码:

#include <bits/stdc++.h>
using namespace std;

vector<bool> kmp(const string &text, const string &pattern)
{
	vector<bool> res(text.size());
	int pi[400];
	pi[0] = 0;
	for(int i = 1; i < pattern.size(); i++){
		int j = pi[i - 1];
		while(j > 0 && pattern[j] != pattern[i])
			j = pi[j - 1];
		if(pattern[j] == pattern[i]) j++;
		pi[i] = j;
	}

	int last = 0;
	for(int i = 0; i < text.size(); i++){
		int j = last;
		while(j > 0 && pattern[j] != text[i])
			j = pi[j - 1];
		if(pattern[j] == text[i]) j++;
		last = j;
		if(last == pattern.size())
			res[i - pattern.size() + 1] = true;
	}

	return res;
}

// 获取循环节长度
int getLen(const string &s)
{
	int n = s.size();
	vector<int> divisors;

	for(int i = 1; i*i <= n; i++){
		if(n % i == 0){
			divisors.push_back(i);
			if(i != n / i) divisors.push_back(n / i);
		}
	}

	sort(divisors.begin(), divisors.end());

	for(auto div: divisors){
		string pattern = s.substr(0, div);
		auto mat = kmp(s, pattern);
		bool flag = true;
		for(int i = 0; i < mat.size(); i += div){
			if(!mat[i]){
				flag = false;
				break;
			}
		}
		if(flag) return div;
	}
	return -1919810;
}

long long gcd(long long a, long long b)
{
    if(b == 0) return a;
    return gcd(b, a % b);
}

int main(void)
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int cNum;
	cin >> cNum;

	while(cNum--){
		int n;
		string s;
		vector<int> trans;
		cin >> n;
		cin >> s;
		trans.resize(n);
		for(int i = 0; i < n; i++){
			cin >> trans[i];
			trans[i]--;
		}

		long long T = 1;
		vector<bool> isv(n);
		for(int q = 0; q < n; q++){
			int j = q;
			string cir;
			do{
				cir.push_back(s[j]);
				isv[j] = true;
				j = trans[j];
			}while(j != q);
			int t = getLen(cir);
			T = (T*t) / gcd(T, t);
		}

		cout << T << '\n';
	}

	return 0;
}

这道题赛时没写出来, 结束前5分钟才想到思路.

A 八卦消息

考虑动态规划, 令$dp[i][d]dp[i][d]$表示第$ii$天时, 还能将这个八卦分享$dd$天的人的数量(注意, 这里的数量统计不包含知道八卦但是还没开始分享的人). dp的维护有两点, 一是$dp[i]dp[i]$左移一位加到$dp[i+1]dp[i+1]$里, 这很好理解, 因为过了一天后, 原本能分享$xx$天的人只能分享$(x-1)(x-1)$天了. 第二是把$dp[i]dp[i]$的总和$ss$(不包括$dp[i][0]dp[i][0]$)加到$dp[i+d1][d2-d1]dp[i\; +d1][d2\; -\; d1]$上, 因为第$ii$天这些人分享到了$ss$个新人, 这$ss$个人在第$(i+d1)(i+d1)$天才开始传八卦. 取答案要把$dp[n]dp[n]$累加起来, 然后往后找到所有的$dp[k][d2-d1]dp[k][d2-d1]$累加起来, 因为第$nn$天仅仅知道而还没有开始分享的人必定在之后某一天开始分享, 剩下天数是最大的.

代码

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define MOD 1000000007

int dp[3100][1020];

signed main(void)
{
    int n, d1, d2;
    cin >> n >> d1 >> d2;
    d2 = d2 - d1;
    dp[1 + d1][d2] = 1;
    for(int i = 1; i <= n; i++){
        int sum = 0;
        for(int j = 0; j <= 1005; j++){
            dp[i + 1][j] += dp[i][j + 1];
            dp[i + 1][j] %= MOD;
        }
        for(int j = 1; j <= 1005; j++){
            sum += dp[i][j];
            sum %= MOD;
        }

        dp[i + d1][d2] += sum;
        dp[i + d1][d2] %= MOD;
    }

    int ans = 0;
    for(int j = 1; j <= 1005; j++){
        ans += dp[n][j];
        ans %= MOD;
    }
    for(int i = n + 1; i <= n + 10 + d1; i++){
        ans += dp[i][d2];
        ans %= MOD;
    }
    ans = (ans + MOD) % MOD;
    cout << ans << '\n';
    return 0;
}

B 花圃喷灌

清新脱俗的题目(?). 首先注意到图形的比例是固定的, 这就意味着答案就是把输入乘上一个系数再出来, 也意味着你搞出答案之后可以对着样例去检验, 只要精度够了就不会错. 至于算的话, 先令$a=1a\; =\; 1$, 记圆心为$OO$, 记圆弧上的动点为$PP$, $\overrightarrow{OP}\backslash overrightarrow\; \{OP\}$可以由$\alpha \backslash alpha$角表示出来, $\alpha \backslash alpha$角是$\overrightarrow{OP}\backslash overrightarrow\; \{OP\}$与$\overrightarrow{AB}\backslash overrightarrow\; \{AB\}$方向的夹角. $\overrightarrow{DO}\backslash overrightarrow\; \{DO\}$, $\overrightarrow{DM}\backslash overrightarrow\; \{DM\}$都很好算, 这样就可以把$\mathrm{\mid }\overrightarrow{PM}\mathrm{\mid }|\backslash overrightarrow\{PM\}|$用$\alpha \backslash alpha$角表示出来, 写成函数用程序枚举求最值. 求最值也不需要什么特殊的迭代法, 给出$\alpha \backslash alpha$的区间嗯for循环, 确定大致范围, 然后缩小范围缩小步长, 精度来个7 8位应该就够了.

E 搬货物

考虑二分答案, 原问题问的是给定最大搬货次数, 要最小化体力值. 那么转换成给定一个体力值$midmid$, 在这个体力值限制下看看需要搬多少次, 如果次数没有超就证明是可行的.

代码

#include <bits/stdc++.h>
using namespace std;

#define int long long

// 保证limit >= max(arr)
int tt(const vector<int> &arr, int limit)
{
    int t = 1;
    int cur = 0;
    for(int i = 0; i < (signed)arr.size(); i++){
        if(cur + arr[i] > limit){
            t ++;
            cur = arr[i];
        }else{
            cur += arr[i];
        }
    }
    
    return t;
}

signed main(void)
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);


    int n, t;
    cin >> n >> t;
    vector<int> arr(n);
    for(int i = 0; i < n; i++) cin >> arr[i];
    int L = *max_element(arr.begin(), arr.end()), R = 40000100;
    while(L < R){
        int mid = (L + R) / 2;
        if(tt(arr, mid) <= t){
            R = mid;
        }else{
            L = mid + 1;
        }
    }
    cout << L << '\n';
    return 0;
}

M 网络线路

我的做法是开26张图, 每张图嗯bfs n次(题目边数范围没给, 我就赌它是稀疏图), 如果边数打满的话应该是会T掉的.