牛客多校第六场题解

Contracting Convex Hull

https://ac.nowcoder.com/acm/contest/11257/A

A - Contracting Convex Hull

solved by Tryna.(-)

题意： 许多半平面正在匀速移动，每次询问给定一个时刻，求该时刻下半平面的交构成的凸包的面积

题解：

  • 凸包收缩时每个顶点都是沿着角平分线移动的，当运动到相邻两个对角线相交的顶点，就会两点重合，凸包的形状就会发生变化
  • 对于当前这个凸包，我们找到最近的那个使凸包发生变化的顶点，我们已知移动的距离，可以通过三角函数求出运动的时间，知道了时间就可以以同样的方法求出其他顶点运动的距离，新的凸包就是已知的，然后就重复操作
  • 对于每次变化，凸包总有一段时间形状不变，然后我们就可以求出在这段时间之内的询问，面积是关于时间的一个二次函数，聚聚们tql，我根本推不出这个函数
  • 其他也没啥了，注意点细节就能过了 
#include<bits/stdc++.h>
using namespace std;

#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {   cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...);}

#define ll long long
#define ull unsigned long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define PII pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define PAUSE system("pause");
const double Pi = acos(-1.0);
const double eps = 1e-6;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
const int mod = 998244353;

inline ll rd() {
    ll f = 0; ll x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}
void out(ll a) {if(a<0)putchar('-'),a=-a;if(a>=10)out(a/10);putchar(a%10+'0');}
#define pt(x) out(x),puts("")
inline void swap(ll &a, ll &b){ll t = a; a = b; b = t;}
inline void swap(int &a, int &b){int t = a; a = b; b = t;}
inline ll min(ll a, ll b){return a < b ? a : b;}
inline ll max(ll a, ll b){return a > b ? a : b;}
ll qpow(ll n,ll k,ll mod) {ll ans=1;while(k){if(k&1)ans=ans*n%mod;n=n*n%mod;k>>=1;}return ans%mod;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int sgn(double x){
    if(fabs(x) < eps) return 0;
    else return x < 0?-1:1;
}

struct Point{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
    Point operator + (Point B){return Point(x + B.x,y + B.y);}
    Point operator - (Point B){return Point(x - B.x,y - B.y);}
    Point operator * (double k){return Point(x*k,y*k);}
    Point operator / (double k){return Point(x/k,y/k);}
    double operator ^ (Point B) {
        return x * B.y - y * B.x;
    }
    bool operator == (Point B){return sgn(x - B.x) == 0 && sgn(y - B.y) == 0;}
    double distance(Point B) {
        return sqrt((x - B.x) * (x - B.x) + (y - B.y) * (y - B.y));
    }
}p[maxn], pos[maxn], pp[maxn];

struct Line{
    Point p1,p2;
    Line(){};
    Line(Point p1,Point p2):p1(p1),p2(p2){}
}L[maxn];

Point Cross_point(Point a, Point b, Point c, Point d){
    double s1 = (b - a)^(c - a);
    double s2 = (b - a)^(d - a);
    return Point(c.x * s2 - d.x * s1, c.y * s2 - d.y * s1) / (s2 - s1);
}

double getangle(Point p1, Point p2, Point p3) {  
    double theta = atan2(p1.x - p3.x, p1.y - p3.y) - atan2(p2.x - p3.x, p2.y - p3.y);
    if(theta > Pi)
        theta -= Pi * 2;
    if (theta < -Pi)
        theta += Pi * 2;
    theta = abs(theta * 180.0 / Pi);
    return theta;
}

struct query{
    int id;
    double sec;
    bool operator < (const query &r) const {
        return sec < r.sec;
    }
}q[maxm];

int n, m;
double tot;
double angle[maxn];
double ans[maxm];
double A, B, C;

void solve(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%lf %lf", &p[i].x, &p[i].y);
    }
    scanf("%d", &m);
    for(int i = 1; i <= m; i++) {
        scanf("%lf", &q[i].sec);
        q[i].id = i;
    }
    sort(q + 1, q + 1 + m);
    int now = 1;
    while(1) {
        A = B = C = 0;
        for(int i = 0; i < n; i++) {  // 求角平分线 true
            int nxt = (i + 1) % n;
            int pre = (i - 1 + n) % n;
            double d1 = p[i].distance(p[pre]);
            double d2 = p[i].distance(p[nxt]);
            Point tmp = p[i] + (p[nxt] - p[i]) * d1 / d2;
            Point mid = (tmp + p[pre]) / 2;
            L[i] = Line(p[i], mid);
        }
        for(int i = 0; i < n; i++) { // 求角平分线交点  true
            pos[i] = Cross_point(L[i].p1, L[i].p2, L[(i + 1) % n].p1, L[(i + 1) % n].p2);
            double d = p[i].distance(p[(i + 1) % n]);
            A += (p[i] ^ p[(i + 1) % n]) / 2;
            B += d;
            C += d * d / (fabs((p[(i + 1) % n] - pos[i]) ^ (p[i] - pos[i]))) * 0.5;
        }
        double minn = INF;
        for(int i = 0; i < n; i++) {
            double d = p[i].distance(pos[i]);
            int nxt = (i + 1) % n;
            int pre = (i - 1 + n) % n;
            angle[i] = getangle(p[nxt], p[pre], p[i]) / 2;
            angle[i] = sin(angle[i] * Pi / 180);
            double t = angle[i] * d;
            minn = min(t, minn);
        }
        while(1) {
            if(sgn(q[now].sec - tot - minn) > 0) break;
            double x = q[now].sec - tot;
            ans[q[now].id] = A - B * x + C * x * x;
            now++;
            if(now > m) break;
        }
        tot += minn;
        int num = 0;
        for(int i = 0; i < n; i++) {
            double d1 = minn / angle[i];
            double d2 = p[i].distance(pos[i]);
            p[i] = p[i] + (pos[i] - p[i]) * (d1 / d2);
        }
        for(int i = 0; i < n; i++) {
            if(p[i] == p[(i + 1) % n])
                continue;
            p[num++] = p[i];
        }
        n = num;
        if(n < 3) {
            for(int i = now; i <= m; i++) {
                ans[q[i].id] = 0;
            }
            break;
        }
    }
    for(int i = 1; i <= m; i++)
        printf("%.10f\n", ans[i]);
}

