[BZOJ 2038]小Z的袜子

今年第一更……噫

终于学会莫队了,不过目前只能做这样的模板题……

代码:

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <utility>
using namespace std;
const int maxn=50005;
typedef long long ll;
ll gcd(ll a,ll b){
    if(!b){
        return a;
    }else{
        return gcd(b,a%b);
    }
}
ll C2(ll n){
    register ll temp,ns1=n-1;
    if(n&1){
        temp=ns1>>1;
        return temp*n;
    }else{
        temp=n>>1;
        return temp*ns1;
    }
}
 
struct Node{
    int L_s;
    int L,R;
    int id;
    ll ans1,ans2;
};
bool cmp1(const Node& a,const Node& b){
    if(a.L_s==b.L_s){
        return a.R<b.R;
    }else{
        return a.L_s<b.L_s;
    }
}
bool cmp2(const Node& a,const Node& b){
    return a.id<b.id;
}
Node Q[maxn];
int C[maxn],d[maxn];
int n,m;
inline void add_p(int x,ll &ans){
    d[x]++;
    ans+=d[x]-1;
}
inline void sub_p(int x,ll &ans){
    d[x]--;
    ans-=d[x];
}
inline void Mo(){
    register int i,j,L_p,R_p,sqrt_n=sqrt(n+0.5);
    register ll ans,t_gcd,t2;
    for(i=1;i<=m;i++){
        Q[i].L_s=Q[i].L/sqrt_n;
    }
    sort(Q+1,Q+1+m,cmp1);
    L_p=R_p=Q[1].L;
    ans=0;
    d[C[L_p]]++;
    for(i=1;i<=m;i++){
        while(L_p<Q[i].L){
            sub_p(C[L_p],ans);
            L_p++;
        }
        while(L_p>Q[i].L){
            L_p--;
            add_p(C[L_p],ans);
        }
        while(R_p<Q[i].R){
            R_p++;
            add_p(C[R_p],ans);
        }
        while(R_p>Q[i].R){
            sub_p(C[R_p],ans);
            R_p--;
        }
        t2=C2(R_p-L_p+1);
        t_gcd=gcd(ans,t2);
        Q[i].ans1=ans/t_gcd;
        Q[i].ans2=t2/t_gcd;
    }
    sort(Q+1,Q+1+m,cmp2);
}
 
int main(){
    register int i;
    int a,b;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&C[i]);
    }
    for(i=1;i<=m;i++){
        Q[i].id=i;
        scanf("%d%d",&a,&b);
        Q[i].L=a;
        Q[i].R=b;
    }
    Mo();
    for(i=1;i<=m;i++){
        printf("%lld/%lld\n",Q[i].ans1,Q[i].ans2);
    }
    return 0;
}

[BZOJ 1798]维护序列

万年不更的zzs出现了……

这个题以前竟然没做……近几天做了一下,首交竟然unAC……看样子是我真不会线段树了。

这题不难,唯一需要注意的是乘法标记对加法标记也有影响,而且下传要乘法优先。

代码(警告:此代码exciting):

/**************************************************************
    Problem: 1798
    User: danihao123
    Language: C++
    Result: Accepted
    Time:7696 ms
    Memory:10980 kb
****************************************************************/
 
#include <cstdio>
typedef long long ll;
const int maxn=100005;
ll ha;
struct Node{
    ll sumv;
    int L,R;
    ll addv,mulv;
    Node *lc,*rc;
    Node(ll v,int pos){
        sumv=v%ha;
        addv=0;
        mulv=1;
        L=R=pos;
        lc=rc=NULL;
    }
    Node(Node *l,Node *r,int Le,int Ri){
        sumv=0;
        addv=0;
        mulv=1;
        L=Le;
        R=Ri;
        lc=l;
        rc=r;
    }
    void paint_add(ll v){
        v=v%ha;
        addv=(addv+v)%ha;
        ll add_v=(v*((R-L+1)%ha))%ha;
        sumv=(sumv+add_v)%ha;
    }
    void paint_mul(ll v){
        v=v%ha;
        addv=(addv*v)%ha;
        mulv=(mulv*v)%ha;
        sumv=(sumv*v)%ha;
    }
    void maintain(){
        if(lc!=NULL && rc!=NULL){
            sumv=(lc->sumv+rc->sumv)%ha;
        }
    }
    void pushdown(){
        if(mulv!=1){
            if(lc!=NULL){
                lc->paint_mul(mulv);
            }
            if(rc!=NULL){
                rc->paint_mul(mulv);
            }
            mulv=1;
        }
        if(addv!=0){
            if(lc!=NULL){
                lc->paint_add(addv);
            }
            if(rc!=NULL){
                rc->paint_add(addv);
            }
            addv=0;
        }
    }
};
 
