• 2022杭电多校（四）

    2022杭电多校（四）

    文章目录

    一、比赛小结

    比赛链接：Problems (hdu.edu.cn)

    和牛客的一场比赛互为姊妹赛： "蔚来杯"2022牛客暑期多校训练营2

    二、题目分析及解法（基础题）

    1001、Link with Bracket Sequence II

    题目链接：Problem - 7174 (hdu.edu.cn)

    题意：

    给你一个 n n n 长度的括号序列，有 m m m 种括号形式， a i = 0 a_i=0 ai​=0 表示的是可以是这 m m m 种任意都可以， a i > 0 a_i>0 ai​>0 表示的是该种的左括号， a i < 0 a_i<0 ai​<0 表示的是该种的右括号。

    求有多少种满足条件。

    题解：

    卡塔兰式 dp 即可

    代码：

    #include 
#define int long long
const int maxn = 600;
const int mod = 1e9 + 7;
using namespace std;
int n, m;
int a[maxn];
int dp[maxn][maxn];  // dp[i][j] 代表区间 [i, j] 的方案数
bool ispair(int i, int j) {
  if (a[i] < 0 || a[j] > 0) return false;
  if (a[i] == 0 || a[j] == 0) return true;
  if (a[i] + a[j] == 0) return true;
  return false;
}
signed main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  while (_--) {
    memset(dp, 0, sizeof(dp));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) dp[i + 1][i] = 1ll;
    for (int len = 2; len <= n; len++)
      for (int i = 1; i + len - 1 <= n; i++)
        for (int j = i + 1; j <= i + len - 1; j++)
          if (ispair(i, j)) {
            int tmp = dp[i + 1][j - 1] * dp[j + 1][i + len - 1] % mod;
            if (a[i] == 0 && a[j] == 0)
              dp[i][i + len - 1] = (m * tmp + dp[i][i + len - 1]) % mod;
            else
              dp[i][i + len - 1] = (tmp + dp[i][i + len - 1]) % mod;
          }
    cout << dp[1][n] << endl;
  }
  return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    1002、Link with Running

    题目链接：Problem - 7175 (hdu.edu.cn)

    题意：

    link 在健身，要从 节点 1 跑向 节点 n n n ，每条路均为有向边，还有两个属性，为能量消耗和健康获益，他想在最少的能量消耗的基础上，获得最多的健康收益。

    求出这两个值。

    题解：

    先用 dijkstra 跑出最短路图，再跑最长路，题目给的图不一定为 DAG ，需要自行缩点

    代码：

    #include 
#define MN 100000

using namespace std;

using ll = long long;

const ll INF = 1e18;

struct Edge {
  int v, w1, w2;
};

namespace GetSpg {
ll dis[MN + 5];
vector<Edge> e[MN + 5];

void clear(int n) {
  for (int i = 1; i <= n; i++) {
    e[i].clear();
  }
}

void addEdge(int u, int v, int w1, int w2) { e[u].push_back({v, w1, w2}); }

void dijkstra(int n, int S) {
  using pii = std::pair<ll, int>;
  priority_queue<pii, vector<pii>, greater<pii>> pq;
  for (int i = 1; i <= n; i++) {
    dis[i] = INF;
  }
  pq.push({dis[S] = 0, S});
  while (!pq.empty()) {
    int u = pq.top().second;
    ll d = pq.top().first;
    pq.pop();
    if (d != dis[u]) continue;
    for (Edge edge : e[u]) {
      int v = edge.v;
      int w = edge.w1;
      if (dis[u] + w < dis[v]) {
        dis[v] = dis[u] + w;
        pq.push({dis[v], v});
      }
    }
  }
}

void solve(int n, function<void(int, int, int, int)> addEdge) {
  dijkstra(n, 1);
  for (int u = 1; u <= n; u++) {
    if (dis[u] == INF) continue;
    for (Edge edge : e[u]) {
      if (dis[u] + edge.w1 == dis[edge.v]) {
        addEdge(u, edge.v, edge.w1, edge.w2);
      }
    }
  }
}

}  // namespace GetSpg

