头像

z林深时见鹿

中北大学




在线 


活动打卡代码 AcWing 1341. 十三号星期五

日期模拟

/*
日期模拟题,判断N年中每个月的13号的各个星期几出现的次数
按月累加天数
*/
#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
int months[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};  // 记录每个月的天数
int weekday[7];  // 记录星期 0代表星期日
int main()
{
    int n;
    cin>>n;
    int days = 0, year =1900;
    while(n--)  // n年
    {
        for(int i = 1; i <= 12; i++)  // 12个月
        {
            weekday[(days + 13)%7]++;  // 每月13号是星期几,进行累加
            days += months[i];
            if(i == 2) // 特判二月
            {
                if((year%4==0&&year%100!=0)||(year%400==0)) days++;
            }
        }
        year++;
    }
    for(int i = 1,j = 6; i <= 7; i++,j++) cout<<weekday[j%7]<<' ';
    cout<<endl;
    return 0;
}




活动打卡代码 AcWing 1208. 翻硬币

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
string a,b;
void turn(int i)
{
    if(a[i]=='*') a[i] = 'o';
    else a[i] = '*';
}
int main()
{
    int cnt = 0;
    cin>>a>>b;
    for(int i = 0; i <= a.size(); i++)
    {
        if(a[i]!=b[i])
        {
            turn(i);
            turn(i+1);
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}



/*
dfs 搜索顺序 枚举每个位置填哪些数
一共m个位置
(1 2 3) (1 3 2) (2 1 3) 为同一种组合
为了实现组合型枚举 
我们新开一个变量 start 
每次填完一个位置后,从 i+1 ~ n中选择数字
这样既保证了升序,又不会重复选择之前的数字
*/
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 25;
int st[N];
int res[N];
int n,m;
void dfs(int pos,int start)
{
    if(pos == m+1)
    {
        for(int i = 1; i <= m; i++)
        {
            cout<<res[i]<<' ';
        }
        cout<<endl;
        return ;
    }
    for(int i = start; i <= n; i++)
    {
        if(!st[i])
        {
            st[i] = 1;
            res[pos] = i;
            dfs(pos+1,i+1);  //下次从i+1开始选择数字填写
            st[i] = 0;
        }
    }
}
int main()
{
    cin>>n>>m;
    dfs(1,1);
    return 0;
}


活动打卡代码 AcWing 95. 费解的开关

在这里插入图片描述

在这里插入图片描述

枚举第一行的所有操作,确定第一行的所有状态

第一行共有 2^5=32种操作 对应 0~31 二进制(00000~11111)

只要第一行的状态固定下来以后,第二行的操作完全取决于第一行的状态

第二行的状态固定下来以后,第三行的操作完全取决于第二行的状态

依次类推

,,,,,,

如果最后一行中有灭着的灯,说明当前方案不合法,否则当前方案合法,我们进行更新答案

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 6;
char g[N][N], backup[N][N];
int dx[5] = { -1,0,1,0,0 };
int dy[5] = { 0,1,0,-1,0 };
void turn(int x, int y)
{
    for (int i = 0; i < 5; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;
        g[a][b]='1'-(g[a][b]-'0');  //改变现有的状态
    }
}
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int res = 10;
        for (int i = 0; i < 5; i++) cin >> g[i];
        for (int op = 0; op < 32; op++)  // 枚举第一行所有的操作
        {
            int step = 0;
            memcpy(backup, g, sizeof g);  //复制备份
            for (int i = 0; i < 5; i++)  //确定第一行的状态
            {
                if (op >> i & 1)
                {
                    step++;
                    turn(0, i);
                }
            }
            for (int i = 0; i < 4; i++) //递推确定后4行的状态
            {
                for (int j = 0; j < 5; j++)
                {
                    if (g[i][j] == '0')
                    {
                        step++;
                        turn(i + 1, j);
                    }
                }
            }
            bool dark = false;
            for (int i = 0; i < 5; i++)
            {
                if (g[4][i] == '0')
                {
                    dark = true;
                    break;
                }
            }
            if (!dark)  res = min(res, step);
            memcpy(g, backup, sizeof g); //还原备份
        }
        if (res <= 6) cout << res << endl;
        else cout << "-1" << endl;
    }
    return 0;
}



活动打卡代码 AcWing 717. 简单斐波那契

/*
 递推式 a[i] = a[i-2] + a[i-1] 
*/
#include<iostream>
using namespace std;
const int N = 50;
int a[N];
int main()
{
    a[1] = 0;   //边界
    a[2] = 1;
    int n;
    cin>>n;
    for(int i = 3; i <= n; i++) 
    {
        a[i] = a[i-1] + a[i-2];
    }
    for(int i = 1; i <= n; i++)
    {
        cout<<a[i]<<' ';
    }
    return 0;
}



在这里插入图片描述

/*
dfs 深度优先搜索
依次枚举每个位置放哪些数
*/
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 12;
int res[N]; //记录答案
int st[N];  //记录状态
int n;
void dfs(int pos)  // pos代表位置
{
    if(pos == n+1) 
    {
        for(int i = 1; i <= n; i++)
        {
            cout<<res[i]<<' ';
        }
        cout<<endl;
        return ;
    }
    for(int i = 1; i <= n; i++) //枚举所有的分支
    {
        if(!st[i])
        {
            res[pos] = i;
            st[i] = 1;
            dfs(pos+1);
            st[i] = 0;   //回溯
        }
    }
}
int main()
{
    cin>>n;
    dfs(1);  //从第一个位置开始搜索
    return 0;
}