ll A[maxn];
void build_tree(Node* &o,int L,int R){
    if(L==R){
        o=new Node(A[L],L);
    }else{
        int M=L+(R-L)/2;
        Node *lc,*rc;
        build_tree(lc,L,M);
        build_tree(rc,M+1,R);
        o=new Node(lc,rc,L,R);
        o->maintain();
    }
}
Node *root;
int ql,qr;
ll v;
ll query_sum(Node *o){
    int L=o->L,R=o->R;
    o->pushdown();
    if(ql<=L && R<=qr){
        return o->sumv;
    }else{
        int M=L+(R-L)/2;
        ll ans=0;
        if(ql<=M){
            ans=(ans+query_sum(o->lc))%ha;
        }
        if(qr>M){
            ans=(ans+query_sum(o->rc))%ha;
        }
        return ans;
    }
}
void update_add(Node *o){
    int L=o->L,R=o->R;
    o->pushdown();
    if(ql<=L && R<=qr){
        o->paint_add(v);
    }else{
        int M=L+(R-L)/2;
        if(ql<=M){
            update_add(o->lc);
        }
        if(qr>M){
            update_add(o->rc);
        }
        o->maintain();
    }
}
void update_mul(Node *o){
    int L=o->L,R=o->R;
    o->pushdown();
    if(ql<=L && R<=qr){
        o->paint_mul(v);
    }else{
        int M=L+(R-L)/2;
        if(ql<=M){
            update_mul(o->lc);
        }
        if(qr>M){
            update_mul(o->rc);
        }
        o->maintain();
    }
}
 
int main(){
    register int i;
    int n,m,op;
    scanf("%d%lld",&n,&ha);
    // ha=0x7fffffff;
    for(i=1;i<=n;i++){
        scanf("%lld",&A[i]);
    }
    build_tree(root,1,n);
    scanf("%d",&m);
    while(m--){
        scanf("%d%d%d",&op,&ql,&qr);
        if(ha==1){
            if(op==3){
                puts("0");
            }else{
                scanf("%lld",&v);
            }
            continue;
        }
        if(op==1){
            scanf("%lld",&v);
            update_mul(root);
        }else{
            if(op==2){
                scanf("%lld",&v);
                update_add(root);
            }else{
                printf("%lld\n",query_sum(root));
            }
        }
    }
    return 0;
}

[COGS 741]负载平衡

这个网络流题挺简单的……

首先从[tex]S[/tex]向每个点连容量为该点存货量的边(费用为0)。首先注意最后所有存货量都要变成总的平均值,所以要从每个点向[tex]T[/tex]连一条容量为总的平均值的边(费用为0)。最后根据题目要求在相邻点之间连边(容量都是无限大,费用为1)。

跑一遍最小费用最大流,得出的费用就是答案。

