2022寒假每日一题（基础）

小记

不知不觉回家已经躺了好几天了，之前就说过，这个寒假不能废了，保研估计也要寄，麻了🤡。前几天刚搭好博客，我琢磨着那么就从刷题开始吧，一天一两道的样子，先刷基础题，开此贴记录。

指导思想

Untitled

1.6

104. 货仓选址 - AcWing题库

Untitled

核心思路：绝对值不等式

$\sum_{0}^{n}|x-a_{i}|$的最小值：先对数据排序，当数据个数n为奇数时，x = 中位数时取；否则x取中间两数之间任意均可（包括两数）

Untitled

代码：

#include <algorithm>

using namespace std;

const int N = 100005;

int n, res;
int a[N];

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

    sort(a, a + n);

    for (int i = 0; i < n; i ++ ) res += abs(a[i] - a[n >> 1]);
    printf("%d\n", res);

    return 0;
}

898. 数字三角形 - AcWing题库

题型：dp问题，依旧采用集合的方式,找到确定的集合（从下到上）

代码：

/** 898题
 * dp[i][j]表示从下到上到达i,j位置的路径最大值
 * dp[i][j] = max(dp[i+1][j],dp[i+1][j+1])+a[i][j]
 * 复杂度n^2
 **/
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    cin >>n;
    int a[n][n];
    for(int i = 0;i<n;i++)
    {
        for(int j = 0;j<=i;j++)
        {
            cin >>a[i][j];
        }
    }
    int dp[n][n];
    for(int i = 0;i<n;i++)
    {
        dp[n-1][i] = a[n-1][i];
    }
    for(int i = n-2;i>=0;i--)
    {
        for(int j = 0;j<=i;j++)
        {
            dp[i][j] = max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
        }
    }
    cout<<dp[0][0]<<endl;
    return 0;
}

1.7

AcWing 756. 蛇形矩阵 - AcWing

算法思想：模拟，网格题

收获：网格问题的技巧

(126条消息) c++二维数组声明及_F13253524870的博客-CSDN博客_c++怎么声明二维数组

Untitled

格子遍历技巧,用dx和dy遍历方向

Untitled

代码：

