CCPC-Wannafly Winter Camp Day7 (Div2, onsite)

Replay

Dup4：

啥都不会? 只能看着两位聚聚A题?

模拟题不会写，日常摔锅
u， v分不清，日常演员
又是自己没理清楚就抢键盘上机导致送了一万个罚时，日常背锅

A：迷宫

Solved.

考虑所有人从1号点排队出发，所有人都回到自己位置的时间

让深度大的先走，这样就不会产生堵塞

那么每个人的时间就是在1号点的等待时间+深度

取最大值即可

 #include<bits/stdc++.h>

 using namespace std;

 #define N 100010

 int n, a[N];

 vector <int> G[N];

 int deep[N], fa[N];

 void DFS(int u)

 {

     for (auto v : G[u]) if (v != fa[u])

     {

         deep[v] = deep[u] + ;

         fa[v] = u;

         DFS(v);

     }

 }

 int main()

 {

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

     {

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

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

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

         {

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

             G[u].push_back(v);

             G[v].push_back(u);

         }

         deep[] = ; DFS();

         vector <int> vec;

         for (int i = ; i <= n; ++i) if (a[i]) vec.push_back(i);

         sort(vec.begin(), vec.end(), [](int a, int b) { return deep[a] > deep[b]; });

         int res = ;

         int cnt = ;

         for (auto it : vec)

         {

             res = max(res, cnt + deep[it]);

             ++cnt;

         }

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

     }

     return ;

 }

C：斐波那契数列

Solved.

斐波那契数列$前n项和的通项是$

$Fib_n \& (Fib_n - 1) = Fib_n - lowbit(Fib_n)$

$S_n = 2 \cdot a_n + a_{n - 1} - 1$

打表找规律发现

后面那部分是

$1 1 2 1 1 8 1 1 2 1 1 16 1 1 2 1 1 8 1 1 2 1 1\cdots$

有对称性，可以递归求和

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 const ll MOD = (ll);

 int t; ll R;

 struct node

 {

     ll a[][];

     node operator * (const node &other) const

     {

         node res; memset(res.a, , sizeof res.a);

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

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

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

                     res.a[i][j] = (res.a[i][j] + a[i][k] * other.a[k][j] % MOD + MOD) % MOD;

         return res;

     }

 };

 ll a[][] =

 {

     , ,

     , ,

 };

 ll b[][] =

 {

     , ,

     , ,

 };

 node qpow(ll n)

 {

     node base;

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

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

             base.a[i][j] = a[i][j];

     node res;

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

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

             res.a[i][j] = b[i][j];

     while (n)

     {

         if (n & ) res = res * base;

         base = base * base;

         n >>= ;

     }

     return res;

 }

 ll qpow(ll base, ll n)

 {

     ll res = ;

     while (n)

     {

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

         base = (base * base) % MOD;

         n >>= ;

     }

     return res;

 }

 ll pos[], num[], sum[];

 ll solve(ll now)

 {

     if (now <= ) return ;

     if (now == ) return ;

     if (now == ) return ;

     if (now == ) return ;

     if (now == ) return ;

     if (now == ) return ;

     int id = upper_bound(pos + , pos + , now) - pos - ;

     if (pos[id] == now) return (sum[id] + num[id]) % MOD;

     return ((solve(now - pos[id]) + solve(pos[id])) % MOD);

 }

 int main()

 {

     pos[] = ;

     for (int i = ; i <= ; ++i) pos[i] = pos[i - ] << ;

     num[] = ;

     for (int i = ; i <= ; ++i) num[i] = (num[i - ] << ) % MOD;

     sum[] = ;

     for (int i = ; i <= ; ++i) sum[i] = ((sum[i - ] << ) % MOD + num[i - ]) % MOD;

     scanf("%d", &t);

     while (t--)

     {

         scanf("%lld", &R);

         ll need = ;

         if (R == ) need = ;

         else if (R == ) need = ;

         else if (R == ) need = ;

         else need = (2ll * qpow(R - ).a[][] % MOD + qpow(R - ).a[][] % MOD -  + MOD) % MOD;

         //cout << R << " " << need << " " << solve(R) << "\n";

         printf("%lld\n", (need - solve(R) % MOD + MOD) % MOD);

     }

     return ;

 }

