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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
signed main()
{
int x = read(), a = read();
if(x < a) cout << 0 << endl;
else cout << 10 << endl;
}
|
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
| #include<bits/stdc++.h>
#define int long long
int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
signed main()
{
int n = read(), x = read();
std::vector<int> v(n + 1);
for(int i = 1; i <= n; i++) v[i] = read(), v[i] += v[i - 1];
for(int i = 1; i <= n; i++)
{
if(v[i] > x)
{
std::cout << i << "\n";
return 0;
}
}
std::cout << n + 1 << "\n";
return 0;
}
|
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
| #include<bits/stdc++.h>
#define int long long
int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
signed main()
{
int w = read(), h = read(), x = read(), y = read();
printf("%.9f %d\n", 1.0 * w * h / 2, (x * 2 == w && y * 2 == h));
return 0;
}
|
双指针+前缀和，找到每个左端点的第一个区间和>k的右端点，因为 $ a_i > 1 $所以在这个右端后的所有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
| #include<bits/stdc++.h>
#define int long long
int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
signed main()
{
int n = read(), k = read();
std::vector<int> a(n + 1);
int res = 0;
for(int i = 1; i <= n; i++) a[i] = read(), a[i] += a[i - 1];
for(int i = 0, j = 0; i <= n; i++)
{
while(a[j] - a[i] < k && j <= n)
{
j++;
}
res += (n - j + 1);
}
std::cout << res << "\n";
return 0;
}
|
DP, 求公共子序列的数量
思考最长公共子序列的状态转移
类比一下$ dp_{i,j} $记录的是s的前i个和t的前j个的公共子序列个数
$$
dp_{i,j} = dp_{i,j-1} + dp_{i-1,j} - dp_{i-1,j-1}
$$
如果$ s_i = t_j $ 最新的这个元素可以加入到$ dp_{i-1,j-1} $中的任意一个公共子序列中，并且他自己也是一个子序列，所以
$$
dp_{i,j} += dp_{i-1,j-1} + 1
$$
最后输出答案$ dp_{n, m} + 1 $, 为什么要+1，因为在题目中空集也算，同时注意%
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
| #include<bits/stdc++.h>
#define int long long
const int mod = 1e9 + 7;
int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
signed main()
{
int n = read(), m = read();
std::vector<int> s(n + 1), t(m + 1);
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1));
for(int i = 1; i <= n; i++) s[i] = read();
for(int i = 1; i <= m; i++) t[i] = read();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1];
if(s[i] == t[j]) dp[i][j] += dp[i - 1][j - 1] + 1;
dp[i][j] = (dp[i][j] % mod + mod) % mod ;
}
std::cout << dp[n][m] + 1 << "\n";
return 0;
}
|
三分，裸的，时间是自变量，是不是单峰不知道，我是蒙的，数学蒟蒻给不了证明，知道是三分的话代码挺好写的
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
| #include<bits/stdc++.h>
#define int long long
const int mod = 1e9 + 7;
int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
signed main()
{
int n = read();
std::vector<int> dx(n), dy(n);
std::vector<std::pair<int, int>> a(n);
double res = 1e18;
double u = 1e9;
double d = 0;
for(int i = 0; i < n; i++)
{
a[i].first = read(), a[i].second = read();
char c;
std::cin >> c;
if(c == 'U') dy[i] = 1;
else if(c == 'D') dy[i] = -1;
else if(c == 'L') dx[i] = -1;
else dx[i] = 1;
}
auto check = [&](double t) -> double {
double mxx = -1e18;
double mnx = 1e18;
double mxy = -1e18;
double mny = 1e18;
for (int i = 0; i < n; i++) {
double x = a[i].first + t * dx[i];
double y = a[i].second + t * dy[i];
mxx = std::max(mxx, x);
mnx = std::min(mnx, x);
mxy = std::max(mxy, y);
mny = std::min(mny, y);
}
return (mxx - mnx) * (mxy - mny);
};
for (int t = 0; t < 200; t++)
{
double uu = (u * 2 + d) / 3;
double dd = (u + d * 2) / 3;
double uv = check(uu);
double dv = check(dd);
res = std::min(res, uv);
res = std::min(res, dv);
if (dv < uv) u = uu;
else d = dd;
}
printf("%.10f", res);
return 0;
}
|