int main() {
//    freopen("in.txt","r",stdin);
//    freopen("out.txt", "w", stdout);
    int t = 1;
    // t = rd();
    // scanf("%d", &t);
    // cin >> t;
    while(t--)
        solve();
    PAUSE;
    return 0;
}

C - Delete Edges

题意： 给出一张完全图，每次可以删掉一个三元环，使得最后边数, 输出方案数量以及方案

题解： 结论题，输出的所有解。

#include<bits/stdc++.h>
using namespace std;

#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {   cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...);}

#define ll long long
#define ull unsigned long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define PII pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define PAUSE system("pause");
const double Pi = acos(-1.0);
const double eps = 1e-10;
const int maxn = 5e4 + 10;
const int maxm = 6e2 + 10;
const int mod = 998244353;
const int S = 5;

inline ll rd() {
    ll f = 0; ll x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}
void out(ll a) {if(a<0)putchar('-'),a=-a;if(a>=10)out(a/10);putchar(a%10+'0');}
#define pt(x) out(x),puts("")
inline void swap(ll &a, ll &b){ll t = a; a = b; b = t;}
inline void swap(int &a, int &b){int t = a; a = b; b = t;}
inline ll min(ll a, ll b){return a < b ? a : b;}
inline ll max(ll a, ll b){return a > b ? a : b;}
ll qpow(ll n,ll k,ll mod) {ll ans=1;while(k){if(k&1)ans=ans*n%mod;n=n*n%mod;k>>=1;}return ans%mod;}

int n;

void solve(){
    scanf("%d", &n);
    vector<pii> v;
    for(int i = 1; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            int k = (n - i - j + n) % n;
            if(k == 0) k = n;
            if(j < k) v.eb(mp(i, j));
        }
    }
    pt(v.size());
    for(auto g : v) {
        int k = (n - g.fi - g.se + n) % n;
        if(k == 0) k = n;
        printf("%d %d %d\n", g.fi, g.se, k);
    }
}

