题目描述

blablabla

样例

#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
/*
思考过程：
我最终得出，它是求一个原始序列中的连续子序列的个数的题，
我无法找到去计算重复元素的序列数量的方法，导致裂开。
看过别人代码后：
这题需要使用数据结构，去对元素进行处理。
首先，这个一定是要排序的，
这里我使用了stl，map容器。
达到去重和排序的作用，
以元素为键，元素出现的次数为值。
在容器中填入所有元素后，一定是一个递增的，也许不连续的数列。只有一个值的情况除外。
遍历map，将每个元素与它之前的一个连续的元素的出现次数进行比较，取大于零的差值，否则就取零。
此处我理解为：
对于一个元素，如果它紧挨着的（连续的）前一个元素出现的次数跟它一样，如2233的情形，就不必再加，因为之前已经加过了。
若二者次数不等，比前者小，他们差值为负，不必理会，说明前面重复的元素有长度为1的子序列。
比前者大，就差值为正，则需要加上差值，差值个数的元素可能是长度为1的子序列，或者新的连续子序列的开头。
就此，所有情况都考虑后，最终的和，就为总的连续子序列的数量。

数据结构类型的，头一次遇见。
*/


int main() {
    int t,n,num;
    cin >> t;
    while (t--) {
        cin >> n;
        map<int, int > ma;
        for (int i = 0; i < n; i++) {
            cin >> num;
            ma[num]++;
        }
        int res = 0;
        for (auto i = ma.begin(); i != ma.end(); i++) {
            res += max(0, i->second - ma[i->first - 1]);
        }
        cout << res << endl;
    }
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

//这里填你的代码^^
#include<iostream>
using namespace std;
/*
思考思路：
对dfs的再次称述：
任意选择一个点，进行深入，直到不能再深入时，谨慎地后退，
每后退一步都要检查是否有新的路可以走，当所有路走完后才再次后退，
以此类推，退到最开始的那个点，再检查是否有其他点可以深入。
此题思路：
根据题意，矩阵的每一行只有一个皇后，，在选定了一个皇后，之后的每个皇后的位置都要满足那三个条件。
这就可以使用dfs，遍历矩阵第一行即可，在选定一个皇后的基础上，去深入得遍历下一行。
直到最后一行。
是为一个完整得路线。
且通过对那三个条件（列、对角线、反对角线）得限制，即剪枝，能达到最后一行得路线一定是可行得。
其中一些我先没想好得点：
一，对于原始得矩阵，一定需要全部初始化为'.'；
我先是想得dfs函数会遍历矩阵得每个点，对于能填Q的位置可直接填'.';
但是，对于dfs，是一条路走到黑的，当走通了一条路就直接输出了，那个时候基本是没有遍历完整个矩阵的，那些没遍历的位置就是空的。
这导致了我的第一次错误。
二，对于恢复现场的处理，重新赋值为'.'是有必要的。
因为，虽然已经把三个bool数组恢复了，想着下次再到这个位置时，可以直接赋值遮盖掉。
但是，对于第一行，是遍历一遍的，其他行还有多次遍历的可能。
导致之前填的Q就无法被覆盖，这是我的第二次错误。
三，是针对对角线和反对角线数组的。
对于遍历的每个数和它对应的对角线，在下标上的关联我还不是很清晰。
但我觉得这不是很关键，只需要记住公式就可以，它最终的目的就是把当前遍历的为位置和对角线数组一一对应就好。

*/
char arr[10][10];
bool col[20]={false}, dg[20]={false}, udg[20]={false};
int r;
void dfs(int n) {
    if (n == r) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < r; j++)cout << arr[i][j];
            cout << endl;
        }cout << endl;
        return;
    }
    for (int i = 0; i < r; i++) {
        if (!col[i] && !dg[n + i] && !udg[r - n + i]) {
            arr[n][i] = 'Q';
            col[i] = dg[n + i] = udg[r - n + i] = true;
            dfs(n + 1);
            col[i] = dg[n + i] = udg[r - n + i] = false;
            arr[n][i] = '.';
        }

    }
}

