序列嵌套

题解

如果直接枚举 $i,j$ 是平方的复杂度，我们改变思路，先利用排序或者 $map$ 找出相等的 $A_i$ 和 $B_k$ ，再处理每个 $B_k$ 能否找到对应的 $C_j$ 即可。

时间复杂度为 $O(n)$ 。

标准代码

C++ 11

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxN = 100010;
ll M[maxN], B[maxN];
int main() {
    ios::sync_with_stdio(false);
	ll N, m, x, c = 0;
	cin >> N;
	for (m = N; m--;)
		cin >> x, ++M[x];
	for(int i = 0; i < N; i++)
		cin >> B[i];
	while (N--) cin >> x, c += M[B[--x]];
	cout << c;
}

最小的公倍数小题

题解

$2,3,5,7$ 的最小公倍数是 $210$ ，因此当 $L < =2$ 时，需要输出 - $1$ ， $L=3$ 时，答案就是 $210$

对于大于 $3$ 的 $L$ ，我们考虑如何构造一个答案。

由于题目要求找到最小的，并且最终的结果一定是 $210$ 的倍数，因此一定不论 $L$ 有多大，一定满足以下条件:

$1.$ 第一位是 $1$ 。(为了构造最小)

$2.$ 除了最后 $3$ 位，其余数字都是 $0$ (这样才是最小)

$3.$ 最后一位是 $0$ (因为是 $210$ 的倍数)。

我们先求出 $1...0$ (共 $L$ 位)这个数对 $210$ 取模的结果 $m$ ，用 $210-m$ 就是最后 $3$ 位数字，其余位置首位为 $1$ ，其余为 $0$ 。

标准代码

C++ 11

#include<cstdio>
int i, p, n;
int main() {
	scanf("%d", &n);
	if (n <= 3)printf("%d\n", n <= 2 ? -1 : 210);
	else {
		printf("1");
		for (p = 50, i = 1; i <= n - 4; ++i)
			printf("0"), p = p * 10 % 210;
		printf("%03d\n", p);
	}
}

选点

题解

本题思路为二分答案，先对 $m$ 个区间按照左端点排序。

然后二分这个最远距离 $D$ ，枚举 $m$ 个区间进行验证，看是否能否放下 $n$ 个点即可。

标准代码

C++ 11

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define INF 2000000000
#define FF first
#define SS second
int n, m;
vector<pair<LL, LL>> intervals;

bool ok(LL d) {
    LL prev = -1LL * INF * INF;
    int cnt = 0;
    for (auto& i : intervals) {
        while (max(prev + d, i.FF) <= i.SS) {
            prev = max(prev + d, i.FF);
            cnt++;
            if (cnt >= n) break;
        }
        if (cnt >= n) break;
    }
    return (cnt >= n);
}

int main() {
    cin >> n >> m;
    intervals.resize(m);
    for (int i = 0; i < m; ++i)
        cin >> intervals[i].FF >> intervals[i].SS;

    sort(intervals.begin(), intervals.end());
    LL lo = 1;
    LL hi = 1LL * INF * INF;
    LL res = -1;
    while (lo <= hi) {
        LL mid = (lo + hi) / 2;

        if (ok(mid)) {
            res = mid;
            lo = mid + 1;
        }
        else {
            hi = mid - 1;
        }
    }
    cout << res << "\n";
}

划分数组

题解

我们考虑 $DP$ ， $DP[i][j]$ 表示前 $i$ 个数恰好分为 $j$ 段的方案数。记录前缀和，根据前缀和模 $j$ 同余进行状态转移，模 $j$ 同余的前缀和最坏情况下有 $n$ 个，因此时间复杂度为 $O(n^3)$ 。

考虑优化，设 $sum_{b[1]}$ 与 $sum_{b[2]} \dots sum_{b[k]}$ 模 $j$ 同余，我们考虑计算 $sum_{b[k-1]}$ 时已经对 $sum_{b[1]}$ 这些前缀做过求和了，因此利用 $dp$ 的前缀和优化，可以 $O(1)$ 计算每个状态的结果，这样时间复杂度为 $O(n^2)$ 。

标准代码

C++ 11

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
int n, t[3010][3010], f[3010]; ll a[3010];
int main() {
	cin >> n; t[1][0] = 1;
	for (int i = 1; i <= n; i++) {
		cin >> a[i], a[i] += a[i - 1];
		for (int j = 1; j <= i; j++)f[j] = t[j][a[i] % j];
		for (int j = 1; j <= i; j++)(t[j + 1][a[i] % (j + 1)] += f[j]) %= mod;
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)(ans += f[i]) %= mod;
	return printf("%d", ans), 0;
}

huhe与FGQ

题解

就是KMP嘛！！！ 题意：已知一个字符串，求其中形如A+B+A子串的数量 ，且要求B不为空且A的长度大于等于k KMP,暴力 首先暴力枚举每个子串，对于每个字串来说，它的next显然满足A的性质 而next[next[i]]也满足条件 所以要尽量去满足条件，即找到大于等于k的最小的next[next[...]]。 采用类似路径压缩，找出后统计答案。

标准代码

C++ 11

#include<bits/stdc++.h>
using namespace std;
const int N=15005;
int nex[N],ans,s,dp[N];
void KMP(char st[]){
	int n=strlen(st+1);
	int k=0;
	nex[1]=0;
	memset(dp,0,sizeof(dp));
	for(int i=2;i<=n;i++){//枚举右端点i,求next数组 
		while(k&&st[k+1]!=st[i])k=nex[k];
		if(st[k+1]==st[i])k++;
		nex[i]=k;
		if(dp[k]){dp[i]=dp[k];}//如果还有更小的，就找最小的next 
		else{
			if(k>=s){dp[i]=k;}//如果达到了限制条件 
			else{dp[i]=0;}
		}
		if(dp[i]&&2*dp[i]+1<=i)ans++;//统计答案 
	}
}
char st[N];
int main(){
	scanf("%s",st+1);
	scanf("%d",&s);
	int n=strlen(st+1);
	for(int i=0;i<=n;i++)KMP(st+i);//枚举左端点，进行KMP 
	printf("%d",ans);
}