欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

2020杭电多校第八场题解

程序员文章站 2022-03-23 22:37:07
Clockwise or Counterclockwise题目传送门Clockwise or Counterclockwise题目大意给你三个点ABC,判断A->B->C的方向(逆时针或者顺时针)思路叉积/*A(x1,y1) B(x2,y2) C(x3,y3)向量AB=(x2-x1,y2-y1)向量AC=(x3-x1,y3-y1)若 AB x AC < 0 则 ABC 顺时针若 AB x AC > 0 则 ABC 逆时针若 AB x AC = 0 则 AB、...

Clockwise or Counterclockwise

题目传送门

Clockwise or Counterclockwise

题目大意

给你三个点ABC,判断A->B->C的方向(逆时针或者顺时针)

思路

叉积

/*
A(x1,y1) B(x2,y2) C(x3,y3)
向量AB=(x2-x1,y2-y1)
向量AC=(x3-x1,y3-y1)
若 AB x AC < 0 则 ABC 顺时针
若 AB x AC > 0 则 ABC 逆时针
若 AB x AC = 0 则 AB、AC 共线 同向或者反向
*/
struct node{
    double x,y;
}a[N];
double cross(node a,node b,node c){//>0,ab在ac顺时针;<0,ab在ac逆时针
    return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}

AC Code

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=4;
struct node{
    double x,y;
}a[N];
double cross(node a,node b,node c){//>0,ab在ac顺时针;<0,ab在ac逆时针
    return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
void solve(){
    cin>>a[1].x>>a[1].y>>a[2].x>>a[2].y>>a[3].x>>a[3].y;
    double d=cross(a[1], a[2], a[3]);
    if(d<0) cout<<"Clockwise"<<endl;
    else    cout<<"Counterclockwise"<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

Fluctuation Limit

题目传送门

Fluctuation Limit

题目大意

给你n个区间l和r,以及波动k
求是否有一个序列满足在l~r(可以波动k)

思路

官方题解:
如果 i 是在 [l,r] 范围内, 那么 i + 1 必须要在 [l−k,r + k] 范围内.这是因为如果 i + 1 选了 范围外的值, i 就无解了. 这样可以从左往右, 把左边的约束带到右边.再从右往左做一遍.最后剩下的区间应该就是可 行域.因为题目只要求一种方案, 全部选最低的即可.复杂度 O(n).

AC Code

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=1e5 +9;
int n, k;
int l[N], r[N], L, R;
void solve(){
    cin>>n>>k;
    l[0]=0, r[0]=INF;
    for(int i=1; i<=n; i++){
        cin>>L>>R;
        l[i]=max(l[i-1]-k, L);
        r[i]=min(r[i-1]+k, R);
    }
    int flag=1;
    for(int i=n-1; i>=1; i--){
        l[i]=max(l[i+1]-k, l[i]);
        r[i]=min(r[i+1]+k, r[i]);
        if(l[i]>r[i])   flag=0;
    }
    if(flag){
        cout<<"YES"<<endl;
        for(int i=1; i<=n; i++) cout<<l[i]<<" ";
        cout<<endl;
    }
    else    cout<<"NO"<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

本文地址:https://blog.csdn.net/xmyrzb/article/details/108130429

相关标签: 2020杭电多校