HZOJ Logo 张义丰的博客

博客

面试笔试算法(上)听课笔记 04-24

2021-04-26 08:25:50 By 张义丰

OJ-477 元音字母

/*************************************************************************
    > File Name: 477.c
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sat 24 Apr 2021 06:43:11 PM CST
 ************************************************************************/

#include <stdio.h>
char s[105];
int main(){
    scanf("%s", s);
    int ans = 0, last = -1;//注意:因为字符串下标从0开始,所以这里初始值要为-1
    for (int i=0; s[i]; ++i){
        if (s[i]=='A' || s[i]=='E' || s[i]=='I' || s[i]=='O' || s[i]=='U'){
            if (last == -1){
                last = i;
            }else{
                if (ans < i-last) ans = i-last;
                last = i;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

【模拟】

OJ-479 乒乓球

/*************************************************************************
    > File Name: 479.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sat 24 Apr 2021 07:00:17 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int ans11[10005][2], ans21[5005][2], cnt11, cnt21;
void print(){
    for (int i=0; i<=cnt11; ++i){
        cout<<ans11[i][0]<<':'<< ans11[i][1] <<endl;
    }
    cout << endl;
    for (int i=0; i<=cnt21; ++i){
        cout<<ans21[i][0]<<':'<< ans21[i][1] <<endl;
    }
}
int main(){
    char s[30];
    while (cin >> s){
        for (int i=0; s[i]; ++i){
            if (s[i] == 'E'){
                print();
                return 0;
            }
            if (s[i] == 'W'){
                ans11[cnt11][0]++;
                ans21[cnt21][0]++;
            }else{
                ans11[cnt11][1]++;
                ans21[cnt21][1]++;
            }
            if ((ans11[cnt11][0] >= 11 || ans11[cnt11][1] >=11) && abs(ans11[cnt11][0]-ans11[cnt11][1]) >= 2) cnt11++;
            if ((ans21[cnt21][0] >= 21 || ans21[cnt21][1] >=21) && abs(ans21[cnt21][0]-ans21[cnt21][1]) >= 2) cnt21++;
        }
    }
    return 0;
}

OJ-480 保龄球

/*************************************************************************
    > File Name: 480.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sat 24 Apr 2021 08:38:59 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
struct node{
    char s[4];
    int num1, num2, flag;//num2:两次总分;flag:加分标记  0->无加分,1->加下一球分,2->加下两球分
};
node bl[15];
int n, ans;
int main(){
    while (cin >> bl[n].s) {
        if (bl[n].s[0] == '/'){
            bl[n].num1 = 10;
            bl[n].num2 = 10;
            bl[n].flag = 2;
        }else if (bl[n].s[1] == '/') {
            bl[n].num1 = bl[n].s[0] -'0';
            bl[n].num2 = 10;
            bl[n].flag = 1;
        }else {
            bl[n].num1 = bl[n].s[0] - '0';
            bl[n].num2 = bl[n].num1 + bl[n].s[1] - '0';
            bl[n].flag = 0;
        }
        n++;
    }
    for (int i=0; i<10; i++){
        ans += bl[i].num2;
        if (bl[i].flag == 1) {
            ans += bl[i + 1].num1;
        }else if (bl[i].flag == 2){
            if (bl[i+1].flag == 2){
                 ans += 10 + bl[i+2].num1;
            }else{
                ans += bl[i+1].num2;
            }
        }
    }
    cout << ans <<endl;
    return 0;
}

OJ-481 冰壶比赛

/*************************************************************************
    > File Name: 481.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sun 25 Apr 2021 07:03:03 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int r, a[10], b[10], sa, sb;
int main(){
    cin >> r;
    for (int i=0; i<10; ++i){
        cin >> a[1];
        if (a[1] == -1) break;
        int mina = a[1], minb = 0x7fffffff;
        for (int j=2; j<=8; ++j){
            cin >> a[j];
            mina = min(mina, a[j]);
        }
        for (int j=1; j<=8; ++j){
            cin >> b[j];
            minb = min(minb, b[j]);
        }
        if (mina == minb) {
            cout<<"0:0\n";
            continue;
        }
        int ta = 0, tb = 0;
        if (mina < minb && mina <= r){
            for (int j=1; j<=8; ++j){
                if (a[j]<=r && a[j]<minb){
                    ta ++;
                }
            }
        }else if (minb < mina && minb <= r){
            for (int j=1; j<=8; ++j){
                if (b[j]<=r && b[j]<mina){
                    tb ++;
                }
            }
        }
        cout<<ta<<':'<< tb <<endl;
        sa += ta, sb += tb;
    }
    cout<<sa << ':' << sb <<endl;
    return 0;
}

作业 :OJ-484 柱状统计图

/*************************************************************************
    > File Name: 484.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sun 25 Apr 2021 07:29:34 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int c[120];
string s;
int main(){
    while (cin >> s){
        for (int i=0; s[i]; ++i){
            if (s[i]>=65 && s[i]<=90){
                c[s[i]] ++;
            }
        }
    }
    int maxn = 0;
    for (int i=65; i<=90; ++i){
        maxn = max(maxn, c[i]);
    }
    for (int i=maxn; i>=1; --i){
        int last;//注意:题目要求每行末尾不能有多余空格,所以要算出每行最后一个*的位置
        for (int j=90; j>=65; --j){
            if (c[j]>=i){
                last = j;
                break;
            }
        }
        if (c[65]>=i) cout<<"*"; else cout<<" ";
        for (int j= 66; j<=last; ++j){
            if (c[j]>=i) cout<<" *";
            else cout<<"  ";
        }
        cout << endl;
    }
    for (int i=65; i<90; ++i){
        cout<<(char)i<<" ";
    }
    cout<<"Z\n";
    return 0;
}

OJ-485 均分纸牌

/*************************************************************************
    > File Name: 485.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sun 25 Apr 2021 07:41:05 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, a[105], sum, ave;
int main(){
    cin >> n;
    for (int i=1; i<=n; ++i){
        cin >> a[i];
        sum += a[i];
    }
    ave = sum / n;
    for (int i=1; i<=n; ++i){
        a[i] -= ave;
    }
    int ans = 0;
    for (int i=1; i<=n; ++i){
        if (a[i] != 0){
            a[i+1] += a[i];
            ans ++;
        }
    }
    cout << ans << endl;
    return 0;
}

【贪心】

作业:OJ-503 独木舟

/*************************************************************************
    > File Name: 503.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sun 25 Apr 2021 07:46:01 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, w, a[30005];
int main(){
    cin >> w >> n;
    for (int i=1; i<=n; ++i){
        cin >> a[i];
    }
    sort(a+1, a+n+1);
    int i=1, j=n, ans = 0;
    while (i <= j){
        if (a[j]+ a[i] <= w) i++;
        j--, ans ++;
    }
    cout << ans << endl;
    return 0;
}

OJ-504 删数

/*************************************************************************
    > File Name: 504.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sun 25 Apr 2021 07:51:46 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
string s;
int n;
int main(){
    cin >> s >> n;
    for (int i=0; i<n; ++i){
        int j=0;
        while (j<s.length()-1 && s[j] <= s[j+1]) j++;
        s.erase(j, 1);
    }
    while (s[0] == '0') s.erase(0, 1);//这里还有一个小bug,如果是0还是要输出0的
    cout << s << endl;
    return 0;
}

String s

s.replace(起始位置,长度,被替换成的内容)

OJ-505 最大整数

/*************************************************************************
    > File Name: 505.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sun 25 Apr 2021 08:07:32 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n;
string a[100005];
bool cmp(string x, string y){
    return x + y > y + x;//套路
}
int main(){
    cin >> n;
    for (int i=0; i<n; ++i){
        cin >> a[i];
    }
    sort(a, a+n, cmp);
    for (int i=0; i<n; ++i){
        cout << a[i];
    }
    cout << endl;
    return 0;
}

OJ-506 打热水

/*************************************************************************
    > File Name: 506.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sun 25 Apr 2021 08:17:36 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, sum, d;
struct node{
    int t, ind;
}a[35];
bool cmp(node x, node y){
    return x.t < y.t;
}
int main(){
    cin >> n;
    for (int i=0; i<n; ++i){
        cin>> a[i].t;
        a[i].ind = i+1;
    }
    sort(a, a+n, cmp);
    for (int i=0; i<n; ++i){
        i==0 || cout<<' ';//行尾不能有多余空格!
        cout << a[i].ind;
        sum += d;
        d += a[i].t;
    }
    printf("\n%.2lf\n", (double)sum/n);
    return 0;
}

OJ-508 两人过河

/*************************************************************************
    > File Name: 508.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sat 24 Apr 2021 06:26:48 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, num[1005], ans;
int main(){
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> num[i];
    }
    sort(num, num + n);
    for (int i=n-1; i>=0; i-=2){
        if (i==0){
            ans += num[i];
        }else if (i==1){
            ans += num[1];
        }else if (i==2){
            ans += num[1] + num[0] + num[2];
            break;
        }else{
            ans += min(num[i] + num[0] + num[i-1] + num[0], num[1] + num[0] + num[i] + num[1]);//1-传手电快; 2-过河快
        }
    }
    cout << ans<<endl;
    return 0;
}

OJ-509 智力大冲浪

/*************************************************************************
    > File Name: 509.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sat 24 Apr 2021 06:35:03 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
struct task{
    int deadline, money;
}t[505];
bool cmp(task x, task y){
    if (x.money != y.money) return x.money > y.money;
    return x.deadline > y.deadline;
}
int n, m, mark[505];
int main(){
    cin >> m >> n;
    for (int i=0; i<n; ++i){
        cin>>t[i].deadline;
    }
    for (int i=0; i<n; ++i){
        cin >> t[i].money;
    }
    sort(t, t+n, cmp);
    for (int i=0, j; i<n; ++i){
        for (j=t[i].deadline; j>=1; --j){
            if (!mark[j]){
                mark[j] = true;
                break;
            }
        }
        if (j==0){
            m -= t[i].money;
        }
    }
    cout << m <<endl;
    return 0;
}

优先完成扣钱多的,靠后完成

【枚举】

OJ-513 楼层编号

/*************************************************************************
    > File Name: 513.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sun 25 Apr 2021 08:57:38 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int m, t;
bool ok(int x){
    while (x){
        if (x % 10 == t) return false;
        x /= 10;
    }
    return true;
}
int main(){
    cin >> m >> t;
    int j = 0;
    for (int i=1; i<=m; ++i){
        if (ok(i)) j++;
    }
    cout << j << endl;
    return 0;
}

OJ-514 火柴棒等式

/*************************************************************************
    > File Name: 514.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sun 25 Apr 2021 09:40:03 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int num[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int n, ans;
int f(int x){
    if (x == 0) return 6;//注意特判!
    int t = 0;
    while (x){
        t += num[x%10];
        x /= 10;
    }
    return t;
}
int main(){
    cin >> n;
    for (int i = 0; i<1111; i++){
        for (int j=0; j<1111; j++){
            if (f(i) + f(j) + f(i+j) + 4 == n){
                ans ++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

实际只要枚举到700+即可

OJ-515 比例简化

/*************************************************************************
    > File Name: 515.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sun 25 Apr 2021 09:49:46 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int A, B, L, a, b;
int main(){
    cin >> A >> B >> L;
    double minn = 1e15, s, t = (double)A/B;
    for (int i=1; i<=L; ++i){
        for (int j=1; j<=L; ++j){
            if (__gcd(i,j) != 1) continue;//这个条件可以省略,因为在之前已经枚举过i/x, j/x
            s = (double)i/ j;
            if (s < t) continue;
            if (s-t < minn){
                minn = s-t;
                a = i, b = j;
            }
        }
    }
    cout << a << ' ' << b << endl;
    return 0;
}

OJ-516 奶牛碑文

前缀和

/*************************************************************************
    > File Name: 516.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sun 25 Apr 2021 10:10:56 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, a[100005], b[100005];
char s[100005];
long long ans;
int main(){
    cin >> n;
    scanf("%s", s+1);
    int len = strlen(s+1);
    for (int i=1; i<=len; ++i){
        if (s[i] == 'C') a[i] = a[i-1]+1; else a[i] = a[i-1];
      //上述代码可简化为:a[i] = a[i-1] + (s[i] == 'C');
    }
    for (int i=len; i>=1; --i){
        if (s[i] == 'W') b[i] = b[i+1]+1; else b[i] = b[i+1];
    }
    for (int i=1; i<=len; ++i){
        if (s[i] == 'O'){
            ans += (long long)a[i-1] * b[i+1];
        }
    }
    cout << ans <<endl;
    return 0;
}

OJ-517 三角形个数

/*************************************************************************
    > File Name: 517.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Mon 26 Apr 2021 07:59:47 AM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, ans;
int main(){
    cin >> n;
    for (int i=1; i*3<=n; ++i){
        for (int j=i; j*2+i<=n; ++j){
            if (i+j > n-i-j) ans ++;
        }
    }
    cout << ans << endl;
    return 0;
}

作业 :OJ-518 金币

/*************************************************************************
    > File Name: 518.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sun 25 Apr 2021 08:01:29 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int x, ans;
int main(){
    cin >> x;
    for (int i=1; x>0; ++i){
        if (i>x){
            ans += i*x;
            break;
        }else{
            ans += i*i;
            x -= i;
        }
    }
    cout << ans << endl;
    return 0;
}

可以用2个循环,1个循环,0个循环

OJ-519 优雅数

构造优雅数

/*************************************************************************
    > File Name: 519.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Mon 26 Apr 2021 08:09:32 AM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
long long L, R, ans;
int main(){
    cin >> L >> R;
    for (int i=0; i<10; ++i){ //枚举特殊数字
        for (int j=0; j<10; ++j){//枚举相同数字
            if (i == j) continue;
            for (int k=3; k<18; ++k){//枚举数字长度
                for (int l=1; l<=k; ++l){//枚举特殊数字的位置
                    if (i==0 && l==1 || j==0 && l!=1) continue;
                  //优化:if (j==0 && l!=1) break;
                    long long num = 0;
                    for (int p=1; p<=k; ++p){
                        if (p == l){
                            num = num*10 + i;
                        }else{
                            num = num*10 + j;
                        }
                    }
                    if (num >= L && num <= R) ans ++;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

思路不是自己的,代码中最好加注释

思路是自己的,忘了可以重新想出来

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。