int main() {
//    freopen("in.txt","r",stdin);
//    freopen("out.txt", "w", stdout);
    int t = 1;
    // t = rd();
    // scanf("%d", &t);
    // cin >> t;
    while(t--)
        solve();
    PAUSE;
    return 0;
}

D - Gambling Monster

题意： 有一个转盘，每次转动得到 ~ (是的幂次)的概率分别给出。最开始你有一个数，每次转动转盘得到一个数，如果,就令,否则不变，求使,期望转动转盘的次数

题解： 设为转到的概率，表示从出发到的期望，表示转动一次转盘变大的概率，那么初始值，我们考虑从后往前转移，可以得到这样的式子。$yS(x)S(x) = \sum_{x \oplus y > x}p(y)yx00O(n\log{n})O(n^2)z > xcdqFWT$去解决。

#include<bits/stdc++.h>
using namespace std;

#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {   cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...);}

#define ll long long
#define ull unsigned long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define PII pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define PAUSE system("pause");
const double Pi = acos(-1.0);
const double eps = 1e-6;
const int maxn = 2e6 + 10;
const int maxm = 1e5 + 10;
const int mod = 1e9 + 7;

inline ll rd() {
    ll f = 0; ll x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}
void out(ll a) {if(a<0)putchar('-'),a=-a;if(a>=10)out(a/10);putchar(a%10+'0');}
#define pt(x) out(x),puts("")
inline void swap(ll &a, ll &b){ll t = a; a = b; b = t;}
inline void swap(int &a, int &b){int t = a; a = b; b = t;}
inline ll min(ll a, ll b){return a < b ? a : b;}
inline ll max(ll a, ll b){return a > b ? a : b;}
ll qpow(ll n,ll k,ll mod) {ll ans=1;while(k){if(k&1)ans=ans*n%mod;n=n*n%mod;k>>=1;}return ans%mod;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll n, a[maxn], p[maxn], s[maxn], sum, pre[maxn];
ll limit, lim, dp[maxn], A[maxn], B[maxn], ans[maxn];
ll add(ll a, ll b) {return a+b>=mod?a+b-mod:a+b;}

void FWTxor(ll *a, long long type) {
    int i, j, k, x, y;
    for (i = 1; i <= limit; i++)
        for (j = 0; j < (1 << limit); j += 1 << i)
            for (k = 0; k < (1 << i - 1); k++)
                x = (a[j | k] + a[j | (1 << i - 1) | k]) * type % mod,
                y = (a[j | k] - a[j | (1 << i - 1) | k] + mod) * type % mod,
                a[j | k] = x, a[j | (1 << i - 1) | k] = y;
}
void Xor(ll *ans, ll *a, ll *b) {
    FWTxor(a, 1);
    FWTxor(b, 1);
    for (int i = 0; i < (1 << limit); i++)
        a[i] = 1ll * a[i] * b[i] % mod;
    FWTxor(a, (mod + 1) >> 1);
    for (int i = 0; i < (1 << limit); i++)
        ans[i] = a[i];
}
void cdq(int l, int r) {
    int mid = (l + r) >> 1;
    if (l == r && l != n - 1){
        dp[l] = ((dp[l] + 1) * qpow(s[l], mod - 2, mod) % mod - 1 + mod) % mod;
    }
    if (l >= r)
        return;
    cdq(mid + 1, r);
    limit = 0;
    while ((1 << limit) < mid - l + 1)
        limit++;
    for (int i = 0; i <= (1 << limit); i++)
        A[i] = B[i] = ans[i] = 0;
    for (int i = mid + 1; i <= r; i++) {
        A[i - mid - 1] = p[i - l];
        B[i - mid - 1] = dp[i] + 1;
    }
    Xor(ans, A, B);
    for (int i = l; i <= mid; i++)
        dp[i] = (dp[i] + ans[i - l]) % mod;
    cdq(l, mid);
}

void solve(){
    scanf("%lld", &n);
    sum = 0;
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        sum = add(sum, a[i]);
        s[i] = pre[i] = dp[i] = 0;
    }
    int k = 0;
    while((1<<k)<n) k++;
    int invSum = qpow(sum, mod - 2, mod);
    for(int i = 0; i < n; i++) {
        p[i] = a[i] * invSum % mod;
        pre[i] = add(p[i], pre[i - 1]);
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < k; j++) {
            if(!((i>>j)&1)) {
                s[i] = add(s[i], (pre[(1 << (j + 1)) - 1] - pre[(1 << j) - 1] + mod) % mod);
            }   
        }
    }
    cdq(0, n - 1);
    printf("%lld\n", dp[0]);
}