D：二次函数

Solved.

枚举哪两个式子相等，做三次

考虑二元一次方程的根，令$y相同，则有$

$x_1 = -\frac{a_1 \pm \sqrt{4 \cdot y + a_1^2 - 4 \cdot b_1}}{2}$

$x_2 = -\frac{a_2 \pm \sqrt{4 \cdot y + a_2^2 - 4 \cdot b_2}}{2}$

考虑根号下一定是一个平方数

那么令$T^2 = 4 \cdot y + a_1^2 - 4 \cdot b_1$

$t^2 = 4 \cdot y + a_2^2 - 4 \cdot b_2$

$T^2 - t^2 = (T + t) \cdot (T - t) = a_1^2 - 4 \cdot b_1 - a_2^2 + 4 \cdot b_2$

$枚举差值的因数分解，得到T 和 t 再判断是否可以$

$再特判差值为0 和差值为1的情况$

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define pll pair <ll, ll>

 int t;

 ll a[], b[];

 pll res;

 bool solve(ll a1, ll b1, ll a2, ll b2)

 {

     ll t1 = (a1 * a1 -  * b1);

     ll t2 = (a2 * a2 -  * b2);

     ll gap = abs(t1 - t2);

     if (gap == )

     {

         if ((t1 & ) == (t2 & ))

         {

             res.first = ;

             res.second = -(a2 - a1) / ;

             return true;

         }

         else

             return false;

     }

     if (gap == )

     {

         if ((t1 & ) != (t2 & ))

         {

             if (t1 > t2 && ((a1 & ) == ))

             {

                 res.first = -(a1 + ) / ;

                 res.second = -a2 / ;

                 return true;

             }

             else if (t1 < t2 && ((a2 & ) == ))

             {

                 res.first = -a1 / ;

                 res.second = -(a2 + ) / ;

                 return true;

             }

             else return false;

         }

     }

     for (int i = ; i * i < gap; ++i) if (gap % i ==  && (i + gap / i) %  == )

     {

         ll T = (i + gap / i) / ;

         ll t = (gap / i - i) / ;

         if (t1 < t2) swap(T, t);

         if ((T + a1) %  ==  && (t + a2) %  == )

         {

             res.first = -((T + a1) / );

             res.second = -((t + a2) / );

             return true;

         }

     }

     return false;

 }

 void work()

 {

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

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

         {

             if (solve(a[i], b[i], a[j], b[j]))

             {

                 if (i == )

                 {

                     printf("%lld %lld %lld\n", res.first, j ==  ? res.second : , j ==  ?  : res.second);

                 }

                 else

                     printf("0 %lld %lld\n", res.first, res.second);

                 return;

             }

         }

 }

 int main()

 {

     scanf("%d", &t);

     while (t--)

     {

         for (int i = ; i < ; ++i) scanf("%lld%lld", a + i, b + i);

         work();

     }

     return ;

 }

E：线性探查法

Solved.

拓扑排序?

 #include<bits/stdc++.h>

 using namespace std;

 const int MAXN = 1e6 + ;

 const int maxn = 1e3 + ;

 struct Edge{

     int to, nxt;

     Edge(){}

     Edge(int to, int nxt): to(to), nxt(nxt){}

 }edge[MAXN << ];

 struct node{

     int val;

     int index;

     node(){}

     node(int val, int index):val(val), index(index){}

     bool operator < (const node &other) const{

         return val > other.val;

     }

 }brr[maxn];

 int n;

 int arr[maxn];

 int head[maxn], tot;

 int du[maxn];

 void Init()

 {

     tot = ;

     memset(head, -, sizeof head);

     memset(du, , sizeof du);

 }

 void addedge(int u,int v)

 {

     edge[tot] = Edge(v, head[u]); head[u] = tot++;

 }

 void solve()

 {

     priority_queue<node>q;

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

     {

         q.push(brr[i]);

     }

     int tot = ;

     while(!q.empty())

     {

         node st = q.top();

         q.pop();

         arr[tot++] = st.val;

         int u = st.index;

         for(int i = head[u]; ~i; i = edge[i].nxt)

         {

             int v = edge[i].to;

             --du[v];

             if(du[v] == ) q.push(brr[v]);

         }

     }

 }

 int main()

 {

     while(~scanf("%d" ,&n))

     {

         Init();

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

         {

             int x;

             scanf("%d", &x);

             int now = i;

             int pre = x % n;

             brr[i] = node(x, i);

             while(now != pre)

             {

                 now = (now -  + n) % n;

                 addedge(now, i);

                 du[i]++;

             }

         }

         solve();

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

     }

     return ;

 }

