C. Insertion Sort

题意

假设存在一个数组A,长度为n,包含1到n这些数:[1,2,3,……,n-1,n],但不保证顺序。
输入整数n、k、q。

  • n:数组A的长度。
  • k:在数组A中,能对前k个数排序。
  • q:结果对q求模。
    输出一个整数,表示有多少数组A的排列组合,满足对前k个数排序后,其中有序的数不少于n-1个。

关键词

数论、排列组合、排序

思路

对于输入的k,分几种情况进行讨论:

  1. k=1
    k为1时,就是只能对第一个数排序,并不会影响整个数组的顺序,可以理解成什么用也没有。
    结果为:n*(n-2)+2。
  2. k>=n-1
    此时,无论数组A如何排列,都能满足至少存在n-1个数有序
    结果为:n!。
  3. k∈(1, n-1)
    此时为最普遍的一种情况可以按照排序前的情况,对其继续细分:
    k∈(1, n-1)时的细分情况

结果为:k!+k!*(n-k-1)+k!*(n-k-1)2+k!*k*(n-k)。

代码

#include <bits/stdc++.h>

#define Debug 0
#define MAXN 300056
#define MAXM 200
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;
int q;
// Calculate the factorial
ll jc (int x)
{
    ll t = 1;
    for (int i = 2; i <= x; ++i)
    {
        t = (t * i) % q;
    }
    return t;
}


int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
    SYNC
    int T;
    cin >> T;
    int Case = 0;
    while (T--)
    {
        int n, k;
        cin >> n >> k >> q;
        if (k == 1)
        {
            cout << "Case #" << ++Case << ": " << (n * (n - 2) + 2) % q << endl;
        } else if (k >= n - 1)
        {
            cout << "Case #" << ++Case << ": " << jc(n) << endl;
        } else
        {
            ll m = jc(k);
            ll t = n - k - 1;
            ll ans = 0;
            ans = (ans + m * (t * t + t + 1)) % q;
            ans = (ans + m * k * (n - k)) % q;
//            ans = (ans + (t * t + t + 1) * m + m * n * (n - k)) % q;
            cout << "Case #" << ++Case << ": " << ans << endl;
        }


    }

#ifdef FILE_IN
    fclose(stdin);
#endif

    return 0;
}

G. Best ACMer Solves the Hardest Problem

题意

在一个二维平面中,给定一堆带权值的点,并定义四个操作:

  1. 增加一个点。
  2. 删除一个点。
  3. 给定一个点的坐标x,y和半径k,将到这个点(x,y)距离为k的点,权值增加w。
  4. 给定一个点的坐标x,y和半径k,求到这个点(x,y)距离为k的点的权值之和。

当进行操作4时需要输出结果。

关键词

分解平方和、欧几里得距离、二维坐标系、卡时间

思路

这个题很容易想到暴力的解法:遍历所有点或者遍历长度为6000的坐标系去做,结果一定会Time limit exceeded。
值得注意的是:

  1. 对于给定的k,能满足a2+b2=k2的a,b数量是比较少的。
    在预处理中,把k按照a2+b2=k2分解为若干个a、b这样的整数对保存起来。在之后处理到x,y距离为k的点时,直接拿来用,时间上会快很多。
  2. 题目给的坐标系范围在6000以内,可以直接使用数组保存,但是,6000*6000的数组在每个案例中都要初始化,使用memset也会比较耗时间。
    直接将每次输入或插入的点坐标保存起来,每个案例处理完之后,按照保存的坐标将上面的点去掉,这样每次最多也就会将整个数组初始化一次的时间,比直接使用memset快很多。

这两点也是最容易卡时间的点,在这个上面贡献了无数发TLE,只要处理好这2个问题,不用读写挂也不会有太大问题。

代码

#include <bits/stdc++.h>

#define Debug 0
#define MAXN 6010
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

ll G[MAXN][MAXN];

vector<Pair> factors[MAXK];
int n, m;

// Used to restore the manipulated coordinates
vector<Pair> changed;

// Use 'set' to remove the duplicate positions
// Sometimes the same 'tx' and 'ty' will appear multiple times in 'increase' method and 'sum' method
set<Pair> se;
ll last_ans = 0;

int dx[] = {-1, -1, 1, 1};
int dy[] = {-1, 1, 1, -1};

inline bool check (int x, int y)
{ return x > 0 && x <= 6000 && y > 0 && y <= 6000 && G[x][y] > 0; }

inline void init ()
{
    for (int i = 0; i < MAXN; ++i)
    {
        for (int j = 0; j < MAXN; ++j)
        {
            int sq = i * i + j * j;
            if (sq < MAXK)
            {
                factors[sq].pb(Pair(i, j));
            } else
                break;
        }
    }
}

inline void init_xy (int &x, int &y)
{
    x = (x + last_ans) % MOD + 1;
    y = (y + last_ans) % MOD + 1;
}

inline void add (int x, int y, int k, bool ini = 0)
{
    if (ini)
        init_xy(x, y);

    G[x][y] = k;
    changed.pb(Pair(x, y));
}

inline void remove (int x, int y)
{
    init_xy(x, y);
    G[x][y] = 0;
}

inline void increase (int x, int y, int k, int w)
{
    init_xy(x, y);
    se.clear();
    for (auto p : factors[k])
    {
        int tx, ty;
        for (int i = 0; i < 4; ++i)
        {
            tx = x + dx[i] * p.first;
            ty = y + dy[i] * p.second;
            if (check(tx, ty))
            {
                se.insert(Pair(tx, ty));
            }
        }
    }
    for (auto p:se)
    {

        G[p.first][p.second] += w;
    }

}

inline ll sum (int x, int y, int k)
{
    init_xy(x, y);
    ll ans = 0;
    se.clear();
    for (auto p : factors[k])
    {
        int tx, ty;
        for (int i = 0; i < 4; ++i)
        {
            tx = x + dx[i] * p.first;
            ty = y + dy[i] * p.second;
            if (check(tx, ty))
            {
                se.insert(Pair(tx, ty));
            }
        }
    }

    for (auto p:se)
    {
        ans += G[p.first][p.second];
    }
    last_ans = ans;
    return ans;
}

inline void restore ()
{
    for (auto p : changed)
    {
        G[p.first][p.second] = 0;
    }
    changed.clear();
}

int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
//    SYNC
    int T;
    scanf("%d", &T);
    init();
    int Case = 0;
    while (T--)
    {
        last_ans = 0;
        printf("Case #%d:\n", ++Case);
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; ++i)
        {
            int x, y, k;
            scanf("%d %d %d", &x, &y, &k);
            add(x, y, k);
        }
        for (int i = 0; i < m; ++i)
        {
            int t;
            scanf("%d", &t);
            int x, y, k, w;
            switch (t)
            {
                case 1:
                    scanf("%d %d %d", &x, &y, &k);
                    add(x, y, k, 1);
                    break;
                case 2:
                    scanf("%d %d", &x, &y);
                    remove(x, y);
                    break;
                case 3:
                    scanf("%d %d %d %d", &x, &y, &k, &w);
                    increase(x, y, k, w);
                    break;
                case 4:
                    scanf("%d %d %d", &x, &y, &k);
                    printf("%lld\n", sum(x, y, k));
                    break;
            }
        }
        restore();
    }

#ifdef FILE_IN
    fclose(stdin);
#endif

    return 0;
}