namespace GetDag {
vector<Edge> e[MN + 5];

stack<int> s;
bool ins[MN + 5];
int low[MN + 5], dfn[MN + 5], scc[MN + 5];
int dfnCnt = 0, sccCnt = 0;

void clear(int n) {
  for (int i = 1; i <= n; i++) {
    e[i].clear();
    ins[i] = false;
    dfn[i] = low[i] = scc[i] = 0;
  }
  dfnCnt = 0;
  sccCnt = 0;
  while (!s.empty()) s.pop();
}

void addEdge(int u, int v, int w1, int w2) { e[u].push_back({v, w1, w2}); }

void tarjan(int u) {
  dfn[u] = ++dfnCnt;
  low[u] = dfn[u];
  s.push(u);
  ins[u] = true;
  for (Edge edge : e[u]) {
    int v = edge.v;
    if (dfn[v]) {
      if (ins[v]) {
        low[u] = min(low[u], dfn[v]);
      }
    } else {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    }
  }
  if (low[u] == dfn[u]) {
    int v;
    ++sccCnt;
    do {
      v = s.top();
      s.pop();
      ins[v] = false;
      scc[v] = sccCnt;
    } while (u != v);
  }
}

void solve(int& n, function<void(int, int, int, int)> addEdge, bool isLoop[]) {
  for (int i = 1; i <= n; i++) {
    if (!dfn[i]) {
      tarjan(i);
    }
  }
  for (int u = 1; u <= n; u++) {
    for (Edge edge : e[u]) {
      int v = edge.v;
      if (scc[u] == scc[v]) {
        if (edge.w2 > 0) {
          isLoop[scc[u]] = true;
        }
      } else {
        addEdge(scc[u], scc[edge.v], edge.w1, edge.w2);
      }
    }
  }
}

}  // namespace GetDag

namespace GetLp {
int din[MN + 5];
bool isLoop[MN + 5];
vector<Edge> e[MN + 5];

struct Dis {
  ll d;
  Dis(ll d = 0) { this->d = d; }
  Dis operator+(const Dis& that) const {
    if (d == -INF || that.d == -INF) return Dis(-INF);
    if (d == INF || that.d == INF) return Dis(INF);
    return Dis(d + that.d);
  }
  bool operator<(const Dis& that) const { return this->d < that.d; }
};

Dis f[MN + 5];

void clear(int n) {
  for (int i = 1; i <= n; i++) {
    din[i] = 0;
    isLoop[i] = false;
    e[i].clear();
  }
}

void addEdge(int u, int v, int w1, int w2) {
  e[u].push_back({v, w1, w2});
  din[v]++;
}

void solve(int n, int S) {
  for (int i = 1; i <= n; i++) {
    f[i] = -INF;
  }
  f[S] = 0;
  queue<int> q;
  for (int i = 1; i <= n; i++) {
    if (din[i] == 0) q.push(i);
  }
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    if (isLoop[u]) f[u] = f[u] + INF;
    for (Edge edge : e[u]) {
      int v = edge.v;
      int w = edge.w2;
      f[v] = max(f[v], f[u] + w);
      if (--din[v] == 0) {
        q.push(v);
      }
    }
  }
}
}  // namespace GetLp