#include<iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
const int N = 110;
int q[N][N];//默认全是0
int main()
{
    cin >>n>>m;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    int x = 0,y = 0,d = 1;//用d来表示当前蛇头方向,1,2,3,0表示四个方向
    for(int i=1; i<=m*n;i++)
    {
        q[x][y] = i;
        int a = x + dx[d],b = y + dy[d];
        if(a<0||a>=n||b<0||b>=m||q[a][b])//q[a][b]表示已经填过数
        {
            d = (d+1)%4;//顺时针旋转90
            a = x + dx[d],b = y + dy[d];
        }
        x = a,y = b;
    }
    for(int i = 0;i<n;i++)
    {
        for(int j = 0;j<m;j++)
        {
            cout << q[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

1113. 红与黑 - AcWing题库

思想： flood fill算法：找网格图中的连通块(bfs,dfs)

收获：使用while(cin>>m)的用法

Untitled

//bfs版
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 25;
char q[N][N];
int m,n;
int bfs(int x,int y)//宽搜（需要队列）
{
    queue<PII> p;
    p.push({x,y});
    q[x][y] = '#';
    int res = 0;
    int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
    while(p.size())
    {
        auto t = p.front();
        p.pop();
        res ++;
        for(int i = 0;i<4;i++)
        {
            int a = t.first+dx[i];
            int b = t.second+dy[i];
            if(a<0||a>=n||b<0||b>=m||q[a][b]!='.')
                continue;
            p.push({a,b});
            q[a][b] = '#';
        }
    }
    return res;
}
int main()
{
    int res;
    while(cin>>m>>n,m||n)
    {
        int x,y;
        for(int i = 0;i<n;i++)
            cin>>q[i];
        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<m;j++)
            {
                if(q[i][j]=='@')
                {
                    x = i;
                    y = j;
                    res = bfs(x,y);
                }
            }
        } 
        cout<<res<<endl;
    }
    return 0;
}

dfs版

#include <iostream>

using namespace std;

const int N = 25;

int n, m;
char g[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int dfs(int x, int y)
{
    int res = 1;
    g[x][y] = '#';
    for (int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == '.')
            res += dfs(a, b);
    }
    return res;
}

int main()
{
    while (cin >> m >> n, n || m)
    {
        for (int i = 0; i < n; i ++ ) cin >> g[i];
        int x, y;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (g[i][j] == '@')
                {
                    x = i;
                    y = j;
                }
        cout << dfs(x, y) << endl;
    }

    return 0;
}

下面这种写法第一次见，用于输入多个数据集合，同时m,n同时为0时输入结束

Untitled

1.8

1346. 回文平方 - AcWing题库

核心思想：进制转换，数字，字符串转化

参考：如何将 a 进制的数直接转换成 b 进制的数？ (qq.com)

参考：(127条消息) C++数字与字符（串）转换_旧时光和任天堂的博客-CSDN博客_c++数字变字符

十进制转任意B进制(短除法)

char get(int x)//将x转换为字符形式，超过10时表示为A,很有必要
{
    if (x <= 9) return x + '0';
    return x - 10 + 'A';
}

string base(int n, int b)//将n转换为b进制，返回对应字符串
{
    string res;
    while (n)
    {
        res += get(n % b);
        n /= b;
    }
    reverse(res.begin(), res.end());//翻转回高位在左
    return res;
}

B进制转十进制

int uget(char c)
{
		if(c<='9') return c - '0';
		return c - 'A' + 10;
}
int change(string s ,int a)//a进制转化成十进制
{
    int res = 0;
    for(auto &x:s)
    {
        res = res*a+uget(x);
    }
    return res;
}

a转b进制(可以a→10,10→b)

略

题目代码：

//cpp#include <iostream>#include <cstring>#include <algorithm>using namespace std;char get(int x)//将x转换为字符形式{    if (x <= 9) return x + '0';    return x - 10 + 'A';}string base(int n, int b)//将n转换为b进制，返回对应字符串{    string res;    while (n)    {        res += get(n % b);        n /= b;    }    reverse(res.begin(), res.end());//翻转回高位在左    return res;}bool check(string s)//检查s是否是回文{    for (int i = 0, j = s.size() - 1; i < j; i ++, j -- )        if (s[i] != s[j])            return false;    return true;}int main(){    int b;    cin >> b;    for (int i = 1; i <= 300; i ++ )//暴力    {        string num = base(i * i, b);        if (check(num))            cout << base(i, b) << ' ' << num << endl;    }    return 0;}

680. 剪绳子 - AcWing题库

🤔思路：二分的思想，将最优化问题转化为简单的判断问题（巧妙）

收获：

Untitled

代码：

#include<iostream>#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 100010;int n,m;int w[N];bool check(double mid){    int cnt = 0;    for(int i = 0;i<n;i++){        cnt += w[i]/mid;    }    return cnt>=m;}int main(){    cin >>n>>m;    for (int i = 0; i < n; i ++ ){        cin >> w[i];    }    double l = 0,r = 1e9;    while(r-l>1e-4){//精度控制        double mid = (r + l)/2;        if(check(mid))            l = mid;        else            r = mid;    }    printf("%.2lf",l);    return 0;}

1.9

AcWing 1227. 分巧克力 - AcWing

核心：整数二分，思路和上一题类似
二分模板(本题用的是第二种)

bool check(int x) {/* ... */} // 检查x是否满足某种性质// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：int bsearch_1(int l, int r){    while (l < r)    {        int mid = l + r >> 1;        if (check(mid)) r = mid;    // check()判断mid是否满足性质        else l = mid + 1;    }    return l;}// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：int bsearch_2(int l, int r){    while (l < r)    {        int mid = l + r + 1 >> 1;        if (check(mid)) l = mid;        else r = mid - 1;    }    return l;}

注意：本题可能存在溢出，需要用long long
代码

#include <iostream>using namespace std;typedef long long LL;const int N = 100010;int n, m;int h[N], w[N];bool check(int mid){    LL res = 0;    for (int i = 0; i < n; i ++ )    {        res += (LL)h[i] / mid * (w[i] / mid);        if (res >= m) return true;    }    return false;}int main(){    scanf("%d%d", &n, &m);    for (int i = 0; i < n; i ++ ) scanf("%d%d", &h[i], &w[i]);    int l = 1, r = 1e5;    while (l < r)    {        int mid = l + r + 1 >> 1;        if (check(mid)) l = mid;        else r = mid - 1;    }    printf("%d\n", r);    return 0;}

AcWing 422. 校门外的树 - AcWing

核心：暴力/区间合并

算法1(模拟,数组遍历) O(ML)
定义一个长度为 L+1L+1 的布尔数组，表示每棵树的状态。

时间复杂度分析
对于每次移动树木的操作，最坏情况下区间长度是 O(L)，因此计算量是 O(L)，一共有 M次操作，因此总时间复杂度是 O(ML)=100×10000=106。

C++ 代码

#include<iostream>#include<algorithm>using namespace std;const int N = 10010;int L,m;int l[N],r[N];bool isremove[N];void remove(int l,int r){    for(int i = l;i<=r;i++)    {        isremove[i] = true;    }}int main(){    cin>>L>>m;//0-l上有树    for(int i = 0;i<m;i++)    {        cin>>l[i]>>r[i];//区间左右    }    for(int i = 0;i<m;i++)    {        remove(l[i],r[i]);    }    int res = 0;    for(int j = 0;j<=L;j++)    {        if(!isremove[j])            res++;    }    cout<<res<<endl;    return 0;}

算法2(区间合并) O(MlogM)
先求出所有移动树木的操作的区间的并集，那么马路上剩余部分即为最终剩下树木的部分。区间合并算法，可以看这里AcWing 803. 区间合并 - AcWing

C++ 代码#include <iostream>#include <algorithm>using namespace std;typedef pair<int, int> PII;const int N = 110;int n, m;PII seg[N];int main(){cin >> m >> n;for (int i = 0; i < n; i ++ ) 	cin >> seg[i].first >> seg[i].second;sort(seg, seg + n);int res = m + 1;int st = seg[0].first, ed = seg[0].second;for (int i = 1; i < n; i ++ )    if (seg[i].first <= ed) ed = max(seg[i].second, ed);    else    {        res -= ed - st + 1;        st = seg[i].first, ed = seg[i].second;    }res -= ed - st + 1;//最后一次cout << res << endl;return 0;}

1-10

429. 奖学金 - AcWing题库

思路：多关键字排序，运算符重载、比较函数

C++中定义比较函数的三种方法 - lengbingshy - 博客园 (cnblogs.com)

重载运算符写法

//429奖学金#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N = 310;int n;struct Person{    int id,sum,a,b,c;    bool operator <(const Person& t)     {        if(sum != t.sum)            return sum > t.sum;        if(a != t.a)            return a > t.a;        return id < t.id;    }}q[N];int main(){    cin >>n;    for(int i = 0;i<n;i++)    {        int a,b,c;        cin >>a>>b>>c;        q[i] = {i+1,a+b+c,a,b,c};    }    sort(q,q+n);    for(int i = 0;i<5;i++)    {        cout<<q[i].id<<' '<<q[i].sum<<endl;    }    return 0;}

比较函数写法

#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 310;int n;struct Person{    int id, sum, a, b, c;}q[N];bool cmp(Person& a, Person& b){    if (a.sum != b.sum) return a.sum > b.sum;    if (a.a != b.a) return a.a > b.a;    return a.id < b.id;}int main(){    cin >> n;    for (int i = 1; i <= n; i ++ )    {        int a, b, c;        cin >> a >> b >> c;        q[i] = {i, a + b + c, a, b, c};    }    sort(q + 1, q + n + 1, cmp);    for (int i = 1; i <= 5; i ++ )        cout << q[i].id << ' ' << q[i].sum << endl;    return 0;}

Untitled

1208. 翻硬币 - AcWing题库

思路：递归找思路，不断确定

代码

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

1-11

1532. 找硬币 - AcWing题库

思路：hash或者双指针
收获

unordered_set :集合（哈希表实现）

hash各种方法：包括count等

Untitled

(124条消息) C++ STL 之 unordered_set 使用（包括unordersd_map）_无痕眼泪的博客-CSDN博客_unordered_set

scanf读取规则，今天突然想到了，有点疑惑

Untitled

代码

//1521找硬币//我的初始代码,报tle/*#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N = 100010;int m,n;int a[N];bool getsum(int b){    for(int i = 0;i<m;i++)    {        if(a[i]!=b){            int c = a[i]+b;            if(c==n)            {                return true;            }        }    }    return false;}int main(){    cin >>m>>n;    for(int i = 0;i<m;i++)    {        cin >> a[i];    }    bool flag;    sort(a,a+m);    for(int j = 0;j<m;j++)    {        if(getsum(a[j]))        {            flag = true;            cout<<a[j]<<" "<<n - a[j]<<endl;            break;        }    }    if(!flag)    {        cout<<"No Solution"<<endl;    }    return 0;}*///ac代码之一(哈希表),O(n)#include<iostream>#include<cstring>#include<algorithm>#include<unordered_set>using namespace std;const int INF = 10000;int m,n;int main(){    cin >>m>>n;    int v1 = INF;    int v2;    unordered_set<int> hash;    for(int i = 0;i<m;i++)    {        int a,b;        cin >>a;        b = n-a;        if(hash.count(b))//hash表中是否有b        {            hash.insert(a);//插入a            if(a>b)swap(a,b);            if(a<v1) v1 = a,v2 = b;        }        else                hash.insert(a);    }    if(v1==INF) puts("No Solution");    else cout<<v1<<" "<<v2;    return 0;}//ac代码2，双指针 O(nlogn)#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--;//这里在排序后，求出w[i]+w[j]<=m的j的最大值        if(i<j&&w[i]+w[j]==m)        {            printf("%d %d\n",w[i],w[j]);            return 0;        }    }    printf("No Solution");    return 0;}

1-12

1381. 阶乘 - AcWing题库

思路：数论,数学推导，大数处理
这种题做之前建议手工推一下结果公式

/*#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 1e9;int n;int main(){    cin >>n;    long long res = 1;    for(int i = 1;i<=n;i++)    {        res *=i;        while(!(res%10))        {            res/=10;        }        res %= N;    }    cout << res%10<<endl;    return 0;}*///方法2#include <iostream>#include <cstring>#include <algorithm>using namespace std;int main(){    int n;    cin>>n;    int res = 1;    int a1=0,a2 = 0;    for(int i = 1;i<=n;i++)    {        int x = i;        while(x%2==0) x/=2,a1++;        while(x%5==0) x/=5,a2++;        res = res*x%10;    }    int k = min(a1,a2);    for(int i = 0;i<a1-k;i++) res = res*2%10;    for(int i = 0;i<a2-k;i++) res = res*5%10;    cout << res<<endl;    return 0;}

1-13

1353. 滑雪场设计 - AcWing题库

思路：贪心，数据不大就枚举
收获：javac编译，java运行
指定编码：javac -encoding utf-8 Test.java

Untitled

苦逼的上海之行

虽然看到了一直想去的大上海和外滩，5小时游遍上海（bushi）！

但是，14天隔离啊我超，也是一段人生经历吧

还是做一点题吧，隔离真是太苦逼了呜呜呜

哎，倒霉倒霉倒霉

1-14

1603. 整数集合划分 - AcWing题库

核酸结果出来后的第一题
思路：贪心

#include<iostream>#include<algorithm>using namespace std;const int N = 100010;int nums[N];int n;int main(){    cin>>n;    for (int i=0;i<n;i++) cin>>nums[i];    sort(nums,nums+n);    int index = n/2-1;    int left=0,right=0;    for (int i=0;i<=index;i++) left+=nums[i];    for (int i=index+1;i<n;i++) right+=nums[i];    cout<<n%2<<" "<<right-left<<endl;    return 0;}

# 1603整数集合划分n = int(input())nums = [int(num) for num in input().split()]nums.sort()if n%2:    index = (n-1)//2    val = sum(nums[index:]) - sum(nums[:index])    print("{} {}".format(1,val))else:    index = n//2    val = sum(nums[index:])-sum(nums[:index])    print("{} {}".format(0,val))

1-15

482. 合唱队形 - AcWing题库

思路：线性dp,最长上升子序列，比较简单

代码：

#include <iostream>#include <cstring>#include <algorithm>#include<cmath>using namespace std;const int N = 110;int a[N];/** if(a[i-1]<a[i]) * dp[i] = max(dp[i-1]+1,dp[i]) **/int dp[N];int get_uparr(int a[],int begin,int end){    for(int i = begin;i<=end;i++)    {        dp[i] = 1;        for(int j = begin;j<i;j++)        {            if(a[j]<a[i])            {                dp[i] = max(dp[i],dp[j]+1);            }        }    }    return dp[end];}int get_downarr(int a[],int begin,int end){    for(int i = end;i>=begin;i--)    {        dp[i] = 1;        for(int j = end;j>i;j--)        {            if(a[i]>a[j])            {                dp[i] = max(dp[j]+1,dp[i]);            }        }    }    return dp[begin];}int main(){    int n;    cin>>n;    for(int i = 0;i<n;i++)    {        cin>>a[i];    }    int res = N;    for(int j = 0;j<n;j++)    {        int d = get_uparr(a,0,j);//获取左边最长递增子序列长度(包括j)        int b = get_downarr(a,j,n-1);//获取右边最长递减子序列长度(包括j)        int c = n - (d+b-1);        res = min(res,c);    }    cout<<res<<endl;    return 0;}

收获

Untitled

420. 火星人 - AcWing题库

模拟
用到的一个技巧，stl中的next_permutation
(126条消息) 【用法总结】C++ STL中 next_permutation函数的用法_荷叶田田-CSDN博客_next_permutation

这里我们考虑一下next_permutation函数的原理，然后手动实现一遍。

Untitled

代码：

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 10010;int n, m;int q[N];int main(){    scanf("%d%d", &n, &m);    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);    while (m -- )    {        int k = n - 1;        while (q[k - 1] > q[k]) k -- ;        k -- ;        int t = k;        while (t + 1 < n && q[t + 1] > q[k]) t ++ ;        swap(q[t], q[k]);        reverse(q + k + 1, q + n);    }    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);    return 0;}

