杭电暑假多校集训营第八场

Clockwise or Counterclockwise

题意：按顺序依次给出A，B，C三个点的坐标，判断这三个点的顺序是顺时针还是逆时针。
思路：利用向量的叉乘进行借用右手螺旋定则判断。
图片说明
通过判断向量ABX向量AC的符号进行判断，如果大于0，说明是逆时针方向，反之则为顺时针方向。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int t;
    cin>>t;
    while(t--){
        ll x1,x2,x3,y1,y2,y3;
        cin>>x1>>y1>>x2>>y2>>x3>>y3;
        if((x2-x1)*(y3-y2)>(x3-x2)*(y2-y1))  cout<<"Counterclockwise"<<endl;
        else  cout<<"Clockwise"<<endl;
    }
    return 0;
}

Fluctuation Limit

题意：给出n个区间，再这n个区间内选择各选择一个数，使得这些数两两之间的差值不会超过k。
思路：差分约束。先从左到右进行约束，将区间左端点往大的约束，将右端点往小的约束。然后对约束好的每个区间，从右边往左边进行约束，每次约束之后判断当前的约束的区间左右端的位置关系，左端大于右端则说明不存在。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l[100010],r[100010];
ll up[100010],down[100010];
void solve(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)  cin>>l[i]>>r[i];
    bool flag=false;
    down[0]=l[0],up[0]=r[0];
    for(int i=1;i<n;i++){
        down[i]=max(down[i-1]-k,l[i]),up[i]=min(r[i],up[i-1]+k);
        if(down[i]>up[i])  flag=true;
    }
    for(int i=n-2;i>=0;i--){
        down[i]=max(down[i+1]-k,down[i]),up[i]=min(up[i+1]+k,up[i]);
        if(up[i]<down[i])  flag=true;
    }
    if(flag)  cout<<"NO"<<endl;
    else{
        cout<<"YES"<<endl;
        for(int i=0;i<n;i++) {
            cout<<down[i];
            if(i<n-1) cout<<" ";
        }
        cout<<endl;
    }
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        solve(); 
    }
    return 0;
}

Hexagon

题意：
图片说明

给出一个半径为n的上图这种的往外拓扑的图形，要求输出一种遍历的路径，使得这些遍历的路径转弯的次数最多，并且每个小六边形只能遍历一次，输出一种遍历方案。
思路：打表找规律。通过找规律可以发现对n进行奇数和偶数次的划分。n=2时，一种遍历方案时3 4 5 6 1 2，n=4时，一种遍历方案是（3） 4 2 4 2 （4） 5 3 5 3 （5） 6 4 6 4 （6） 1 5 1 5 （1） 2 6 2 6 （2） 3 1 3 4 （3）（4）（5）（6）（1）（3）n=3时，一种遍历方案为（3）（4） 2 4 （5） 3 5 （6） 4 6 1 5 1 2 6 2 3 4 n=5时，一种遍历方案为3 4 2 4 2 4 2 4 5 3 5 3 5 3 5 6 4 6 4 6 4 6 1 5 1 5 1 5 1 2 6 2 6 2 6 2 3 1 3 1 3 4 3 4 2 4 5 3 5 6 4 6 1 5 1 2 6 2 3 4。

#include<bits/stdc++.h>
using namespace std;
int n;
void odd(){
    for(int k=n-2;k>=1;k-=2){
        int a=4,b=2;
        cout<<"3";
        for(int t=1;t<=5;t++){
            for(int i=1;i<=k;i++){
                cout<<a<<b;
            }
            cout<<a;
            a++,b++;
            if(a>6) a=1;
            if(b>6) b=1;
        }
        cout<<a;
        for(int i=1;i<=k-1;i++) {
            cout<<b<<a;
        }
        cout<<"4";
    }
    cout<<endl;
}
void even(){
    for(int k=n-1;k>=1;k-=2){
        int a=4,b=2;
        cout<<"3";
        for(int t=1;t<=5;t++){
            if(t==5&&k==1)  break;
            cout<<a;
            for(int i=1;i<=k-1;i++){
                cout<<b<<a;
            }
            a++,b++;
            if(a>6) a=1;
            if(b>6) b=1;
        }
        if(k!=1){
            cout<<a;
            for(int i=1;i<=k-2;i++) cout<<b<<a;
        } 
        if(k==1)  cout<<"3";
        else  cout<<"4";
    }
    cout<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        if(n&1)  odd();
        else  even();
    } 
    return 0;
}