骚猪代码仓库v2补充包

ACM

线段相交

struct point{
    double x, y;
    point():x(0), y(0){}
    point(double _x, double _y): x(_x),y(_y){}
    inline void read(){
        scanf("%lf%lf", &x, &y);
    }
    point operator + (const point &a) const {
        return point(x+a.x, y+a.y);
    }
    point operator - (const point &a) const {
        return point(x-a.x, y-a.y);
    }
    point operator * (const double &k) const {
        return point(x * k, y * k);
    }
    double operator ^ (const point &a) const {  // det
        return x*a.y - y*a.x;
    }
    double dis(const point &b) {
        return (x-b.x)*(x-b.x) + (y-b.y)*(y-b.y);
    }
    inline void print(){
        printf("point: (%.2lf, %.2lf)\n", x, y);
    }
    bool onSeg(point P1, point P2){
        point Q = point(x, y);
        if (min(P1.x,P2.x) > Q.x || Q.x > max(P1.x,P2.x)) return false;
        if (min(P1.y,P2.y) > Q.y || Q.y > max(P1.y,P2.y)) return false;
        double ans = fabs((Q - P1) ^ (Q - P2));
        //printf("??? = %.4lf\n", ans);
        if (fabs((Q - P1) ^ (Q - P2)) > 0) return false;
        return true;
    }
} A, B, C;
double s(point p, point a, point b){
    return fabs((p - a) ^ (p - b));
}
bool inTra(point P, point A, point B, point C){
    double s1 = s(P, A, B), s2 = s(P, B, C), s3 = s(P, C, A);
    if (s1 == 0 || s2 == 0 || s3 == 0) return false;
    double a =  s1 + s2 + s3;
    double b = s(A, B, C);
    //printf("%.2lf\n", a-b);
    return fabs(a - b) == 0.;
}
bool segXseg(point p1, point p2, point p3, point p4){
    // attention, not good
    if (p1.onSeg(p3, p4) || p2.onSeg(p3, p4)) return false;
    if (p3.onSeg(p1, p2) || p4.onSeg(p1, p2)) return false;
    //---------------------------------------------
    if (max(p1.x, p2.x) < min(p3.x, p4.x)) return 0;
    if (max(p1.y, p2.y) < min(p3.y, p4.y)) return 0;
    if (max(p3.x, p4.x) < min(p1.x, p2.x)) return 0;
    if (max(p3.y, p4.y) < min(p1.y, p2.y)) return 0;//ju xin shi yan
    double x = (p3 - p1) ^ (p2 - p1);
    double y = (p4 - p1) ^ (p2 - p1);
    double z = (p1 - p3) ^ (p4 - p3);
    double w = (p2 - p3) ^ (p4 - p3); //KuaLi
    return x*y <= 0 && z*w <= 0;
}
bool xj(point p1, point p2, point A, point B, point C){  //xiangjiao
    //for (double k = 0.01; k < 1; k += 0.01) // seg & tra
        //if (inTra((p1*k + p2*(1-k)), A, B, C)) return true;
    if (inTra(p1*0.01 + p2*0.99, A, B, C)) return true;
    if (inTra(p1*0.99 + p2*0.01, A, B, C)) return true;
    if (segXseg(p1, p2, A, B)) return true;
    if (segXseg(p1, p2, A, C)) return true;
    if (segXseg(p1, p2, C, B)) return true;
    return false;
}

匈牙利

#include<bits/stdc++.h>
using namespace std;
const int N = 200 + 7;
const int INF = 0x3f3f3f3f;
struct Hungary{
    vector <int> G[N];
    bool used[N];// main里面记得memset
    int girl[N], n;
    inline void init(int _n){
        n = _n;
        for (int i = 0; i <= n; i++) G[i].clear();
    }
    inline void addEdge(const int &u, const int &v){
        G[u].push_back(v);
        //printf("addEdge %d %d\n", u, v);
    }
    bool Find(int x){
        for (int i = 0; i < G[x].size(); i++){    //扫描每个妹子
            int j = G[x][i];
            if (used[j]) continue;
            // 如果有暧昧并且还没有标记过
            // (这里标记的意思是这次查找曾试图改变过该妹子的归属问题，
            // 是没有成功，所以就不用瞎费工夫了）
            used[j] = 1;
            if (girl[j] == -1 || Find(girl[j])) {
                //名花无主或者能腾出个位置来，这里使用递归
                girl[j] = x;
                return true;
            }
        }
        return false;
    }
    inline int hungary(const int &n, const int &m){
        int all = 0;
        memset(girl, -1, sizeof girl);
        for (int i = 0; i < n; i++) {
            memset(used, 0, sizeof(used)); //这个在每一步中清空
            if (Find(i)) all += 1;
        }
        //for (int i = 0; i < m; i++) printf("girl[%d] = %d\n", i, girl[i]);
        //printf("all = %d\n", all);
        return all;
    }
} hg;

一个哈希版和一个stdio

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAXN = 5e4 + 5;
const LL MAXNN = 3e5 + 5;
const LL base = 29;
const LL base2 = 31;
const LL MOD = 1e9 + 7;
LL p[MAXNN], Hash[MAXN], len[MAXN];
string s[MAXN];
vector<LL> vec[MAXN];
LL getval(LL i, LL j, LL m) {
    return ((vec[i][j+m] - vec[i][j] * p[m]) % MOD + MOD) % MOD;
}
bool ok(int m, int n) {
    if(m > len[0]) return false;
    set<LL> myset;
    for(int i = 1; i < n; i++) {
        if(len[i] < m) continue;
        for(int j = 0; j <= len[i] - m; j++) {
            myset.insert(getval(i, j, m));
        }
    }
    for(int i = 0; i <= len[0] - m; i++) {
        if(myset.find(getval(0, i, m)) == myset.end()) return true;
    }
    return false;
}
void init() {
    p[0] = 1;
    for(LL i = 1; i < MAXNN; i++) {
        p[i] = (p[i - 1] * base) % MOD;
    }
}
int main(){
    std::ios::sync_with_stdio(false);
    init();
    LL _;
    cin >> _;
    for (LL n, cas = 1; cas <= _; cas++){
        cin >> n;
        for(int i = 0; i <= n; i++) vec[i].clear();
        for(LL i = 0; i < n; i++) {
            cin >> s[i];
            len[i] = s[i].length();
            LL tmp = 0;
            vec[i].push_back(0);
            for(int j = 0; j < len[i]; j++) {
                tmp = (tmp * base + s[i][j] - 'a') % MOD;
                vec[i].push_back(tmp);
            }
        }
        LL l = 0, r = len[0] + 1, mc = log(len[0]) / log(2) + 2;
        for(LL i = 0; i < mmc; i++) {
            LL m = (l + r) / 2;
            if(ok(m, n)) r = m;
            else l = m;
        }
        if(r > len[0]) cout << "Impossible" << endl;
        else           cout << getans(r, n) << endl;
    }
    return 0;
}

双指针尺取法

int cal(int n, int m, char c) {
    int ans = 0;
    int cnt = 0;
    int l = 0, k = 0, mx = 0;
    for(int r = 0; r < n; r++) {
        if(s[r] != c) k++;
        while(k > m) {
            if(s[l++] != c) k--;
        }
        mx = max(mx, r - l + 1);
    }
    return mx;
}