收获

Untitled

内置或者自定义函数都可以用map转换

Untitled

1-16

1015. 摘花生 - AcWing题库

简单dp

#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 110;int main(){    int t;    cin>>t;    for(int i = 0;i<t;i++)    {        int r,c;        cin >> r>>c;        int q[N][N];        for (int k = 0; k < r; k ++ )        {            for (int j = 0; j < c; j ++ )            {                cin >> q[k][j];            }        }        int dp[N][N];        dp[0][0]=q[0][0];        dp[0][1]=q[0][0]+q[0][1];        dp[1][0]=q[0][0]+q[1][0];        for (int k = 1; k < r; k ++ )        {            for (int j = 1; j < c; j ++ )            {                dp[k][j] = max(dp[k][j-1],dp[k-1][j])+q[k][j];            }        }        cout << dp[r-1][c-1]<<endl;    }    return 0;}

收获：push_back、push_front、insert简单运用

(126条消息) C++(7):push_back、push_front、insert简单运用_Leo的博客-CSDN博客_push_front函数

126. 最大的和 - AcWing题库

思路：递归问题（dp），将二维转化为一维
代码

//126最大的和//核心是将二维问题转化成一维前缀和最大#include<iostream>#include<algorithm>using namespace std;const int N = 110;int n;int s[N][N];int main(){    cin>>n;    for(int i = 1;i<=n;i++)    {        for(int j = 1;j<=n;j++)        {            int x;            cin>>x;            s[i][j]=s[i-1][j]+x;//s[i][j]表示i,j(x)上方向所有元素和，预处理        }    }    int res = -300;    for(int i = 1;i<=n;i++)    {        for(int j = i;j<=n;j++)        {            int f = 0;//f表示以w结尾的最大和            for(int k = 1;k<=n;k++)            {                int w = s[j][k] - s[i-1][k];//对每一列一段数求和，w就是同列的几个数之和                f = max(f,0)+w;                res = max(res,f);            }        }    }    cout<<res<<endl;    return 0;}

