A LG3030
一看 \(1 \le N \le 10\)，所以我就准备写一个暴搜。
可是，\(M\) 比较大，暴搜也不行啊？
突然，我发现，\(1 \le M \le 10000\)！
所以，这个题，就被记搜秒了......
code
#include <bits/stdc++.h>
using namespace std;
int n, m, mem[10010][20], arr[20];
int DFS(int rst, int cnt) {
if(rst == 0 || cnt == 0) {
return (rst || cnt? 1145141919 : 0);
}
if(mem[rst][cnt] != -1) {
return mem[rst][cnt];
}
int ans = 1145141919;
for(int i = 1; i * i <= rst; i++) {
ans = min(ans, DFS(rst - i * i, cnt - 1) + (arr[cnt] - i) * (arr[cnt] - i));
}
return mem[rst][cnt] = ans;
}
int main() {
memset(mem, -1, sizeof(mem));
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> arr[i];
}
DFS(m, n);
cout << (mem[m][n] == 1145141919? -1 : mem[m][n]) << '\n';
return 0;
}
B LG3029
一看就是双指针，所以没有思路，只有方法。
直接双指针维护对于每一个右端点，它的最后面的可能的左端点（注意有些时候区间一定不合法，此时忽略）。
code
#include <bits/stdc++.h>
using namespace std;
struct node {
int x, id;
}arr[50050];
int n, brr[50050], cnt[50050], ans = INT_MAX;
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> arr[i].x >> arr[i].id;
brr[i] = arr[i].id;
}
//What do you think it is?
sort(brr + 1, brr + n + 1);
int len = unique(brr + 1, brr + n + 1) - brr - 1;
for(int i = 1; i <= n; i++) {
arr[i].id = lower_bound(brr + 1, brr + len + 1, arr[i].id) - brr;
}
sort(arr + 1, arr + n + 1, [](node a, node b) {return a.x < b.x;});
int cur = len;
for(int l = 1, r = 1; r <= n; r++) {
cur -= !cnt[arr[r].id];
cnt[arr[r].id]++;
for(; cnt[arr[l].id] > 1; cnt[arr[l++].id]--) {
}
if(!cur) {
ans = min(ans, arr[r].x - arr[l].x);
}
}
cout << ans << '\n';
return 0;
}
C LG2176
场上误解了方法，只得 40 分。
后来发现可以挂一个大边权欺骗算法，所以改成了枚举边，暴力 Dijkstra。
然后加上 O2 的力量，就可以过了。
codes
40 分
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node {
int v, w;
};
struct nodee {
int v, w, w2;
bool operator >(const nodee &b) const {
return w > b.w;
}
};
int n, m, dis[110][3], u, v, w, mx[110], cnt[110];
vector<node> to[110];
priority_queue<nodee, vector<nodee>, greater<nodee> > lq;
void dijkstra() {
for(lq.push({1, 0, 0}); lq.size(); ) {
nodee tmp = lq.top();
lq.pop();
if(cnt[tmp.v] == 2) {
continue;
}
if(cnt[tmp.v] == 0) {
mx[tmp.v] = tmp.w2;
}
dis[tmp.v][++cnt[tmp.v]] = tmp.w;
for(auto i : to[tmp.v]) {
lq.push({i.v, tmp.w + i.w, max(tmp.w2, i.w)});
}
}
}
signed main() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
cin >> u >> v >> w;
to[u].push_back({v, w});
to[v].push_back({u, w});
}
dijkstra();
cout << min(dis[n][2], dis[n][1] + mx[n]) - dis[n][1] << '\n';
return 0;
}
100 分
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node {
int v, w;
bool operator >(const node &b) const {
return w > b.w;
}
};
struct edge {
int u, v, w;
}arr[10010];
int n, m, u, v, w, d[110], dis[110], ans, org, vis[110];
vector<node> to[110];
void dijkstra(int db) {
d[0] = INT_MAX;
for(int i = 2; i <= n; i++) {
d[i] = INT_MAX, dis[i] = INT_MAX, vis[i] = 0;
}
d[1] = 0;
vis[1] = 0;
for(int i = 1; i <= n; i++) {
int tmp = 0;
for(int j = 1; j <= n; j++) {
if(d[tmp] > d[j]) {
tmp = j;
}
}
dis[tmp] = d[tmp];
d[tmp] = INT_MAX;
vis[tmp] = 1;
for(auto j : to[tmp]) {
if(!vis[j.v]) {
d[j.v] = min(d[j.v], dis[tmp] + j.w + j.w * ((j.v == arr[db].v && tmp == arr[db].u) || (j.v == arr[db].u && tmp == arr[db].v)));
}
}
}
}
signed main() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
cin >> u >> v >> w;
to[u].push_back({v, w});
to[v].push_back({u, w});
arr[i] = {u, v, w};
}
dijkstra(0);
org = dis[n];
for(int i = 1; i <= m; i++) {
dijkstra(i);
ans = max(ans, dis[n]);
}
cout << ans - org << '\n';
return 0;
}