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