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,分几种情况进行讨论:
- k=1
k为1时,就是只能对第一个数排序,并不会影响整个数组的顺序,可以理解成什么用也没有。
结果为:n*(n-2)+2。 - k>=n-1
此时,无论数组A如何排列,都能满足至少存在n-1个数有序
结果为:n!。 - 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
题意
在一个二维平面中,给定一堆带权值的点,并定义四个操作:
- 增加一个点。
- 删除一个点。
- 给定一个点的坐标x,y和半径k,将到这个点(x,y)距离为k的点,权值增加w。
- 给定一个点的坐标x,y和半径k,求到这个点(x,y)距离为k的点的权值之和。
当进行操作4时需要输出结果。
关键词
分解平方和、欧几里得距离、二维坐标系、卡时间
思路
这个题很容易想到暴力的解法:遍历所有点或者遍历长度为6000的坐标系去做,结果一定会Time limit exceeded。
值得注意的是:
- 对于给定的k,能满足a2+b2=k2的a,b数量是比较少的。
在预处理中,把k按照a2+b2=k2分解为若干个a、b这样的整数对保存起来。在之后处理到x,y距离为k的点时,直接拿来用,时间上会快很多。 - 题目给的坐标系范围在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; }