首页 > 试题广场 >

牛牛排队

[编程题]牛牛排队
  • 热度指数：2064 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
牛牛和他的小伙伴一共n个人参加冬令营，他们的教官要求他们排成一排，每个人都有固定的位置，但是牛牛和他的小伙伴有些马虎，所以总是不记得他们到底站在哪个位置，但是他们记得之前站在他们左部分和站在他们右部分的人的人数差的绝对值a_i，根据这些值，牛牛想知道他们到底有多少种不同的站法？（结果需要对1e9+7取模）
示例1

输入

3,[2,0,2]

输出

2

说明

可能的站法(1 2 3)， (3 2 1)
示例2

输入

3,[1,1,1]

输出

0

说明

不存在这样的站法

备注:
其中1<=n<=1000000, 0<=a_i<=1000000
算法知识视频讲解
添加回答
笨鸟的GPS头像 笨鸟的GPS
为什么我连题目都没看懂，心累
发表于 2021-03-05 17:27:19 回复(1)
C/C++
nbgao头像 nbgao 
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int solve(int n, vector<int>& a) {
        const int M = 1e9+7;
        int s = 1, cnt[1000001];
        memset(cnt, 0, sizeof(cnt));
        for(int i=0;i<a.size();i++)
            cnt[a[i]]++;
        if(n&1){
            for(int i=0;i<n;i++){
                if(i==0){
                    if(cnt[0] != 1)
                        return 0;
                }else{
                    if(((i&1) && cnt[i]!=0) || (!(i&1) && cnt[i]!=2))
                        return 0;
                    if(!(i&1))
                        s = (s<<1)%M;
                }
            }
        }else{
            for(int i=0;i<n;i++){
                if(((i&1) && cnt[i]!=2) || (!(i&1) && cnt[i]!=0))
                    return 0;
                if(!(i&1))
                    s = (s<<1)%M;
            }
        }
        return s;
    }
};

发表于 2020-07-02 01:21:24 回复(0)
张杰头像 张杰
示例1 里面，为什么213这种站法不可以？
发表于 2021-07-20 14:09:20 回复(1)
C/C++
.晚安头像 .晚安 
class Solution {
public:
    int solve(int n, vector<int>& a) {
        vector<int> b(n);
        for (auto num: a) if (num < 0 || num >= n || num & 1 == n & 1 || b[num]++ == 2) return 0;
        for (int i = !(n & 1); i < n; i += 2) if ((i == 0 && b[i] != 1) || (i > 0 && b[i] != 2)) return 0;
        long long res = 1, base = 2, mod = 1000000007;
        while (n >>= 1) {
            if (n & 1) res = res * base % mod;
            base = base * base % mod;
        }
        return res;
    }
};

编辑于 2020-07-30 16:11:03 回复(0)
Java
Fubuki_0v0头像 Fubuki_0v0
题不难，输出坑，中间计算用的变量记得用long
public int solve (int n, int[] a) {
        // write code here
        //如果n为奇数，中间人1种，其余人每人2种，但某人确定后，对应另一个位置的人也确定了，共2^((n-1)/2)种
        //如果n为偶数，每人2种，但某人确定后，对应另一个位置的人也确定了，共2^(n/2)种
        if(n==1) {
            return a[0]==0 ? 1 : 0;
        }
        if(n==2) {
            return a[0]==a[1]&&a[0]==1 ? 2 : 0;
        }
        Arrays.sort(a);
        if(n%2!=0 && a[0]!=0) {
            return 0;
        }
        int c = (n%2==0 ? 1 : 2);
        for(int i=(n%2==0 ? 0 : 1)+1; i<n; i+=2) {
            if(a[i-1]!=a[i] || a[i]!=c) {
                return 0;
            }
            c+=2;
        }
        
        int m = n/2;
        long r = 1;
        long d = 2;
        while(m>0) {
            if(m%2==1) {
                r *= d;
            }
            if(r > 1000000007) {
                r = r % 1000000007;
            }
            d*=d;
            if(d > 1000000007) {
                d = d % 1000000007;
            }
            m = m>>1;
        }
        return (int)r;
    }
编辑于 2020-07-04 19:53:16 回复(0)
早睡早起多锻炼头像 早睡早起多锻炼
排序+快速幂 
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型vector 
     * @return int整型
     */
    const int M = 1000000007;
    int qpow(long long a, long long n) {
        long long res = 1;
        while (n) {
            if (n & 1) res = (res * a) % M;
            a = (a * a) % M;
            n >>= 1;
            //cout<< res<< " "<< a<< " "<< n<< endl;
        }
        return (int)res;
    }
    int solve(int n, vector<int>& a) {
        // write code here
        if (n<= 0) return 0;
        if (n==1) return (a[0] == 0);
        sort(a.begin(), a.end());
        int now, start;
        if (n & 1) {
        	if (a[0] != 0) return 0;
            now = 2;
            start = 1;
        } else {
            now = 1;
            start = 0;
        }
        while (start < a.size()) {
            if (a[start] != now || a[start+1] != now) return 0;
            start += 2;
            now += 2;
        }
        return qpow((long long)2, (long long)n/2);
    }
};



发表于 2020-06-23 00:11:39 回复(0)
牛客382923277号头像 牛客382923277号
n=2时 只能是【1，1】
n=3时 只能是【2，0，2】
无非是位置调换
可以排列，那么排列数必定是2^(n/2 
class Solution {
public:
    /**
     *
     * @param n int整型
     * @param a int整型vector
     * @return int整型
     */
    static const int N = 1000001;
    int solve(int n, vector<int>& a) {
        // write code here
        const int MOD = 1000000007;
        int len = a.size();
        int count[N] = {0};
        int ans=1;
        for(auto &k : a) count[k]++;
        if(n%2==0){
            for(int i=0;i<n;i++){
                if(i%2==1 && count[i]!=2) return 0;
                if(i%2==0 && count[i]!=0) return 0;
                if(i%2==0) ans=ans*2%MOD;
            }
        }
        if(n%2==1){
            for(int i=0;i<n;i++){
                if(i==0){
                    if(count[0]!=1) return 0;
                }else{
                    if(i%2==1 && count[i]!=0) return 0;
                    if(i%2==0 && count[i]!=2) return 0;
                    if(i%2==0) ans=ans*2%MOD;
                }
            }
        }
        return ans;
    }
};

)
发表于 2020-04-10 18:10:38 回复(0)
提交观点

问题信息

思维 快速幂 排序
难度：
7条回答 6671浏览

热门推荐

通过挑战的用户

查看代码

相关试题

牛牛排队

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号