526互联

CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)

发布时间 2023-04-02 16:06:37作者: 努力的德华

题目链接

C

核心思路

其实这个操作无非就两种：插入和删除。

我们可以把重复的元素都先删除，因为这肯定是每个操作必须要做的。

我们可以从最基础的情况出发也就是怎么构造出来\(1\sim a[i]\)的序列呢。肯定是吧\(i\sim n\)之后的序列都删除吧，然后把前面缺少的再补上去吧。

所以我们可以把前面都排序，也就是比如：1 3 4 7 8.到4的时候前面肯定已经有了2个数。所以只需要再补一个数就好了。

唯一需要注意的是需要特判1的情况。

#include<bits/stdc++.h>
using namespace std;
int p[100005];
typedef long long ll;
void solve()
{
    int n,a,b;scanf("%d%d%d",&n,&a,&b);
    set<int> st;
    ll sol = 0 , ans = 2e18;
    for(int i = 1;i <= n;i++) {
        int x;scanf("%d",&x);
        if(st.find(x) == st.end()) st.insert(x);
        else sol += a;
    }
    int c = 0;
    for(auto x : st) p[++c] = x;
    for(int i = 1;i <= c;i++) {
        ans = min(ans , 1LL*(p[i] - i)*b + 1LL*(c-i)*a);
    }
    ans = min(ans , 1LL*c*a + b) ;
    printf("%lld\n",ans+sol);
}
int main()
{
    int t;scanf("%d",&t);
    while(t--) solve();
}

D

核心思路

首先我们可以很容易的得出来这个最大的L也就是爬行长度是：\((n-1)*(a-b)+a\),那么最小的自然也就是我们不可以在\(n-1\)天就提前爬完了所有的路程，所以L需要大于\((n-2)*(a-b)+a\).也就是\(L \in ((n-2)*(a-b)+a,(n-1)*(a-b)+a]\).

所以我们的操作1就比较好维护了，不断地两个区间取交集就好了。

那么操作2，首先需要明确操作2是要我们求天数，我们可以从上面的式子中把天数的表达式求出来：

\(n-2 \leq \frac{L-a}{a-b} \leq n-1\).

于是我们向上取整在加1就是n，接下来只需要看l和r代表的n是否相同就好了。

// Problem: D. Climbing the Tree
// Contest: Codeforces - CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)
// URL: https://codeforces.com/contest/1810/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 


void solve()
{
	int q;
	cin>>q;
	int l=1,r=1e18;
	while(q--)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int a,b,n;
			cin>>a>>b>>n;
			int ql=(n-2)*(a-b)+a+1;
			int qr=(n-1)*(a-b)+a;
			if(n==1)
			ql=1,qr=a;
			if(ql>r||qr<l)
			puts("0");
			else
			l=max(l,ql),r=min(r,qr),puts("1");
			
		}
		else
		{
			int a,b;
			cin>>a>>b;
			int ans1=max(1ll,(l-b-1)/(a-b)+1);
			int ans2=max(1ll,(r-b-1)/(a-b)+1);
			if(ans1==ans2)
			cout<<ans1<<endl;
			else
			puts("-1");
		}
	}
}


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