8/2 小白月赛33 C H J

没写完，J 线段相交，花的时间太久了，一开始想用向量写，发现不会向量写法；用直线，求面积的时候传错参数，调了好久， $H$ 原本有点头绪的，但是也没时间想了。

C

分析 ：

如果要进行最小交换的话，得先找出从 $i -> to[i] -> to[to[i]] -> … -> i$ 这个环，然后对于每个环，假设环长为 $K$ ，则可以通过 $K - 1$ 次交换完成这 $K$ 个酒瓶的归位， 而如果要使这个交换的成本最小， 可以考虑每次利用环内最小值进行交换，即先找到环内最小重量酒瓶， 然后以它开始，倒着去交换（假设最小值对应的位置是 $to[i]$ ,而环内前面一个数是 $i$ ，那么就是 $swap(i,to[i])$ ，然后 旧$to[i]$ 就成了 环内 旧$i$的 前一个数假设是 $j$ 的 $to[j]$ 。这样的话，我们可以通过 $K - 1$ 次交换，以 环内酒瓶重量和 + $K - 2$ 个最小酒瓶重量 $Minn$ 的成本完成 $K$ 个酒瓶的归位 。除此之外，还有一种可能，那就是用 全局最小重量的酒瓶 和 环内最小重量的酒瓶 做一个交换，这样的话，可以将 全局最小重量的酒瓶所在的环 和 当前所在环合并 。 接着，就是在这个新环内以每一次 全局最小重量 $minn$ 的价值 + 环内元素的重量的成本 进行交换，对于 原环来说，他对答案的贡献就是 $minn$ + $Minn$ + 原环内酒瓶重量和 + $K * minn$ 。

对于每个环，在这两个答案取个 $min$ 即可

G

环形数组，首先扩展数组为 $2n$，然后由于数组和为零，所以每 $n$ 个数必定为零，因此转移的时候必定会使用到$f[i - n / 2]$，因此可以进行 $DP$

#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'

using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;

const int maxn = 2e5 + 10 ;
int a[maxn] ;
int f[maxn] ;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1 ;
    cin >> T ;
    rep(test,1,T + 1){
        unordered_map<int,int> M ;
        int n ;
        cin >> n ;
        rep(i,1,n + 1) cin >> a[i],a[i + n] = a[i] ;
        n <<= 1;
        M[0] = 0 ;
        int res = 0 ;
        rep(i,1,n + 1) {
            if (i >= n / 2) M[0] = max(M[0],i - n / 2) ;
            a[i] += a[i - 1] ;
            if (M.count(a[i]) && i - M[a[i]] <= n / 2)
                f[i] = f[M[a[i]]] + 1 ;
            else 
                f[i] = 0 ;
            if (i >= n / 2)
                res = max(res,f[i] - f[i - n / 2]) ;
            M[a[i]] = i ;
        }
        cout << res << endl ;
    }

    return 0;
}

H

因为没有路径流量限制，所以找到最短路之后，猛走就可以了，直接 $floyd$

#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'

using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;

const int maxn = 210 ;
ll dis[maxn][maxn] ;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1 ;
    cin >> T ;
    rep(test,1,T + 1){
        memset(dis,0x3f,sizeof dis) ;
        int n,m,s,e,f ;
        cin >> n >> m >> s >> e >> f ;
        rep(i,1,m + 1) {
            int a,b,d;
            ll c,c_;
            cin >> a >> b >> c >> d >> c_ ;
            if (d <= f)
                c = (c * d) + (c_ * (f - d)) ;
            else 
                c = c * f;
            dis[a][b] = min(dis[a][b],c) ;
        }
        rep(i,1,n + 1) dis[i][i] = 0 ;
        rep(k,1,n + 1) rep(i,1,n + 1) rep(j,1,n + 1) dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]) ;
        cout << dis[s][e] << endl ;
    }

    return 0;
}

I

可以发现，每次只能取奇数个球，因此，因为n <= 2 的时候 $Alice$必赢，后面的每两轮一奇数，每两轮换一次赢家 。

#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'

using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;

const int maxn = 2e5 + 10 ;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1 ;
    cin >> T ;
    rep(test,1,T + 1){
        int n ;
        cin >> n ;
        -- n ;
        n %= 4 ;
        if (n < 2) cout << "Alice" << endl ;
        else cout << "Bob" << endl ;
    }

    return 0;
}

j

求直线，看有无交点，求两个三角形的面积

#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'

using namespace std;
using ll = long long ;
using ad2 = array<double,2> ;

const int maxn = 10 ;
mt19937 rnd(233) ;
struct line {
    double k,b ;
    int st = 0 ;
    double lx,rx,ly,ry ;
    void mk(ad2 &a, ad2 &b) {
        lx = min(a[0],b[0]) ;
        rx = max(a[0],b[0]) ;
        ly = min(a[1],b[1]) ;
        ry = max(a[1],b[1]) ;
        if (fabs(a[0] - b[0]) < 1e-8) {
            st = 1;
            k = 1e18 ;
            return ;
        }
        k = (a[1] - b[1]) / (a[0] - b[0]) ;
        this->b = a[1] - k * a[0] ;
    }
};

ad2 pt[maxn] ;
line a,b;

inline double get_d(ad2 a,ad2 b) {
    return __builtin_sqrt((a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1])) ;
}

ostream& operator<<(ostream &os,const ad2 &a) {
    for (auto t : a) os << t << ' ' ;
    cout << endl;
    return os ;
}
inline double cal(ad2 a,ad2 b,ad2 c) {
    double ab = get_d(a,b),ac = get_d(a,c),bc = get_d(b,c) ;   
    double p = (ab + ac + bc) / 2 ;
    // cout << __builtin_sqrt(p * (p - ab) * (p - bc) * (p - ac)) << endl ;
    return __builtin_sqrt(p * (p - ab) * (p - bc) * (p - ac)) ;
}
inline bool check(line l1,line l2) {
    if (l1.st && l2.st) return false;
    if (l2.st == 1) swap(l1,l2) ;
    if (l1.st == 1) {
        if (fabs(l2.k) < 1e-8) {
            return l1.lx >= l2.lx && l1.lx <= l2.rx && l2.ly >= l1.ly && l2.ly <= l2.ry ;
        }
        double x = l1.lx ;
        if (x < l2.lx || x > l2.rx ) return false ;
        double y = l2.k * x + l2.b ;
        return y >= l1.ly && y <= l1.ry ;        
    }
    double x = (l2.b - l1.b) / (l1.k - l2.k) ;
    double y = l1.k * x + l1.b ;
    if (x < l1.lx || x > l1.rx || x < l2.lx || x > l2.rx) return false ;
    return true ;
}

inline void solve(){
    if (fabs(a.k - b.k) < 1e-8 || !check(a,b)) {
        cout << 0 << endl ;
        return ;
    } 
    cout << fixed << setprecision(10) << cal(pt[1],pt[2],pt[3]) + cal(pt[1],pt[2],pt[4]) << endl ;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    rep(i,1,5) cin >> pt[i][0] >> pt[i][1] ;
    a.mk(pt[1],pt[2]) ;
    b.mk(pt[3],pt[4]) ;
    solve() ;
    return 0;
}