F：逆序对!

Solved.

考虑两个位置的数对有多少个数异或会让他们对答案产生贡献

如果$a > b 那么从高位到地位找到第一位不同的数这一位要放0，其他位任意的比m小的数$

$a < b 同理$

复杂度$O(n^2logn)$

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define N 1010

 const ll MOD = (ll);

 ll Bit[], res;

 int n, m, b[N];

 void solve(ll a, ll b)

 {

     for (int i = ; i >= ; --i)

     {

         int n1 = ((a >> i) & ), n2 = ((b >> i) & );

         if (n1 != n2)

         {

             ll tmp1 = m >> (i + );

             ll tmp2 = m & (Bit[i] - );

             ll sum = ;

             if((m >> i) & )

                 sum = (tmp1 * Bit[i] % MOD + tmp2 + ) % MOD;

             else

                 sum = (tmp1 * Bit[i]) % MOD;

             if (a < b) res = (res + sum) % MOD;

             else res = (res + m - sum + MOD) % MOD;

             return ;

         }

     }

 }

 int main()

 {

     Bit[] = ;

     for (int i = ; i <= ; ++i) Bit[i] = (Bit[i - ] << );

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

     {

         res = ;

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

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

             solve(b[i], b[j]);

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

     }

     return ;

 }

G：抢红包机器人

Solved.

至少存在一个机器人，枚举这一位机器人

那么它前面所有账号都是机器人，并且这种关系是传递的，DFS即可

u, v 傻傻分不清楚可还行

 #include<bits/stdc++.h>

 using namespace std;

 const int INF = 0x3f3f3f3f;

 const int MAXN = 1e6 + ;

 const int maxn = 1e2 + ;

 struct Edge{

     int to, nxt;

     Edge(){}

     Edge(int to, int nxt):to(to), nxt(nxt){}

 }edge[MAXN << ];

 int n, m;

 int head[maxn], tot;

 int vis[maxn];

 int arr[maxn];

 void Init()

 {

     tot = ;

     memset(head, -, sizeof head);

 }

 void addedge(int u,int v)

 {

     edge[tot] = Edge(v, head[u]); head[u] = tot++;

 }

 void DFS(int u)

 {

     for(int i = head[u]; ~i; i = edge[i].nxt)

     {

         int v = edge[i].to;

         if(vis[v]) continue;

         vis[v] = ;

         DFS(v);

     }

 }

 int main()

 {

     while(~scanf("%d %d", &n, &m))

     {

         Init();

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

         {

             scanf("%d", &k);

             for(int j = ; j <= k; ++j)

             {

                 scanf("%d", arr + j);

             }

             for(int u = k; u >= ; --u)

             {

                 for(int v = u - ; v >= ; --v)

                 {

                     addedge(arr[u], arr[v]);

                 }

             }

         }

         int ans = INF;

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

         {

             memset(vis, , sizeof vis);

             vis[i] = ;

             DFS(i);

             int sum = ;

             for(int j = ; j <= n; ++j) sum += vis[j];

             ans = min(ans, sum);

         }

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

     }

     return ;

 }

J：强壮的排列

Solved.

打了个表？ Comet OJ 支持512Kb 感人

巴特西

CCPC-Wannafly Winter Camp Day7 (Div2, onsite)

最新文章

热门文章