T2
开的第一题，难度不高，不想说什么。
写的比较仓促，所以码风可能不是很好，不知道为什么忘记用struct了。
满分。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const ll inf = 4e18;
ll n, m, q, a[N], b[N], mxa[N][21], mna[N][21], mxb[N][21], mnb[N][21], mxa1[N][21], mna1[N][21];
inline ll querymxa(ll l, ll r)
{
ll k = log2(r - l + 1);
return max(mxa[l][k], mxa[r - (1 << k) + 1][k]);
}
inline ll querymna(ll l, ll r)
{
ll k = log2(r - l + 1);
return min(mna[l][k], mna[r - (1 << k) + 1][k]);
}
inline ll querymxa1(ll l, ll r)
{
ll k = log2(r - l + 1);
return max(mxa1[l][k], mxa1[r - (1 << k) + 1][k]);
}
inline ll querymna1(ll l, ll r)
{
ll k = log2(r - l + 1);
return min(mna1[l][k], mna1[r - (1 << k) + 1][k]);
}
inline ll querymxb(ll l, ll r)
{
ll k = log2(r - l + 1);
return max(mxb[l][k], mxb[r - (1 << k) + 1][k]);
}
inline ll querymnb(ll l, ll r)
{
ll k = log2(r - l + 1);
return min(mnb[l][k], mnb[r - (1 << k) + 1][k]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> q;
for (ll i = 1; i <= n; i++)
{
cin >> mxa[i][0];
mna[i][0] = mxa[i][0];
if (mxa[i][0] >= 0)
{
mna1[i][0] = mxa[i][0];
mxa1[i][0] = -inf;
}
else
{
mna1[i][0] = inf;
mxa1[i][0] = mxa[i][0];
}
}
for (ll i = 1; i <= m; i++)
{
cin >> mxb[i][0];
mnb[i][0] = mxb[i][0];
}
for (ll i = 1; i <= 20; i++)
for (ll j = 1; j + (1 << i) - 1 <= n; j++)
{
mxa[j][i] = max(mxa[j][i - 1], mxa[j + (1 << i - 1)][i - 1]);
mna[j][i] = min(mna[j][i - 1], mna[j + (1 << i - 1)][i - 1]);
mxa1[j][i] = max(mxa1[j][i - 1], mxa1[j + (1 << i - 1)][i - 1]);
mna1[j][i] = min(mna1[j][i - 1], mna1[j + (1 << i - 1)][i - 1]);
}
for (ll i = 1; i <= 20; i++)
for (ll j = 1; j + (1 << i) - 1 <= m; j++)
{
mxb[j][i] = max(mxb[j][i - 1], mxb[j + (1 << i - 1)][i - 1]);
mnb[j][i] = min(mnb[j][i - 1], mnb[j + (1 << i - 1)][i - 1]);
}
while (q--)
{
ll l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
ll Mxa = querymxa(l1, r1), Mxb = querymxb(l2, r2), Mna = querymna(l1, r1), Mnb = querymnb(l2, r2), Mxa1 = querymxa1(l1, r1), Mna1 = querymna1(l1, r1), ans = -inf;
ans = max(ans, Mxa * (Mxa >= 0 ? Mnb : Mxb));
ans = max(ans, Mna * (Mna >= 0 ? Mnb : Mxb));
if (Mxa1 != -inf)
ans = max(ans, Mxa1 * (Mxa1 >= 0 ? Mnb : Mxb));
if (Mna1 != inf)
ans = max(ans, Mna1 * (Mna1 >= 0 ? Mnb : Mxb));
cout << ans << '\n';
}
return 0;
}
T1
开的第二题。
第一眼想到SPFA，但是写完发现四个点不重复好像很难实现。
当时没发现根本没法阻止重复，以为是bug，调了很久，心态崩了，所以就交了。
喜提55。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2505, M = 2e4 + 5;
int n, m, p, a[N], head[N], to[M], nxt[M], tot, _empty_array[4];
ll dis[N][105][5], ans;
bool vis[N][105][5];
inline void link(int u, int v)
{
to[tot] = v;
nxt[tot] = head[u];
head[u] = tot++;
}
struct node
{
int x, k, use, pos[4];
inline node()
{
x = k = use = 0;
memset(pos, 0, sizeof(pos));
}
inline node(int _x, int _k, int _use, int _pos[])
{
x = _x;
k = _k;
use = _use;
for (int i = 0; i < 4; i++)
pos[i] = _pos[i];
}
};
queue<node> q;
inline void spfa()
{
memset(dis, -1, sizeof(dis));
q.emplace(node(1, p, 0, _empty_array));
vis[1][p][0] = true;
dis[1][p][0] = 0;
while (!q.empty())
{
node x = q.front();
q.pop();
vis[x.x][x.k][x.use] = false;
for (int i = head[x.x]; ~i; i = nxt[i])
{
if (to[i] > 1 && x.k > 0 && dis[to[i]][x.k - 1][x.use] < dis[x.x][x.k][x.use])
{
dis[to[i]][x.k - 1][x.use] = dis[x.x][x.k][x.use];
if (!vis[to[i]][x.k - 1][x.use])
{
vis[to[i]][x.k - 1][x.use] = true;
q.emplace(node(to[i], x.k - 1, x.use, x.pos));
}
}
if (to[i] > 1 && x.use < 4 && dis[to[i]][p][x.use + 1] < dis[x.x][x.k][x.use] + a[to[i]])
{
bool flag = true;
for (int j = 0; j < x.use; j++)
if (x.pos[j] == to[i])
{
flag = false;
break;
}
if (flag)
{
dis[to[i]][p][x.use + 1] = dis[x.x][x.k][x.use] + a[to[i]];
if (!vis[to[i]][p][x.use + 1])
{
vis[to[i]][p][x.use + 1] = true;
x.pos[x.use] = to[i];
q.emplace(node(to[i], p, x.use + 1, x.pos));
}
}
}
if (x.use == 4 && to[i] == 1)
ans = max(ans, dis[x.x][x.k][x.use]);
}
}
cout << ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
memset(head, -1, sizeof(head));
cin >> n >> m >> p;
for (int i = 2; i <= n; i++)
cin >> a[i];
for (int i = 1, u, v; i <= m; i++)
{
cin >> u >> v;
link(u, v);
link(v, u);
}
spfa();
return 0;
}
T3
开的第三题。
很快想到，如果满足条件1，条件2没有任何作用。
一个$n$点$n$边的图构成了一个基环树，显然满足条件2，因此只需要判断条件1就行了。
因此，一个$map$记录每个$u\to v$对应的边的编号，一个$has[]$记录边是否还存在。删边/修边直接$O(logn)$（map的复杂度）解决，删点/修点暴力$O(n)$解决。
操作1/3时间复杂度：$O(logn)$
操作2/4时间复杂度：$O(n)$
出题人还算良心，测试点11和12并没有太多操作4，所以拿了60。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
int n, m, q, head[N], from[N << 1], to[N << 1], nxt[N << 1], tot, out[N], cnt;
bool has[N << 1];
map<pair<int, int>, int> mp;
inline void link(int u, int v)
{
to[tot] = v;
has[tot] = true;
nxt[tot] = head[u];
head[u] = tot++;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
memset(head, -1, sizeof(head));
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++)
{
cin >> u >> v;
link(v, u);
out[u]++;
mp[make_pair(u, v)] = tot - 1;
}
for (int i = 1; i <= n; i++)
if (out[i] == 1)
cnt++;
cin >> q;
while (q--)
{
int op, u, v;
cin >> op;
switch (op)
{
case 1:
cin >> u >> v;
if (out[u] == 1)
cnt--;
else if (out[u] == 2)
cnt++;
out[u]--;
has[mp[make_pair(u, v)]] = false;
break;
case 2:
cin >> u;
for (int i = head[u]; ~i; i = nxt[i])
if (has[i])
{
if (out[to[i]] == 1)
cnt--;
else if (out[to[i]] == 2)
cnt++;
has[i] = false, out[to[i]]--;
}
break;
case 3:
cin >> u >> v;
if (!out[u])
cnt++;
else if (out[u] == 1)
cnt--;
out[u]++;
has[mp[make_pair(u, v)]] = true;
break;
default:
cin >> u;
for (int i = head[u]; ~i; i = nxt[i])
if (!has[i])
{
if (!out[to[i]])
cnt++;
else if (out[to[i]] == 1)
cnt--;
has[i] = true, out[to[i]]++;
}
}
cout << (cnt == n ? "YES\n" : "NO\n");
}
return 0;
}
T4
没开。。。
感觉自己应该做不出来，而且前三题时间差不多也满了。
总结
55 + 100 + 60 + 0 = 215pts。
第一题听说爆搜分能拿70。。。
6级线183，7级线240，我是6级线。
希望明年能7级勾吧，毕竟还有将近一年呢。
标签：use,int,ll,VP,2022,ans,dis,CSP,out From： https://www.cnblogs.com/creation-hy/p/CSP-S-2022-VP.html