2022-10-11总结

Rainbow Rectangles

先枚举上下边界 $up,down$，考虑有多少满足条件的 $l,r$，如果直接枚举 $l$ 然后算 $r$ 的话时间至少是 $O(n^3 \log n)$ 的，但是可以倒着枚举上下边界，把加点改成删点，这样的话之前算出来的答案可以转移到现在，时间复杂度 $O(n^2 \log n)$ 。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

#define int long long 

typedef long long ll;
const int N = 2e3+10;
const int P = 1e9+7;

int n, k, L; ll ans;
int x[N], y[N], col[N];
int lshx[N], lshy[N], xcnt, ycnt;
vector<int> idx[N], idy[N];
multiset<int> s[N];
int pos[N];

namespace segment_tree {
    struct node {
        int l, r;
        int max, lz;
        ll val, sum;
    } a[N*4];
    void assign(int ql, int qr, ll val, int i = 1);
    void build(int l, int r, int i = 1);
    int query(ll val, int i = 1);
} using namespace segment_tree;

void prework();

signed main()
{
    cin >> n >> k >> L;
    for(int i = 1; i <= n; i++)
    {
        cin >> x[i] >> y[i] >> col[i];
        lshx[i] = ++x[i], lshy[i] = ++y[i];
    }
    
    prework();
    
    segment_tree::build(1, ycnt);
    
    for(int i = 1; i <= k; i++)
        s[i].insert(0), s[i].insert(ycnt+1);
    
    for(int i = 1; i <= xcnt; i++)
    {
        multiset<int> tmp;
        for(int j = 1; j <= k; j++)
            pos[j] = ycnt+1, tmp.insert(ycnt+1);
        
        for(int j = ycnt; j >= 1; j--)
        {
            for(auto z : idy[j])
                if(x[z] >= i)
                {
                    tmp.erase(tmp.find(pos[col[z]]));
                    pos[col[z]] = j, tmp.insert(pos[col[z]]);
                    s[col[z]].insert(j);
                }
            assign(j, j, lshy[*tmp.rbegin()]);
        }
        
        for(int j = xcnt; j >= i; j--)
        {
            (ans += (ll)(lshx[i]-lshx[i-1])%P * (lshx[j+1]-lshx[j])%P * (((ll)lshy[ycnt]*(L+1)%P-a[1].sum+P)%P)%P) %= P;
            for(auto z : idx[j])
            {
                s[col[z]].erase(s[col[z]].find(y[z]));
                int pre = *--s[col[z]].upper_bound(y[z]);
                int nxt = *s[col[z]].upper_bound(y[z]);
                if(pre+1 <= y[z])
                {
                    int w = min(query(lshy[nxt])-1, y[z]);
                    if(pre+1 <= w) assign(pre+1, w, lshy[nxt]);
                }
            }
        }
    }
    cout << ans << "\n";
}

void prework()
{
    sort(lshx+1, lshx+n+1);
    sort(lshy+1, lshy+n+1);
    xcnt = unique(lshx+1, lshx+n+1)-lshx-1;
    ycnt = unique(lshy+1, lshy+n+1)-lshy-1;
    lshx[xcnt+1] = L+1, lshy[ycnt+1] = L+1;
    for(int i = 1; i <= n; i++)
    {
        x[i] = lower_bound(lshx+1, lshx+xcnt+1, x[i])-lshx;
        y[i] = lower_bound(lshy+1, lshy+ycnt+1, y[i])-lshy;
        idx[x[i]].push_back(i), idy[y[i]].push_back(i);
    }
}