void solve() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int u, v, w1, w2;
    scanf("%d%d%d%d", &u, &v, &w1, &w2);
    GetSpg::addEdge(u, v, w1, w2);
  }
  GetSpg::solve(n, GetDag::addEdge);
  GetDag::solve(n, GetLp::addEdge, GetLp::isLoop);
  GetLp::solve(GetDag::sccCnt, GetDag::scc[1]);
  printf("%lld %lld\n", GetSpg::dis[n], GetLp::f[GetDag::scc[n]].d);
  GetSpg::clear(n);
  GetDag::clear(n);
  GetLp::clear(n);
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) solve();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211

    1003、Magic

    题目链接：Problem - 7176 (hdu.edu.cn)

    题意：

    有 n n n 个魔法塔，每个魔法塔的魔法值都需要魔法原料，求一个差分约束

    题解：

    我们令 a [ i ] a[i] a[i] 为前 i i i 个魔法塔中加入的魔法原料之和。由于第 i i i 个魔法塔的魔法值只与有效半径 k k k 内的魔法原料数量有关，则魔法值需求 p i p_i pi​ 可以表示为

    a [ min ⁡ ( n , i + k − 1 ) ] − a [ max ⁡ ( 0 , i − k ) ] ≥ p i a[\min (n,i+k-1)]-a[\max(0,i-k)]\ge p_i a[min(n,i+k−1)]−a[max(0,i−k)]≥pi​

    对于魔法原料添加的限制 L j , R j , B j L_j, R_j, B_j Lj​,Rj​,Bj​ 可以表示为

    a [ R j ] − a [ L j − 1 ] ≤ B j a[R_j]-a[L_j-1]\le B_j a[Rj​]−a[Lj​−1]≤Bj​

    由于每个魔法塔中的原料数量非负，需要满足

    a [ i ] − a [ i − 1 ] ≥ 0 a[i]-a[i-1]\ge 0 a[i]−a[i−1]≥0

    将上述三组不等式使用差分约束求解即可。

    代码：

    #include 
using namespace std;
const int maxne = 600001;
const int maxnn = 100001;
const long long int inf = 1e18;
int n, k;
int e, s, t, cnt;
int last[maxne], q[maxne], check[maxnn];
long long dis[maxnn];
bool is[maxnn], fuhuan;
struct line {
  int to, next, v;
} l[maxne];
void add(int u, int v, int w) {
  l[++cnt].to = v;
  l[cnt].next = last[u];
  last[u] = cnt;
  l[cnt].v = w; /*printf("u:%d v:%d w:%d\n",u,v,w);*/
}
void spfa(int a, int maxnode) {
  for (int i = 1; i <= maxnode; i++) {
    dis[i] = inf;
    check[i] = is[i] = 0;
  }
  dis[a] = 0;
  is[a] = 1;
  q[0] = a;
  check[a]++;
  fuhuan = 0;
  int head = 0, tail = 1;
  while (head != tail) {
    int now = q[head++];
    if (head == maxnode + 1) head = 0;
    for (int i = last[now]; i; i = l[i].next) {
      if (dis[now] + l[i].v < dis[l[i].to] && dis[now] != inf) {
        dis[l[i].to] = dis[now] + l[i].v;
        if (!is[l[i].to]) {
          is[l[i].to] = 1;
          if (dis[l[i].to] < dis[q[head]]) {
            head--;
            if (head == -1) head = n;
            q[head] = l[i].to;
            check[l[i].to]++;
            if (check[l[i].to] == maxnode) {
              fuhuan = 1;
              return;
            }
          } else {
            q[tail++] = l[i].to;
            if (check[l[i].to] == maxnode) {
              fuhuan = 1;
              return;
            }
            if (tail == maxnode + 1) tail = 0;
          }
        }
      }
    }
    is[now] = 0;
  }
}
void clear(int x) {
  cnt = 0;
  for (int i = 0; i <= x; i++) {
    last[i] = q[i] = 0;
  }
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int p, q;
    scanf("%d%d", &n, &k);
    // x[j]-x[i]>=k  ==> x[i]-x[j]<=-k
    for (int i = 1; i <= n; i++) {
      scanf("%d", &p);
      int st = (i - k >= 1) ? (i - k) : n + 1;
      int ed = (i + k - 1 <= n) ? (i + k - 1) : n;
      add(ed, st, -1 * p);
    }
    for (int i = 1; i <= n; i++) add(i, (i - 1 == 0 ? n + 1 : i - 1), 0);
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
      int x, y;
      scanf("%d%d%d", &x, &y, &p);
      add((x != 1) ? (x - 1) : n + 1, y, p);
    }
    spfa(n, n + 1);
    int tmp = dis[n + 1];
    printf("%d\n", fuhuan ? -1 : -1 * tmp);
    clear(n + 2);
  }
  return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94

    1004、Link with Equilateral Triangle

    题目链接：Problem - 7177 (hdu.edu.cn)

    题意：

    给你一个边长为n的三角形，左侧不能填0，右侧不能填1，下边不能填2，对于每一个小三角形都不能是3的倍数，求是否可以构造出一个这样的三角形。

    img

    题解：

    对于一个合法的解，应当满足不存在同时包含0,1,2的三角形，下面我们证明这样的三角形一定存在。

    左下角必然是1，右下角必然是0，底边不能含有2，则底边上必然有奇数条1-0的边，这些边都属于一个小三角形。考虑其他的0-1边，由于不在两个斜边上，其他的0-1边必然属于两个三角形。因此“每个三角形内0-1边的数量”的和必然为奇数。

    但是，假设不存在0-1-2的三角形，则所有三角形都必然包含0条或2条的0-1边，产生了矛盾。

    因此一定存在0-1-2的三角形。

    代码：

    #include 
