牛客国庆集训派对Day7 Solution

分类: IT文章 • 2025-01-09 09:13:25

A Relic Discovery

水。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3  
 4 int t, n;
 5  
 6 int main()
 7 {
 8     scanf("%d", &t);
 9     while (t--)
10     {
11         scanf("%d", &n);
12         int res = 0;
13         for (int i = 1, a, b; i <= n; ++i)
14         {
15             scanf("%d%d", &a, &b);
16             res += a * b;
17         }
18         printf("%d
", res);
19     }
20     return 0;
21 }

View Code

B Pocket Cube

按题意模拟即可，注意顺时针转逆时针转均可，也就是说一个面有八种旋转可能

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3  
 4 int t;
 5 int G[10][10], tmp[10][10];
 6  
 7 bool ok()
 8 {
 9     for (int i = 1; i <= 6; ++i)
10         for (int j = 2; j <= 4; ++j)
11             if (tmp[i][j] != tmp[i][j - 1])
12                 return false;
13     return true;
14 }
15  
16 void clear()
17 {
18     for (int i = 1; i <= 6; ++i)
19         for (int j = 1; j <= 4; ++j)
20             tmp[i][j] = G[i][j];
21 }
22  
23 int origin[][8][2] =
24 {
25     // top
26     {4, 3, 4, 4, 6, 1, 6, 3, 2, 2, 2, 1, 5, 4, 5, 2,},
27     // bottom
28     {4, 1, 4, 2, 6, 1, 6, 3, 2, 4, 2, 3, 5, 3, 5, 1,},     
29     // left
30     {1, 1, 1, 3, 2, 1, 2, 3, 3, 1, 3, 3, 4, 1, 4, 3,},
31     // right
32     {1, 4, 1, 2, 4, 4, 4, 2, 3, 4, 3, 2, 2, 4, 2, 2,},
33     // front
34     {1, 3, 1, 4, 6, 3, 6, 4, 3, 2, 3, 1, 5, 3, 5, 4,},
35     // back
36     {3, 3, 3, 4, 6, 2, 6, 1, 1, 2, 1, 1, 5, 2, 5, 1,},
37 };
38  
39 int Move[][8][2] =
40 {
41     {5, 4, 5, 2, 4, 3, 4, 4, 6, 1, 6, 3, 2, 2, 2, 1,},
42     {5, 3, 5, 1, 4, 1, 4, 2, 6, 1, 6, 3, 2, 4, 2, 3,},
43     {4, 1, 4, 3, 1, 1, 1, 3, 2, 1, 2, 3, 3, 1, 3, 3,},
44     {2, 4, 2, 2, 1, 4, 1, 2, 4, 4, 4, 2, 3, 4, 3, 2,},
45     {5, 3, 5, 4, 1, 3, 1, 4, 6, 3, 6, 4, 3, 2, 3, 1,},
46     {5, 2, 5, 1, 3, 3, 3, 4, 6, 2, 6, 1, 1, 2, 1, 1,},
47 };
48  
49 bool work()
50 {
51     clear(); if (ok()) return true;
52     for (int i = 0; i < 6; ++i)
53     {
54         for (int j = 0; j < 8; j += 2)
55         {
56             clear();
57             for (int k = 0; k < 8; ++k)
58             {
59                 int x = (j + k) % 8;
60                 tmp[origin[i][x][0]][origin[i][x][1]] = G[Move[i][x][0]][Move[i][x][1]];
61             }
62             if (ok()) return true;
63         }
64         for (int j = 1; j < 8; j += 2)
65         {
66             clear();
67             for (int k = 0; k > -8; --k)
68             {
69                 int x = (j + k + 8) % 8;
70                 int y = (x + 4) % 8;
71                 tmp[origin[i][x][0]][origin[i][x][1]] = G[Move[i][y][0]][Move[i][y][1]];
72             }
73             if (ok()) return true;
74         }
75     }
76     return false;
77 }
78  
79 int main()
80 {
81     scanf("%d", &t);
82     while(t--)
83     {
84         for (int i = 1; i <= 6; ++i)
85             for (int j = 1; j <= 4; ++j)
86                 scanf("%d", &G[i][j]);
87         puts(work() ? "YES" : "NO");
88     }
89     return 0;
90 }

View Code

C Pocky

根据样例发现规律答案为 log(l / d) + 1.0 如果 l <= d 答案为0

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3  
 4 const double eps = 1e-8;
 5  
 6 int t;
 7 double l, d;
 8  
 9 int main()
10 {
11     scanf("%d", &t);
12     while (t--)
13     {
14         scanf("%lf%lf", &l, &d);
15         if (l <= d || fabs(l - d) <= eps)
16             printf("%.6f
", 0.0);
17         else
18             printf("%.6f
", log(l / d) + 1.0);
19     }
20     return 0;
21 }

View Code

D Lucky Coins

留坑。

E Fibonacci

留坑。

F Lambda Calculus

留坑。

G Coding Contest

题意：有n个区域，每个区域有$s_i$个人以及$b_i$个食物，有m条路，每条路最多让$c_i$个人走，其中第一个人走不产生影响，后面的每个人都有p的可能破坏求最小的破坏可能

思路：将p取log就变成了累加最小，建立一个源点以及一个汇点，其中每块区域需要出走的人和汇点相连，可以进来的人与源点相连，跑一遍最小费用最大流即可

  1 #include<bits/stdc++.h>
  2  
  3 using namespace std;
  4  
  5 const double eps = 1e-8;
  6 const double EI = exp(1.0);
  7 const int maxn = 10000;
  8 const int maxm = 100000;
  9 const int INF = 0x3f3f3f3f;
 10  
 11 int sgn(double x)
 12 {
 13     if(fabs(x) < eps) return 0;
 14     else return x > 0 ? 1 : -1;
 15 }
 16  
 17 struct Edge{
 18     int to, nxt, cap, flow;
 19     double cost;
 20 }edge[maxm];
 21  
 22 double ans;
 23 int head[maxn], tot;
 24 int pre[maxn];
 25 double dis[maxn];
 26 bool vis[maxn];
 27 int N;
 28  
 29 void Init(int n)
 30 {
 31     N = n;
 32     tot = 0;
 33     for(int i = 0; i <= n; ++i) head[i] = -1;
 34 }
 35  
 36 void addedge(int u, int v,int cap, double cost)
 37 {
 38     edge[tot].to = v;
 39     edge[tot].cap = cap;
 40     edge[tot].cost = cost;
 41     edge[tot].flow = 0;
 42     edge[tot].nxt = head[u];
 43     head[u] = tot++;
 44  
 45     edge[tot].to = u;
 46     edge[tot].cap = 0;
 47     edge[tot].cost = -cost;
 48     edge[tot].flow = 0;
 49     edge[tot].nxt = head[v];
 50     head[v] = tot++;
 51 }
 52  
 53 bool SPFA(int s,int t)
 54 {
 55     queue<int>q;
 56     for(int i = 0; i < N; ++i)
 57     {
 58         dis[i] = INF;
 59         vis[i] = false;
 60         pre[i] = -1;
 61     }
 62     dis[s] = 0;
 63     vis[s] = true;
 64     q.push(s);
 65     while(!q.empty())
 66     {
 67         int u = q.front();
 68         q.pop();
 69         vis[u] = false;
 70         for(int i = head[u]; ~i; i = edge[i].nxt)
 71         {
 72             int v = edge[i].to;
 73             if(edge[i].cap > edge[i].flow && sgn(dis[v] - dis[u] - edge[i].cost) > 0)
 74             {
 75                 dis[v] = dis[u] + edge[i].cost;
 76                 pre[v] = i;
 77                 if(!vis[v])
 78                 {
 79                     vis[v] = true;
 80                     q.push(v);
 81                 }
 82             }
 83         }
 84     }
 85     if(pre[t] == -1) return false;
 86     else return true;
 87 }
 88  
 89 int minCostMaxflow(int s, int t)
 90 {
 91     int flow = 0;
 92     ans = 0;
 93     while(SPFA(s, t))
 94     {
 95         int Min = INF;
 96         for(int i = pre[t]; ~i; i = pre[edge[i ^ 1].to])
 97         {
 98             Min = min(Min, edge[i].cap - edge[i].flow);
 99         }
100         for(int i = pre[t]; ~i; i = pre[edge[i ^ 1].to])
101         {
102             edge[i].flow += Min;
103             edge[i ^ 1].flow -= Min;
104             ans += edge[i].cost * Min;
105         }
106         flow += Min;
107     }
108     return flow;
109 }
110  
111 int n, m;
112 int s[maxn], b[maxn], tmp[maxn];
113  
114 int main()
115 {
116     int t;
117     scanf("%d", &t);
118     while(t--)
119     {
120         scanf("%d %d", &n, &m);
121         Init(n + 2);
122         for(int i = 1; i <= n; ++i)
123         {
124             scanf("%d %d", s + i, b + i);
125             if(s[i] - b[i] > 0) addedge(0, i, s[i] - b[i], 0);
126             if(s[i] - b[i] < 0) addedge(i, n + 1, b[i] - s[i], 0);  
127         }
128  
129         for(int i = 1; i <= m; ++i)
130         {
131             int u, v, c;
132             double p;
133             scanf("%d %d %d %lf", &u, &v, &c ,&p);
134             p = -log(1.0 - p);
135             if(c > 0) addedge(u, v, 1, 0);
136             if(c > 1) addedge(u, v, c - 1, p);
137         }
138         int flow = minCostMaxflow(0, n + 1);
139         ans = pow(EI, -ans);
140         printf("%.2f
", 1.0 - ans);
141     }
142     return 0;
143 }

View Code

H Pattern

留坑。

I Travel Brochure

留坑。

J Cliques

留坑。

K Finding Hotels

题意：有若干酒店，以及一些旅客，每个旅客有价格接受范围，对于每个旅客要找出可接受价格以内的所有酒店中最近的

思路：KDTree 对于价格直接特判，如果超出，直接return INF 还要注意多解的情况下取id小的

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 #define ll long long
  5 #define N 200010
  6 #define DIM 10
  7 #define INF 0x3f3f3f3f3f3f3f3f
  8 inline ll sqr(ll x) { return x * x; }
  9 namespace KD
 10 {
 11     int K;
 12     struct Point
 13     {
 14         ll x[DIM]; 
 15         int id;
 16         ll distance(const Point &b) const  
 17         { 
 18             if (x[2] < b.x[2]) return INF;      
 19             ll ret = 0;  
 20             for (int i = 0; i < K; ++i) ret += sqr(x[i] - b.x[i]);  
 21             return ret;
 22         }
 23         void input(int id) { this->id = id; for (int i = 0; i < K + 1; ++i) scanf("%lld", x + i); }
 24         void output() { for (int i = 0; i < K + 1; ++i) printf("%lld%c", x[i], " 
"[i == K]); }
 25     };
 26     struct cmpx  
 27     {
 28         int div;
 29         cmpx(const int &div) { this->div = div; }
 30         bool operator () (const Point &a, const Point &b)
 31         { 
 32             for (int i = 0; i < K; ++i) if (a.x[(div + i) % K] != b.x[(div + i) % K]) 
 33                 return a.x[(div + i) % K] < b.x[(div + i) % K];
 34             return true;
 35         }
 36     };
 37     bool cmp(const Point &a, const Point &b, int div) { return cmpx(div)(a, b); }   
 38     struct node
 39     {
 40         Point e;
 41         node *lc, *rc; 
 42         int div; 
 43     }pool[N], *tail, *root; 
 44     void init() { tail = pool; } 
 45     node* build(Point *a, int l, int r, int div) 
 46     {
 47         if (l >= r) return NULL;
 48         node *p = tail++;
 49         p->div = div;  
 50         int mid = (l + r) >> 1;
 51         nth_element(a + l, a + mid, a + r, cmpx(div));
 52         p->e = a[mid];
 53         p->lc = build(a, l, mid, (div + 1) % K);
 54         p->rc = build(a, mid + 1, r, (div + 1) % K);
 55         return p;  
 56     }
 57     Point res; ll Min;
 58     void search(Point p, node *x, int div) 
 59     {
 60         if (!x) return; 
 61         if (cmp(p, x->e, div))
 62         {
 63             search(p, x->lc, (div + 1) % K);  
 64             ll tmp = p.distance(x->e); 
 65             if (tmp < Min || tmp == Min && x->e.id < res.id)   
 66             {
 67                 Min = tmp;
 68                 res = x->e;
 69             }
 70             if (sqr(x->e.x[div] - p.x[div]) <= Min)  
 71                 search(p, x->rc, (div + 1) % K);  
 72         }
 73         else
 74         {
 75             search(p, x->rc, (div + 1) % K);
 76             ll tmp = p.distance(x->e);  
 77             if (tmp < Min || tmp == Min && x->e.id < res.id)
 78             {
 79                 Min = tmp;
 80                 res = x->e;  
 81             }
 82             if (sqr(x->e.x[div] - p.x[div]) <= Min)
 83                 search(p, x->lc, (div + 1) % K);  
 84         }
 85     }
 86     void search(Point p)
 87     {
 88         Min = INF;
 89         search(p, root, 0);
 90     }
 91 }
 92 
 93 int t, n, q;
 94 KD::Point p[N];
 95 
 96 void Run()
 97 {
 98     for (scanf("%d", &t); t--; )
 99     {
100         KD::K = 2;
101         scanf("%d%d", &n, &q); 
102         for (int i = 0; i < n; ++i) p[i].input(i);
103         KD::init();
104         KD::root = KD::build(p, 0, n, 0);
105         for (int i = 1; i <= q; ++i)
106         {
107             KD::Point o; o.input(0);
108             KD::search(o);
109             KD::res.output(); 
110         }
111     }
112 }
113 
114 int main()
115 {
116     #ifdef LOCAL
117         freopen("Test.in", "r", stdin); 
118     #endif 
119 
120     Run();
121     return 0;
122 
123 }

View Code

L Tower Attack

留坑。

M Generator and Monitor

留坑。

牛客国庆集训派对Day7 Solution

相关推荐