ex题解

CodeForces - 1216F

题意

$n$ 个房间拍成一排，标号为 $1\sim n$ ，要联网的花费为 $i$ ，一些房间可以装 $Wi-Fi$ ，使得 $[i-k,i+k]$ 的房间都有 $Wi-Fi$ ，问最小花费。

题解

$dp[i]$ 表示前 $i$ 个房间通网的最小花费，初始化为 $\large dp[i]=\frac {(n+1)*n}2$ ，

$$\large \left\{ \begin{array}{c} dp[i]=min(dp[i],dp[i-1]+i)&s[i]=='1'\ or\ s[i]=='0'\\ dp[i+k]=min(dp[i+k],min(dp[i-k-1,i+k])+i)&s[i]=='1' \end{array} \right.$$

区间最小值使用树状数组维护

代码

char s[N];
ll dp[N],h[N];
int lowbit(int x){
    return x&(-x);
}
int n;
void update(int p,ll x){
  	dp[p]=x;
    while(p<=n){
        h[p]=min(h[p],x);
        p+=p&-p;
    }
}
ll query(int l,int r){
    if(l==0)return 0;
    ll ans = 1e18;
    while(l<=r){
      	ans = min(ans,dp[r]);
      	r--;
		for(; l<=r-lowbit(r) ;r-=lowbit(r))ans = min(ans,h[r]);
    }
    return ans;
}
void change(int id,ll v){
    if(v<dp[id]){
        update(id,v);
    }
}
int main() {
    int k;
    memset(h,inf,sizeof(h));
    in(n,k);
    in(s+1);  
    for (int i = 1; i <= n; i++)update(i,dp[i-1]+i);
    for (int i = 1; i <= n; i++){
        change(i,dp[i-1]+i);
        if(s[i]=='1'){
            int id=min(n,i+k);
            change(id,query(max(i-k-1,0),id)+i);
            // change(id,query(i,id)+i);
        }
    }
    out(dp[n],1);
    return 0;
}

## 51nod-2571 楼梯数字 ### 题意 问有多少长度为 $n(1\le n\le 1e18)$ 的数字（无前导零），满足后一位都不小于前一位，且是 $k(2\le k\le 500)$ 的倍数。 ### 题解 显然这样的阶梯数字是由 $1,11,111,1111,\cdots$ 构成的，我们将这 $n$ 种数按照 $\mod k$ 分类，用 $cnt[i]$ 计数， $dp[i][j]$ 表示使用 $i$ 个数字，其和 $\mod k=j$ 的方案数 ### 代码

ll cnt[600],dp[11][600];
ll inv[20],fac[20];
ll qPow(ll a,ll b,ll c){
    ll ans=1;
    a%=c;
    while(b){
        if(b%2)ans=ans*a%c;
        a=a*a%c;
        b/=2;
    }
    return ans;
}
void init(){//快速计算阶乘的逆元
    fac[0]=fac[1]=1;
    for(int i=2;i<N;i++)fac[i]=fac[i-1]*i%mod;
    inv[N-1] = qPow(fac[N-1], mod - 2, mod);
  	for (int i = N - 2; i >= 0; i--) inv[i] = (inv[i + 1] * (i + 1)) % mod;
}
ll C(ll n,ll m){
    if(n<m)return 0;
    ll ans=1;
    for(ll i=n-m+1;i<=n;i++){
        ans=i%mod*ans%mod;
    }
    return ans*inv[m]%mod;
}
int main() {
    init();
    ll n,k;
    in(n,k);
    vii v;
    map<int,int>ma;
    v.pu_b(0);
    int pre=1;
    int l,r;//记录循环节
    for(int i=1;;i++){
        if(ma.count(pre)){
            l=ma[pre];
            break;
        }else{
            v.pu_b(pre);
            ma[pre]=i;
            r=i;
            pre=(pre*10+1)%k;
        }
    } 
    int last;
    if(n<=r){
        for (int i = 1; i <= n; i++){
            cnt[v[i]]++;
        }
        last=v[n];
    }else{
        for (int i = 1; i <= r; i++){
            cnt[v[i]]++;
        }
        n-=r;
        ll shang=n/(r-l+1),yu=n%(r-l+1);
        for (int i = l; i <= r; i++){
            cnt[v[i]]+=shang;
        }
        for (int i = 1; i <= yu; i++){
            cnt[v[l+i-1]]++;
        }
        if(yu)last=v[l+yu-1];
        else last=v[r];
    }
    dp[1][last]=1;
    for (int i = 0; i < k; i++){//要增加的块
        for (int j = 8; j >0; j--){//从后往前，避免重复计数
            for (int p = 0; p < k; p++){
                for (int q = 1; q <= 9-j; q++){
                    dp[j+q][(p+i*q)%k]=(dp[j+q][(p+i*q)%k]+dp[j][p]*C(cnt[i]+q-1,q)%mod)%mod;
                }
            }
        }
    }
    ll ans=0;
    for (int i = 1; i <= 9; i++){
        ans=(ans+dp[i][0])%mod;
    }
    out(ans,1);
    return 0;
}

## 2019-牛客day1-XOR ### 题意 给 $n(1\le n\le 1e5)$ 个数 $0\le a_i\le1e18$ ，求 $\Large\left(\sum_{S \subseteq A, \oplus_{x \in S} x=0}|S|\right) \bmod \left(10^{9}+7\right)$ ### 题解 对一个数 $a_i$ ，我们求其贡献，将其加入另外 $n-1$ 个数构成的线性基，如果能加入则没有贡献，如果不能加入，则其贡献为 $\large2^{n-1-cnt}$ ，因为对于除线性基外的 $n-1-cnt$ 个数构成的任意集合与 $a_i$ 的异或和都能够由**线性基里的一些元素**异或得到。 维护一个后缀线性基，在从前往后处理，若当前值为 $a_i$ ，前缀线性基为 $pre$ ，若 $a_i$ 不能加入线性基，则其对应的 $cnt$ 为所有 $n$ 个元素的线性基的元素个数，反之，我们需要将 $pre$ 与 $suf[i+1]$ 合并来求 $cnt$ 。显然能加入的个数只有 $\mathcal O(\log a)$ ，所以复杂度为 $\mathcal{O}(n\log a+\log ^3a)$ ### 代码

struct da{
    ll d[70];
    int cnt;
    bool add(ll x){
        for(int i=63;i>=0;i--){
            if(x&(1ll<<i)){
                if(d[i])x^=d[i];
                else{
                    cnt++;
                    d[i]=x;
                    return 1;
                }
            }
        }
        return 0;
    }
    void merge(da y){
        for(int i=63;i>=0;i--){
            if(y.d[i])add(y.d[i]);
        }
    }
    void init(){
        cnt=0;
        memset(d,0,sizeof(d));
    }
}suf[N],tm;
ll po[N];
ll a[N];

int main() {
    int n;
    ll ans;
    po[0]=1;
    for (int i = 1; i < N; i++)po[i]=po[i-1]*2%mod;
    while(~in(n)){
        tm.init();
        ans=0;
        for (int i = 0; i < n; i++)in(a[i]);
        suf[n].init();
        for(int i=n-1;i>=0;i--){
            suf[i]=suf[i+1];
            suf[i].add(a[i]);
        }
        for (int i = 0; i < n; i++){
            da tt=tm;
            if(tt.add(a[i])){//最多只有60次
                suf[i+1].merge(tm);
                if(!suf[i+1].add(a[i])){
                    ans=(ans+po[n-1-suf[i+1].cnt])%mod;
                }
            }else{
                ans=(ans+po[n-1-suf[0].cnt])%mod;
            }
            tm.add(a[i]);
        }
        out(ans,1);
    }
    return 0;
}

UVA - 10535 - Shooter

题意

给 $n$ 个线段，给一个点，从这个点引一条射线，问最多可以与几个线段相交

题解

• 法一：

  暴力枚举方向（ $2*n$ 个端点）

• 法二：

  对所有端点极角排序，这样问题就转化成了区间最大覆盖问题了，注意因为极角排序会将点按照 $[-\pi,\pi]$ 排序，我们需要特殊考虑跨越 $-\pi,\pi$ 的区间，还有当两点的极角相同时，要将区间的左端点放在前面

代码

struct Point{
    ll x,y;
    int id;
    bool type;
    int ty2;
    Point(){}
    Point(ll _x,ll _y) : x(_x),y(_y){}
    Point operator - (const Point &k1) const{return Point(x-k1.x,y-k1.y);}
    db operator ^ (const Point b) const{return x * b.y - y * b.x;}//叉积,顺时针为负
    bool operator < (const Point k1) const{//极角排序
        int p1=sign(y)==1||(sign(y)==0&&sign(x)==-1),p2=sign(k1.y)==1||(sign(k1.y)==0&&sign(k1.x)==-1);
        if(p1==p2&&sign(*this^k1)==0){
            return ty2<k1.ty2;
        }
        return p1<p2||(p1==p2&&sign(*this^k1)>0);
    }
};
typedef Point Vector;
bool vis[N];
Vector a[N];
int main() {
    int n;
    while(~in(n)&&n){
        memset(vis,0,sizeof(vis));
        for (int i = 0; i < 2*n; i+=2){
            in(a[i].x,a[i].y);
            in(a[i+1].x,a[i+1].y);
            a[i].id=a[i+1].id=i/2;
        }
        int x,y;
        in(x,y);
        int cnt=0;
        for (int i = 0; i < 2*n; i+=2){
            a[i].x-=x;
            a[i].y-=y;
            a[i+1].x-=x;
            a[i+1].y-=y;
            if(a[i].y>a[i+1].y)swap(a[i],a[i+1]);
            if(a[i].y<0&&a[i+1].y>=0&&sign((a[i].x*a[i+1].y-a[i].y*a[i+1].x)/(db)(a[i+1].y-a[i].y))==-1){
                a[i].type=a[i+1].type=1;
                cnt++;
                if(a[i]<a[i+1]){
                    a[i].ty2=1;a[i+1].ty2=0;
                }else{
                    a[i].ty2=0;a[i+1].ty2=1;
                }
            }else {
                a[i].type=a[i+1].type=0;
                if(a[i]<a[i+1]){
                    a[i].ty2=0;a[i+1].ty2=1;
                }else{
                    a[i].ty2=1;a[i+1].ty2=0;
                }
            }
        }
        sort(a,a+2*n);
        int ans=cnt;
        for (int i = 0; i < 2*n; i++){
            if(a[i].type){
                if(vis[a[i].id]){
                    cnt++;
                    ans=max(ans,cnt);
                }else{
                    cnt--;
                    vis[a[i].id]=1;
                }
            }else{
                if(vis[a[i].id]){
                    cnt--;
                }else{
                    vis[a[i].id]=1;
                    cnt++;
                    ans=max(ans,cnt);
                }
            }
        }
        out(ans,1);
    }
    return 0;
}

题目

题意

题解

代码