Educational Codeforces Round 68 (Rated for Div. 2)

link for contests: http://codeforces.com/contest/1194

水平有限只能做出其中三题

Problem-A. Remove a Progression

分析:

第i次删除第i个数，操作x后输出第x个数。规律：输出的数始终是x的两倍

code:

#include <cstdio>

using namespace std;
typedef long long LL;

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        LL num, x;
        scanf("%lld %lld", &num, &x);
        printf("%lld\n", x*2);
    }

    return 0;
}

Problem-B. Yet Another Crosses Problem

题意：

因英文水平有限，所以光琢磨题意就花了好长时间

题目大概意思就是，一个方格所在的行和列都要是黑色的，这样才算是一个cross.

问题是给出一个一个图形，问最少需要涂几次才能最少有一个cross

分析：

选出以某个方格为基础，涂满这个方格所在的行或列所用最小的次数

code:

#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 5e4+7;
const int INF = 0x3f3f3f3f;

vector<vector<int> > G; // 存图  .为0 *为1
int a[MAXN], b[MAXN];   // 行和列
char s[MAXN];   // 每次读入一行

int main()
{
    int q;
    scanf("%d", &q);
    while(q--)
    {
        int n, m;
        scanf("%d %d", &n, &m);
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        G.clear(); G.resize(n+1);
        for(int i=1; i<=n; i++)  // 读入数据
        {
            scanf("%s", s);
            G[i].resize(m+1);
            for(int j=1; j<=m; j++)
            {
                if(s[j-1] == '*')   // .为0 *为1
                    G[i][j] = 1;
                else
                {   // 如果为 . 说明这个方格是白的，这个方格所在的行和列的白格数就都要加一
                    a[i] ++; 
                    b[j] ++;
                }
                
            }
        }
        int ans = INF;
        /* 遍历所有的方格，并选出以每个方格为基础，涂满所在的行或列最小的值 */
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(G[i][j])
                    ans = min(ans, a[i] + b[j]);
                else
                    ans = min(ans, a[i]+b[j] - 1);
            }
        }
        printf("%d\n", ans);
    }

    return 0;
}

Problem-C. From S To T

题意：

有三个字符串，p t s, 现在可以从p中任取出一个字符然后插入到s中，问是否能使s等于t

分析：

若s经过操作后能等于t，则s满足的条件是，初始s是t的字串（不需要连续），且p中对应的字符需要足够

code:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100+7;

map<char, int> s, t, p;
char ss[MAXN], tt[MAXN], pp[MAXN];

int check(int lens, int lent)
{
    int i = 0, j = 0;
    while(i<lent && j<lens)
    {
        if(tt[i] == ss[j])
        {
            i++, j++;
        }
        else
            i++;
    }
    if(j == lens)
        return 1;
    return 0;
}

int main()
{
    int q;
    scanf("%d", &q);
    while(q--)
    {   
        scanf("%s", ss);
        scanf("%s", tt);
        scanf("%s", pp);
        // printf("%d %s %s %s\n",q, ss, tt, pp);
        int lens = strlen(ss);
        int lent = strlen(tt);
        int lenp = strlen(pp);
        s.clear(); t.clear(); p.clear();
        for(int i=0; i<lens; i++)
            s[ss[i]]++;
        for(int i=0; i<lent; i++)
            t[tt[i]] ++;
        for(int i=0; i<lenp; i++)
            p[pp[i]] ++;
        map<char, int>::iterator it;
        if( !check(lens, lent))
            printf("NO\n");
        else
        {
            for(it=t.begin(); it != t.end(); it++)
            {
                if(!s.count(it->first))
                    s[it->first] = 0;
                if(it->second != s[it->first])
                {
                    int cnt = it->second - s[it->first];
                    if(cnt < 0 || p[it->first] < cnt)
                    {
                        printf("NO\n");
                        break;
                    }
                }
            }
            if(it == t.end())
                printf("YES\n");
            }
    
    }

    return 0;
}