首页 > 其他分享 >SMU Summer 2024 Contest Round 8

SMU Summer 2024 Contest Round 8

时间:2024-07-27 19:28:18浏览次数:14  
标签:Summer int auto SMU cin mid 2024 vector dp

SMU Summer 2024 Contest Round 8

Product

思路

注意到 \(\prod\limits_{i=1}^NL_i\le10^5\),也就是说 N 不会超过 16,因为 \(2^{17}>10^5\),所以我们可以直接暴搜。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 n, x;
    cin >> n >> x;

    vector L(n, vector<i64>());
    for (int i = 0; i < n; i ++) {
        int k;
        cin >> k;
        vector<i64> a(k);
        for (auto &j : a)
            cin >> j;
        L[i] = a;
    }

    i64 ans = 0;
    auto dfs = [&](auto & self, int num, __int128 res)->void{

        if (res > x) return;

        if (num == n) {
            if (res == x)
                ans ++;
            return ;
        }

        for (int i = 0; i < L[num].size(); i ++) {
            self(self, num + 1, res * L[num][i]);
        }

    };

    dfs(dfs, 0, 1);

    cout << ans << '\n';

    return 0;
}

Dice Sum

思路

考虑 dp。

设 \(dp_{i,j}\) 为前 i 个数中总和为 j 的方案数 则有转移方程:

\[dp_{i,j}=\sum\limits_{k=1}^{min(j,m)}dp_{i-1,j-k} \]

上面是取模模板太长不放了。

代码

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);

   int n, m, k;
   cin >> n >> m >> k;

   vector<vector<Z>> dp(n + 1, vector<Z>(k + 1));

   for (int i = 1; i <= m; i ++)
      dp[1][i] = 1;

   for (int i = 2; i <= n; i ++) {
      for (int j = 1; j <= k; j ++)
         for (int p = 1; p <= min(j, m); p ++) {
            dp[i][j] += dp[i - 1][j - p];
         }
   }

   Z ans = 0;
   for (int i = 0; i <= k; i ++)
      ans += dp[n][i];

   cout << ans << '\n';

   return 0;
}

Ubiquity

思路

每一个位置有 10 中选择,总方案数为 \(10^N\) 种,选定一个为 0/9 的方案数有 \(9^N\) 种,直接相减会多减去 0 和 9 的方案数,需要加上 \(8^N\) 。

即:

\[10^N-2\times9^N+8^N \]

上快速幂搞一下即可。

代码

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);

   int n;
   cin >> n;

   cout << Z(power(Z(10), n) - 2 * power(Z(9), n) + power(Z(8), n)) << '\n';

   return 0;
}

FG operation

思路

考虑 dp。

因为每次是删掉前两个数,所以考虑从左往右转移。

设 \(dp_{i,j}\) 表示为删掉第 i 个数后 \((x+y)\%10\) 为 j 的方案数。

转移方程为 :

\[dp_{i,(j+a_i)\bmod 10}=dp_{i,(j+a_i)\bmod 10}+dp_{i-1,j} \]

\[dp_{i,(j\times a_i)\bmod 10}=dp_{i,(j\times a_i)\bmod 10}+dp_{i-1,j} \]

代码

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<i64> a(n + 1);
    for (int i = 1; i <= n; i ++)
        cin >> a[i];

    vector<vector<Z>> dp(n + 1, vector<Z>(10));

    dp[1][a[1]] = 1;
    for (int i = 2; i <= n; i ++) {
        for (int j = 0; j <= 9; j ++) {
            dp[i][j * a[i] % 10] += dp[i - 1][j];
            dp[i][(j + a[i]) % 10] += dp[i - 1][j];
        }
    }

    for (int i = 0; i <= 9; i ++) {
        cout << dp[n][i] << '\n';
    }

    return 0;
}

Left Right Operation

思路

前缀和后缀和枚举 L 和 R 两数更新前后缀更小的和,然后枚举 i 找到最小的答案即可。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 n, l, r;
    cin >> n >> l >> r;

    vector<i64> a(n + 1), pre(n + 1), suf(n + 2);
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }

    for (int i = 0; i <= n; i ++) {
        pre[i] = min(pre[i], i * l);
    }

    for (int i = n; i >= 1; i --) {
        suf[i] = min(suf[i + 1] + a[i], (n - i + 1) * r);
    }

    i64 ans = 1e15;
    for (int i = 0; i <= n; i ++) {
        ans = min(ans, pre[i] + suf[i + 1]);
    }

    cout << ans << '\n';

    return 0;
}

Add and Mex

思路