1-17

426. 开心的金明 - AcWing题库

思路：简单dp，可压缩

#include <iostream>#include <cstdio>using namespace std;const int N = 3e4 + 10,M = 30;int v[M], w[M];int f[M][N];int n, m;int main() {    cin >> m >> n;    for(int i = 1; i <= n; i++)  cin >> v[i] >> w[i];    for(int i = 1; i <= n; i++)     {        for(int j = 0; j <= m; j++)         {            f[i][j] = f[i-1][j];            if(j>=v[i]) f[i][j] = max(f[i][j], f[i-1][j-v[i]]+v[i]*w[i]);        }    }    cout << f[n][m] << endl; return 0;    }

考虑优化

状态计算时f[i]层的更新只用到了f[i-1]层,我们去掉前一维

状态计算方程为：

                                    $f[j] = max(f[j], f[j-v]+v*w)$

代码：

#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 30010;int f[N];int main(){    int n,m;    cin >> n>>m;    while(m--)    {        int v,w;        cin >> v>>w;        w = w*v;        for(int j = n;j>v;j--)        {            f[j] = max(f[j],f[j-v]+w);        }    }    cout<<f[n]<<endl;    return 0;}

703. 数独检查 - AcWing题库

大模拟

# 703数组检查def check_row(w,m):    for i in range(m):        st = [False]*40        for j in range(m):            if w[i][j]< 1 or w[i][j]>m:                return False            if st[w[i][j]]:                return False            st[w[i][j]] = True    return Truedef check_col(w,m):    for i in range(m):        st = [False]*40        for j in range(m):            if w[j][i]< 1 or w[j][i]>m:                return False            if st[w[j][i]]:                return False            st[w[j][i]] = True    return Truedef check_cell(w,m,n):    for i in range(0,m,n):        for j in range(0,m,n):            st = [False]*40            for dx in range(n):                for dy in range(n):                    t = w[i+dx][j+dy]                    if t<1 or t>m:                        return False                    if st[t]:                        return False                    st[t] = True    return Truedef main():    x = int(input())    for num in range(1,1+x):        n = int(input())        m = n*n        w = [list(map(int,input().split()))for i in range(m)]        if check_row(w,m) and check_col(w,m) and check_cell(w,m,n):            print("Case #"+str(num)+":Yes")        else:            print("Case #"+str(num)+":No")if __name__=="__main__":    main()

