记录历年所有CCF CSP中的简单题 (第一题)

202203-1

未初始化警告

#include 
using namespace std;
const int N = 100010;

int n, k, res;
int l[N], r[N], map[N];

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= k; i ++ ) scanf("%d%d", &l[i], &r[i]);
    for (int i = i; i <= k; i ++ )
    {
        map[l[i - 1]] ++ ; // 记录左边第 i - 1 个位置上的变量被初始化
        if (r[i] && !map[r[i]]) res ++ ; // 特判一下当右边不是常数时则在 map 中寻找
    }
    cout << res << endl;
    return 0;
}

202112-1

序列查询

#include 
using namespace std;

int n, m, res;
int a[220];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) 
    {
        scanf("%d", &a[i]);
        res += (i - 1) * (a[i] - a[i - 1]); // 求出a[n]之前各项f(x)对应的值的和
    }
    printf("%d\n", res + (m - a[n]) * n); // 在最后加上a[n]右边各项f(x)对应的值直到边界m
    return 0;
}

202109-1

数组推导

#include 
using namespace std;
const int N = 100010;

int n, mx, mn;
int b[N], ma[N], mi[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);　//读入最大值数组
    ma[1] = b[1], mi[1] = b[1];
    for (int i = 2; i <= n; i ++ )
    {
        if (b[i] > b[i - 1]) ma[i] = b[i], mi[i] = b[i];　//分类讨论
        else ma[i] = ma[i - 1], mi[i] = 0;
    }
    for (int i = 1; i <= n; i ++) mx += ma[i], mn += mi[i]; // 求和
    cout << mx << endl << mn;
    return 0;
}

202012-1

期末预测之安全指数

#include 
using namespace std;
const int N = 200010;

int l[N], r[N], s[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> l[i] >> r[i];
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + l[i] * r[i];
    if (s[n] > 0) printf("%d", s[n]);
    else printf("0");
    return 0;
}

202009-1

称检测点查询

#include 
using namespace std;
const int N = 220;

int n, x[N], y[N], d[N], mn[3] = {-1, -1, -1}; // 使用mn数组来存放前三个最小路径的下标

int main()
{
    cin >> n >> x[0] >> y[0];
    for (int i = 1; i <= n; i ++ ) cin >> x[i] >> y[i];
    for (int i = 1; i <= n; i ++ ) d[i] = (x[0] - x[i]) * (x[0] - x[i]) + (y[0] - y[i]) * (y[0] - y[i]); // d数组中存放的是距离的平方
    for (int x = 0; x < 3; x ++ )
    {
        for (int i = 1 ; i <= n; i ++ ) 
            if (mn[x] == -1 || d[mn[x]] > d[i]) mn[x] = i; // 寻找最小值的下标
        d[mn[x]] = 1e7; // 如果找到就将这个最小值抹去，防止下次寻找干扰结果
        cout << mn[x] << endl;
    }
    return 0;
}

202006-1

线性分类器

#include 
using namespace std;
const int N = 1010;
typedef long long LL; // 两个1e6相乘会爆int，因此需要用到long long

int n, m, x[N], y[N];
char str[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) scanf("%d%d%s", &x[i], &y[i], &str[i]);
    while (m -- )
    {
        int a, b, c, A = 0, B = 0; // A和B用来计数属于A区域或B区域的每个点是否满足
        cin >> a >> b >> c;
        for (int i = 1; i <= n; i ++ ) // 这里只讨论A上B下的情况，另一种是对称的
        {
            if (str[i] == 'A' && a + (LL)b * x[i] + (LL)c * y[i] > 0) A ++ ;
            if (str[i] == 'B' && a + (LL)b * x[i] + (LL)c * y[i] < 0) B ++ ;
        }
        if (A + B == n || !(A + B)) puts("Yes"); // 如果能完美分割，计数之和要么为n，要么为0
        else puts("No");
    }
    return 0;
}

201912-1

报数

#include 
using namespace std;
const int N = 700;

int n, cnt[5];