using namespace std;
int n;
int main() {
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  while (_--) {
    cin >> n;
    cout << "No\n";
  }
  return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    1005、Link with Level Editor II

    题目链接：Problem - 7178 (hdu.edu.cn)

    题意：

    link 正在玩一个游戏，在这个游戏中，一个关卡由几个世界组成。每个世界由以下几个部分组成：m 节点和一些定向道路。从 节点1 开始，在每个世界中，玩家可以留在当前节点，也可以通过该世界中存在的一条道路。之后，玩家将被传送到下一个世界，而不会改变他所停留的节点的ID。如果没有下一个世界，游戏就结束了。如果玩家在 节点m 上结束，则玩家获胜.

    link 正在编辑一个新的关卡，他已经做了 n 世界（编号从1自n），并希望选择它们的连续子段以形成一个新关卡。唯一的限制是不应该超过k获胜的方式。（当且仅当某些世界中的操作不同时，两种方式才被认为是不同的。

    link 不想丢弃太多的世界。Link 在新关卡中可以使用的最大世界数是多少？

    和之前牛客的一道题很像： L-Link with Level Editor I

    题解：

    考虑用双指针求解，用矩阵的方式维护1~m的路径数量。发现矩阵并非全部可逆，难以进行删除操作，使用对顶栈的技巧规避掉删除操作即可。

    用矩阵维护路径数量也是比较常见的一种的手段

    代码：

    #include 
#define MN 5000
#define MM 20

using std::max;

using ll = long long;

const int INF = 1000000001;

namespace GTI {
char gc(void) {
  const int S = 1 << 16;
  static char buf[S], *s = buf, *t = buf;
  if (s == t) t = buf + fread(s = buf, 1, S, stdin);
  if (s == t) return EOF;
  return *s++;
}
ll gti(void) {
  ll a = 0, b = 1, c = gc();
  for (; !isdigit(c); c = gc()) b ^= (c == '-');
  for (; isdigit(c); c = gc()) a = a * 10 + c - '0';
  return b ? a : -a;
}
int gts(char* s) {
  int len = 0, c = gc();
  for (; isspace(c); c = gc())
    ;
  for (; c != EOF && !isspace(c); c = gc()) s[len++] = c;
  s[len] = 0;
  return len;
}
int gtl(char* s) {
  int len = 0, c = gc();
  for (; isspace(c); c = gc())
    ;
  for (; c != EOF && c != '\n'; c = gc()) s[len++] = c;
  s[len] = 0;
  return len;
}
}  // namespace GTI
using GTI::gti;
using GTI::gtl;
using GTI::gts;

int n, m, k;

struct Matrix {
  int a[MM + 2][MM + 2];

  Matrix(int x = 0) {
    memset(a, 0, sizeof(a));
    for (int i = 1; i <= m; i++) {
      a[i][i] = x;
    }
  }

  Matrix operator*(const Matrix& that) const {
    Matrix ret;
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= m; j++) {
        for (int k = 1; k <= m; k++) {
          ret.a[i][j] = limit(ret.a[i][j] + (ll)this->a[i][k] * that.a[k][j]);
        }
      }
    }
    return ret;
  }

  static int limit(ll x) {
    if (x >= INF)
      return INF;
    else
      return x;
  }
};

