2021 Niuke summer multi school training camp 6
F-Hamburger Steak
thinking
Sort and calculate in descending order of time a n s b e s t = m a x ( ⌈ a v g ( t i ) ⌉ , m a x { t i } ) ans_{best} = max(\lceil avg(t_i) \rceil , max\{t_i\}) ansbest = max(⌈ avg(ti) ⌉, max{ti}), and then arrange the time of hamburger in the pot in descending order of time. If the current pot time has exceeded a n s b e s t ans_{best} ansbest, change to the next pot for arrangement, cut off the excess part and put it into the next pot, so as to fully meet the meaning of the question (hamburgers can't be put in two pots at the same time) and minimize the time.
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
const int mod = 998244353;
struct node
{
ll l, r;
int id;
bool operator < (const node& obj) const
{
return l < obj.l;
}
};
struct node1
{
int id;
ll num;
bool operator < (const node1& obj) const
{
return num > obj.num;
}
};
node1 t[N];
vector<node> vec[N];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
ll sum = 0;
for(int i = 0; i < n; i++)
{
scanf("%lld", &t[i].num);
t[i].id = i;
sum += t[i].num;
}
ll best = (sum + m - 1) / m;
sort(t, t + n);
if(t[0].num > best)
best = t[0].num;
int id = 1;
ll cnt = 0;
for(int i = 0; i < n; i++)
{
if(cnt + t[i].num > best)
{
vec[t[i].id].push_back({cnt, best, id});
t[i].num = t[i].num - best + cnt;
cnt = 0;
id++;
i--;
}
else
{
vec[t[i].id].push_back({cnt, cnt + t[i].num, id});
cnt += t[i].num;
if(cnt == best)
{
cnt = 0;
id++;
}
}
}
for(int i = 0; i < n; i++)
{
node t1, t2;
if(vec[i].size() == 1)
{
t1 = vec[i][0];
cout << 1 << ' ';
cout << t1.id << ' ' << t1.l << ' ' << t1.r << endl;
}
else
{
t1 = vec[i][0];
t2 = vec[i][1];
cout << 2 << ' ';
if(t2.l > t1.l)
{
cout << t1.id << ' ' << t1.l << ' ' << t1.r << ' ';
cout << t2.id << ' ' << t2.l << ' ' << t2.r << endl;
}
else
{
cout << t2.id << ' ' << t2.l << ' ' << t2.r << ' ';
cout << t1.id << ' ' << t1.l << ' ' << t1.r << endl;
}
}
}
return 0;
}
H-Hopping Rabbit
thinking
Actually from ( x , y ) (x, y) Starting from (x,y) and starting from ( x + d , y + d ) (x + d, y + d) (x+d,y+d) starting is the same, because you can only jump left and right d d d, then the different starting points can be summarized as follows x ∈ [ 0 , d ) , y ∈ [ 0 , d ) x \in [0, d), y \in [0, d) x ∈ [0,d),y ∈ [0,d). We map all traps to x ∈ [ 0 , d ) , y ∈ [ 0 , d ) x \in [0, d), y \in [0, d) Within the range of x ∈ [0,d),y ∈ [0,d) (assigned as 1), and then find any point with a value of 0 to output its coordinates. If there is no such point, it is not feasible.
It sounds simple, but d's scope 1e5, violence obviously doesn't work. At first, I thought I could do it with a two-dimensional line segment tree, but I wouldn't. later, when I was thinking about "what data structure can be used to deal with the rectangular coverage problem", I suddenly thought of the scan line. In the process of scanning line scanning, find out whether the value of a column is not full. If so, it means that the column has 0, and then O ( n ) O(n) O(n) just find 0. This complexity is O ( log d + d ) O(\log d + d) O(logd+d) can be passed.
However, it seems that the subject data is a little weak. We missed the part from the beginning to the first rectangle, but it passed.
code
(put a teammate's code first. I don't know how to implement it yet
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
using namespace std;
const int N = 2e5 + 10;
ll x[N * 8];
struct Line {
ll l, r, h;
int mark;
Line() {}
Line(ll _l, ll _r, ll _h, int m) {
l = _l; r = _r, h = _h; mark = m;
}
bool operator<(const Line& v) const {
return h < v.h;
}
}li[N * 8];
#define ls (rt << 1)
#define rs ((rt << 1) | 1)
struct SegTree{
int l, r, cnt;
ll len; //Coverage length
}tr[N * 8];
void build(int l, int r, int rt) {
tr[rt].l = l; tr[rt].r = r;
tr[rt].cnt = 0;
tr[rt].len = 0;
if (l == r) {
return;
}
int mid = (l + r) >> 1;
build(l, mid, ls);
build(mid + 1, r, rs);
}
void pushup(int rt) {
int l = tr[rt].l, r = tr[rt].r;
if (tr[rt].cnt) tr[rt].len = x[r + 1] - x[l];
else tr[rt].len = tr[ls].len + tr[rs].len;
}
void modify(ll st, ll ed, int rt, int v) {
int l = tr[rt].l, r = tr[rt].r;
if (x[r + 1] <= st || ed <= x[l])
return;
if (st <= x[l] && x[r + 1] <= ed) {
tr[rt].cnt += v;
pushup(rt);
return;
}
modify(st, ed, ls, v);
modify(st, ed, rs, v);
pushup(rt);
}
int cnt = 0;
void addline(ll x1, ll y1, ll x2, ll y2) {
++cnt;
x[2 * cnt - 1] = x1;
x[2 * cnt] = x2;
li[2 * cnt - 1] = Line(x1, x2, y1, 1);
li[2 * cnt] = Line(x1, x2, y2, -1);
}
int main () {
ll n, d;
scanf("%lld%lld", &n, &d);
cnt = 0;
bool f = true;
ll add = 1e9 * d;
for (int i = 1; i <= n; i++) {
ll x1, x2, y1, y2;
scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
x1 += add;
x2 += add;
y1 += add;
y2 += add;
if (x2 - x1 >= d && y2 - y1 >= d) f = false;
if (!f) continue;
x1 = (x1) % d;
x2 = (x2 - 1) % d + 1;
y1 = (y1) % d;
y2 = (y2 - 1) % d + 1;
// cout << x1 << ", " << y1 << " " << x2 << ", " << y2 << "\n";
if (x1 < x2) {
if (y1 < y2) {
addline(x1, y1, x2, y2);
}
else if (y1 > y2) {
addline(x1, y1, x2, d);
addline(x1, 0, x2, y2);
}
else {
addline(x1, 0, x2, d);
}
}
else if (x1 > x2){
if (y1 < y2) {
addline(x1, y1, d, y2);
addline(0, y1, x2, y2);
}
else if (y1 > y2) {
addline(x1, y1, d, d);
addline(0, 0, x2, y2);
addline(0, y1, x2, d);
addline(x1, 0, d, y2);
}
else {
addline(x1, 0, d, d);
addline(0, 0, x2, d);
}
}
else {
if (y1 < y2) {
addline(0, y1, d, y2);
}
else if (y1 > y2) {
addline(0, y1, d, d);
addline(0, 0, d, y2);
}
else {
f = false;
}
}
}
if (!f) {
printf("NO\n");
return 0;
}
// for (int i = 1; i <= 2 * cnt; i++) {
// printf("%lld %lld %lld\n", li[i].l, li[i].r, li[i].h);
// }
sort(li + 1, li + 1 + 2 * cnt);
sort(x + 1, x + 1 + 2 * cnt);
int tot = unique(x + 1, x + 1 + 2 * cnt) - x - 1;
build(1, tot - 1, 1);
int hh = -1;
li[2 * cnt + 1] = Line(0, d, d, 1);
for (int i = 1; i <= 2 * cnt; i++) {
modify(li[i].l, li[i].r, 1, li[i].mark);
ll len = tr[1].len;
ll h = li[i + 1].h - li[i].h;
// cout << len << " " << h << "\n";
if (len < d && h > 0) {
hh = li[i].h;
break;
}
}
if (hh == -1) {
printf("NO\n");
}
else {
vector<ll> a(d + 5, 0);
for (int i = 1; i <= 2 * cnt; i++) {
if (li[i].h <= hh) {
a[li[i].l] += li[i].mark;
a[li[i].r] -= li[i].mark;
}
}
for (int i = 1; i < d; i++)
a[i] += a[i - 1];
bool ok = false;
int xx;
for (int i = 0; i < d && !ok; i++) {
if (a[i] == 0) ok = true, xx = i;
}
if (ok) {
printf("YES\n");
printf("%d %d\n", xx, hh);
}
else printf("NO\n");
}
return 0;
}
I-Intervals on the Ring
thinking
Set the set to be rounded up as [ l 1 , r 1 ] , [ l 2 , r 2 ] , ... , [ l n , r n ] {[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]} [l1, r1], [l2, r2],..., [ln, rn], then the answer sequence is [ l 1 , r n ] , [ l 2 , r 1 ] , [ l 3 , r 2 ] , ... , [ l n , r n − 1 ] {[l_1, r_n], [l_2, r_1], [l_3, r_2], \dots, [l_n, r_{n - 1}]} [l1,rn],[l2,r1],[l3,r2],...,[ln,rn−1] .
Note that the input may have a l > r l > r l> In the case of R, this should be handled in two ways.
Obviously, it will not exist.
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10;
const int mod = 998244353;
struct node
{
int l, r;
bool operator < (const node& obj) const
{
return l < obj.l;
}
};
vector<node> vec;
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
vec.clear();
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0, l, r; i < m; i++)
{
scanf("%d%d", &l, &r);
if(l > r)
{
vec.push_back({l, n});
vec.push_back({1, r});
}
else
{
vec.push_back({l, r});
}
}
sort(vec.begin(), vec.end());
printf("%d\n", vec.size());
printf("%d %d\n", vec[0].l, vec[vec.size() - 1].r);
for(int i = 1; i < vec.size(); i++)
{
printf("%d %d\n", vec[i].l, vec[i - 1].r);
}
}
return 0;
}