Codeforces Round #799 (Div. 4)

目录

官方题解

A. Marathon

B. All Distinct

C. Where's the Bishop?

D. The Clock

E. Binary Deque

F. 3SUM

G. 2^Sort

H. Gambling

---

官方题解

点击跳转：官方题解

A. Marathon

A. Marathon

思路：略

代码如下：

#include 

#define fast ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)

using namespace std;

typedef long long LL;
typedef pair PII;

const int N = 1e6 + 10, mod = 1e9 + 7;

int T;

void solve()
{
    int n, m;
    scanf("%d", &n);

    int res = 0;
    for(int i = 0; i < 3; i ++ )
    {
        scanf("%d", &m);
        if(m > n) res ++;
    }


    printf("%d\n", res);
}

int main()
{
    //fast;
    //cin >> T;
    scanf("%d", &T);
    while(T -- )
        solve();

    return 0;
}

B. All Distinct

B. All Distinct

思路：先将结果定义为所有的不重复数字，将同一个数多于1的部分删去，若删去的部分为奇数，则在结果中再删去一个，

可以用：用 map 离散化一下

代码如下：

#include 

#define fast ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)

using namespace std;

typedef long long LL;
typedef pair PII;

const int N = 1e6 + 10, mod = 1e9 + 7;

int T;

void solve()
{
    int n, m;
    scanf("%d", &n);

    int res = 0, x;
    map mp;
    for(int i = 0; i < n; i ++ )
    {
        scanf("%d", &x);
        if(!mp[x]) res ++;
        mp[x] ++;
    }

    int f = 0;
    for(auto it : mp)
    {
        if(it.second >= 2) f += (it.second-1);
    }

    if( f%2 ) res --;

    printf("%d\n", res);
}

int main()
{
    //fast;
    //cin >> T;
    scanf("%d", &T);
    while(T -- )
        solve();

    return 0;
}

C. Where's the Bishop?

C. Where's the Bishop?

思路：暴力枚举即可，用到了坐标偏移小技巧

代码如下：

#include 

#define fast ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)

using namespace std;

typedef long long LL;
typedef pair PII;

const int N = 1e6 + 10, mod = 1e9 + 7;

int T;

void solve()
{
    int x, y;
    char s[10][10];

    for(int i = 1; i <= 8; i ++ )
        cin >> s[i] + 1;
    int dx[4] = {1, 1, -1, -1}, dy[4] = {1, -1, 1, -1};
    for(int i = 1; i <= 8; i ++ )
    {
        for(int j = 1; j <= 8; j ++ )
        {
            if(s[i][j] == '#')
            {
                int f = 0;
                for(int k = 0; k < 4; k ++ )
                {
                    int xx = i + dx[k], yy = j + dy[k];
                    if(xx >= 1 && xx <= 8 && yy >= 1 && yy <= 8 && s[xx][yy] == '#') f ++;
                }
                if(f == 4)
                {
                    printf("%d %d\n", i, j);
                    return;
                }
            }
        }

    }

    //printf("%d\n", res);
}

int main()
{
    //fast;
    //cin >> T;
    scanf("%d", &T);
    while(T -- )
        solve();

    return 0;
}

D. The Clock

D. The Clock

思路：记录时间是否出现过，枚举

代码如下：

#include 

#define fast ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)

using namespace std;

typedef long long LL;
typedef pair PII;

const int N = 2e5 + 10, mod = 1e9 + 7;

int T;

void solve()
{
    int h, m, k;
    scanf("%d:%d %d", &h, &m, &k);
    int time = (h*60 + m)%(24*60);

    int st[N] = {0};
    int res = 0;

    while(!st[time])
    {
        st[time] = 1;
        int h = time/60;
        int m = time%60;
        //cout << h << " " << m << endl;
        if( h == m%10*10 + m/10) res ++;
        time = (time + k)%(24*60);
    }

    printf("%d\n", res);
}

int main()
{
    //fast;
    //cin >> T;
    scanf("%d", &T);
    while(T -- )
        solve();

    return 0;
}

E. Binary Deque

E. Binary Deque

思路：

方法一：建立前缀和，后缀和数组，枚举每个后缀，二分找到最小前缀，判断是否为最小的 *** 作数

方法二：双指针，判断保留部分的最大值

代码如下：

方法一：

#include 

#define fast ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)

using namespace std;

typedef long long LL;
typedef pair PII;

const int N = 2e5 + 10, mod = 1e9 + 7;

int T;

void solve()
{
    int n, k;
    scanf("%d %d", &n, &k);

    int res = 0x3f3f3f3f;
    int sum = 0;
    bool a[N];
    int sq[N] = {0}, sh[N] = {0};
    for(int i = 1; i <= n; i ++ )
        scanf("%d", &a[i]), sum += a[i];

    int m = sum - k;
    //cout << m << endl;

    if(sum < k)
    {
        puts("-1");
        return;
    }

    for(int i = 1; i <= n; i ++ )
        sq[i] = sq[i-1] + a[i];


    for(int i = n; i >= 1; i -- )
        sh[i] = sh[i+1] + a[i];

    for(int j = n+1; j >= 0; j -- )
    {
        int t = sh[j];
        int l = 0, r = n + 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(sq[mid] >= (m - t) ) r = mid;
            else l = mid + 1;
        }

        //cout << l << " " << j << endl;

        if(l >= j) continue;
        if( t + sq[l] == m ) res = min(res, n-j+1+l);
    }

    printf("%d\n", res);
}

