灰度直方图#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include<bits/stdc++.h>
using namespace std;
const int N = 500;
const int L = 256;
int gray_L[L];
int main(){
int n, m, l, tmp;
cin>>n>>m>>l;
for(int i = 0; i < n; i ++){
for(int j = 0; j < m; j ++){
cin>>tmp;
gray_L[tmp]++;
}
}
for(int i = 0; i < l; i ++){
cout<<gray_L[i]<<" ";
}
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
|
n, m, l = map(int, input().split())
ans = [ 0 for i in range(0, 257)]
for i in range(0, n):
L = list(map(int, input().split()))
for j in range(0, m):
tmp = L[j];
ans[tmp] = ans[tmp] + 1
for i in range(0, l):
print(str(ans[i]) + " ", end="")
|
领域均值#
这种求和应该一下子就想到是前缀和（前缀矩阵）
[[前缀和（前缀和矩阵）]]
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
|
#include<bits/stdc++.h>
using namespace std;
const int N = 610;
int g[N][N];
int main(){
int n, l, r, t;
cin>>n>>l>>r>>t;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j ++){
int tmp;
cin>>tmp;
g[i][j] = tmp + g[i-1][j] + g[i][j-1] - g[i-1][j-1];
}
}
int res = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j ++){
int x1 = max(1, i - r), y1 = max(1, j - r);
int x2 = min(n, i + r), y2 = min(n, j + r);
int sum = g[x2][y2] - g[x1 - 1][y2] - g[x2][y1 - 1] + g[x1 - 1][y1 - 1];
int cnt = (x2 - x1 + 1) * (y2 - y1 + 1);
if(sum <= cnt * t) res++;
}
}
cout<<res;
return 0;
}
|
DHCP 服务器#
直接对着描述翻译为代码即可
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int n, m, t_def, t_max, t_min;
string h;
struct IP
{
int state; // 0：未分配，1：待分配，2：占用，3：过期
int t; // 过期时间
string owner;
}ip[N];
void update_ips_state(int tc)
{
for (int i = 1; i <= n; i ++ )
if (ip[i].t && ip[i].t <= tc)
{
if (ip[i].state == 1)
{
ip[i].state = 0;
ip[i].owner = "";
ip[i].t = 0;
}
else
{
ip[i].state = 3;
ip[i].t = 0;
}
}
}
int get_ip_by_owner(string client)
{
for (int i = 1; i <= n; i ++ )
if (ip[i].owner == client)
return i;
return 0;
}
int get_ip_by_state(int state)
{
for (int i = 1; i <= n; i ++ )
if (ip[i].state == state)
return i;
return 0;
}
int main()
{
cin >> n >> t_def >> t_max >> t_min >> h;
cin >> m;
while (m -- )
{
int tc;
string client, server, type;
int id, te;
cin >> tc >> client >> server >> type >> id >> te;
if (server != h && server != "*")
{
if (type != "REQ") continue;
}
if (type != "DIS" && type != "REQ") continue;
if (server == "*" && type != "DIS" || server == h && type == "DIS") continue;
update_ips_state(tc);
if (type == "DIS")
{
int k = get_ip_by_owner(client);
if (!k) k = get_ip_by_state(0);
if (!k) k = get_ip_by_state(3);
if (!k) continue;
ip[k].state = 1, ip[k].owner = client;
if (!te) ip[k].t = tc + t_def;
else
{
int t = te - tc;
t = max(t, t_min), t = min(t, t_max);
ip[k].t = tc + t;
}
cout << h << ' ' << client << ' ' << "OFR" << ' ' << k << ' ' << ip[k].t << endl;
}
else
{
if (server != h)
{
for (int i = 1; i <= n; i ++ )
if (ip[i].owner == client && ip[i].state == 1)
{
ip[i].state = 0;
ip[i].owner = "";
ip[i].t = 0;
}
continue;
}
if (!(id >= 1 && id <= n && ip[id].owner == client))
cout << h << ' ' << client << ' ' << "NAK" << ' ' << id << ' ' << 0 << endl;
else
{
ip[id].state = 2;
if (!te) ip[id].t = tc + t_def;
else
{
int t = te - tc;
t = max(t, t_min), t = min(t, t_max);
ip[id].t = tc + t;
}
cout << h << ' ' << client << ' ' << "ACK" << ' ' << id << ' ' << ip[id].t << endl;
}
}
}
return 0;
}
|
校门外的树#
参考笔记：AcWing 3414. 校门外的树 - AcWing AcWing 3414. 校门外的树 - AcWing
题意大概就是往不同的区间内插树，要求是要么在整个大区间树之间的距离是等差的，要不然是在不同的子区间内是等差的，然后障碍物的地方不能插树。
那么首先看到这个题，直觉上这个题应该分为两个步骤，第一计算我们要选择哪个区间插树，第二就是计算当前方案下的等差方案。感觉第一步比较关键并且费事，第二步不算难，求区间长度的约数即可。
这种选择问题一般就是 DP，为啥呢，当确定选择区间 A 后，后续可以有不同情况，当继续选择区间 A、B 后后续又有不同情况，这种情况的结构很像树，从一个结点延伸很多种情况，这种用 DP 来动态的推结果，一般叶子结点存储的结果就是答案。
那么闫氏 DP 分析法走起[[闫氏DP分析法]]
- 确定状态表示，这题我们用一维 f (i) 表示（实际分析的时候也是从一维开始分析，后面觉得不够，再加维度）以 i 为右端点的区间的插树方案（a0~ai 区间所有插树方法的集合）
- 状态转移：状态转移就要求如何从 f (0)~f (i-1) 的值求得 f (i) 的值
- 对于 f (j)，0<=j<=i-1 来说，f (j) 表示以 j 为右端点的方案数，那么对于 f (i) 而言新增加的情况就是区间 j~i 的方案数，那么遍历 j，把 f (j)*cnt（j, i) 求和便是我们的答案
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
|
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1010, M = 100010, MOD = 1e9 + 7;
int n;
int a[N];
int f[N];
vector<int> q[M];
bool st[M];
int main(){
//打表以算倍数的方式来求约数，q[i]表示i的约数
for(int i = 1; i < M; i ++){
for(int j = i * 2; j < M; j += i){//因为间隔不能等于区间大小，那样就不能插树了
q[j].push_back(i);
}
}
cin>>n;
for(int i = 0; i < n; i ++) cin>>a[i];
f[0] = 1;
for(int i = 1; i < n; i++){
memset(st, 0, sizeof st);
for(int j = i - 1; j >= 0; j --){
int d = a[i] - a[j], cnt = 0;
for(int k: q[d]){
if(!st[k]){
cnt++;
st[k] = true;
}
}
st[d] = true;
f[i] = (f[i] + (LL)f[j] * cnt) % MOD;
}
}
cout<<f[n-1];
return 0;
}
|
在 y 总的代码中还有一个巧妙的点在于，如何去判定插树的位置有没有避开障碍物呢，代码的第 25 行和 st 数组解决了这个问题。
- St 数组维护了使用过的约数，也就是说，当你的选择的区间使用过某个间隔 k，那么该间隔就不能再用了，因为区间两个断点是障碍物，也就是说如果比当前区间大的区间也选择了间隔 k 的方案，那么树一定会插在障碍物上
- 这也解释了为啥内层循环要从大到小遍历，从最小的区间开始一个一个把间隔 k ban 掉