2021-07-02新高二一期暑假集训1(s2ojcontest88)

发表于

走夜路

考虑贪心，显然在价格低的地方要多买电，使电量达到上限或者能到达更便宜的充电站

所以得到一个暴力的想法，对于每一个电站，求出凭借它的电能到达的电站，如果能到更便宜的电站，那么就充能够到达最便宜电站的电，否则在其它比较便宜的电站补电。

然后发现可以考虑反悔，在每一个充电站把电充满，遇到更便宜的充电站时把已经充了的还没有用掉的比当前更贵的电反悔掉。

发现单调队列可以很好的进行这个操作。

步骤：

  1. 把比当前更贵的电弹出。
  2. 用当前的电充满手电筒 （把当前的电和电量放入队尾）
  3. 模拟消耗的电（显然消耗队头比较便宜的电）

Code:

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
#include <iostream>
#include <cstdio>
#include <queue>
#include <functional>
#include <deque>
#define int long long

using namespace std;

const int N = 1e6 + 10;
int n, t;
int d[N], p[N];
deque<pair<int, int> > q;

signed main()
{
  scanf("%lld%lld", &n, &t);
  int cnt = t;
  int ans = 0;
  for (int i = 1; i <= n; ++i)
  {
    scanf("%lld%lld", &d[i], &p[i]);
    if (d[i] > t)
    {
      puts("-1");
      return 0;
    }
    while (q.size() && q.back().first > p[i])
    {
      ans -= q.back().first * q.back().second;
      cnt += q.back().second;
      q.pop_back();
    }
    q.push_back(make_pair(p[i], cnt));
    ans += p[i] * cnt;
    cnt = d[i];
    while (q.size() && q.front().second <= d[i])
    {
      d[i] -= q.front().second;
      q.pop_front();
    }
    if (q.size() && d[i])
    {
      q.front().second -= d[i];
    }
  }	
  while (q.size())
  {
    ans -= q.front().first * q.front().second;
    q.pop_front();
  }
  cout << ans <<endl;
  return 0;
}

t2

数位 dpdp 裸题

Code:

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long

using namespace std;

int l, r, x, y;
int f[30][2][2][30];
int cnt[40], len;

int dfs(int step, int ze, int lim, int last)
{
  if (f[step][ze][lim][last]) return f[step][ze][lim][last];
  if (step == 0) return 1;
  int tmp = 0;
  int maxx = lim ? cnt[step] : 9;
  for (int i = 0; i <= maxx; ++i)
  {
    if (last == x && i == y) continue;
    tmp += dfs(step - 1, ze & (i == 0), lim & (i == maxx), (ze & (i == 0)) ? 20 : i);
  }
  f[step][ze][lim][last] = tmp;
  return tmp;
}

int dp(int x)
{
  memset(f, 0, sizeof(f));
  len = 0;
  while (x)
  {
    cnt[++len] = x % 10;
    x /= 10;
  }
  return dfs(len, 1, 1, 20);
}

signed main()
{
  scanf("%lld%lld%lld%lld", &l, &r, &x, &y);
  printf("%lld", dp(r) - dp(l - 1));
  return 0;
}

奇怪的集训队

二项式反演裸题

设 g(k)g(k) 表示钦定至少全部都会 kk 种算法的方案数。

即 g(k)=(nk)（2(2n−k)−1）g(k) = \tbinom{n}{k}（2^{(2^{n-k})}-1） 因为在钦定 kk 种算法后，其它算法随意，所以有 2n−k2^{n-k} 种算法组合，每种算法组合都随意存在，所以共有 2(2n−k)2^{(2^{n-k})} 种算法组合的组合，注意算法组合的组合不能为空，所以要 −1-1

然后设 f(k)f(k) 表示所有同学全部都会的算法恰好为 kk 种的方案数。

有式子：g(k)=∑i=kn(ik)f(i)g(k) = \sum_{i=k}^{n}\tbinom{i}{k}f(i)

因为对于每种方案，其中都有 kk 种算法可能是被钦定的。

然后只需要二项式反演得到 : f(k)=∑i=kn(−1)i−k(ik)g(i)f(k) = \sum_{i=k}^{n} (-1)^{i-k} \tbinom{i}{k} g(i)

要注意 2(2n−k)2^{(2^{n-k})} 中指数要模的是 φ(p)\varphi(p)

Code:

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
#include <iostream>
#include <cstdio>
#define int long long

using namespace std;

const int N = 3e6 + 10, mod = 1e9 + 7;
int g[N], f[N];
int n, k;
int fac[N], ifac[N];

