Codeforces Round #447 (Div. 2)

54 阅读 0 评论 36 点赞

我是靠谱客的博主犹豫夕阳，最近开发中收集的这篇文章主要介绍Codeforces Round #447 (Div. 2)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送门：http://codeforces.com/contest/894/problem

A. QAQ

题意：找字符串QAQ出现的次数。
思路：这道题做到类似的。在PAT中有一道求有多少个PAT的如出一辙。
统计Q的个数。从头开始，这样每次读到A的时候就知道A前面的Q和后面的Q的个数，相乘就可以求出当前A对应QAQ的个数。

#include<bits/stdc++.h>
using namespace std;

int main ()
{
    //yyy_3y
    string s; cin >> s;
    int cnt_Q = 0;
    for (int i = 0; i < s.length(); i++ ){
        if (s[i] == 'Q') cnt_Q ++;
    }
    int temp = 0;
    int ans = 0;
    for (int i = 0; i < s.length(); i++ ){
        if (s[i] == 'Q') cnt_Q --, temp++;
        if (s[i] == 'A') ans += cnt_Q * temp;
    }
    cout << ans << endl;
    return 0;
}

B. Ralph And His Magic Field

题意：给出一个n*m的方格矩阵，给定k=-1或1，在所有方格里面填上-1或1，使得每行每列的乘积都为k，则算作一种方案，求总共有多少种不同方案。
思路：每个格子只能填1或-1，对于每一行，不管前m-1列填的是什么，最后一列都一定有办法填一个数使得乘积满足题目要求，每一列也是如此。所以填数的办法就是(n-1)(m-1)个，又因为只能填1或-1，所有答案就是2的(n-1)(m-1)次方。那么右下角那个格子呢？设前(n-1)*(m-1)个格乘积为sum，对于列来说，右下角填上A=k^(n-1)*sum，对于行来说右下角填上B=k^(m-1)*sum。那么显然如果k=-1，且n和m奇偶性不同时A不等于B，其余情况都能满足。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod =  1000000007;

 long long quickmod(long long a,long long b,long long m)
{
    long long ans = 1;
    while(b)//用一个循环从右到左便利b的所有二进制位
    {
        if(b&1)//判断此时b[i]的二进制位是否为1
        {
            ans = (ans*a)%m;//乘到结果上，这里a是a^(2^i)%m
            b--;//把该为变0
        }
        b/=2;
        a = a*a%m;
    }
    return ans;
}
int main ()
{
    ll n,m,k; cin >> n >> m >> k;
    if (n%2 != m % 2 && k == -1) cout << 0 << endl;
    else if ( n == 1 || m == 1) cout << 1 << endl;
    else {

        ll ans = quickmod(2,n-1,mod);
        ans = quickmod(ans,m-1,mod);
        cout << ans << endl;
    }
    return 0;
}

C. Marco and GCD Sequence

题意：1000个数，每个数不超过1e6，让你构造一个不超过4000的数列，使得对于新数列，任意区间内的数求GCD都出现在这1000个数中。
思路：赤裸裸的构造题啊。
先判断所有数的gcd是不是数列中最小的数，如果不是输出-1.
否则就构造一个数列，在没一项之间插入gcd，这样gcd不是最小的数字就是本身。符合规则。

#include<bits/stdc++.h>
using namespace std;
int a[10000];
int main()
{
   int n; cin >> n;
   for (int i = 1; i <= n; i++) cin >>a[i];

   int gcd = a[1];
   for (int i = 2; i <= n; i++) gcd =  __gcd(gcd,a[i]);
   if (gcd != a[1]) cout << -1 <<endl;
   else{
        cout << 2*n-1 <<endl;
        for (int i = 1; i <= n; i++) {
            if (i == 1) cout << a[1];
            else cout << " " << gcd << " " << a[i];
        }
   }

    return 0;
}