ZOJ Monthly, March 2018 Solution

A - Easy Number Game

水。

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define N 100010

 ll arr[N];

 int n, m;

 int main()

 {

     int t; scanf("%d", &t);

     while (t--)

     {

         scanf("%d%d", &n, &m);

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

         sort(arr + , arr +  + n);

         ll res = ;

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

             res += arr[i] * arr[ * m - i + ];

         printf("%lld\n", res);

     }

     return ;

 }

B - Lucky Man

题意：判断大数开根后的奇偶性

思路：牛顿迭代法

 import java.io.BufferedInputStream;

 import java.util.Scanner;

 import java.math.*;

 public class Main {

     public static void main(String[] args) {

         Scanner in = new Scanner(new BufferedInputStream(System.in));

         int t = in.nextInt();

         BigInteger a, x, two; String n;

         two = BigInteger.valueOf();

         while (t-- != )

         {

             n = in.next();

             a = new BigInteger(n);

             x = new BigInteger(n.substring(, n.length() /  + ));

             while (a.compareTo(x.multiply(x)) < )

                 x = x.add(a.divide(x)).divide(two);

             if (x.mod(two).compareTo(BigInteger.ZERO) == ) System.out.println();

             else System.out.println();

         }

         in.close();

     }

 }

C - Travel along the Line

题意：一维坐标系中，刚开始位于原点，有$\frac{1}{4}$的概率坐标 +1 和 -1 有$\frac {1}{2} 的概率不动$ 求在第n秒的时候恰好到达第m个位置的概率

思路：考虑把一个0拆成两个0，变成四种操作，这样四种操作是等概率的，那么所有的可能性就是 $4^n$ 再考虑符合条件的方案数

可以考虑将m通过坐标变换转化成正的，那么一个满足题意的操作序列肯定是 1 的个数减去 -1的个数恰好为m

那么我们只需要枚举1的个数，排列组合一下即可

16说假如用a 表示 1 的个数 b 表示 -1 的个数 c 表示 0的个数

那么有$\frac {n!} {a! \cdot b! \cdot c!}$ 但是这里要考虑多乘上$2^c$ 因为每个0都有两种选择，可以是$0_1 或者是 0_2$

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define N 100010

 ll MOD = (ll)1e9 +;

 ll fac[N], Bit[N];

 ll qmod(ll base, ll n)

 {

     ll res = ;

     while (n)

     {

         if (n & ) res = res * base % MOD;

         base = base * base % MOD;

         n >>= ;

     }

     return res;

 }

 void Init()

 {

     fac[] = ;

     Bit[] = ;

     for (int i = ; i < N; ++i) fac[i] = fac[i - ] * i % MOD;

     for (int i = ; i < N; ++i) Bit[i] = Bit[i - ] *  % MOD;

 }

 int n, m;

 int main()

 {

     Init();

     int t; scanf("%d", &t);

     while (t--)

     {

         scanf("%d%d", &n, &m);

         if (m < ) m = -m;

         ll p = , q = qmod(, n);

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

             p = (p + (fac[n] * qmod(fac[i], MOD - ) %MOD * qmod(fac[i + m], MOD - ) % MOD * qmod(fac[n -  * i - m], MOD - ) % MOD * Bit[n -  * i - m] % MOD)) % MOD;

         ll res = p * qmod(q, MOD - ) % MOD;

         printf("%lld\n", res);

     }

     return ;

 }

D - Machine Learning on a Tree

留坑。

E - Yet Another Tree Query Problem

题意：每次询问$[l, r]$ 区间内所有点所在的连通块个数

思路：先预处理l 为 1 r 为 1 ->n 的答案考虑删去一个点对后面答案的影响

将一个点的所有孩子和父亲中，按编号排序

比如说点1 连出去的边有 4, 10, 20

那么对于右界为 2-3 的连通块个数少一

右界为5 - 9 的连通块个数不变

右界为 11 - 19 的连通块个数加1

