第一题：ACS

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
已知大写字母 A 的 ASCII 码为 65，请问大写字母 L 的 ASCII 码是多少？
运行限制
最大运行时间：1s
最大运行内存: 128M

看代码

#include
using namespace std;int main(){char c = 'L';cout<

第二题：递增三元组

题目描述
给定三个整数数组
A=[A1,A2,⋯AN],
B=[B1,B2,⋯BN],
]C=[C1,C2,⋯CN]，
请你统计有多少个三元组(i,j,k) 满足：
1≤i,j,k≤N;
Ai输入描述
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,⋯AN。
第三行包含 N 个整数 B1,B2,⋯BN。
第四行包含 N 个整数 C1,C2,⋯CN。
其中，1≤N≤105,0≤Ai,Bi,Ci≤105。
输出描述
输出一个整数表示答案。
输入输出样例

输入

3
1 1 1
2 2 2
3 3 3

输出

27

暴力做法，过了87.5%, 通过找比b小的a，和比b大的b,找到方案

再对应相乘就是答案，但是有一个样例超时

#include 
#include
using namespace std;typedef long long LL;
const int N = 100010;
int a[N], b[N], c[N];
int s[N], t[N];
int n;int main()
{ scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);for(int i = 1; i <= n; i++) scanf("%d", &b[i]);for(int i = 1; i <= n; i++) scanf("%d", &c[i]);for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++){if(a[j] < b[i]) s[i]++;if(b[i] < c[j]) t[i]++;}LL ans = 0;for(int i = 1; i <= n; i++){ans += s[i]*t[i];}cout<

通过暴力优化，变为一重循环

排序，再使用双指针，每此确定比b小的a的位置，比b大的c的位置（再用减去）

为什么这样可行，因为数组是有序的，前面都比b[i]小，b向后移动变为b[i+1]

此时比b[i]小的都比b[i+1]小

#include 
#include
using namespace std;typedef long long LL;
const int N = 100010;
int a[N], b[N], c[N];
int s[N], t[N];
int n;int main()
{ scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);for(int i = 1; i <= n; i++) scanf("%d", &b[i]);for(int i = 1; i <= n; i++) scanf("%d", &c[i]);sort(a + 1, a + 1 + n);sort(b + 1, b + 1 + n);sort(c + 1, c + 1 + n);LL ans = 0, s1 = 1, s2 = 1;for(int i = 1; i <= n; i++){while(s1 <= n && a[s1] < b[i]) s1++;while(s2 <= n && c[s2] <= b[i]) s2++;ans += (LL)(s1 - 1) * (n - s2 + 1);}cout<

使用了algorithm中的函数

lower_bound()返回第一个大于等于的地址

upper_bound()返回第一个大于的地址

减去起始地址，即得到最新的地址

#include
#include
using namespace std;typedef long long LL;
const int N = 1e5 + 10;
int a[N], b[N], c[N];int main(){int n;scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%d", &a[i]);for(int i = 0; i < n; i++) scanf("%d", &b[i]);for(int i = 0; i < n; i++) scanf("%d", &c[i]);sort(a, a + n); sort(b, b + n); sort(c, c + n);LL ans = 0;for(int i = 0; i < n; i++){LL x = lower_bound(a, a + n, b[i]) - a;LL y = n - (upper_bound(c, c + n, b[i]) - c);ans += x * y;}cout<

第三题：环境治理

环境治理 - 蓝桥云课 (lanqiao.cn)

floyd+二分

#include
#include
#include
using namespace std;const int N = 110;
typedef long long LL;
LL g[N][N], f[N][N], minv[N][N];
LL n, q;int floyd(){for(int k = 1; k <= n; k++)for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)f[i][j] = min(f[i][j], f[i][k] + f[k][j]);LL a = 0;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)a += f[i][j];return a;
}bool check(LL x){memcpy(f, g, sizeof g);LL h = x / n, s = x % n;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++){if(i == j) continue;if(s >= i) f[i][j] = max(minv[i][j], f[i][j] - h - 1);else f[i][j] = max(minv[i][j], f[i][j] - h);f[j][i] = f[i][j];}return floyd() <= q;
}int main(){scanf("%lld%lld", &n, &q);for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)scanf("%lld", &g[i][j]);for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++){scanf("%lld", &minv[i][j]);f[i][j] = minv[i][j];}if(floyd() > q){puts("-1");return 0;}LL l = 0, r = 1e9;while(l < r){LL mid = l + r >> 1;if(check(mid)) r = mid;else l = mid + 1;}cout<