总结

Q1-Countdown

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

#define maxN 200000+50

// 直接遍历+判断即可
int main()
{
    int num[maxN];
    int t,T,N,n,K,k,temp_K;
    int cnt,flag;
    scanf("%d", &T);
    for(t=1; t<=T; t++)
    {
        cnt = 0;
        memset(num, 0, sizeof(num));
        scanf("%d %d", &N, &K);
        // 先全部输入
        for(n=0; n<N; n++)
        {
            scanf("%d", &num[n]);
        }
        for(n=0; n<N; n++)
        {
            // 发现K值,判断是否为m-countdown
            if(num[n] == K)
            {
                flag = 1;
                temp_K = K;
                // 向后遍历K个数
                for(k=0; k<K; k++)
                {
                    if(num[n+k] == temp_K)
                    {
                        temp_K = temp_K-1;
                        continue;
                    }
                    else
                    {
                        flag = 0;       
                        break;
                    }
                }
                if(flag == 1)
                {
                    cnt++;
                    //n = n+K;
                }
            }
        }
        printf("Case #%d: %d\n", t, cnt);
    }

    /* std::cout << "Hello world" << std::endl; */
    return 0;
}

Q2-StableWall

/***********************************************
#
#      Filename: 2020C-Q2-StableWall.cpp
#
#        Author: Li Xudong - 757264690@qq.com
#   Description: ---
#        Create: 2020-11-12 15:08:39
# Last Modified: 2020-11-13 01:42:42
#
 ***********************************************/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <string.h>
#include <set>
using namespace std;

// 这一题其实很简单
// 题目的意思是用字母当多米诺骨牌进行堆叠,判断这个堆叠方案是否稳定,如果稳定,输出堆叠序列
// 但是字母的堆叠是有顺序的,每个字母是一次性堆好的.
// 比如,下面的一个序列:
// MM
// MF
// MM
// 如果先堆字母M,则最右上角的字母M,因为它的下面是空的(还没有堆F呢),所以M容易落下来,则是不稳定的
// 
// 看到先后顺序,首先想到了拓扑排序
// 怎么建图呢?
// 从下面往上开始建立,并且一列一列建立,对于上面的例子,
// 首先第一列都是M,肯定是稳定的,无需增加边,加一个顶点M
// 对于第二列,从往上,分别是M-F-M,则需要在顶点M和顶点F之间增加一条边,之后在顶点F和顶点M之间增加一条边(其实,这时候已经有环了,是不稳定的)
// 建好拓扑图后,拓扑排序,输入节点即可,如果没有将所有节点输出,则有环,输出-1
//
#define maxN 35
// 26个顶点
#define maxP 26

// 字母矩阵
char alp[maxN][maxN];
int main()
{
    int t,T,R,C;
    int i,j,k;

    scanf("%d", &T);
    // 拓扑图
    vector<int> G[maxP];
    // 入度
    int d[maxP];
    // 拓扑排序的输出队列
    queue<int> tst,ans;
    // 字母集合
    set<int> ss;

    for(t=1; t<=T; t++)
    {
        scanf("%d %d", &R, &C);
        memset(alp, 0, sizeof(alp));
        // 拓扑图和入度数组的初始化
        for(i=0; i<maxP; i++)
        {
            G[i].clear();
            d[i] = 0;
        }
        for(i=0; i<R; i++)
            for(j=0; j<C; j++)
            { 
                scanf(" %c", &alp[i][j]);
                ss.insert(alp[i][j]-'A');
            }

        // 建立拓扑图形
        for(i=0; i<R-1; i++)
        {
            for(j=0; j<C; j++)
            {
                // 如果上下两个字母相同,则不添加任何边
                if(alp[i][j] != alp[i+1][j])
                {
                    G[alp[i+1][j]-'A'].push_back(alp[i][j]-'A');
                    d[alp[i][j]-'A']++;
                }
            }
        }

        // 建好图后, 就可以拓扑排序了
        // 先添加入度为0的序列入队
        for(i=0; i<maxP; i++)
            if(!d[i] && ss.count(i))
                tst.push(i);

        while(!tst.empty())
        {
            // 输出入度为0的顶点,由于不知道有没有环,还不能输出
            // printf("%c", tst.front()+'A');
            k = tst.front();
            tst.pop();
            ans.push(k);
            // 删除该顶点出发的边,并且对应的顶点入度-1
            for(i=0; i<G[k].size(); i++)
            {
                d[G[k][i]]--;
                // 如果为0,则加入队列
                if(!d[G[k][i]])
                    tst.push(G[k][i]);
            }

        }

        printf("Case #%d: ",t);
        if(ans.size() == ss.size())
        {
            while(!ans.empty())
            {
                printf("%c", ans.front()+'A');
                ans.pop();
            }
            printf("\n");
        }
        else
            printf("-1\n");
        /* printf("Case #%d: ",t); */
        // 清除集合
        ss.clear();
        // 清除所有的顶点
        for(i=0; i<maxP; i++)
            G[i].clear();
        // 清空tst队列、ans队列
        while(!ans.empty())
            ans.pop();
        while(!tst.empty())
            tst.pop();
    }
    return 0;
}