根据 Mex 的性质,只有在 \([0,N]\) 的范围内才会对答案有贡献,且最大答案为 N + 1,又因为每次 +i,所以一个数会在第 \(\frac Ni\) 超过 N ,不再对答案产生贡献,因此我们可以求出一个每个数会在哪个区间次数内对答案产生贡献,即 \(0\le a_i+k\times i\le N\),得出 \(k\in [\lceil\frac{-a_i}{i}\rceil,\lfloor\frac{N-a_i}{i}\rfloor]\),这样枚举区间是一个调和级数级别的,即最终复杂度为 \(O(nln\ n)\) ,然后对于每一次询问暴力枚举区间内的 Mex 值即可。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);

   int n, m;
   cin >> n >> m;

   vector idx(m + 1, set<int>());

   for (int i = 1; i <= n; i ++) {
      int a;
      cin >> a;
      int l = max((-a + i - 1) / i, 0), r = max((n - a) / i, 0);
      a += l * i;
      for (int j = l; j <= min(r, m); j ++, a += i) {
         idx[j].insert(a);
      }
   }

   for (int i = 1; i <= m; i ++) {
      int ans = 0;
      while (idx[i].count(ans))
         ans ++;
      cout << ans << '\n';
   }

   return 0;
}

Diameter set

思路

根据树的直径的性质:树的每一条直径一定经过一个公共点或一条公共边,经过的是点还是边取决于直径的长度为奇数还是偶数。

要找到相隔为 D 也就是树的直径的点的集合,就是要以树的中心为根,找到其子树内相差为 \(\frac D2\) 的点的集合。

树的直径为偶数的时候,这时候说明肯定存在一个中心点,找到离树的中心 \(\frac D2\) 的位置也就是找它子树中以离它儿子结点 \(\frac D2 -1\) 的位置,假设中心点为 mid,其儿子结点子树中共存在 x 个满足要求的集合,cnt 表示一个集合中的满足要求的点数,其中每个集合中只能选择一个点,因为同在一个子树里的两点其连成的路径不会经过输的中心,也就不可能为 D,其次集合中的点也可以不选作为一种方案,所以一个集合产生的贡献就是 cnt+1,所以总方案为 \(\prod\limits_{v\in son_{mid}}(cnt_v+1)\),根据题目要求至少要有两个点,所以我们要减去所有集合只选了一个点的方案数和所有点都没选的方案数,即最终答案就是 \(\prod\limits_{v\in son_{mid}}(cnt_v+1)-\sum\limits_{v\in son_{mid}}cnt_v-1\)。

树的直径为奇数的时候,这时候只存在一条中心边,所以答案只能由这条中心边的两点的子树来产生贡献,即两边的集合点数乘起来 \(cnt_1\times cnt_2\) ,这个时候不能加 1 了,因为只有两个集合,必须要选两个点也就是两个集合一边选一个。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

struct Tree {
   int n, d = 0; //顶点,直径,树中心
   //自顶向下u到其叶子结点最远距离d1,次长距离d2(与最长路径无公共边)
   //p1,p2表示结点u向下更新时是由哪个结点更新来的
   //up表示结点u向上到祖宗结点的最远距离
   vector<int> d1, d2, p1, p2, up;
   vector<vector<int>> g;
   Tree(int n): n(n), d1(n + 1), d2(n + 1), g(n + 1), p1(n + 1), p2(n + 1), up(n + 1) {}

   void  add(int u, int v) {
      g[u].emplace_back(v);
      g[v].emplace_back(u);
   }
   //求直径//自顶向下求u到叶子结点的最远距离
   void dfs(int u, int fa) {
      d1[u] = d2[u] = 0;
      for (auto v : g[u]) {
         if (v == fa)continue;
         dfs(v, u);
         auto t = d1[v] + 1;
         if (t > d1[u]) {
            d2[u] = d1[u], p2[u] = p1[u];
            d1[u] = t, p1[u] = v;
         } else if (t > d2[u]) {
            d2[u] = t, p2[u] = v;
         }
      }
      d = max(d, d1[u] + d2[u]);
   }
   //自底向上求u到其它结点的最长路径
   void dfsup(int u, int fa) {
      for (auto v : g[u]) {
         if (v == fa) continue;
         //如果父结点u向下的最长路径经过v
         if (p1[u] == v) {
            //结点v向上走到最长路径为
            //父结点u继续向上的的最长路径和u向下走的次长路径的最大值+边权
            up[v] = max(up[u], d2[u]) + 1;
         } else {
            //如果父结点u向下的最长路径不经过v
            up[v] = max(up[u], d1[u]) + 1;
         }
         dfsup(v, u);
      }
   }

   //求树的直径
   int FindDiameter() {
      dfs(1, 0);
      return d;
   }

