社区讨论

AC了但有疑问

bbyk_ALEX
P15288「YLLOI-R3-T3」龙卷风参与者 3已保存回复 28

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
28 条
当前快照
1 份
快照标识符
@mljeqywv
此快照首次捕获于
2026/02/12 20:01
7 天前
此快照最后确认于
2026/02/15 12:15
4 天前
查看原帖
为啥两份代码明明差不多，一份赛时代码，一份赛后代码，改变的仅仅是遍历方式，赛后代码却 AC 了，而赛时代码仅仅 60 分。why？
赛时代码：
CPP
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
//const int maxa = 1e6 + 5;
int t, n, m;
int a[maxn];
int gcd(int a1, int b1){
	if(a1 % b1 == 0){
		return b1;
	}
	return gcd(b1, a1 % b1);
}
unordered_map<int, int> mp;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while(t--){
        mp.clear();
		long long ans = 0;
		cin >> n >> m;
		for(int i = 1; i <= n; i++){
			cin >> a[i];
			mp[a[i]]++;
		}
		for(int k = 1; k <= m; k++){
			bool flag = true;
			int gs = gcd(n, k);
			for(int i = 1; i <= n; i++){
				if(mp[a[i]] % (n / gs) != 0){
					flag = false;
					break;
				}
			}
			if(flag){
             //   cout << k << '\n';
				ans++;
			}
		}
		cout << ans << '\n';
	}
	return 0;
}
赛后代码：
CPP
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
//const int maxa = 1e6 + 5;
int t, n, m;
int a[maxn];
int gcd(int a1, int b1){
	if(a1 % b1 == 0){
		return b1;
	}
	return gcd(b1, a1 % b1);
}
unordered_map<int, int> mp;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while(t--){
        mp.clear();
		long long ans = 0;
		cin >> n >> m;
		for(int i = 1; i <= n; i++){
			cin >> a[i];
			mp[a[i]]++;
		}
		for(int k = 1; k <= m; k++){
			bool flag = true;
			int gs = gcd(n, k);
			for(auto i : mp){
				if(i.second % (n / gs) != 0){
					flag = false;
					break;
				}
			}
			if(flag){
             //   cout << k << '\n';
				ans++;
			}
		}
		cout << ans << '\n';
	}
	return 0;
}
两份代码复杂度应该都是 O(nm)O(nm)，第二份代码是不是没被卡掉？

回复

共 28 条回复，欢迎继续交流。

正在加载回复...