D. Omkar and Medians
题目描述
解法
不难想到可以保证 (b[1...i-1]) 这些中位数合法，考虑加入两个数让 (b[i]) 也合法，可以用的条件是 (b[i-1]) 是前 (2i-3) 个数的中位数，可以讨论 (b[i]) 和 (b[i-1]) 的关系：
- 如果 (b[i]>b[i-1])，那么此时一定有 (i-1) 个数比 (b[i]) 小，所以 (b[i]) 和 (b[i-1]) 中间就不能有任何元素。
- 如果 (b[i]<b[i-1])，那么此时一定有 (i-1) 个数比 (b[i]) 大，所以 (b[i]) 和 (b[i-1]) 中间就不能有任何元素。
- 如果 (b[i]=b[i-1]) 显然仍然可以合法。
如果满足上述条件那么一定有解，我们把随意确定的元素放在正无穷或者负无穷即可，我们可以用 ( t set) 来判断前驱后继，或者利用前驱后继的特性可以直接用双向链表 (O(n)) 解决。
#include <cstdio>
#include <set>
using namespace std;
const int M = 200005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int T,n,f,a[M];set<int> s;
signed main()
{
T=read();
while(T--)
{
n=read();s.clear();f=1;
for(int i=1;i<=n;i++)
{
a[i]=read();
s.insert(a[i]);
if(i==1 || a[i]==a[i-1]) continue;
if(a[i]>a[i-1] && *s.upper_bound(a[i-1])!=a[i])
f=0;
if(a[i]<a[i-1] && *s.upper_bound(a[i])!=a[i-1])
f=0;
}
if(f) puts("YES");
else puts("NO");
}
}
E. Omkar and Forest
题目描述
解法
这道题有两个限制，不妨一起用：如果当前格子为 (x>0)，那么存在一个相邻的格子满足其权值恰好为 (x-1)
这就是 ( t bfs) 的过程嘛！所以如果固定了 (0)，那么剩下的权值也就确定了，设#的数量是 (cnt)，那么方案数就是 (2^{cnt})，如果整张图都是#那么答案是要减 (1)，因为要排除全部非 (0) 的情况。
#include <cstdio>
const int M = 2005;
const int MOD = 1e9+7;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int T,n,m,f,ans;char s[M];
signed main()
{
T=read();
while(T--)
{
n=read();m=read();f=ans=1;
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);
for(int j=1;j<=m;j++)
{
if(s[j]=='0') f=0;
else ans=ans*2%MOD;
}
}
printf("%d
",ans-f);
}
}
F. Omkar and Akmar
题目描述
解法
首先考虑必胜策略，终止状态要不然是-A-B-，要不然是-A-X-B，也就是说空格一定夹在AB之间的。考虑去掉空格后是AB交替出现的一个环，所以AB的出现次数都是偶数，推出后手必胜，而且无论怎么玩都是后手必胜。
那么把操作序列的个数算出来就行了，假设最后有 (k) 个空格，那么就有 ((n-k)!) 种操作方法，再乘上在长度为 (n) 的环中选取 (k) 个空格不能相邻的方案数即可，这时候我们要破环为链，设 (f(n,k)) 为长度为 (n) 的序列中选 (k) 个空格不能相邻的方案数，讨论第一个格子是不是空格，方案数是 (f(n-1,k)+f(n-3,k-1))
(f) 的计算是容易的，我们先拿出 (k-1) 个格子，再从中任意选取 (k) 个空格，方案数是 ({n-k+1choose k})
因为ABAB和BABA都是可以的，所以答案需要乘 (2)
#include <cstdio>
const int MOD = 1e9+7;
const int M = 1000005;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,ans,fac[M],inv[M];
void init(int n)
{
fac[0]=inv[0]=inv[1]=1;
for(int i=2;i<=n;i++) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=n;i++) inv[i]=inv[i-1]*inv[i]%MOD;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
}
int C(int n,int m)
{
if(n<m || m<0) return 0;
return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int f(int n,int k)
{
return C(n-k+1,k);
}
signed main()
{
n=read();init(n+1);
for(int i=0;i<=n;i++)
{
if((n-i)&1) continue;
int t=(f(n-1,i)+f(n-3,i-1))%MOD;
ans=(ans+2*fac[n-i]*t)%MOD;
}
printf("%lld
",ans);
}