int qpow(int a, int b, int mod)
{
  int res = 1;
  while (b)
  {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}

int C(int n, int m)
{
  return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

signed main()
{
  scanf("%lld%lld", &n, &k);
  fac[0] = 1;
  for (int i = 1; i <= n; ++i)
  {
    fac[i] = fac[i - 1] * i % mod;
  }
  ifac[n] = qpow(fac[n], mod - 2, mod);
  for (int i = n - 1; i; --i)
  {
    ifac[i] = ifac[i + 1] * (i + 1) % mod;
  }
  ifac[0] = 1;
  for (int i = 0; i <= n; ++i)
  {
    g[i] = C(n, i) * (qpow(2, qpow(2, n - i, mod - 1), mod) - 1 + mod) % mod;
  }
  int ans = 0;
  for (int i = k; i <= n; ++i)
  {
    ans = (ans + (qpow(-1, i - k, mod) * C(i, k) % mod + mod) % mod * g[i] % mod) % mod;
  }
  cout << ans << endl;
  return 0;
}

最短路

显然 aa 和 bb 一定是在最短路上的点，所以先把所有在最短路上的点求出来。

从 11 求最短路 fif_i, 再从 nn 求最短路gig_i，对于每个点 ii 如果 fi+gi=fnf_i + g_i = f_n 那么这个点为最短路上的点。

因为先到 aa， 再到 bb 所有对于最短路上的点建一个 dagdag ：对于有边相连的点对，由 fif_i 小的点向 fif_i 大的点连边。

对于每个最短路上的点，如果它是 bb ，那么 aa 就是它的前驱，每个点的前驱就是它直接前驱的前驱并，用 bitsetbitset 维护。

复杂度 O((n+m)lg⁡n+(n+m)n32)O((n+m)\lg n + \frac{(n+m)n}{32}) ，时间给开了 22 秒，应该不会被卡常

Code:

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
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <bitset>
#include <unordered_map>
#define ll long long
#define int long long
#pragma GCC optimize(3)
using namespace std;

const int N = 2e6 + 10;
int n, m;
int head[N], nxt[N], to[N];
ll len[N], e_tot;
ll f[N], g[N];
ll dis[N];
int vis[N];
int siz[N];
int imp[N], tot, isimp[N];
unordered_map<int, int> mapp[N];
vector<int> ne[N];
vector<int> stk;
int in[N];
priority_queue<pair<ll, int> > q;
ll ans;
bitset<30010> S[30010];

void add(int x, int y, ll z)
{
  nxt[++e_tot] = head[x], head[x] = e_tot, to[e_tot] = y, len[e_tot] = z;
}

void dij(int s)
{
  memset(dis, 0x3f, sizeof(dis));
  memset(vis, 0, sizeof(vis));
  dis[s] = 0;
  q.push(make_pair(0, s));
  while (q.size())
  {
    int u = q.top().second;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (int i = head[u]; i; i = nxt[i])
    {
      int v = to[i];
      //if (vis[v]) continue;
      if (dis[v] > dis[u] + len[i])
      {
        dis[v] = dis[u] + len[i];
        q.push(make_pair(-dis[v], v));
      }
    }
  }
}

signed main()
{
  scanf("%lld%lld", &n, &m);
  for (int i = 1; i <= m; ++i)
  {
    int a, b;
    ll c;
    scanf("%lld%lld%lld", &a, &b, &c);
    add(a, b, c), add(b, a, c);
  }
  dij(1);
  for (int i = 1; i <= n; ++i)
  {
    f[i] = dis[i];
  }
  dij(n);
  for (int i = 1; i <= n; ++i)
  {
    g[i] = dis[i];
  }
  for (int i = 1; i <= n; ++i)
  {
    if (f[i] + g[i] == f[n])
    {
      isimp[i] = 1;
      imp[++tot] = i;
    }
  }
  for (int i = 1; i <= tot; ++i)
  {
    int u = imp[i];
    for (int i = head[u]; i; i = nxt[i])
    {
      int v = to[i];
      if (isimp[v] && f[u] < f[v] && !mapp[u][v]) ne[u].push_back(v), mapp[u][v] = 1, ++in[v];
    }
  }
  for (int i = 1; i <= tot; ++i)
  {
    int u = imp[i];
    if (!in[u]) stk.push_back(u);
  }
  for (int i = 1; i <= tot; ++i)
  {
    int u = stk[i - 1];
    S[u][u] = 1;
    for (vector<int> :: iterator it = ne[u].begin(); it != ne[u].end(); ++it)
    {
      int v = *it;
      --in[v];
      S[v] |= S[u];
      if (!in[v])
      {
        stk.push_back(v);
      }
    }
  }
    
  for (int i = 1; i <= tot; ++i)
  {
    int u = imp[i];
    ans = ans + 1ll * (S[u].count() - 1);
  }
  cout << ans  << endl;
  return 0;
}