头像

世界2065




离线:16天前


活动打卡代码 AcWing 843. n-皇后问题

/*
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 11;
int n;
int state[N]={0};//第i列是否已经有皇后 state[j]=1=>第i列已经有皇后
int ans[N]={0};
bool check(int row,int column)
{
    for(int i=1;i<=row;i++)
    {   

        if(column+row==ans[i]+i) return false;//右斜向上
        if(row-column==i-ans[i]) return false;//左斜向上
    }
    return true;
}
void dfs(int u )//传入行
{

    if(u==n+1)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {   
                if(ans[i]==j)
                printf("Q");
                else
                printf(".");
            }
            printf("\n");
        }
        puts("");
        return;
    }
    for(int j=1;j<=n;j++)//对第u行遍历j列
    {
        if(state[j])
        continue;
        if(check(u,j))//左斜上对角线和右斜上对角线没有皇后
        {
            ans[u]=j;
            state[j]=1;
            dfs(u+1);
            state[j]=0; 
        }
    }
}

int main()
{
    cin>>n;
    dfs(1);
    return 0;
}
*/

#include<cstdio>
#include<ctime>
#include<iostream>
using namespace std;

int n;
int cnt = 0;//cnt存储方案个数
int ans[14] = {0};
int usedc[14] = { 0 };


bool check(int row, int column)
{
    int i;
    for (i = 1; i < row; i++)
    {
        if ((i + ans[i]) == row + column) return false;
        if ((i - ans[i]) == row - column) return false;
    }

    return true;
}

void dfs(int siden)
{
    if (siden == n + 1)
    {
        cnt++;
        for (int v = 1; v <= n; v++)
        {
            for(int x=1;x<=n;x++)
            {
                if(ans[v]==x)
                printf("Q");
                else
                printf(".");
            }
            printf("\n");
        }
        puts("");
        return;
    }
    for (int k = 1; k <= n; k++)
    {
        if (usedc[k])
            continue;
        if (check(siden, k))
        {

            ans[siden] = k;
            usedc[k] = 1;
            dfs(siden + 1);
            usedc[k] = 0;
        }
    }
}
int main()
{



    cin >> n;
    dfs(1);
    return 0;
}

未解之谜 为什么第一个代码(被注释掉了的)会跑不出来???



活动打卡代码 AcWing 842. 排列数字

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

const int N = 11;
int n;
int ans[N];
bool state[N];
void dfs(int u )
{
    if(u==n+1)
    {
        for(int i=1;i<=n;i++)printf("%d ",ans[i]);
        printf("\n");
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!state[i])
        {
            ans[u]=i;
            state[i]=true;
            dfs(u+1);
            state[i]=false;

        }
    }
}

int main()
{
    cin>>n;
    dfs(1);
    return 0;
}



活动打卡代码 AcWing 831. KMP字符串

#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    for (int i = 2, j = 0; i <= n; i ++ )
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }

    for (int i = 1, j = 0; i <= m; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }

    return 0;
}



活动打卡代码 AcWing 154. 滑动窗口

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n, k, q[N], a[N];//q[N]存的是数组下标
int main()
{
    int tt = -1, hh=0;//hh队列头 tt队列尾
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i = 0; i <n; i ++) cin>>a[i];
    for(int i = 0; i < n; i ++)
    {
        //维持滑动窗口的大小
        //当队列不为空(hh <= tt) 且 当当前滑动窗口的大小(i - q[hh] + 1)>我们设定的
        //滑动窗口的大小(k),队列弹出队列头元素以维持滑动窗口的大小
        if(hh <= tt && k < i - q[hh] + 1) hh ++;
        //构造单调递增队列
        //当队列不为空(hh <= tt) 且 当队列队尾元素>=当前元素(a[i])时,那么队尾元素
        //就一定不是当前窗口最小值,删去队尾元素,加入当前元素(q[ ++ tt] = i)
        while(hh <= tt && a[q[tt]] >= a[i]) tt --;
        q[ ++ tt] = i;
    }
    puts("");
    /*
    hh = 0,tt = -1;
    for(int i = 0; i < n; i ++)
    {
        if(hh <= tt && k < i - q[hh] + 1) hh ++;
        while(hh <= tt && a[q[tt]] <= a[i]) tt --;
        q[ ++ tt] = i;
        if(i + 1 >= k ) printf("%d ", a[q[hh]]);
    }
    */
    return 0;
}


