挑战赛 #16 全题解！

复仇者_帅童

2025-03-23 23:12:38

发布于：广东

55阅读

0回复

0点赞

终于 AK 了一次挑战赛，不容易啊...

T1

个人难度：红中位

如果按照题意直接模拟的话，那么就会每个数都会有 $101$ 种情况，需要运算 $101^5\approx1.05\times 10^{10}$ 次，肯定会 TLE。

注意到 $i,j,k,z,p$ 都是非负整数，

所以 $8\times i\le x,6\times j\le x,4\times k\le 10,2\times z\le 10,p\le 10$ ，

即 $i\le 1,j\le 1,k\le 2,l\le 5,p\le 10$ 。

按照上面这个范围去循环判断即可，运算次数为 $2\times 2\times 3\times 6\times 11=792$ ，可以通过。

#include <iostream>
#include <cstdio>
using namespace std; 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for(int i = 0; i <= 1; i++){
		for(int j = 0; j <= 1; j++){
			for(int k = 0; k <= 2; k++){
				for(int l = 0; l <= 5; l++){
					for(int m = 0; m <= 10; m++){//枚举
						if(8 * i + 6 * j + 4 * k + 2 * l + m == n){//判断
							cout << i << ' ' << j << ' ' << k << ' ' << l << ' ' << m << '\n';
						}
					}
				}
			}
		}
	}

	return 0;
}

时间复杂度： $O(1)$ 。

T2

个人难度：橙下位

模拟，筛出 $n$ 以内的所有质数，一个一个累加即可。（如果不会埃式筛等筛法，使用 $O(n\sqrt n)$ 的暴力找质数也是能通过的。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
bool vis[200005];
int n, ans;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	vis[0] = vis[1] = 1;
	for(int i = 2; i * i <= n; i++){//埃式筛
		if(vis[i]) continue;
		for(int j = i * 2; j <= n; j += i) vis[j] = 1;
	}
	for(int i = 2; i <= n; i++){
		if(!vis[i]){
			string tmp = to_string(i);//直接转换成字符串加
			for(char c:tmp) ans += c - '0';
		}
	}
	cout << ans % 1093;//别忘了取模！

	return 0;
}

时间复杂度： $O(n\log\log n)$ （感觉埃式筛的复杂度更高，后面计算的就舍去了）

T3

个人难度：橙中位

显然题目是想让我们找出 $A,B$ 的所有公因数。

显然 $A,B$ 的所有公因数就是 $A,B$ 最大公因数的所有因子。所以我们就可以通过这个方法轻松找出了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
vector <int> v;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;
	int ans = __gcd(n, m);//求最大公因数
	for(int i = 1; i * i <= ans; i++){
		if(ans % i == 0){//如果能被整除就说明有两个因子
			cout << i << ' ';
			v.push_back(ans / i);
		}
	}
	if(v.back() * v.back() == ans) v.pop_back();//注意判断完全平方数的情况，不能重复输出
	reverse(v.begin(), v.end());//反转
	for(int i:v) cout << i << ' ';

	return 0;
}

时间复杂度： $O(\sqrt N)$ 。

T4

个人难度：黄上位

$O(n^3)$ 的解法是个人都会，所以我来教大家一个 $O(n^2\log n)$ 的解法。

思考一下如果一个三角形是直角三角形，那它得满足什么？

有直角。
符合勾股定理（即存在两边的平方和等于第三边）。

性质 2 想不出来怎么优化，所以我考虑性质 1。

注意到在平面直角坐标系内，如果一个角是直角，它的两边的解析式分别为 $y=k_1x+b_1,y=k_2x+b_2(k_1,k_2\not= 0)$ ，则有 $k_1\times k_2=-1$ 。如果两边解析式分别为 $y=b_1$ 和 $x=b_2$ ，也可以构成直角。

