作业介绍

A 判断生肖

P3465判断生肖

  • 分析：当m≤1,d≤24m \leq 1, d \leq 24 是属于 PigPig，否则属于 MouseMouse。
  • 代码中使用了三目运算符号：(m==1 && d<=24) ? 表达式1：表达式2 当 m==1 && d<=24 成立，则执行表达式1，否则执行表达式2。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;

int main() {
    int m, d;
    cin >> m >> d;
    cout << (m == 1 && d < 25 ? "Pig" : "Mouse");
  
    return 0;
}

B 传输数据

P3529传输数据

  • 分析：新增收到数据的电脑数量变化：$1 \to 1*k \to (1+k)*k \to (1+k)*k^2 + (1+k)*k^3 ...$
  • 找到规律，令已收到数据的电脑数量为 s，则变化规律为：s += s * k；
  • 注意 s += s * k 爆 int。
  • 分析2：全部收到数据的电脑数量变化：1→(1+k)→(1+k)2→(1+k)3...1\to(1+k) \to (1+k)^2 \to (1+k)^3...
  • 找到规律：xx 秒后，已收到数据的电脑数量 s=(1+k)xs=(1+k)^x
  • x≥log(1+k)nx≥log_{(1+k)}^n
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;

int main() {
    int n, k, ans = 0;
    cin >> n >> k;
    LL s = 1;  // s表示已经收到数据的电脑数量
    while (s < n) {
        s += s * k;
        ans ++;
    }
    cout << ans;
    //cout <<(int)ceil(log(n)/log(1+k));
    return 0;
}

C 学习效率

P3606学习效率

  • 分析：需要求周围数据，那么必须将元素存放起来，使用二维数组 a[][] 存放元素，b[][] 记录答案；
  • 由于有八个方向，可以直接写，但是过于麻烦，考虑使用偏移数组 d[][]，其中 d[k][0] 表示行的偏移量，d[k][1] 表示列的偏移量，于是 int x = i + d[k][0], y = j + d[k][1]; 就可以求出(i,j) 的所有邻居 (x,y)，将其累加到 b[i][j] 即可。
  • 输出：程序中使用了 cout << b[i][j] << " \n"[j == n];
  • 其中 " \n"[j == n] 表示输出间隔为空格，最后一个输出换行符，具体介绍如下：
  • 如果 j==n 不成立那么就等于0 ，于是取" \n" 的下标为0的字符空格 ；
  • 如果 j==n 成立那么就等于1 ，于是取" \n" 的下标为1的字符 \n；
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 11, INF = 0x3f3f3f3f;
int n, a[N][N], b[N][N];
int d[][2] = {-1, -1, -1, 0, -1, 1, 0, -1, 0, 0, 0, 1, 1, -1, 1, 0, 1, 1};

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> a[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 0; k < 9; k++) {
                int x = i + d[k][0], y = j + d[k][1];
                b[i][j] += a[x][y];
            }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cout << b[i][j] << " \n"[j == n];
    return 0;
}

D 平衡数

P3566平衡数

  • 分析：对区间 [l,r] 元素进行查询，那么首先对其进行 for(i=l; i<=r; i++) 遍历
  • 由于 i 不能修改，于是构建一个临时变量 t，用于在循环中复制 i 并逐步分解其每一位。
  • st[]：一个大小为 10 的数组，用于记录数字 0-9 在当前整数中出现的次数。
  • 通过 while (t) st[t % 10]++, t /= 10; 记录数字 t%10 出现次数
  • 循环 0-9 判断该区间中的数字是否满足要求：出现的元素的出现次数 st[j] 为该数字 j 本身
  • 代码描述：st[j]>0 && st[j] == j 如果所有数字满足要求，那么最后 j=10，可以确定 i 是答案，将其累加到 ans。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 11, INF = 0x3f3f3f3f;

int main() {
    int l, r, ans = 0;
    cin >> l >> r;
    for (int i = l; i <= r; i++) {
        int t = i, st[10] = {0}, j;
        while (t) st[t % 10]++, t /= 10; // 记录数字出现次数
        for (j = 0; j <= 9; j++)
            if (st[j] && st[j] != j) break;
        if (j == 10) ans += i;// 当 j=10，那么i是要求的数
    }
    cout << ans;
    return 0;
}

E 文体两开花

