2018年2月

Problem

给定一个环,每个节点有一个所属国家,k次事件,每次对[l,r]区间上的每个点点权加上一个值,求每个国家最早多少次操作之后所有点的点权和能达到一个值

Konachan.com - 259853 blush boots cyan hoodie hoshizora_rin love_live!_school_idol_project orange_hair short_hair tagme_(artist) yellow_eyes.png

Solution

感谢@陈常杰的题解。

所谓整体二分呢,就是....
我也不知道是啥

嘛,就讲讲这题的做法。
首先想到二分。对每个国家进行二分时间来找答案。
然而这么做,一个国家可以,那么多国家怕是吃不消。

于是就干脆所有国家一起处理。

一开始定时间为0到t+1(共t次操作),那么mid就是操作的中间一个。把1~mid的操作全部执行,看看哪些国家已经满足,满足的放到A集合,不满足的放到B集合。然后带着A集合里的国家递归左边二分(时间为0~mid),因为A集合中的国家已经满足,那么把他们的时间缩小;同理B集合里的国家右边二分(时间为mid+1~t+1)。当时间的左右端点相同的时候,端点就是当前集合里国家所需要的时间。如果时间为t+1的话,就是永远无法满足。

你认为这样时间复杂度会很大?平摊下来其实只有$O(nlog^2n)$。
如何验证国家是否满足,我们就一个个操作来作就行(线段树会被卡,得用树状数组),但是下一层递归得充分利用上一层已做的操作,节省时间。
那么具体怎么做呢?

请看下面的代码,我猜您看完后会大呼一声:妙!

当然如果没有也当我没说,因为我菜

使用全局变量一定要谨慎。一般尽量就别用。

Code

// Code by ajcxsu
// Problem: meteor

#include<bits/stdc++.h>
#define INF (0x3f3f3f3f)
using namespace std;

const int N=3e5+10;
typedef long long ll;
struct Con {
    int l,r,a;
} con[N];
ll need[N];
vector<int> lab[N];
int now;
int n,m,t;

ll C[N];
#define lowbit(x) x&-x
inline void updata(int x,int d) {
    while(x) {
        C[x]+=d;
        x-=lowbit(x);
    }
}
inline ll query(int x) {
    ll ret=0;
    while(x<=m) {
        ret+=C[x];
        x+=lowbit(x);
    }
    return ret;
}

int X[N],A[N],B[N],pa,pb;
int tim[N];
void div(int l,int r,int tl,int tr) {
    if(l>r) return;
    if(tl==tr) { for(int i=l;i<=r;i++) tim[X[i]]=tl; return;}
    int mid=(tl+tr)>>1;
    while(now<mid) {
        now++;
        if(con[now].l<=con[now].r) {
            updata(con[now].l-1,-con[now].a), updata(con[now].r,con[now].a);
        }
        else {
            updata(con[now].l-1,-con[now].a), updata(m,con[now].a);
            updata(con[now].r,con[now].a);
        }
    }
    while(now>mid) {
        if(con[now].l<=con[now].r) {
            updata(con[now].l-1,con[now].a), updata(con[now].r,-con[now].a);
        }
        else {
            updata(con[now].l-1,con[now].a), updata(m,-con[now].a);
            updata(con[now].r,-con[now].a);
        }
        now--;
    }
    int pa=pb=0;
    int cnt=0,len;
    for(int i=l;i<=r;i++) {
        cnt=0;
        len=lab[X[i]].size();
        for(int j=0;j<len;j++) cnt+=query(lab[X[i]][j]);
        if(cnt>=need[X[i]]) A[pa++]=X[i];
        else B[pb++]=X[i];
    }
    for(int i=l;i<=l+pa-1;i++) X[i]=A[i-l];
    for(int i=l+pa;i<=r;i++) X[i]=B[i-l-pa];
    div(l,l+pa-1,tl,mid), div(l+pa,r,mid+1,tr);
}

int main() {
    scanf("%d%d",&n,&m);
    int na;
    for(int i=1;i<=m;i++) scanf("%d",&na), lab[na].push_back(i);
    for(int i=1;i<=n;i++) scanf("%lld",&need[i]), X[i]=i;
    scanf("%d",&t);
    for(int i=1;i<=t;i++) scanf("%d%d%d",&con[i].l,&con[i].r,&con[i].a);
    div(1,n,0,t+1);
    for(int i=1;i<=n;i++)
        if(tim[i]>t) printf("NIE\n");
        else printf("%d\n",tim[i]);
    return 0;
}

Problem

你有一组非零数字(不一定唯一),你可以在其中插入任意个0,这样就可以产生无限个数。比如说给定{1,2},那么可以生成数字12,21,102,120,201,210,1002,1020,等等。

现在给定一个数,问在这个数之前有多少个数。(注意这个数不会有前导0).

范围:n长度不超过50。答案不超过$2^{63}-1$

Solution

题解由@noob提供。
洛谷题解可见。地址:https://www.luogu.org/blog/CSGO/solution-p2518

由于0置于最前面代表前导零,则求所有比数字n小的排列即可。

则首先枚举最大位数。
然后枚举最高位的数字,接着算方案数。
然后最大位的数字固定为原位数字上限,位数-1,继续枚举最高位,算方案数。
所有方案数相加即可。

已知位数m和每个数字i(0~9)的个数ai。怎么求组合方案数? 假设我们先把0固定。则方案数为$C(m,a_0)$。然后再把1固定,则方案数为$C(m-a_0,a_1)$。以此类推。 按照乘法原理,最终答案是$C(m,a_0)C(m-a_0,a_1)C(m-a_0-a_1,a_2)...$。若$a_i=0$,则不参与讨论。

Code

// Code by ajcxsu
// Sol by @Ju_Xing_Fang_Kuai

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1010;
long long f[N][N];

ll C(int i,int j) {
    if(i==j || j==0) return 1;
    if(f[i][j]) return f[i][j];
    f[i][j]=C(i-1,j)+C(i-1,j-1);
    return f[i][j];
}

int n;
int v[100],a[20];

ll deal() {
    int m=n;
    ll ret=1;
    for(int i=0;i<=9;i++)
        if(a[i]) ret*=C(m,a[i]), m-=a[i];
    return ret;
}

int main() {
    char ch;
    while(cin>>ch)
        if(isdigit(ch)) v[n++]=ch-'0', a[v[n-1]]++;
    int nn=n;
    ll ans=0;
    for(int i=0;i<nn;i++) {
        n--;
        for(int j=0;j<v[i];j++)
            if(a[j]) { a[j]--; ans+=deal(); a[j]++; }
        a[v[i]]--;
    }
    cout<<ans<<endl;

    return 0;
}