活动打卡代码 AcWing 154. 滑动窗口

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n, k, q[N], a[N];//q[N]存的是数组下标
int main()
{
    int tt = -1, hh=0;//hh队列头 tt队列尾
    cin.tie(0);
    cin>>n>>k;
    for(int i = 0; i <n; i ++) cin>>a[i];
    for(int i = 0; i < n; i ++)
    {
        //维持滑动窗口的大小
        //当队列不为空(hh <= tt) 且 当当前滑动窗口的大小(i - q[hh] + 1)>我们设定的
        //滑动窗口的大小(k),队列弹出队列头元素以维持滑动窗口的大小
        if(hh <= tt && k < i - q[hh] + 1) hh ++;
        //构造单调递增队列
        //当队列不为空(hh <= tt) 且 当队列队尾元素>=当前元素(a[i])时,那么队尾元素
        //就一定不是当前窗口最小值,删去队尾元素,加入当前元素(q[ ++ tt] = i)
        while(hh <= tt && a[q[tt]] >= a[i]) tt --;
        q[ ++ tt] = i;
        if(i + 1 >= k) printf("%d ", a[q[hh]]);

        //printf("%d    %d\n",hh,tt);
        //for(int j=hh;j<=tt;j++)printf("~%d",a[q[j]]);
        //printf("\n");
    }
    puts("");
    hh = 0,tt = -1;
    for(int i = 0; i < n; i ++)
    {
        if(hh <= tt && k < i - q[hh] + 1) hh ++;
        while(hh <= tt && a[q[tt]] <= a[i]) tt --;
        q[ ++ tt] = i;
        if(i + 1 >= k ) printf("%d ", a[q[hh]]);
    }
    return 0;
}


活动打卡代码 AcWing 4. 多重背包问题

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int N=110;
int n,m;
int v[N],w[N],s[N]; //V体积 w价值 s个数
int f[N][N];//所有只从前i个物体里面选 且体积不大于j的时候的w最大值

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>s[i];//一行同时输入的v w
    for(int i=1;i<=n;i++) //物品
    {
        for(int j=1;j<=m;j++) //限制 本题是体积v 
        {   
            for(int k=0;k*v[i]<=j&&k<=s[i];k++)
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);

        }
    }
        cout<<f[n][m];
        return 0;
}


活动打卡代码 AcWing 3. 完全背包问题

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
/*
const int N=1010;
int n,m;
int v[N],w[N]; //V体积 w价值
int f[N][N];//所有只从前i个物体里面选 且体积不大于j的时候的w最大值

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];//一行同时输入的v w
    for(int i=1;i<=n;i++) //物品
    {
        for(int j=1;j<=m;j++) //限制 本题是体积v 
        {   
            for(int k=0;k*v[i]<=j;k++)
            //不选的情况一定存在 但选该物品的情况 不一定存在
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);

        }
    }
        cout<<f[n][m];
        return 0;
}


*/
//优化1-》类似01背包
//优化2 -》类似01背包问题的优化方法
const int N=1010;
int n,m;
int v[N],w[N]; //V体积 w价值
int f[N];//所有只从前i个物体里面选 且体积不大于j的时候的w最大值
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];//一行同时输入的v w
    for(int i=1;i<=n;i++) //物品
    {
        for(int j=v[i];j<=m;j++) //限制 本题是体积v 
        {   
                 f[j]=max(f[j],f[j-v[i]]+w[i]);//优化前的f【i】【x】是同一个i
        }
    }
        cout<<f[m];
        return 0;
}