int main() {
//    freopen("in.txt","r",stdin);
//    freopen("out.txt", "w", stdout);
    int t = 1;
    // t = rd();
    scanf("%d", &t);
    // cin >> t;
    while(t--)
        solve();
    PAUSE;
    return 0;
}

F - Hamburger Steak

solved by Sstee1XD & lllllan. 2:07(+)

题意：
n块牛排，m个烤盘，每块牛排要烤分钟，而且最多可以分两次烤，只要时间达到就行，输出最小花费时间时，每块牛排的烤制方案，按照时间顺序输出。

思路：
先考虑最优的方案，用总时间除以总盘数向上取整。此时，如果烤制最久的牛排需要的时间比这个想要的最优解要小的话，我们就可以直接开始放了，放到不够为止，再开下一个盘。因为需要最长的时间都能够符合，那么我把一块牛排拆成两份，按照顺序放在两个盘里，也不会有任何重合的部分。如果时间比最优解要大的话，就说明要满足这个最优解的话，切完这块牛排，放在不同的盘里会有重复的部分，不满足题目要求，所以把最优值取成这个最大值就是当前情况下的最优。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5 + 7;

struct Steak {
    int id;
    ll t;
    bool operator < (const Steak &a) const {
        return t > a.t;
    }
}s[N];
vector<tuple<int, ll, ll>> ans[N];
void run() {
    int n;
    ll m;
    scanf("%d %lld", &n, &m);
    ll sum = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &s[i].t);
        s[i].id = i;
        sum += s[i].t;
    }
    sort(s + 1, s + 1 + n);
    ll now = (sum + m - 1) / m;
    ll lst = m;
    ll l = 0, r = 0;
    int pos = 1;
    now = max(now, s[1].t);
    ll pan = now;
    while (pos <= n) {
        int aid = s[pos].id;
        ll t = s[pos].t;
        if (pan >= t) {
            ans[aid].push_back(make_tuple(lst, l, l + t));
            l += t;
            pan -= t;
        } else {
            ans[aid].push_back(make_tuple(lst, l, l + pan));
            t -= pan;
            lst--;
            l = 0;
            pan = now;
            ans[aid].push_back(make_tuple(lst, l, l + t));
            l += t;
            pan -= t;
        }
        if (pan == 0) {
            lst--;
            l = 0;
            pan = now;
        }
        pos++;
    }
    for (int i = 1; i <= n; ++i) {
        printf("%d", ans[i].size());
        if (ans[i].size() == 2) swap(ans[i][0], ans[i][1]);
        for (auto t : ans[i]) {
            int a;
            ll b, c;
            tie(a, b, c) = t;
            printf(" %d %lld %lld", a, b, c);
        }
        puts("");
    }
}

int main() {
    int t = 1;
    while (t--) run();
    return 0;
}

G - Hasse Diagram

题意： 对于正整数，定义为其所有因子组成的一张有向图，两个因子之间右边当且仅当他们的倍数是质数倍，定义为属于的边数，求

题解： 的范围来到了，不难发现这题得用亚线性筛来解决。赛时我的思路就到这了
对于一个，我们枚举任意一个它的质因数，可得这样的式子，我也不知道这式子是怎么推出来的，就枚举了几个数验证正确性
其中为的因子个数，可以和一起筛出来
改改板子就好了，知道了，则，要知道改哪里还是需要自己手推一遍min_25筛，第一天学这东西现在还是云里雾里的。