1-18

1101. 献给阿尔吉侬的花束 - AcWing题库

思路：
收获：声明global的python变量

Untitled

(129条消息) python global 用法_coder-CSDN博客_pythonglobal

Untitled

def bfs(start,q):    global x,y    dx = [-1,0,1,0]    dy = [0,1,0,-1]    queue = []    queue.append(start)    dist = [[-1 for i in range(200)]for i in range(200)]    dist[start[0]][start[1]] = 0    while len(queue)>0:        t = queue[0]        queue.pop(0)        for i in range(4):            nx = t[0]+dx[i]            ny = t[1]+dy[i]            if nx >=0 and nx<x and ny>=0 and ny<y and q[nx][ny] !='#' and dist[nx][ny] == -1:                dist[nx][ny] = dist[t[0]][t[1]]+1                if q[nx][ny] == 'E':                    return dist[nx][ny]                queue.append((nx,ny))    return -1n = int(input())for i in range(n):    x,y = map(int, input().split())    q = [list(input())for i in range(x)]    for i in range(0,x):        for j in range(0,y):            if q[i][j] == 'S':                start = (i,j)    res = bfs(start,q)    if res == -1:        print("oop!")    else:        print(res)

1-19

433. ISBN号码 - AcWing题库

思路：字符串大模拟，没啥难度，注意回顾string 和 char*的转换
注意输出