活动打卡代码 AcWing 2. 01背包问题

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
/*
const int N=1010;
int n,m;
int v[N],w[N]; //V体积 w价值
int f[N][N];//所有只从前i个物体里面选 且体积不大于j的时候的w最大值

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];//一行同时输入的v w
    for(int i=1;i<=n;i++) //物品
    {
        for(int j=1;j<=m;j++) //限制 本题是体积v 
        {
            //不选的情况一定存在 但选该物品的情况 不一定存在
            f[i][j]=f[i-1][j];
            if(j>=v[i])//当体积可以装得下物品i的时候 选该物品的情况才存在
                f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    }
        cout<<f[n][m];
        return 0;
}
*/
//优化成1维数组:f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
//①f[i][x]这一层只用到了f[i],f[i-1] 更小的没用到 只有两层 所以用先-后 来记录这i-1 i
//②第二维度都小于等于j
const int N=1010;
int n,m;
int v[N],w[N]; //V体积 w价值
int f[N];//去掉第一位

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];//一行同时输入的v w
    for(int i=1;i<=n;i++) //物品
    {
        for(int j=m;j>=v[i];j--) //限制 本题是体积v 
        {
                f[j]=max(f[j],f[j-v[i]]+w[i]);//第一层小的先更新 所以,f[j-v[i]]+w[i]相当于是第[i-1]层的
        }
    }
        cout<<f[m];
        return 0;
}






//集合:f[i,j]//所有在A[1...i]和B[1...j]中都出现过 且以B[j]结尾的公共上升子序列的集合
//属性:max
//状态切割①f[i-1,j]
//②f[i-1,r]+1;
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;

const int N=3010;
int n;
int a[N],b[N];
int f[N][N];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);

    /*
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)//固定A
    {
        f[i][j]=f[i-1][j];//a[i]不在公共最长上升子序列里
        if(a[i]==b[j])
        {
            int maxn=1;
            for(int k=1;k<j;k++)
            {
                if(b[k]<a[i])maxn=max(maxn,f[i-1][k]+1);
            }
            f[i][j]=max(maxn,f[i][j]);
        }
    }
    */
    for(int i=1;i<=n;i++)
    //固定A
    {
        int maxv=1;
        for(int j=1;j<=n;j++)
        {
            f[i][j]=f[i-1][j];//a[i]不在公共最长上升子序列里
            if(a[i]==b[j])//a[i]==b[j]) a[i]可能在公共上升子序列里 
            {
                f[i][j]=max(maxv,f[i][j]);//不在和在了的比较
            }
            if(b[j]<a[i])maxv=max(maxv,f[i-1][j]+1);//若b[j]<a[i] 这是f【i,x】  
            //则b[j]可以在f[i,j]里 比较b[j]在与不在的大小
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans=max(f[n][i],ans);

    cout<<ans;
    return 0;
}


活动打卡代码 AcWing 187. 导弹防御系统

世界2065
1个月前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 55;

int n;
int a[N];
int up[N], down[N];
int ans;

void dfs(int u, int su, int sd)//当前搜索的下标u  上升子序列的长度su  下降子序列的长度sd
{
    if (su + sd >= ans) return;//剪枝 比已有的答案还大 不符合
    if (u == n)//遍历到最后一个数了 
    {
        ans = min(ans, su + sd);
        return;
    }
    //情况1 安排给上升子序列
    int k = 0;
    while (k < su && up[k] >= a[u]) k ++ ;
    if (k < su)//安排给第k个子序列
    {
        int t = up[k];//记录第k个子序列的最后一个数 up[k]
        up[k] = a[u];//更新为a[u]
        dfs(u + 1, su, sd);
        up[k] = t;
    }
    else//新开一个子序列
    {
        /*
        当前dfs中维护的区间下标是0 ~ su - 1和0 ~ sd - 1
        所以如果我们在下一层中修改下标是su或者sd的数,对当前dfs节点没有任何影响,所以不需要回溯。
        */
        up[k] = a[u];
        dfs(u + 1, su + 1, sd);
    }
    //情况2 安排给下降子序列
    k = 0;
    while (k < sd && down[k] <= a[u]) k ++ ;
    if (k < sd)
    {
        int t = down[k];
        down[k] = a[u];
        dfs(u + 1, su, sd);
        down[k] = t;
    }
    else
    {
        down[k] = a[u];
        dfs(u + 1, su, sd + 1);
    }
}

int main()
{
    while (cin >> n, n)
    {
        for (int i = 0; i < n; i ++ ) cin >> a[i];

        ans = n;//最差情况 每一个数都是一个子序列 答案为ans
        dfs(0, 0, 0);

        cout << ans << endl;
    }

    return 0;
}