🈲抄袭 🈲抄袭🈲抄袭 🈲抄袭🈲抄袭🈲抄袭 🈲抄袭🈲抄袭🈲抄袭🈲抄袭 🈲抄袭🈲抄袭🈲抄袭🈲抄袭🈲抄袭 🈲抄袭🈲抄袭🈲抄袭🈲抄袭🈲抄袭🈲抄袭

Day 2总结

T1 神秘金币

题目描述：

在一个古老的文明中，有一种神秘的金币。你是一名考古学家，偶然发现了这个文明的遗址，现在是时刻0，有n枚金币同时被发现。第 i枚金币会在t_i时刻后消失，它的价值是v_i。 然而，由于地形和其他条件的限制，你每个时刻只能收集一枚金币。此外，你的背包有限，你最多只能收集k枚金币。现在，你面前有n枚金币，你的任务是确定如何选择金币，以便在收集的金币数量不超过k的前提下，最大化你可以获取的金币价值总和。 注意：金币被收集到背包之后就不会消失了。

数据范围：n<=10⁵，1<=k<=n，v_i<=10⁶。

总结：

贪心题，比较简单，只用考虑价值，不用考虑时间，只给价值排序，往背包里放k个即可。

先排除废物信息t_i，输入完后，将v_i排序然后求和

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct node{
    int t;
    int v;
};
node a[N];
int n,k;
long long ans;
bool cmp(node a,node b){
    return a.v>b.v;
}
int main(){
    freopen("coin.in", "r", stdin);
    freopen("coin.out", "w", stdout);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i].t;
    for(int i=1;i<=n;i++) cin>>a[i].v;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=k;i++){
        ans+=a[i].v;
    }
    cout<<ans;
    return 0;
}

T2 学习乘法

题目描述：

牛牛上小学二年级了，现在他开始学习乘法。经过老师的悉心教导，牛牛已经能够算出 a, b 两个数字的乘积了。结果老师发现，牛牛是偷偷拿到了老师的练习题答案，背下答案之后才说对了乘积！ 老师非常愤怒，决定给牛牛出更多的乘法题目，现在老师打算对 a, b 这两个数字的数位进行交换，这样就可以构造出新的数字来考牛牛乘法了。 例如原来的两个数字 a, b 是 1234 和 5678，那么他可以交换两个数字的千位，使得两个数字变成 5234 和 1678，然后再计算它们的乘积。 老师只会交换相同位置的数位，例如交换两个数字的千位，或者交换两个数字的百位，但是不能交换一个数字的千位和另一个数字的百位（例如交换出 6234 和 5178 是不被允许的）。 老师可以进行无限次交换操作最终得到新的数字a₁, b₁，请问新的两个数字的乘积最大是多少。

数据范围：a,b<=999999。

总结：

当两个数的和一定时，这两个数的差越小，它们的乘积就越大。

思路：

1.确保大的数在前，小的数在后（方便下一步操作）。

2.找到两个数不相同的第一个位置。

3.从这个位置的下一个开始，如果大的数的其中一位比小的数大，那么交换（使这两个数的差距尽量小）。

4.计算乘积（注意数据类型）。

代码：

#include<bits/stdc++.h>
using namespace std;
long long max;
bool cmp(string a,string b){
	return a>b;
}
int f(string a,string b){
	int idx=0;
	int len=a.size();
	for(int i=0;i<len;i++){
		if(a[i]!=b[i]){
			idx=i;
			break;
		}
	}
	return idx+1;
}
int main(){
	freopen("mul.in","r",stdin);
	freopen("mul.out","w",stdout);
	string a,b;
	cin>>a>>b;
	if(!cmp(a,b)) swap(a,b);
	int len=a.size();
	int idx=f(a,b);
	for(int i=idx;i<len;i++){
		if(a[i]>b[i]) swap(a[i],b[i]);
	}
	long long n=0,m=0;
	for(int i=0;i<len;i++){
        n=n*10+a[i]-'0';
		m=m*10+b[i]-'0';
	}
	cout<<n*m;
	return 0;
}

T3 饮料难题

题目描述：

牛牛因为数学太差被老师赶出教室了，虽然老师侵犯了牛牛的公平教育权，但是牛牛在教室外的小卖部大彻大悟，提升了自己的数学水平。 故事是这样的：学校里的小卖部里有一个活动：只要有三个饮料瓶就可以换一瓶新的饮料。 现在牛牛从路边捡到了10个饮料瓶，于是牛牛开始兑换饮料。他的兑换操作如下： 先用 9个饮料瓶换3瓶饮料，喝完。 然后手里有4个饮料瓶，再拿出3个换1瓶饮料，这时手里有2个饮料瓶。 牛牛再问老板借1瓶饮料，喝完之后又多了1个饮料瓶，然后拿3个饮料瓶换1瓶饮料还给老板。 有借有还，再借不难。在这个过程中，牛牛总共喝了5瓶饮料。 牛牛现在有n个饮料瓶，小卖部的活动是每k个饮料瓶能换一瓶饮料，牛牛最多能喝几瓶饮料？ 牛牛已经大彻大悟，现在他拿这道题来考你，他希望你和他一样大彻大悟。