我们可以先预处理出每个边的解析式的 $k$ 值，然后枚举每个顶点，计算它们作为直角顶点的个数，这个个数就是这个图内直角三角形的个数。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
int a[100005], b[100005], ans;
pair <int, int> mp[1505][1505];
int ct[1505];
int n;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> b[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
        	if(i == j) continue;
            int den = a[i] - a[j], num = b[i] - b[j];//用分数表达解析式
            if(den == 0) num = 1;//与 x 轴平行，k 用 0/1 表示
            else if(num == 0) den = 1;//与 y 轴平行，k 用 1/0 表示
            else{
                if(den < 0) den = -den, num = -num;//保证分母为正
                int gcd = __gcd(abs(den), abs(num));
                den /= gcd, num /= gcd;//约分
            }
            mp[i][++ct[i]] = {num, den};
        }
    }
    for(int i = 1; i <= n; i++){
    	sort(mp[i] + 1, mp[i] + ct[i] + 1);//聚集相等元素，以便计算
	}
    for(int i = 1; i <= n; i++){
    	for(int j = 1; j <= ct[i]; j++){
    		int den, num;
    		if(mp[i][j].second == 0) num = 0, den = 1;
    		if(mp[i][j].first == 0) num = 1, den = 0;
			else{
				den = -mp[i][j].first, num = mp[i][j].second;//计算与这条线垂直的线段的解析式
				if(den < 0) den = -den, num = -num;
			}
			auto idx1 = lower_bound(mp[i] + 1, mp[i] + ct[i] + 1, make_pair(num, den));//寻找在同一个点且与之垂直的线段
    		auto idx2 = upper_bound(mp[i] + 1, mp[i] + ct[i] + 1, make_pair(num, den));
    		ans += idx2 - idx1;
		}
    }
    cout << ans / 2;//加了两边，要除 2
    
    return 0;
}

时间复杂度： $O(n^2\log n)$ 。

T5

个人难度：黄中位

比 T4 简单。

简单的并查集板子题，参考 01迷宫_信奥算法普及/提高--ACGO题库。不做详细解释。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int a[1005][1005];
int father[1000005], size[1000005];
bool vis[1000005];
vector <int> v;
int n, m;
int find(int n){return (father[n] == n ? n : father[n] = find(father[n]));}//查找父亲节点
void merge(int x, int y){//合并
	int n = find(x), m = find(y);
	if(n == m) return;//如果不判断是否在同一集合会使size的值重复加
	father[min(n, m)] = max(n, m);
	size[max(n, m)] += size[min(n, m)];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
			father[(i - 1) * m + j] = (i - 1) * m + j;//初始化
			size[(i - 1) * m + j] = 1;
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(i > 1 && (~a[i][j] & 8) && (~a[i - 1][j] & 2)){//如果这格的北方无墙且上一格的南方无墙就说明可以到达
				merge((i - 1) * m + j, (i - 2) * m + j);//和上方合并
			}
			if(j > 1 && (~a[i][j] & 1) && (~a[i][j - 1] & 4)){//如果这格的西方无墙且左一格的东方无墙就说明可以到达
				merge((i - 1) * m + j, (i - 1) * m + j - 1);//和左方合并
			}
		}
	}
	for(int i = 1; i <= n * m; i++){
		if(!vis[find(i)]){
			vis[find(i)] = 1;
			v.push_back(size[find(i)]);//记录大小
		}
	}
	sort(v.begin(), v.end(), greater <int>());//从大到小排序
	for(int i:v) cout << i << ' ';
	

	return 0;
}

时间复杂度： $O(N\times M\log (N\times M))$ 。

T6

个人难度：黄上位

首先来一个正常的 DP：

$dp[i][j]$ 记录在第 $i$ 格，当 $l=j$ 时收集宝石的最大值。

显然递推式如下：

$dp[i][j]=max(dp[i-j][j-1],dp[i-j][j],dp[i-j][j+1])+b_i$

