題源：【LGR-182-Div.4】洛谷入門賽 #22

A 瘋狂大減價

分析：兩張票的先后順序枚舉一下，求出最小值。

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n, k, ans;

int main(){
    cin>>n;
    int a = n, b = n;
    if(a >= 100) a -= 20;
    if(a >= 200) a -= 50;

    if(b >= 200) b -= 50;
    if(b >= 100) b -= 20;
    cout<<min(a,b);
    return 0;
}

具體分析發現，如果可以用第二張券，那么必然可以用第一張券；如果先用第一張，不一定可以用第二張，所以先用第二張。

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n, k, ans;

int main(){
    cin>>n;
    int b = n;
    if(b >= 200) b -= 50;
    if(b >= 100) b -= 20;
    cout<<b;
    return 0;
}

B ZngivaeL 的中考

分析：模擬，但是代碼可能較為麻煩，運用前綴和思想
s[0] -- 表示 A 的數量
s[1] -- 表示 A~B 的數量
s[2] -- 表示 A~C 的數量
s[3] -- 表示 A~D 的數量
之后怎么做，相信不用多說了吧！

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;

int main(){
    string s;
    while(cin>>s){
        int st[27]={0};
        for(int i=0; i<s.size(); i++) st[s[i]-'A'] ++;
        for(int i=1; i<4; i++) st[i] += st[i-1];

        if(st[1] >= 4 && st[0]>=1) cout<<"I'm so happy.";
        else if(st[2] >= 4) cout<<"This is ok.";
        else cout<<"Never give up.";
        cout<<endl;
    }
    return 0;
}

C 游樂場

分析：開數組模擬即可，其實還可以分析ans是否需要開 long long.

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N];

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

    int money = 0, ans=0;
    for(int i=1; i<=n; i++){
        int t = a[i] - a[i-1]; // 這段時間新增的零花錢
        if(money + t > 50) money = 50;
        else money += t;
        ans += money / 8, money %= 8;
    }
    cout<<ans;
    return 0;
}

D 吃蘋果

分析：
求最大最小的和就是答案

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N];

int main(){
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    int mx=a[1], mn=a[1];
    for(int i=1; i<=n; i++){
        mx = max(mx, a[i]);
        mn = min(mn, a[i]);
    }
    long long ans = 1ll * mx + mn;
    cout<<ans;
    return 0;
}

排序后，首尾求和就是答案，注意數據范圍，開 long long。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N];

int main(){
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    sort(a+1, a+1+n);
    long long ans = 1ll * a[1] + a[n];
    cout<<ans;
    return 0;
}

E 天上的氣球

分析：使用二維數組記錄即可;
這里可使用兩個二維數組，一個記錄 h，一個記錄 c;
也可以使用一個二維數組，但是每個元素是一個pair<int,int> 使用 first記錄 h， second記錄 c；
后面如果有更低的高度就更新。

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m,k;
pair<int,int> a[N][N];

int main(){
    cin>>n>>m>>k; int x,y,h,c;
    while(k--){
        cin>>x>>y>>h>>c;
        if(!a[x][y].second ||a[x][y].first > h)
            a[x][y] = make_pair(h, c);
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cout<<a[i][j].second<<" \n"[j==m];
    return 0;
}

F 神秘排列

分析：其實就是兩個問題的組合

問題1：元素 1~n是否都出現了，可以使用標記數組對出現元素進行標記；
問題2：\(\forall {i}, p[i]=a[i]\)，提醒：對于題目中的符號，代碼中最好不變，這樣思路更加清晰

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N], p[N], st[N];

int main(){
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=n; i++) {
        st[a[i]] = 1;
        p[a[i]] = i;
    }
    int s = 0;
    for(int i=1; i<=n; i++) {
        if(p[i] != a[i]) break;
        s += st[i];
    }
    cout<<(s == n ? "YES" :"NO");
    return 0;
}

G 道法考試

分析：其實就是看某寫元素是否出現，可以使用for查詢，但是效率低，可以利用set/map優化

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10, M=2e3+10;
int n,m,x, l[M];
set<int> se[N];
int main(){
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++){
             cin>>x; se[i].insert(x);
        }
    int ans = 0;
    for(int i=1; i<=n; i++){
        cin>>l[i];
        int t = 0;
        for(int j=1; j<=l[i]; j++) {
            cin>>x;
            t += se[i].count(x);
        }
        if(t == m) ans += 2;
    }
    cout<<ans;
    return 0;
}

H 非眾數

分析：將全部非空子串求出來，一個一個判斷。

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10, M=2e3+10;
int ans;
queue<string> q;

int main(){
    string s; cin>>s;
    for(int i=0; i<s.size(); i++)
        for(int j=i; j<s.size(); j++)
            q.push(s.substr(i, j-i+1));
    while(q.size()){
        s = q.front(); q.pop();
        int st[27] = {0}, mx = 0;
        for(int i=0; i<s.size(); i++){
            st[ s[i] -'a' ] ++;
            mx = max(mx, st[ s[i] - 'a']);
        }
        if(mx <= s.size() / 2) ans ++;
    }
    cout<<ans;
    return 0;
}