namespace segment_tree {
    #define ls (i<<1)
    #define rs (i<<1|1)
    void assign(node &i, ll val)
    {
        i.sum = val*i.val%P;
        i.max = i.lz = val;
    }
    void push_up(int i)
    {
        a[i].sum = (a[ls].sum + a[rs].sum)%P;
        a[i].max = max(a[ls].max, a[rs].max);
    }
    void push_down(int i)
    {
        if(!a[i].lz) return;
        assign(a[ls], a[i].lz);
        assign(a[rs], a[i].lz);
        a[i].lz = 0;
    }
    void build(int l, int r, int i)
    {
        a[i].l = l, a[i].r = r;
        if(l == r)
        {
            a[i].val = lshy[l]-lshy[l-1];
            return void();
        }
        int mid = (l+r)>>1;
        build(l, mid, ls);
        build(mid+1, r, rs);
        a[i].val = (a[ls].val + a[rs].val)%P;
    }
    void assign(int ql, int qr, ll val, int i)
    {
        if(ql <= a[i].l and a[i].r <= qr)
            return assign(a[i], val);
        push_down(i);
        if(ql <= a[ls].r) assign(ql, qr, val, ls);
        if(qr >= a[rs].l) assign(ql, qr, val, rs);
        push_up(i);
    }
    int query(ll val, int i)
    {
        if(a[i].max <= val) return ycnt+1;
        if(a[i].l == a[i].r)
            return a[i].l;
        push_down(i);
        if(a[ls].max > k)
            return query(val, ls);
        else
            return query(val, rs);
    }
}

Die Siedler

先把所有手牌等价地缩放到 $1$ 上(就是这个局面等价于多少张 $1$ 能换出来的局面) ，这样可以把每个局面用一个整数表示。】

因为 $2n$ 张 $n$ 号牌也能换成一张 $1$, 所以我们可以一圈一圈地一直换，设原先有 $x$ 张 $1$，最终可以得到 $x \bmod (2^n n! - 1)$ 张 $1$。

设第 $i$ 套卡包缩放到 $1$ 上对应数 $c_i$ ，初始有 $A$ 张 $1$, 那么最后得到的 $1$ 的个数

$$v = A + \sum_{i=1}^n c_ix_i - y(2^n n! - 1)$$

题目要求的就是所有 $v$ 中能换成的卡牌的最小数量。

由裴蜀定理知，$v-A$ 一定是 $\gcd(x_1, x_2, \cdots, x_n, 2^n n! -1)$ 的倍数。

设 $d = gcd(x_1, x_2, \cdots, x_n, 2^n n! -1)$，则 $v \equiv A \pmod d$。

直接枚举会 TLE，考虑根号分治:

若 $d > \sqrt{2^n n!}$，则直接暴力。

若 $d \le \sqrt{2^n n!}$ ，跑同余最短路：

把 $2^{k-1} (k-1)!$ 作为边权为 $1$ 的边，把所有边建出来跑 bfs 即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

#define ll long long
#define int long long

const int SIZE=65;
long long c[SIZE], s[SIZE][SIZE];
long long cnt1[SIZE];
long long fact[SIZE];

long long gcd(ll a, ll b)
{
    if(!b) return a;
    return gcd(b,a%b);
} void __init__(int n){
    fact[0]=1;
    for(int i=1;i<=n;i++)
        fact[i]=fact[i-1]*i;

}

ll dis[SIZE*100000];
bool vis[SIZE*100000];

void SPFA(int n,int d){

    queue<int> q;
    memset(dis,63,sizeof(dis));
    for(int i=1;i<=n;i++)
    {
        ll k=((1ll<<(i-1)))*fact[i-1]%d;
        dis[k]=1,vis[k]=1;
        q.push(k);
    }

    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=false;
        for(int i=1;i<=n;i++)
        {
            int v=(u+((1ll<<(i-1))*fact[i-1]))%d;
            if(dis[v]>dis[u]+1)
            {
                dis[v]=dis[u]+1;
                if(!vis[v])
                    q.push(v),vis[v]=true;
            }
        }
    }

}
 
signed main(){
 
    int n,m;
    cin>>n>>m;
 
    __init__(n);
 
    ll st=0;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
        st+=(c[i]<<(i-1))*fact[i-1];
    }
 
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>s[i][j];
            cnt1[i]+=(s[i][j]<<(j-1))*fact[j-1];
        }
    }
 
    ll lim=(1ll<<n)*fact[n];
    int d=lim-1;
    for(int i=1;i<=m;i++)
        d=gcd(d,cnt1[i]);        
     
    ll ans=1e18;
    if((__int128)d*d>lim)
    {
        for(ll v=st%d;v<lim;v+=d)
        {
            if(!v) continue;
            ll tmp=v,res=0;
            for(int i=1;i<=n;i++)
            {
                res+=tmp%(2*i);
                tmp/=2*i;
            }
            ans=min(ans,res);
        }
        cout<<ans;
    }
    else
    {
        SPFA(n,d);
        cout<<dis[st%d];
    }
    
    return 0;
    
}