1. 可达性统计

时间：半小时之内
https://www.acwing.com/problem/content/166/

思路：

  • 暴力，每一个点做一次dfs探查能到达多少个点
  • 拓扑排序加bitset记录能到达的点。A能到达B点，则A所能到达的点就是A这个点本身并上B所能到达的点，同理，B所能到达的点则为B这个点并上与B相连的点所能到达的点，如果一个点出度为0，该点只能到达它本身。因此，只需要做个拓扑排序（将所有边反向），第一次找出度为0的点，这些点可以直接确定所能到达的点，接着再继续更新与这些点相邻的点，为了便于直接查找哪些点到达这个出度为0的点，所以处理之前将所有边反向。

代码示例：

  1. #include <iostream>
  2. #include <bitset>
  3. #include <vector>
  4. #include <queue>
  6. using namespace std;
  8. struct Edge{
  9.     int to;
  10.     Edge(int _v){to = _v;}
  11. };
  12. typedef struct Edge Edge;
  14. int n, m;
  15. int deg[30005];
  16. bitset<30005> bs[30005];
  18. vector<Edge> revg[30005];
  21. void top_sort(){
  22.     queue<int> que;
  23.     for(int i = 1; i <= n; i++){
  24.         if(deg[i] == 0){
  25.             que.push(i);   
  26.         }
  27.     }
  28.     while(!que.empty()){
  29.         int t = que.front();
  30.         que.pop();
  31.         bs[t].set(t, 1);
  32.         for(int i = 0; i < revg[t].size(); i++){
  33.             Edge e = revg[t][i];
  34.             bs[e.to] |= bs[t];
  35.             deg[e.to]--;
  36.             if(deg[e.to] == 0){
  37.                 que.push(e.to);
  38.             }
  39.         }
  40.     }
  41. }
  43. int main(){
  44.     int a, b;
  45.     cin>>n>>m;
  46.     for(int i = 0; i < m; i++){
  47.         cin>>a>>b;
  48.         revg[b].push_back(Edge(a));
  49.         deg[a]++;
  50.     }
  52.     top_sort();
  53.     for(int i = 1; i <= n; i++){
  54.         cout<<bs[i].count()<<endl;
  55.     }
  57.     return 0;
  58. }

2. 小猫爬山

https://www.acwing.com/problem/content/167/

思路：

  • 贪心，每次从第一个缆车开始找，能放的进就直接放（WA，过不了， 比如5 5 1 2 3 4 5这组数据）
  • 纯暴力，找出所有可能，TLE
  • 暴力+剪枝，AC。当次数超过答案，剪枝；当新加上一个缆车，剪枝，不需要再考虑放到更后面的缆车。

代码实现：

  1. #include <iostream>
  3. using namespace std;
  5. int n, w;
  6. int cats[20], cars[20];
  8. int ans = 0x3f3f3f3f;
  10. void dfs(int catpos, int cnt){
  11.     // 不可能比最小值更小，返回
  12.     if(cnt >= ans)return;
  13.     if(catpos >= n){
  14.         ans = min(ans, cnt);
  15.         return;
  16.     }
  17.     for(int i = 0; i < n; i++){
  18.         if(w - cars[i] >= cats[catpos]){
  19.             // 有新加入缆车，那么需要的缆车数应为到当前缆车之前的车，否则数量不变
  20.             int tcnt;
  21.             if(cars[i] == 0)tcnt = i + 1;
  22.             else tcnt = cnt;
  23.             cars[i] += cats[catpos];
  24.             dfs(catpos + 1, tcnt);
  25.             cars[i] -= cats[catpos];
  26.         }
  27.         // 加入了新车，不考虑后边的缆车
  28.         if(cars[i] == 0)break;
  29.     }
  30. }
  32. int main(){
  33.     cin>>n>>w;
  34.     for(int i = 0; i < n; i++){
  35.         cin>>cats[i];
  36.     }
  37.     dfs(0, n);
  38.     cout<<ans;
  39.     return 0;
  40. }

3.数独

4.