终于上红啦.....................
我感觉.....真开心
ACB这个顺序真心有毒
以及那些人到底怎么A题挂的一片.............
我真不明白.....................
A题:
区间操作:
区间翻转(0变1,1变0),代价y
区间反转(110-->011),代价x
问变成全1的最小代价
做法:
首先连续的一起操作肯定不会有问题
所以变成一个
01010101...这样的串(第一位可能是1,反正01相间就对了)
然后翻转=删除一个01
设0的数量是n
那么要么y*n
要么是x*(n-1)+y
第二种情况要求n!=0
C题
*吐槽:
这场比赛真有毒,B和C都是输入n输出一个数....
然后.....先做C后做B..............
B想了半天不会做也是醉了...............
然后C题.........
C题弱智错误WA了两发
----------------------------
题意:
n*n的格子,每个颜色是RGB三种颜色之一(任意放)
如果其中一行或者一列是相同颜色就是"好的"
问一共3n*n种方案里面,有多少种是好的
做法:
标准的容斥做法
三种情况:
一共有k行颜色相同,方案数是(注意到这k行可以互不相同)
3k*3n(n-k)*C(n,k)*(-1)k-1
一共有k列颜色相同,也是上述的方案数
一共有i行j列颜色相同
注意到这i行j列一定颜色相同
方案数是
3*3(n-i)(n-j)*C(n,i)*C(n,j)*(-1)i+j
我们可以利用二项式定理来解决这个问题
我们可以这么计算
3*C(n,i)*(-1)i*C(n,j)*(3(n-i))(n-j)*(-1)j
所以后面的东西可以用二项式定理
j = 1 ... n改为j = 0 ... n就是标准的二项式定理(3(n-i)-1)n的内容
所以我们直接用二项式定理即可
具体式子看代码.............
B题
I,V,X,L一共有4个罗马字符
(I=1 V=5 X=10 L=50)
用n个,能得到多少种数字
注意:我们不在意罗马字符的顺序,换而言之,IX=XI=11
做法:
我们在n<=100的时候直接暴力,a个I,b个V,c个X,n-a-b-c个L这样
复杂度O(n4)
在n>100的时候
我们思考,首先所有数-=n
那么就只有0,4,9,49这些数字构成的
那么假设无限个,我们就能构成
24以上的所有数和24以下的一部分数
我们思考,所有数=50n-它本身
那么只有0,-40,-45,-49构成
那么假设有无限个,我们能构成-(40*49)以下的所有数
两端的dp就行了
===================
A题
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char a[300005];
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n,x,y;
scanf("%d%d%d",&n,&x,&y);
scanf("%s",a);
int i;
char last_char=' ';
int zeros=0;
for (i=0;i<n;i++)
{
if (a[i]==last_char)
{
continue;
}
last_char=a[i];
if (a[i]=='0')
{
zeros++;
}
}
if (zeros==0)
{
puts("0");
return 0;
}
cout<<min(zeros*(long long)y,y+(long long)(zeros-1)*x)<<endl;
return 0;
}
C题
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int modo=998244353;
int power(int x,int y)
{
if (y==0) return 1;
int t=power(x,y/2);
t=(long long)t*t%modo;
if (y%2==1) t=(long long)t*x%modo;
return t;
}
int pow3[100005];
int pow3_head[100005];
int fact[1000005];
int anti_fact[1000005];
int power3(long long x)
{
x%=(modo-1);
return (long long)pow3_head[x/100000]*pow3[x%100000]%modo;
}
int c(int n,int x)
{
return (long long)fact[n]*anti_fact[x]%modo*anti_fact[n-x]%modo;
}
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int i;
pow3[0]=1;
for (i=1;i<=100000;i++)
{
pow3[i]=(long long)pow3[i-1]*3%modo;
}
pow3_head[0]=1;
for (i=1;i<=100000;i++)
{
pow3_head[i]=(long long)pow3_head[i-1]*pow3[100000]%modo;
}
fact[0]=1;
for (i=1;i<=1000000;i++)
{
fact[i]=(long long)fact[i-1]*i%modo;
}
anti_fact[1000000]=power(fact[1000000],modo-2);
for (i=1000000;i>=1;i--)
{
anti_fact[i-1]=(long long)anti_fact[i]*i%modo;
}
int n;
scanf("%d",&n);
int ans=0;
int p=-1;
for (i=1;i<=n;i++)
{
p*=-1;
ans=(ans+p*(long long)c(n,i)*power3(i)%modo*power3((long long)(n-i)*n))%modo;
ans=(ans+p*(long long)c(n,i)*power3(i)%modo*power3((long long)(n-i)*n))%modo;
ans=(ans-p*(long long)c(n,i)*3%modo*power3((long long)(n-i)*n))%modo;
}
p=-1;
for (i=1;i<=n;i++)
{
p*=-1;
ans=(ans+p*c(n,i)*(long long)3*power(power3(n-i)-1,n))%modo;
}
ans=(ans+modo)%modo;
printf("%d
",ans);
return 0;
}
B题
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int ans[50005];
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n;
scanf("%d",&n);
if (n<=100)
{
int i,j,k,l;
for (i=0;i<=n;i++)
{
for (j=0;i+j<=n;j++)
{
for (k=0;i+j+k<=n;k++)
{
l=n-i-j-k;
ans[i+j*5+k*10+l*50]=true;
}
}
}
int cnt=0;
for (i=0;i<=50000;i++)
{
if (ans[i]) cnt++;
}
printf("%d
",cnt);
return 0;
}
int i;
long long min_val=n+24;
long long max_val=(long long)n*50-1960;
for (i=0;i<=49;i++)
{
int j,k;
for (j=0;i+j<=49;j++)
{
for (k=0;i+j+k<=49;k++)
{
ans[i*40+j*45+k*49]=true;
}
}
}
long long f_ans=max_val-min_val+1;
for (i=0;i<1960;i++)
{
if (ans[i]) f_ans++;
}
f_ans+=12;
cout<<f_ans<<endl;
return 0;
}