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

2020杭电多校第八场

程序员文章站 2022-06-22 17:25:18
1008 Hexagon构造,思维,分治题意:有一个半径为n的六边形块,现在让你用最多更换方向次数的走法,走遍这整个块,起点可以在任意点,输出走的每步的方向。思路:瞎搞以后发现可以从左上角开始,先走一个2,然后分别走<3,1><4,2><5,3><6,4><1,5>直到不能再走<2,6>,然后再走个3,这时候我们就可以发现我们把外面的两圈都方向不同地走完了,然后进入了内部的左上角,重复一样的操作就行了,分治的思想从n的问题转....
  • 1003 Clockwise or Counterclockwise
    签到,向量叉积
    题意:
    给你三个点a,b,c,按照a,b,c的顺序连出一个圆,现在问你是顺时针画的圆还是逆时针画的圆。
    思路:
    判断c是不是在ab的右边就行,在右边就是顺时针,左边就只逆时针。
    可以用向量ac叉积ab判断,如果大于0就是顺时针,如果小于0就是逆时针。
#include <bits/stdc++.h>
using namespace std;
int tc,x1,yo,x2,y2,x3,y3;
const double eps = 1e-8;
int sgn(double x) {
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    else return 1;
}
struct Point {
    double x, y;
    Point() {}
    Point(double _x, double _y) {
        x = _x;
        y = _y;
    }
    void input() {
        scanf("%lf%lf", &x, &y);
    }
    void output() {
        printf("%.8f%.8f\n", x, y);
    }
    bool operator == (Point b) const {
        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
    }
    bool operator < (Point b) const {
        return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;
    }
    Point operator - (const Point &b) const {
        return Point(x - b.x, y - b.y);
    }
    //点积
    double operator * (const Point &b) const {
        return x * b.x + y * b.y;
    }
    //叉积
    double operator ^ (const Point &b) const {
        return x * b.y - y * b.x;
    }
}a,b,c;
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.precision(10);cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "r", stdin);
#endif
    cin>>tc;
    while(tc--){
        cin>>x1>>yo>>x2>>y2>>x3>>y3;
        a=Point(x1,yo);
        b=Point(x2,y2);
        c=Point(x3,y3);
        Point x,y;
        x=b-a;
        y=c-a;
        double res=y^x;
        if(sgn(res)==1) cout<<"Clockwise"<<'\n';
        else cout<<"Counterclockwise"<<'\n';
    }
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}

  • 1006 Fluctuation Limit
    签到,思维
    题意:
    给你n个区间,你现在要从第一个区间的某个点开始走,走遍n个区间,每次要走在n个区间内部,每次最多走[-k,+k]这个gap,现在问你能不能有一种走法满足,没有的话输出-1,有的话输出每次在的点。
    思路:
    先从后往前维护一下合法的区间,l取个max,r取个min,夹出来的那个区间就是合法区间,然后瞎搞就行,接下来的思路有点像没有问题我就不动,有了问题我再去动这种感觉。
#include <bits/stdc++.h>
using namespace std;
const int maxn=(int)1e5+100;
int tc, n, k;
struct node{
    int l,r;
}nd[maxn];
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.precision(10);cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "r", stdin);
#endif
    cin>>tc;
    while(tc--){
        cin>>n>>k;
        for(int i=1; i<=n; ++i) cin>>nd[i].l>>nd[i].r;
        bool ok=true;
        for(int i=n-1; i>=1; --i){
            int tl=nd[i+1].l-k;
            int tr=nd[i+1].r+k;
            if(tl>nd[i].r || tr<nd[i].l) {
                ok=false;
                break;
            }
            nd[i].l=max(tl, nd[i].l);
            nd[i].r=min(tr, nd[i].r);
        }
        if(!ok) cout<<"NO"<<'\n';
        else{
            cout<<"YES"<<'\n';
            int now=nd[1].l;
            cout<<now<<' ';
            for(int i=2; i<=n; ++i){
                if(now<nd[i].l){
                    now=nd[i].l;
                } else if(now>nd[i].r){
                    now=nd[i].r;
                }
                cout<<now<<' ';
            }cout<<'\n';
        }
    }
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}

  • 1008 Hexagon
    构造,思维,分治
    题意:
    有一个半径为n的六边形块,现在让你用最多更换方向次数的走法,走遍这整个块,起点可以在任意点,输出走的每步的方向。
    思路:
    瞎搞以后发现可以从左上角开始,先走一个2,然后分别走<3,1><4,2><5,3><6,4><1,5>直到不能再走<2,6>,然后再走个3,这时候我们就可以发现我们把外面的两圈都方向不同地走完了,然后进入了内部的左上角,重复一样的操作就行了,分治的思想从n的问题转换为n-2的问题,所以先预处理一下n=2和n=3的时候,然后瞎搞就行。
#include <bits/stdc++.h>
using namespace std;
int tc,n;
vector<int> G[1000];
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.precision(10);cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "r", stdin);
#endif
    G[2].emplace_back(2);
    G[2].emplace_back(3);
    G[2].emplace_back(4);
    G[2].emplace_back(5);
    G[2].emplace_back(6);
    G[2].emplace_back(2);

    G[3].emplace_back(2);
    G[3].emplace_back(3);
    G[3].emplace_back(1);
    G[3].emplace_back(3);
    G[3].emplace_back(4);
    G[3].emplace_back(2);
    G[3].emplace_back(4);
    G[3].emplace_back(5);
    G[3].emplace_back(3);
    G[3].emplace_back(5);
    G[3].emplace_back(6);
    G[3].emplace_back(4);
    G[3].emplace_back(6);
    G[3].emplace_back(1);
    G[3].emplace_back(5);
    G[3].emplace_back(1);
    G[3].emplace_back(2);
    G[3].emplace_back(3);
    cin>>tc;
    while(tc--){
        int sum=0;
        cin>>n;
        while(n>1){
            if(int(G[n].size())==0){
                int tot=n-2;
                G[n].emplace_back(2);
                for(int i=0; i<tot; ++i) {
                    G[n].emplace_back(3);
                    G[n].emplace_back(1);
                }G[n].emplace_back(3);
                for(int i=0; i<tot; ++i) {
                    G[n].emplace_back(4);
                    G[n].emplace_back(2);
                }G[n].emplace_back(4);
                for(int i=0; i<tot; ++i) {
                    G[n].emplace_back(5);
                    G[n].emplace_back(3);
                }G[n].emplace_back(5);
                for(int i=0; i<tot; ++i) {
                    G[n].emplace_back(6);
                    G[n].emplace_back(4);
                }G[n].emplace_back(6);
                for(int i=0; i<tot; ++i) {
                    G[n].emplace_back(1);
                    G[n].emplace_back(5);
                }G[n].emplace_back(1);
                tot--;
                for(int i=0; i<tot; ++i){
                    G[n].emplace_back(2);
                    G[n].emplace_back(6);
                }
                G[n].emplace_back(2);
                G[n].emplace_back(3);
                for(int x:G[n]) {
                    cout<<x;
                }
            } else{
                for(int x:G[n]) cout<<x;
            }
            n-=2;
        }
        cout<<'\n';
    }
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}

本文地址:https://blog.csdn.net/qq_43555854/article/details/107993015