2018 icpc 徐州

素颜马尾好姑娘i 2023-06-03 02:53 26阅读 0赞

## A ##

矩阵树定理可以用于最小生成树计数，最直观的做法就是求个mst，再用矩阵树定理求最小生成树个数，但是n<=1e5，显然不是o(n^3)可以做出来的。

考虑随机数据生成器，固定1e5的边，但是边权在unsigned long long的范围内随机指定，由样例看出，即使是点数很少的情况下，最多也只有一个生成树

于是，我们猜测，只需要做一遍最小生成树，并假定不会有更多的生成树就可以了。

#include<bits/stdc++.h>
    #define ull unsigned long long
    using namespace std;
    const int maxn = 100050;
    const ull mod = 1000000007;
    int f[maxn];
    int findf(int x){
        return f[x] == x ? x : f[x] = findf(f[x]); 
    }
    int n,m;
    ull k1,k2;
    struct edge{
        int u;
        int v;
        ull w;
        friend bool operator < (edge a,edge b){
            return a.w < b.w;
        }
    }e[maxn];
    ull xorS(){
        ull k3 = k1,k4 = k2;
        k1 = k4;
        k3 ^= k3 << 23;
        k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
        return k2 + k4;
    }
    int main(){
        int T;
        cin>>T;
        while(T--){
            cin>>n>>m>>k1>>k2;
            for(int i = 1;i <= m;i++){
                e[i].u = xorS() % n + 1;
                e[i].v = xorS() % n + 1;
                e[i].w = xorS();
            }
            sort(e+1,e+1+m);
            for(int i = 1;i <= n;i++){
                f[i] = i;
            }
            ull tot = 0;
            int uu,vv,cnt = 0;
            for(int i = 1;i <= m;i++){
                uu = e[i].u;
                vv = e[i].v;
                uu = findf(uu);
                vv = findf(vv);
                if(uu == vv) continue;
                else{
                    cnt++;
                    e[i].w %= mod;
                    tot = (tot + e[i].w) % mod;
                    f[uu] = vv;
                }
            }
            if(cnt != n-1) tot = 0;
            cout<<tot<<endl;
        }
        return 0;
    }

## G ##

选择k个路径，它们至少有一个交点，首先先把路径经过的点标记一下，对于一个点，它被选中，至少要有k个路径经过它。

这样就有一个需要考虑的地方，如果这k个路径有不止一个交点，就会被重复统计，如何去重？

两条路径的交点，只可能是树上连续的一段，所以多条路径的交点，也只能是树上的一段，对于一个方案，可以只在深度最小的那个点统计一次，而这个点，肯定是某个路径深度最小的点。

遍历每个点，新加进去以这个点为lca的路径，和经过这个点的其他路径联合起来算对方案的贡献。

如何快速计算一个点经过多少路径？可以让深度最深的点+1，走出这条路径或者达到交点（lca）时-1，也就是树上差分。