Untitled

#include<iostream>#include<cstring>using namespace std;int main(){    string s;    int a,b = 0;    cin >> s;    int n = s.size();    a = s[n-1] - '0';    for(int i = 0,j=1;i<n-1;i++)    {        if(s[i]!='-')        {            b+=(s[i]-'0')*j;            j++;        }    }    b = b%11;    if(b==10&&s.back()=='X')    {        cout<<"Right";    }    else if(b == a)    {        cout<<"Right";    }    else    {    s[n-1] = (b==10)?'X':(b+'0');    cout<<s<<endl;    }    return 0;}

c++ string的front()和back():

string a="abcd";1.获取字符串最后一个字符auto b=a.back(); //结果为 b='d';2.修改字符串最后一个字符a.back()='!'; //结果为 a="abc!";3.获取字符串第一个字符auto b=a.front(); //结果为 b='a';4.修改字符串第一个字符a.front()='!'; //结果为 a="!bcd";

不错的一篇博客：(129条消息) no match for ‘operator+’ (operand types are ‘basic_string‘ and ‘int’)_ddou_pan的博客-CSDN博客

Untitled

记住string的每一个元素都还是字符型，下面这么干可以

Untitled

428. 数列 - AcWing题库

思路和收获：将任何一个进制的数映射成一个二进制数，该位上有数为1，没数为0，终归是0，1问题，大小顺序不变

