分类目录归档:题解

2018江苏省大学生程序设计竞赛(JSCPC)总结

题面:JSCPC2018 (1)

因为能拿到官方题解,我自己就不在写题解了(逃…

官方题解:analysis(1)

终榜:

开场后,扫了一眼发现A是水题加原题,然后我直接上去写,WA。重新读题,发现看错题意了,重写过了(14′)。这时,上机队列已经满了。Calabash_boy告诉我F题是个排序题,我上去写了个带比较器的sort,WA。仔细一查是爆ull了,换了一种写法过了(28′)。Roundgod把K题改对(30′)后,Calabash_boy又告诉我G题是个水题,我上去乱写一通交上去过了(35′),并且拿到了一血。这时队列已经空了,并且由于开场过题太猛,升到了榜首,无法跟榜,不知道开哪题。卡了近半小时后,Roundgod写了个B的二分,1A(62′)。随后开始长时间掉线,Roundgod开了D题发现推不出公式,又说J题是神仙题。我发现I题可能可做,就开始想I。看榜发现有队过C,Calabash_boy想了个两个log的做法,感觉有点虚。由于机时空出来了,Calabash_boy就开始敲二分主席树(我:这是啥?(懵逼脸))。刷榜发现J题有过,再一看J并不是神仙题,直接preemptive multitasking双开JC。J写完后发现WA,然后切C在写。J题改了又交,时间片切了快10次,还是不过,已经6发罚时了,心态有点崩。我查了一下代码,发现有个地方ans没取模,加上去后J题就过了(172′)。随后,C题也写出来了,交上去也过(186′)(葫芦爷真是太强辣)。又开始卡题了,发现I已经有人过了,我就接着想I。I题想了个算法,感觉有点难实现,然后抱着反正没人要机时,不用白不用的想法上去敲。敲了一个多小时,发现答案总是不对,一查发现之前想的算法全是假的。这时已经封榜了。Calabash_boy说E可以尝试一下,然后4:52写出来了,交上去T了。怀疑被卡常数,加了点剪枝还是T。发现剪枝是假的,我就帮着玄学卡常,但到比赛结束都没有做出来。最终7题Rank7(去掉打星队Rank6),特等奖。

总的来说,前期切水题比较快,积累了一些罚时优势,但由于中档题还不是很熟练,并没有什么卵用,最后还是掉下去了。以后还是要加强中档题和中等偏上难度题的训练。

 

2016 China Collegiate Programming Contest Final 题解

题面:http://codeforces.com/gym/101206/attachments/download/5010/ccpc-20162017-finals-en.pdf

(更新中)

Problem A. The Third Cup is Free

有n杯咖啡,每三杯咖啡中最便宜的那杯可以免单,求最小花费。

题解

签到题。从大到小排好序后,每三个免一个即可。

代码:(by Roundgod)

#include<bits/stdc++.h>
#define MAXN 100005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int t,n,a[MAXN];
int main()
{
    scanf("%d",&t);
    int kase=0;
    while(t--)
    {
        kase++;
        printf("Case #%d: ",kase);
        scanf("%d",&n);
        int sum=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d", &a[i]);
            sum += a[i];
        }
        sort(a,a+n);
        for(int i=n-3;i>=0;i-=3)
            sum-=a[i];
        printf("%d\n",sum);
    }
    return 0;
}

Problem B. Wash

给定L件脏衣服,N台洗衣机,D台烘干机。第i台洗衣机要花Wi时间洗一件脏衣服,第j台烘干机要花Dj时间烘干一件衣服。衣服必须先洗完再烘干。所有机器可以并行工作。问洗完并烘干所有衣服要多少时间。

数据范围:$1 \leq L \leq 10^6, 1 \leq N, M \leq 10^5, 1 \leq W_i, D_i \leq 10^9 $

题解

我们先考虑只洗衣服该如何安排。显然每台洗衣机中间不会停止工作,否则我们将后面的任务向前移动,不会得到一个更差的解。这样,第i台洗衣机洗完地j件衣服的时间就是$w_{ij} = jW_{i}$。只要选取前L小的$T_{ij}$即可。为便于实现,可用优先队列。