数据范围：k<=10¹⁸，n<=10¹⁰⁰⁰⁰⁰。

总结：

这个题首先不能硬算，要找公式，因为数据范围太大了。

公式：n/(k-1)

重点是高精度算法，这个一定要记牢。 但主要错误原因是因为没有推出公式

代码：

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

vector<int> v1;

vector<int> div(vector<int> a, int b){
	vector<int> res;
	int t=0;
	int r=0;
    int len=a.size()-1;
	for(int i=len;i>=0;i--){
		t=r*10+a[i];
		res.push_back(t/b);
		r=t%b;
	}
	reverse(res.begin(),res.end());
    while(res.size()>1 && res.back()==0) res.pop_back();
	return res;
}

signed main(){
    freopen("drink.in","r",stdin);
    freopen("drink.out","w",stdout);
	string n;
    cin>>n;
    int k;
    cin>>k;
	int len=n.size();
	for(int i=len-1;i>=0;i--)
		v1.push_back(n[i]-'0');
	auto C=div(v1, k-1);
	int len2=C.size();
	for(int i=len2-1;i>=0;i--){
		cout << C[i];
	}
	return 0;
}

T4 手术

题目描述：

在上一题中，牛牛喝了 10¹⁰⁰⁰⁰⁰ 数量级的饮料，他得了一个需要去医院动手术的大病——蛀牙。 但是和他一起去医院的总共有n名患者。而这家医院只有一个医生和床位，所以只能同时给一个人做手术。每个人有一个病情严重度 p_i，保证所有人的严重度均不同，严重度越小说明所剩寿命越短，病情越紧急。 第 i 名患者到达时间是 t_i，治病后会向医生付款 a_i 个金币，手术时长是 b_i。>假设第 x个单位时间开始手术，则第 x+b_i-1个单位时间结束手术，医生在第x+b_i个单位时间及以后才能接待别的患者。手术过程不能中断。 患者到达医院之后可以不手术，先等待医生的通知（无论此时床位是否空闲），通知之后才进行手术。 如果一个患者发现医院里有一个病情严重度比自己轻微的患者正在手术而自己还没有进行手术，则他会开始医闹。医生不想让医闹发生，问他第 k个单位时间结束后能收获金币的最大值。

数据范围：n<=10⁵，t_i，a_i，b_i，k<=10⁹。

总结：

无（因为不会）

代码：

#include<bits/stdc++.h>
using namespace std ;
int main() 
{
	freopen("op.in", "r", stdin);
	freopen("op.out", "w", stdout);

    int n , k ;
    cin >> n >> k ;
    vector<int> p(n + 1 , 0) ;    
    vector<int> t(n + 1 , 0) ;    
    vector<int> a(n + 1 , 0) ;    
    vector<int> b(n + 1 , 0) ;    
    for(int i = 1 ; i <= n ; i ++)  cin >> p[i] ;
    for(int i = 1 ; i <= n ; i ++)  cin >> t[i] ;
    for(int i = 1 ; i <= n ; i ++)  cin >> a[i] ;
    for(int i = 1 ; i <= n ; i ++)  cin >> b[i] ;
    vector<int> id(n + 1 , 0) ;
    for(int i = 1 ; i <= n ; i ++)  id[i] = i ;
    sort(id.begin() + 1 , id.end() , [&](int x , int y)
    {
        return p[x] < p[y] ;
    }) ;
    set<pair<int , int>> s ;
    s.insert({1 , k}) ;
    long long res = 0 ;
    for(int i = 1 ; i <= n ; i ++)
    {
        int c = id[i] ;
        if(s.empty())  break ;
        auto it = s.lower_bound({t[c] , 0}) ;
        auto it2 = it ;
        if(it2 != s.begin())  it2 -- ;
        if(it2 -> first <= t[c] && t[c] <= it2 -> second)  it = it2 ;
        if(it != s.end())
        {
            t[c] = max(t[c] , it -> first) ;
            if(t[c] <= it -> second)
            {
                if(it -> first < t[c])
                {
                    int l = it -> first ;
                    int r = it -> second ;
                    s.erase({l , r}) ;
                    s.insert({l , t[c] - 1}) ;
                    s.insert({t[c] , r}) ;
                    it = s.lower_bound({t[c] , 0}) ;
                }
                vector<pair<int , int>> v ;
                while(it != s.end())
                {
                    int l = it -> first ;
                    int r = it -> second ;
                    if(r - l + 1 >= b[c])
                    {
                        res += a[c] ;
                        s.erase(it) ;
                        if(r - l + 1 > b[c])  s.insert({l + b[c] , r}) ;
                        break ;
                    }
                    else
                    {
                        v.push_back({l , r}) ;
                        it ++ ;
                    }
                }
                for(auto now : v)  s.erase(now) ;
            }
        }
    }
    cout << res  ;

    return 0 ;
}