int main() {

    cin >> r;

    for (int i = 0; i < r; i++)
        for (int j = 0; j < r; j++)arr[i][j] = '.';
    dfs(0);
    return 0;
}

//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

题目描述

blablabla

样例

#include<iostream>
#include<algorithm>
using namespace std;
/*
思考过程：
我简单地认为，是两个玩家交替地着拿石头，只需要看石头的堆数就可以了，
奇数就是Mike赢，偶数就是Joe赢。
这其中我默认，二者取石头的位子在下一次循环时，会重合，
即mike第一个拿，而在下一次面对第一堆石头时，是Joe拿，这是错误的。
且，我在思考中，我默认每个人拿的时候，都是把所有石头拿完。
下一次再到这个位置时，必定失败。
看他人思路后，
我发才察觉到，，奇数情况，我是正确的，但是偶数情况，我想得太简单了。
偶数情况，不存在我上面的那个下次循环会重合位置的情况，两个玩家取石头的位置都是固定的，即mike第一次在第一堆拿石头，下次循环到第一堆时，还是mike拿。
这样，我们就不能一次拿完了，否则mike必输。
因为，位置固定，所以我们在这个情况下比的是谁坚持得最久，最晚拿完石头。
也就是在原来的石堆中，最少石子的那一堆的位置下标，的奇偶性，决定了谁赢。
奇数，说明，mike最先拿完，Joe赢了，反之，Mike赢了。
这里我反糊涂了，以为谁先拿完，谁赢，困住了一会。

*/
int main() {
    long long t, n,num,indx;
    cin >> t;
    while (t--) {
        cin >> n;
    long long  min = 1e9 + 1;
        for (int i = 1; i <= n; i++) {

            scanf("%lld", &num);

            if (num < min)min = num, indx = i;

        }
        if (n % 2 == 0) { 
            if (indx % 2 == 0)cout << "Mike" << endl;
            else cout << "Joe" << endl;
        }
        else cout << "Mike" << endl;
    }

    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

题目描述

blablabla

样例

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;

/*思考过程：
* 自我思考阶段：
最先我以为是字符串s中的字符和字符串t中的字符进行替换。
然后发现是s中的a字符与整个字符串t进行替换。
他们都是非空字符串，所以我们只需要研究字符串t即可。
首先对于字符串的长度进行考虑。
在长度为1的情况下，
若为a，则只有一种情况。
若不为a，我认为不同字符串的种类就是字符串的长度加1.
我简单的认为每替换一次就是一种。
有多少个a就有多少种。
在长度大于1的情况下
若字符串t中存在a则可以无限套娃，属于无限大。
若不存在，我就是s字符串长度加1。
最终结果是，答案错误。
我看到题目后有个提示，察觉到在非a的情况下，不是简单的字符串长度加1的行为了。
我一度以为，每次替换后还可以放回的，我并没有找到字符串s长度与总的字符串种类数量之间的关系。
查看题解思路后：
发现，这里面就是一个完全二叉树，
对于t字符串，分两种情况；
t字符串中存在a时：
当t字符串长度为1，种类为1；
当t字符串长度不为1，种类无穷。
当t字符串中不存在a时，
就是一个二叉树了，去替换s字符串中的a，
对于每个a都要替换与不替换两者选择，在此基础上，去对下一个a进行抉择。
最终，字符串种类数就是，
总的节点数，即2的n次方，n为s字符串的长度。
我看到这里以为不是替换后可以放回，但好像也是，每一个结点分叉处，就要分两者情况去讨论。


*/
int main() {
    int q;
    string s, t;

    cin >> q;
    while (q--) {
        cin >> s >> t;
        if (t.length() == 1) {
            if (t == "a")cout << 1 << endl;
            else printf("%lld\n", (long long)pow(2, s.length()));

        }
        else {
            int flag = 0;
            for (int i = 0; i < t.length(); i++) {
                if (t[i] == 'a') {
                    flag = 1;
                    break;
                }
            }
            if (flag == 1) {
                cout << -1 << endl;
            }
            else printf("%lld\n",(long long) pow(2, s.length()));
        }
    }
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

//这里填你的代码^^
#include<iostream>
using namespace std;
const int N = 10;
int path[N], flag[N]={0}, n;
/*
记住目的是增进对dfs的理解；
dfs：深度优先搜索（爆搜）
具体而言是对一系列的数据，进行选择，每个元素都有两个可能，选或不选，在当前元素的选择的可能的基础上去选择下一个元素，这样就形成了一个二叉树。
在这个树中，从根节点开始，选择任意一个方向一条路走到黑，无路可走时才返回最近的岔路口，走另一条路，没有路口可走时再退回，往后每次遇到死胡同时都如此退回。
最终会遍历整个树，我们可以感觉到，每条走到黑的路都可以看作一个栈，向前为入栈，向后为出栈。
对于重复的岔路口选择场景，我们采用递归的方式，岔路口为递归式，死胡同就是递归出口。
可以感受到递归与dfs是等价的，想想递归的具体过程我们可以看到dfs的影子。
本题思考：
1到n为一排数据，我们可以根据选择其中的元素的顺序为为线索，构建二叉树。
具体而言就是，可以先选1，在选择1的基础上再去选第二个数；也可以先选其他的数，再在这个基础上去选接下来的数。
这样，树的第一层为根节点，啥也不选，第二层为所有的数，因为第一数字的选择是都有可能的。
再往下推断，每次可选的数字数量都比上一次少一个，这就是所谓的要在这一次的选择的基础上去选择接下来的数。
这就构成了树，
我们需要一个递归函数去实现数字的排列，
函数参数是第一个要选择的第一个数的数组下标，
在函数中递归填剩下的数。
递归的出口就是当填了最后一个数后，也就是走到死胡同的时候，就可以输出数组模拟的栈里面的元素了。
提一句，我们这里的栈是用两个数组来模拟，一个数组放元素，另一个数组放元素的状态，即是否被入栈或出栈。
当未到达死胡同时，遍历所有元素，找未入栈的，进行入栈，修改状态，再去找下一个数，也可以说是找下一个岔路口。
这样出口和路线都设计好了，只等程序执行了。
这里巧妙地使用了存入数组地下标作为判断条件，也使用全局变量，去减少了函数地参数，否则，那个n，还需要加入到参数队列里去。



*/
void dfs(int w) {
    if (w == n) {
        for (int i = 0; i < n; i++)printf("%d ", path[i]);
        printf("\n");
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (flag[i] == 0) {
            flag[i] = 1;
            path[w] = i;
            dfs(w + 1);
            flag[i] = 0;
        }
    }

}
int main() {

    cin >> n;
    dfs(0);

    return 0;
}

//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

题目描述

blablabla

样例

#include<iostream>
#include<string>
using namespace std;

/*
思考过程：
自我思考：
这个题简单地说就是找到一个指定字符c与字符g之间最大的间隔值。

首先这是一个需要循环的字符串，我的思路是，是使用双指针，
前指针i遍历每一个字符，直到找到指定的字符c。哦，再者之前我先对c进行一个判断如果c=‘g’就可以直接输出为0了。
接着说，当找到一个字符c时，就启用后指针j，j=i，接着往前走，并不断记数，直到遇到一个g，此时就是一个间隔值，并与上一个间隔值比较留最大值。
这其中最需要注意的就是，当j指向字符串最后一位，且不为g时，需要循环到字符串的开头，所以当j=n-1时需要j=0；这个操作。
一个操作后，i接着遍历，找下一个字符c，直到字符串的末尾。
这个思路通过了四个案例，但第五个案例超时了。
尝试改变思路，打算采用预处理的方式，在一个一个字符输入的时候，去对每个字符进行处理，但是我发现当我找到一个指定字符c时，它后面的字符还没输入，
我就不知道怎么去记数了。
到此思索失败。
查看题解代码后：
我发现与我二次思考的方式类似，对字符串进行遍历，但没有那种类似回溯的行为，时间复杂度应该为On，
它有新的东西就是对字符串进行了处理，即将字符串复制再连接上，达到循环的效果。
再者就是它设置了一个开关，当遇到指定字符时就打开，遇到g时就关闭，并处理间隔值。
最终思路：
输入字符串后，复制原字符串进行拼接，达到循环字符串的效果。
设置开关flag，最大值max和计数器res。
再对指定字符进行判断是否为g。
对新字符串进行遍历，遇到指定字符就打开开关，遇到g就关闭开关，再对res和max进行处理，进行最大值的存储。
最后在开关打开时进行记数。
这里要注意计数器是每次找到指定字符时，都要初始化，不然就会出错。

*/
int main() {
    int t,n;
    char c;
    string s;
    cin >> t;
    while (t--) {
        cin >> n >> c >> s;
        s += s;
        if (c == 'g') {
            cout << 0 << endl;
            continue;

        }
        int flag = 0,res=0, max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == c)flag = 1;
            if (s[i] == 'g') {
                flag = 0;
                max = max > res ? max : res;
                res = 0;

            }
            if (flag == 1)res++;
        }
        cout << max << endl;
    }
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

题目描述

样例

#include<iostream>
#include<algorithm>
using namespace std;


/*
* 思考过程：
啊，可恶
这tm就是个数学规律题，我没找到，所以想暴力遍历来找，
但是我发现这样基本搞不出来，搞出来了时间复杂度也很惊人，虽然它数据范围很小。
最先我想先暴力地去做，我发现需要优先删除那些相同地数字，
这样剩下就都是不同地，就还可以操作剩下数字个数地操作次数。
但我觉得在优先删除地时候，如果两边的数相同，就暂时不删，接着遍历下去，
然后遍历第二个相同数字数大于1的数字，删除的时候，我发现可能会解除掉先前暂时不删的那个数窘境
，这样我就要回头再次遍历，去搞，不断的循环遍历，觉得时间复杂度很大，直接崩掉。
这就是没找到规律的后果。
我是在往具体的，细节处去想，其实我跳出，从整体上看，
我们可以看到，只要不是只存在两种数的循环，我们都可以找到切入点一个一个的去删除，操作数为n。
如果是那种特殊的，则我们没删一个，环会自己擦一个，
就是我们一次删俩，直到剩下最后俩数，才是一个一个的删的。
所以操作数为（n-2）/2+2；
*/
bool cmp(int a, int b) {
    return a > b;
}
int main() {
    int t, n,num;
    cin >> t;
    while (t--) {
        cin >> n;
        int arr[105] = { 0 };
        for (int i = 0; i < n; i++) {
            cin >> num;
            arr[num]++;
        }
        sort(arr, arr + 105, cmp);
        if (arr[0] + arr[1] == n)cout << (n + 2) / 2 << endl;
        else cout << n<<endl;
    }
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

题目描述

blablabla

样例

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
/*思考过程：
本体就是要找输入的字符串中是否存在两个长度为2的相同的字串。
咱们就是要想想怎么去检验原字符串中是否有这个特征。
我刚开始是希望用双指针去遍历每个字符。
但是我不知道string不能用scanf输入，会报错。导致出错。
最近练题也没遇到过使用string的，有点生疏。
接着说，我感觉到用双指针去找到两个相同的字符再看各自字符的后一位是否相等。
但是用while的时候我想不到好的条件，有想到使用两个while但是感觉时间复杂度太大而放弃。
我发现我思路是没什么问题的，但是现在每次我看见双for的我都想去用双指针，更准确地说是用acwing地那个模板去写，但是用不好。
导致心态崩塌。
最终思路：
对输入的字符串进行双指针遍历，双for的形式。
两指针间隔一个字符，保证前有个指针所指的的字符前有个字符与其形成长度为2的字串。
前指针遍历每一个字符，后指针与前指针间隔一个字符开始遍历直到倒数第二个字符，保证后指针所指字符后还有一个字符。
两个指针所指字符进行比较，满足条件即是YES否则为NO。

*/
int main() {
    int t, n;
    string st;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        cin >> st;
        bool flag = true;
        for (int i = 0; i < n; i++) {
            for (int j = i + 2; j < n - 1; j++) {
                if (st[i] == st[j] && st[i + 1] == st[j + 1]) {
                    printf("YES\n");
                    flag = false;
                    break;
                }

            }if (!flag)break;

        }   if (flag)printf("NO\n");
    }
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

//这里填你的代码^^


#include<iostream>
using namespace std;
const int N = 1e6+5;
int arr[N], qq[N];
/*
滑动窗口：
利用双指针维护一个区间，这个区间的长度固定，形似一个窗口
实质一个数组模拟的队列
通过出队入队维护窗口

本题思路：
两个数组。arr存数字，qq存数字的下标
qq就是一个队列
我们可以看出随着数字入队，当长度达到k值，就会开始出队，那时候，每入队一个就会相应出队一个。
暴力做法是当入队到k大小，就遍历窗口内的元素，找出最值
时间复杂度很大
利用滑动窗口，我们可以发现，当找最小值时，如果后入队的比前入队的小，在这个窗口内，前入队的值就没用了，一定不会选到它。
因为，随之出队的进行，小值在大值之后出队，大值是不会被选中的。
所以对于队尾元素比即将入队的值更大时，队尾元素可以被删掉，直到队空，或者队尾更小的情况。才入队当前元素。
对于窗口大小达到固定值k的判断，是在遍历所有元素时，根据元素下标与k值得差值是否小于队头元素下标来判断。
当元素下标达到k值时，就可以开始出队了，且最小值一定是对头。
我们可以发现，最终在队列中存在得元素都是具有单调性，否则是会被删去的，
找最小值，则为单调增。最大值为单调减

*/
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)scanf("%d", &arr[i]);

    int hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        if (hh <= tt && i +1-k > qq[hh])hh++;
        while (hh <= tt && arr[qq[tt]] >= arr[i])tt--;
        qq[++tt] = i;
        if (i >= k - 1)printf("%d ", arr[qq[hh]]);
    }
    printf("\n");
    hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        if (hh <= tt && i - k +1 > qq[hh])hh++;
        while (hh <= tt && arr[qq[tt]] <= arr[i])tt--;
        qq[++tt] = i;
        if (i >= k - 1)printf("%d ", arr[qq[hh]]);
    }
    return 0;
}