代码:

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=110;
namespace MCMF{
	struct Edge{
        int u,v,cap,flow,cost;
    };
    vector<Edge> edges;
    vector<int> G[maxn];
    int m;
    inline void AddEdge(int u,int v,int cap,int cost){
        edges.push_back((Edge){u,v,cap,0,cost});
        edges.push_back((Edge){v,u,0,0,-cost});
        m=edges.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }
    int a[maxn];
    bool inQueue[maxn];
    int d[maxn],p[maxn];
    bool BellmanFord(int s,int t,long long& cost){
        register int i,u;
        queue<int> Q;
        memset(d,0x7f,sizeof(d));
        memset(inQueue,0,sizeof(inQueue));
        d[s]=0;
        inQueue[s]=true;
        p[s]=0;
        a[s]=0x7f7f7f7f;
        Q.push(s);
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            inQueue[u]=false;
            for(i=0;i<G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if(e.cap>e.flow && d[e.v]>d[u]+e.cost){
                    d[e.v]=d[u]+e.cost;
                    p[e.v]=G[u][i];
                    a[e.v]=min(a[u],e.cap-e.flow);
                    if(!inQueue[e.v]){
                        Q.push(e.v);
                        inQueue[e.v]=true;
                    }
                }
            }
        }
        if(d[t]==0x7f7f7f7f)
            return false;
        cost+=((long long)d[t])*((long long)a[t]);
        for(u=t;u!=s;u=edges[p[u]].u){
            edges[p[u]].flow+=a[t];
            edges[p[u]^1].flow-=a[t];
        }
        return true;
    }
    long long MincostMaxflow(int s,int t){
        register long long ans=0;
        while(BellmanFord(s,t,ans));
        return ans;
    }
};

int A[maxn];
int main(){
	register int i,ave=0;
	int n;
	freopen("overload.in","r",stdin);
	freopen("overload.out","w+",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&A[i]);
		ave+=A[i];
		MCMF::AddEdge(0,i,A[i],0);
	}
	ave/=n;
	for(i=1;i<=n;i++){
		MCMF::AddEdge(i,n+1,ave,0);
		if(i>1){
			MCMF::AddEdge(i-1,i,0x7f7f7f7f,1);
			MCMF::AddEdge(i,i-1,0x7f7f7f7f,1);
		}
		if(i<n){
			MCMF::AddEdge(i+1,i,0x7f7f7f7f,1);
			MCMF::AddEdge(i,i+1,0x7f7f7f7f,1);
		}
	}
	MCMF::AddEdge(1,n,0x7f7f7f7f,1);
	MCMF::AddEdge(n,1,0x7f7f7f7f,1);
	printf("%lld\n",MCMF::MincostMaxflow(0,n+1));
	fclose(stdin);
	fclose(stdout);
	return 0;
}

[BZOJ 3155]Preprefix sum

蛮有意思的一题……

考虑询问[tex]SS_i[/tex],[tex][1,i][/tex]中的每个位置[tex]j[/tex]在答案中被计算的次数为[tex]i-j+1[/tex],然后式子就可以变成这样:

[tex]\Sigma_{j=1}^{i} A[j]*(i-j+1)[/tex]

[tex](i+1)*\Sigma_{j=1}^{i} A[j]-\Sigma_{j=1}^{i} A[j]*j[/tex]

这样问题就简单多了,开两个树状数组乱搞搞即可。

代码:

/**************************************************************
    Problem: 3155
    User: danihao123
    Language: C++
    Result: Accepted
    Time:464 ms
    Memory:3164 kb
****************************************************************/
 
#include <cstdio>
#include <cstdlib>
const int maxn=100005;
typedef long long ll;
int n;
ll A[maxn];
ll C_1[maxn]; // 正常的BIT
inline int lowbit(int x){
    return x&(-x);
}
inline void add(int p,ll v){
    while(p<=n){
        C_1[p]+=v;
        p+=lowbit(p);
    }
}
inline ll sum(int p){
    register ll ans=0;
    while(p>0){
        ans+=C_1[p];
        p-=lowbit(p);
    }
    return ans;
}
ll C_2[maxn]; // 累积的BIT
inline void add_2(int p,ll v){
    register int pos=p;
    while(pos<=n){
        C_2[pos]+=((ll)p)*v;
        pos+=lowbit(pos);
    }
}
inline ll sum_2(int p){
    register ll ans=0;
    while(p>0){
        ans+=C_2[p];
        p-=lowbit(p);
    }
    return ans;
}
 