#include <iostream>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <queue>
    #include <vector>
    #define fo(i, l, r) for (long long i = l; i <= r; i++)
    #define fd(i, l, r) for (long long i = r; i >= l; i--)
    #define mem(x) memset(x, 0, sizeof(x))
    #define ll long long
    #define ld double
    using namespace std;
    const int maxn = 300050;
    const ll mod = 1e9 + 7;
    ll read()
    {
        ll x = 0, f = 1;
        char ch = getchar();
        while (!(ch >= '0' && ch <= '9'))
        {
            if (ch == '-')
                f = -1;
            ch = getchar();
        };
        while (ch >= '0' && ch <= '9')
        {
            x = x * 10 + (ch - '0');
            ch = getchar();
        };
        return x * f;
    }
    int n, m, k;
    vector<int> g[maxn];
    int d[maxn];
    int fa[maxn][25];
    void dfs(int u, int f, int deep)
    {
        d[u] = deep;
        fa[u][0] = f;
        int t = 0;
        while (fa[u][t] && fa[fa[u][t]][t])
        {
            fa[u][t + 1] = fa[fa[u][t]][t];
            t++;
        }
        int sz = (int)g[u].size() - 1, v;
        fo(i, 0, sz)
        {
            v = g[u][i];
            if (v == f)
                continue;
            dfs(v, u, deep + 1);
        }
    }
    int lca(int u, int v)
    {
        if (d[u] < d[v])
            swap(u, v);
        int delta = d[u] - d[v];
        int t = 0;
        while (delta)
        {
            if (delta & 1)
                u = fa[u][t];
            t++;
            delta >>= 1;
        }
        if (u == v)
            return u;
        t = 0;
        while (t >= 0)
        {
            if (fa[u][t] != fa[v][t])
            {
                u = fa[u][t];
                v = fa[v][t];
                t++;
            }
            else
            {
                t--;
            }
        }
        return fa[u][0];
    }
    int addamt[maxn], cf[maxn], uu[maxn], vv[maxn];
    
    ll fac[maxn], inv[maxn];
    ll ans;
    ll C(ll n, ll m)
    {
        return fac[n] * inv[m] % mod * inv[n - m] % mod;
    }
    void dfs2(int u)
    {
        int v, sz = (int)g[u].size() - 1;
        fo(i, 0, sz)
        {
            v = g[u][i];
            if (v == fa[u][0])
                continue;
            dfs2(v);
            cf[u] += cf[v];
        }
    }
    int main()
    {
        //freopen("data.in","r",stdin);
        fac[0] = fac[1] = 1;
        fo(i, 2, maxn - 1)
        {
            fac[i] = (fac[i - 1] * i) % mod;
        }
        inv[0] = inv[1] = 1;
        fo(i, 2, maxn - 1)
        {
            inv[i] = (mod - (mod / i)) * inv[mod % i] % mod;
        }
        fo(i, 2, maxn - 1)
        {
            inv[i] = (inv[i] * inv[i - 1]) % mod;
        }
        int T = read();
        while (T--)
        {
            memset(fa, 0, sizeof(fa));
            memset(d, 0, sizeof(d));
            ans = 0;
            n = read();
            m = read();
            k = read();
            fo(i, 1, n) g[i].clear();
            int u, v;
            fo(i, 1, n - 1)
            {
                u = read();
                v = read();
                g[u].push_back(v);
                g[v].push_back(u);
            }
            fo(i, 1, m)
            {
                uu[i] = read();
                vv[i] = read();
            }
            dfs(1, 0, 1);
            fo(i, 1, n) cf[i] = addamt[i] = 0;
            int zz, cd;
            fo(i, 1, m)
            {
                zz = lca(uu[i], vv[i]);
                addamt[zz]++;
                cf[uu[i]]++;
                cf[vv[i]]++;
                cf[zz]--;
                cf[fa[zz][0]]--;
            }
            dfs2(1);
            fo(i, 1, n)
            {
                cf[i] -= addamt[i];
                fo(j, 1, addamt[i])
                {
                    
                    
                    if (j > k)
                        break;
                    if (cf[i] >= k - j){
                        ans = (ans + C(cf[i], k - j) * C(addamt[i], j) % mod) % mod;
                    }
                }
            }
            printf("%lld\n", ans);
        }
        return 0;
    }

## H ##

如果区间的数量不大于颜色数，那么每个区间染上不同的颜色就可以了。

如果有断层，尽量染上缺少的颜色，如果区间比较多，如何确保染到一个最优的颜色？

某些颜色在大于某个位置就没有了，如果染上那个最早失效的颜色，就可能会使答案增大。

对于每个颜色，维护一个它消失的位置，每次取出那个消失位置最靠前的染色。

这个题spj有毛病，行尾有空格算你wa，是真的无语。

## M ##

首先预处理每个灯照亮的边，它是一段连续的区间。

能不能照亮某个边，需要 点与边的两个端点的连线不经过凸包内部，可以利用叉积快速判断，逆时针方向下只要点在边的右边就可以。

处理之后，要做一个线段覆盖，由于是环，需要做n次