//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

include[HTML_REMOVED]

using namespace std;
int main() {
int t, n;
cin >> t;
/*
子序列和字串的区别：
子序列是，对于两个字符串a和b，如果a字符串减去若干个字符后，（这若干个字符不一定连续）
剩余字符的顺序不变形成的字符串等于字符串b，则字符串b是a的字符串
字串是原字符串中一段连续的字符组成的字符串。
理解了子序列的概念，我们就要改变这n个ban，操作一次最多改变两个ban，则可以根据n的奇偶性进行最少操作数的确定。
确定了操作数，还要确定操作的位置。
要进行子序列的限制，则要保证每个B之后没有子序列AN
那么就不能逐个的改变每个BAN，得采用两头操作，可以采用调换B和N
尽量保证把B朝序列得后方调，N往字符串得前部调。
这样，才能避免BAN的出现。
对于单个的BAN，直接内部的BN调换即可。

*/
while (t--) {
    cin >> n; //对BAN的个数进行奇偶判断。
    if (n % 2 == 0) {
        cout << n / 2 << endl;//偶数
        for (int i = 0; i < n/2; i++) {
            printf("%d %d\n", i * 3 + 1, n * 3-i*3);//从字符串的两端同时进行
        }
    }else {//奇数
        printf("%d\n", n / 2 + 1);
        for (int i = 0; i <n/2+1; i ++) {
            printf("%d %d\n", i * 3 + 1, n*3-i*3);//从两侧开始调换，最终定点在中间的那个。
        }

    }


}
return 0;

}