补题【Darkness+Different Billing+Dice Game】

1.Darkness

题目来源：Darkness I


这题不难想，通过作图我们发现
当n=m时直接取对角线就好
当n!=m时，取m,n的最小值，那么最小值的这个正方形都可以被填为黑色，剩下的行（即n,m的差值）只需每间隔一行填一个黑色格。
那么可以推导出公式：
s=min(n,m)+(abs(n-m)+1)/2

#include<bits/stdc++.h>
using namespace std;
int main()
{int n,m;cin>>n>>m;cout<<min(n,m)+(abs(n-m)+1)/2;return 0;} 

2.Different Billing

题目来源：Different Billing


其实这题可以纯暴力来写，一看x的范围是10的6次方，那么可以查找a然后再通过式子得出b和c，判断是否符合条件就可以了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int x,y,a,b,c,f,q;
const int N=1e6;
int check(int a)
{c=(q-2*x+2*a)/3;if(c<0||(q-2*x+2*a)!=c*3)return 0;b=x-a-c;if(b<0)return 0;return 1;
}
signed main()
{cin>>x>>y;if(y%500!=0||y==500){cout<<-1;return 0;}q=y/500;for(int i=0;i<=N;i++){if(check(i)){cout<<i<<" "<<b<<" "<<c<<endl;f=1;break;}}if(! f)cout<<-1;return 0;
}

还有一种常规方法，不过这个在比赛中我们没有写出来，还是考虑的太不全面了，于是下去再思考一下，思绪清晰了许多；
可以先让s=y/500,因为500是1000和2500的最大公约数，然后我们可以从（1_{s)循环遍历，如果能得到（s-i）的值能对2整除，那么**c=i,b=(s-c*5)/2,a=x-b-c**,然后判断和是否等于y，就行了，不要忘了a不能小于0哦}

#include<bits/stdc++.h>
#define int long long
using namespace std;
int x,y,a,b,c;
signed main()
{cin>>x>>y;int s=y/500;for(int i=0;i<=s;i++){if((s-i)%2==0){c=i;b=(s-c*5)/2;a=x-b-c;if(b*1000+c*2500==y&&a>=0){cout<<a<<" "<<b<<" "<<c<<endl;return 0;}}}cout<<"-1";return 0;
}

3.Dice Game

题目来源：Dice Game

其实这道题很简单，只是考察了快速幂和对题目的理解！！！
这道题是什么意思呢？就是说呀，有n+1个人投骰子，骰子有m个可能的值，数最小的人输，求第一个人所投的数字为x（1~i)时，第一个人输的概率。

• 如果x=1，因为1就是最小的数，那么输的概率一定为1。
• 如果x=m,m时1~m中最大的数，所以一定不会输，输的概率为0。
• 那么中间的数的概率该怎么算呢？
  就样例而言，当x=2时，拿其他的人只有摇到3，4，5。第一个人才会输，那么剩下的每个人摇到3，4，5的概率是$(m-2{)}^n/$（m-1)^n$。
  那么可以推导出公式：

分子:p=(m-i)的n次方
分母：q=(m-1)的n次方
但由于数据较大，我们每次都要用快速幂优化一下。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,p,q;
const int MOD=998244353;
const int N=998244351;
int Qmi(int a,int b)
{int ans=1;a%=MOD;while(b!=0){if(b&1)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;
}
signed main()
{cin>>n>>m;cout<<1<<" ";for(int i=2;i<m;i++){p=Qmi(m-i,n);q=Qmi(m-1,n);cout<<p*Qmi(q,N)%MOD<<" ";}cout<<0;return 0;
}

结束啦~辛苦各位看到这里，希望对你有所帮助！