Codeforces Round #744 (Div. 3)部分题解

点击此处查看对应的题目.
本题模拟
本题是看所有是否能你模拟出来的所有√勾是否能对标记的单元格进行所有覆盖，我这里模拟了所有 ′ ∗ ′ '*' ′∗′元素不断向上两边延伸的过程就行（这里我用了递归来进行延伸的操作）。

时间复杂度 O ( n 2 ∗ m ) O(n^2*m) O(n2∗m)

#include
using namespace std;
const int N = 110,INF = 1e9;
char g[N][N];
bool st[N][N];
int n,m,k;
struct Node
{
    int a,b,c;
};
vector v;

bool judge()
{
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            if(!st[i][j] && g[i][j] == '*')
                return false;
    return true;
}
void init()
{
    for(int i = 0;i < N;i ++)
        for(int j = 0;j < N;j ++){
            g[i][j] = '.';
            st[i][j] = false;
        }
}
int dg(int x,int y1,int y2,int h)
{
    if(g[x][y1] != '*' || g[x][y2] != '*'){
        if(h >= k){
            for(int i = 0;i < v.size();i ++)
                st[v[i].a][v[i].b] = true,st[v[i].a][v[i].c] = true;
            return 1;
        }
        return 0;
    }
    v.push_back({x,y1,y2});
    dg(x - 1,y1 + 1,y2 - 1,h + 1);
}
void solve()
{
    cin >> n >> m >> k;
    init();
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            cin >> g[i][j];

    int maxn = -INF;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            if(g[i][j] == '*'){
                int t = dg(i - 1,j + 1,j - 1,0);
                if(t) st[i][j] = true;
                v.clear();
            }

    if(judge()) puts("Yes");
    else puts("No");
}
int main()
{
    int t;
    cin >> t;
    while (t -- ){
        solve();
    }
    return 0;
}

点击此处查看对应的题目.
本题涉及算法：贪心
本题应该要贪心的选取两个最大的元素，将这两个元素减1，最后达到整个序列只有一个非0元素的目的。

这里用优先队列来进行数据储存，以便于进行实时排序。选取队列队头即为最大值。

时间复杂度 O ( n ) O(n) O(n)

#include
using namespace std;
typedef long long ll;
typedef pair PII;
const int N = 1e5 + 10;

void solve()
{
    priority_queue, less> q;
    vector res;
    int n;
    cin >> n;

    for(int i = 1;i <= n;i ++){
        int x;
        cin >> x;
        if(x) q.push({x,i});
    }

    while(q.top().first && q.size() > 1){
        int x = q.top().first;
        int index_x = q.top().second;
        q.pop();

        int y = q.top().first;
        int index_y = q.top().second;
        q.pop();

        x --,y --;
        res.push_back({index_x,index_y});

        if(x > 0) q.push({x,index_x});
        if(y > 0) q.push({y,index_y});
    }

    cout << res.size() << 'n';
    if(res.size()){
        for(int i = 0;i < res.size();i ++) cout << res[i].first << " " << res[i].second << 'n';
    }
}
int main()
{
    int t;
    cin >> t;
    while(t -- ){
        solve();
    }
    return 0;
}

点击此处查看对应的题目.
本题涉及算法：双端队列 + 贪心
简单模拟题意即可，贪心地从前后加入元素即可。

时间复杂度 O ( n ) O(n) O(n)

#include
using namespace std;
const int N = 1e5 + 10,INF = 1e9 + 7;
int a[N];

void solve()
{
    int n;
    deque q;
    cin >> n;

    for(int i = 0;i < n;i ++){
        int x;
        cin >> x;
        if(q.empty() || x < q.front()) {
            q.push_front(x);
        }else {
            q.push_back(x);
        }
    }
    for(auto it : q) cout << it << " ";
    puts("");
}
int main()
{
    int t;
    cin >> t;
    while(t -- ){
        solve();
    }
    return 0;
}