int main(){
    int m,p;
    ll v;
    register int i;
    char *buf=(char*)calloc(10,1);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%lld",&A[i]);
        add(i,A[i]);
        add_2(i,A[i]);
    }
    while(m--){
        scanf("%s%d",buf,&p);
        if(buf[0]=='Q'){
            printf("%lld\n",((ll)p+1LL)*sum(p)-sum_2(p));
        }else{
            scanf("%lld",&v);
            add(p,v-A[p]);
            add_2(p,v-A[p]);
            A[p]=v;
        }
    }
    free(buf);
    return 0;
}

[BZOJ 3333]排队计划

传说中的大结论题TAT

假设每个数的后面小于它的数的个数为[tex]f[i][/tex](其位置为[tex]i[/tex]),那么逆序对数显然为[tex]\Sigma f[i][/tex]。

每次操作,只需要将涉及到的数的[tex]f[i][/tex]清为0即可。

为什么呢?任何数的后面比他小的数肯定也被一起拉出来排序了,所以这些数的[tex]f[i][/tex]要被清零。其他数为什么不收这个影响呢?因为这之后的比他小的位置,有的可能没被操作,有的可能被操作了。但是就算被操作了,放到后面位置的数照样会比这个数小(因为这个数如果在第一个选定位置的后面(在前面更是不受影响)还没被操作,肯定比那个第一个位置数还大)。

还有一个细节,一个被操作过的数不需要再被操作一遍,操作完了直接设为INF即可。

代码:

