牛客练习赛65

(Updated: )
(15 mins to read)

C 二维动点

题意

平面上有n个点，每次可以选择一个与当前不重合的点，然后移动到两者直线上的任意一点，多次询问从原点到(x, y)最少的移动次数

做法

大力分类讨论：

  • (0, 0）是没有用的，如果出现需要去掉
  • 如果平面上所有点到原点的连线是相同的，且询问点不在该连线上，输出-1
  • 如果询问点与原点连成的直线上存在平面上的n个点中的至少一个，输出1，可以利用pair来存斜率，注意归约化处理
  • 如果点数>=3，输出2，只要有两条直线相交，就可以先移到交点，再移过去
  • 当只有2个点时，考虑一种特殊情况（样例已经提示），原点+这2个点+询问点构成平行四边形，此时需要3次，先随便移到某个点处，再按上一条的做法
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
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 2e5 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int n, q, x[N], y[N];
map<pii, int> cnt;
int gcd(int a, int b)
{
  if(!b) return a;
  return gcd(b, a%b);
}
int sgn(int x) { return (x>0 ? 1 : -1); }
pii cal(int a, int b, int c, int d)
{
  int x = c - a, y = d - b;
  assert(x || y);
  if(!x) return mp(0, 1);
  if(!y) return mp(1, 0);
  int f = sgn(x)*sgn(y);
  int t = gcd(abs(x), abs(y));
  return mp(f*x/t, y/t);
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> q;
  int m = n;
  for(int i=1; i<=n; i++)
  {
    cin >> x[i] >> y[i];
    if(!x[i]&&!y[i])
    {
      m--;
      continue;
    }
    cnt[cal(0, 0, x[i], y[i])]++;
  }
  while(q--)
  {
    int a, b;
    cin >> a >> b;
    if(!a&&!b) cout << 0 << '\n';
    else if(cnt.count(cal(0, 0, a, b))) cout << 1 << '\n';
    else if(sz(cnt)<=1) cout << -1 << '\n';
    else if(m>=3) cout << 2 << '\n';
    else if(m==2)
    {
      if(cal(0, 0, x[1], y[1])==cal(x[2], y[2], a, b) && cal(0, 0, x[2], y[2])==cal(x[1], y[1], a, b)) cout << 3 << '\n';
      else cout << 2 << '\n';
    }
    else cout << -1 << '\n';
  }
  return 0;
}

D 最小公倍数

题意

给出一个数n，要求拆分成k个数，定义拆分后的价值为该序列的所有子序列的lcm的种类数 ，注意空序列的lcm=1

做法

因为答案要取模，所以感觉没法比较大小，所以在做题的时候以为是个构造。。。然后其实就是dp考虑数$p_1*p_2$​，显然没有拆成$p_1, p_2$​两个数优，因为它们的贡献是一样的，但是后者更小。所以最后一定是拆成若干个素数的幂次。考虑进行背包dp，因为各个素数的贡献其实是一样的，所以一定是从小往大选，前100多个素数的和就超过$10^5$了，如果当前这个素数选了k个，即选择了$p_1,p_2 … p_k$​，假设之前有x个不同的种类，那现在就有(k+1)*x个不同的种类。下面的问题是由于要取模，没法比较最后的大小了（毒瘤），一种方法是用double来存价值，并记录转移路径，最后在回溯的时候用longlong，并且取模，另一种是用Pair<double, long long>，前者利用log函数将乘法转为加法，后者存答案，即取模后的值，由于pair已经封装好了，所以直接取max即可。

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
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int n, prime[N];
bool vis[N];
pair<double,ll> dp[N];
void getprime(int x)
{
  vis[1] = 1;
  for(int i=2; i<=x; i++)
  {
    if(!vis[i]) prime[++prime[0]] = i;
    for(int j=1; j<=prime[0]&&1ll*prime[j]*i<=x; j++)
    {
      vis[prime[j]*i] = 1;
      if(i%prime[j]==0) break;
    }
  }
}
int main()
{
  scanf("%d", &n);
  getprime(n);
  int cur = 0, tot = 1;
  while(tot<=prime[0]&&cur+prime[tot]<=n) cur += prime[tot++];
  dp[0].se = 1;
  for(int i=1; i<tot; i++)
    for(int j=n; j>=prime[i]; j--)
    {
      ll t = prime[i], s = t;
      for(int k=1; s<=j; s += (t*=prime[i]), k++)
        dp[j] = max(dp[j], mp(dp[j-s].fi+log2(k+1), dp[j-s].se*(k+1)%mod));
    }
  pair<double, ll> ans = {0.0, 0};
  for(int i=0; i<=n; i++) ans = max(ans, dp[i]);
  cout << ans.se << '\n';
  return 0;
}

E 游走配对

题意

无向图上，有q个蓝点，q个红点，要求将蓝点和红点进行配对，每次配对产生的费用是他们路径上经过的所有点权的和，此外一个点如果被经过了k次，那么它的点权是$a_i + (k-1)*b_i$​，问最小的配对费用

做法

数据量较小，MCMF。由于是点权，我们拆成入点和出点，点权放在入点到出点的边上，并且拆除q条边，每条边流量为1，费用为第i次经过产生的费用，再将源点与q个蓝点的入点相连，q个红点的出点与汇相连，原图的m条边，则将u的出点和v的入点相连，v的出点和u的入点相连，然后跑最小费用最大流算是网络流基础题了

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
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
const int N = 1e3 + 5, M = 1e6 + 5;
int n, q, m, x[N], y[N];
int cnt, head[N];
struct node
{
  int next, to, w, f;
}e[M<<1];
void add(int u,int v,int w,int f)
{
  e[++cnt] = {head[u],v,w,f};
  head[u] = cnt;
}
struct MCMF
{
  int n, m, s, t;
  int flow, cost;
  bool inq[N];
  int d[N], p[N], a[N];
  void init(int n,int s,int t)
  {
    this->n = n, this->s = s, this->t = t;
    cnt = 1, m = 0, flow = cost = 0;
    memset(head,0,(n+1)*sizeof(int));
  }
  void addedge(int u,int v,int cap,int cost)
  {
    add(u,v,cap,cost);
    add(v,u,0,-cost);
    m += 2;
  }
  bool spfa()
  {
    memset(d,0x3f,(n+1)*sizeof(int));
    memset(inq,0,(n+1)*sizeof(bool));
    queue<int> q;
    q.push(s);
    d[s] = 0, a[s] = INF;
    while(!q.empty())
    {
      int u = q.front(); q.pop();
      inq[u] = 0;
      if(u==t) continue;
      for(int i=head[u];i;i=e[i].next)
      {
        int v = e[i].to;
        if(e[i].w&&d[v]>d[u]+e[i].f)
        {
          d[v] = d[u] + e[i].f;
          p[v] = i;
          a[v] = min(a[u],e[i].w);
          if(!inq[v])
          {
            q.push(v);
            inq[v] = 1;
          }
        }
      }
    }
    return d[t] != INF;
  }
  void go()
  {
    while(spfa())
    {
      flow += a[t];
      cost += a[t] * d[t];
      int u = t;
      while(u!=s)
      {
        e[p[u]].w -= a[t];
        e[p[u]^1].w += a[t];
        u = e[p[u]^1].to;
      }
    }
  }
}MM;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m >> q;
  MM.init(2*n+2, 0, 2*n+1);
  for(int i=1; i<=n; i++)
  {
    int a, b;
    cin >> a >> b;
    for(int j=1; j<=q; j++)
      MM.addedge(i, n+i, 1, (j-1)*b+a);
  }
  for(int i=1; i<=m; i++)
  {
    int c, d;
    cin >> c >> d;
    MM.addedge(c+n, d, q, 0);
    MM.addedge(d+n, c, q, 0);
  }
  for(int i=1; i<=q; i++) cin >> x[i];
  for(int i=1; i<=q; i++) cin >> y[i];
  for(int i=1; i<=q; i++)
  {
    MM.addedge(MM.s, x[i], 1, 0);
    MM.addedge(y[i]+n, MM.t, 1, 0);
  }
  MM.go();
  cout << MM.cost << '\n';
  return 0;
}