• CodeCraft-21 and Codeforces Round 711 (Div. 2)A-F

    1.Problem - A - Codeforces

            （1）题意 

                    求一个大于等于n的整数x，满足gcd(x,sum(dig(x)) > 1，dig表示x的各个数位。

            （2）思路

                    考虑最差是满足gcd(x,sum(dig(x)) = 2,因此不会枚举很多，直接暴力枚举即可。

            （3）代码

    1. #include 
    2. #define rep(i,z,n) for(int i = z;i <= n; i++)
    3. #define per(i,n,z) for(int i = n;i >= z; i--)
    4. #define PII pair
    5. #define fi first
    6. #define se second
    7. #define vi vector
    8. #define vl vector
    9. #define pb push_back
    10. #define sz(x) (int)x.size()
    11. #define all(x) (x).begin(),(x).end()
    12. using namespace std;
    13. using ll = long long;
    14. const int N = 2e5 + 10;
    15. bool check(ll x)
    16. {
    17.     ll s = 0,rx = x;
    18.     while(rx) {
    19.         s += rx % 10;
    20.         rx /= 10;
    21.     }
    22.     return __gcd(x,s) >= 2;
    23. }
    24. void solve()
    25. {
    26.     ll n;
    27.     cin >> n;
    28.     while(n) {
    29.         if(check(n)) break;
    30.         n ++;
    31.     }
    32.     cout << n << '\n';
    33. }
    34. int main()
    35. {
    36.     ios::sync_with_stdio(false);
    37.     cin.tie(0),cout.tie(0);
    38.     int T = 1;
    39.     cin >> T;
    40.     while(T --) solve();
    41.     return 0;
    42. }

    2.Problem - B - Codeforces

            （1）题意

                    给你n个高为1，宽为w[i]的矩形，你有一个大矩型已经确定了宽为W，你需要确定最小的h满足能放入所有的高为1的矩形。

            （2）思路

                    考虑h一定满足单调性，所以直接二分h的值即可。

            （3）代码

    1. #include 
    2. #define rep(i,z,n) for(int i = z;i <= n; i++)
    3. #define per(i,n,z) for(int i = n;i >= z; i--)
    4. #define PII pair
    5. #define fi first
    6. #define se second
    7. #define vi vector
    8. #define vl vector
    9. #define pb push_back
    10. #define sz(x) (int)x.size()
    11. #define all(x) (x).begin(),(x).end()
    12. using namespace std;
    13. using ll = long long;
    14. const int N = 2e5 + 10;
    15. int a[N],n,w;
    16. bool check(int x)
    17. {
    18.     multiset<int> st;
    19.     rep(i,1,x) st.insert(w);
    20.     per(i,n,1) {
    21.         auto it = st.lower_bound(a[i]);
    22.         if(it == st.end()) return false;
    23.         int res = *it - a[i];
    24.         st.erase(it);
    25.         st.insert(res);
    26.     }
    27.     return true;
    28. }
    29. void solve()
    30. {
    31.     cin >> n >> w;
    32.     rep(i,1,n) cin >> a[i];
    33.     sort(a + 1,a + 1 + n);
    34.     int l = 1,r = n;
    35.     while(l <= r) {
    36.         int m = (l + r) >> 1;
    37.         if(check(m)) r = m - 1;
    38.         else l = m + 1;
    39.     }
    40.     cout << l << '\n';
    41. }
    42. int main()
    43. {
    44.     ios::sync_with_stdio(false);
    45.     cin.tie(0),cout.tie(0);
    46.     int T = 1;
    47.     cin >> T;
    48.     while(T --) solve();
    49.     return 0;
    50. }

    3.Problem - C - Codeforces

            （1）题意

                    给你一条长为k的射线，有n面镜子，每次你穿过一面镜子有两种选择，一种是降低你目前的等级，然后新生成一条反方向为目前等级-1的射线，一种是直接穿过镜子，问最多会有多少条射线。

            （2）思路

                    发现这是个计数题，因此直接考虑dp，dp[i][j]表示当前射线为i有j面镜子的方案数是多少。

                    转移方程：

                            1.若前一条是通过降级来的，则应该是dp[i - 1][n - j]这个位置来的。

                            2.若前一条是通过直接穿的，则应该是dp[i][j - 1]这个位置来的。

            （3）代码

    1. #include 
    2. #define rep(i,z,n) for(int i = z;i <= n; i++)
    3. #define per(i,n,z) for(int i = n;i >= z; i--)
    4. #define PII pair
    5. #define fi first
    6. #define se second
    7. #define vi vector
    8. #define vl vector
    9. #define pb push_back
    10. #define sz(x) (int)x.size()
    11. #define all(x) (x).begin(),(x).end()
    12. using namespace std;
    13. using ll = long long;
    14. const int N = 2e5 + 10;
    15. using i64 = long long;
    16.  
    17. constexpr int P = 1e9 + 7;
    18. // assume -P <= x < 2P
    19. int Vnorm(int x) {
    20.     if (x < 0) {
    21.         x += P;
    22.     }
    23.     if (x >= P) {
    24.         x -= P;
    25.     }
    26.     return x;
    27. }
    28. template<class T>
    29. T power(T a, i64 b) {
    30.     T res = 1;
    31.     for (; b; b /= 2, a *= a) {
    32.         if (b % 2) {
    33.             res *= a;
    34.         }
    35.     }
    36.     return res;
    37. }
    38. struct Mint {
    39.     int x;
    40.     Mint(int x = 0) : x(Vnorm(x)) {}
    41.     Mint(i64 x) : x(Vnorm(x % P)) {}
    42.     int val() const {
    43.         return x;
    44.     }
    45.     Mint operator-() const {
    46.         return Mint(Vnorm(P - x));
    47.     }
    48.     Mint inv() const {
    49.         assert(x != 0);
    50.         return power(*this, P - 2);
    51.     }
    52.     Mint &operator*=(const Mint &rhs) {
    53.         x = i64(x) * rhs.x % P;
    54.         return *this;
    55.     }
    56.     Mint &operator+=(const Mint &rhs) {
    57.         x = Vnorm(x + rhs.x);
    58.         return *this;
    59.     }
    60.     Mint &operator-=(const Mint &rhs) {
    61.         x = Vnorm(x - rhs.x);
    62.         return *this;
    63.     }
    64.     Mint &operator/=(const Mint &rhs) {
    65.         return *this *= rhs.inv();
    66.     }
    67.     friend Mint operator*(const Mint &lhs, const Mint &rhs) {
    68.         Mint res = lhs;
    69.         res *= rhs;
    70.         return res;
    71.     }
    72.     friend Mint operator+(const Mint &lhs, const Mint &rhs) {
    73.         Mint res = lhs;
    74.         res += rhs;
    75.         return res;
    76.     }
    77.     friend Mint operator-(const Mint &lhs, const Mint &rhs) {
    78.         Mint res = lhs;
    79.         res -= rhs;
    80.         return res;
    81.     }
    82.     friend Mint operator/(const Mint &lhs, const Mint &rhs) {
    83.         Mint res = lhs;
    84.         res /= rhs;
    85.         return res;
    86.     }
    87.     friend std::istream &operator>>(std::istream &is, Mint &a) {
    88.         i64 v;
    89.         is >> v;
    90.         a = Mint(v);
    91.         return is;
    92.     }
    93.     friend std::ostream &operator<<(std::ostream &os, const Mint &a) {
    94.         return os << a.val();
    95.     }
    96. };
    97.  
    98. void solve()
    99. {
    100.     int n,k;
    101.     cin >> n >> k;
    102.     vector> dp(k + 1,vector(n + 1));
    103.     rep(i,1,k) dp[i][0] = 1;
    104.     rep(i,1,k) {
    105.         rep(j,1,n) {
    106.             dp[i][j] += dp[i - 1][n - j] + dp[i][j - 1];
    107.         }
    108.     }
    109.     cout << dp[k][n] << '\n';
    110. }
    111. int main()
    112. {
    113.     ios::sync_with_stdio(false);
    114.     cin.tie(0),cout.tie(0);
    115.     int T = 1;
    116.     cin >> T;
    117.     while(T --) solve();
    118.     return 0;
    119. }

    4.Problem - D - Codeforces

            （1）题意

                    你有n个活动事件，m个位置，初始在0这个位置，每一次活动给出Ti,Xi,Yi表示这个活动的类型是Ti，每一次步长为Xi'(Xi = Xi'/100000)，可以执行[0,Yi]次这个步长，若Ti为1或2，若Ti为1，则表示这一次会变成pos = (pos + Xi),若Ti为2，则表示这一次会变成pos = (pos * Xi), 问你最早到达[1,m]每一个位置是第几个活动事件。

            （2）思路

                    直接暴力即可，记Ans[i]表示到第i个位置的最早时间，若这个位置被走过了则时间可以不执行了，若当前位置已经跳出m了，则也不执行了。

            （3）代码

    1. #include 
    2. #define rep(i,z,n) for(int i = z;i <= n; i++)
    3. #define per(i,n,z) for(int i = n;i >= z; i--)
    4. #define PII pair
    5. #define fi first
    6. #define se second
    7. #define vi vector
    8. #define vl vector
    9. #define pb push_back
    10. #define sz(x) (int)x.size()
    11. #define all(x) (x).begin(),(x).end()
    12. using namespace std;
    13. using ll = long long;
    14. const int N = 2e5 + 10;
    15. int Ans[N];
    16. const int inf = 0x3f3f3f3f;
    17. void solve()
    18. {
    19.     int n,m;
    20.     cin >> n >> m;
    21.     rep(i,1,m) Ans[i] = inf;
    22.     rep(i,1,n) {
    23.         ll t,x,y;
    24.         cin >> t >> x >> y;
    25.         per(j,m,0) {
    26.             if(Ans[j] == inf) continue;
    27.             ll p = j;
    28.             rep(k,1,y) {
    29.                 if(t == 1) p = p + (99999 + x) / 100000;
    30.                 else p = (p * x + 99999) / 100000;
    31.                 if(p > m) break;
    32.                 if(Ans[p] < inf) break;
    33.                 Ans[p] = i;
    34.             }
    35.         }
    36.     }
    37.     rep(i,1,m) {
    38.         if(Ans[i] == inf) cout << -1 << ' ';
    39.         else cout << Ans[i] << ' ';
    40.     }
    41. }   
    42. int main()
    43. {
    44.     ios::sync_with_stdio(false);
    45.     cin.tie(0),cout.tie(0);
    46.     int T = 1;
    47.     // cin >> T;
    48.     while(T --) solve();
    49.     return 0;
    50. }

    5.Problem - E - Codeforces

            （1）题意        （2）思路

                    考虑这个图是一个竞赛图，我们可以直接用竞赛图解，对于一个竞赛图若按照点的出度进行排序，缩点后前面的点必定向后面所有点右边，若某一个位置前面的点的出度和为i * (i - 1) / 2,说明前面必定出现了SCC，如果前面j个点也出现了这个情况，说明要么前i个点存在两个SCC，要么后面这个不存在SCC，证明可得后面这个也一定是SCC。那么我们只需要挑一个最大的SCC的|Ka-Kb|即可。

            （3）代码

    1. #include 
    2. #define rep(i,z,n) for(int i = z;i <= n; i++)
    3. #define per(i,n,z) for(int i = n;i >= z; i--)
    4. #define PII pair
    5. #define fi first
    6. #define se second
    7. #define vi vector
    8. #define vl vector
    9. #define pb push_back
    10. #define sz(x) (int)x.size()
    11. #define all(x) (x).begin(),(x).end()
    12. using namespace std;
    13. using ll = long long;
    14. const int N = 2e5 + 10;
    15. PII e[N];
    16. void solve()
    17. {
    18.     int n;
    19.     cin >> n;
    20.     rep(i,1,n) {
    21.         cin >> e[i].fi;
    22.         e[i].se = i;
    23.     }
    24.     stable_sort(e + 1,e + 1 + n);
    25.     int v = 0,mx = -1,lst = 0;
    26.     PII Ans = {0,0};
    27.     rep(i,1,n) {
    28.         v += e[i].fi;
    29.         if(v == i * (i - 1) / 2) {
    30.             if(lst != i - 1) {
    31.                 int rs = e[i].fi - e[lst + 1].fi;
    32.                 if(rs > mx) {
    33.                     Ans = {e[lst + 1].se,e[i].se};
    34.                     mx = rs;
    35.                 }
    36.             }
    37.             lst = i;
    38.         }
    39.     }
    40.     cout << "! " << Ans.fi << ' ' << Ans.se << endl;
    41. }
    42. int main()
    43. {
    44.     ios::sync_with_stdio(false);
    45.     cin.tie(0),cout.tie(0);
    46.     int T = 1;
    47.     // cin >> T;
    48.     while(T --) solve();
    49.     return 0;
    50. }

    6.Problem - F - Codeforces

            （1）题意

                    Alice和Bob在一颗树上玩游戏，第i个节点有a[i]个石头，每轮可以选择一个距离根深度至少为k的点往上移动任意石头，问对每个节点作为根最后谁会赢。

            （2）思路

                    对于k为1，无非就是一个树上阶梯尼姆博弈

                    对于k为d，我们猜测会是一个dep/d的树上阶梯尼姆博弈

                    因此我们考虑dp[i][j][k]表示在第i个点，距离i为j的，奇偶性为k的贡献是多少。

                    1.对于j < k的奇偶性不会发生变化

                            dp[x][i][j] ^= dp[y][i - 1][j]

                    2.对于j == k的会发生变化因此特殊转移就行。

                            dp[x][0][j] ^= dp[y][k - 1][j ^ 1]

                    剩下的其他根换根dp一下就可以

           （3）代码

    1. #include 
    2. #define rep(i,z,n) for(int i = z;i <= n; i++)
    3. #define per(i,n,z) for(int i = n;i >= z; i--)
    4. #define PII pair
    5. #define fi first
    6. #define se second
    7. #define vi vector
    8. #define vl vector
    9. #define pb push_back
    10. #define sz(x) (int)x.size()
    11. #define all(x) (x).begin(),(x).end()
    12. using namespace std;
    13. using ll = long long;
    14. const int N = 1e5 + 10;
    15. vector<int> e[N];
    16. int dp[N][21][2],Ans[N],a[N];
    17. int n,k;
    18. inline void do_dp(int x,int y)
    19. {
    20.     rep(i,1,k - 1) {
    21.         rep(j,0,1) {
    22.             dp[x][i][j] ^= dp[y][i - 1][j];
    23.         }
    24.     }
    25.     dp[x][0][0] ^= dp[y][k - 1][1];
    26.     dp[x][0][1] ^= dp[y][k - 1][0];
    27. }
    28. inline void dfs(int u,int f)
    29. {
    30.     dp[u][0][0] = a[u];
    31.     for(auto v : e[u]) {
    32.         if(v == f) continue;
    33.         dfs(v,u);
    34.         do_dp(u,v);
    35.     }
    36. }
    37. inline void dfs2(int u,int f)
    38. {
    39.     if(f) {
    40.         do_dp(f,u);
    41.         do_dp(u,f);
    42.     }
    43.     rep(i,0,k - 1) Ans[u] ^= dp[u][i][1];
    44.     for(auto v : e[u]) {
    45.         if(v == f) continue;
    46.         dfs2(v,u);
    47.     }
    48.     if(f) {
    49.         do_dp(u,f);
    50.         do_dp(f,u);
    51.     }
    52. }
    53. void solve()
    54. {
    55.     cin >> n >> k;
    56.     rep(i,2,n) {
    57.         int u,v;
    58.         cin >> u >> v;
    59.         e[u].pb(v),e[v].pb(u);
    60.     }
    61.     rep(i,1,n) cin >> a[i];
    62.     dfs(1,0);
    63.     dfs2(1,0);
    64.     rep(i,1,n) {
    65.         if(Ans[i]) cout << 1 << ' ';
    66.         else cout << 0 << ' ';
    67.     }
    68. }
    69. int main()
    70. {
    71.     ios::sync_with_stdio(false);
    72.     cin.tie(0),cout.tie(0);
    73.     int T = 1;
    74.     // cin >> T;
    75.     while(T --) solve();
    76.     return 0;
    77. }

                    

  • 相关阅读:
    Windows10/11 缩放与布局自定义
    Redis
    全网最全最深：web前端架构师面试题+缜密全面的学习笔记
    毕业论文Word文档中排版各种问题（持续更新中）
    ConfigMaps in K8s
    Numpy切片操作
    Java 泛型 T，E，K，V，?
    使用Docker部署Jenkins
    小程序优化：第三方SDK过大解决方案
    冷热电气多能互补的微能源网鲁棒优化调度(Matlab代码实现）
  • 原文地址：https://blog.csdn.net/scanner___yw/article/details/133493512