在这里插入图片描述

// 从1到n,考虑每个点选或者不选
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 16;
int st[N];  //记录状态 为0表示还未考虑,为1表示选择,为2表示不选
int n;
void  dfs(int u)
{
    if(u == n+1)  //递归边界
    {
        for(int i = 1; i <= n; i++)
        {
            if(st[i]==1) cout<<i<<' ';
        }
        cout<<endl;
        return ;
    }
    // 两种选择
    st[u]=1;
    dfs(u+1);
    st[u]=0; //回溯

    st[u]=2;
    dfs(u+1);
    st[u]=0; //回溯
}
int main()
{
   cin>>n;
   dfs(1);
   return 0;
}



什么是双指针算法?

简介
双指针算法应用非常广泛,而它能够拿出来作为一种效率较高的算法是因为它和普通的暴力搜索相比,为组合项固定了一些顺序,直接排除了一些组合选项。其思路就是,每次两个指针里面,一个指针负责循环遍历,另一个指针负责检查条件,配合。
模板

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}
常见问题分类:
    (1) 对于一个序列,用两个指针维护一段区间
    (2) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作

使用条件有哪些?

能用双指针算法的地方一定可以暴力求解,我们先想出一个暴力解法,再考虑使用双指针算法优化。如果可以用双指针来维护一段区间,那么这段区间一定要是单调的。因为只有满足单调性,我们才可以为组合项固定一些顺序,直接排除了另一些组合选项。

解题思路

对于这道题,先想出暴力解法。

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < i; j++)
    {
        if (a[i] + a[j] == m) //更新答案
        {

        }
    }
}

时间复杂度为 O(n^2) 很容易超时。

考虑双指针算法优化

先将数组排序,使它有序

然后定义两个指针i,ji指向数组开头,j指向数组结尾。
在这里插入图片描述

当两个指针未相交,并且a[i]+a[j]>m 说明 a[j]取大了,向左移动j指针,使其两数之和a[i] +a[j]减小。 即执行 while (i<j&&a[i] + a[j]>m) j--; 直到a[i]+a[j]<=m 退出循环 。

然后判断 a[i] +a[j] 是否等于 m ,若不等于,说明 a[i]取小了,向右移动i指针 ,使两数之和a[i] +a[j]增大。

继续上述操作 直到 a[i] +a[j] ==m时,我们记录答案。

    sort(a, a + n);
    for (int i = 0, j = n - 1; i < j; i++)
    {
        while (i<j&&a[i] + a[j]>m) j--;
        if (i < j&&a[i] + a[j] == m)
        {
            //记录答案
        }
    }

由于i指针或者j指针只能向一个方向移动,因此i++或者 j--最多执行n次,时间复杂度为 O(n)

完整代码

代码1

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int w[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &w[i]);
    sort(w, w + n);

    for (int i = 0, j = n - 1; i < j; i ++ )
    {
        while (i < j && w[i] + w[j] > m) j -- ;
        if (i < j && w[i] + w[j] == m)
        {
            printf("%d %d\n", w[i], w[j]);
            return 0;
        }
    }

    puts("No Solution");
    return 0;
}


如果你不习惯这种写法的话,这里提供了另一种写法, 思路是一样的。

代码2

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int a[N];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)  cin >> a[i]; 
    sort(a, a + n); //排序
    int l = 0; int r = n - 1; //定义两个指针
    int v1, v2,flag = 0;
    while (l < r) 
    {
        if (a[l] + a[r] > m)        r--; 
        else if (a[l] + a[r] < m)   l++; 
        else if (a[l] + a[r] == m)   //记录答案
        {
            cout << a[l] << " " << a[r] << endl;
            return 0;
        }
    }
    cout << "No Solution" << endl;
    return 0;
}




活动打卡代码 AcWing 1532. 找硬币

两数之和的变化版

/*
思路:类似于力扣的第一题,两数之和
步骤:
1. 定义一个hash[]数组 hash[数] = 下标
2.sort排序数组a
3. 从头到尾遍历数组a
4. another =  m - a[i]
5. 在原数组中寻找another,找到直接返回输出
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<unordered_map>
const int N = 1e5+10;
int a[N];
using namespace std;
int main()
{
    int n,m;
    unordered_map<int,int>hash;
    scanf("%d%d",&n,&m);
    for(int i = 0; i < n; i++) scanf("%d",&a[i]);
    int flag = 0;
    int v1=1e9,v2;
    sort(a,a+n);
    for(int i = 0; i < n; i++)
    {
        int another = m - a[i];
        if(hash.count(another))
        {
            if(another<v1) 
            {
                v1 = another;
                v2 = a[i];
                flag=1;
            }
        }
        hash[a[i]] ++; 
    }
    if(flag) printf("%d %d\n",v1,v2);
    else printf("No Solution\n");
    return 0;
}







新鲜事 原文

AcWing《蓝桥杯C++ AB组辅导课》拼团优惠!https://www.acwing.com/activity/content/introduction/19/group_buy/6660/ 差一人