Avito Cool Challenge 2018 Solution

A. Definite Game

签.

 #include <bits/stdc++.h>

 using namespace std;

 int main()

 {

     int a;

     while (scanf("%d", &a) != EOF)

     {

         [](int x)

         {

             for (int i = x - ; i >= ; --i) if (x % i)

             {

                 printf("%d\n", x - i);

                 return;

             }

             printf("%d\n", x);

         }(a);

     }

     return ;

 }

B. Farewell Party

签。

 #include <bits/stdc++.h>

 using namespace std;

 #define N 100010

 int n, a[N], b[N], cnt[N];

 vector <int> v[N];

 int ans[N];

 bool ok()

 {

     for (int i = ; i <= n; ++i) if (!v[i].empty() && v[i].size() != i)

         return false;

     return true;

 }

 void solve()

 {

     int cnt = ;

     for (int i = ; i <= n; ++i) v[i].clear();

     for (int i = ; i <= n; ++i)

     {

         int id = n - a[i];

         if (v[id].size() == id)

         {

             ++cnt;

             for (auto it : v[id]) ans[it] = cnt;

             v[id].clear();

         }

         v[id].push_back(i);

     }

     if (!ok())

     {

         puts("Impossible");

         return;

     }

     else

     {

         for (int i = ; i <= n; ++i) if (!v[i].empty())

         {

             ++cnt;

             for (auto it : v[i])

                 ans[it] = cnt;

         }

         puts("Possible");

         for (int i = ; i <= n; ++i) printf("%d%c", ans[i], " \n"[i == n]);

     }

 }

 int main()

 {

     while (scanf("%d", &n) != EOF)

     {

         for (int i = ; i <= n; ++i) scanf("%d", a + i);

         solve();

     }

     return ;

 }

C. Colorful Bricks

Upsolved.

题意：

有$一行n个方格，m种颜色，恰好有k个方块与它左边方块的颜色不同$

求方案数

思路：

$dp[i][j] 表示到第i个方格，有j个方块与左边方块颜色不同的方案数$

转移有

$dp[i + 1][j] += dp[i][j]$

$dp[i + 1][j + 1] += dp[i][j] * (m - 1)$

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define N 2010

 const ll MOD = (ll);

 int n, m, k;

 ll f[N][N];

 int main()

 {

     while (scanf("%d%d%d", &n, &m, &k) != EOF)

     {

         memset(f, , sizeof f);

         f[][] = m;

         for (int i = ; i <= n; ++i)

         {

             for (int j = ; j <= min(i - , k); ++j)

             {

                 f[i][j] = (f[i][j] + f[i - ][j]) % MOD;

                 f[i][j + ] = (f[i][j + ] + f[i - ][j] * (m - ) % MOD) % MOD;

             }

         }

         printf("%lld\n", f[n][k]);

     }

     return ;

 }

D. Maximum Distance

Upsolved.

题意：

有一张图

定义一条路径的长度的路径上边权最大值

定义两点距离为两点之间最短路径

有一些特殊点，要对所有特殊点求离它最远的特殊点

思路：

我们考虑一条边所连接的两个连通块里，如果这两个连通块里都有特殊点

那么这条边的权值就可以用于更新特殊点的答案

其实就是一个求最小生成树的过程，先按边权排序

要注意的是不是求整个图的最小生成树，而是所有特殊点的最小生成树

其实是最小瓶颈生成树.

 #include <bits/stdc++.h>

 using namespace std;

 #define N 100010

 int n, m, k;

 struct node

 {

     int u, v, w;

     void scan() { scanf("%d%d%d", &u, &v, &w); }

     bool operator < (const node &other) const { return w < other.w; }

 }edge[N];

 int pre[N], cnt[N];

 int find(int x) { return pre[x] ==  ? x : pre[x] = find(pre[x]); }

 int Kruskal()

 {

     sort(edge + , edge +  + m);

     for (int i = ; i <= m; ++i)

     {

         int u = edge[i].u, v = edge[i].v, w = edge[i].w;

         int fu = find(u), fv = find(v);

         if (fu == fv) continue;

         cnt[fv] += cnt[fu];

         pre[fu] = fv;

         if (cnt[fv] == k) return w;

     }

 }

 int main()

 {

     while (scanf("%d%d%d", &n, &m, &k) != EOF)

     {

         memset(pre, , sizeof pre);

         memset(cnt, , sizeof cnt);

         for (int i = , x; i <= k; ++i) scanf("%d", &x), cnt[x] = ;

         for (int i = ; i <= m; ++i) edge[i].scan();

         int res = Kruskal();

         for (int i = ; i <= k; ++i) printf("%d%c", res, " \n"[i == k]);

     }

     return ;

 }

E. Missing Numbers

Upsolved.

题意：

有$n个数，给出a_2, a_4 \cdots a_n$

$n是偶数，提供a_1, a_3 \cdots a_{n - 1}$

使得

$所有前缀和都是平方数$

思路：

考虑$n = 2的时候$

$我们令b^2 = a_1 + a_2$

$a^2 = a_1$

那么有

$b^2 - a^2 = (b + a) \cdot (b - a) = a_2$

$我们将a_2 拆成 p \cdot q 的形式$

$令p >= q$

$那么有 b + a = p, b - a = q$

$解方程有 b = \frac{p + q}{2}$

$发现一限制条件 p, q的奇偶性要相同$

$那么a_1 = (\frac{p + q}{2})^2 - a_2$

那么如果有多解我们取$a_1最小的$

$因为当n >= 2的情况也可以同样这样推下去，会发现前面的项越小越好$

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define N 100010

 int n;

 ll x[N];

 vector <int> vec[N << ];

 void init()

 {

     for (int i = ; i <= ; ++i)

         for (int j = i * i; j <= ; j += i)

             vec[j].push_back(i);

 }

 int main()

 {

     init();

     while (scanf("%d", &n) != EOF)

     {

         for (int i = ; i <= n; i += ) scanf("%lld", x + i);

         bool flag = true;

         ll base = ;

         for (int i = ; i <= n; i += )

         {

             base += x[i + ];

             int limit = sqrt(x[i + ]);

             ll res = (ll)1e18;

             ll p, q;

             for (auto j : vec[x[i + ]])

                 if ((j % ) == ((x[i + ] / j) % ))

                 {

                     p = j, q = (x[i + ] / j);

                     ll tot = (p + q) / ;

                     tot *= tot;

                     if (tot > base)

                         res = min(res, tot - base);

                 }

             if (res <= (ll)1e13)

             {

                 x[i] = res;

                 base += res;

             }

             else

             {

                 flag = false;

                 break;

             }

         }

         if (!flag) puts("No");

         else

         {

             puts("Yes");

             for (int i = ; i <= n; ++i)

                 printf("%lld%c", x[i], " \n"[i == n]);

         }

     }

     return ;

 }

巴特西

Avito Cool Challenge 2018 Solution

最新文章

热门文章