CodeForces - 1426_综合

CodeForces - 1426

A - Floor Number

小模拟int t,n,x;
int main()
{
    scanf("%d",&t);while(t--){
    scanf("%d%d",&n,&x);int left=1,right=2,id=1;while(1){
    if (left<=n&&n<=right){
    W(id);break;}left=right+1;right=left+x-1;id++;}}return 0;
}

B - Symmetric Matrix

如果边长不是偶数肯定不行
1 2
3 4
画个图就会发现只看2、3位置是否相等int t,n,m,a,b,c,d;
int main()
{
    scanf("%d",&t);while(t--){
    scanf("%d%d",&n,&m);bool mark=false;rep(i,1,n){
    scanf("%d%d%d%d",&a,&b,&c,&d);if (b==c)mark=true;}if (m%2||!mark)printf("NO\n");else printf("YES\n");}return 0;
}

C - Increase and Copy

肯定是先把一个数加到很大，然后copy很多份
枚举这个最大的数字即可
注意最后的sum不一定是n，超过n也可以int t,n;
int main()
{
    scanf("%d",&t);while(t--){
    scanf("%d",&n);int ans=n-1;rep(i,1,sqrt(n)+100){
    if (n%i==0)ans=min(ans,n/i+i-2);else ans=min(ans,n/i+i-1);}W(ans);}return 0;
}

D - Non-zero Segments

没有和为0的区间等价于 前缀和不等于0并且前缀和不重复出现
假设前缀和是-9 -4 3 -4 -9
显然只需要在第二个-4的前面插入一个数字就可以同时把第二个-9改变
也就是说 一旦插入一个数字，那么前面所有的记录的前缀和都可以直接清空，重新开始遍历
注意不要把0删去，因为任意时刻出现了前缀和为0的情况都是不符合的map<ll,int> M;
int n;
ll a[maxn],ans=0,sum=0;
int main()
{
    ll sum=0;scanf("%d",&n);M[0]=1;rep(i,1,n){
    scanf("%lld",&a[i]);sum+=a[i];if (M[sum]){
    M.clear();ans++;sum=a[i];M[0]=1;}M[sum]=1;}W(ans);return 0;
}

E - Rock, Paper, Scissors

根据贪心思想，一共3*3种对局，每一种对局必然是进行完全的，至少有一方会被消耗完
所以可以O(9!)枚举对局顺序，然后更新答案
（虽然写起来麻烦了一些，但是蛮好想的）int a[10],a1,a2,b1,b2,c1,c2,n,A1,A2,B1,B2,C1,C2,Minans=INF,Maxans=0,ans=0,minn;
int check(int x)
{
    if (x==1){
    minn=min(a1,a2);a1-=minn;a2-=minn;}if (x==2){
    minn=min(a1,b2);a1-=minn;b2-=minn;ans+=minn;}if (x==3){
    minn=min(a1,c2);a1-=minn;c2-=minn;}if (x==4){
    minn=min(b1,a2);b1-=minn;a2-=minn;}if (x==5){
    minn=min(b1,b2);b1-=minn;b2-=minn;}if (x==6){
    minn=min(b1,c2);b1-=minn;c2-=minn;ans+=minn;}if (x==7){
    minn=min(c1,a2);c1-=minn;a2-=minn;ans+=minn;}if (x==8){
    minn=min(c1,b2);c1-=minn;b2-=minn;}if (x==9){
    minn=min(c1,c2);c1-=minn;c2-=minn;}
}
int main()
{
    scanf("%d",&n);scanf("%d%d%d",&A1,&B1,&C1);scanf("%d%d%d",&A2,&B2,&C2);rep(i,1,9)a[i]=i;do{
    ans=0;a1=A1,b1=B1,c1=C1,a2=A2,b2=B2,c2=C2;rep(i,1,9)check(a[i]);Maxans=max(Maxans,ans);Minans=min(Minans,ans);}while(next_permutation(a+1,a+10));printf("%d %d\n",Minans,Maxans);return 0;
}

F - Number of Subsequences

思路一：
一开始想的是dp，没想出来
思路二：
假如遍历到一个a，假设以它作为abc的序列共有 $k_1$ 个
假如遍历到一个b，假设以它作为abc的序列共有 $k_2$ 个
假如遍历到一个c，假设以它作为abc的序列共有 $k_3$ 个
假如遍历到一个?，假设以它作为abc的序列共有 $k_1+k_2+k_3$ 个
后来发现一个问题，以a作为开头，后面的串中共有多少个bc子序列，配合后缀和的复杂度是O(n)，也就是说总复杂度达到了O(n^2)，排除
思路三：
为了解决这个问题，遍历每一个中间位置b即可(’?‘也可以作为b)
只要用前缀和和后缀和就可以处理a和c包括’?'的个数

如果没有问号的情况下，abaccbc
第一个b的左边有1个a，右边有3个c，ans+=1×3
第二个b的左边有2个a，右边有1个c，ans+=2×1
如果有问号的情况下,a??bcc
k个问号可以组成的所有情况是 $3^k$
对于任意一个问号，a在其中出现的概率是 $131\over 3$
所以k个问号中出现的a的个数是 $k*3^{k-1}$
别忘记加上原本的a的个数prea[i-1]乘上所有的情况 $3^k$
左边的a的总个数
$a n s = p r e a [i ? 1] ? q p o w (3, p r e n u m [i ? 1], m o d) + p r e n u m [i ? 1] ? q p o w (3, p r e n u m [i ? 1] ? 1, m o d)$
同理可以求出右边的c的总个数
两者相乘计入答案即可


ll qpow(ll a,ll b,ll mod){
    ll res=1;while(b){
    if (b&1)res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return res;}
ll prea[maxn],preb[maxn],prec[maxn],lasa[maxn],lasb[maxn],lasc[maxn],prenum[maxn],lasnum[maxn],ans=0;
int n;
char s[maxn];
int main()
{
    scanf("%d%s",&n,s+1);rep(i,1,n){
    prea[i]=prea[i-1];preb[i]=preb[i-1];prec[i]=prec[i-1];prenum[i]=prenum[i-1];if (s[i]=='a')prea[i]++;if (s[i]=='b')preb[i]++;if (s[i]=='c')prec[i]++;if (s[i]=='?')prenum[i]++;}for (int i=n;i>=1;i--){
    lasa[i]=lasa[i+1];lasb[i]=lasb[i+1];lasc[i]=lasc[i+1];lasnum[i]=lasnum[i+1];if (s[i]=='a')lasa[i]++;if (s[i]=='b')lasb[i]++;if (s[i]=='c')lasc[i]++;if (s[i]=='?')lasnum[i]++;}rep(i,1,n){
    if (s[i]=='b'||s[i]=='?'){
    ll left=prea[i-1]*qpow(3,prenum[i-1],mod);if (prenum[i-1])left=(left+prenum[i-1]*qpow(3,prenum[i-1]-1,mod))%mod;ll right=lasc[i+1]*qpow(3,lasnum[i+1],mod);if (lasnum[i+1])right=(right+lasnum[i+1]*qpow(3,lasnum[i+1]-1,mod))%mod;ans=(ans+left*right%mod)%mod;}}WW(ans);return 0;
}