Q3-PerfectSubway

/***********************************************
#
#      Filename: 2020C-Q3-PerfectSubway.cpp
#
#        Author: Li Xudong - 757264690@qq.com
#   Description: ---
#        Create: 2020-11-13 17:42:55
# Last Modified: 2020-11-15 00:44:57
#
***********************************************/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <unordered_map>

// 运行： g++ 2020C-Q3-PerfectSubway-AC.cpp -std=c++11 ; ./a.out 

// 貌似是以前的组合数学问题,要求求出 子集合元素和 为完全平方数的子集数量
// 比如一个数组a1到a10,
// 假设a5到a7是一个满足的子集，其和为b的平方
// 则a5+a6+a7=b*b
// 等同于sum(1,7)-sum(1,4)=b*b
// 等同于sum(1,7)-b*b = sum(1,4)
// 因此，我们需要对b依次进行遍历，看数组中是否有sum(1,4)存在，如果存在，则有满足的子集和
// 第一次用的set来做，看到别人用map AC了，尝试用map做一下

using namespace std;

const int maxN = 1e5+20;
const int inf = 1e7+20;
int sum[maxN];
unordered_map<int, int> m;
void solve()
{
    int N;
    int n;
    int i,j,k;
    long long ans=0;
    int minn=0;
    scanf("%d", &N);
    memset(sum, 0, sizeof(sum));
    m.clear();

    // 存储和
    for(n=1; n<=N; n++)
    {
        scanf("%d", &k);
        sum[n] += sum[n-1]+k;
        minn = min(minn, sum[n]);
    }

    m[0]=1;

    for(i=1; i<=N; i++)
    {
        for(j=0; j*j<=inf; j++)
        {
            if(m.count(sum[i]-j*j))
            {
                ans += m[sum[i]-j*j];
            }
            if((sum[i]-j*j)<minn)
                break;

        }

        m[sum[i]]++;
    }
    printf("%lld\n", ans);

}
int main()
{
    int t,T;
    scanf("%d", &T);
    for(t=1; t<=T; t++)
    {
        //solve();
        printf("Case #%d: ", t);
        solve();
    }
}

Q4-Candies

/***********************************************
♡        Filename : 2020C-Q4-Candies.cpp
♡  
♡     Description : ---
♡          Author : Li Xudong
♡         Contact : 757264690@qq.com
♡         Created : 2020-12-17 09:29:13
***********************************************/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

// 如果直接对原数组操作，则查询操作为O(n)，而更新操作复杂度为O(1)。
// 如果构建前缀和数组，则查询操作为O(1)，而更新操作复杂度为O(n)。
// 因此出现了矛盾。
//
// 一个比较常用的方法就是使用线段树方法。
// 构建两个线段树：
// 假设数组元素为[t1,t2,t3,t4,t5...]
// 1.第一棵树，构建了t1,-t2,t3,-t4,t5...等元素的线段树
// 2.第二棵树，构建了1*t1, 2*(-t2), 3*t3, 4*(-t4), 5*t5...等元素的线段树
// 则每次查询的结果"Q L R"可以表示为，(第二棵树-第一棵树*(L-1)) * ((-1)^(L-1))
//
// 都是线段树的基础操作：建立树、更新树、查询树
// 
const int maxn = 2e5+10;