同理,可处理出前L小的$d_{ij}$烘干时间。下面我们就是要求一个$w_{ij}$和$d_{ij}$的完美匹配,使得对应的$w_{ij}$和$d_{ij}$的和的最大值最小。这只需要将$w_{ij}$正向排序,$d_{ij}$反向排序,然后一一匹配即可。容易证明,这样匹配一定是最优的。

代码:(by sy_chen)

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
  __func__, ##__VA_ARGS__)
#else
# define _debug(...) (void(0))
#endif

#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ull;

int l, n, m;
LL w[100006], d[100006];
LL t1[1000006], t2[1000006];

typedef pair<LL, int> p;

int main() {
  int T; scanf("%d", &T);
  Rep (t, T) {
    priority_queue<p, vector<p>, greater<p> > q1, q2;
    scanf("%d%d%d", &l, &n, &m);
    rep (i, n) {
      int a; scanf("%d", &a);
      w[i] = a;
      q1.push({w[i], i});
    }
    rep (i, m) {
      int a; scanf("%d", &a);
      d[i] = a;
      q2.push({d[i], i});
    }
    rep (i, l) {
      LL val; int id;
      tie(val, id) = q1.top(); q1.pop();
      _debug("i=%d, val=%lld, id=%lld, l-1-i=%d", i, val, id, l-1-i);
      t1[i] = val;
      q1.push({val+w[id], id});
    }
    rep (i, l) {
      LL val; int id;
      tie(val, id) = q2.top(); q2.pop();
      _debug("i=%d, val=%lld, id=%lld, l-1-i=%d", i, val, id, l-1-i);
      t2[l-1-i] = val;
      q2.push({val+d[id], id});
    }
    LL ans = 0;
    rep (i, l) {
      ans = max(ans, t1[i] + t2[i]);
    }
    cout << "Case #" << t << ": " << ans << endl;
  }
  return 0;
}

Problem C. Mr. Panda and Survey


Problem D. Game Leader


Problem E. Problem Buyer


Problem F. Periodical Cicadas


Problem G. Pandaland

给出一个4000个点的带权无向图,求图中的最小权环。

题解

枚举所有边,删去该边后,求这条边两点间的最短路,然后加上该边的权值,取最小值即可。