#include <iostream>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <stack>
    #include <vector>
    #include <set>
    #include <cmath>
    #include <queue>
    #include <map>
    #include <ctime>
    #define ll long long
    #define ld double
    #define lson rt << 1, l, m
    #define pi acos(-1)
    #define rson rt << 1 | 1, m + 1, r
    #define fo(i, l, r) for (int i = l; i <= r; i++)
    #define fd(i, l, r) for (int i = r; i >= l; i--)
    #define mem(x) memset(x, 0, sizeof(x))
    #define eps 1e-11
    using namespace std;
    const ll maxn = 2050;
    const ll mod = 998244353;
    ll read()
    {
        ll x = 0, f = 1;
        char ch = getchar();
        while (!(ch >= '0' && ch <= '9'))
        {
            if (ch == '-')
                f = -1;
            ch = getchar();
        };
        while (ch >= '0' && ch <= '9')
        {
            x = x * 10 + (ch - '0');
            ch = getchar();
        };
        return x * f;
    }
    int sgn(double x)
    {
        if (fabs(x) < eps)
            return 0;
        if (x < 0)
            return -1;
        else
            return 1;
    }
    struct Point
    {
        double x, y;
        Point() {}
        Point(double _x, double _y)
        {
            x = _x;
            y = _y;
        }
        double operator^(const Point &b) const
        {
            return x * b.y - y * b.x;
        }
        double operator*(const Point &b) const
        {
            return x * b.x + y * b.y;
        }
        Point operator-(const Point &b) const
        {
            return Point(x - b.x, y - b.y);
        }
    } pts[maxn],bulb[maxn];
    struct Line
    {
        Point s, e;
        Line() {}
        Line(Point _s, Point _e)
        {
            s = _s;
            e = _e;
        }
        int linecrossseg(Line v)
        {
            int d1 = sgn((e - s) ^ (v.s - s));
            int d2 = sgn((e - s) ^ (v.e - s));
            if ((d1 ^ d2) == -2)
                return 2;
            return (d1 == 0 || d2 == 0);
        }
        int relation(Point p)
        {
            int c = sgn((p - s) ^ (e - s));
            if (c < 0)
                return 1;
            else if (c > 0)
                return 2;
            else
                return 3;
        }
        bool parallel(Line v)
        {
            return sgn((e - s) ^ (v.e - v.s)) == 0;
        }
        int linecrossline(Line v)
        {
            if (this->parallel(v))
                return v.relation(s) == 3;
            return 2;
        }
        Point crosspoint(Line v)
        {
            double a1 = (v.e-v.s) ^ (s-v.s);
            double a2 = (v.e-v.s) ^ (e-v.s);
            return Point((s.x * a2-e.x * a1) / (a2-a1), (s.y * a2-e.y * a1) / (a2-a1));
        }
    }A,B;
    int n,m;
    int lp[maxn],rp[maxn];
    int rec[maxn],tmp[maxn];
    int ans,tot;
    struct dat{
        int p,l,r;
        friend bool operator < (dat a,dat b){
            if(a.l != b.l) return a.l < b.l;
            else return a.r > b.r;
        }
    }dats[maxn];
    int main()
    {
        int T=read();
        while(T--){
            n=read();m=read();
            fo(i,1,m) lp[i]=rp[i]=0;
            fo(i,1,n){
                pts[i].x=read();
                pts[i].y=read();
                pts[n+i] = pts[i];
            }
            fo(i,1,m){
                bulb[i].x=read();
                bulb[i].y=read();
                bool lst=false,cur=false;
                rp[i]=n;
                fo(j,1,n){
                    A = Line(pts[j],pts[j+1]);
                    if(A.relation(bulb[i])!=2)cur=false;
                    else cur=true;
                    if(!lst&&cur) lp[i]=j;
                    if(lst&&!cur){
                        rp[i]=j-1;
                    }
                    lst = cur;
                }
                if(rp[i]<lp[i])rp[i]+=n;
                dats[i].l=lp[i];dats[i].r=rp[i];dats[i].p=i;
            }
            sort(dats+1,dats+1+m);
            ans = m + 1;
            fo(t,1,n){
                tot = 0;
                int pt = t,pp,vv=-1;
                fo(i,1,m){
                    tmp[i]=false;
                }
                fo(i,1,m){
                    if(pt >= t+n)break;
                    if(dats[i].l > pt){
                        pt = vv + 1;
                        tot++;
                        tmp[pp]=true;
                    }                
                    if(dats[i].l<=pt&&dats[i].r>=pt){
                        if(vv<dats[i].r){
                            pp=dats[i].p;
                            vv=dats[i].r;
                        }
                    }
                }
                if(pt<t+n && vv>=t+n-1){
                    pt = vv+1;
                    tot++;
                    tmp[pp]=true;
                }
                if(pt>=t+n&&ans>tot){
                    ans=tot;
                    fo(i,1,m) rec[i]=tmp[i];
                }
            }
            if(ans==m+1){
                printf("-1\n");
                continue;
            }
            printf("%d\n",ans);
            bool fst=true;
            fo(i,1,m){
                if(rec[i]){
                    if(fst) fst=false;
                    else putchar(' ');
                    printf("%d",i);
                }
            }
            putchar('\n');
        }
        return 0;
    }

##  I ##

要构造一个最长上升子序列长度至少为n-1的序列，可以让一个数移动到另一个数后边，这样就有o(n^2）个

每个序列，经过排序之后，若符合条件，那么一定在这些目标序列之内。

可以倒着枚举哪些排序器起到了作用。

转载于:https://www.cnblogs.com/hyfer/p/11588333.html