Ying

codeforces Contest 459

 
  • Aug 17, 2014

题目链接在这里

A. Pashmak and Garden

给定矩阵的两个点，判断正方形是否存在，存在则打印剩余的两个顶点。
注意按三种情况处理就可以了。

int main()
{
    int x[4],y[4];
    cin >> x[0] >> y[0] >> x[1] >> y[1];

    //vertical
    if (x[0] == x[1])
    {
        x[2] = x[3] = x[0] + y[1] - y[0];
        y[2] = y[0];
        y[3] = y[1];
    }
    //horizontal
    else if (y[0] == y[1])
    {
        y[2] = y[3] = y[0] + x[1] - x[0];
        x[2] = x[0];
        x[3] = x[1];
    }
    else if (abs(x[0] - x[1]) == abs(y[0] - y[1]))
    {
        x[2] = x[1];
        y[2] = y[0];
        x[3] = x[0];
        y[3] = y[1];
    }
    else
    {
        cout << -1 << endl;
        return 0;
    }

    cout << x[2] << " "
         << y[2] << " "
         << x[3] << " "
         << y[3] << endl;

    return 0;
}

B. Pashmak and Flowers

要求得到最大的差，因此只要求出最大值和最小值就可以了。
再次遍历分别得到个数相乘就是组合数。
注意最大值最小值相等的情况，即所有花的beauty完全相等。此时组合数为C(n,2)。
n的范围[2,2*1e5]，n*(n - 1)可能会超int范围，要用long long。

int main()
{
    LL n;
    LL b[200000] = {0};

    cin >> n;

    for (LL i = 0; i < n; ++i)
        cin >> b[i];

    LL maxb = max(b[0], b[1]);
    LL minb = min(b[0], b[1]);

    for (LL i = 2; i < n; ++i)
    {
        maxb = max(b[i], maxb);
        minb = min(b[i], minb);
    }

    LL max_cnt = 0, min_cnt = 0;
    for (LL i = 0; i < n; ++i)
    {
        if (b[i] == maxb)
            max_cnt++;
        if (b[i] == minb)
            min_cnt++;
    }

    LL cnt = max_cnt * min_cnt;
    if (maxb == minb)
    {
        cnt = n * (n - 1) / 2;
    }

    cout << (maxb - minb) << " " << cnt << endl;

    return 0;
}

C. Pashmak and Buses

题目意思为有k辆车，n个学生做d天，能否使得没有任何学生会跟另外一个学生一直坐一辆车。
k辆车d天的话，一共有k**d种排列，只要排列数≤n即可。
数值的范围： 1≥n,d≤1000 1≥k≤1000

注意两点：

n最大为1000，因此计算k**d过程中能够大于该值就可以返回了，否则会越界。

如何打印全排列，我用的是递归的办法。
例子后面贴了另外一种思路更清楚办法

typedef long long LL;
LL n,k,d, stu;
int a[1001][1001] = {0};
int b[1001];

void f(int day)
{
    if (day == d)
    {
        for (int i = 0; i < d; ++i)
            a[stu][i] = b[i];
        stu++;
        if (stu == n)
            return;
    }
    else if (day < d)
    {
        for (int i = 1; i <= k; ++i)
        {
            b[day] = i;
            f(day + 1);
            if (stu == n)
                return;
        }
    }
}

int main()
{
    cin >> n >> k >> d;
    int tmp = 1;
    for (int i = 0; i < d; ++i)
    {
        tmp *= k;
        if (tmp >= n)
            break;
    }
    if (tmp >= n)
    {
        f(0);
        for (int i = 0; i < d; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                cout << a[j][i] << " ";
            }
            cout << endl;
        }
    }
    else
    {
        cout << -1 << endl;
    }

    return 0;
}

一种比较清晰的打印全排列的方式是看做k进制，位数为d。
f/g分别是两种表现，本质相同

具体看程序,打印前20个排列：

int n,k,d;

void f()
{
    for (int m = 0; m < n; ++m)
    {
        //直接计算m的k进制表示
        int j = m;
        vector<int> v;
        while (j)
        {
            v.push_back(j % k);
            j /= k;
        }

        for (int i = 0; i < d - v.size(); ++i)
        {
            cout << 1 << " ";
        }
        for (int i = v.size() - 1; i >= 0; --i)
        {
            cout << v[i] + 1 << " ";
        }
        cout << endl;
    }
}

int a[1000][1000];
void g()
{
    //i = 0可以单独稍后输出
    for (int i = 1; i <= n; ++i)
    {
        //根据i-1的k进制表示+1得到i的k进制表示
        for (int j = 0; j < d; ++j)
        {
            a[i][j] = a[i - 1][j];
        }

        for (int j = d - 1; j >= 0; --j)
        {
            a[i][j] = (a[i][j] + 1) % k;
            if (a[i][j])
                break;
        }

        for (int j = 0; j < d; ++j)
            cout << a[i][j] + 1 << " ";
        cout << endl;
    }
}

int main()
{
    n = 20; k = 4; d = 5;
    cout << "===================================" << endl;
    f();
    cout << "===================================" << endl;
    g();
    cout << "===================================" << endl;

    return 0;
}
Search