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;
}