BIT区间更新即可

 #include <bits/stdc++.h>

 using namespace std;

 #define N 200010

 #define pii pair <int, int>

 int t, n, q;

 vector <int> G[N];

 vector <pii> que[N];

 int base[N], ans[N];

 struct BIT

 {

     int a[N];

     void init() { memset(a, , sizeof a); }

     void update(int x, int val)    { for (; x <= n; x += x & -x) a[x] += val; }

     void update(int l, int r, int val)

     {

         if (r < l) return;

         update(l, val);

         update(r + , -val);

     }

     int query(int x)

     {

         int res = ;

         for (; x; x -= x & -x)

             res += a[x];

         return res;

     }

 }bit;

 void Run()

 {

     scanf("%d", &t);

     while (t--)

     {

         for (int i = ; i <= n; ++i) G[i].clear(), que[i].clear();

         bit.init();

         scanf("%d%d", &n, &q);

         for (int i = , u, v; i < n; ++i)

         {

             scanf("%d%d", &u, &v);

             G[u].push_back(v);

             G[v].push_back(u);

         }

         for (int i = , l, r; i <= q; ++i)

         {

             scanf("%d%d", &l, &r);

             que[l].emplace_back(r, i);

         }

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

         {

             int tmp = ;

             sort(G[i].begin(), G[i].end());

             for (auto v : G[i]) if (v < i)

                 --tmp;

             base[i] = base[i - ] + tmp;

         }

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

         {

             for (auto it : que[i])

                 ans[it.second] = base[it.first] + bit.query(it.first);

             G[i].push_back(n + );

             int pre = i + ;

             for (int j = , len = G[i].size(), add = -; j < len; ++j)

             {

                 int v = G[i][j];

                 if (v < i) continue;

                 bit.update(pre, v - , add);

                 pre = v; ++add;

             }

         }

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

     }

 }

 int main()

 {

     #ifdef LOCAL

         freopen("Test.in", "r", stdin);

     #endif 

     Run();

     return ;

 }

F - And Another Data Structure Problem

题意：两种操作，一种是区间立方，一种是区间求和

思路：考虑这个模数很特殊

$3^{48} \equiv 1 \pmod {99970}$

所以有

$a^{3^{48}} \equiv a \pmod {99971}$

所有任意数做48次后必然会回到原数考虑开48棵线段树解决

 #include <bits/stdc++.h>

 using namespace std;

 #define N 100010

 #define ll long long

 const ll MOD = ;

 int t, n, q;

 ll arr[N];

 struct SEG

 {

     ll a[N << ][], tmp[];

     int lazy[N << ];

     void init() { memset(a, , sizeof a); }

     void pushup(int id)

     {

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

             a[id][i] = (a[id << ][(i + lazy[id << ]) % ] + a[id <<  | ][(i + lazy[id <<  | ]) % ]) % MOD;

     }

     void pushdown(int id)

     {

         if (!lazy[id]) return;

         lazy[id << ] = (lazy[id << ] + lazy[id]) % ;

         lazy[id <<  | ] = (lazy[id <<  | ] + lazy[id]) % ;

         for (int i = ; i < ; ++i) tmp[i] = a[id][(i + lazy[id]) % ];

         memcpy(a[id], tmp, sizeof tmp);

         lazy[id] = ;

     }

     void build(int id, int l, int r)

     {

         lazy[id] = ;

         if (l == r)

         {

             a[id][] = arr[l];

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

                 a[id][i] = a[id][i - ] * a[id][i - ] % MOD * a[id][i - ] % MOD;

             return;

         }

         int mid = (l + r) >> ;

         build(id << , l, mid);

         build(id <<  | , mid + , r);

         pushup(id);

     }

     void update(int id, int l, int r, int ql, int qr, int val)

     {

         if (l >= ql && r <= qr)

         {

             lazy[id] = (lazy[id] + val) % ;

             return;

         }

         pushdown(id);

         int mid = (l + r) >> ;

         if (ql <= mid) update(id << , l, mid, ql, qr, val);

         if (qr > mid) update(id <<  | , mid + , r, ql, qr, val);

         pushup(id);

     }

     ll query(int id, int l, int r, int ql, int qr)

     {

         if (l >= ql && r <= qr) return a[id][lazy[id]];

         pushdown(id);

         int mid = (l + r) >> ;

         ll res = ;

         if (ql <= mid) res = (res + query(id << , l, mid, ql, qr)) % MOD;

         if (qr > mid) res = (res + query(id <<  | , mid + , r, ql, qr)) % MOD;

         //pushup(id);

         return res;

     }

 }seg;

 void Run()

 {

     scanf("%d", &t);

     while (t--)

     {

         scanf("%d%d", &n, &q);

         for (int i = ; i <= n; ++i) scanf("%lld", arr + i), arr[i] %= MOD;

         seg.build(, , n);

         for (int i = , op, l, r; i <= q; ++i)

         {

             scanf("%d%d%d", &op, &l, &r);

             if (op == ) seg.update(, , n, l, r, );

             else printf("%lld\n", seg.query(, , n, l, r));

         }

     }

 }

 int main()

 {

     #ifdef LOCAL

         freopen("Test.in", "r", stdin);

     #endif 

     Run();

     return ;

 }

 #include <bits/stdc++.h>

 using namespace std;

 #define N 100010

 #define ll long long

 const ll MOD = ;

 int t, n, q;

 ll arr[N];

 struct SEG

 {

     ll a[N << ][], tmp[];

     int lazy[N << ];

     void pushup(int id)

     {

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

             a[id][i] = (a[id << ][(i + lazy[id << ]) % ] + a[id <<  | ][(i + lazy[id <<  | ]) % ]) % MOD;

     }

     void build(int id, int l, int r)

     {

         lazy[id] = ;

         if (l == r)

         {

             a[id][] = arr[l];

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

                 a[id][i] = a[id][i - ] * a[id][i - ] % MOD * a[id][i - ] % MOD;

             return;

         }

         int mid = (l + r) >> ;

         build(id << , l, mid);

         build(id <<  | , mid + , r);

         pushup(id);

     }

     void update(int id, int l, int r, int ql, int qr, int val)

     {

         if (l >= ql && r <= qr)

         {

             lazy[id] = (lazy[id] + ) % ;

             return;

         }

         int mid = (l + r) >> ;

         if (ql <= mid) update(id << , l, mid, ql, qr, val);

         if (qr > mid) update(id <<  | , mid + , r, ql, qr, val);

         pushup(id);

     }

     ll query(int id, int l, int r, int ql, int qr, int k = )

     {

         k = (k + lazy[id]) % ;

         if (l >= ql && r <= qr) return a[id][k];

         int mid = (l + r) >> ;

         ll res = ;

         if (ql <= mid) res = (res + query(id << , l, mid, ql, qr, k)) % MOD;

         if (qr > mid) res = (res + query(id <<  | , mid + , r, ql, qr, k)) % MOD;

         return res;

     }

 }seg;

 void Run()

 {

     scanf("%d", &t);

     while (t--)

     {

         scanf("%d%d", &n, &q);

         for (int i = ; i <= n; ++i) scanf("%lld", arr + i), arr[i] %= MOD;

         seg.build(, , n);

         for (int i = , op, l, r; i <= q; ++i)

         {

             scanf("%d%d%d", &op, &l, &r);

             if (op == ) seg.update(, , n, l, r, );

             else printf("%lld\n", seg.query(, , n, l, r));

         }

     }

 }

 int main()

 {

     #ifdef LOCAL

         freopen("Test.in", "r", stdin);

     #endif 

     Run();

     return ;

 }

