B题

题意：现已给出长度为n的数组a，表示n张已确定值的牌（1<=ai<=m）。还有k张没有确定值的鬼牌，每张可为[1,m]内任意一个值。问从这n+k张牌中选出x张数值连续的牌，求x能达到的最大值。

———————————————————————————————————

思路：双指针维护窗口，窗口内的数值是可在使用不超过k张鬼牌的情况下连续的数。

用队列来实现双指针不容易出现边界错误且代码更短逻辑更清晰

时间复杂度：排序O(nlogn)+双指针O(n)

void solved()
{
    int n,m,k;
	cin>>n>>m>>k;
    
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    
    sort(a.begin()+1,a.end());//排序
    n=unique(a.begin()+1,a.end())-a.begin()-1;//去重
    
    queue<int> q;//队列 
    int ans=0,cost=0;//cost是当前消耗的鬼牌
    for(int i=1;i<=n;i++)
    {
    	while(q.size() && a[i]-q.back()-1+cost>k)//确保a[i]能加入队列
    	{
    		int x=q.front();q.pop();
    		if(q.size())cost-=q.front()-x-1;//取消连接时撤回前面消耗的鬼牌数
		}
		
		//加入a[i] 
		if(q.size())cost+=a[i]-q.back()-1;//与前面连接新消耗的鬼牌 
		q.push(a[i]);
		
		//计算答案 
		int l=q.front(),r=q.back();
		ans=max(ans,r-l+1+min((l-1)+(m-r),k-cost));//k-cost张剩下的鬼牌用来向左向右补长[l,r]的区间 
	}
	cout<<ans<<'\n';
}

C题

需要求组合数，先O(n)预处理出1e7范围内的阶乘及其阶乘逆元，然后处理每一个询问即可

正面考虑所有美丽图的情况太多，所以考虑所有情况减去不是美丽图的情况

注意不是美丽图的情况：C(n/2,k)*(2^k) (其中k<=n/2)

解释：C(n/2,k)是因为n/2对直径中任意选k对，(2^k)是因为每对直径只能涂一个点，所以每队用2种涂法，k对就是2^k种，然后根据乘法原理乘起来即可

void solved()
{
    auto qpow=[&](int a,int b)//快速幂
    {
        int res=1;
        while(b)
        {
            if(b&1)res=res*a%mod;
            a=a*a%mod;
            b/=2;
        }
        return res;
    };
    
    int n,k;
    n=10000000;
    vector<int> f(n+1),ff(n+1);
    
    f[0]=1;
    for(int i=1;i<=n;i++)f[i]=f[i-1]*i%mod;//阶乘
    ff[n]=qpow(f[n],mod-2);
    for(int i=n-1;i>=0;i--)ff[i]=ff[i+1]*(i+1)%mod;//阶乘逆元
    
    auto fc=[&](int n,int m)//组合数
    {
        return f[n]*ff[n-m]%mod*ff[m]%mod;
    };
    
    int t;cin>>t;
    while(t--)
    {
        cin>>n>>k;
        
        if(k<2 || n%2==1)cout<<0<<'\n';//不可能是美丽图
        else
        {
    		if(k>n/2)cout<<fc(n,k)<<'\n';//任意情况都是美丽图
    		else cout<<(fc(n,k)-qpow(2,k)*fc(n/2,k)%mod+mod)%mod<<'\n';//考虑所有情况减去不是美丽图的情况
		}
    }
}