9.13复赛总结

经验分享区
1

T1:用埃式筛加上模拟就行了，20分钟AC;
题解：

#include <bits/stdc++.h>  
#define int long long    
using namespace std;     
int n,f=1,ans,vis[105000];  // 变量定义

signed main(){ 
    cin>>n; 
	//埃式筛   
    // 外层循环，从1到n迭代
    for(int i=1;i<=n;i++){
        // 内层循环，寻找下一个未被标记的数
        for(int j=f+1;j<=105000;j++){
            if(vis[j]==0){  // 找到未被标记的数
                f=j;        // 更新f为当前找到的未被标记的数
                ans=ans+j*i; // 模拟，累加j*i到结果中
                
                // 标记当前数的所有倍数
                for(int k=j;k<=105000;k+=j){
                    vis[k]=1;  // 将j的所有倍数标记为已处理
                }
                break;  // 找到一个未被标记的数后，跳出内层循环
            }
        }
    }
    
    cout<<ans;  // 输出最终结果
    return 0; 
}

{\color[RGB]{255,255,255} 其实欧拉筛更快 }
T2:其实就是二分答案，但考试时写了一个有问题的模拟20pts;
题解：

#include <bits/stdc++.h>  
#define int long long   
using namespace std;     

int n, m;             
int a[100005];       
int o[100005];       
int ans;              

// 检查函数：判断当参数为x时，是否所有路程中共消耗天数不超过m
bool check(int x){
    int sum = 0;     
    
    // 遍历所有项目，计算每段路程在参数x下的消耗天数
    for(int i = 1; i <= n; i++){
        // 计算第i段距离需要走几天：
        sum = sum + ceil((double)a[i]/x*1.0) + o[i];
    }
    
    // 判断总天数是否不超过天数上限m
    return sum <= m;
}

signed main()
{
    cin >> n >> m;    
    memset(a, 0, sizeof(a));  
    
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> o[i];
    }
    
    // 二分查找的左边界和右边界
    int l = 1;          // 左边界设为1
    int r = 1e15;       // 右边界设为10^15（m的上限）
    
    // 二分查找过程
    while(l < r){
        int mid = (l + r) >> 1;  // 计算中间值，相当于(l + r)/2
        if(check(mid))           // 如果mid满足条件
            r = mid;             // 调整右边界为mid
        else                     // 如果mid不满足条件
            l = mid + 1;         // 调整左边界为mid+1
    }
    
    // 判断是否找到有效解
    if (r == 1e15) {
        cout << -1 << endl;      // 如果右边界仍为初始值，说明无解
    }
    else{
        cout << r << endl;       // 否则输出找到的最小满足条件的值
    }
    
    return 0; 
}

T3:双指针加模拟，考试时没模拟出来，写了个骗分代码，10pts;
题解：

#include <bits/stdc++.h>  
#define int long long   
using namespace std;    


pair<int, int> a[100005];  
int b[100005];          

// 函数f：检查是否可以构造满足条件的序列，并生成结果数组
// 参数n：元素个数
// 返回值：bool类型，表示是否可以构造满足条件的序列
bool f(int n)
{
    // 对数组a按数值从小到大排序（默认按pair的first值排序）
    sort(a + 1, a + n + 1);
    
    // 初始化双指针：l指向数组左端，r指向数组右端
    int l = 1, r = n, cnt = 0;  // cnt用于记录已经分配的正数数量
    
    // 从大到小遍历可能的数值i
    for (int i = n; i >= 1; i--)
    {
        // 尝试将较大的可用数值分配为正数i
        if (a[r].first - cnt == i)  // 检查当前最大未分配值减去已分配正数数量是否等于i
        {
            b[a[r].second] = i;  // 将数值i分配到原始位置
            r--;                 // 右指针左移，跳过已分配的元素
            cnt++;               // 已分配正数数量加1
        }
        // 如果无法分配正数，则尝试分配负数
        else if (a[l].first - cnt == 0)  // 检查当前最小未分配值减去已分配正数数量是否等于0
        {
            b[a[l].second] = -i;  // 将数值-i分配到原始位置
            l++;                  // 左指针右移，跳过已分配的元素
        }
        // 如果以上两种情况都不满足，则无法构造满足条件的序列
        else
        {
            return 0;  // 返回false表示无法构造
        }
    }
    
    return 1;  // 返回true表示成功构造满足条件的序列
}

signed main()
{
    int T;  
    cin >> T;
    
    while (T--)
    {
        int n;  
        cin >> n;
        

        for (int i = 1; i <= n; i++)
        {
            cin >> a[i].first;  
            a[i].second = i;  
        }
        
        // 调用函数f检查是否可以构造满足条件的序列
        int pp = f(n);
        
        if (pp)  
        {
            cout << "YES" << endl;  
            // 输出结果数组，按照原始顺序排列
            for (int i = 1; i <= n; i++)
            {
                cout << b[i] << " ";
            }
            cout << endl;
        }
        else  
        {
            cout << "NO" << endl;  
        }
    }
    
    return 0;  
}

T4:是个01背包加动规，考试时写了个模拟代码，但没考虑有些数据超long long，只拿了40pts，加了long long 90分:unamused_face:
题解：

#include <bits/stdc++.h>
#define int long long    
using namespace std;     

int n;                   
int a[100005];            
int b[100005];             
int c[100005];             
int dp[100005];         
int bb[100005];          

signed main()
{
    cin >> n;            
    int sum = 0;          
    
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i] >> c[i]; 
        sum += c[i];                  // 累加c[i]到sum
        // 计算bb[i] = max(0, (b[i] - a[i] + 1) / 2)
        // 这表示某种与a[i]和b[i]相关的代价计算
        bb[i] = max(0LL, (b[i] - a[i] + 1) / 2);
    }
    
    // 计算目标值m，为sum的一半向上取整
    int m = (sum + 1) / 2;
    
    // 将dp数组初始化为一个很大的值（表示不可达状态）
    memset(dp, 0x3f, sizeof(dp));  
    dp[0] = 0;  // 初始状态：容量为0时，代价为0
    
    // 动态规划主体部分，类似于0-1背包问题
    for (int i = 1; i <= n; i++) 
    {
        // 逆序遍历容量，避免重复选择同一项目
        for (int j = m; j >= 0; j--)
        {
            int k;  
            
            // 判断当前容量j是否足够容纳当前部落的子民c[i]
            if (j >= c[i])
            {
                k = j - c[i];  // 如果足够，前一个状态为j - c[i]
            }
            else
            {
                k = 0;  // 如果不够，前一个状态为0
            }
            
            // 如果前一个状态可达（
            if (dp[k] != 0x3f3f3f3f3f3f3f3f)
            {
                // 更新当前状态的最小代价
                dp[j] = min(dp[j], dp[k] + bb[i]);
            }
        }
    }
    
    // 输出达到目标容量m所需的最小代价
    cout << dp[m] << endl;
    return 0;  
}

共计170pts，预计200，还阔以。

1 个赞