题解:

首先预处理出$l_i$表示第$i$个数左侧比第$i$个数大的个数,$r_i$右侧同理.

首先脑补出我们应该将序列排成先单调不降,后单调不增的形式.

我们从大到小将数插入序列,考虑插入某个数,比这个数大的已经全部插入完毕了,由于排成那种形式,我们只能将这个数放在当前序列的头或尾.

若放在开头,则带来$l_i$的逆序对;否则带来$r_i$的逆序对.

显然每个数之间都是独立的,我们直接贪心就行了.

时间复杂度$O(nlogn)$.

代码:

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

typedef long long ll;

#define N 300010
int n,_n,a[N],b[N];

inline int getc(){
	static const int L=1<<15;
	static char buf[L],*S=buf,*T=buf;
	if(S==T){
		T=(S=buf)+fread(buf,1,L,stdin);
		if(S==T)
			return EOF;
	}
	return*S++;
}
inline int getint(){
	int c;
	while(!isdigit(c=getc()));
	int x=c-'0';
	while(isdigit(c=getc()))
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}

int A[N],l[N],r[N];
inline int ask(int x){
	int re=0;
	for(;x;x-=x&-x)
		re+=A[x];
	return re;
}
inline void upd(int x){
	for(;x<=_n;x+=x&-x)
		++A[x];
}
int main(){
	n=getint();
	int i,j;
	for(i=1;i<=n;++i)
		a[i]=b[i]=getint();
	sort(b+1,b+n+1);
	_n=unique(b+1,b+n+1)-b-1;
	for(i=1;i<=n;++i)
		a[i]=lower_bound(b+1,b+_n+1,a[i])-b;
	for(i=1;i<=n;++i){
		l[i]=i-1-ask(a[i]);
		upd(a[i]);
	}
	memset(A,0,sizeof A);
	for(i=n;i>=1;--i){
		r[i]=n-i-ask(a[i]);
		upd(a[i]);
	}
	long long ans=0;
	for(i=1;i<=n;++i)
		ans+=min(l[i],r[i]);
	cout<<ans<<endl;
	return 0;
}

题解:

(我这个大傻叉连这题都不会做了)

首先肯定是转移了...

我们单独考虑每个球,变化的概率都是$\frac{1}{m}$.

于是令$f_i$表示编号为$i$的球的个数,考虑一次操作$f_i$的变化.

考虑单个标号为$i$的球对$f_i$的影响:$\frac{1}{m}\times{0}+(1-\frac{1}{m})\times{1}$

考虑单个标号为$i-1$的球对$f_i$的影响:$\frac{1}{m}\times{1}+(1-\frac{1}{m})\times{0}$

然后我们就搞出了转移矩阵.

有意思的是,这是一个循环矩阵!

也就是说,从第二行开始,每一行都是上一行右移一位得到的.

显而易见,循环矩阵的乘积依然是循环矩阵.

所以我们只要暴力算出第一行就行了,所以可以$O(n^2)$暴力,也可以利用FFT优化至$O(nlogn)$.

这样的话就能做这道题目了.

代码:

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef double f2;
 
#define N 1010
int n,m,k,a[N];
struct Vector{
    f2 line[N],row[N];
    inline void operator*=(const Vector&B){
        static f2 _line[N];
        int i,j,k;
        for(i=0;i<n;++i)
            _line[i]=0;
        for(i=0;i<n;++i)
            for(j=(n-i)%n,k=0;k<n;++k,(++j)%=n)
                _line[i]+=line[k]*B.row[j];
        for(i=0;i<n;++i)
            line[i]=_line[i];
        for(i=0;i<n;++i)
            row[(n-i)%n]=line[i];
    }
}t,re;
int main(){
    cin>>n>>m>>k;
    int i,j;
    for(i=0;i<n;++i)
        scanf("%d",&a[i]);
    re.line[0]=re.row[0]=1;
    t.line[0]=(f2)(m-1)/m;
    t.line[1]=1.0/m;
    t.row[0]=(f2)(m-1)/m;
    t.row[n-1]=1.0/m;
    for(;k;k>>=1,t*=t)
        if(k&1)
            re*=t;
     
    f2 ans;
    for(i=0;i<n;++i){
        for(ans=0,j=(n-i)%n,k=0;k<n;++k,(++j)%=n)
            ans+=a[k]*re.row[j];
        printf("%.3lf\n",ans);
    }
    return 0;
}