int t[maxn];
long long tree[maxn<<2][2]; // 第一棵树tree[][0],第二棵树tree[][1]

void build_tree(int node, int start, int end)
{
    if(start==end)
    {
        tree[node][0] = t[start];
        tree[node][1] = t[start]*start;
    }
    else
    {
        int mid = (start+end)/2;
        int leftnode = node*2;
        int rightnode = node*2+1;
        build_tree(leftnode, start, mid);
        build_tree(rightnode, mid+1, end);
        tree[node][0] = tree[leftnode][0] + tree[rightnode][0];
        tree[node][1] = tree[leftnode][1] + tree[rightnode][1];
    }
}

void update_tree(int node, int start, int end, int idx, int val)
{
    if(start==end)
    {
        //t[idx] = val;
        tree[node][0] = val;
        tree[node][1] = val*start;
    }
    else
    {
        int mid = (start+end)/2;
        int leftnode = node*2;
        int rightnode = node*2+1;
        if(idx<=mid)
        {
            update_tree(leftnode, start, mid, idx, val);
        }
        else
        {
            update_tree(rightnode, mid+1, end, idx, val);
        }
        tree[node][0] = tree[leftnode][0] + tree[rightnode][0];
        tree[node][1] = tree[leftnode][1] + tree[rightnode][1];
    }
}

// 查询第一棵树
long long query_tree1(int node, int start, int end, int L, int R)
{
    if(L>end || R<start) return 0;
    else if((start == end) || (L<=start && end<=R) ) return tree[node][0];
    else{
        int mid = (start+end)/2;
        int leftnode = node*2;
        int rightnode = node*2+1;
        long long sum_left = query_tree1(leftnode, start, mid, L, R);
        long long sum_right = query_tree1(rightnode, mid+1, end, L, R);
        return sum_left + sum_right;
    } 
}


// 查询第二棵树
long long query_tree2(int node, int start, int end, int L, int R)
{
    if(L>end || R<start) return 0;
    else if((start == end) || (L<=start && end<=R) ) return tree[node][1];
    else{
        int mid = (start+end)/2;
        int leftnode = node*2;
        int rightnode = node*2+1;
        long long sum_left = query_tree2(leftnode, start, mid, L, R);
        long long sum_right = query_tree2(rightnode, mid+1, end, L, R);
        return sum_left + sum_right;
    } 
}

void solve()
{
    int N, Q;
    scanf("%d %d", &N, &Q);
    int i,j;
    memset(t, 0, sizeof(t));
    memset(tree, 0, sizeof(tree));

    for(i=1; i<=N; i++)
    {
        scanf("%d", &t[i]);
        if(!(i&1))
        {
            t[i] = -t[i];
        }
    }

    build_tree(1, 1, N);

    long long ans = 0;
    char c;
    int num1, num2;
    for(i=1; i<=Q; i++)
    {
        scanf(" %c", &c);
        if(c=='U')
        {
            scanf("%d %d", &num1, &num2);
            if(!(num1&1)) num2 = -num2;
            update_tree(1, 1, N, num1, num2);
        }
        else
        {
            scanf("%d %d", &num1, &num2);
            long long sum1 = query_tree1(1, 1, N, num1, num2);
            long long sum2 = query_tree2(1, 1, N, num1, num2);
            sum2 = sum2-sum1*(num1-1);
            if(!(num1&1)) sum2 = -sum2;
            ans += sum2;
        }

        //printf("%lld\n", ans);
    }
    printf("%lld\n", ans);
}
int main()
{
    int t, T;
    scanf("%d", &T);
    for(t=1; t<=T; t++)
    {
        printf("Case #%d: ", t);
        solve();
    }
}