/**************************************************************
    Problem: 3333
    User: danihao123
    Language: C++
    Result: Accepted
    Time:7920 ms
    Memory:24264 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <utility>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=500005;
const int maxnode=maxn*4;
const int INF=0x7fffffff;
int A[maxn];
pii minv[maxnode];
inline void maintain(int o){
    minv[o]=min(minv[o<<1],minv[o<<1|1]);
}
void build_tree(int o,int L,int R){
    if(L==R){
        minv[o]=make_pair(A[L],L);
    }else{
        int M=L+(R-L)/2;
        build_tree(o<<1,L,M);
        build_tree(o<<1|1,M+1,R);
        maintain(o);
    }
}
int ql,qr;
pii query_min(int o,int L,int R){
    if(ql<=L && R<=qr){
        return minv[o];
    }else{
        int M=L+(R-L)/2;
        pii ans=make_pair(INF,INF);
        if(ql<=M)
            ans=min(ans,query_min(o<<1,L,M));
        if(qr>M)
            ans=min(ans,query_min(o<<1|1,M+1,R));
        return ans;
    }
}
int p;
void update(int o,int L,int R){
    if(L==R){
        minv[o].first=INF;
    }else{
        int M=L+(R-L)/2;
        if(p<=M)
            update(o<<1,L,M);
        else
            update(o<<1|1,M+1,R);
        maintain(o);
    }
}
 
int lsh_siz;
int C[maxn];
inline int lowbit(int x){
    return x&(-x);
}
inline void add(int p){
    while(p<=lsh_siz){
        C[p]++;
        p+=lowbit(p);
    }
}
inline int sum(int p){
    int ans=0;
    while(p>0){
        ans+=C[p];
        p-=lowbit(p);
    }
    return ans;
}
 
inline int readint(){
    register int x;
    register char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[21];
template<typename T>
inline void putint(T x){
    register int i,p=0;
    if(!x){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(i=p-1;i>=0;i--)
        putchar(bf[i]+'0');
    putchar('\n');
}
int n;
int A2[maxn],f[maxn];
int main(){
    register int i,m,pos;
    register ull ans=0;
    pii temp;
    n=readint();
    m=readint();
    for(i=1;i<=n;i++){
        A[i]=readint();
        A2[i]=A[i];
    }
    sort(A2+1,A2+1+n);
    lsh_siz=unique(A2+1,A2+1+n)-A2-1;
    for(i=n;i>=1;i--){
        pos=lower_bound(A2+1,A2+1+lsh_siz,A[i])-A2;
        f[i]=sum(pos-1);
        ans+=f[i];
        add(pos);
    }
    putint(ans);
    build_tree(1,1,n);
    while(m--){
        pos=readint();
        ql=pos;
        qr=n;
        while(true){
            temp=query_min(1,1,n);
            if(temp.first>A[pos])
                break;
            p=temp.second;
            ans-=f[p];
            f[p]=0;
            update(1,1,n);
        }
        putint(ans);
    }
    return 0;
}

[BZOJ 3306]树

这个题其他操作都不难(DFS序+线段树水过),就是换根有点头疼……直接做的话要TopTree吧。

不过我们考虑用DFS序+线段树的“偷懒”做法。每次查询的时候考虑当前的根,如果这个根最初不在x的子树中,那么对目前的查询值没有影响;如果就是x,那么整个树都是x的子树;如果是x的某个后代,那么整个树里除了他的后代所在额这颗子树以外的所有部分全部变成了x的子树(试着翻转一下就明白了)。判断后代祖先以及在哪个子树这些东西可以用倍增LCA高效实现,问题就这样简单了。

代码:

/**************************************************************
    Problem: 3306
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2308 ms
    Memory:17544 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100005;
const int maxnode=maxn*4;
const int INF=0x7fffffff;
#define SEG_STD int o,int L,int R
#define MAKE_MID int M=L+(R-L)/2
// #define MAKE_CLD int lc=o<<1,rc=o<<1|1
#define LCH o<<1,L,M
#define RCH o<<1|1,M+1,R
int n;
int minv[maxnode];
int A[maxn];
void maintain(int o){
    minv[o]=min(minv[o<<1],minv[o<<1|1]);
}
void build_tree(SEG_STD){
    if(L==R){
        minv[o]=A[L];
    }else{
        MAKE_MID;
        build_tree(LCH);
        build_tree(RCH);
        maintain(o);
    }
}
int ql,qr;
int query(SEG_STD){
    if(ql<=L && R<=qr){
        return minv[o];
    }else{
        MAKE_MID;
        int ans=INF;
        if(ql<=M)
            ans=min(ans,query(LCH));
        if(qr>M)
            ans=min(ans,query(RCH));
        return ans;
    }
}
int p,v;
void update(SEG_STD){
    if(L==R){
        minv[o]=v;
    }else{
        MAKE_MID;
        if(p<=M)
            update(LCH);
        else
            update(RCH);
        maintain(o);
    }
}
inline int query(int l,int r){
    if(l<1 || l>n || r<1 || r>n)
        return INF;
    ql=l;
    qr=r;
    return query(1,1,n);
}
inline void update(int pos,int value){
    p=pos;
    v=value;
    update(1,1,n);
}
 
int first[maxn];
int next[maxn],to[maxn];
int graph_cnt=0;
inline void AddEdge(int u,int v){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
}
 
int d[maxn];
int tid[maxn];
int anc[maxn][19],dep[maxn];
int siz[maxn];
int dfs_clk=0;
void dfs(int x,int fa,int depth){
    dfs_clk++;
    tid[x]=dfs_clk;
    A[dfs_clk]=d[x];
    anc[x][0]=fa;
    dep[x]=depth;
    siz[x]=1;
    int i;
    for(i=first[x];i;i=next[i]){
        dfs(to[i],x,depth+1);
        siz[x]+=siz[to[i]];
    }
}
void process(){
    register int i,j;
    for(j=1;(1<<j)<n;j++)
        for(i=1;i<=n;i++)
            if(anc[i][j-1]!=-1)
                anc[i][j]=anc[anc[i][j-1]][j-1];
}
int root;
bool isAnc(int x){
    register int p=root,j;
    if(dep[p]<dep[x])
        return false;
    for(j=18;j>=0;j--)
        if(dep[p]-(1<<j)>=dep[x] && anc[p][j]!=-1)
            p=anc[p][j];
    return p==x;
}
int findAnc(int x,int y){
    register int j;
    for(j=18;j>=0;j--)
        if(dep[y]-dep[x]-(1<<j)>0 && anc[y][j]!=-1)
            y=anc[y][j];
    return y;
}
 
int getAns(int x){
    if(x==root){
        return query(1,n);
    }else{
        if(isAnc(x)){
            register int t=findAnc(x,root);
            register int l=tid[t],r=tid[t]+siz[t]-1;
            return min(query(1,l-1),query(r+1,n));
        }else{
            return query(tid[x],tid[x]+siz[x]-1);
        }
    }
}
 
int main(){
    int q,x,f;
    register int i;
    char buf[3];
    scanf("%d%d",&n,&q);
    for(i=1;i<=n;i++){
        scanf("%d%d",&f,&d[i]);
        if(!f){
            root=i;
        }else{
            AddEdge(f,i);
        }
    }
    memset(anc,-1,sizeof(anc));
    dfs(root,-1,0);
    process();
    build_tree(1,1,n);
    while(q--){
        scanf("%s%d",buf,&x);
        if(buf[0]=='V'){
            scanf("%d",&f);
            update(tid[x],f);
        }else{
            if(buf[0]=='Q'){
                printf("%d\n",getAns(x));
            }else{
                root=x;
            }
        }
    }
    return 0;
}

[BZOJ 2186]沙拉公主的困惑

这个题啊……亦可赛艇!

答案是[tex]\varphi(m!)*n!/m![/tex]。原因很简单,把[tex][1,n!][/tex]分成长度为[tex]m![/tex]的若干段,除去第一段外每一段中与[tex]m![/tex]互质的数[tex]k[/tex]肯定满足[tex](k\bmod m!,m!)=1[/tex](否则,[tex]k[/tex]和[tex]m![/tex]就会有大于一的公因子了)。所以说每一段内与[tex]m![/tex]互质的数都有[tex]\varphi(m!)[/tex]个。

麻烦好像就在于求一个阶乘的欧拉函数。考虑一个新乘上的数能给答案带来的贡献——如果这个数是合数,它的所有因子在前面都有了,只能把他自己贡献出来;如果这个数是质数(假设为[tex]p[/tex]),出了贡献自己以外还会贡献一个[tex](1-1/p)[/tex],最后乘起来就是贡献了[tex]p-1[/tex]。筛一遍素数再递推一下就好辣~

并且……[tex]n-m[/tex]可能非常大,所以说除去[tex]m![/tex]那块要用逆元做。

(顺便说下阶乘也要递推)

代码:

/**************************************************************
    Problem: 2186
    User: danihao123
    Language: C++
    Result: Accepted
    Time:9408 ms
    Memory:166836 kb
****************************************************************/
 