#include<bits/stdc++.h>
using namespace std;

#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {   cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...);}

#define ll long long
#define ull unsigned long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define PII pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define PAUSE system("pause");
const double Pi = acos(-1.0);
const double eps = 1e-10;
const int maxn = 1e6 + 10;
const int maxm = 6e2 + 10;
const int mod = 1145140019;

inline ll rd() {
    ll f = 0; ll x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}
void out(ll a) {if(a<0)putchar('-'),a=-a;if(a>=10)out(a/10);putchar(a%10+'0');}
#define pt(x) out(x),puts("")
inline void swap(ll &a, ll &b){ll t = a; a = b; b = t;}
inline void swap(int &a, int &b){int t = a; a = b; b = t;}
inline ll min(ll a, ll b){return a < b ? a : b;}
inline ll max(ll a, ll b){return a > b ? a : b;}
ll qpow(ll n,ll k,ll mod) {ll ans=1;while(k){if(k&1)ans=ans*n%mod;n=n*n%mod;k>>=1;}return ans%mod;}

ll prime[maxn],num,sp1[maxn];
ll n,Sqr,tot,g1[maxn],w[maxn],ind1[maxn],ind2[maxn];
bool flag[maxn];
void pre(int n){
    flag[1] = 1;
    for(int i = 1; i <= n; i++){
        if(!flag[i]) {
            prime[++num] = i;
            sp1[num] = (sp1[num - 1] + 1) % mod;
        }
        for(int j = 1; j <= num && prime[j] * i <= n; j++) {
            flag[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}
PII S(ll x,int y) {
    if(prime[y] >= x) return mp(0, 0);
    ll k = x <= Sqr ? ind1[x] : ind2[n / x];
    ll ansf = (g1[k] - sp1[y] + mod) % mod;
    ll ansd = (g1[k] - sp1[y] + g1[k] - sp1[y] + 2ll * mod) % mod;
    for(int i = y + 1; i <= num && prime[i] * prime[i] <= x; i++) {
        ll pe = prime[i];
        for(int e = 1; pe <= x; e++, pe = pe * prime[i]){
            PII tmp = S(x / pe, i);
            ansf = (ansf + (e + 1) * tmp.fi % mod + e * (tmp.se + (e > 1)) % mod) % mod;
            ansd = (ansd + (e + 1) * (tmp.se + (e > 1))% mod) % mod;
        }
    }
    return mp(ansf, ansd);
}
void solve() {
    scanf("%lld", &n);
    Sqr = sqrt(n);
    pre(Sqr);
    tot = 0;
    for(ll i = 1; i <= n; ){
        ll j = n / (n / i);
        w[++tot] = n / i;
        g1[tot] = (w[tot] - 1 + mod) % mod;
        if(n / i <= Sqr) ind1[n / i] = tot;
        else ind2[n / (n / i)] = tot;
        i = j + 1;
    }
    for(int i = 1; i <= num; i++) {
        for(int j = 1; j <= tot && prime[i] * prime[i] <= w[j]; j++) {
            ll k = w[j] / prime[i] <= Sqr ? ind1[w[j] / prime[i]] : ind2[n / (w[j] / prime[i])];
            g1[j] -= (g1[k] - sp1[i - 1] + mod) % mod;
            g1[j] %= mod;
            if(g1[j] < 0) g1[j] += mod;
        }
    }
    printf("%lld\n", (S(n, 0).fi) % mod);    
}
int main() {
    int t;
    scanf("%d", &t);
    while(t--) 
        solve();
    return 0;
}

H - Hopping Rabbit

题意：
二维平面，一些矩阵块不能进，你每次会上下左右选择一个方向，移动个单位。找一个起点，使得不管怎么走都不会走到非法矩阵块里。

思路：
可以看作人不动，矩阵块向人移动。因为每次移动的距离是一定的，所以在一个的矩阵里就可以表示出所有情况了。把所有非法矩阵往这个起点矩阵里移动，剩下的没有被覆盖掉的点就是合法起点。注意非法矩阵可能不会完全移动到起点矩阵里面，所以得上下左右都移动一下，把所有能被覆盖到的点都覆盖掉。

然后这道题就变成了在一个大矩阵中求没有被覆盖掉的矩阵。用扫描线维护下二维偏序就行。扫到一个矩阵的左边界时，将这块对应的值都，扫到右边界时，都，找区间最小值是否有为的，如果有就说明存在合法的点，找到其中一个输出即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 4e5 + 7;

int n, d;
const int inf = 0x3f3f3f3f;
struct ret{
    int x1, y1, x2, y2;
    ret(int _x1 = 0, int _y1 = 0, int _x2 = 0, int _y2 = 0) {
        x1 = _x1; x2 = _x2;
        y1 = _y1; y2 = _y2;
    }
}a[maxn];
vector<ret> add[maxn], del[maxn];

struct Seg {
    int t[maxn << 2], tag[maxn << 2];
    void up(int id) {
        t[id] = min(t[id << 1], t[id << 1 | 1]);
    }
    void build(int id, int l, int r) {
        t[id] = 0;
        tag[id] = 0;
        if (l == r) return;
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }
    void down(int id) {
        if (!tag[id]) return;
        tag[id << 1 | 1] += tag[id];
        tag[id << 1] += tag[id];
        t[id << 1] += tag[id];
        t[id << 1 | 1] += tag[id];
        tag[id] = 0;
    }
    void modify(int id, int l, int r, int ql, int qr, int v) {
        if (l >= ql && r <= qr) {
            tag[id] += v;
            t[id] += v;
            return;
        }
        down(id);
        int mid = l + r >> 1;
        if (ql <= mid) modify(id << 1, l, mid, ql, qr, v);
        if (qr > mid) modify(id << 1 | 1, mid + 1, r, ql, qr, v);
        up(id);
    }
    int query(int id, int l, int r) {
        if (t[id]) return -1;
        if (l == r) return l;
        down(id);
        int mid = l + r >> 1;
        if (!t[id << 1]) return query(id << 1, l, mid);
        else return query(id << 1 | 1, mid + 1, r);
    }
}seg;

void run() {
    scanf("%d %d", &n, &d);
    int num = 0;
    for(int i = 1, X1, X2, Y1, Y2; i <= n; i++) {
        scanf("%d %d %d %d", &X1, &Y1, &X2, &Y2);
        int tmpx = 0, tmpy = 0;
        if(X1 > 0) tmpx = -1 * X1 / d;
        if(X1 < 0) tmpx = (abs(X1) + d - 1) / d;
        if(Y1 > 0) tmpy = -1 * Y1 / d;
        if(Y1 < 0) tmpy = (abs(Y1) + d - 1) / d;
        X1 = X1 + tmpx * d;
        Y1 = Y1 + tmpy * d;
        X2 = X2 + tmpx * d;
        Y2 = Y2 + tmpy * d;
        if(X2 > d && Y2 > d) {
            a[++num] = ret(X1, Y1, d, d);
            // right
            a[++num] = ret(0, Y1, min(d, X2 - d), d);
            // top
            a[++num] = ret(X1, 0, d, min(d, Y2 - d));
            // right - top
            a[++num] =ret(0, 0, min(d, X2 - d), min(d, Y2 - d));
        }
        else if(X2 > d) {
            a[++num] = ret(X1, Y1, d, Y2);
            // right
            a[++num] = ret(0, Y1, min(d, X2 - d), Y2);
        }
        else if(Y2 > d) {
            a[++num] = ret(X1, Y1, X2, d);
            // top
            a[++num] = ret(X1, 0, X2, min(d, Y2 - d));
        }
        else {
            a[++num] = ret(X1, Y1, X2, Y2);
        }
    }
    for(int i = 1; i <= num; i++) {
        add[a[i].x1].push_back(a[i]);
        del[a[i].x2].push_back(a[i]);
    }
    // 输入y2-1,因为要加个0.5，所以上边界的点是合法的
    seg.build(1, 0, d - 1);
    for (int i = 0; i < d; ++i) {
        for (auto v : add[i]) {
            seg.modify(1, 0, d - 1, v.y1, v.y2 - 1, 1);
        }
        for (auto v : del[i]) {
            seg.modify(1, 0, d - 1, v.y1, v.y2 - 1, -1);
        }
        int y = seg.query(1, 0, d - 1);
        if (y >= 0) {
            puts("YES");
            printf("%d %d\n", i, y);
            return;
        }
    }
    puts("NO");
}

int main() {
    run();
    return 0;
}

I - Intervals on the Ring

题意： 给出一些不相交的区间，要求你构造出一些区间。使得你构造的区间取交集，等于题目给的区间取并集。构造不出输出-1

注意：如果区间其中，这种对应的区间应该是

思路： 首先，一定是构造的出来的。无论题目区间取并集一共有多少个连续的区间，都一定可以构造的出。

题目很友好地已经保证了区间不相交。只需要将所有区间，对其左端点进行排序，然后依次输出即可

举个栗子，有如下几个区间
我们依次输出

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e3 + 7;

int n, m;

struct node {
    int l, r;
    node () {}
    node (int l, int r) : l(l), r(r) {}
    friend bool operator<(const node& A, const node& B) {
        return A.l < B.l;
    }
} nodes[maxn];

void run() {
    scanf("%d%d", &n, &m);

    for (int i = 1, l, r; i <= m; ++i) {
        scanf("%d%d", &l, &r);
        nodes[i] = node(l, r);
    }

    sort(nodes + 1, nodes + m + 1);

    printf("%d\n", m);

    for (int i = 1; i <= m; ++i) {
        printf("%d %d\n", nodes[i].l, i == 1 ? nodes[m].r : nodes[i - 1].r);
    }

}

int main() {
    int t = 1;
    scanf("%d", &t);
    while (t--) run();
    return 0;
}

J - Defend Your Country

题意： 在一个无向连通图中，每个点都有点权。如果一个连通分量中点的个数是偶数，那么这些点的权值都不变；如果是奇数，则对这些权值取负。

你可以删除一些边，改变图的连通性，以获得最大的权值和。

思路： 我们的目的其实就是，删除一些边，使得有足够多的偶数点的连通分量。

关键信息：无向连通图。即输入给出的原图，已经是连通的，如果一共有偶数个点，那就无需做任何删除。

如果是奇数：那么最理想的是不是就是拆分成若干个偶数点的连通分量，以及一个落单的孤立点。于是我们想办法，要怎么确定这个 孤儿 孤立点。

  • 割点：假如我们分离出一个割点，改变了原图的连通性，那么我们还要检查剩下的连通分量中点的个数。 —— 如果还存在奇数个点的连通分量，那么这次分离，似乎是不划算的。
  • 非割点：我随意分离出去，并不影响剩下的图的连通性，反倒将奇数个点扭转成了偶数个点，稳赚不赔，找一个权值最小的非割点似乎是最划算的。

讨论，是不是在任何奇数点的情况下，都只需要删除一个点，就能获得最优解。

krx7qyjm.png

嘴笨说不清楚，就先附上别的聚聚的题解了，其题解链接

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e6 + 10;

int cnt, head[maxn];
struct edge {
    int v, next;
    edge() {}
    edge(int v, int next) : v(v), next(next) {}
} e[maxn << 2];

void add(int u, int v) {
    e[++cnt] = edge(v, head[u]), head[u] = cnt;
    e[++cnt] = edge(u, head[v]), head[v] = cnt;
}

int n, m;
int a[maxn];

int ans, tot;
int num[maxn];
int low[maxn];
int dfn[maxn];

void dfs(int u, int fa) {
    num[u] = 1;
    dfn[u] = low[u] = ++tot;

    int flag = 1;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if (v == fa) continue;

        if (!dfn[v]) {
            dfs(v, u);
            num[u] += num[v];
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u] && num[v] & 1) flag = 0;
        } else
            low[u] = min(low[u], dfn[v]);
    }

    if (flag) ans = min(ans, a[u]);
}

