#223Div1的第四题，题意大致是一排n个座位，每个座位两侧有个电源（那么总共就是n+1个电源），每来一个人坐在某个位置上后，他就会占用这个座位两侧的电源，如果只剩一个可用就用一个，如果两个都被占了，他就会生气的离开，现在如果个别位置上的人是第几个入场确定的话，问如何安排省下位置上的人的进场顺序，可以使所有人都能有至少一个电源用而不至于生气的离开。         这题一直没什么思路，昨天拿去问了下凡姐结果被她一晚上秒掉了......首先，如果不是第一个人的话，每个人入场后必须要坐在恰好一个人的旁边，这样才能使所有人都高兴，这个很好想，很面的话大致思路分两种情况，第一个人的位置确定还是不确定。首先把所有非0的情况读进来，用一个结构体存下他的位置和他是第几个进场的，然后按进场的优先级排个序，之后按这个序列来扩展，如果第一个人的位置确定的话，那么就直接从第1个人的位置开始扩展，维护一个区间l,r表示当前l,r已经坐满了人，如果下一个非零的入场顺序是k的话，就根据k的位置在这个区间在左边还是右边，用组合公式算出来从1开始入场到第k个人入场，这中间有多少种合法的入场方式，之后扩展l,r的范围。例如第二组样例1确定后，下一个是3，他的位置是2，此时l==r==3,3在区间的左边，可知1的左边已经没有位置，第二个入场的人只能坐到1的右边，那么此时可行的方案是C(3-1-1//中间有几个人入场，2-1-1//左边还剩0个空位)=1,之后扩展区间，2,3,4都坐满了人，所以l==2,r==4，然后扩展下一个非零的入场顺序。注意末尾要添加一个虚拟的rank n+1用来计算剩下的情况，这个位置在0或者在n+1无所谓了，因为无论左边还是右边，算出一边的情况另一边的情况就出来了.如果1的位置不确定的话，就枚举1在每一个位置的情况，求个和就好。具体实现看代码吧。 #include #include #include #include #include #include using namespace std; typedef long long ll; int n,m,tot; const int MOD=1e9+7; const int maxn=1e5+10; ll fenzi[maxn]; ll fenmu[maxn]; ll ans; ll pow_mod(ll a,ll b) { ll ans=1; while(b) { if(b%2==1) ans=ans*a%MOD; a=a*a%MOD; b/=2; } return ans%MOD; } ll C(int a,int b) { if(ar) { len=a[i].pos-r-1; tmp=a[i].rank-lastv-1; if (tmp