bool check(int x)
{
    while (x)
    {
        if (x % 10 == 7) return true;
        x /= 10;
    }
    return false;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        if (i % 7 == 0 || check(i)) 
        {
            n ++ ;
            cnt[i % 4] ++ ;
        }
    }
    for (int i = 1; i <= 3; i ++ ) cout << cnt[i] << endl;
    cout << cnt[0] << endl;
    return 0;
}

201909-1

小明种苹果

#include 
using namespace std;
const int N = 1e6 + 10;

int q[N], s[N]; // s[i]表示第i颗树的蔬果量（负数）
int n, m, ini, all, mn = 1; // ini表示每棵树初始苹果数; all表示剩下的所有苹果; mn表示指向最小值的下标

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &ini);
        for (int j = 1; j <= m; j ++ ) 
        {
            scanf("%d", &q[j]);
            s[i] += q[j];
        }
        all += s[i] + ini;
    }
    for (int i = 2; i <= n; i ++ ) if (s[mn] > s[i]) mn = i; // 寻找最小值的下标（最小值对应的蔬果量最大）
    printf("%d %d %d", all, mn, -s[mn]);
    return 0;
}

201903-1 

小中大

#include 
using namespace std;
const int N = 1e7 + 10;

int n;
int q[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n ; i ++ ) scanf("%d", &q[i]);
    int l = 1, r = n;
    while (l < r) l ++ , r -- ;
    double mid = (q[l] + q[r]) / 2.0;
    if (mid == (int)mid) printf("%d %d %d\n", max(q[1], q[n]), (int)mid, min(q[1], q[n]));
    else printf("%d %.1f %d\n", max(q[1], q[n]), mid, min(q[1], q[n]));
    return 0;
}

201812-1

小明上学

#include 
using namespace std;

int n, r, y, g, lf, rt, res;

int main()
{
    cin >> r >> y >> g >>n;
    while (n -- )
    {
        cin >> lf >> rt;
        if (!lf || lf == 1) res += rt;
        if (lf == 2) res += rt + r;
    }
    cout << res << endl;
    return 0;
}

201803-1

跳一跳

#include 
using namespace std;
const int N = 33;

int cnt, sum, i = 1, h[N], res[N];

int main()
{
    while (i)
    {
        scanf("%d", &h[ ++ cnt]);
        if (!h[cnt]) i = 0;
    }
    for (int i = 1; i < cnt; i ++ )
    {
        if (h[i] == 2 && h[i - 1] != 2) res[i] = 2;
        else if (h[i] == 2) res[i] = 2 + res[i - 1];
        else res[i] = 1;
        sum += res[i];
    }
    cout << sum << endl;
    return 0;
}

201712-1

最小差值

#include 
#include 
using namespace std;
const int N = 1010;

int n, sum[N], q[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &q[i]);
    sort(q + 1, q + n + 1);
    for (int i = 2; i <= n; i ++ ) sum[i - 1] = q[i] - q[i - 1];
    sort(sum + 1, sum + n);
    cout << sum[1] << endl;
    return 0;
}

201709-1

打酱油

#include 
using namespace std;

int n, res;

int main()
{
    cin >> n;
    for (;n / 50; n %= 50) res += n / 50 * 7; // 能买5就买5
    for (;n / 30; n %= 30) res += n / 30 * 4; // 买完5以后能买3就买3
    cout << res + n / 10 << endl;             // 结果加上买1
    return 0;
}

201703-1

分蛋糕

#include 
using namespace std;
const int N = 1010;

int n, k, cnt, s;
int q[N];

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &q[i]);
    for (int i = 1; i <= n; i ++ )
    {
        s += q[i];
        if (s >= k)
        {
            cnt ++ ;
            s = 0;
        }
        
    }
    if (s) cnt ++ ;
    cout << cnt << endl;
    return 0;
}

201612-1

中间数

#include 
using namespace std;
const int N = 1010;

int q[N];