其中 $b_i$ 为第 $i$ 格的宝石数，并且要保证 $i-j\ge m$ 。

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
int a[5005], b[5005], dp[5005][5005];
int n, m, mx;
signed main(){
	memset(dp, -64, sizeof(dp));
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i], b[a[i]]++;
	dp[m][m] = b[m];
	for(int i = m + 1; i <= 5000; i++){
		for(int j = 1; j <= i - m; j++){
			dp[i][j] = max(max(dp[i - j][j - 1], dp[i - j][j]), dp[i - j][j + 1]) + b[i];
			mx = max(mx, dp[i][j]);
		}
	}
	cout << mx;

	return 0;
}

时间复杂度： $O(a_i\times (a_i-d))$ 。

得分： $70pts$ 。

这对于 $a_i\le 3\times 10^4$ 的数据还是太吃操作了，怎么优化呢？

注意到在 $3\times 10^4$ 格内，跳跃过程中 $l$ 的取值范围很小，一定在 $d\pm 300$ 的范围内，也就是说上面的 $dp$ 存在大量无效状态。

根据上面的推理，我们可以把 $dp$ 的第二维的大小减少到 $601$ ， $dp[i][j]$ 表示第 $i$ 格，当 $l=j+d-301$ 时收集宝石的最大值。将上面的状态转移方程稍加改变即可。

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
int a[30005], b[30005], dp[30005][615];
//(d-300)~(d+300) 
int n, m, mx;
signed main(){
	memset(dp, -64, sizeof(dp));
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i], b[a[i]]++;
	dp[m][301] = b[m];
	for(int i = m + 1; i <= 30000; i++){
		for(int j = 1; j <= 601; j++){
			int realj = j + m - 301;
			if(realj < 1 || realj > i) continue;
			dp[i][j] = max(max(dp[i - realj][j - 1], dp[i - realj][j]), dp[i - realj][j + 1]) + b[i];
			mx = max(mx, dp[i][j]);
		}
	}
	cout << mx;

	return 0;
}

时间复杂度： $O((a_i-d)\times \sqrt{a_i})$ 。

得分： $100pts$ 。

有帮助，赞一个

去预览

0/2000

全部评论 5

M97星云-李灵晟
普及+/提高
现有N个位置的数组a

$a1,a2,a3……an$

ai表示第i个位置硬币状态1->正
q次操作
操作1：格式 : 1 x y
输出 x~y正面数量
操作2：格式： 2 x y
将第x至第y个翻转
输入n,q;
输入数组初始状态（0，1）；
输入操作；
样例1：
输入
3 2
0 1 1
2 1 2
1 1 3
输出：
2
对于20%数据：n<=1000,q<=1000
对于40%数据：n<=10 0000,q<=10 0000
另有10%数据：n<=100 0000,无操作2
另有10%数据：n<=100 0000,操作2有x=y
另有10%数据：n<=100 0000,操作1有x=y
100%数据：n<=100 0000,q<=150 0000

2025-03-26 来自北京
0
- 复仇者_帅童
  回复M97星云-李灵晟
  注意到20+40+10+10+10=100，所以可以暴力（？
  
  2025-03-26 来自广东
  0
- 复仇者_帅童
  回复M97星云-李灵晟
  但是不如传奇根号算法，你知道的（
  
  2025-03-26 来自广东
  0
- 复仇者_帅童
  回复复仇者_帅童
  好吧加起来是90（
  
  2025-03-26 来自广东
  0
M97星云-李灵晟
？？？

2025-03-26 来自北京
0
亚洲卷王 AK IOI
并查集不是 $\alpha(n)$ ？

2025-03-23 来自北京
0
- 复仇者_帅童
  回复亚洲卷王 AK IOI
  没按秩合并就是 $O(\log N)$ ，具体见 OI Wiki
  
  2025-03-23 来自广东
  0
- 亚洲卷王 AK IOI
  回复复仇者_帅童
  ok
  
  2025-03-23 来自北京
  0
亚洲卷王 AK IOI
%%%%%%

2025-03-23 来自北京
0
复仇者_帅童
顶

2025-03-23 来自广东
0

T1

T2

T3

T4

T5

T6

全部评论 5

热门讨论