Educational Codeforces Round 95 (Div. 2) A - B题题解（A题数据连错3次，搞人心态中）

1418A. Buying Torches

这次A题，真心fo了（导致wa了我两次）
样例出错两次，数据出错一次。
讲一下我的思路吧。

• 首先先明确至少需要多少个棍。 个火炬，至少需要$k ∗ y + k $ 个棍棍。
• 其次要想，怎么从个棍，利用第一条贸易，变成 个棍。我们可以先通过观察，假设 。

可以发现每次加,也就是

所以，设是贸易一的次数。

%20%E2%88%97%20t%20m%20p%20%E2%88%92%20%3E%20k%20%E2%88%97%20y%20%2B%20k%0A#card=math&code=1%20%2B%20%28%20x%20%E2%88%92%201%20%29%20%E2%88%97%20t%20m%20p%20%E2%88%92%20%3E%20k%20%E2%88%97%20y%20%2B%20k%0A)

这里我为什么要用而不是$= $呢？

因为可能不能正好等于$k ∗ y + k $。
那就取

%E2%88%97tmp%3Ek%E2%88%97y%2Bk%0A#card=math&code=1%2B%28x%E2%88%921%29%E2%88%97tmp%3Ek%E2%88%97y%2Bk%0A)

时 的值。

最后 再加上 次即可。

#python
for _ in range(int(input())):
    x,y,k=map(int,input().split())
    tmp=(k*y+k-1)//(x-1)
    if tmp*(x-1)<k*y+k-1:
        tmp+=1
    tmp+=k
    print(tmp)

//C++
#include<bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int N = 1e5 + 100;
ll _, n, m, a[N], i, j;
void solve() {
    ll x, y, k;
    cin >> x >> y >> k;
    ll tmp = (k * y + k - 1) / (x - 1);
    if (tmp * (x - 1) < k * y + k - 1)tmp++;
    tmp += k;
    cout << tmp << endl;
}
int main() {
    //freopen("in.txt", "r", stdin);
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> _; while (_--) solve();
}

再看看一下dalao的数学解法：

由于第二次交易是获取煤炭的唯一方法，因此我们显然需要进行 次第二次交易。 那么，我们需要进行多少次首次交易？ 我们可以看到，为了最终得到足够的棒和煤，我们需要获得 棒（将 转换为煤，将 转换为棒）。 由于第一次交易实际上每次都给我们 个新的摇杆，因此我们需要进行 个第一次交易（对于不熟悉的人请参考下限和上限功能）。
有关实现细节，请注意，对于正整数 和 ，。

//C++实现
#include <iostream>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        long long x,y,k;
        cin>>x>>y>>k;
        cout<<((y+1)*k+x-3)/(x-1)+k<<endl;
    }
    return 0;
}

1418B. Negative Prefixes

模拟题，记录可以动的，从大到小排序。

#python
for _ in range(int(input())):
    n=int(input())
    lst=list(map(int,input().split()))
    s=list(map(int,input().split()))
    index=[]
    t=[]
    for i in range(n):
        if s[i]==0:
            index.append(i)
            t.append(lst[i])
    if len(t)==0:
        print(*lst)
        continue
    t.sort(reverse=True)
    for i in range(len(index)):
        lst[index[i]]=t[i]
    print(*lst)

//c++
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
    int t=1;
    cin>>t;
    while(t--){
        int n,i,j=0;
        cin>>n;
        int a[n],b[n];
        vector<int>v;
        for(i=0;i<n;i++)cin>>a[i];
        for(i=0;i<n;i++)cin>>b[i];
        for(i=0;i<n;i++){if(b[i]==0){v.push_back(a[i]);}}
        sort(v.rbegin(),v.rend());
        for(i=0;i<n;i++){if(b[i]==0){a[i]=v[j];j++;}}
        for(i=0;i<n;i++)cout<<a[i]<<" ";
        cout<<endl;
    }
}