Matrix d[MN + 5], b[MN + 5];

bool check(const Matrix& lhs, const Matrix& rhs) {
  int ans = 0;
  for (int i = 1; i <= m; i++) {
    ans = Matrix::limit(ans + (ll)lhs.a[1][i] * rhs.a[i][m]);
  }
  return ans <= k;
}

void solve() {
  n = gti();
  m = gti();
  k = gti();
  for (int i = 1; i <= n; i++) {
    int l = gti();
    d[i] = 1;
    while (l--) {
      int u = gti();
      int v = gti();
      d[i].a[u][v] = 1;
    }
  }
  int ans = 0;
  Matrix csuf = 1;
  b[0].a[1][m] = INF;
  for (int r = 1, l = 0, lim = 0; r <= n; r++) {
    csuf = csuf * d[r];
    while (!check(b[l], csuf)) {
      l++;
      if (l > lim) {
        b[r] = d[r];
        for (int i = r - 1; i > lim; i--) {
          b[i] = d[i] * b[i + 1];
        }
        lim = r;
        csuf = 1;
      }
    }
    ans = max(ans, r - l + 1);
  }
  printf("%d\n", ans);
}

int main() {
  int T = gti();
  while (T--) solve();
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126

    1006、BIT Subway

    题目链接：Problem - 7179 (hdu.edu.cn)

    题意：

    签到题，写一个分段函数即可，读入 double 的速度很慢，读入 int 则会快许多

    题解：

    a n s = { x 0 ≤ x < 100 ( x − 100 ) ∗ 0.8 + 100 100 ≤ x < 225 ( x − 225 ) ∗ 0.5 + 200 225 ≤ x ans =

    {x0≤x<100(x−100)∗0.8+100100≤x<225(x−225)∗0.5+200225≤x" role="presentation" style="text-align: center; position: relative;">{x0≤x<100(x−100)∗0.8+100100≤x<225(x−225)∗0.5+200225≤x
    ans=⎩ ⎨ ⎧​x(x−100)∗0.8+100(x−225)∗0.5+200​0≤x<100100≤x<225225≤x​

    代码：

    #include 
using namespace std;
const int maxn = 100010;
int n;
long double a[maxn];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  cout << fixed << setprecision(3);
  while (_--) {
    cin >> n;
    double ans1 = 0, ans2 = 0;
    double x, y;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      if (ans2 < 100.0)
        ans2 += a[i];
      else if (ans2 < 200.0)
        ans2 += 0.8 * a[i];
      else
        ans2 += 0.5 * a[i];
      if (ans1 < 100.0) {
        double x = 100.0 - ans1;
        if (a[i] > x) {
          a[i] -= x;
          ans1 = 100;
          double y = 200.0 - ans1;
          if (a[i] * 0.8 > y) {
            a[i] -= (y / 0.8);
            ans1 = 200 + a[i] * 0.5;
          } else
            ans1 += a[i] * 0.8;
        } else
          ans1 += a[i];
      } else if (ans1 < 200.0) {
        double x = 200.0 - ans1;
        if (a[i] * 0.8 > x) {
          a[i] -= (x / 0.8);
          ans1 = 200.0 + a[i] * 0.5;
        } else
          ans1 += a[i] * 0.8;
      } else
        ans1 += a[i] * 0.5;
    }
    cout << ans1 << " " << ans2 << "\n";
  }
  return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    1007、Climb Stairs

    题目链接：Problem - 7180 (hdu.edu.cn)

    题意：

    这里有  n n n 个怪物，每个怪物都有  a [ i ] a[i] a[i] 的血量，初始你有  a [ 0 ] a[0] a[0] 的攻击力。

    当你的攻击力大于等于怪物的血量，你就可以干掉怪物，并且你的攻击力会加上怪物的血量。

    你初始在  0 0 0 这个位置上，当你在点  i i i 上，每次你可以选择向上跳到  i + 1 , i + 2 , . . . , i + k i+1, i+2, ..., i+k i+1,i+2,...,i+k 点。或者移动到  i − 1 i-1 i−1 这个点上。但是你不能经过已经打过怪物的点。

    问能否打完全部的怪物。

    题解：

    模拟+贪心即可

    代码：

    #include 
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int n, k;
int a[maxn];
int s[maxn], t[maxn];
bool vis[maxn];
struct segtree {
  int l, r;
  int val;
} tr[maxn << 2];
void init() {
  memset(s, 0, sizeof(s));
  memset(t, 0, sizeof(t));
  memset(a, 0, sizeof(a));
  memset(vis, 0, sizeof(vis));
}
void build(int id, int l, int r) {
  tr[id].l = l, tr[id].r = r, tr[id].val = -inf;
  if (l == r) {
    tr[id].val = t[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(id << 1, l, mid);
  build(id << 1 | 1, mid + 1, r);
  tr[id].val = max(tr[id << 1].val, tr[id << 1 | 1].val);
}
int query(int id, int l, int r) {
  if (l <= tr[id].l && tr[id].r <= r) return tr[id].val;
  int ans = -inf;
  int mid = (tr[id].l + tr[id].r) >> 1;
  if (l <= mid) ans = max(ans, query(id << 1, l, r));
  if (r > mid) ans = max(ans, query(id << 1 | 1, l, r));
  return ans;
}
int main() {
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _t;
  cin >> _t;
  while (_t--) {
    init();
    cin >> n >> a[0] >> k;
    vis[0] = true;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = n; i >= 1; i--) {
      s[i] = a[i] + s[i + 1];
      t[i] = a[i] - s[i + 1];
    }
    build(1, 1, n);
    // 从 last 楼层（曾经最高点）下来打怪一直到 cur 楼层（当前点）
    int cur = 0, last = 0;
    int hp = a[0];
    while (cur < n) {
      bool flag = false;
      for (int i = last - cur + 1; i <= k && (cur + i <= n); i++) {
        if (vis[cur + i]) continue;
        int q = query(1, cur + 1, cur + i);
        if (hp >= q + s[cur + i + 1]) {
          hp += (s[last + 1] - s[cur + 1 + i]);
          int tmp = last;
          last = cur + i;
          cur = tmp + 1;
          flag = true;
          // printf("cur: %d, hp: %d, last: %d\n", cur, hp, last);
          break;
        }
        vis[cur + i] = true;
      }
      if (!flag) break;
    }
    if (last == n)
      printf("YES\n");
    else
      printf("NO\n");
  }
  return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82

    1011、Link is as bear

    题目链接：Problem - 7184 (hdu.edu.cn)

    题意：

    给你一个长度为 n n n 的数组，你选择一个区间 [ l , r ] [l,r] [l,r] 将其异或得出的答案给这些区间内的数都赋值，求最后获得最大的异或和

    题解：

    是个思维+结论题，可以证明，从这 n 个数里任取一些数异或起来的方案，都是可以构造出对应的操作来
    做到的。
    所以，问题完全等价于给n个数，从中选一些数，使得这些数的异或和最大。
    这是线性基的板题，抄一个板子即可。

    下面给出证明：

    • 如果序列里有连续的两个0，那么一定都可以构造出操作方案。例如 0,0,a1​,a2​中，比如我们要保留a1​不保留a2​ ，就可以先两次操作变成a1​,0,0,a2​ ，再两次操作变成a1​,0,0,0 ，因为上述操作总可以保证操作完后还有两个0，所以可以以此类推一直往下处理。如果两个0两边都有数字当然也没问题，我们先处理完一边儿的再回过头来处理另一边。
    • 如果用 来表示一个需要保留的数字， 来表示一个想要删去的数字，则出现110 或011 的形状时，可
      以通过操作删掉想删的那个数并制造出两个0 。以110 为例：

    a 1 ​ , a 2 ​ , a 3 ​ → a 1 ​ ⊕ a 2 ​ , a 1 ​ ⊕ a 2 ​ , a 3 ​ → a 1 ​ ⊕ a 2 ​ , 0 , 0 a1​,a2​,a3​→a1​⊕a2​,a1​⊕a2​,a3​→a1​⊕a2​,0,0 a1​,a2​,a3​→a1​⊕a2​,a1​⊕a2​,a3​→a1​⊕a2​,0,0

    就可以做到只删掉 a3​ 而产生两个0 。

    • 由上面2和1可以看出，只要出现110 、011 就可以完全解决问题，也就是出现连续两个1 就完全可以构造出任意方案，而有连续的两个 也可以完全解决问题。综上，有连续两个0 和连续两个1 的序列，都可以造出来任意的异或方案。
    • 所以现在唯一处理不了的就是既没有连续0 也没有连续1 的序列，也就是形如01010101 或1010101 这样的情况，这时就要用到两个数相同的条件，该条件实际上是保证了不会出现这种情况。假设相同的两个数都是x ，如果最后方案里没有异或上x ，则两个x 的位置可以都当作0 或都当作1 ；如果最后的方案里有异或上x ，则两个x 可以一个填0 一个填1 也可以一个填1 一个填0 。而上述两种情况下，x 都有两种填法，且两种填法之一一定保证存在连续0 或连续1 ，因此也可以构造出。

    代码：

    把 n n n 设成全局变量不会超时，设成局部变量会超时

    #include 
#define int long long
using namespace std;
int base[70];
void insert(int x) {
  for (int i = 62; i >= 0; i--) {
    if (!(x & (1ll << i))) continue;  // x的第i位是0
    if (!base[i]) {                   // 对角线上第一个 0 的位置
      base[i] = x;
      return;
    }
    x ^= base[i];
  }
}
int n, res;
signed main() {
  //   freopen("in.txt", "r", stdin);
  //   freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  while (_--) {
    res = 0;
    for (int i = 0; i <= 62; i++) base[i] = 0;
    cin >> n;
    int x;
    for (int i = 0; i < n; i++) cin >> x, insert(x);
    for (int i = 62; i >= 0; i--)
      if ((res ^ base[i]) > res) res ^= base[i];
    cout << res << endl;
  }
  return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    三、题目分析及解法（进阶题）

    不会做

    1008、Fight and upgrade

    1009、Fall with Full Star

    1010、Fall with Intersection

  • 相关阅读:
    【云原生之k8s】Pod 基础概念
    基于Java发起HTTP请求实现文件的上传
    windows flask 多进程高并发
    JAVA餐饮掌上设备点餐系统计算机毕业设计Mybatis+系统+数据库+调试部署
    【微服务保护】
    2023最新SSM计算机毕业设计选题大全（附源码+LW）之java新冠疫苗接种管理系统nt3mc
    MATLAB中cellstr函数的使用
    基于SpringBoot的个性化推荐的图书借阅管理系统前后台设计
    21.1 Python 使用PEfile分析PE文件
    机器人仿真-gazebo学习笔记（5）添加Gazebo属性
  • 原文地址：https://blog.csdn.net/m0_54646258/article/details/126869907