void run() {
    scanf("%d%d", &n, &m);

    ll sum = 0;
    cnt = tot = 0;
    for (int i = 1; i <= n; ++i) head[i] = num[i] = low[i] = dfn[i] = 0;

    for (int i = 1; i <= n; ++i) scanf("%d", a + i), sum += a[i];

    for (int i = 1, u, v; i <= m; ++i) {
        scanf("%d%d", &u, &v);

        add(u, v);
    }

    if (n % 2 == 0) return (void)(printf("%lld\n", sum));

    ans = 1e9 + 7;
    dfs(1, 0);

    printf("%lld\n", sum - 2 * ans);
}

int main() {
    int _ = 1;

    scanf("%d", &_);

    while (_--) run();

    return 0;
}
全部评论

相关推荐

04-22 16:50
已编辑
安徽农业大学 运营
点赞 评论 收藏
分享
昨天 07:41
同济大学 ARM工程师
点赞 评论 收藏
分享
02-24 14:18
北京邮电大学 Java
26界，开始准备大厂实习，之前有一段不知名小厂实习，求指教
简历还需要完善吗，boss投了一些没有面试机会。另外暑期开始，感觉自己太菜不敢投递
AAA不喝拿铁：校友好，开投就完事了！要准备面试的话更建议刷codetop，hot100有些题并不是面试常考题。另外想看刷题路线的可以看我的帖子，有讲怎么刷leetcode，除此之外可以看看我根据真实面经整理得到的最全（高/中/低频）面试题，加油
点赞 评论 收藏
分享
03-06 01:16
云南大学 Java
点赞 评论 收藏
分享
04-20 15:00
魔门塔（苏州）科技有限公司_感知算法工程师(准入职员工)
魔门塔momenta内推-内推码
真实工作体验纯手码在Momenta实习是我所有的实习中最忙碌也是最充实的一段。&nbsp;最开始在外企，基本是早9晚5，虽然是开发岗，但任务需求都很少，常常是我需要自己去找Mentor聊想法，自己给自己arrange一些任务，每天基本是回email、各种meeting、Leetcode，日子虽然很惬意，但感觉提升很少。之后去到小红书，工作经常是忙一阵闲一阵，正职们倒是都挺忙的，所以经常没空管我，最喜欢做的事情就是在完成Mentor布置的任务后，翻大家沉淀下来的各种业务文档，看大家的解决方案和业务逻辑，也是在努力赋予这段实习意义。&nbsp;来到Momenta后，真正的感受到了真正工作的强度。每天都会被各种各样的需...
Momenta公司福利 453人发布
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 京东美团大战，你怎么看？ #
36986次浏览 239人参与
# 一觉醒来，我成论文导师了… #
5107次浏览 101人参与
# 平安产险科技中心求职汇总 #
244939次浏览 2613人参与
# 实习进度记录 #
176486次浏览 2006人参与
# 毕业论文怎么查AI率 #
5473次浏览 295人参与
# 读研or工作，哪个性价比更高？ #
53714次浏览 651人参与
# 哪个瞬间让你对大厂祛魅了？ #
285378次浏览 2002人参与
# 24届的你们都什么时候入职？ #
54715次浏览 421人参与
# 我的求职精神状态 #
6616次浏览 124人参与
# 海康威视求职进展 #
62316次浏览 350人参与
# 摸鱼打卡站 #
36355次浏览 669人参与
# 机械人还在等华为开奖吗？ #
210153次浏览 1084人参与
# 好未来求职进展汇总 #
7447次浏览 60人参与
# 大疆求职进展汇总 #
469099次浏览 3169人参与
# 如果公司降薪，你会跳槽吗？ #
60803次浏览 481人参与
# 大城市找工作会更容易吗 #
18460次浏览 137人参与
# 小红书求职进展汇总 #
49973次浏览 445人参与
# 金山WPS工作体验 #
22359次浏览 140人参与
# 第一份工作应该选择高薪还是大平台 #
128878次浏览 809人参与
# 大家每天通勤多久？ #
32255次浏览 246人参与
# 互联网行业现在还值得去吗 #
5651次浏览 38人参与
牛客网
牛客企业服务