int main()
{
    int n, bg, sm; cin >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &q[i]);
    for (int i = 1; i <= n; i ++ )
    {
        bg = 0, sm = 0;
        for(int j = 1; j <= n; j ++ )
        {
            if (q[i] < q[j]) bg ++ ;
            if (q[i] > q[j]) sm ++ ;
        }
        if (bg == sm) 
        {
            cout << q[i] << endl;
            break;
        }
    }
    if (bg != sm) cout << "-1" << endl;
    return 0;
}

201609-1

最大波动

#include 
using namespace std;
const int N = 1010;

int n, mx, q[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &q[i]);
    for (int i = 1; i < n; i ++ ) mx = max(abs(q[i + 1] - q[i]), mx);  // 求差值并找到绝对值最大值
    cout << mx << endl;
    return 0;
}

201604-1

折点计数

#include 
using namespace std;
const int N = 1010;

int n, cnt, q[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &q[i]);
    for (int i = 2; i < n; i ++ ) 
    {
        if (q[i] > q[i - 1] && q[i] > q[i + 1]) cnt ++ ; // 下折点
        if (q[i] < q[i - 1] && q[i] < q[i + 1]) cnt ++ ; // 上折点
    }
    cout << cnt << endl;
    return 0;
}

201512-1

数位之和

#include 
using namespace std;

int n, s;

int main()
{
    cin >> n;
    for (; n; n /= 10) s += n % 10; // 只要n不为0,就取模除10
    cout << s << endl;
    return 0;
}

201509-1

数列分段

#include 
using namespace std;

int n, m, cnt; 

int main()
{
    cin >> n >> n; // 先读入n以后再读入数列的第一个值,方便拿来和m作比较
    while (cin >> m) n == m ? : cnt ++, n = m; // 从第二个值开始读入m,相同则继续,不同则计数加一
    cout << ++ cnt << endl; //最后加1的原因是主函数循环比较的时候没有计数序列第一个值的分段
    return 0;
}

201503-1

图像旋转

#include 
using namespace std;
const int N = 1010;

int n, m, q[N][N];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            scanf("%d", &q[i][j]);
    for (int j = m - 1; j >= 0; j -- )
    {
        for (int i = 0; i < n; i ++ )
            cout << q[i][j] << ' ';
        cout << endl;
    }
    return 0;
}

201412-1

门禁系统

#include 
using namespace std;
const int N = 1010;

int n, map[N];

int main()
{
    cin >> n;
    while (cin >> n) cout << ++ map[n] << ' ';
}

201409-1

相邻数对

#include 
#include 
using namespace std;
const int N = 1010;

int n, cnt, q[N],sub[N];

int main()
{
    
    cin >> n;
    
    for (int i = 1; i <= n; i ++ ) scanf("%d", &q[i]);
    
    sort(q + 1, q + n + 1);
    
    for (int i = 1; i < n; i ++ ) sub[i] = q[i + 1] - q[i];
    
    for (auto x : sub) if (x == 1) cnt ++ ;
    
    cout << cnt;
    
    return 0;
}

201403-1

相反数

#include 
using namespace std;
const int N = 1010;

int n, cnt, q[N], map[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) 
    {
        scanf("%d", &q[i]);
        if (q[i] < 0) map[-q[i]] ++ ;
    }
    for (int i = 1; i <= n; i ++ ) if (q[i] > 0 && map[q[i]]) cnt ++;
    cout << cnt;
    return 0;
}

201312-1

出现次数最多的数

#include 
using namespace std;
const int N = 100010;

int n, mx, q[N], map[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) 
    {
        scanf("%d", &q[i]);
        map[q[i]] ++ ;
    }
    for (int i = 1; i <= N; i ++ ) if (map[i] > map[mx]) mx = i;
    cout << mx;
    return 0;
}

算法

相关

如何实现LRU（最近最少使用）缓存淘汰算法？

2021.11.16（各排序算法对比）

react dom移动算法

算法第四章上机实验报告

算法第二章实践报告

【莫队算法】

算法第四章实践报告

关于tarjan算法的一些整理

【基础】排序算法学习笔记

常用的排序算法介绍和在JAVA的实现（一）

数据结构与算法之PHP查找算法（哈希查找）

数据结构与算法之PHP查找算法（二分查找）

标签