P3602文体两开花

  • 分析：本题目的数据范围较大 n≤105,x≤109n\leq 10^5, x\leq 10^9；
  • 这里给出不同解法，希望大家好好理解
  • 解法1：代码中使用了 两个for 循环，复杂度为 n*m，会超时；
  • 解法2：在解法1的基础上优化，利用二分查找，可以通过；
  • 解法3：查询一个元素在一个序列中是否出现，可以使用数组标记，由于 xx 过大，可能下标越界；
  • 解法4：在解法3的基础上优化，由于 xx 过大，导致不能使用数组，可以利用map<int,int>；
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n, m, a[N], b[N], st[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];

    // 解法1：代码中使用了 两个for 循环，复杂度为 n*m，会超时；
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i] == b[j]) {
                cout << a[i] << " ";
                break;
            }
    cout << endl;

    // 解法2：在解法1的基础上优化，利用二分查找，可以通过；
    sort(b + 1, b + 1 + n);  // 二分必须在有序的基础上
    for (int i = 1; i <= n; i++) {
        int id = lower_bound(b + 1, b + 1 + n, a[i]) - b;  // >= a[i]
        if (b[id] == a[i])
            cout << a[i] << " ";
    }
    cout << endl;

    // 解法3：查询一个元素在一个序列中是否出现，可以使用数组标记，由于 x 过大，可能下标越界；
    // 如：st[x]=1 表示 x 出现过，但是一般要求 x 不能太打，毕竟下标有限
    for (int i = 1; i <= n; i++)
        st[b[i]] = 1;
    for (int i = 1; i <= n; i++)
        if (st[a[i]])
            cout << a[i] << " ";
    cout << endl;

    // 解法4：在解法3的基础上优化，由于数据x过大，导致不能使用数组，可以利用map<int,int>
    map<int, int> st;  // 局部变量屏蔽全局变量，不报错
    for (int i = 1; i <= n; i++)
        st[b[i]] = 1;
    for (int i = 1; i <= n; i++)
        if (st[a[i]])
            cout << a[i] << " ";
    cout << endl;
    return 0;
}

F 波兰表达式

P3170波兰表达式

  • 分析：前缀表达式（+ab）求值，由两种方式实现，递归 or 栈
  • 如下代码，使用递归实现的分析：
  • 因为数据一定是 + a b 的形式，其中 a b 也可以不断拆分为 +ab + ab 的形式，所以可以使用递归完成。
  • 递归函数：cal() 表示计算一个表达式 + a b 的值
  • double x = atof(s) 将字符数组转为小数
  • int n = strlen(s) 返回字符数组中元素数量
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;

// + a b，可以利用递归完成
double cal() {
    char s[33]; scanf("%s", s);
    if(s[0]=='-' && strlen(s)>1) return atof(s); // number
    switch (s[0]) {
        case '+': return cal() + cal();
        case '-': return cal() - cal();
        case '*': return cal() * cal();
        case '/': return cal() / cal();
        default : return atof(s); // number
    }
}
int main() {
    printf("%f\n", cal());
    return 0;
}

G 清除地雷

P3615清除地雷

  • 分析：由于当前元素的修改汇影响别的点位，所以可以考虑 dfs(x,y) 来修改 (x,y)
  • 需要注意的是数据给的是一串连续字符，那么就可以使用字符数组一行输入的形式，具体件代码。
  • 一般字符数组的使用下标会从0开始，主要是因为方便输入；
  • 那么对于的 x,y 就需要减少 1
  • 同样因为邻居较多，使用了偏移数组。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 110, INF = 0x3f3f3f3f;
int n,m;
char s[N][N];
int d[][2] = {-1, -1, -1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 0, 1, 1};

void dfs(int x,int y){
    s[x][y] = '2';
    for(int i=0; i<8; i++){
        int a=x+d[i][0], b=y+d[i][1];
        if(a<0||a>=n||b<0||b>=m) continue;
        if(s[a][b]=='1') dfs(a,b);
        s[a][b] = '2';
    }
}
int main() {
    cin>>n>>m;
    for(int i=0; i<n; i++) cin>>s[i];
    int x,y; cin>>x>>y;
    x--, y--;
    if(s[x][y]=='1') dfs(x,y);
    for(int i=0; i<n; i++) cout<<s[i]<<endl;
    return 0;
}

H 图论入门

P3616图论入门

  • 分析：使用二维数组存图（邻接矩阵），a[i][j] = w 表示有一条 x→yx \to y 的边权为 ww 的边。
  • 本问其实是三个小问题
  1. 入度：a[i][x] != 0 的数量为 x 的入度。
  2. 出度：a[x][i] != 0 的数量为x 的出度。
  3. 边数：a[i][j] != 0 的数量为图的边数。
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+1;
int n,m,a[N][N];

int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++) cin>>a[i][j];

    int du1=0, du2=0, ans=0;
    for(int j=1; j<=n; j++)  if(a[m][j]) du1 ++;// a[u][j] !=0
    for(int i=1; i<=n; i++)  if(a[i][m]) du2 ++;// a[i][u] !=0

    for(int i=1; i<=n; i++) // a[i][j] !=0
        for(int j=1; j<=n; j++) if(a[i][j]) ans ++;

    cout<<m<<" "<<du1<<" "<<du2<<endl;
    cout<<ans<<endl;
    return 0;
}

I 猴子分香蕉

P3667猴子分香蕉

  • 分析：

J 数组的距离

P3644数组的距离

  • 分析：

K 平方差(T2)

P3682平方差(T2)

  • 分析：

题目

题目
3465   判断生肖
3529   传输数据
3606   学习效率
3566   平衡数
3602   文体两开花
3170   波兰表达式
3615    清除地雷
3616   图论入门
3667   猴子分香蕉
3644   数组的距离
3682   平方差(T2)
状态
已结束
题目
11
开始时间
2024-5-19 0:00
截止时间
2024-5-27 23:59
可延期
24 小时
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  6. Worker 0, 44ms
  7. Powered by Hydro v4.18.0 Community