题解:

我们单独考虑每个格子,如果这个格子在一次染色中不被染色的概率为$p$,则这个格子在$k$次染色中被染色的概率就是$1-p^k$.

对于每个格子如何求$p$:

看着代码自己脑补一下吧= =

代码:

#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
typedef long long ll;
 
ll calc(int n,int m){
    return(ll)n*m*n*m;
}
 
ll C[1010][1010];
int main(){
    int k,w,h;
    cin>>k>>w>>h;
    ll total;
    f2 ans=0;
    for(int i=0;i<=w;++i)
        for(int j=0;j<=h;++j)
            C[i][j]=calc(i,j);
    for(int i=1;i<=w;++i){
        for(int j=1;j<=h;++j){
            total=0;
            total-=C[i-1][j-1]+C[i-1][h-j]+C[w-i][j-1]+C[w-i][h-j];
            total+=C[w][j-1]+C[w][h-j]+C[i-1][h]+C[w-i][h];
            ans+=1-pow((f2)total/C[w][h],k);
        }
    }
    cout<<(ll)ans+(ans-(ll)ans>=.5?1:0)<<endl;
    return 0;
}

题解:

考虑任意一个串都是两个前缀之差.

如果这个串要满足$num(J)=num(O)=num(I)$,那么两个前缀$num(J),num(O),num(I)$的相对大小关系必须是相同的.

我们对于每个前缀记下$num(J)-num(O),num(J)-num(I)$,然后利用map随便搞搞就行了.

代码:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
 
typedef pair<int,int> pii;
#define mp make_pair
 
#define N 200010
char s[N];
 
map<pii,int>M;
int main(){
    int n;
    scanf("%d",&n);
    scanf("%s",s+1);
     
    M[mp(0,0)]=0;
    int J=0,O=0,I=0,ans=0;
    for(int i=1;i<=n;++i){
        if(s[i]=='J')
            ++J;
        if(s[i]=='O')
            ++O;
        if(s[i]=='I')
            ++I;
        if(M.count(mp(J-O,J-I)))
            ans=max(ans,i-M[mp(J-O,J-I)]);
        else
            M[mp(J-O,J-I)]=i;
    }
    cout<<ans<<endl;
    return 0;
}

题解:

考虑三个点在树上的形态:

(1)成一条链(其实就是中心是三个点中的一个点)

(2)存在一个唯一中心连接三个点，且中心到三个点的路径除了中心之外不相交

(定义自己脑补一下吧...)

显然只有在(2)情况下,并且唯一中心到三个点的路径长度相等才能满足条件.

我们直接枚举唯一中心,以其为根做有根树,则三个点必须分布在不同的子树中,且深度相同.

这个就很容易搞了,看代码搞搞就行了.

代码:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long ll;
#define N 5010
int head[N],next[N<<1],end[N<<1];
inline void addedge(int a,int b){
    static int q=1;
    end[q]=b;
    next[q]=head[a];
    head[a]=q++;
}
inline void make(int a,int b){
    addedge(a,b);
    addedge(b,a);
}
 
int sum1[N];
ll sum2[N];
struct Array{
    int a[N],t[N],tclock;
    inline int operator[](int x){
        if(t[x]!=tclock){
            t[x]=tclock;
            a[x]=0;
        }
        return a[x];
    }
    inline void add(int x){
        if(t[x]!=tclock){
            t[x]=tclock;
            a[x]=0;
        }
        ++a[x];
    }
}temp;
 
