算法和计算复杂度（问题A01-A05/B01-B04）
总结
题单（问题A01-A05/B01-B04）
主要是简单题，但是很多题都是可以以更优的时间复杂度通过的
A05 - Three Cards
本题 $O(n^2)$ 即可通过（甚至$O(n^3)$也可以卡过），这里我们用一种$O(n)$的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void solve()
{
int n,k;
cin>>n>>k;
ll ans=0;
for(int i=1;i<=n;i++){
int rest = k - i;
if (rest < 2) break;
int min_val = max(1LL, rest - n);
int max_val = min(n, rest - 1);
if (min_val <= max_val) {
ans += max_val - min_val + 1;
}
}
cout<<ans<<endl;
}
|
事实上可以$O(1)$，但是代码过于繁琐，详见
B03 - Supermarket 1
本题$O(n^3)$ 可通过，这里用了$O(n^2)$ 的做法，但是额外消耗了$O(n^2)$ 的空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| unordered_set<int> sum[2010];
void solve()
{
int n;cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
vector<int> ex(2010);
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
ex[a[i]+a[j]]++;
sum[a[i]+a[j]].insert(i);
sum[a[i]+a[j]].insert(j);
}
}
for(int i=0;i<n;i++){
//保证a[i]不在已经被选的两个中
if(ex[1000-a[i]]>0&&sum[1000-a[i]].find(i)==sum[1000-a[i]].end()){
cout<<"Yes\n";
return ;
}
}
cout<<"No\n";
}
|