#include <iostream>#include <algorithm>using namespace std;typedef long long LL;LL get(int a, int b){    LL res = 1;    while (b -- ) res *= a;    return res;}int main(){    int n, k;    cin >> k >> n;    LL res = 0;    for (int i = 0; i < 20; i ++ )        if (n >> i & 1)            res += get(k, i);    cout << res << endl;    return 0;}

代码2

1	k,n = map(int, input().strip().split()) #k是底数，n是求得第几个数res = 0m = 0# 将十进制的n转换成2进制while n: res += (n%2)*pow(k, m) m = m+1 n = n//2print(res)

1-20

知识遗忘(129条消息) while(n–)和while(–n)_Mr_不二的博客-CSDN博客_while(n–)

Untitled

417. 不高兴的津津 - AcWing题库

思路：简单模拟

#include <iostream>#include <cstring>#include <algorithm>using namespace std;typedef pair<int, int> PII;int main(){    PII k = {0,0};    vector<PII> p ;    int n = 7;    while(n--)        {            int a,b;            cin >> a>>b;            int c = a+b;            if(c>8){                p.push_back({c,n-7});            }        }        if(!p.size())        {            cout << "0"<<endl;        }        else{            for(vector<PII>::iterator iter = p.begin();iter!=p.end();++iter)            {            k = max(*iter,k);            }            int res = -k.second;            cout << res<<endl;        }        return 0;}

425. 明明的随机数 - AcWing题库

思路：十分简单
收获：set, unique去重

Untitled

set详解 STL中的set容器的一点总结 - VincentPass - 博客园 (cnblogs.com)（自动出重排序）

unique：可以将序列中所有相邻的重复元素删除（只保留一个）。此处的删除，并不是真的删除，而是指重复元素的位置被不重复的元素覆盖了。最后会返回不重复序列的后一个位置。返回的是迭代器。

代码：

//set版#include<iostream>#include<set>using namespace std;int main(){    int n;    cin >> n;    set<int>res;    while(n--)    {        int x;        cin >> x;        res.insert(x);    }    cout<<res.size()<<endl;    for(auto x:res) cout<<x<<' ';    return 0;}

