牛客多校第六场题解

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;
}
全部评论

相关推荐

10-21 11:13
海康威视_产品经理(准入职员工)
海康威视内推，海康威视内推码
海康首先给我的感觉是人真的好多，尤其食堂的人，我可能上学都没有见过这么多人，还有电梯，我每次坐是一头雾水。当然这些对于我来说都不是很重要。&nbsp;可能很多人最关心的就是海康的工作强度和时间是不是真如网上说的那么严重，而通过这段时间的感受，我觉得海康可能是我节奏最慢的一次体验，完成了任务就可以开开心心的回家了，根本不需要无效加班，如果自己想学点产品类的知识还是可以在公司里多学一点的。&nbsp;关于部门小组氛围，我一开始是有点惊讶的，主管和我说这里扁平化管理。我们组可以说是神仙小组了，不用无效加班，请教主管问题都会随时给你解答，大主管也会给你安排学习计划。小组成员也都非常年轻，总之是很棒的。&nbsp;关于学到的东西，我...
海康威视公司氛围 916人发布
点赞 评论 收藏
分享
10-23 16:35
门头沟学院 运营
点赞 评论 收藏
分享
10-16 16:32
字节跳动_广告_后端开发工程师(准入职员工)
这素什么情况
二面完进录用评估了？
Java面试先知：我也是和你一样的情况，hr 说等开奖就行了
点赞 评论 收藏
分享
09-16 02:14
东北大学 图像识别
点赞 评论 收藏
分享
10-21 23:48
已编辑
东南大学 Java
科大讯飞timeline 2025.10.21 意向
2025.9.23&nbsp;一面&nbsp;（压力面）35min这个面试官沟通起来非常费劲，喜欢东一句西一句，回答起来超级累。介绍第一段实习项目用到了哪些接口？查到了哪些信息？怎么样组成的一套完整的业务的？不知道面试官想表达啥，我说了我用到的接口，说了怎么使用的，他却说哪些是我做的，这不都是其他团队提供的吗？可是这不是你刚才问的我用到了哪些接口吗？有点搞不懂他想问什么我刚开始介绍了一遍项目，他又说有没有复杂点的业务设计到多服务能力支持的，刚才讲的那个业务已经够复杂了，然后我又介绍了一遍可订态的计算流程，难崩，不知道他想问啥。接着又问我调了哪些接口，我又讲了一遍我调的接口，怎么使用的。说着说着，又给我打断了，逆天...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 牛客树洞，我想对你说 #
14787次浏览 117人参与
# 求职中的尴尬瞬间 #
6377次浏览 53人参与
# 快手技术岗信息交流阵地 #
6756次浏览 52人参与
# 牛客周边新品开箱 #
11559次浏览 91人参与
# 大学最后一个寒假，我想…… #
55098次浏览 600人参与
# 牛友的志愿填报指南 #
36274次浏览 188人参与
# 应届生被毁约被毁意向了怎么办 #
47592次浏览 280人参与
# 如何KTV领导 #
73928次浏览 505人参与
# 研究所笔面经互助 #
97589次浏览 550人参与
# 怎么给家人解释你的工作？ #
14928次浏览 87人参与
# 国企还是互联网，你怎么选？ #
172331次浏览 1305人参与
# 得物app工作体验 #
29802次浏览 69人参与
# 硬件人的春招flag #
52806次浏览 435人参与
# 机械人避雷的岗位/公司 #
29901次浏览 249人参与
# 你的mentor是什么样的人？ #
18718次浏览 119人参与
# 帮我看看，领导说这话什么意思？ #
24840次浏览 107人参与
# 打工人锐评公司红黑榜 #
175836次浏览 1023人参与
# 大疆工作体验 #
19869次浏览 85人参与
# 校招泡的最久的公司是哪家？ #
15446次浏览 92人参与
# 机械人集合！你是什么工程师？ #
21035次浏览 91人参与
# 今年形式下双非本找得到工作吗 #
239610次浏览 1435人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务