C猪猪养成计划1#

题目描述#

1.从l->r，与没有玩耍过的猪猪玩耍，标记是第几个玩耍的猪，并标记已玩耍 2.对编号为x的猪猪输出是第几个和Tobo玩耍的猪，没有玩耍过则为0

思路#

考场思路：建两个数组，一个存储是第几个玩耍的猪，一个用于标记是否玩耍过但n,q都是最大10的五次方，操作时l,r会重复多次扫描已经标记过的猪，时间复杂度太高解法一：想到要去掉已经扫描过的猪，让下次不会再扫描。可以用set维护，已经玩耍过后从set中删去

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

int tot;
set<int> st;
int b[200010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    for(int i = 1;i<=n;i++)
        st.insert(i);
    while(q--){
        int op;
        cin>>op;
        if(op == 1){
            int l,r;
            cin>>l>>r;
            auto it = st.lowr_bound(l);
            while(it ! =st.end() && *it <= r){
		        b[*it] = ++tot;
		        it = st.erase(it);
            }
        }
        else{
            int x;
            cin>>x;
            cout<<b[x]<<endl;
        }
    }
    return 0;
}

cpp

D猪猪养成计划2#

题目描述#

Tobo 养了 n 只猪猪，但是 Tobo 为了不让它们吃醋，所以一视同仁不管陪哪只猪猪都只陪 m 天。
现在第i只猪猪有个要求，要 Tobo 第 $a_i$ 天去陪它，即需要从第 $a_i$ 天陪到第 $a_{i+m-1}$ 天。然而，因为 Tobo 精力有限，一天只能陪一只猪猪，显然 Tobo 大概率不能陪伴他的每只猪猪。
如果不陪第 iii 只猪猪，就要给它买 $val_i$ 价值的礼物来补偿它；反之，如果陪它，就要花费 $b_i$ 的精力。
现在 Tobo 需要做一个抉择来选择陪的猪猪来使得花费的金钱与精力之和最少。他想知道这个最小值是多少。

思路#

如果陪0只猪，那么总的金钱和精力和为 $\sum_{1}^{n}val_i$ ,如果陪第i只猪那么金钱和精力和为 $\sum_{1}^{n}val_i-val_i+b_i$ 可以看到我们要求b-val的最小值，可以用dp求

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

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int n,m;
    cin>>n>>m;
	long long a[100010][3];
    vector<vector<long long>> c(n+10);
    long long res = 0;
    for(int i = 1;i<=n;i++) cin>>a[i][0];
    for(int i = 1;i<=n;i++) cin>>a[i][1]>>a[i][2],res+=a[i][2];
    for(int i = 1;i<=n;i++) c[a[i][0]].push_back(a[i][1] - a[i][2]);//插入b-val
    long long dp[n+10];
    memset(dp,0x7f,sizeof dp);//注意不能用1e18赋值，1e18为浮点数
    dp[0] = 0;//按照天数动态规划，第0天为0
    //定义：第i天的最小的b-val
    for(int i = 0;i<=n;i++)
    {
        long long ci = 0x7f;
        for(auto x : c[i]) dp[i+m] = min(dp[i+m],dp[i]+x);
        dp[i+1] = min(dp[i+1],dp[i]);
    }
    cout<<res+dp[n+1]<<endl;
	return 0;
}

cpp

Emin25筛 #

思路#

可以看到如果是暴力的话时间复杂度是 $O(n^2)$ ，太慢！观察到 $5*5=25$ ，可以转化为模5的奇数个和偶数个,可以存储前缀积, $a_i*a_{i+1}**……*a_j = sum_j/sum_{i-1}$ 可以从后往前枚举左端点，用 $num_0$ 和 $num1$ 分别表示左端点右边5因子奇偶的和，按照对应的公式计算即可。 注意除法容易造成精度问题，可以用除法逆元, $b^{-1}=b^{(p-2)} mod p$

代码#

int n;
	cin>>n;
	vector<int> a(n+1),cnt(n+1);
	vector<long long> sum(n+1),num(2,0);
	vector<long long> pre(n+1);
	sum[0] = 1;
	for(int i = 1;i<=n;i++)
	{
		cin>>a[i];
		while(a[i]%5==0){
			a[i]/=5;
			cnt[i]++;
		}
		cnt[i]%=2;
	}
	for(int i = 1;i<=n;i++){
		sum[i] = sum[i-1]*a[i];
		pre[i] = (pre[i-1]+cnt[i])%2;
	}

	long long ans = 0;
	for(int i = n;i>=0;i--)
	{
        ans = (ans + num[pre[i]] * ksm(sum[i],mod-2) % mod) % mod;
        ans = (ans + num[pre[i] ^ 1] *ksm(sum[i],mod-2) %mod *  5 % mod) % mod;
        num[pre[i]] += sum[i];
        num[pre[i]] %= mod;
	}
	cout<<ans<<endl;

cpp

牛客小白月赛109补题

C猪猪养成计划1#

题目描述#

思路#

D猪猪养成计划2#

题目描述#

思路#

Emin25筛#

思路#

代码#

Emin25筛 #