2022杭电第二场

1002 C++ to Python
1007 Snatch Groceries
1012 Luxury cruise ship

1002 C++ to Python

题意+思路：

用C读元组将std::make_tuple里所有字符都忽略。其他都正常输出即可

代码：

using namespace std;
int t;
string s;
int main(){
	cin>>t;
	while(t--){
		cin>>s;
		for(int i=0;i<s.size();i++){
			if(s[i]!='s'&&s[i]!='t'&&s[i]!=':'&&s[i]!='_'&&s[i]!='d'&&s[i]!='m'&&s[i]!='a'&&s[i]!='k'&&s[i]!='e'&&s[i]!='u'&&s[i]!='p'&&s[i]!='l'&&s[i]!='e')
			cout<<s[i];
		}
		cout<<endl;
	}
}

1007 Snatch Groceries

题意:

读取n个区间，求出第一次出现区间重合前的区间数。

思路：

算是阅读题，要注意到区间重合时服务器会炸裂，后面的就不用考虑了。直接sort排序即可，有相交的情况即终止。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =1e6+10;
struct node{
	int l,r,f;
}a[N];
int n;
bool cmp(node x,node y){
	if(x.l!=y.l) return x.l<y.l;
	return x.r>y.r;
}

inline void solve(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
    	scanf("%d%d",&a[i].l,&a[i].r);
    	a[i].f=0;
	}
	sort(a,a+n,cmp);
	int x=a[0].r;
	int pos=n;
	for(int i=1;i<n;i++){
		if(a[i].l<=x){
			a[i-1].f=1;
			a[i].f=1;
			pos=i;
			break;
		}
		x=max(x,a[i].r);
	}
	int ans=0;
	for(int i=0;i<pos;i++){
		if(a[i].f==0) {
			ans++;
		} 
	}
	printf("%d\n",ans);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	scanf("%d",&t);
	while(t--){
		solve();
	}
	return 0;
}

1012 Luxury cruise ship

题意：

有三种硬币，请问恰好付款m用的最少的硬币数。

思路：

可以看做完全背包，背包容量很大1e18,考虑贪心，把一大部分的体积都交给体积最大的那个物体，其余容积用完全背包解决即可。

代码：

#include <iostream>
#include <map>
#include <algorithm>
#include <set>
#include <cstring>
#include <queue>
#define N 10000010
using namespace std;
#define int long long
#define INF 1000000000
int f[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t, n;
    cin >> t;
    for (int i = 0; i < N; i++)
    {
        f[i] = INF;
    }
    f[0] = 0;
    int v[3] = {7, 31, 365};
    for (int i = 0; i < 3; i++)
    {
        for (int j = v[i]; j <= 10000000; j++)
            f[j] = min(f[j], f[j - v[i]] + 1);
    }

    
    while (t--)
    {
        cin >> n;
        int u = n / 79205;
        long long temp = 0;
        if (n > N)
            temp = (n - N) / 365 + 1;
        n -= temp * 365;
        cout << temp + f[n] << endl;
    }
    return 0;
}