G - Neighboring Characters

留坑。

H - Happy Sequence ZOJ

题意：用1-n的数，每个数可以用无限次，组成长度为m的序列，求有多少个序列满足 $gcd(b_i, b_{i +1}) = b_{i}$

思路：考虑枚举序列里面不同的数的个数，根据题目范围，最多有10个不同的数，然后隔板法求方案数

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 long long f[];

 long long C[];

 long long MOD;

 int p[];

 int n, m;

 void dp(int t) {

     int j;

     j = ;

     while (p[t - ] * j <= n) {

         p[t] = p[t - ] * j;

         f[t]++;

         dp(t + );

         j++;

     }

 }

 ll qmod(ll base, ll n)

 {

     ll res = ;

     while (n)

     {

         if (n & ) res = res * base % MOD;

         base = base * base % MOD;

         n >>= ;

     }

     return res;

 }

 int main()

 {

     int i, j, t;

     long long ans;

     scanf("%d", &t);

     MOD = ;

     while (t--) {

         scanf("%d %d", &n, &m);

         memset(f, , sizeof f);

         memset(p, , sizeof p);

         ans = ;

         C[] = ;

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

             C[i] = (C[i - ] * (m - i) % MOD * qmod(i, MOD - )) % MOD;

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

             p[] = i;

             ++f[];

             dp();

         }

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

             ans = (ans + f[i] * C[i - ] % MOD) % MOD;

         }

         printf("%lld\n",ans);

     }

     return ;

 }

I - Your Bridge is under Attack

留坑。

J - Super Brain

水。

 #include <bits/stdc++.h>

 using namespace std;

 #define N 100010

 int n;

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

 int main()

 {

     int t; scanf("%d", &t);

     while (t--)

     {

         scanf("%d", &n);

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

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

         memset(cnt, , sizeof cnt);

         for (int i = ; i <= n; ++i) ++cnt[a[i]];

         int res = ;

         for (int i = ; i <= n; ++i) if (cnt[b[i]] == )

         {

             res = b[i];

             break;

         }

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

     }

     return ;

 }

巴特西

ZOJ Monthly, March 2018 Solution

最新文章

热门文章