Educational Codeforces Round 159 (Rated for Div. 2)

Educational Codeforces Round 159 (Rated for Div. 2)

A

有0肯定可以没0肯定不行

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n;
    string s;
    cin >> n;
    cin >> s;
    int c0 = count(s.begin() , s.end() , '0') , c1 = count(s.begin() , s.end() , '1');
    if(c0 > 0){
        cout << "YES\n";
        return ;
    }
    cout << "NO\n";
    return ;
}

int main()
{
    int T;
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}

B

数学模拟，从后往前优先把有活动的先做再做没活动的
记得加奇数周

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    long long n , p , l , t;
    cin >> n >> p >> l >> t;
    int wk = ((n +6)/7) ,ans = 0;
    // cout << wk << endl;
    long long a = l + 2 * t;
    ans =ceil((double)p/ a);
    if(ans > (wk / 2))ans = wk / 2;
    p -= a * ans;

    if(p > 0 && (wk & 1)){
        ans ++;
        p-= l + t;
    }
    if(p > 0) ans += ceil((double)p/ l);
    cout << n - ans << endl;
}

int main()
{
    int T;
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}

C

贪心，排序后取gcd得到k最大再从其中找an位置

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
const int INF = 1e9;
int a[N], b[N];
int n , k , mx;
int gcd(int aa, int bb)
{
    return bb ? gcd(bb, aa % bb) : aa;
}

void solve()
{
    
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    if(n == 1){
        cout << "1\n";
        return ;
    }
    sort(a + 1, a + n + 1);
    k = 0;
    int ans = 0;
    for (int i = 2; i <= n; i++)
    {
        k = gcd(k, a[i] - a[i - 1]);
    }
    for (int i = 1; i <= n; i++)
    {
        ans += (a[n] - a[i])/k;
    }
    int d = 0x3f3f3f3f;
    for(int i = n; i >= 2; -- i){
        if((a[i] - a[i - 1]) / k > 1){
            d = a[i] - k;
            break;
        }
    }
    if(d == 0x3f3f3f3f)ans += n;
    else ans +=  (abs(a[n]-d)/k);
    cout << ans << endl;
}

main()
{
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}