前缀和

Acwing121
Acwing121

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
const int maxn = 1000 + 10;
int C, n;

class A {
public:
int x, y;
} a[maxn];

map<int, int> got;
vector<int> nums;
int sum[maxn][maxn];

// discrete
void discrete() {
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
for (auto x : nums) got[x] = lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

// prework
void prework() {
_rep(i, 1, n) {
int x = got[a[i].x], y = got[a[i].y];
sum[x][y]++;
}

_for(i, 1, nums.size()) _for(j, 1, nums.size()) {
sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
}
}

// check
inline bool check(int R) {
for (int x2 = 1, x1 = 0; x2 < nums.size(); x2++) {
while (nums[x2] - nums[x1+1] + 1 > R) x1++;
for(int y2 = 1, y1 = 0; y2 < nums.size(); y2++) {
while (nums[y2] - nums[y1+1] + 1 > R) y1++;
int cnt = sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1];
if (cnt >= C) return true;
}
}
return false;
}

void solve() {
int l = 1, r = 10000;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", r);
}

void init() {
got.clear();
nums.clear();
nums.push_back(0);

memset(sum, 0, sizeof sum);
}

int main() {
freopen("input.txt", "r", stdin);
init();

// get data
scanf("%d%d", &C, &n);
_rep(i, 1, n) {
int x, y;
scanf("%d%d", &x, &y);
nums.push_back(x), nums.push_back(y);
a[i].x = x, a[i].y = y;
}

// discrete
discrete();

// prework
prework();

// check and binary search
solve();
}

取整函数

取整函数的性质如下

mn=m1n+1\lceil \frac{m}{n} \rceil = \lfloor \frac{m-1}{n}\rfloor + 1

等价于鸽巢原理
mm 个球放入nn 个盒子
存在一个盒子里至少有ceil(m/n)\textbf{ceil}(m/n) 个球
存在一个盒子里至多有floor(m/n)\textbf{floor}(m/n) 个球

在算法竞赛中,经常出现的是
对区间[l,r][l, r] 进行()/k(\cdots) / k 取整操作

1
2
3
4
5
下取整 floor
(l+r) / k

上取整 ceil
(l+r-1) / k + 1

特别地,如果是中位数,即k=2k=2

l+r12+1=l+r1+22=l+r+12\frac{l+r-1}{2} + 1 = \frac{l+r-1+2}{2} = \frac{l+r+1}{2}

1
2
3
4
5
下取整 floor
(l+r) >> 1;

上取整 ceil
(l+r+1) >> 1;

数的进制转换

Acwing124
Acwing124

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
int a, b;

void solve(const string& str) {
vector<int> nums;
for (auto c : str) {
if (c <= '9') nums.push_back(c-'0');
if (c >= 'A' && c <= 'Z') nums.push_back(c-'A' + 10);
if (c >= 'a' && c <= 'z') nums.push_back(c-'a' + 36);
}
reverse(nums.begin(), nums.end());

vector<int> ans;
while (nums.size()) {
int r = 0;
for (int i = nums.size()-1; i >= 0; i--) {
nums[i] += r * a;
r = nums[i] % b;
nums[i] /= b;
}
ans.push_back(r);
while (nums.size() && nums.back() == 0) nums.pop_back();
}

reverse(ans.begin(), ans.end());
string str_b;
for (auto c : ans) {
if (c <= 9) str_b += char(c+'0');
if (c >= 10 && c <= 35) str_b += char(c - 10 + 'A');
if (c >= 36 && c <= 61) str_b += char(c - 36 + 'a');
}

cout << str_b << endl;
}

void init() {
//
}

int main() {
freopen("input.txt", "r", stdin);
int kase;
cin >> kase;

while (kase--) {
string str_a;
cin >> a >> b >> str_a;
cout << a << " " << str_a << endl;
cout << b << " ";

// then solve
solve(str_a);
cout << endl;
}
}

邻项交换求解贪心最优化

Acwing125
Acwing125

贪心问题,扫描法

Acwing127
Acwing127

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
const int maxn = 100000 + 10;
int n, m;
// m tasks n machine

class A {
public:
int x, y;
bool operator< (const A &rhs) const {
return x < rhs.x || (x == rhs.x && y < rhs.y);
}
} T[maxn], M[maxn];

void solve() {
sort(T, T+m);
sort(M, M+n);
multiset<int> st;

ll ans = 0;
ll cnt = 0;
for (int i = m-1, j = n-1; i >= 0; i--) {
while (j >= 0 && M[j].x >= T[i].x) st.insert(M[j--].y);
auto it = lower_bound(st.begin(), st.end(), T[i].y);
if (it != st.end()) {
cnt++;
ans += T[i].x * 500 + T[i].y * 2;
st.erase(it);
}
}
printf("%lld %lld\n", cnt, ans);
}

void init() {
//
}

int main() {
freopen("input.txt", "r", stdin);
init();

scanf("%d%d", &n, &m);
_for(i, 0, n) scanf("%d%d", &M[i].x, &M[i].y);
_for(i, 0, m) scanf("%d%d", &T[i].x, &T[i].y);

// then solve
solve();
}