A - What a Beautiful Lake

题目链接：https://vjudge.net/contest/331813#problem/A

题意：

给出一串数字，该数字在环上，问你这个环构成的最长的上升或者下降连续子序列的长度

题解：

当时自己代码写错了，wa了几发才知道自己错在了没有考虑如果存在非递增和非递减的情况，其实解法就是将这个数组扩大二倍，从1到2n遍历，找寻最长的上升或者下降子序列的长度

#include <cstdio>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <string>
using namespace std;
#define ll long long
int a[205];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        if(n == 0){
            break;
        }
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            a[i+n] = a[i];
        }
        int ans = 0,ans1 = 0,ans2 = 0;
        for(int i=1;i<2*n;i++)
        {
            if(a[i] > a[i-1]){
                ans1++;
                ans = max(ans,ans1);
            }else{
                ans1 = 0;
            }

            if(a[i] < a[i-1]){
                ans2++;
                ans = max(ans,ans2);
            }else{
                ans2 = 0;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

B - What a Ridiculous Election

题目链接：https://vjudge.net/contest/331813#problem/B

题意：

给你一个五位数的数字，问你从12345变成这个数字最少需要几步，如果不可能，输出-1。只存在三种操作，第一种是可以将相邻的俩位数字调换，次数不限；第二种是将一个位置上的数字+1然后对10取模，次数仅限3次；第三种操作是将一个位置上的数字*2然后对10取模，次数仅限2次。

题解：

bfs(12345),定义一个三维数组dp[99999][3][2]，直接看代码更好懂

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
#define ll long long
const int maxx = 100005;
int a[maxx][4][3];
int ans[maxx];
struct node{
    int x;
    int k1,k2;
    int cnt;
};
queue<node> q;
int b[6];
int swapp1(int x,int pos)
{
    int sum = 0,k1 = 0,k2 = 1;
    pos = 5-pos+1;
    memset(b,0,sizeof(b));
    while(x){
        b[++sum] = x%10;
        x/=10;
    }
    swap(b[pos],b[pos+1]);
    for(int i=1;i<=5;i++){
        k1 += b[i]*k2;
        k2 *= 10;
    }
    return k1;
}
int swapp2(int x,int pos)
{
    int sum = 0,k1 = 0,k2 = 1;
    pos = 5-pos+1;
    memset(b,0,sizeof(b));
    while(x){
        b[++sum] = x%10;
        x/=10;
    }
    b[pos] = (b[pos]+1)%10;
    for(int i=1;i<=5;i++){
        k1 += b[i]*k2;
        k2 *= 10;
    }
    return k1;
}
int swapp3(int x,int pos)
{
    int sum = 0,k1 = 0,k2 = 1;
    pos = 5-pos+1;
    memset(b,0,sizeof(b));
    while(x){
        b[++sum] = x%10;
        x/=10;
    }
    b[pos] = (b[pos]*2)%10;
    for(int i=1;i<=5;i++){
        k1 += b[i]*k2;
        k2 *= 10;
    }
    return k1;
}
void bfs()
{
    memset(a,0x3f3f3f3f,sizeof(a));
    memset(ans,0x3f3f3f3f,sizeof(ans));
    node now;
    now.x = 12345,now.k1 = 0,now.k2 = 0,now.cnt = 0;
    a[12345][0][0] = 0;
    q.push(now);

    while(!q.empty())
    {
        node pre = q.front();
        q.pop();

        for(int i=2;i<=5;i++)
        {
            node now = pre;
            now.x = swapp1(now.x , i);
            now.cnt += 1;
            if(now.cnt >= a[now.x][now.k1][now.k2])
                continue;
            a[now.x][now.k1][now.k2] = now.cnt;
            q.push(now);
        }
        if(pre.k1 < 3){
            for(int i=1;i<=5;i++)
            {
                node now = pre;
                now.x = swapp2(now.x , i);
                now.cnt += 1;
                now.k1 += 1;
                if(now.cnt >= a[now.x][now.k1][now.k2])
                    continue;
                a[now.x][now.k1][now.k2] = now.cnt;
                q.push(now);
            }
        }
        if(pre.k2 < 2){
            for(int i=1;i<=5;i++)
            {
                node now = pre;
                now.x = swapp3(now.x , i);
                now.cnt += 1;
                now.k2 += 1;
                if(now.cnt >= a[now.x][now.k1][now.k2])
                    continue;
                a[now.x][now.k1][now.k2] = now.cnt;
                q.push(now);

            }

        }
    }
    for(int i=0;i<=99999;i++){
        for(int j=0;j<=3;j++){
            for(int k=0;k<=2;k++){
                ans[i] = min(ans[i] , a[i][j][k]);
            }
        }
    }
    return ;
}
int main()
{
    int n;
    bfs();
    while(~scanf("%d",&n))
    {
        if(ans[n] == 0x3f3f3f3f){
            printf("-1\n");
            continue ;
        }
        printf("%d\n",ans[n]);
    }
    return 0;
}

J - Counting Cliques

题目链接：https://vjudge.net/contest/331813#problem/J

题意：

给出一个无向图的n个点和m条边以及数字k，问你这个图里存在多少个k完全图。k完全图即无向图中有k个点，每俩个点之间都有一条边。

题解：

递归查找答案，从一个点出发，将这个点所有的相连的点都push进一个数组，然后接着重复之间的步骤，直到当数组大小等于k，且第k个点和前k-1个点都有连边，答案加1，第一次用数组当参数传，好像还挺好用的。。。

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <string.h>

using namespace std;
#define ll long long

int ans = 0, a[105][105];
vector<int> v[105];
int n,m,k;
void solve(int x,int b[],int siz)
{
    for(int i=1;i<siz;i++)
    {
        if(a[b[i]][b[siz]] != 1){
            return ;
        }
    }
    if(siz == k){
        ans++;
        return ;
    }
    for(int i=0;i<v[x].size();i++)
    {
        b[siz+1] = v[x][i];
        solve(v[x][i] ,b , siz+ 1);
    }
}
int main()
{
    int t,x,y;
    scanf("%d",&t);
    while(t--)
    {
        ans = 0;
        memset(a,0,sizeof(a));
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=n;i++){
            v[i].clear();
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            v[x].push_back(y);
            a[x][y] = a[y][x] = 1;
        }
        for(int i=1;i<=n;i++)
        {
            int b[12];
            b[1] = i;
            solve(i,b,1);
        }
        cout<<ans<<endl;
    }
    return 0;
}