首页 > 其他分享 >Contest3376 - 2024寒假集训-排位赛竞赛（一）

Contest3376 - 2024寒假集训-排位赛竞赛（一）

时间：2024-01-19 18:00:42浏览次数：23  
标签：Contest3376 int 排位赛 cin 2024 ans tie dp define

A: 幂位和

高精度。

用高精度加法或乘法算出\(2^{1000}\)，再将各位累加即为答案。

#include <bits/stdc++.h>

using namespace std;

#define cctie ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

string AP_add(string A, string B) // 高精度加法
{
    int lena = A.size(), lenb = B.size(), lenc = max(lena, lenb) + 1;
    reverse(A.begin(), A.end()); reverse(B.begin(), B.end());
    vector<int> a(lenc), b(lenc), c(lenc);
    for (int i = 0; i < lena; i++) a[i] = A[i] - '0';
    for (int i = 0; i < lenb; i++) b[i] = B[i] - '0';
    int x = 0;
    for (int i = 0; i < lenc; i++)
    {
        c[i] = a[i] + b[i] + x;
        x = c[i] / 10;
        c[i] %= 10;
    }
    while (c.back() == 0 && c.size() > 1) c.pop_back();
    string C = "";
    for (auto i : c) C += i + '0';
    reverse(C.begin(), C.end());
    return C;
}

int main()
{
	cctie;
	
	string s = "1";
	for (int i = 1; i <= 1000; i++) s = AP_add(s, s);

	int ans = 0;
	for (auto i : s) ans += i - '0'; // 各位累加
	cout << ans << '\n';

	return 0;
}

B: 三角形数

质因数分解/试除法。

对某数质因数分解后，将各个次幂的指数累乘即为该数的约数个数（试除法也行，较慢一些），按要求循环直到找到约数个数大于\(500\)的数即可。

#include <bits/stdc++.h>

using namespace std;

#define cctie ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

int get(int n) // 求n的约数个数
{
    int ans = 1;
    for (int i = 2; i <= n / i; i++)
    {
        int cnt = 0;
        while (n % i == 0)
            n /= i, cnt++;
        ans *= cnt + 1;
    }
    if (n > 1) ans *= 2;
    return ans;
}

int main()
{
	cctie;
    
    int k = 1;
	for (int i = 1; ; i += ++k)
    {
        if (get(i) > 500) // 找到目标数
        {
            cout << i << '\n';
            break;
        }
    }

	return 0;
}

C: 生日蛋糕

搜索、剪枝、后缀和。

所求表面积即为第一层蛋糕的下表面积（相当于每一层蛋糕上表面外露面积之和）与每层蛋糕的侧面积之和。