#include <cstdio>
#include <cmath>
typedef unsigned long long ull;
const int maxn=10000000;
ull R;
bool vis[maxn+5];
inline void sievePrime(){
    register int i,j,m=sqrt(maxn+0.5);
    for(i=2;i<=m;i++)
        if(!vis[i])
            for(j=i*i;j<=maxn;j+=i)
                vis[j]=true;
}
ull fac[maxn+5];
inline void sieveFac(){
    register int i;
    fac[0]=1%R;
    for(i=1;i<=maxn;i++)
        fac[i]=(fac[i-1]*(i%R))%R;
}
ull phifac[maxn+5];
inline void sievePhiFac(){
    register int i;
    phifac[1]=1%R;
    for(i=2;i<=maxn;i++){
        if(vis[i])
            phifac[i]=(phifac[i-1]*(i%R))%R;
        else
            phifac[i]=(phifac[i-1]*((i%R-1%R+R)%R))%R;
    }
}
void exgcd(ull a,ull b,ull& d,ull& x,ull& y){
    if(!b){
        d=a;
        x=1;
        y=0;
    }else{
        exgcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}
ull inv(ull a){
    ull d,x,y;
    exgcd(a,R,d,x,y);
    return (x+R)%R;
}
int main(){
    int T;
    int n,m;
    scanf("%d%llu",&T,&R);
    sievePrime();
    sieveFac();
    sievePhiFac();
    while(T--){
        scanf("%d%d",&n,&m);
        printf("%llu\n",(phifac[m]*((fac[n]*inv(fac[m]))%R))%R);
    }
    return 0;
}

[BZOJ 3339]Rmq Problem

万恶的标题党啊~

这个题明显扫描线辣……但是怎么扫呢?

我们可以考虑对于每个前缀区间[tex][1,r][/tex]先求出他们的[tex]mex[/tex]值,然后用线段树维护。

从[tex][l,r][/tex]转移到[tex][l+1,r][/tex]时,需要将[tex][l,next[l]-1][/tex]([tex]next[l][/tex]是下一个和[tex]l[/tex]具有相同值的位置)中的所有大于[tex]A[l][/tex]([tex]l[/tex]的值)的值全部变为[tex]A[l][/tex]。但是这一步怎么做啊……难道要用Segment Beats?

答案是否定的。注意到我们真正需要的只是叶子结点,所以其他非叶子结点的最小值全部弄成无限大,然后这样做就可以把最小值当做标记来弄了……非常精巧。

代码:

/**************************************************************
    Problem: 3339
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1988 ms
    Memory:10396 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=200005,INF=0x7f7f7f7f;
const int maxnode=maxn*4;
int A[maxn];
int minv[maxnode];
void build_tree(int o,int L,int R){
    if(L==R){
        minv[o]=A[L];
    }else{
        int M=L+(R-L)/2;
        minv[o]=INF;
        build_tree(o<<1,L,M);
        build_tree(o<<1|1,M+1,R);
    }
}
inline void paint(int o,int v){
    minv[o]=min(minv[o],v);
}
inline void pushdown(int o){
    paint(o<<1,minv[o]);
    paint(o<<1|1,minv[o]);
    minv[o]=INF;
}
int pos;
int query(int o,int L,int R){
    if(L==R)
        return minv[o];
    if(minv[o]<INF)
        pushdown(o);
    int M=L+(R-L)/2;
    if(pos<=M)
        return query(o<<1,L,M);
    else
        return query(o<<1|1,M+1,R);
}
int ql,qr,v;
void update(int o,int L,int R){
    if(ql<=L && R<=qr){
        paint(o,v);
    }else{
        if(minv[o]<INF)
            pushdown(o);
        int M=L+(R-L)/2;
        if(ql<=M)
            update(o<<1,L,M);
        if(qr>M)
            update(o<<1|1,M+1,R);
    }
}
 
inline int readint(){
    register int x=0;
    register char c;
    fread(&c,1,1,stdin);
    while(!isdigit(c))
        fread(&c,1,1,stdin);
    while(isdigit(c)){
        x=x*10+c-'0';
        fread(&c,1,1,stdin);
    }
    return x;
}
int buf[21];
inline void putint(int x){
    register int i,p=0;
    if(!x){
        buf[p++]=0;
    }else{
        while(x){
            buf[p++]=x%10;
            x/=10;
        }
    }
    for(i=p-1;i>=0;i--)
        putchar(buf[i]+'0');
    putchar('\n');
}
 
bool vis[maxn];
int last[maxn],next[maxn];
struct Query{
    int id;
    int l,r;
    int ans;
};
bool cmp1(const Query& x,const Query& y){
    if(x.l==y.l)
        return x.r<y.r;
    else
        return x.l<y.l;
}
bool cmp2(const Query& x,const Query& y){
    return x.id<y.id;
}
Query QS[maxn];
int V[maxn];
int main(){
    int n,q;
    register int i,l=1,k=0;
    n=readint();
    q=readint();
    for(i=1;i<=n;i++){
        V[i]=readint();
        vis[V[i]]=true;
        if(k==V[i])
            while(vis[k])
                k++;
        A[i]=k;
    }
    build_tree(1,1,n);
    for(i=n;i>=1;i--){
        if(!last[V[i]])
            next[i]=n+1;
        else
            next[i]=last[V[i]];
        last[V[i]]=i;
    }
    for(i=1;i<=q;i++){
        QS[i].id=i;
        QS[i].l=readint();
        QS[i].r=readint();
    }
    sort(QS+1,QS+1+q,cmp1);
    for(i=1;i<=q;i++){
        while(l<QS[i].l){
            ql=l;
            qr=next[l]-1;
            v=V[l];
            update(1,1,n);
            l++;
        }
        pos=QS[i].r;
        QS[i].ans=query(1,1,n);
    }
    sort(QS+1,QS+1+q,cmp2);
    for(i=1;i<=q;i++){
        putint(QS[i].ans);
    }
    return 0;
}

[BZOJ 1433]假期的宿舍

这几乎是个二分图匹配的裸题了……

不过有很多细节问题,比如说题面里提到的那些。还有多组数据的话注意清理数组。

代码:

/**************************************************************
    Problem: 1433
    User: danihao123
    Language: C++
    Result: Accepted
    Time:68 ms
    Memory:824 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
const int maxn=55;
bool G[maxn][maxn];
int n,m;
int Pei[maxn];
bool vis[maxn];
bool DFS(int x){
    int i;
    for(i=1;i<=m;i++)
        if(G[x][i] && !vis[i]){
            vis[i]=true;
            if(!Pei[i] || DFS(Pei[i])){
                Pei[i]=x;
                return true;
            }
        }
    return false;
}
int Hungray(){
    register int i,ans=0;
    memset(Pei,0,sizeof(Pei));
    for(i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(DFS(i))
            ans++;
    }
    return ans;
}
 
int Per[maxn],Bed[maxn];
bool isStudent[maxn],Back[maxn];
int main(){
    int T,N,u,v;
    register int i,j;
    scanf("%d",&T);
    while(T--){
        n=m=0;
        scanf("%d",&N);
        memset(G,0,sizeof(G));
        memset(Per,0,sizeof(Per));
        memset(Bed,0,sizeof(Bed));
        memset(isStudent,0,sizeof(isStudent));
        memset(Back,0,sizeof(Back));
        for(i=1;i<=N;i++){
            scanf("%d",&u);
            isStudent[i]=u;
        }
        for(i=1;i<=N;i++){
            scanf("%d",&u);
            if(isStudent[i]){
                Back[i]=u;
            }
        }
        for(i=1;i<=N;i++){
            if(isStudent[i]){
                Bed[i]=++m;
                if(!Back[i]){
                    Per[i]=++n;
                }
            }else{
                Per[i]=++n;
            }
        }
        for(i=1;i<=N;i++){
            if(isStudent[i]){
                G[Per[i]][Bed[i]]=true;
            }
            for(j=1;j<=N;j++){
                scanf("%d",&v);
                if(v && isStudent[j]){
                    G[Per[i]][Bed[j]]=true;
                }
            }
        }
        if(Hungray()==n)
            puts("^_^");
        else
            puts("T_T");
    }
    return 0;
}

[POJ 3974]Palindrome

Manacher……妙,妙啊……

这个题就要是给一个字符串,输出最大回文字串长度。Manacher即可。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000005;
char buf[maxn],s[maxn<<1];
int p[maxn<<1];
inline void FactStr(){
	register int i,j=0,n=strlen(buf);
	s[j++]='$';
	s[j++]='#';
	for(i=0;i<n;i++){
		s[j++]=buf[i];
		s[j++]='#';
	}
	s[j]='\0';
}
inline int Manachar(){
	register int i,n=strlen(s);
	register int mx=0,id;
	register int ans=-1;
	for(i=1;i<n;i++){
		if(i<mx)
			p[i]=min(p[2*id-i],mx-i);
		else
			p[i]=1;
		while(s[i-p[i]]==s[i+p[i]])
			p[i]++;
		if((p[i]+i)>mx){
			id=i;
			mx=p[i]+i;
		}
		ans=max(ans,p[i]-1);
	}
	return ans;
}
int main(){
	register int Case=0;
	while(scanf("%s",buf)==1){
		if(buf[0]=='E')
			break;
		Case++;
		FactStr();
		printf("Case %d: %d\n",Case,Manachar());
	}
	return 0;
}