int max_dep;
inline void dfs(int x,int fa,int dep){
    temp.add(dep);
    max_dep=max(max_dep,dep);
    for(int j=head[x];j;j=next[j])
        if(end[j]!=fa)
            dfs(end[j],x,dep+1);
}
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
    int n;
    scanf("%d",&n);
    int i,j,k,a,b;
    for(i=1;i<n;++i){
        scanf("%d%d",&a,&b);
        make(a,b);
    }
    ll ans=0;
    int son;
    for(i=1;i<=n;++i){
        memset(sum1,0,sizeof sum1);
        memset(sum2,0,sizeof sum2);
        for(son=1,j=head[i];j;j=next[j],++son){
            ++temp.tclock;
            max_dep=0;
            dfs(end[j],i,1);
            for(k=1;k<=max_dep;++k){
                if(son>=3)
                    ans+=sum2[k]*temp[k];
                sum2[k]+=temp[k]*sum1[k];
                sum1[k]+=temp[k];
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

题解:

首先如果对于一条边的两个端点均满足$>k$,则显然可以缩到一起变成一个点.

然后对于剩下的边,我们需要添加若干条使得不出现环,因为如果出现了环肯定有$\leq{k}$的点在环上.

我们可以按任意顺序添加,因为最后图的形态是固定的.

所以直接并查集水过就可以.

代码(非常蠢):

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 1000010
#define M 2000010
struct Edge{
    int a,b;
    Edge(){}
    Edge(int _a,int _b):a(_a),b(_b){
        if(a>b)
            swap(a,b);
    }
    bool operator<(const Edge&B)const{
        return a>B.a;
    }
}E[M];
 
inline int getc(){
    static const int L=1<<15;
    static char buf[L],*S=buf,*T=buf;
    if(S==T){
        T=(S=buf)+fread(buf,1,L,stdin);
        if(S==T)
            return EOF;
    }
    return*S++;
}
inline int getint(){
    int c;
    while(!isdigit(c=getc()));
    int x=c-'0';
    while(isdigit(c=getc()))
        x=(x<<1)+(x<<3)+c-'0';
    return x;
}
 
int r[N],siz[N];
inline int find(int x){
    int q=x,rq;
    for(;x!=r[x];x=r[x]);
    for(;q!=x;rq=r[q],r[q]=x,q=rq);
    return x;
}
inline void merge(int a,int b){
    if(siz[a]>siz[b])
        swap(a,b);
    siz[b]+=siz[a];
    r[a]=b;
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
    int n,m,k,i;
    n=getint();
    m=getint();
    k=getint();
    for(i=1;i<=m;++i)
        E[i]=Edge(getint(),getint());
    for(i=1;i<=n;++i)
        r[i]=i,siz[i]=1;
    int ra,rb,cnt=0;
    for(i=1;i<=m;++i){
        if(E[i].b<=k){
            ra=find(E[i].a);
            rb=find(E[i].b);
            if(ra!=rb)
                ++cnt,merge(ra,rb);
        }
    }
    for(i=1;i<=m;++i){
        if(E[i].a>k){
            ra=find(E[i].a);
            rb=find(E[i].b);
            ++cnt;
            if(ra!=rb)
                merge(ra,rb);
        }
    }
    for(i=1;i<=m;++i){
        if(E[i].a<=k&&E[i].b>k){
            ra=find(E[i].a);
            rb=find(E[i].b);
            if(ra!=rb)
                ++cnt,merge(ra,rb);
        }
    }
    cout<<m-cnt<<endl;
    return 0;
}

题解:

首先枚举$k$,那我们需要知道给定$k$,最少进行多少次操作.

显然应该从小到大进行扫描,考虑当前位置$i$,若颜色不对,则反转$[i,i+k-1]$.

然后再判定剩下的位置颜色对不对.

这个过程可以利用单调队列轻松实现,详情见代码.

代码:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 5010
bool a[N];
int q[N],fr,ta;
int main(){
    int n;
    scanf("%d",&n);
    int i,j;
    char s[10];
    for(i=1;i<=n;++i){
        scanf("%s",s);
        a[i]=(s[0]=='F');
    }
    int ans=0x3f3f3f3f,temp,k;
    for(i=1;i<=n;++i){
        fr=ta=0;
        for(temp=0,j=1;j+i-1<=n;++j){
            while(fr!=ta&&q[fr]+i-1<j)
                ++fr;
            if((((ta-fr)&1)^a[j])==0){
                q[ta++]=j;
                ++temp;
            }
        }
        bool ok=1;
        for(j=n+2-i;j<=n;++j){
            while(fr!=ta&&q[fr]+i-1<j)
                ++fr;
            if((((ta-fr)&1)^a[j])==0)
                ok=0;
        }
        if(ok){
            if(temp<ans){
                ans=temp;
                k=i;
            }
        }
    }
    cout<<k<<" "<<ans<<endl;
    return 0;
}

题目大意:

自己看.

题解:

利用AC自动机顺序扫描.

在AC自动机上的每个终止节点上记录串的长度.

每当发现完全匹配到某一个串,就将当前状态回退[串的长度]那么多,回到那个节点继续.

实在不懂的就看代码吧.

代码:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
 
#define N 100010
char s1[N],s2[N];
int tr[N][26],cnt,fail[N],len[N];
bool end[N],del[N];
int stack[N],top,ins[N];
int main(){
    scanf("%s",s1+1);
    int n=strlen(s1+1),i,j,m,_n;
    scanf("%d",&m);
    int p;
    while(m--){
        scanf("%s",s2+1);
        _n=strlen(s2+1);
        for(p=0,i=1;i<=_n;++i){
            if(!tr[p][s2[i]-'a'])
                tr[p][s2[i]-'a']=++cnt;
            p=tr[p][s2[i]-'a'];
        }
        end[p]=1;
        len[p]=_n;
    }
    queue<int>q;
    for(i=0;i<26;++i)
        if(tr[0][i])
            q.push(tr[0][i]);
    int u,v,r;
    while(!q.empty()){
        u=q.front();
        q.pop();
        for(i=0;i<26;++i){
            if((v=tr[u][i])){
                q.push(v);
                for(r=fail[u];r&&!tr[r][i];r=fail[r]);
                end[v]|=end[fail[v]=tr[r][i]];
            }
            else
                tr[u][i]=tr[fail[u]][i];
        }
    }
    for(p=0,i=1;i<=n;++i){
        stack[++top]=i;
        if(end[ins[i]=p=tr[p][s1[i]-'a']]){
            for(j=1;j<=len[p];++j)
                del[stack[top--]]=1;
            p=ins[stack[top]];
        }
    }
    for(i=1;i<=n;++i)
        if(!del[i])
            putchar(s1[i]);
    return 0;
}

题目大意:

(1)给定一个排列,问排列的序号.

(2)给定一个序号,要求构造出给定序号的排列.

题解:

首先要知道怎么得出排列的序号.

假如序列的长度为$n$,且第$i$个元素为$P_i$.

则序号为:$\sum_{i=1}^{n}(n-i)!\sum_{j=i+1}^{n}[P_i>P_j]$

这样的话可以$O(n^2)$算出排列的序号.

构造序列的话也是一个道理,我是暴力的,没管复杂度...

代码:

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

typedef unsigned long long llu;

int a[21],ans[21];
llu fac[21];
bool ok[21];
int main(){
	int n,Q,i,j;
	char s[10];
	cin>>n>>Q;
	llu x;
	for(fac[0]=i=1;i<=20;++i)
		fac[i]=fac[i-1]*i;
	int temp;
	while(Q--){
		scanf("%s",s);
		if(s[0]=='P'){
			cin>>x;
			--x;
			for(i=1;i<=n;++i)
				a[i]=x/fac[n-i],x-=a[i]*fac[n-i];
			memset(ok,1,sizeof ok);
			for(i=1;i<=n;++i){
				temp=0;
				for(j=1;j<=n;++j){
					if((temp+=ok[j])==a[i]+1)
						break;
				}
				ok[ans[i]=j]=0;
			}
			for(i=1;i<=n;++i){
				if(i!=1)
					putchar(' ');
				printf("%d",ans[i]);
			}
			puts("");
		}
		else{
			for(i=1;i<=n;++i)
				scanf("%d",&a[i]);
			for(x=0,i=1;i<=n;++i){
				for(temp=0,j=i+1;j<=n;++j)
					temp+=(a[i]>a[j]);
				x+=fac[n-i]*temp;
			}
			cout<<x+1<<endl;
		}
	}
	return 0;
}

题目大意:

最大生成树裸题.

题解:

Kruskal,$O(mlogm)$.

代码:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 1010
#define M 100010
int r[N];
inline int find(int x){
    int q=x,rq;
    for(;x!=r[x];x=r[x]);
    for(;q!=x;rq=r[q],r[q]=x,q=rq);
    return x;
}
struct Edge{
    int u,v,l;
    Edge(){}
    Edge(int _u,int _v,int _l):u(_u),v(_v),l(_l){}
    bool operator<(const Edge&B)const{
        return l>B.l;
    }
}E[M];
int main(){
    int n,m,i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
        scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].l);
    sort(E+1,E+m+1);
    int ans=0,cnt=0;
    for(i=1;i<=n;++i)
        r[i]=i;
    int ra,rb;
    for(i=1;i<=m;++i){
        ra=find(E[i].u);
        rb=find(E[i].v);
        if(ra!=rb){
            ++cnt,ans+=E[i].l;
            r[ra]=rb;
        }
    }
    printf("%d\n",cnt==n-1?ans:-1);
    return 0;
}