主要对\(dfs\)中的四个剪枝分析。

  1. \(V<minV[u]\)。剩余体积不足以按要求设计出第\(u\)层及以上的蛋糕。

  2. \(S + minS[u] >= ans\)。即使能够按要求设计出剩余层数的蛋糕但也无法更新答案。

  3. \(S + 2 * \frac{V}{R[u - 1]} >= ans\)。最重要的剪枝，推导如下（忽略所有\(\pi\)）。

    记第\(1\)层到第\(u-1\)层的侧面积和第一层的下表面积为\(S\)，第\(u\)层到第\(m\)层的侧面积为\(S'=\sum_{i=u}^{m}2R_iH_i=\frac{2}{R_{u-1}}\sum_{i=u}^{m}R_{u-1}R_iH_i\)；

    由\(R_{u-1}>R_{u}>R_{u+1}>...>R_m\)得\(S'>=\frac{2}{R_{u-1}}\sum_{i=u}^{m}R_i^2H_i\)（当且仅当\(u=m+1\)时取得等号）；

    由\(V=\sum_{i=u}^{m}R_i^2H_i\)得\(S'\geq\frac{2}{R_{u-1}}V\)；

    当\(S+S'>=S + 2 * \frac{V}{R[u - 1]}>=ans\)时无法更新答案（道理同\(2\)）。

  4. \(for\)循环中\(r\)和\(h\)的取值范围。由每一层的\(r\)和\(h\)都是正整数且都比上一层的\(r\)和\(h\)的大得到下界，由第\(u\)层的体积最大值\(V-minV[u+1]\)和该层的高的最小值确定\(r\)的上界，\(h\)的值随\(r\)而确定。

#include <bits/stdc++.h>

using namespace std;

#define cctie ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

const int N = 30, INF = 0x3f3f3f3f; // INF表示一个极大的值（本题答案无法达到，用于判断是否有答案）

int n, m;
int minV[N], minS[N]; // minV[i]、minS[i]分别表示第i层及以上部分构成的最小体积、表面积
int R[N], H[N]; // R[i]、H[i]表示当前第i层蛋糕的半径和高度
int ans = INF; 

void dfs(int u, int V, int S) // 搜索，表示考虑第u层蛋糕，剩余体积为V，已有蛋糕的表面积为S
{
    if (V < minV[u]) return;
    if (S + minS[u] >= ans) return;
    if (S + 2 * V / R[u - 1] >= ans) return;
    if (u == m + 1) // 搜索完m层蛋糕
    {
        if (V == 0) ans = S; // 更新答案
        return;
    }
    // 从大到小，先遍历r，后遍历h
    for (int r = min(R[u - 1] - 1, (int)sqrt((V - minV[u + 1]) / (m + 1 - u))); r >= m + 1 - u; r--) 
        for (int h = min(H[u - 1] - 1, (V - minV[u + 1]) / (r * r)); h >= m + 1 - u; h--)
        {
            R[u] = r, H[u] = h;
            dfs(u + 1, V - r * r * h, S + 2 * r * h + (u == 1) * r * r); // 第一层有额外的下表面积
        }
}

int main()
{
	cctie;
	
	cin >> n >> m;
    R[0] = H[0] = INF; // dfs中第三行if需要
    for (int i = m; i >= 1; i--) // 求后缀和
    {
        int j = m + 1 - i;
        minV[i] = minV[i + 1] + j * j * j;
        minS[i] = minS[i + 1] + 2 * j * j;
    }

    dfs(1, n, 0);

    if (ans == INF) ans = 0; // 没有搜索到可行解
    cout << ans << '\n';

	return 0;
}

D: 头疼的数列

动态规划。

\(dp[i][j]\)表示使序列的前\(i\)个数都变成\(j\)所需要的最少操作数，\(1\leq i\leq n\)，\(0\leq j \leq 1\)。

状态转移方程如下：

若\(a[i]=1\)，则\(dp[i][1]=\min(dp[i-1][1],dp[i-1][0]+1),dp[i][0]=\min(dp[i-1][0],dp[i-1][1])+1\)。

若\(a[i]=0\)，则\(dp[i][0]=\min(dp[i-1][0],dp[i-1][1]+1),dp[i][1]=\min(dp[i-1][1],dp[i-1][0])+1\)。

用异或运算\(\oplus\)可以合二为一，如下：

\(dp[i][a[i]] = min(dp[i - 1][a[i]],dp[i - 1][a[i]\oplus 1] + 1),dp[i][a[i] \oplus 1] = min(dp[i - 1][a[i] \oplus 1],dp[i - 1][a[i]]) + 1\)。

答案即为\(dp[n][0]\)。

时间复杂度：\(O(n)\)

#include <bits/stdc++.h>

using namespace std;

#define cctie ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

const int N = 100010, INF = 0x3f3f3f3f;

int n;
int a[N];
int dp[N][2];

int main()
{
	cctie;
	
	cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    dp[1][a[1]] = 0, dp[1][a[1] ^ 1] = 1;
    for (int i = 2; i <= n; i++)
    {
        dp[i][a[i]] = min(dp[i - 1][a[i]], dp[i - 1][a[i] ^ 1] + 1);
        dp[i][a[i] ^ 1] = min(dp[i - 1][a[i] ^ 1], dp[i - 1][a[i]]) + 1;
    }
    cout << dp[n][0] << '\n';

	return 0;
}

E: 杨辉三角

模拟。

按题目要求即\(a[i][j]= a[i - 1][j - 1] + a[i - 1][j]\)构造出杨辉三角，再按题目要求的格式输出即可。

#include <bits/stdc++.h>
 
using namespace std;
 
#define cctie ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define i64 long long 
#define double long double 
#define PII pair<int, int>
 
const int N = 1010;
 
int n;
int a[N][N];
 
int get(int x) // 求x的宽度
{
    int cnt = 0;
    while (x) cnt++, x /= 10;
    return cnt;
}
 
void solve()
{
    int mx = 0; // 最大值
    for (int j = 1; j <= n; j++)
        mx = max(mx, a[n][j]);
    int cnt = get(mx); // 最大数的宽度
    for (int i = 1; i <= n; i++)
    {
        cout << a[i][1];
        for (int j = 2; j <= i; j++)
            cout << setw(cnt + 1) << a[i][j]; // 按要求格式输出
        cout << '\n';
    }
    cout << '\n';
}
 
int main()
{
    cctie;
    a[1][1] = 1;
    for (int i = 2; i <= 30; i++)
        for (int j = 1; j <= i; j++)
            a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
    while (cin >> n) solve();
 
    return 0;
}

F: 头疼的花匠

树状数组/线段树、离散化、排序、离线询问。

对每朵花和询问的点的坐标按x的大小分别排序（升序），我们依次求排序后的每个询问，不妨设当前处理的询问的点的横坐标为\(x\)，纵坐标为\(y\)，则只需要求所有横坐标不大于\(x\)的花中纵坐标不大于\(y\)的有几朵，此处需要借助树状数组或线段树实现单点修改和区间查询，我们遍历排序后的每朵花，只要当前花的横坐标不大于x，就在树状数组中标记该花的纵坐标出现次数加一，而对于之前处理询问过程中已经标记过的点不需要重复遍历。这样处理每朵花只会被标记一次，每个询问处理也只有一次区间查询。

时间复杂度：\(O((n + q)log(n+q))\)

#include <bits/stdc++.h>
 
using namespace std;
 
#define cctie ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define PII pair<int, int>
 
const int N = 100010, INF = 0x3f3f3f3f, mod = 998244353;

template <typename T>
class Fenwick // 树状数组
{
private:
    int n;
    vector<T> c;
    int lowbit(int x) 
    {
        return x & -x;
    }
public:
    Fenwick(int n) : n(n - 1), c(n) {}
    
    void add(int k, T x) // 单点修改
    {
        for (int i = k; i <= n; i += lowbit(i)) c[i] += x;
    }
    
    T sum(int k) // 区间查询
    {
        T sum = T();
        for (int i = k; i; i -= lowbit(i)) sum += c[i];
        return sum;
    }
};

int n, q;
PII a[N], b[N];
int order[N];
int ans[N];

int main()
{
    cctie;
    
    cin >> n >> q;
    vector<int> v(1);
    for (int i = 1; i <= n; i++)
    {
        int x, y; cin >> x >> y;
        a[i] = {x, y};
        v.push_back(y);
    }
    for (int i = 1; i <= q; i++)
    {
        int x, y; cin >> x >> y;
        b[i] = {x, y};
        v.push_back(y);
    }

    sort(v.begin() + 1, v.end());
    v.erase(unique(v.begin() + 1, v.end()), v.end()); // 离散化

    sort(a + 1, a + n + 1);
    iota(order + 1, order + q + 1, 1);
    sort(order + 1, order + q + 1, [&](int i, int j)
    {return b[i] < b[j];});

    auto get = [&](int x)->int
    {
        return lower_bound(v.begin() + 1, v.end(), x) - v.begin();
    }; // 求离散化后的值

    Fenwick<int> F(v.size());
    int now = 1;
    for (int i = 1; i <= q; i++)
    {
        int j = order[i];
        while (now <= n && a[now].first <= b[j].first) F.add(get(a[now++].second), 1); // 标记纵坐标
        ans[j] = F.sum(get(b[j].second)); // 处理询问
    }

    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';

    return 0;
}

G: 货仓选址

数学。

经典数学问题，货仓建在中位数即可。

时间复杂度：\(O(nlogn)\)

#include <bits/stdc++.h>

using namespace std;

#define cctie ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define i64 long long
 
const int N = 100010, INF = 0x3f3f3f3f;

int n;
int a[N];

int main()
{
    cctie;
    
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    int k = n + 1 >> 1; // 求中位数下标
    i64 ans = 0;
    for (int i = 1; i <= n; i++) ans += abs(a[i] - a[k]);
    
    cout << ans << '\n';
    
    return 0;
}

H: 进阶杨辉三角

模拟。

其实就是将\(E\)题里的杨辉三角按顺序存放到一维数组里，然后求第\(k\)个数直接输出即可，注意取模。

#include <bits/stdc++.h>
 
using namespace std;
 
#define cctie ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define i64 long long 
 
const int N = 1010, mod = 1e9 + 7;
 
i64 a[N][N];
vector<i64> v(2, 1);
 
void solve()
{
    int k; cin >> k;
    cout << v[k] << '\n';
}
 
int main()
{
    cctie;
    a[1][1] = 1;
    for (int i = 2; ; i++)
    {
        if (v.size() - 1 >= 50000) break;
        for (int j = 1; j <= i; j++)
        {
            if (v.size() - 1 >= 50000) break;
            a[i][j] = (a[i - 1][j - 1] + a[i - 1][j]) % mod;
            v.push_back(a[i][j]); // 存放到一维数组
        }
    }
    int t; cin >> t;
    while (t--) solve();
 
    return 0;
}

I: 切面条

找规律。

将面条两端相接则成环（视为已对折一次），则一共对折\(n(n>0)\)次后切割能得到\(2^n\)根面条，而面条相较于环多了个开口，也就是切割后多了一根面条，所以答案为\(2^n+1\)。

#include <bits/stdc++.h>
 
using namespace std;
 
#define cctie ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
 
int n;
 
int main()
{
    cctie;
    cin >> n;
 
    cout << (1 << n) + 1 << '\n';
 
    return 0;
}

J: 进制转换

进制转换。

\(p\)进制数转\(q\)进制：先将\(p\)进制数转为十进制数，再将十进制数转为\(q\)进制数。

转换原理和过程略。

#include <bits/stdc++.h>
 
using namespace std;
 
#define cctie ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
 
int p, q;
string n;
 
string itoa1(int n, int m) // 十进制数n转m进制
{
    string ret = "";
    do
    {
        int t = n % m;
        if (0 <= t && t <= 9) ret += t + '0';
        else ret += t - 10 + 'A';
        n /= m;
    } 
    while(n);
    reverse(ret.begin(), ret.end());
    return ret;
}
 
int itoa2(string n, int m) // m进制数n转十进制
{
    int ret = 0, k = 1;
    while (n != "")
    {
        char c = n.back();
        n.pop_back();
        if (c >= 'A') ret += (c - 'A' + 10) * k;
        else ret += (c - '0') * k;
        k *= m;
    }
    return ret;
}
 
int main()
{
    cctie;
 
    cin >> p >> q >> n;
    cout << itoa1(itoa2(n, p), q) << '\n';
 
    return 0;
}

K: 超级杨辉三角

组合数学、乘法逆元。

题目要求所有满足条件\(\exists \{i,j\}, a_{i-1}<a_i,a_{j-1}>a_j\)的长度为\(n\)且每个数不大于\(k\)的序列个数\(C\)。直接求很困难，不妨先求其对立部分的序列个数记为\(B\)，再用长度为\(n\)且每个数不大于\(k\)的序列个数\(A\)减去\(B\)即为答案。显然与前面条件对立的序列即为单调序列（非严格），转而求长度为\(n\)且每个数不大于\(k\)的单调序列个数。

先求单调上升的序列个数。把序列的\(n\)个位置当作\(n\)个球，从\(1\)到\(k\)的\(k\)个数当作\(k\)个盒子（按升序摆放），则求单调上升的序列个数及等效于把\(n\)个球放到\(k\)个盒子里的放法个数（可以有空盒），这是经典组合数学问题。先手动将每个盒子放一个球，则问题转变为把\(n+k\)个球放到\(k\)个盒子里的放法个数（不能有空盒），用隔板法解决，在\(n+k-1\)个间隙里放\(k-1\)个隔板，答案即为\(C_{n+k-1}^{k-1}\)。

单调下降的序列个数显然同样也为\(C_{n+k-1}^{k-1}\)，由于与单调上升序列有所重合，重合部分为n个数相等的所有序列，一共\(k\)个。

则\(B=2C_{n+k-1}^{k-1}-k\)，再求\(A\)，显然\(A=k^n\)，则\(C=A-B=k^n -(2C_{n+k-1}^{k-1}-k)\)。

时间复杂度：\(O(\min(n, k))\)

#include <bits/stdc++.h>
 
using namespace std;
 
#define cctie ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define i64 long long
 
const int mod = 998244353;

i64 pow(i64 a, i64 b, i64 p = mod) // 快速幂
{
	i64 ans = 1 % p;
	while (b)
	{
		if (b & 1) ans = ans * a % p;
		b >>= 1;
		a = a * a % p;
	}
	return ans;
}

i64 C(i64 a, i64 b, i64 p = mod) // 求组合数
{
    if (b > a) return 0;
    if (b > a - b) b = a - b;
    i64 x = 1, y = 1;
    for (int i = 0; i < b; i++)
    {
        x = x * (a - i) % p;
        y = y * (b - i) % p;
    }
    return x * pow(y, p - 2) % p;
}

void solve()
{
    i64 n, k; cin >> n >> k;
    i64 ans = (pow(k, n) - ((2 * C(n + k - 1, k - 1) - k + mod) % mod) + mod) % mod;
    cout << ans << '\n';
}

int main()
{
    cctie;
    
    int t; cin >> t;
    while (t--) solve();

    return 0;
}

L: 数列的平方和

前缀和/尺取法。

本题要求出所有长度为\(m\)的区间和（每个数平方后）的最小值。

这里主要讲一下尺取法的写法，类似滑动窗口的思路，我们从左往右求每一个区间的和，\(i\)表示当前所维护区间的最右端，则当前需要维护的区间和为\(\sum_{j=i-m+1}^{i}\)，而上一个区间的和为\(\sum_{j=i-m}^{i-1}=now\)，可以得出当前区间的和为\(now-a[i-m]+a[i]\)，一直维护取最小值即可。

时间复杂度：\(O(n)\)

#include <bits/stdc++.h>
 
using namespace std;
 
#define cctie ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define i64 long long 
 
const int N = 100010, mod = 1e9 + 7;
 
int n, m;
int a[N];
 
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) 
    {
        cin >> a[i];
        a[i] *= a[i];
    }
    i64 ans = LLONG_MAX, now = 0;
    for (int i = 1; i <= n; i++)
    {
        now += a[i];
        if (i > m) now -= a[i - m];
        if (i >= m) ans = min(ans, now);
    }
    cout << ans << '\n';
}
 
int main()
{
    cctie;
 
    int T; cin >> T;
    while (T--) solve();
 
    return 0;
}

标签：Contest3376,int,排位赛,cin,2024,ans,tie,dp,define
From： https://www.cnblogs.com/xiojoy/p/17975288

相关文章

  • 2024.1.19
    9点26解决了一个第三方库require(xxxx)导致的vite4在build时报错Can'tfindvariable:requirehttps://github.com/vite-plugin/vite-plugin-commonjs《代码提取》三种等级，导出提取、函数提取和闭包提取。其中可以导出提取和闭包提取很有趣。其中导出提取解释了react-r......
  • 2024.1.18
    9：50公司《关于React组件组织和拆分。》几个思路，1）提取子组件以拆分视图，2）提取非视图逻辑到hooks，3）提取领域模型以封装逻辑。但也要注意别过度抽象，个人感觉文中的抽象有些过，线性的逻辑更适合阅读。https://martinfowler.com/articles/modularizing-react-apps.html《React中的......
  • Windows 10, version 22H2 (updated Jan 2024) 中文版、英文版下载
    Windows10,version22H2(updatedJan2024)中文版、英文版下载Windows1022H2企业版arm64x64请访问原文链接：https://sysin.org/blog/windows-10/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.orgWindows10更新历史记录Windows10,version22H2,alledit......
  • Windows 11 version 23H2 中文版、英文版 (x64、ARM64) 下载 (updated Jan 2024)
    Windows11version23H2中文版、英文版(x64、ARM64)下载(updatedJan2024)Windows11,version23H2，2024年1月更新请访问原文链接：https://sysin.org/blog/windows-11/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.orgWindows11目前版本所有的日期都按照I......
  • 经纬恒润4D成像毫米波雷达亮相 CES 2024
        在刚刚结束的CES2024上，经纬恒润联合以色列ArbeRobotics公司展出了基于Arbe芯片组方案的4D成像毫米波雷达LRR610。      经纬恒润自主研发的4D成像毫米波雷达LRR610，具备48发48收通道，在方位和俯仰向均具有高分辨能力，可以形成丰富的点云信息，甚至可以对目标......
  • Adobe InDesign 2024 v19.1 (macOS, Windows) - 版面设计和桌面出版软件
    AdobeInDesign2024v19.1(macOS,Windows)-版面设计和桌面出版软件Acrobat、AfterEffects、Animate、Audition、Bridge、CharacterAnimator、Dimension、Dreamweaver、Illustrator、InCopy、InDesign、LightroomClassic、MediaEncoder、Photoshop、PremierePro、Adob......
  • Adobe InCopy 2024 v19.1 (macOS, Windows) - 编写和副本编辑软件
    AdobeInCopy2024v19.1(macOS,Windows)-编写和副本编辑软件Acrobat、AfterEffects、Animate、Audition、Bridge、CharacterAnimator、Dimension、Dreamweaver、Illustrator、InCopy、InDesign、LightroomClassic、MediaEncoder、Photoshop、PremierePro、AdobeXD......
  • Nessus 10.6 Auto Installer for RHEL 9/AlmaLinux 9/Rocky Linux 9 (updated Jan 202
    Nessus10.6AutoInstallerforRHEL9/AlmaLinux9/RockyLinux9(updatedJan2024)发布Nessus试用版自动化安装程序，支持macOSSonoma、RHEL9和Ubuntu22.04请访问原文链接：https://sysin.org/blog/nessus-auto-install-for-rhel-9/，查看最新版。原创作品，转载请保留出处......
  • Nessus 10.6 Auto Installer for macOS Sonoma (updated Jan 2024)
    Nessus10.6AutoInstallerformacOSSonoma(updatedJan2024)发布Nessus试用版自动化安装程序，支持macOSSonoma、RHEL9和Ubuntu22.04请访问原文链接：https://sysin.org/blog/nessus-auto-install-for-macos/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.org......
  • Nessus 10.6 Auto Installer for Ubuntu 22.04 (updated Jan 2024)
    Nessus10.6AutoInstallerforUbuntu22.04(updatedJan2024)发布Nessus试用版自动化安装程序，支持macOSSonoma、RHEL9和Ubuntu22.04请访问原文链接：https://sysin.org/blog/nessus-auto-install-for-ubuntu/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.org......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99