算法组月赛视频讲解

▶ 点击查看讲解视频

---

T1 思路

• $80pts:$ 可以自行随意找一个起点进行模拟，从而判断结果
• $100pts:$ 可以将模拟的范围较小的若干组结果列出查找规律，可以发现如果 $n,m$ 互质，则最终可以挖完所有格子。如果 $n,m$ 有非 $1$ 的公因数 $d$，那么经过 $\frac{n}d\times \frac{m}d$ 天之后又会回到初始点，从而无法遍历完所有的格子。

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

int main (){
	int n, m;
	cin >> n >> m;
	int ans = __gcd(n, m);
	cout << (ans == 1 ? "Yes" : "No");
	return 0;
}

---

T2 思路

• $30\%:$ 使用嵌套循环，在 $O(n^2)$ 逐一判断即可
• $60\%:$ 采用筛法的操作，结合唯一分解定理，在 $O(nlglgn)$ 时间计算出所有的 $f(i)$
• $100\%:$ 不再单独求 $f(i)$，而是考虑每个因数在 $f()$ 中出现的贡献。如 $2$ 在 $f(2),f(4),f(6),f(8)...$ 中都会有 $1$ 的贡献，那么最后所求中因数 $2$ 的总贡献为：$1\times2+1\times4+1\times8...$。

即对于因数 $i$ 而言，在 $f(i),f(2\times i),f(3\times i)...$$f(\lfloor\frac{n}{i}\rfloor\times i)$ 中均有 $1$ 的贡献，最后的总贡献为 $1\times i+1\times 2i+1\times 3i+...$$+1\times \lfloor\frac{n}{i}\rfloor\times i$

即为 $(1+\lfloor\frac{n}{i}\rfloor)\times$ $\lfloor\frac{n}{i}\rfloor /2\times i$

枚举所有因数累加即可，复杂度 $O(n)$

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

int main() {
    long long n, ans = 0; cin >> n;
    for(int i = 1; i <= n; i++)
        ans += (n / i + 1) * (n / i) / 2 * i;
    cout << ans;
}

---

T3 思路

数据范围不大，考虑搜索。

若已知给定的项数，可以先尝试写出相应的搜索代码，其中参数 $x$ 表示准备尝试搜索第 $x$ 项，同时使用数组 $a$ 存储当前结果。因为要求是字典序最小，因此从上一项$+1$ 开始尝试搜索。注意使用辅助数组 $cnt[i]$ 表示数字 $i$ 已能被之前的元素之和表示的方案数以节省判断时间。

当前不明确知晓项数，但项数也并不大，因此再对项数从小到大进行枚举，从而实现最小项数的求解，最小字典序的求解。

#include "bits/stdc++.h"
using namespace std;
const int N = 1005;
int n, m, flag, a[N] = {0, 1}, cnt[N] = {0, 1, 1};
void dfs(int x) {
    if(flag)  return;
    if(x == n + 1) {
        if(a[n] == m) {
            flag = 1;
            for(int i = 1; i <= n; i++) cout << a[i] << " ";
        }
        return;
    }
    for(int i = a[x - 1] + 1; i <= m; i++) {
        if(!cnt[i]) continue;
        a[x] = i;
        for(int j = 1; j <= x; j++)
            cnt[a[j] + i]++;
        dfs(x + 1);
        for(int j = 1; j <= x; j++)
            cnt[a[j] + i]--;
    }
}
int main() {
    cin >> m;
    for(n = 1; ;n++) {
        memset(cnt, 0, sizeof(cnt));
        cnt[2] = 1;
        dfs(2);
        if(flag) return 0;
    }
}

---

T4 思路

• $testcases 1\sim8:$

  先bfs求出任意两点之间的最短距离 $d_{ij}$，枚举 $a,b,c,d\;4$ 个点，求 $max(d_{ab}+d_{bc}+d_{cd})$即可

  复杂度 $O(n^4)$

• $testcases 9\sim10:$

  此为完全图，则答案为 $3$

• $testcases 11\sim15:$

  除了bfs求出任意两点之间的最短距离 $d_{ij}$之外，还需预处理出每个点 $i$ 最远的点、第二远的点、第三远的点，分别为 $f_{i1},f_{i2},f_{i3}$。再枚举 $a,b,c$，则 $d$ 即为$f_{i1},f_{i2},f_{i3}$ 中的一个

  复杂度 $O(n^3)$

• $testcases 16\sim20:$

  与上类似，枚举 $b,c$，则答案一定为 $f_{b1}/f_{b2}/f_{b3}\rightarrow b\rightarrow c$$\rightarrow f_{c1}/f_{c2}/f_{c3}$

复杂度 $O(n^2)$

#include<bits/stdc++.h>
#define ll long long
#define db double
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
int read(){
	int sum=0,f=1;char st=getchar();
	while(st<'0'||st>'9'){
		if(st=='-')f=-1;
		st=getchar();
	}
	while('0'<=st&&st<='9'){
		sum=(sum<<3)+(sum<<1)+st-'0';
		st=getchar();
	}
	return sum*f;
}
const int maxn=4010;
vector<int> a[maxn];
int n,m,v[maxn],d[maxn][maxn];
queue<int>p;
pii ma[maxn][3];
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		int x=read(),y=read();
		a[x].push_back(y),a[y].push_back(x);
	}
	for(int i=1;i<=n;++i){
		int S=i;
		d[i][i]=1,p.push(S);
		while(p.size()){
			int x=p.front();p.pop();
			for(int y:a[x]){
				if(!d[i][y])d[i][y]=d[i][x]+1,p.push(y);
			}
		}
		for(int j=1;j<=n;++j)
			if(d[i][j]>=ma[i][0].fi)ma[i][2]=ma[i][1],ma[i][1]=ma[i][0],ma[i][0]=mp(d[i][j],j);
			else if(d[i][j]>=ma[i][1].fi)ma[i][2]=ma[i][1],ma[i][1]=mp(d[i][j],j);
			else ma[i][2]=max(ma[i][2],mp(d[i][j],j));
		// cout<<"i="<<i<<" ma[i][0].fi="<<ma[i][0].fi<<" ma[i][1].fi="<<ma[i][1].fi<<" ma[i][2].fi="<<ma[i][2].fi<<endl;
	}
	int ans=0;
	for(int i=1;i<=n;++i) // b 
		for(int j=i+1;j<=n;++j){ // c
			int st=0;
			v[i]=1,v[j]=1;
			for(int k=0;k<3;++k)
				if(!v[ma[i][k].se]){st=k;break;}
			v[ma[i][st].se]=1; // 先找与c不同的a 
			for(int k=0;k<3;++k)
				if(!v[ma[j][k].se]){ // 与ab不同的d 
					ans=max(ans,d[i][j]+ma[i][st].fi+ma[j][k].fi);
					break;
				}
			v[ma[i][st].se]=0;
			
			for(int k=0;k<3;++k)
				if(!v[ma[j][k].se]){st=k;break;}
			v[ma[j][st].se]=1; // 先找与b不同的d 
			for(int k=0;k<3;++k)
				if(!v[ma[i][k].se]){ // 与bd不同的a 
					ans=max(ans,d[i][j]+ma[j][st].fi+ma[i][k].fi);
					break;
				}
			v[ma[j][st].se]=0;

			v[i]=v[j]=0;
		}	
	cout<<ans-3<<endl;
	return 0;
}

---