国庆集训day3 A B D F G
A
Leftbest
该题要求你求数列中每个数前面的数比他大的数的最小值有并求出其累积
这是一个签到题 我们按顺序将每个数压入set 在压入之前用upper_bound求比该数大的数
如果找不到就说明没有比他大的就+0，否则就+那个数
注意要用set自带的upper_bound 这样才不会超时
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
ll a[maxn],sum;
int n;
set<ll> st;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
}
for(int i=1;i<=n;++i){
set<ll>::iterator it = st.upper_bound(a[i]);
if(it!=st.end()) sum += *it;
st.insert(a[i]);
}
printf("%lld\n",sum);
return 0;
}B
First Date
这题的范围很小，于是我跑了一个暴力 a 从 0-1 每次+1e-4 答案累积除以10000就是期望了 内部就是跑一个最短路
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>=
#define MAXN 1e10+7
using namespace std;
int n, m, s, t;
vector<int> graph[205];
int que[205], head, tail;
struct edge{
int u, v, x, y;
} edges[405];
int cur;
bool visited[205];
double dis[205], ans, minn;
int main()
{
scanf("%d%d%d%d", &n, &m, &s, &t);
for(int i = 1;i <= m;i ++)
{
scanf("%d%d%d%d", &edges[i].u, &edges[i].v, &edges[i].x, &edges[i].y);
graph[edges[i].u].push_back(i);
graph[edges[i].v].push_back(i);
}
for(double a = 0; a <= 1; a += 1e-4)
{
for(int i = 1;i <= n;i ++) {
visited[i] = 0;
dis[i] = MAXN;
}
dis[s] = 0;
cur = 0;
minn = MAXN;
do{
cur = 0;
minn = MAXN;
for(int i = 1;i <= n;i ++)
{
if(visited[i]) continue;
if(dis[i] < minn) {
minn = dis[i];
cur = i;
}
}
//printf("cur = %d\n", cur);
if(!cur) break;
//printf("cur = %d\n", cur);
visited[cur] = true;
for(int i = 0;i < graph[cur].size();i ++)
{
dis[edges[graph[cur][i]].u] = min(dis[edges[graph[cur][i]].u], dis[cur] + a * edges[graph[cur][i]].y + edges[graph[cur][i]].x);
dis[edges[graph[cur][i]].v] = min(dis[edges[graph[cur][i]].v], dis[cur] + a * edges[graph[cur][i]].y + edges[graph[cur][i]].x);
}
}while(true);
//cout<<dis[t]<<endl;
ans += dis[t];
}
printf("%lf", ans / 10000);
return 0;
}D
Capture Stars
这题是一个很典型的计算几何题目，他要求我们求在两个圆内切的其他范围内用一个圆覆盖最多的点 看到这一点 就应该能想到这是一个圆的反演问题
反演的规则中有这三条
1： 两个圆相切且切点是反演中心的话，这两个圆反演后面变成两条平行的直线
又因为两圆切于原点，所以这两个圆反演后会变成两条竖线，竖线的距离和坐标是可以求出来的
2： 不经过反演中心的圆反演后仍是一个圆
但因为这个圆应该是和那两个圆一个外切一个内切，所以反演过去这个圆刚好与那两条直线相切 圆心一定在两条线的中线上
3： 点反演过去任然是点
因为点是在大圆内部小圆外部，所以反演过去点是在两线内部
所以题目的要求变成了，反演过去的半径固定的圆最多能包括几个点
因为圆心一定在中线上，所以我们以反演过去的点作为圆心以固定的半径画一个圆求出交点
圆心画圆在这两个点范围内的一定能包括这个点（可能相切）
这样就变成了求最多区间覆盖
有两个交点的上方点以1压入vector里 下方点以-1压入
这样我们在遍历vector求出最大的前缀和 这就是能求出最多覆盖的点
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const double pi = acos(-1);
const double zero = 1e-14;
const double eps = 1e-8;
const int N=1e4+5;
int t,n;
double r1, r2, R, x1, x2, ans, r, mid ,rr;
struct node {
double x, y;
node(double _x,double _y){
x=_x,y=_y;
}
node() : node(0, 0) {}
} p[N];
int sgn(double x){
if(fabs(x)<eps)return 0;
if(x<0)return -1;
else return 1;
}
bool cmp(node A,node B){
if(sgn(A.y-B.y)==0) return A.x>B.x;
return A.y<B.y;
}
inline double sqr(double x){return x*x;}
vector<node> a;
int main() {
//R = 20.0;
cin>>t;
while (t--) {
//scanf("%lf %lf", &r1, &r2);
a.clear();
cin>>n;
cin>>R>>r;
//for(int i=1;i<=n;++i)cin>>p[i].x>>p[i].y;
//scanf("%d", &n);
//x1 = sqr(R) / (2.0 * r1);///两条平行线
//x2 = sqr(R) / (2.0 * r2);
//mid = (x1+x2)*0.5;
//rr = fabs(x1-x2) *0.5;
double mid=(double)R+(double)(R*R)/(double)r;
double rr=(double)(R*R)/(double)r-(double)R;
for(ll i=1;i<=n;++i){
//LL x,y;scanf("%lld%lld",&x,&y);
ll x,y;
cin>>x>>y;
p[i].x=(double)(4LL*R*R*x)/(double)(x*x+y*y);
p[i].y=(double)(4LL*R*R*y)/(double)(x*x+y*y);
//点的反演
if(sgn(fabs(p[i].x-mid)-rr)==0){
a.push_back((node){1,p[i].y});
a.push_back((node){-1,p[i].y});
}
else if(sgn(fabs(p[i].x-mid)-rr)<0){
double h=sqrt(sqr(rr)-sqr(p[i].x-mid));
a.push_back((node){-1,p[i].y+h});
a.push_back((node){1, p[i].y-h});
}
else continue;
}
/*
double k;
for(int i=1;i<=n;++i){
k = sqr(R) / ((p[i].x*p[i].x)+(p[i].y*p[i].y));
p[i].x*=k;
p[i].y*=k;
if( sgn(fabs(p[i].x-mid)-rr)== 0 ){
a.push_back(node(1,p[i].y));
a.push_back(node(-1,p[i].y));
}
else if( sgn(fabs(p[i].x-mid)-rr)<0){
double h = sqrt( sqr(rr)-sqr(p[i].x-mid));
a.push_back(node(1,p[i].x+h));
a.push_back(node(-1,p[i].x-h));
}
else continue;
}
*/
ll ans=0,cnt=0;
sort(a.begin(),a.end(),cmp);
for(ll i=0;i<a.size();++i){
cnt+=a[i].x;
//cout<<cnt<<endl;
ans=max(cnt,ans);
}
cout<<ans<<endl;
}
return 0;
}F
Points
这是一个签到题 求度数为1的点的数量 连图都不用建
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N=1e5+5;
int n,t,ans,du[N];
vector<int>a[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<n;++i){
int u,v;
cin>>u>>v;
a[u].pb(v);
a[v].pb(u);
du[u]++,du[v]++;
}
for(int i=1;i<=n;++i){
if(du[i]==1) ans++;
}
cout<<ans<<endl;
return 0;
}
J
Flowers
求n种不同数量的花做要m种花的花团能做多少种
这题我们二分答案 二分能做多少个 然后每个花大于这个个数的一定能全部放 小于的
挨个放放完了就换下一个 最后判断每个花团里有多少花来判断二分的边界判断
#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
int t, n, m;
int arr[300005];
long long pre[300005];
long long ans2, cur;
int l, r, ll, rr, mid2, mid;
signed main()
{
scanf("%lld", &t);
while(t --)
{
ans2 = 0ll;
scanf("%lld%lld", &n, &m);
if(m > n)
{
printf("0\n");
continue;
}
for(int i = 1;i <= n;i ++) {
scanf("%lld", arr + i);
}
sort(arr + 1, arr + n + 1);
for(int i = 1;i <= n;i ++) {
pre[i] = pre[i - 1] + arr[i];
//cout<<pre[i]<<" ";
}
l = arr[1];
r = pre[n] / m + 1;
while(l + 1 < r)
{
mid = (l + r) / 2;
ans2 = 0;
ll = 1, rr = n + 1;
//cout<<"l , r, mid = "<<l<<" "<<r<<" "<<mid<<endl;
while(ll + 1 < rr)
{
mid2 = (ll + rr) / 2;
//cout<<"mid2 = "<<mid2<<endl;
if(arr[mid2] > mid) rr = mid2;
else ll = mid2;
}
//cout<<"pre["<<ll<<"] = "<<pre[ll]<<endl;
ans2 = (pre[ll] + (n - ll) * mid) / mid;
//cout<<"ans2 = "<<ans2<<endl;
if(ans2 >= m) l = mid;
else r = mid;
}
cout<<l<<endl;
}
return 0;
}
拼多多集团-PDD公司氛围 522人发布
投递海康威视等公司10个岗位 >
