layout: post
title: Codeforces Round 258(Div. 2)
author: "luowentaoaa"
catalog: true
tags:
mathjax: true
- codeforces
- 卢卡斯定理
[A - Game With Sticks (签到)
题意
给出n条垂直线m条平行线他们互相相交 形成n×m条交点
现在每次取一个交点然后把过这个交点的线段全部去除
不能选择交点的失败，问你最后谁会赢
思路
很明显 交点取的最大数量和N和m的最小值有关
并且每次取一个点都肯定会有一条水平和一条竖线被取出
所以答案就是n和m的最小值的奇偶判断
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e7+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef unsigned long long ull;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n,m;
cin>>n>>m;
if(min(n,m)%2)cout<<"Akshat"<<endl;
else cout<<"Malvika"<<endl;
return 0;
}
B - Sort the Array
问你能否旋转一个区间使得整个数组严格递增
思路
直接暴力枚举需反转的区间判断是否符合
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef unsigned long long ull;
int a[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
int st=0;
for(int i=0;i<n-1;i++){
if(a[i]>a[i+1]){
st=i;
break;
}
}
int ed=0;
for(int i=n-1;i>=1;i--){
if(a[i]<a[i-1]){
ed=i;
break;
}
}
reverse(a+st,a+ed+1);
bool flag=1;
for(int i=1;i<n;i++){
if(a[i]<a[i-1])flag=0;
}
if(flag)cout<<"yes"<<endl<<st+1<<" "<<ed+1;
else cout<<"no"<<endl;
return 0;
}
C - Predict Outcome of the Game (分类讨论)
题意
三个队伍有n场比赛，你错过了K场但是你知道第一个队伍和第二个队伍的分数差的绝对值，和第二个队伍和第三个队伍分数差的绝对值，问你能否使得三个队伍分数都一样
注意！比赛不会出现平局
思路
首先N肯定要是三的倍数 不然绝对不能平均分配
然后根据题意我们得出两个不等式，假设队伍的分数分别是a.b.c
那么
[|a-b|=d1\|b-c|=d2
]
那么会得出四个方程然后都比较判断一下就行
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef unsigned long long ull;
ll n, k, d1, d2, ave, x, ok;
bool one() {
if(n%3==0&&(k+2*d1+d2)%3==0){
ave=n/3;
x=(k+2*d1+d2)/3;
if(ave>=x&&x>=(d1+d2))
return true;
}
return false;
}
bool two() {
if((k+2*d1-d2)%3==0&&(k+2*d1-d2)>=0){
ave=n/3;
x =(k+2*d1-d2)/3;
if(ave>=x&&x>=d1&&ave>=(x-d1+d2))
return true;
}
return false;
}
bool three() {
if((k-2*d1+d2)%3==0&&(k-2*d1+d2)>=0) {
ave=n/3;
x=(k-2*d1+d2)/3;
if(ave>=(x+d1)&&(x+d1)>=d2)
return true;
}
return false;
}
bool four() {
if((k-2*d1-d2)%3==0&&(k-2*d1-d2)>=0){
ave=n/3;
x=(k-2*d1-d2)/3;
if(ave>=(x+d1+d2))
return true;
}
return false;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int t;
cin>>t;
while(t--){
cin>>n>>k>>d1>>d2;
if(n%3){
cout<<"no"<<endl;continue;
}
if(one()||two()||three()||four()){
cout<<"yes"<<endl;continue;
}
else cout<<"no"<<endl;
}
return 0;
}
D - Count Good Substrings (水题)
题意
给你只含a,b的字符串，然后相同的字符串会合并
问你有多少个奇数 和偶数的字串是回文
思路
首先只有a和b 题目难度小了很多
然后因为相同字符串会合并
所以最后回文串的只需要头尾相同就行，然后现在就是判断长度了
发现奇数的 就只要是相同奇数和奇数 偶数和偶数匹配就行
偶数就是奇数和偶数 匹配就行
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef unsigned long long ull;
ll a[2][2];
char s[maxn];
ll odd(){
ll ans=0;
ans+=1LL*(a[0][1]+a[1][1]);
ans+=1LL*a[0][1]*(a[0][1]-1LL)/2LL;
ans+=1LL*a[1][1]*(a[1][1]-1LL)/2LL;
ans+=1LL*a[0][0]*(a[0][0]-1LL)/2LL;
ans+=1LL*a[1][0]*(a[1][0]-1LL)/2LL;
ans+=1LL*(a[0][0]+a[1][0]);
return ans;
}
ll even(){
ll ans=0;
ans+=a[0][0]*a[0][1];
ans+=a[1][0]*a[1][1];
return ans;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin>>s+1;
int len=strlen(s+1);
for(int i=1;i<=len;i++){
int id=s[i]-'a';
int ok=i%2;
a[id][ok]++;
}
cout<<even()<<" "<<odd()<<endl;
return 0;
}
E - Devu and Flowers (组合数 卢卡斯定理 容斥定理)
题意
给你n个盒子 每个盒子有k个花，让你从n个盒子选出s朵花，求方案数
思路
首先不考虑盒子的花的数量，那么答案是
[C_{n+s-1}^{n-1}
]
但是这时候有的盒子的花数量超出了，所以我们就要减去超出的数量
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef unsigned long long ull;
ll n,s;
ll pow_mod(ll x, ll n, ll mod){
ll res=1;
while(n){
if(n&1)res=res*x%mod;
x=x*x%mod;
n>>=1;
}
return res;
}
ll inv(ll a,ll p){return pow_mod(a,p-2,p);}
ll cal(ll a,ll b,ll p){
if(a<b)return 0;
if(b>a-b)b=a-b;
ll fz=1,fm=1;
for(ll i=0;i<b;i++){
fz=fz*(a-i)%p;
fm=fm*(i+1)%p;
}
return fz*inv(fm,p)%p;
}
ll lucas(ll a,ll b,ll p){
if(b==0)return 1;
return cal(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
ll f[50];
ll solve(){
ll ans=0;
for(int i=0;i<(1<<n);i++){
ll sign=1,sum=s;
for(int j=0;j<n;j++){
if(i&(1<<j)){
sum-=(f[j]+1);
sign*=-1;
}
}
if(sum<0)continue;
ans+=sign*lucas(sum+n-1,n-1,mod);
ans=(ans+mod)%mod;
}
return ans;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin>>n>>s;
for(int i=0;i<n;i++)cin>>f[i];
cout<<solve()<<endl;
return 0;
}