//unique版#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 110;int n;int q[N];int main(){    scanf("%d", &n);    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);    sort(q, q + n);    int k = unique(q, q + n) - q;    printf("%d\n", k);    for (int i = 0; i < k; i ++ ) printf("%d ", q[i]);    return 0;}

Untitled

非常好的而一篇博客：

(129条消息) C++ | C++入门总结（三）迭代器、数组_该用户还没想到好的昵称的博客-CSDN博客_c++迭代器数组

Untitled

1-21

458. 比例简化 - AcWing题库

思路：暴力枚举，没啥，注意做好类型转换
代码

#include <iostream>#include <cstring>#include <algorithm>using namespace std;int main(){    int A,B,L;    cin >> A>>B>>L;    int res1,res2;    double min = 1e9;    for(int i = 0;i<=L;i++)    {        for (int j = 1; j <= L; j ++ )        {            double x = (double)i/j;            double y = (double)A/B;            if(x>=y&&x-y<min)            {                min = x - y;                res1 = i,res2 = j;            }        }    }    cout<<res1<<' '<<res2;    return 0;}

445. 数字反转 - AcWing题库

emmm，简单题，过

#include <iostream>#include <cstring>#include <algorithm>using namespace std;int main(){    int n;    cin >> n;    if(n<0)    {        cout<<"-";        n = -n;    }    int res = 0;    while(n)    {        res =n%10+res*10;        n/=10;    }    cout<<res;    return 0;}

1-22

3208. Z字形扫描 - AcWing题库

思路：有些难度，不得不佩服y总真是tql，模拟题
不要被给的图的横线迷惑

Untitled

// https://www.acwing.com/problem/content/3211/#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>using namespace std;const int N = 510;int q[N][N];int main(){    int n;    scanf("%d",&n);    for(int i = 1;i<=n;i++)    {        for(int j = 1;j<=n;j++)        {            scanf("%d",&q[i][j]);        }    }    for(int i = 2;i<=2*n;i++)//此处i是行和列的总和    {        if(i%2==1)//行列和为奇数，则从上到下        {            for(int j = 1;j<i;j++)            {                if(j>=1&&j<=n&&i-j>=1&&i-j<=n)                {                    cout<<q[j][i-j]<<" ";                }            }        }        else{//否则行列和为偶数，从下到上            for(int j = i-1;j>=1;j--)            {                if(j>=1&&j<=n&&i-j>=1&&i-j<=n)                {                    cout<<q[j][i-j]<<" ";                }            }        }    }    return 0;}

3203. 画图 - AcWing题库

很简单，不比比

#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 110;int q[N][N];int main(){    int n;    cin >> n;    while(n--)    {        int x1,y1,x2,y2;        cin>>x1>>y1>>x2>>y2;        for(int i = x1+1;i<=x2;i++)        {            for(int j = y1+1;j<=y2;j++)                if(q[i][j]!=1)                    q[i][j]= 1;        }    }    int res = 0;    for(int i = 1;i<N;i++)    {        for (int j = 1; j <N;j ++ )        {            if(q[i][j] ==1)                res++;        }    }    cout << res;}

最后想说的

emmm，后面几题太过简单，索性一把做了，不再记录。这样一来寒假每日一题（基础）就做完了，总体感觉吧，c++stl用的已经比较熟练了，中间也脑子抽过有一些基本的语法还莫名其妙的忘了。 😅也记载了一些之前没记录的东西，还是有些收获的。
总感觉y总后面在放水，后面的题模拟比较多，不愧是入门，收获不大，保持手感而已。此次刷题总时长大概15天，40道题的样子，算法都比较基础，最难也就bfs，dfs这样的，（难的也做不出来是真的，寄！）
寒假快过半了，后面打算开刷提高组或者2022版，怎么说呢，不想开摆，中途也用python和java交过ac代码，毕竟加深熟练度，希望对考研/工作有用吧。
最后还得来一句,y总yyds!
截图纪念一下

Untitled