1003 Clockwise or Counterclockwise

meaning of the title

​ Judge whether the three points form a triangle in order, clockwise or counterclockwise.

thinking

​ Direct vector inner product interpretation.

code

pair<ll, ll> a, b, c;

void slove() {
    cin >> a.first >> a.second >> b.first >> b.second >> c.first >> c.second;
    a.first = a.first - b.first; a.second = a.second - b.second;
    b.first = c.first - b.first; b.second = c.second - b.second;
    if(a.first * b.second - a.second * b.first > 0) puts("Clockwise");
    else puts("Counterclockwise");
}

1006 Fluctuation Limit

meaning of the title

​ For some intervals, ask whether you can construct an array so that each number is within the corresponding interval, and the fluctuation of two adjacent numbers does not exceed \ (k \).

thinking

​ From the front to the back, prefix all intervals once and take min, and then suffix all intervals once and take min. if there is NO \ (L > R \) in all the last intervals, output "YES", take the left end point of the interval in turn, and otherwise output "NO".

code

int n, k;
pii a[maxn], res[maxn];

pii min(pii a, pii b) {
    a.first = max(a.first, b.first);
    a.second = min(a.second, b.second);
    return a;
}

void slove() {
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        scanf("%lld%lld", &a[i].first, &a[i].second);
        res[i].first = 0;
        res[i].second = mod;
    }
    res[0] = a[0];
    for(int i = 1; i < n; i++) {
        pii temp = res[i - 1];
        temp.first -= k; temp.second += k;
        res[i] = min(a[i], temp);
    }
    bool flag = true;
    for(int i = n - 2; i >= 0; i--) {
        pii temp = res[i + 1];
        temp.first -= k; temp.second += k;
        res[i] = min(res[i], temp);
        if(res[i].first > res[i].second) flag = false;
    }
    if(res[n - 1].first > res[n - 1].second) flag = false;
    if(!flag) puts("NO");
    else {
        puts("YES");
        for(int i = 0; i < n; i++) {
            printf("%lld", res[i].first);
            if(i == n - 1) puts("");
            else printf(" ");
        }
    }
}

1008 Hexagon

meaning of the title

​ A two-dimensional coordinate in which each lattice is a hexagon. Walking in six directions is 1, 2, 3, 4, 5 and 6. Output the scheme of completing all grids from the starting point, which requires the maximum number of turns.

thinking

​ It can be divided into odd and even numbers to simulate respectively.

code

void slove() {
    cin >> n;
    if(n % 2) {  //Odd number
        cout << "16535424313262151";
        int cnt = 2;
        for(int i = 5; i <= n; i += 2) {
            cout << "616";
            for(int j = 0; j < cnt; j++) cout << "46";
            cout << "535";
            for(int j = 0; j < cnt; j++) cout << "35";
            cout << "424";
            for(int j = 0; j < cnt; j++) cout << "24";
            cout << "313";
            for(int j = 0; j < cnt; j++) cout << "13";
            cout << "262";
            for(int j = 0; j < cnt; j++) cout << "62";
            cout << "151";
            for(int j = 0; j < cnt; j++) cout << "51";
            cnt += 2;
        }
        cout << "6\n";
    }
    else {  //even numbers
        cout << "64321";
        int cnt = 1;
        for(int i = 4; i <= n; i += 2) {
            cout << "616";
            for(int j = 0; j < cnt; j++) cout << "46";
            cout << "535";
            for(int j = 0; j < cnt; j++) cout << "35";
            cout << "424";
            for(int j = 0; j < cnt; j++) cout << "24";
            cout << "313";
            for(int j = 0; j < cnt; j++) cout << "13";
            cout << "262";
            for(int j = 0; j < cnt; j++) cout << "62";
            cout << "151";
            for(int j = 0; j < cnt; j++) cout << "51";
            cnt += 2;
        }
        cout << "6\n";
    }
}

1009 Isomorphic Strings

meaning of the title

​ Give a string with a length of N. if there is a factor \ (k \quad (k!=n) \) of \ (n \), the string can be divided into \ (n/k \) blocks, and these block strings belong to the cyclic isomorphic string of a string.

thinking

​ All factors of \ (n \) are processed. For each factor, the sub string of \ (n/k \) is distinguished, and the maximum and minimum representation of the string is used to judge whether it is a circular isomorphic string.

code

string minstr(string s) {
    int len = s.size(), i = 0, j = 1, k = 0;
    s += s;
    while(i < len && j < len && k < len - 1) {
        int temp = s[(i + k) % len] - s[(j + k) % len];
        if(!temp) k++;
        else {
            if(temp > 0) i = i + k + 1;
            else if(temp < 0) j = j + k + 1;
            if(i == j) j++;
            k = 0;
        }
    }
    if(i > j) swap(i, j);
    return s.substr(i, len);
}

void slove() {
    cin >> n >> s;
    string ans = "No";
    vector<int> fac;
    for(int i = 1; i * i <= n; i++) {
        if(n % i == 0) {
            fac.push_back(i);
            fac.push_back(n / i );
        }
    }
    for(int item: fac) {
        if(item == n) continue;
        string mins = minstr(s.substr(0, item));
        int k = n / item, pos = item, cnt = 0;
        for(int i = 1; i < k; i++) {
            string temps = minstr(s.substr(pos, item));
            if(mins == temps) cnt++;
        }
        if(cnt == k) ans = "Yes";
    }
    cout << ans << endl;
}