int main()
{
    //fast;
    //cin >> T;
    scanf("%d", &T);
    while(T -- )
        solve();

    return 0;
}

方法二：

#include 

#define fast ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)

using namespace std;

typedef long long LL;
typedef pair PII;

const int N = 2e5 + 10, mod = 1e9 + 7;

int T;

void solve()
{
    int n, k;
    scanf("%d %d", &n, &k);

    int sum = 0;
    bool a[N];
    int sq[N] = {0}, sh[N] = {0};
    for(int i = 1; i <= n; i ++ )
        scanf("%d", &a[i]), sum += a[i];

    if(sum < k)
    {
        puts("-1");
        return;
    }

    int res = 0;
    int t = 0;
    for(int j = 1, i = 1; j <= n; j ++ )
    {
        t += a[j];
        while(i < j && t > k) t -= a[i++];
        if(t == k) res = max(res, j - i + 1);
    }

    printf("%d\n", n-res);
}

int main()
{
    //fast;
    //cin >> T;
    scanf("%d", &T);
    while(T -- )
        solve();

    return 0;
}

 

F. 3SUM

F. 3SUM

思路：模 10 ，暴力枚举 0~10 内的数，

代码如下：

#include 

#define fast ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)

using namespace std;

typedef long long LL;
typedef pair PII;

const int N = 2e5 + 10, mod = 1e9 + 7;

int T;

void solve()
{
    int n, k;
    scanf("%d", &n);

    int st[20] = {0}, x;
    for(int i = 0; i < n; i ++ )
        scanf("%d", &x), st[x%10] ++;

    for(int i = 0; i < 10; i ++ )
    {
        if(st[i]) st[i] --;
        else continue;
        for(int j = 0; j < 10; j ++ )
        {
            if(st[j]) st[j] --;
            else continue;
            for(int k = 0; k < 10; k ++ )
            {
                if(st[k]) st[k] --;
                else continue;
                if( (i + j + k) % 10 == 3)
                {
                    //cout << i << " " << j << " " << k << endl;
                    puts("YES");
                    return;
                }
                st[k] ++;
            }
            st[j] ++;
        }
        st[i] ++;
    }

    puts("NO");

    //printf("%d\n", res);
}

int main()
{
    //fast;
    //cin >> T;
    scanf("%d", &T);
    while(T -- )
        solve();

    return 0;
}

G. 2^Sort

G. 2^Sort

思路：判断每个位置是否符合题目条件，即、a[i]*2 > a[i-1]，若满足则标记为1（1位置必定为1），反之为0；然后判断每段连续的1，可以贡献最多多少组数据，最终结果为数据的数量累加

代码如下：

#include 

#define fast ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)

using namespace std;

typedef long long LL;
typedef pair PII;

const int N = 2e5 + 10, mod = 1e9 + 7;

int T;

void solve()
{
    int n, k;
    scanf("%d %d", &n, &k);

    int a[N] = {0}, s[N] = {0};
    s[0] = 1;
    for(int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
        if(a[i-1]  < a[i] * 2  ) s[i] = 1;
    }

    int res = 0;
    int t = 0;
    for(int i = 1; i <= n; i ++ )
    {
        //cout << s[i]  << " " << t << endl;
        if( s[i] == 1 ) t ++;
        if( s[i] == 0 )
        {
            if(t >= k + 1) res += (t-k);
            t = 1;
        }
    }
    if(t >= k + 1) res += (t-k);

    printf("%d\n", res);
}

int main()
{
    //fast;
    //cin >> T;
    scanf("%d", &T);
    while(T -- )
        solve();

    return 0;
}

H. Gambling

H. Gambling

思路：考察最大连续子序列：点击跳转模板题，回忆算法

将每个相同数的位置放入vector，枚举所有的vector，vector中的前后元素的差为，模板题中的a[i]，每次加上差值；

若小于0，则重置为1，重置左右边界；

反之更新 t ( 当前vector的最大子序列的值）r (有边界） ，res（最大子序列的值），resn（最大子序列的模板数）resl（左边界），resr（右边界）。

代码如下：

#include 

#define fast ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)

using namespace std;

typedef long long LL;
typedef pair PII;

const int N = 2e5 + 10, mod = 1e9 + 7;

int T;

void solve()
{
    int n, k;
    scanf("%d", &n);

    map> mp;

    int x = 0;
    for(int i = 1; i <= n; i ++ )
        scanf("%d", &x), mp[x].push_back(i);

    int res = 0, resn = 0, resl = 0, resr = 0;

    for(auto it : mp)
    {
        int t = 1, l = 0, r = 0;

        for(int i = 0; i < it.second.size() - 1; i ++ )
        {
            int cha = it.second[i] - it.second[i+1] + 1;
            t += cha;
            if(t > 0) t ++, r = i + 1;
            else
            {
                t = 1;
                l = r = i + 1;
            }

            if(t > res)
            {
                res = t;
                resn = it.first;
                resl = it.second[l];
                resr = it.second[r];
            }
        }

        if(t > res)
        {
            res = t;
            resn = it.first;
            resl = it.second[l], resr = it.second[r];
        }

    }

    printf("%d %d %d\n", resn, resl, resr);
}

int main()
{
    //fast;
    //cin >> T;
    scanf("%d", &T);
    while(T -- )
        solve();

    return 0;
}