注意,当图中不含圈时,要输出0(而不是-1)(补题的时候因为这个原因WA了5发,qaq…

代码:(by aequa)

#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
    __func__, ##__VA_ARGS__)
#else 
# define _debug(...) ((void) 0)
#endif
#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ULL;

#define int LL
#undef INT_MAX
#define INT_MAX LLONG_MAX

typedef pair<int, int> pt;


struct Sol {
  int n = 0;
  map<pt, int> mp;
  vector<pair<int, int>> edges;
  vector<vector<int>> adj;

  int getID(int x, int y) {
    auto ptr = mp.find({x, y});
    if (ptr != mp.end()) return ptr->second;
    mp[{x, y}] = n;
    adj.push_back({});
    return n++;
  }
  
  int ans = INT_MAX / 2;
  int d[10000];
  bool done[10000];

  void dijkstra(int src) {
    priority_queue<pt, vector<pt>, greater<pt>> q;

    fill(d, d+n, INT_MAX / 2);
    d[src] = 0;
    fill(done, done+n, false);
    q.push({0, src});
    while (q.size()) {
      int u = q.top().second; q.pop();
      if (done[u]) continue;
      done[u] = 1;
      for (int id : adj[u]) {
        int v, w; tie(v, w) = edges[id];
        if (d[v] > d[u] + w) {
          d[v] = d[u] + w;
          if (d[v] < ans) q.push({d[v], v});
        }
      }
    }
  }

  Sol(int t) {
    int m; cin >> m;
    edges.resize(m+m);
    rep (i, m) {
      int x1, y1, x2, y2, w;
      int id1, id2;
      cin >> x1 >> y1 >> x2 >> y2 >> w;
      id1 = getID(x1, y1); id2 = getID(x2, y2);
      edges[i<<1] = {id2, w};
      edges[i<<1|1] = {id1, w};
      adj[id1].push_back(i<<1);
      adj[id2].push_back(i<<1|1);
    }
    rep (u, n) {
      for (int id : adj[u]) {
        int v, w;
        tie(v, w) = edges[id];
        edges[id].second = edges[id^1].second = INT_MAX / 2;
        dijkstra(u);
        ans = min(ans, d[v] + w);
        edges[id].second = edges[id^1].second = w;
      }
    }
    if (ans >= INT_MAX / 2) ans = 0;
    cout << "Case #" << t << ": " << ans << endl;
  }
};

int32_t main() {
  int T; cin >> T;
  Rep (t, T) {
    Sol sol(t);
  }
  return 0;
}

 


Problem H. Engineer Assignment


Problem I. Mr. Panda and Crystal

有N种宝石,每种宝石有一些价值。有些宝石可以直接由法力值合成。此外,还存在K种合成方案,可以利用若干已有的宝石合成新的宝石。给定初始的法力值M,求能够合成的宝石的价值的最大值。

数据范围:$1 \leq M \leq 10000, 1 \leq N \leq 200, 1 \leq K \leq 200$

题解

背包的变形题。本题主要的问题是,一种宝石可能有多种获得方法,除了可以直接用法力值合成外,还有可能存在多种合成该宝石的方案。我们希望预处理出来(直接或间接)获得该种宝石的最小法力值消耗。由于更新一种宝石的最小法力值消耗可能会影响其他宝石的最小法力值消耗,这很像最短路中更新某个节点的距离会影响其他节点的距离,因此可以采用Bellman-Ford算法,迭代更新直到无法更新为止。显然这么做的复杂度是$N^2K$的。预处理出来后,直接套多重背包即可。

代码:(by sy_chen)

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
  __func__, ##__VA_ARGS__)
#else
# define _debug(...) (void(0))
#endif

#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ull;

int m, n, k;
LL c[256], v[256];

vector<int> dep[205];
//   id                id  cnt
pair<int, vector<pair<int, int>>> formula[205];

bool flag = false;

void update(int i) {
  LL tot = 0;
  int id = formula[i].first;
  for (auto& item : formula[i].second) {
    tot += c[item.first] * item.second;
  }
  if (tot < c[id]) {
    _debug("update %d!", formula[i].first);
    c[formula[i].first] = tot;
    flag = true;
  }
}

LL dp[10005];

int main() {
  int T; scanf("%d", &T);
  Rep (t, T) {
    scanf("%d%d%d", &m, &n, &k);
    Rep (i, n) {
      int tp; scanf("%d", &tp);
      int co = INT_MAX, va = 0;
      if (tp == 0) {
        scanf("%d", &va);
      } else {
        scanf("%d%d", &co, &va);
      }
      c[i] = co;
      v[i] = va;
    }
    _debug("!");
    rep (i, k) {
      int x, y;
      scanf("%d%d", &x, &y);
      formula[i].first = x;
      formula[i].second.resize(y);
      rep (j, y) {
        int u, v;
        scanf("%d%d", &u, &v);
        formula[i].second[j] = {u, v};
      }
    }
    _debug("!");
    do { // bellman-ford
      flag =  false;
      rep (i, k) update(i);
    } while (flag);
    memset(dp, 0, sizeof dp);
    Rep (i, n) {
      for (int w = c[i]; w <= m; w++) {
        dp[w] = max(dp[w], dp[w - c[i]] + v[i]);
      }
    }
    printf("Case #%d: %d\n", t, int(dp[m]));
  }
  return 0;
}

Problem J. Worried School


Problem K. Lazors

神仙题。


Problem L. Daylight Saving Time

每年的三月的第二个星期日的2点整,将时间拨快1小时,进入夏令时(PST);每年的十一月的第一个星期日的2点整,将时间拨慢1小时,进入标准时(PDT)。给一个日期和时间,判断该时间是PST,PDT,两者都有可能或是两者都不可能。时间在2007-01-01 00:00:00和2100-12-31 23:59:59之间。

题解

只要预处理出每一天的类型(一定是PST,一定是PDT,从PST变换为PDT,从PDT变换为PST),然后分情况讨论即可。

实现的时候要注意处理闰年的情况。除2100年外,年数是4的倍数就是闰年。

代码:(by sy_chen)

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
  __func__, ##__VA_ARGS__)
#else
# define _debug(...) (void(0))
#endif

#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned long long ull;

enum {
  A, B, C, D
};

const int  mday[13] = { 0,
  31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};

int type = A;
int yy = 2007, mm = 1, dd = 1;
int wday = 1;

bool isleap(int y) {
  if (y % 4 == 0  && y != 2100) return true;
  return false;
}

void adv_year() {
  yy++;
}

void adv_month() {
  mm++;
  if (mm > 12) {
    mm = 1;
    adv_year();
  }
}

int advan() {
  dd++;
  wday ++;
  if (wday > 7) wday = 1;
  int mmday = mday[mm];
  if (mm == 2 && isleap(yy)) mmday++;
  if (dd > mmday) {
    dd = 1;
    adv_month();
  }
  if (mm == 3 && wday == 7 && dd > 7 && dd <= 14) {
    type = C;
    return B; 
  }
  if (mm == 11 && wday == 7 && dd <= 7) {
    type = A;
    return D;
  }
  return type;
}

string genstr() {
  char buf[100];
  sprintf(buf, "%04d-%02d-%02d", yy, mm, dd);
  return string(buf);
}

map<string, int> m;

void prep() {
  m[genstr()] = type;
  do {
    int tp = advan();
    m[genstr()] = tp;

  } while (yy <= 2100);
}


int main() {
  prep();
  string str;
  char tim[20];
  int hh;
  int T;
  cin >> T;
  Rep(t, T) {
    cin >> str >> tim;
    sscanf(tim, "%d", &hh);
    switch (m[str]) {
      case A:
        printf("Case #%d: PST\n", t);
        break;
      case B:
        if (hh < 2) {
          printf("Case #%d: PST\n", t);
        } else if (hh >= 3) {
          printf("Case #%d: PDT\n", t);
        } else {
          printf("Case #%d: Neither\n", t);
        } 
        break;
      case C:
        printf("Case #%d: PDT\n", t);
        break;
      case D:
        if (hh < 1) {
          printf("Case #%d: PDT\n", t);
        } else if (hh >= 2) {
          printf("Case #%d: PST\n", t);
        } else {
          printf("Case #%d: Both\n", t);
        } 
        break;
    }
  }
  return 0;
}

线性代数相关OJ题选讲

这篇文章是关于线性代数的OJ题选讲,这几道题目都不难,主要是考察思维的灵活程度。


Fast Matrix Calculation

2014 Multi-University Training Contest 9, available at HDUOJ 4965

给定 $N\times k$ 的矩阵 $A$,$k \times N$ 的矩阵 $B$ $(2 \leq k \leq 6, 4 \leq N \leq 1000)$:
Step 1. 计算 $N \times N$ 的矩阵 $C = AB$.
Step 2. 计算 $M = C^{N \times N} \bmod 6$.
Step 3. 输出 $M$ 中所有元素的和.

题解

根据矩阵乘法的结合律,

\[M = (AB)^{N \times N} = A (BA)^{N \times N – 1} B\]

时间复杂度由裸的快速幂$O(N^3 \log N)$变成了$O(N^2k + Nk^2 + k^3 \log N)$。


Matrix Multiplication

2014 Multi-University Training Contest 5, available at HDUOJ 4920

给定$n \times n$的矩阵$A, B$,求模3意义下的乘积。 $(1 \leq n \leq 800)$

题解

令 $M_x$: $M_x(i, j) = [M(i, j) = x]$.

\[ AB = (A_1 – A_2)(B_1 – B_2) = A_1B_1 – A_1B_2 – A_2B_1 + A_2B_2 \]

其中 $A_1, A_2, B_1, B_2$ 是 01矩阵. 使用 std::bitset,可以做做到$O(4n^3/wordsize)$。

(当然,使用其他一些优秀的卡常方法也能过这题)


Matrix Revolution

HDUOJ 1759

给定一个 $n \times n$ 的矩阵 $A$,计算下述矩阵的非零元素的数量

\[ A + A^2 + \cdots + A^k\]

$A$ 是稀疏矩阵,用 $m$ 个三元组 $(a, b, c)$ 表示,每个三元组代表 $A_{ab} = c$。此外,保证主对角线上的元素全为 1。其他元素均为0。

$(0 \leq n \leq 1000, 0 \leq m \leq 10n, n < k < 10^{100}, 0 < c < 10^9)$

题解

利用图的邻接矩阵表示,可知答案就是距离不超过 $k$ 的点对数。


Matrix Multiplication

POJ 3318

给定 $n \times n$ 的矩阵 $A, B, C$。判断$A B = C$是否成立。$(n \leq 500, |A_{ij}|, |B_{ij}| \leq 100, |C_{ij}| \leq 10,000,000)$

提示:有多组测试数据,$O(n^3)$ 的算法会 TLE。

题解

随机生成 $n$ 维列向量 $\vec{x}$,判断 $AB\vec{x} = C\vec{x}$ 是否成立。可在 $O(n^2)$ 时间内完成。

算法出错当且仅当 $(AB-C)\vec{x} = 0$ 而 $AB – C \neq 0$。 假设我们在 $\mathbb{F}_p$ 里做。令 $M = AB – C$, 则 $\vec{x}$ 在 $M$ 的零空间中。仔细想一想 $M$ 的零空间最多 $n-1$ 维,因此出错的概率不会超过$1/p$。

(当然,使用三次方的算法加一些优秀的卡常,也许也能过)

Remark: 

这一算法被称为Freivalds算法,是一种单边错Monte Carlo随机算法。对于整数矩阵,存在确定性的$O(n^2)$的算法判断乘法是否正确。不过由于Freivalds算法非常易于实现,目前实际上仍然大量使用该算法 。


Square

UVA 11542, also available at vjudge

给定 $n$ 个整数的集合你可以生成 $2^n-1$ 个非空子集。求有多少个子集,其中的数之积为完全平方数。

$1 \leq T \leq 30$, $1 \leq n \leq 100$, 所有整数在 1 和 $10^{15}$ 之间。整数的素因子最多为 500。

题解

每个整数的唯一分解序列都看成 $\mathbb{F}_2$ 上的一个的向量,就是要求这些向量构成矩阵的零空间的大小。

2017-2018年问题求解(三)期末上机考试 Day2 题解

C. 花椰菜与西兰花

题意:有一块菜地,被分成 $latex n \times m$ 格,每格被种上花椰菜、西兰花或什么都不种。现在要在格子之间建一些篱笆,使得被篱笆分隔出来的每一连通区域中,至多只有一种作物。问篱笆的总长度最少是多少。

数据范围:$latex 1 \leq n \leq 50, 1 \leq m \leq 1000$

题解:最小割还是挺明显的。源点到所有花椰菜连上无穷容量边,所有西兰花到汇点连无穷容量边,然后相邻两个区域连容量为 1 的双向边。根据 MFMC 定理,答案就是从源点到汇点的最大流。

D. 旅游路线

题意:有 $latex n$ 个区域,每个区域内有 $latex s_i$ 个车站。区域内的车站之间移动需花费 $latex k_i$ 时间;此外,还有 $latex m$ 辆班车来回于两个车站之间,并需要花费 $latex c_j$ 代价。问从 1 号区域的第 1 个车站到 $latex n$ 号区域至少需要花费多少时间。

数据范围:

  • 部分数据满足 $latex 1≤n≤20, 1≤m≤100, 1≤s_i≤5, 1≤k_i, c≤1000$;
  • 部分数据满足 $latex 1≤n≤1000, 1≤m≤50000, 1≤s_i≤200, 1≤k_i, c≤1000$;
  • 部分数据满足 $latex 1≤n≤30000, 1≤m≤2*10^5, s_i=1, 1≤k_i, c≤1000$;
  • 部分数据满足 $latex 1≤n≤5000, 1≤m≤2*10^5, 1≤s_i≤50, 1≤k_i, c≤1000$。

题解:最短路,但是裸的 Dijkstra 肯定是过不了的。这是因为区域内暴力连边的话,会形成完全图,导致边数爆炸。为此,可以为每个区域设置一个特殊节点,该节点可以表示从区域内任何一个节点出发。这样,每个区域内的点都可以连一条长度为 $latex k_i$ 的单向边到该特殊节点,此外,从该区域中的某一点出发的边,同样也可以从特殊节点出发。这样整个图中只有 $latex m + \sum s_i $ 条边,跑 Dijkstra 就不会T了。

2017-2018年问题求解(三)期末上机考试 Day1 题解

A. 智能机器

题意:求 $latex \sum_{i=l}^r d(i^k)$ 模 16290047,其中 $latex d(n)$ 表示 $latex n$ 的约数个数。

数据范围:$latex r – l \leq 10^6, l \leq r \leq 10^{12}, k \leq 10^6$。

题解:首先,对于任意正整数 $latex n$,如果它的唯一分解为

$$ n = q_1^{a_1} q_2^{a_2} \cdots q_m^{a_m} $$

那么它的约数个数就是

$$ d(n) = (1+a_1)(1+a_2)\cdots(1+a_m) $$

从而

$$ d(n^k) = (1+ka_1)(1+ka_2)\cdots(1+ka_m) $$

这样,我们只要对每个要求的 $latex i$,找出所有形如 $latex p^x | i$ 中 $latex x$ 最大的因子。注意到这样的因子不可能超过 $latex \sqrt{i}$,除非 $latex x = 1$。从而我们对素数 $latex p$,可以枚举 l~r 区间范围内的 $latex rp^x$ 形式的数(其中 $latex r$ 不是 $latex p$ 的倍数),并乘上 $latex kx+1$ 的贡献。如果某个数除以所有枚举过的 $latex p^x$ 形式的因子仍然不为 1,说明剩下的数一定是一个素数,那么还要乘上 $latex k+1$ 的贡献。

经过仔细的分析,上述三重循环枚举的时间复杂度实际上不会超过 $latex O(\frac{\sqrt{r}}{\log r} \log (r – l))$,完全可以接受。

B.  Lunatic

题意:一共有 $latex n$ 个动作,每个动作可以在 $latex [l_i, r_i]$ 之间的某个时刻完成,完成后可得到 $latex v_i$ 分数。每一时刻只能做一样动作,计算最多能拿多少分。

数据范围:$latex 1 \leq n \leq 1000, 1 \leq s_i \leq t_i \leq 30000, 1 \leq v_i \leq 1000$

题解:显然是带权二分图的最大权匹配。考场上没带 Kuhn-Munkres 的板子,只好敲费用流,最后 2 分钟卡过去的…(不过这题用裸的 KM 算法应该也过不了 233)其实这题标答是贪心匹配,将边按收益排序,优先匹配收益高的就行了…

说一下费用流的做法吧。每个动作连一条容量为 1,费用为 $latex -v_i$ 的边到 $latex [l_i, r_i]$ 中的每个时间点,源点到每个动作连费用为 0 容量为 1 的边,每个时间点连费用为 0 容量为 1 的边到汇点,然后跑最小费用流取负就好了。不过这样是过不了全部数据的,要过全部数据,还要加两个优化:一是把时间区间离散化;二是如果某个动作有 $latex r_i – l_i + 1 \geq n$,那么这个动作一定可以在某个时刻完成,就不需要加到图里面了。