   //求树的中心
   vector<int> FindCenter() {
      dfsup(1, 0);
      i64 res = INT_MAX;
      vector<int> mid;
      for (int i = 1; i <= n; i ++) {
         auto t = max(d1[i], up[i]);
         if (t < res) {
            res = t;
            vector<int>().swap(mid);
            mid.emplace_back(i);
         } else if (t == res) {
            mid.emplace_back(i);
         }
      }
      return mid;
   }

};

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);

   int n;
   cin >> n;

   Tree tr1(n);
   for (int i = 1; i < n; i ++) {
      int u, v;
      cin >> u >> v;
      tr1.add(u, v);
   }

   const i64 mod = 998244353;
   auto D = tr1.FindDiameter();
   auto mid = tr1.FindCenter();

   auto calc = [&](auto & self, int u, int fa, int dis, int x)->int{
      int res = 0;
      if (dis == x) res ++;
      for (auto v : tr1.g[u]) {
         if (v == fa)continue;
         res += self(self, v, u, dis + 1, x);
      }
      return res;
   };

   if (D % 2 == 0) {
      i64 ans = 1, no = 0, d = D / 2 - 1;
      for (auto v : tr1.g[mid[0]]) {
         int cnt = 0;
         cnt = calc(calc, v, mid[0], 0, d);
         ans = ans * (cnt + 1) % mod;
         no += cnt;
      }
      cout << (ans - no - 1 + mod) % mod << '\n';
   } else {
      i64 d = D / 2;
      i64 cnt1 = calc(calc, mid[0], mid[1], 0, d);
      i64 cnt2 = calc(calc, mid[1], mid[0], 0, d);
      cout << cnt1 * cnt2 % mod << '\n';
   }

   return 0;
}

标签:Summer,int,auto,SMU,cin,mid,2024,vector,dp
From: https://www.cnblogs.com/Kescholar/p/18327377

相关文章

  • 2024年大厂AI大模型面试题精编+答案解析!!
    前言随着AI市场,人工智能的爆火,在接下来的金九银十招聘高峰期,各大科技巨头和国有企业将会对AGI人才的争夺展开一场大战,为求职市场注入了新的活力。为了助力求职者在面试中展现最佳状态,深入理解行业巨头的选拔标准变得至关重要。尤其是对于AGI(ArtificialGeneralIntelligen......
  • 2024牛客暑期多校训练营2
    GTheSetofSquares思路:对于一个序列内的所有数的乘积可以分解为p1k1p2k2...pnkn,(p为质数)此时只有当k都为偶数时,这个序列数的乘积才为完全平方数当在两个序列当中,所有k为奇数时对应的质数p都相同,说明这两个序列合并可以构成完全平方数那么可以以ki的奇偶来表示某个质数的状态......
  • 2024/07/27 每日一题
    LeetCode3106满足距离约束且字典序最小的字符串classSolution:defgetSmallestString(self,s:str,k:int)->str:ans=list(s);res=ord('a')fori,xinenumerate(map(ord,ans)):cnt=min(x-res,res+26-x)......
  • 算法训练 2024.7.27 17:25
    目录1.两数之和2.反转链表3.是否为有效的括号4.最长公共前缀5.合并两个有序数组6.岛屿的个数7.最小路径和8.三数之和9.计数质数10.字符串转换整数(atoi)1.两数之和题目:给定一个整数数组nums和一个目标值target,请你在该数组中找出和为目标值的那两个整......
  • Python数据预处理+正态性检验+异常值处理+Q-Q图-K-S检验+相关性分析(2024MathorCup A题
    #数据预处理#正态性检验、Q-Q图、箱线图、直方图、相关性分析#Q-Q图importnumpyasnpimportpandasaspdimportmatplotlib.pyplotaspltfromscipy.statsimportnormfromscipy.statsimportprobplota=pd.read_excel('附件1:小区基本信息.xlsx',engine='openpyxl'......
  • 2024暑假第四周总结
    数组容器,可以用来存储同种数据类型的多个值需要结合隐式转换考虑容器的类型和存储数据的类型保持一致数组的定义:格式一:数据类型[]数组名int[]array格式二:数据类型数组名[]intarray[]数组初始化:在内存中,为数组容器开辟空间,并将数据存入容器中的过程数组静态初......
  • 2024.7.22至2024.7.27周总结
    本周学习任务清单数据结构:树链剖分。解题思路:CDQ分治,整体二分。数论:费马小定理,素数筛法,欧拉定理,逆元,拓展欧几里得算法,中国剩余定理,Miller_Rabin素数检测,PollarRho分解质因数算法。多项式和生成函数:拉格朗日插值法,普通生成函数。线性代数:向量,线性组合,线性变换,线性,矩阵,行列......
  • 2024暑假集训测试13
    前言比赛链接。从来没见过交互题,T1狂CE不止心态炸了,后面的题也没打好,T2、T3简单题都不会了,所以为啥T4又放黑题。T1大众点评原题:AT_joisc2014_d。难点主要在交互,赛时琢磨了半场比赛终于搞明白是啥玩意儿了,可以将给定库当成压缩的一部分代码,可以调用里面的函数,输入......
  • 怎么判断电脑屏幕被监控?电脑被监控可以看到什么?丨2024超强科普!
    各位同仁,是不是正在怀疑自己的电脑被监控了?那么又该怎么盘点自己的电脑是不是正在被监控,假如真的被监控,老板又会看到什么内容呢?别急,且听我慢慢道来!一、电脑被监控的表现黑屏闪烁当电脑被监控时,屏幕可能会出现短暂的黑屏或频繁闪烁。这种情况多出现在电脑启动或打开特定程......
  • P2024 [NOI2001] 食物链
    原题链接题解关系具有矢量特性,因此可以带权并查集维护code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;intfa[50006];intval[50006];intfinds(intnow){if(now==fa[now])returnnow;inttem=fa[now];fa[now]=finds(fa[now])......