C,D,K,L题解
C.奶龙日历
一道有意思的数学推式子题。
首先，根据题意可以写出式子：
经过几步移项和消元，我们可以将式子化简成：
也就是：
进一步化简
统计有多少对正整数对 ( (x, y) ) 使得 ( w' ) 是 ( y - x ) 的因数。
所以最后答案就是：
最后对式子进行等差数列求和公式就可以得到答案
void solve(){
LL m,d,w;
cin>>m>>d>>w;
LL mn=min(m,d);
LL a=w,b=d-1;
LL g=gcd(a,b);
a/=g,b/=g;
LL mx=(mn-1)/a;
LL ans=mn*mx-a*((mx+1)*mx)/2;
cout<<ans<<endl;
}
D.计算几何
签到题，计算长方体的体积，长宽高相乘就行
void solve(){
double a,b,c;
cin>>a>>b>>c;
double s=a*b*c;
printf("%lf\n",s);
}
K.城市连接
并查集板子题，注意压状
#include<bits/stdc++.h>
using namespace std;
int i,j,k,n,m,s,ans,f[10010],p1,p2,p3;
int find(int k){
if(f[k]==k)return k;
return f[k]=find(f[k]);
}
int main()
{
cin>>n>>m;
for(i=1;i<=n;i++)
f[i]=i;
for(i=1;i<=m;i++){
cin>>p1>>p2>>p3;
if(p1==1)
f[find(p2)]=find(p3);
else
if(find(p2)==find(p3))
printf("Y\n");
else
printf("N\n");
}
return 0;
}
L.解小学方程
防ak题
题意
给定 ( A ), ( B ), 和 ( C )，求解如下的线性规划问题：
最大化目标函数：
约束条件：
解法
可以看出是线性规划的标准形式，但是有一个重要的条件是线性约束只有两个，考虑转化问题，使用线性规划的对偶原理将问题转化为变量只有两个。
对偶得到如下线性规划：
最小化目标函数：
约束条件：
利用图解法
对于对偶问题，只有两个变量的情况，我们可以把 ( x, y ) 当作平面上的二维，每个限制
可以看作直线的一般式方程，分割平面得到的可行域为一个半平面，问题转化为在这些半平面的交集中找到一点使 ( Sx + Ty ) 最小。
我们可以首先离线询问，然后按照 S,T 排序最后统一处理即可。
#include<bits/stdc++.h>
using namespace std;
#define __float128 long double
namespace Basis2D{
const double PI = acosl(-1.L);
constexpr double INF = 1e8;
constexpr double EPS = 1e-20;
struct Point{
__float128 x,y;
Point(__float128 _x=0, __float128 _y=0):x(_x),y(_y){}
Point& operator=(const Point&o){
x = o.x; y = o.y;
return *this;
}
friend bool operator<(const Point& a, const Point&b){
return std::abs(a.x-b.x)<EPS?a.y<b.y:a.x<b.x;
}
friend Point operator+(const Point& a, const Point&b){
return {a.x+b.x, a.y+b.y};
}
friend Point operator-(const Point&p){
return {-p.x, -p.y};
}
friend Point operator-(const Point& a, const Point&b){
return a + (-b);
}
friend __float128 operator*(const Point& a, const Point&b){
return a.dot(b);
}
__float128 norm()const{
return std::hypotl(x, y);
}
__float128 dot(const Point&o)const{
return x*o.x + y*o.y;
}
__float128 cross(const Point&o)const{
return x*o.y - y*o.x;
}
__float128 theta()const{
return std::abs(x)+std::abs(y)>EPS?atan2l(y,x):-INF;
}
};
using Points = std::vector<Point>;
__float128 norm(const Point&p){
return p.norm();
}
__float128 dot(const Point&a, const Point&b){
return a.dot(b);
}
__float128 cross(const Point&a, const Point&b){
return a.cross(b);
}
__float128 theta(const Point&p){
return p.theta();
}
struct Line : public std::array<Point,2>{
using std::array<Point,2>::array;
Line(Point a, Point b):array({a,b}){}
operator Point()const{
return (*this)[1] - (*this)[0];
}
friend Point operator&(const Line&a, const Line&b){
return a.intersection(b);
}
Point intersection(const Line&o)const{
__float128 S1 = cross(o[1]-(*this)[0], *this);
__float128 S2 = cross(o[0]-(*this)[0], *this);
return Point{
(S1 * o[0].x - S2 * o[1].x) / (S1 - S2),
(S1 * o[0].y - S2 * o[1].y) / (S1 - S2)
};
}
};
using Lines = std::vector<Line>;
Point intersection(const Line&a, const Line&b){
return a.intersection(b);
}
}
namespace Algorithm2D{
using namespace Basis2D;
namespace HalfPlane{
template<typename LineContainer>
Points overlap(const LineContainer&_lines){
Lines lines(_lines.begin(), _lines.end());
std::sort(lines.begin(), lines.end(), [](auto a,auto b){
return theta(a) < theta(b);
});
if(lines.empty() || norm(lines[0]) < EPS) return {};
std::deque<Point> res;
std::deque<Line> dq;
for(auto l : lines){
while(!res.empty() && cross(l, res.back() - l[0]) < -EPS){
res.pop_back(); dq.pop_back();
}
while(!res.empty() && cross(l, res.front() - l[0]) < -EPS){
res.pop_front(); dq.pop_front();
}
dq.push_back(l);
if(dq.size()>1){
if(std::abs(cross(dq.back(), dq[dq.size()-2])) < EPS){
Line bk = dq.back(); dq.pop_back();
if(cross(bk, dq.back()[0] - bk[0]) < -EPS){
if(dot(bk, dq.back()) < -EPS) return {};
dq.back() = l;
}
if(!res.empty()) res.pop_back();
}
if(dq.size()>1) res.push_back(intersection(dq.back(), dq[dq.size()-2]));
}
}
while(!res.empty() && cross(dq.front(), res.back() - dq.front()[0]) < -EPS){
res.pop_back(); dq.pop_back();
}
if(dq.size()>1) res.push_front(intersection(dq.back(), dq.front()));
assert(res.size() >= 3 && cross(dq.front(), dq.back()) <= EPS);
return Points(res.begin(), res.end());
}
}
}
int solve()//a+b范例
{
using namespace Basis2D;
int n, m;
n=100000,m=10000;
cin>>n>>m;
Lines lines;
lines.emplace_back(Point{-INF,-INF},Point{INF,-INF});
lines.emplace_back(Point{INF,-INF},Point{INF,INF});
lines.emplace_back(Point{INF,INF},Point{-INF,INF});
lines.emplace_back(Point{-INF,INF},Point{-INF,-INF});
for(int i=0;i<n;i++){
int a, b, c;
cin>>a>>b>>c;
lines.emplace_back(Point{0,1.L*(__float128)c/b}, Point{0,1.L*(__float128)c/b}+Point{1,-1.L*(__float128)a/b});
}
auto poly = Algorithm2D::HalfPlane::overlap(lines);
n = poly.size();
vector<tuple<int, int, int>> query(m);
vector<__float128> ans(m);
for(int i=0; i<m; i++){
int a, b;
cin>>a>>b;
query[i] = {a, b, i};
}
sort(query.begin(), query.end(), [](auto x, auto y){
auto[a1,b1,_1] = x;
auto[a2,b2,_2] = y;
// {0,0} -> {b,-a}
return atan2l(-a1,b1) < atan2l(-a2,b2);
});
for(int i=0,j=0; j<m; i=(i+1)%n){
while(true){
auto[a,b,id] = query[j];
auto[x,y] = (poly[(i+1)%n]-poly[i]);
if(x < 0) x=-x, y=-y;
if((__float128)y*b >= -(__float128)a*x + EPS) break;
i = (i+1)%n;
}
while(j<m){
auto[a,b,id] = query[j];
auto[x,y] = (poly[(i+1)%n]-poly[i]);
if(x < 0) x=-x, y=-y;
if((__float128)y*b + EPS < -(__float128)a*x) break;
ans[id] = (__float128)a*poly[i].x + (__float128)b*poly[i].y;
j++;
}
}
for(int i=0; i<m; i++){
if(ans[i] < -EPS){
string s="IMPOSSIBLE";
cout<<s<<endl;
continue;
}
if(std::abs(ans[i])<EPS) ans[i] = 0.;
printf("%.5Lf\n", ans[i]);
}
return 0;
}
int main()
{
solve();
return 0;
}
搜狐畅游公司福利 965人发布
投递搜狐畅游等公司10个岗位 >
查看15道真题和解析
