2 solutions
2024-02-17 18:38:20
发布于:广东
6阅读
0回复
0点赞
The first method is to exceed the memory limit.Recommend using the second
method.
1st method:
#include <bits/stdc++.h>
using namespace std;
using P = pair<long long, long long>;
P operator+(P a, P b){
return {a.first + b.first, a.second + b.second};
}
P operator-(P a, P b){
return {a.first - b.first, a.second - b.second};
}
vector<pair<P, int>> all_subsets(const vector<P> &dirs){
vector<pair<P, int>> v{{}};
for(const P &d : dirs){
v.resize(2 * v.size());
for(int i = 0; i < v.size() / 2; i++){
v[i + v.size() / 2] = {v[i].first + d, v[i].second + 1};
}
}
return v;
}
struct hsh{
size_t operator()(const P &p) const {
return p.first * 239 + p.second;
}
};
int main(){
int N;
cin >> N;
P goal;
cin >> goal.first >> goal.second;
vector<P> dirs(N);
for(auto &d : dirs){
cin >> d.first >> d.second;
}
vector<pair<P, int>> a =
all_subsets(vector<P>(begin(dirs), begin(dirs) + N / 2));
vector<pair<P, int>> b =
all_subsets(vector<P>(begin(dirs) + N / 2, end(dirs)));
unordered_map<P, map<int, int>, hsh> first_half;
for(const auto &[offset, num] : a){
++first_half[offset][num];
}
vector<long long> ans(N + 1);
for(const auto &[offset, num] : b){
auto it = first_half.find(goal - offset);
if(it != end(first_half)){
for(const auto &[num2, ways] : it->second){
ans[num + num2] += ways;
}
}
}
for (int i = 1; i <= N; i++){
cout << ans[i] << "\n";
}
}
2nd method:
#include <bits/stdc++.h>
using namespace std;
using P = pair<long long, long long>;
P operator+(P a, P b){
return {a.first + b.first, a.second + b.second};
}
P operator-(P a, P b){
return {a.first - b.first, a.second - b.second};
}
vector<pair<P, int>> all_subsets(const vector<P> &dirs){
vector<pair<P, int>> v{{}};
for(const P &d : dirs){
v.resize(2 * v.size());
for(int i = 0; i < v.size() / 2; i++){
v[i + v.size() / 2] = {v[i].first + d, v[i].second + 1};
}
}
sort(v.begin(), v.end());
return v;
}
int main(){
int N;
cin >> N;
P goal;
cin >> goal.first >> goal.second;
vector<P> dirs(N);
for(auto &d : dirs){
cin >> d.first >> d.second;
}
vector<pair<P, int>> a =
all_subsets(vector<P>(begin(dirs), begin(dirs) + N / 2));
vector<pair<P, int>> b =
all_subsets(vector<P>(begin(dirs) + N / 2, end(dirs)));
reverse(b.begin(), b.end());
vector<long long> ans(N + 1);
vector<int> with_num;
P rest_prev{1e18, 1e18};
int ib = 0;
for(const auto &[offset, num] : a){
const P rest = goal - offset;
if(rest != rest_prev){
rest_prev = rest;
with_num = vector<int>(N - N / 2 + 1);
for(; ib < b.size() && b.at(ib).first > rest; ++ib);
for(; ib < b.size() && b.at(ib).first == rest; ++ib){
++with_num.at(b.at(ib).second);
}
}
for(int i = 0; i < with_num.size(); i++){
ans[i + num] += with_num[i];
}
}
for(int i = 1; i <= N; i++){
cout << ans[i] << "\n";
}
}
The following code is not the solution to this preblem.
#include <iostream>
using namespace std;
int main(){
cout << "subscribe~";
return 0;
}
全部评论 2
https://game.hullqin.cn/bzm/1145
2024-08-14 来自 广东
0抄我题解?扣税!
2024-08-10 来自 广东
0
有帮助,赞一个