目录
1001 Blank
1002 Operation
1004 Vacation
1005 Path
1001 Blank
不会做，看题解。
设dp[i][j][k][l]表示4种颜色出现的最后的位置分别是i,j,k,l的方法数，保证i>=j>=k>=l。其实不取=号，因为同一个位置不能放两个元素，除了开始的若干个比如dp[1][0][0][0]=4。
合法的转移叠加：
比如
刷新的颜色是i：dp[i+1][j][k][l]+=dp[i][j][k][l]
刷新的颜色是j：dp[i+1][i][k][l]+=dp[i][j][k][l]
刷新的颜色是k：dp[i+1][i][j][l]+=dp[i][j][k][l]
刷新的颜色是l：dp[i+1][i][j][k]+=dp[i][j][k][l]
假如从dp[i][j][k][l]转移到上述状态会导致新状态不满足约束则不进行这次转移，就太麻烦了。
由于是dp，其实只要遇到约束区间的右端点R的时候再考虑约束就可以了。
考虑四个数其实是[l,k,j,i]，i肯定就是R，要是l>=L则有恰好4种颜色，否则要是k>=L则恰好3种颜色，否则要是j>=L则恰好2种颜色，否则只有1种颜色。
对每次转移后新状态的i维度必定是i+1，对i维度进行滚动节省空间。复杂度是精确的O(n4+mn3)，据说很多队觉得过不了。
还卡memset？？？15组数据还卡memset？
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read() {
int x = 0;
char c = 0;
while(c < '0' || c > '9')
c = getchar();
while(c >= '0' && c <= '9')
x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x;
}
inline void _write(int x) {
if(x > 9)
_write(x / 10);
putchar(x % 10 + '0');
}
inline void write(int x) {
_write(x);
putchar('
');
}
struct Condition {
int l, r, x;
bool operator<(const Condition &c)const {
return r < c.r;
}
} con[105];
const int mod = 998244353;
int n, m, dp[2][105][105][105], ctop;
inline void clear0(int n) {
for(int j = 0; j <= n; ++j) {
for(int k = 0; k <= j; ++k) {
for(int l = 0; l <= k; ++l) {
dp[n & 1][j][k][l] = 0;
}
}
}
}
inline void clear1(int i, int L) {
//清除==1种的
for(int j = L - 1 ; j >= 0; --j) {
for(int k = j ; k >= 0; --k) {
for(int l = k ; l >= 0; --l) {
dp[i & 1][j][k][l] = 0;
}
}
}
}
inline void clear2(int i, int L) {
//清除==2种的
for(int j = i ; j >= L; --j) {
for(int k = L - 1; k >= 0; --k) {
for(int l = k ; l >= 0; --l) {
dp[i & 1][j][k][l] = 0;
}
}
}
}
inline void clear3(int i, int L) {
//清除==3种的
for(int j = i ; j >= L ; --j) {
for(int k = j ; k >= L; --k) {
for(int l = L - 1; l >= 0; --l) {
dp[i & 1][j][k][l] = 0;
}
}
}
}
inline void clear4(int i, int L) {
//清除==4种的
for(int j = i ; j >= L ; --j) {
for(int k = j ; k >= L ; --k) {
for(int l = k ; l >= L; --l) {
dp[i & 1][j][k][l] = 0;
}
}
}
}
inline void update1(int i) {
if(ctop > m || i < con[ctop].r)
return;
while(ctop <= m && i == con[ctop].r) {
//printf("cons %d
", ctop);
int L = con[ctop].l, x = con[ctop].x;
++ctop;
if(x == 1) {
clear2(i, L);
clear3(i, L);
clear4(i, L);
} else if(x == 2) {
clear1(i, L);
clear3(i, L);
clear4(i, L);
} else if(x == 3) {
clear1(i, L);
clear2(i, L);
clear4(i, L);
} else {
clear1(i, L);
clear2(i, L);
clear3(i, L);
}
}
}
inline void update2(int i, int j, int k, int l) {
dp[(i + 1) & 1][j][k][l] += dp[i & 1][j][k][l];
if(dp[(i + 1) & 1][j][k][l] >= mod)
dp[(i + 1) & 1][j][k][l] -= mod;
dp[(i + 1) & 1][i][k][l] += dp[i & 1][j][k][l];
if(dp[(i + 1) & 1][i][k][l] >= mod)
dp[(i + 1) & 1][i][k][l] -= mod;
dp[(i + 1) & 1][i][j][l] += dp[i & 1][j][k][l];
if(dp[(i + 1) & 1][i][j][l] >= mod)
dp[(i + 1) & 1][i][j][l] -= mod;
dp[(i + 1) & 1][i][j][k] += dp[i & 1][j][k][l];
if(dp[(i + 1) & 1][i][j][k] >= mod)
dp[(i + 1) & 1][i][j][k] -= mod;
}
int solve() {
ctop = 1;
memset(dp[1], 0, sizeof(dp[1]));
dp[1][0][0][0] = 4;
update1(1);
for(int i = 1; i <= n - 1; ++i) {
//printf("i=%d
", i);
clear0(i + 1);
for(int j = i; j >= 0; --j) {
for(int k = j ; k >= 0; --k) {
if(k == j && k)
continue;
for(int l = k ; l >= 0; --l) {
if(l == k && l)
continue;
update2(i, j, k, l);
}
}
}
update1(i + 1);
for(int j = i; j >= 0; --j) {
for(int k = j; k >= 0; --k) {
if(k == j && k)
continue;
for(int l = k ; l >= 0; --l) {
if(l == k && l)
continue;
//printf("dp[%d][%d][%d][%d]=%d
", i + 1, j, k, l, dp[(i + 1) & 1][j][k][l]);
}
}
}
//printf("
");
}
int ans = 0;
for(int j = n - 1; j >= 0; --j) {
for(int k = j ; k >= 0; --k) {
for(int l = k ; l >= 0; --l) {
ans += dp[n & 1][j][k][l];
if(ans >= mod)
ans -= mod;
}
}
}
return ans;
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
int T = read();
while(T--) {
n = read(), m = read();
for(int i = 1; i <= m; ++i) {
con[i].l = read(), con[i].r = read(), con[i].x = read();
}
sort(con + 1, con + 1 + m);
write(solve());
}
return 0;
}
1002 Operation
这道题要用什么前缀线性基（类似的思想）。假如要求[1,r]的值能表示的最大值，那对每个位置保存一个前缀线性基，每次插入就复制前一个并插入就可以了。现在的问题是要求[l,r]里面的值能表示的最大值。题解有个思路，现在倒也觉得很显然，和以前尺取的做法一样，越靠右的元素一定越容易出现在[l,r]之中，插入一个新的元素的时候，由这个新元素从最高位开始贪心，遇到一个他能表示的位则和那个线性基进行交换，这样子就会有更多的贡献的可能，同时不会更差。求最大值的时候那也是从最高位开始向下问，在[l,r]范围内的就采用。
1004 Vacation
当时二分时间通过了这道题。实际上每辆车都会和前面的若干车组成一组通过终点线，所以只需要枚举每辆车通过终点线的时间，在时间中取最大值就可以了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000;
const double eps = 1e-9;
int l[maxn + 5], s[maxn + 5], v[maxn + 5], n;
double pos[maxn];
inline bool check(double t) {
pos[n - 1] = t * v[n - 1] + s[n - 1] - l[n - 1];
for(int i = n - 2; i >= 0; --i) {
if(t * v[i] + s[i] >= pos[i + 1])
pos[i] = pos[i + 1] - l[i];
else
pos[i] = t * v[i] + s[i] - l[i];
}
return pos[0] + l[0] >= -eps;
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
while(~scanf("%d", &n)) {
++n;
for(int i = 0; i < n; ++i)
scanf("%d", l + i);
for(int i = 0; i < n; ++i)
scanf("%d", s + i), s[i] = -s[i];
for(int i = 0; i < n; ++i)
scanf("%d", v + i);
double l = 0.0, r = 1e9;
while(r - l >= eps) {
double mid = (l + r) / 2.0;
if(check(mid))
r = mid;
else
l = mid;
}
printf("%.8f
", l);
}
return 0;
}
1005 Path
题意：给定一个有向图，删去其中的一些边使得1到n的最短路变长，删去边的代价与边的长度相等。
补题思路：跑一遍Dijkstra，找出两个点之间的最短路，然后遍历每一条边，假如边两端的最短距离就是边的长度，说明这条边是最短路的组成部分之一，注意到两点之间的最短路可能会有好几种走法，这样检查之后的确不会遗漏任何一种。比如1->2(4),2->3(6),1->3(10)，这样三条都是1->3最短路的组成部分。然后假如割断最短路连通的两端，则最短路一定变长了，所以变成了一个最大流的问题。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace Dijkstra {
const int MAXN = 1e4 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll dis[MAXN];
bool vis[MAXN];
struct Edge {
int v, w;
Edge() {};
Edge(int v, int w): v(v), w(w) {}
};
vector<Edge> G[MAXN];
priority_queue<pair<ll, int> >pq;
void dijkstra(int s, int n) {
memset(dis, INF, sizeof(dis[0]) * (n + 1));
memset(vis, false, sizeof(vis[0]) * (n + 1));
dis[s] = 0;
pq.push({-dis[s], s});
while(!pq.empty()) {
int u = pq.top().second;
pq.pop();
if(vis[u])
continue;
vis[u] = true;
for(auto e : G[u]) {
int v = e.v, w = e.w;
if(!vis[v] && dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
pq.push({-dis[v], v});
}
}
}
}
}
using namespace Dijkstra;
namespace Dinic {
const int MAXN = 1e4 + 5;
const int MAXM = 2e4 + 500;
const int INF = 1e18;
int top;
int head[MAXN];
struct Edge {
int to, next;
ll cap, flow;
Edge() {}
Edge(int to, int next, ll cap, ll flow): to(to), next(next), cap(cap), flow(flow) {}
} e[MAXM];
void Init() {
top = 2;
memset(head, -1, sizeof(head));
}
void AddEdge(int u, int v, ll w = 1, ll rw = 0) {
e[top] = Edge(v, head[u], w, 0);
head[u] = top++;
e[top] = Edge(u, head[v], rw, 0);
head[v] = top++;
}
int Q[MAXN];
int dep[MAXN], cur[MAXN], sta[MAXN];
bool bfs(int s, int t) {
int fnt = 0, bak = 0;
memset(dep, -1, sizeof(dep[0]) * (t + 1));
dep[s] = 0;
Q[bak++] = s;
while(fnt < bak) {
int u = Q[fnt++];
for(int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].to;
if(dep[v] == -1 && e[i].cap > e[i].flow) {
dep[v] = dep[u] + 1;
if(v == t)
return true;
Q[bak++] = v;
}
}
}
return false;
}
ll dinic(int s, int t) {
ll maxflow = 0;
while(bfs(s, t)) {
for(int i = 0; i <= t; i++)
cur[i] = head[i];
int u = s, tail = 0;
while(cur[s] != -1) {
if(u == t) {
ll tp = INF;
for(int i = tail - 1; i >= 0; i--)
tp = min(tp, e[sta[i]].cap - e[sta[i]].flow);
maxflow += tp;
for(int i = tail - 1; i >= 0; i--) {
e[sta[i]].flow += tp;
e[sta[i] ^ 1].flow -= tp;
if(e[sta[i]].cap - e[sta[i]].flow == 0)
tail = i;
}
u = e[sta[tail] ^ 1].to;
} else if(cur[u] != -1 && e[cur[u]].cap > e[cur[u]].flow
&& dep[u] + 1 == dep[e[cur[u]].to]) {
sta[tail++] = cur[u];
u = e[cur[u]].to;
} else {
while(u != s && cur[u] == -1)
u = e[sta[--tail] ^ 1].to;
cur[u] = e[cur[u]].next;
}
}
}
return maxflow;
}
}
using namespace Dinic;
int main() {
#ifdef Yinku
//freopen("Yinku.in", "r", stdin);
#endif // Yinku
int T;
scanf("%d", &T);
while(T--) {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)
G[i].clear();
for(int i = 1, u, v, w; i <= m; ++i) {
scanf("%d%d%d", &u, &v, &w);
G[u].push_back({v, w});
}
dijkstra(1, n);
Init();
for(int u = 1; u <= n; ++u)
for(auto &e : G[u])
if(dis[e.v] - dis[u] == e.w)
AddEdge(u, e.v, e.w);
printf("%lld
", dinic(1, n));
}
return 0;
}