# 2020 Hangzhou power multi school #8 (supplementary)

### 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;
}


Posted by dm3 on Thu, 19 May 2022 04:10:37 +0300