2020年牛客アルゴリズム入門授業練習試合1補題

関連:大量のデータのk番目の小さい、幾何学的な傾き、円形の尺取り、離散化、差分制約、接頭辞と、シミュレーション.A第K小数はn個の数を意味して、第kの小さい要素を求めます.(n<=5 e 6)構想は直接sortタイムアウトする.速い列の思想を利用して、毎回1つの基準要素を選んで、小さい要素を左に置いて、大きい要素を右に置いて、左の要素の個数>=kならば、左からk番目を探すだけで、右は放っておくことができる;もしこの基準がちょうどk番目の小さい位置であれば、それでは直接この数を出力する;さもなくばk番目が小さいのは右にあるあ、右から(k-左の要素の個数)を探せばいいですが、左のものは直接放棄してソートする必要はありません.時間複雑度O(logn).

#include 
using namespace std;
const int maxn = 5e6 + 7;
typedef long long ll;
inline int read() {
    int sum=0; char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch))
        sum=sum*10+(ch^48),ch=getchar();
    return sum;
}
int a[maxn], n, k;
int getKth(int l, int r) {
    if(l == r) return a[l];
    int i = l, j = r;
    int mid = (l + r) / 2;
    int x = a[mid];
    while (i <= j) {
        while (a[i] < x) i++;
        while (a[j] > x) j--;
        if(i <= j) swap(a[i], a[j]), i++, j--;
    }
    if(k <= j) return getKth(l, j);
    else if(i <= k) return getKth(i, r);
    else return a[k];
}
int main()
{
    int t;
    t = read();
    while (t--) {
        n = read(), k = read();
        for (int i = 1; i <= n; i++) a[i] = read();
        printf("%d
", getKth(1, n));
    }
}

B平行でない直線はn点を意味し、2つの線分を尋ね、その中から最大何本を選び、2つの間は重なり合わず平行ではない.(n<=200)思考暴力の任意の2つの辺は、傾きを記録し、傾きが存在しない場合は答えに1を加え、存在する場合はスキップし、傾きが0と傾きが存在しないことに注意する.

#include 
using namespace std;
const int maxn = 1e5 + 7;
typedef long long ll;
struct node {
    int x, y;
}p[maxn];
int n;
map<int, map<int,int> > mp;// map       
int Gcd(int x, int y) {
    return !y ? x : Gcd(y, x % y);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d", &p[i].x, &p[i].y);
    int ans = 0;
    bool f = false, ff = false;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int y = p[i].y - p[j].y;
            int x = p[i].x - p[j].x;
            if(y == 0) {//   0  
                if(!ff) ans++;
                ff = true;
                continue;
            }
            if(x == 0) {//       
                if(!f) ans++;
                f = true;
                continue;
            }
            int gcd = Gcd(x, y);
            y /= gcd;
            x /= gcd;
            if(mp.count(y)) {
                if(!mp[y].count(x)) {
                    ans++;
                    mp[y][x] = 1;
                }
            }
            else {
                mp[y][x] = 1;
                ans++;
            }
        }
    }
    cout << ans << endl;
}

Cハンカチをなくしてn人で輪を作って、隣り合う二人の距離(円の上の距離)を与えて、最も遠い二人の間の距離を聞きます(円の上の距離).構想円の上で最も遠い距離は必ず周長sum/2を超えない.円の上で尺で取る方法.一人一人を挙げて、時計に沿って彼と最も遠い人との距離を計算し、tmpと記す.tmpがsum/2を超えなければ、tmpは前人から次の時計に乗る人の距離を加え、尺取り法に似ている.tmpがsum/2を超えた場合、さらに新しい答えはans=max(ans,min(tmp,sum-tmp))です.次の人を計算するときは、前の人から彼までの距離を減らします.

#include 
using namespace std;
const int maxn = 1e5 + 7;
typedef long long ll;
int n, a[maxn];
ll sum;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), sum += a[i];
    int tp = 1;
    ll tmp = sum / 2, maxx = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        while (maxx < tmp) {
            maxx += a[tp++];
            if(tp == n + 1) tp = 1;
        }
        ans = max(ans, min(maxx, sum - maxx));
        maxx -= a[i];
    }
    printf("%lld
", ans);
}

D二分問題には目標の数字があります.審判はあなたの数字が目標の数字に比べて高いのか低いのか、ちょうど目標の数字なのかを与えますが、審判の答えは必ずしも正しいとは限りません.そして、あなたが当てた数と審判の答えを出して、審判に最大何回正しい答えを言ったかを聞いてみましょう.(データ範囲がint以内)何の見当もつかない...仮に私が1つの数5を当てたとしたら、審判が低いと言って、審判が正しいとしたら、この目標数字は[6,max];仮にまた1つの8を当てて、審判が高いと言ったら、審判が正しいとしたら、この目標数字は[min,7];10を当てて、審判が低いと言ったら、目標数字は[11,max].問題は審判が最も多く何回答えを言ったかを問うもので、この3回当てたら、目標答えは[6,7]か[11,max]の時、審判が正しい答えを最も多く言った.解法が出てきて、審判の答えを一つの区間として表し、区間の数に1を加えると、一番多い数が審判が一番多い答えの回数になります.離散化後、差分コンストレイント+接頭辞和.

#include 
using namespace std;
const int maxn = 1e5 + 7;
typedef long long ll;
int n;
struct node {
    int o, x;
}p[maxn];
vector<int> v;
int getid(int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
int num[2 * maxn];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        char c;
        scanf("%d %c", &p[i].x, &c);
        if(c == '.') p[i].o = 3;
        else if(c == '+') p[i].o = 1, p[i].x--;
        else p[i].o = 2, p[i].x++;
        v.push_back(p[i].x);
    }
    sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());//   
    for (int i = 1; i <= n; i++) {
        if(p[i].o == 1) {
            num[1]++; num[getid(p[i].x) + 1]--;
        }
        else if(p[i].o == 2) {
            num[getid(p[i].x)]++; num[2 * maxn - 1]--;
        }
        else {
            num[getid(p[i].x)]++; num[getid(p[i].x) + 1]--;
        }
    }
    int sum = 0, ans = 0;
    for (int i = 1; i <= 2 * maxn; i++) {
        sum += num[i];
        ans = max(ans, sum);
    }
    printf("%d
", ans);
}

E交換問題はn個人が一列に並んでいることを意味し、一人一人に1つのシーケンス番号があり、n個のシーケンス番号を小さいから大きいまで並べて少なくとも何回交換するかを尋ね、交換は隣接しなくてもよく、与えられたシーケンス番号は連続しない可能性があり、シーケンス番号は唯一である.構想は4つの数字を仮定します:3 1 4 2第1の位置を並べ替えた後に1であるべきで、それでは1と3を交換して、第2の位置は2であるべきで、2と3を交換して、第3の位置は3であるべきで、3と4を交換します.これは最低の交換回数に違いない.シミュレーションプロセスでいいです.

#include 
using namespace std;
const int maxn = 5e6 + 7;
typedef long long ll;
int n, a[maxn], b[maxn];
map<int, int> mp, tp;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i], tp[a[i]] = i;
    sort (b + 1, b + 1 + n);
    for (int i = 1; i <= n; i++) mp[i] = b[i];
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if(a[i] != b[i]) {
            ans++;
            tp[a[i]] = tp[mp[i]];
            swap(a[i], a[tp[mp[i]]]);
        }
    }
    cout << ans << endl;
}