牛客算法竞赛入门课第二节习题

Laptop

有问题可能是题目没看懂，就是假如有一台电脑的内存和速度都低于另一台，那么就是被完爆

所以我们只需要将电脑用其中一个属性从小到大排序，然后比较另一个属，只要另一个属性也比后面的更小，那么就是被完爆

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;

struct node{
    int x , y;
    bool operator <(node &b) const{
        return b.x > x;
    }
}a[MAXN];

int main(void){
    int n ; 
    cin>>n;
    for(int i = 1 ; i <= n ; ++i)
        cin>>a[i].x>>a[i].y;
    sort(a + 1 , a + n + 1);
    int ans = 0;
    // for(int i = 1 ; i <= n ; ++i)
    //     cout<<a[i].x<<" "<<a[i].y<<endl;
    for(int i = 1 ; i <= n ; ++i){
        for(int j = i + 1 ; j <= n ; ++j){
            if(a[i].y < a[j].y){
                ans++;
                break;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

大吉大利，今晚吃鸡

如果我们假设$n$个物品需要$f(n)$的话，那么对于过程来说

把个东西通过去，需要

把最大移动到，一步

把个东西通过去，需要

把最大移动到，一步

把个东西通过去，需要

合计 得到递推公式，

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;

int main(void){
    int n;
    while(cin>>n){
        cout<<pow(3 , n) - 1<<endl;
    }
    return 0;
}

简单的数据结构

直接stl就好了

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;
vector<int> v;

int main(void){
    int  n , m;
    scanf("%d%d", &n, &m);
    while(m--){
        int op , x;
        scanf("%d" , &op);
        if(op == 1){
            cin>>x;
            v.insert(v.begin() , x);
        }
        else if(op == 2){
            v.erase(v.begin());
        }
        else if(op == 3){
            cin>>x;
            v.push_back(x);
        }
        else if(op == 4){
            v.pop_back();
        }
        else if(op == 5){
            reverse(v.begin() , v.end());
        }
        else if(op == 7){
            sort(v.begin() , v.end());
        }
        else{
            cout<<v.size()<<endl;
            for(auto it = v.begin() ; it != v.end() ; ++it){
                printf("%d%c" , *it , it == v.end() - 1 ? '\n' :' ');
            }
        }
    }
    return 0;
}

栈和排序

要尽可能的让大的数字先输出来，

很容易就能知道如果比他后面的数字都大，那么我们在入栈之后立即让他出栈，则得到的序列一定比后出栈的序列更大

code

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int a[MAXN] , maxe[MAXN] , sta[MAXN] , top;

int main(void){
    int n;
    scanf("%d" , &n);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d" , &a[i]);
    for(int i = n ; i > 0 ; --i){
        maxe[i] = max(maxe[i + 1] , a[i]);
    }
    // for(int i = 1 ; i <= n ; ++i)
    //     cout<<a[i]<<" ";
    // cout<<endl;
    // for(int i = 1 ; i <= n ; ++i)
    //     cout<<maxe[i]<<" ";
    // cout<<endl;
    for(int  i = 1 ; i <= n ; ++i){
        sta[++top] = a[i];
        while(top && sta[top] > maxe[i + 1])
            printf("%d " ,sta[top--]);
    }
    return 0;
}

吐泡泡

这个题目，啊，一点都不难 ，但是我做了好久，一开始用stl的栈搞了半天做了好久

图片说明

最后还是手写的栈好用。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN  = 105;

int main(void){
    char st[MAXN];
    string s;
    while(cin>>s){
        int h = 0;
        for(int  i = 0 ; i < s.size() ; ++i){
            if(h == 0) st[++h] = s[i];
            else{
                if(st[h] == s[i]){
                    if(s[i] == 'O') h--;
                    else{
                        st[h] = 'O';
                        if(h > 1){
                            if(st[h - 1] == 'O') h-=2;
                        }
                    }
                }
                else st[++h] = s[i];
            }
        }
        for(int i = 1 ; i <= h ; ++i)
            cout<<st[i];
        cout<<endl;
    }
    return 0;
}

竞赛技巧

简单题 用结构体存 然后重载一下就好了

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN  = 5007;

struct node{
    int a , b , c;
    bool operator <(node &k) const{
        if(a == k .a){
            if(b == k.b)
                return c < k.c;
            return b < k.b;
        }
        return a < k .a;
    }
}s[MAXN];

int main(void){
    int n;
    cin>>n;
    for(int i = 1 ; i <= n ; ++i){
        cin>>s[i].a>>s[i].b>>s[i].c;
    }
    sort(s + 1 , s + n + 1);
    for(int i = 1 ; i <= n ; ++i){
        cout<<s[i].a<<" "<<s[i].b<<" "<<s[i].c<<endl;
    }
    return 0;
}

老子的全排列呢

STL真好看用。。。next_permutation 求下一个全排列

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(void){
    string s = "12345678";
    do{
        for(int  i = 0 ; i < 8 ; ++i){
            cout<<s[i];
            if(i != 7) cout<<" ";
        }
        cout<<endl;
    }while(next_permutation(s.begin() , s.end()));
    return 0;
}

逆序数

求逆序对 看了一眼大佬的博客 太秀了。。

x = 1e5 + 10 - x;使得越大的数字存的越靠前，所以用query记一下前面有多少个数就可以知道他的逆序对了

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(x) x&(-x)

const int MAXN = 2e5 + 10;

int sum[MAXN] , cnt = MAXN - 1;
void add(int x){
    while(x <= cnt){
        sum[x]++;
        x+=lowbit(x);
    }
}

int query(int x , int ans = 0){
    while(x){
        ans += sum[x];
        x -=lowbit(x);
    }
    return ans;
}

int main(void){
    int n;
    cin>>n;
    ll ans = 0;
    for(int i = 1 ; i <= n ; ++i){
        int x;
        cin>>x;
        x = 1e5 + 10 - x;
        ans += query(x - 1);
        add(x);
    }
    cout<<ans<<endl;
    return 0;
}

The Biggest Water Problem

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(void){
    ll n;
    cin>>n;
    while(n > 10){
        ll ans = 0;
        while(n){
            ans += n%10;
            n /= 10;
        }
        n = ans;
    }
    cout<<n<<endl;
    return 0;
}

小C的记事本

用c++自带的string就可以解决绝大多数问题

操作4我们可以用一个栈，（因为他是回溯到上一次修改字符串的操作）每一次操作都是将一个新的串压进去，然后需要回溯的时候，就只要把栈顶弹出去就好了

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 7;
stack<string> st;
string tmp;
int op , n , k;

int main(void){
    ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
    while(cin>>n){
        while(st.size()) st.pop();
        st.push(" ");
        while(n--){
            cin>>op;
            if(op == 1){
                cin>>tmp;
                st.push(st.top() + tmp);
            }
            else if(op == 2){
                cin>>k;
                tmp = st.top();
                tmp.erase(tmp.size() - k , k);
                st.push(tmp);
            }
            else if(op == 3){
                cin>>k;
                string temp = st.top();
                cout<<temp[k]<<endl;
            }
            else if(op == 4)
                st.pop();
        }
    }
    return 0;
}

分数线划定

有两个坑点：

1，最后如果划到的分数线的下一位和分数线相同，也应该被算进去

2，即有可能出现人不够，即的情况，特判一下即可

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5000 + 7;
struct node{
    int a,b;
    bool operator <(node &k) const{
        if(b == k.b) return a < k.a;
        return b > k .b;
    }
}s[MAXN];

int main(void){
    int n , m;
    cin>>n>>m;
    for(int i = 1 ; i <= n ; ++i)
        cin>>s[i].a>>s[i].b;
    sort(s + 1 , s + n + 1);
    int ans = m * 1.5;
    int i = ans + 1;
    while(s[ans].b == s[i].b && i <= n){
        ans++;
        i++;
    }
    if(ans > n){
        cout<<s[n].b<<" "<<n<<endl;
    }
    else{
        cout<<s[ans].b<<" "<<ans<<endl;
    }
    for(i = 1 ; i <= ans && i <= n; ++i){
        cout<<s[i].a<<" "<<s[i].b<<endl;
    }
    return 0;
}

FBI树

我的做法是先把这个字符串赋给底层的值，

然后向上维护树

然后然后，我是！我是！我是***

2的十次方的正确写法：1<<10 而不是 2^10

code

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int mod=1e9+7;
const int MAXN = 1<<10 +5;
char k[MAXN] ={0}, post[MAXN] = {0};
int cnt = 1;
void postorder(int i){
    if(k[i]){
        postorder(i * 2);
        postorder(i * 2 + 1);
        post[cnt++] = k[i];
    }
}

ll qpow(ll a , ll b){
    ll ans = 1;
    while(b){
        if(b & 1) ans = ans * a % mod;
        a = a*a % mod;
        b >>= 1;
    }
    return ans;
}

int main(void){
    string s = "";
    int n;
    cin>>n;
    cin>>s;
    for(int i = qpow(2 , n) , j = 0 ; j < s.size() ; ++i , ++j){
        if(s[j] == '1') k[i] = 'I';
        else k[i] = 'B';
    }
    //for(int i = 1 ; i <= 15 ;++i)
    //    cout<<k[i];
    //cout<<endl;
    for(int i = n - 1; i >= 0 ; --i){
        for(int j = qpow(2 , i) ; j < qpow(2 , i + 1) ; j++){
            if(k[2 * j] == k[2 * j + 1])
                k[j] = k[2 * j];
            else
                k[j] = 'F';
            //cout<<k[j]<<k[2 * j]<<k[2 * j + 1]<<j<<2 * j<<2 * j + 1<<endl;
        } 
    }
    //for(int i = 1 ; i <= 15 ;++i)
    //    cout<<k[i];
    //cout<<endl;
    postorder(1);
    for(int i = 1 ; i < qpow(2 , n + 1) ; ++i){
        printf("%c", post[i]);
    }
    cout<<endl;
    return 0; 
}

指纹锁

挺简单的一个题目 是我想复杂了

删除操作 如果x处没有指纹 那么久不会删除

再加上出现重合部分就不会录入

所以根本不存在出现一次删两个及以上的可能，只有可能被x处这个位置的指纹被删

然后我还模拟了半天 准备用线段树写。。。

实际上只需要一个简单的set重载一下就好了

code

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)

int n , k , x;
string s;
struct cmp{
    bool operator() (const int& a , const int& b) const {
        if(abs(a - b) <= k ) return false;
        return a < b;
    }
};

int main(void){
    js;
    cin>>n>>k;
    set<int , cmp> st;
    while(n--){
        cin>>s>>x;
        if(s == "add") st.insert(x);
        else if(s == "del") st.erase(x);
        else{
            if(st.find(x) != st.end()) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

新建 Microsoft Office Word 文档

用两个set进行操作，一个保存已经建立了的，另一个保存删除了的

每一次New就先看看有没有之前删除了，有的话就先建立那个，没有再继续往后新建

code

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;

int main(void){
    int  n;
    set<int> st1,st2;
    int i = 0 , j = 0;
    cin>>n;
    while(n--){
        string s; 
        cin>>s;
        if(s == "New"){
            i++;
            if(st2.empty()){
                cout<<i - j<<endl;
                st1.insert(i - j);
            }
            else{
                st1.insert(*st2.begin());
                cout<<*st2.begin()<<endl;
                st2.erase(st2.begin());
            }
        }
        else{
            int k;
            cin>>k;
            if(st1.find(k) != st1.end()){
                st1.erase(k);
                cout<<"Successful"<<endl;
                st2.insert(k);
                j++;
            }   
            else cout<<"Failed"<<endl;
        }
    }
    return 0;
}

区区区间间间

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100005];
int l[100005],r[100005],n,ans;
void solve() {
    for(int i=1;i<=n;++i) {
        int j=i;
        while(j>1&&a[j-1]<=a[i])
            j=l[j-1];
        l[i]=j;
    }
    for(int i=n;i;--i) {
        int j=i;
        while(j<n&&a[j+1]<a[i])
            j=r[j+1];
        r[i]=j;
    }
    for(int i=1;i<=n;++i) {
        ans+=a[i]*(r[i]-l[i]);
        ans+=a[i]*(i-l[i])*(r[i]-i);
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t;
    cin>>t;
    while(t--) {
        cin>>n;
        ans=0;
        for(int i=1;i<=n;++i) cin>>a[i];
        solve();
        for(int i=1;i<=n;++i) a[i]=-a[i];
        solve();
        cout<<ans<<endl;
    }
}

兔子的逆序对

因为我们操作$[l,r]$这个区间，受影响的的逆序对只有$[l,r]$之间的，其他的都没有影响

假设原来有个逆序对，区间之间原来有个逆序对，那么我们翻转之后

就变成了

即减去原先的逆序对个数然后加上顺序对个数

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(x) x&(-x)

const int MAXN = 1e5 + 7;
int c[MAXN] , n , m;
ll t = 0;

void add(int i , int x){
    for(; i <= n ; i += lowbit(i)){
        c[i] += x;     
    }
}

ll quary(int i){
    ll sum = 0;
    for(; i ; i -=lowbit(i) ) sum += c[i];
    return sum;
}

int main(void){
    scanf("%d" , &n);
    for(int i = 1 ; i <=n ;++i){
        int j;
        scanf("%d" , &j);
        t += quary(n) - quary(j - 1);
        add( j , 1);
    }
    scanf("%d" , &m);
    int ans = t & 1;
    while(m--){
        ll l , r;
        scanf("%lld%lld" , &l , &r);
        t = (r - l) * (r - l + 1) >> 1;
        ans ^= t & 1;
        if(ans) printf("dislike\n");
        else printf("like\n");
    }
    return 0;
}

华华教月月做数学

快速幂算法通常用在求 A^B%C 的时候，因为当B足够大的时候 n与logn 的差距就非常巨大了。并且B十分巨大的时候通常我们已经存不下这个数值了。所以一般要对一个C 取模。
如果B十分大，那么有可能会产生a的2^n次方时比 long long 还大。这时就有可能输出负数也就是溢出了。所以这个时候可以用加法来模拟乘法，并且每次相加都对C取模，这样就不会溢出了。
加法模拟乘法：
列如：求75：
n=5的二进制是101，
此时n为奇数，则ans=ans+tmp；tmp=tmp+tmp；n右移一位；（ans=0+7，tmp=72）
此时n为偶数，则直接tmp=tmp+tmp；n右移一位；（ans=7，tmp=74）
此时n为奇数，则ans=ans+tmp；tmp=tmp+tmp；n右移一位；（ans=7+74，tmp=78）;
快速幂算法：https://blog.csdn.net/wuyileiju__/article/details/81056150
列如求5^19:
n=19的二进制是10011，
此时n为奇数，则ans=anstmp；tmp=tmptmp；n右移一位；（ans=15，tmp=55=25）
此时n为奇数，则ans=anstmp；tmp=tmptmp；n右移一位；（ans=525，tmp=2525）
此时n为偶数，则直接tmp=tmptmp；n右移一位；（ans=125，tmp=625625）
此时n为偶数，则直接tmp=tmptmp；n右移一位；（ans=125，tmp=390625390625）
此时n为奇数，则ans=anstmp；tmp=tmptmp；n右移一位；（ans=125390625390625，tmp=(390625390625）^2）;

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll pow_mul(ll a , ll b , ll mod){
    ll ans = 0 ;
    while(b){
        if(b&1) ans = (ans + a) % mod;
        a = (a + a) % mod;
        b>>=1;
    }
    return ans;
}

ll pow_mod(ll a , ll b , ll mod){
    ll ans = 1;
    while(b){
        if(b&1) ans = pow_mul(ans , a , mod);
        a = pow_mul(a, a , mod);
        b >>= 1;
    }
    return ans;
}

int main(void){
    ll t, a, b, p;
    scanf("%d" , &t);
    while(t--){
        scanf("%lld%lld%lld" , &a , &b , &p);
        printf("%lld\n" , pow_mod(a , b, p)); 
    }
    return 0;
}

表达式计算4

又是模拟。。

实在是太麻烦了，可以用python的eval来求

只要手动改一下出题人卡的地方就行了

code

def deal(a):
    a = a.replace('^','**')
    a = a.replace(' ','')
    a = a.replace('()','')
    a = a.replace('/','//') #注意整除
    cnt = 0
    r = []
    for i in range(len(a)):
        if a[i] == '(':   cnt+=1
        elif a[i] == ')':
            if cnt == 0:    r.append(i)
            else:   cnt-=1
    la = list(a)
    for i in r: la.pop(i)
    n = len(la)
    cnt = 0
    l = []
    for i in range(n):
        if la[n - 1 - i] == ')':  cnt+=1
        elif la[n - 1 - i] == '(':
            if cnt == 0:  l.append(n - 1 - i)
            else:   cnt-=1
    for i in l: la.pop(i)
    a = ''.join(la)
    return a

s = input()
s = deal(s)
print(eval(s))

Sliding Window

题意很简单 就是求区间里的最大值和最小值

这里我们使用单调队列来做

用数组模拟单调队列 首先就是理解为啥用单调队列

就用题目中的例子举例

图片说明

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1e6 + 7;

int a[MAXN] , que[MAXN];

int main(void){
    int n , m;
    scanf("%d%d" , &n , &m);
    for(int  i = 1 ; i <= n ; ++i)
        scanf("%d" , &a[i]);
    int l = 0 , r = 0;
    que[r++] = 1;
    if(m == 1) printf("%d ", a[1]);
    for(int  i = 2 ; i <= n ; ++i){
        if(r > l && i - que[l] >= m) 
            ++l;
        while(r > l && a[que[r - 1]] >= a[i] )
            --r;

        que[r++] = i;
        if(i >= m)
            printf("%d " , a[que[l]]);
    } 
    cout<<endl;
    l  = r =0;
    que[r++] = 1;
    if(m == 1) printf("%d " , a[1]);
    for(int i = 2 ; i <= n ; ++i){
        if(r > l && i - que[l] >= m)    ++l;
        while(r > l && a[que[r - 1]] <= a[i])    --r;

        que[r++] = i;
        if(i >= m)
            printf("%d " , a[que[l]]);
    }
    cout<<endl;
    return 0;
}

Raid

分治的运用，计算不同类型的点的最近距离

将点按照x分成两组，通过递归来求最近距离

code

#include<cstdio>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include<cmath>
#include<cstring>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;

struct node{
    int x ,  y;
    int k;
    bool operator < (const node& b) const {
        if(x != b.x) return x < b.x;
        return y < b.y;
    }
}a[N<<1];

double dis(int x , int y){
    return sqrt(1.0 * (a[x].x - a[y].x) * (a[x].x - a[y].x) + 1.0 * (a[x].y - a[y].y) * (a[x].y - a[y].y));
}


double solve(int l ,int r){
    if(l == r) return INF;
    int mid = l + r >> 1;
    double ans = INF;
    ans = min(ans , min(solve(l , mid) , solve(mid +  1 , r)));
    for(int  i = mid ; i >= l ; --i){
        if(dis(mid , i) > ans) break;
        for(int j = mid ; j <=r ; ++j){
            if(dis(j , i) > ans) break;
            if(a[j].k != a[i].k) ans = min(ans , dis(i , j)); 
        }
    }
    return ans;
}

int main(void){
    int T = read();
    while(T--){
        int n = read();
        for(int i = 1 ; i <= n ; ++i)
            a[i].x = read() , a[i].y = read() , a[i].k = 0;
        for(int i = n + 1 ; i <= 2 * n ; ++i)
            a[i].x = read() , a[i].y = read() , a[i].k = 1;
        sort(a + 1 , a + 1 + 2 *n);
        printf("%.3f\n" , solve(1 , 2 * n));
    }
    return 0;
}

Efficient Solutions

这个题目和前面的那个完爆电脑的有点相似

题意就是一个人有俩个数值，按顺序读入，如果这个人的某一个数值是最低的，那么他就会被记录下来，如果都不是最低的，那就会被排除掉，我们可以使用set按照x排序，然后比较y，如果y小于set最前面的，那么就会保存下来，因为会出现重复的值，所以我们使用multiset

然后我可能是个***吧，漏了一个#都没注意，还交了好多发。。。

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;

struct node{
    int x, y;
    bool operator <(const node& b) const{
        if(x == b.x) return y < b.y;
        return x < b.x;
    }
};

int main(void){
    int T;
    cin>>T;
    int cnt = 1;
    multiset<node> st;
    while(T--){
        int n;
        st.clear();
        cin>>n;
        if(cnt > 1) cout<<endl;
        cout<<"Case #"<<cnt++<<":"<<endl;
        for(int i = 1 ; i <= n ; ++i){
            int x , y;
            cin>>x>>y;
            node t = {x , y};
            multiset<node>::iterator it = st.lower_bound(t);
            if(it == st.begin() || (--it)->y > y){
                st.insert(t);
                it = st.upper_bound(t);
                while(it != st.end() && it->y >= y) st.erase(it++);
            }  
            cout<<st.size()<<endl;
        }
    }
    return 0;
}

Golf Bot

用到了bitset专门写了一篇博客介绍 博客链接

Bits

就是一个裸的汉诺塔问题，然后将他的过程模拟出来即可

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

int n , m;
int t[3][12], width;
string _begin , _str , str;
int cost[5];

inline void print(){
    for(int floor = n , pos , len ; floor ; floor--){
        str = _str;
        for(int i = 0 ; i < 3 ; ++i){
            if(cost[i] >= floor){
                len = 2 * t[i][floor] + 1;
                pos = width * i + i + 1 + (width - len) / 2;
                for(int j = pos + 1 ; j <= pos + len ; j++)
                    str[j - 1] = '*';
            }
        }
        cout<<str<<"\n";
    }
}

inline void move(int a , int b){
    t[b][++cost[b]] = t[a][cost[a]--];
    cout<<_begin;
    print();
}

void hanoi(int a , int b , int x) {
    if(x == 1){
        move(a , b);
        return ;
    }
    hanoi(a , 3 - a - b , x - 1);
    move(a , b);
    hanoi(3 - a - b , b , x - 1);
}

int main(void){
    cin>>n;
    m = 6 * n + 7;
    for(int i = 1 ; i <= n ; ++i)
        t[0][i] = n - i + 1;
    cost[0] = n;
    for(int i = 0 ; i < m ; ++i){
        _begin += '.';
        _str+='.';
    }
    width = 2 * n + 1;
    _str[width / 2 + 1] = _str[width + 2 + width / 2] = _str[width * 2 + 3 + width / 2] = ' |';
    _begin += '\n' + _str + '\n';

    cout<<_begin;
    print();
    string tmp;
    for(int i = 0 ; i < m ; ++i) tmp += '-';
    _begin = tmp + '\n' + _begin;
    (n & 1) ? hanoi(0 , 1, n) : hanoi(0 , 2 ,n);
    return 0; 
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
11-29 22:00
点赞 评论 收藏
分享
11-28 17:23
武汉大学 C++
华为（算法工程师）
时间线7.29&nbsp;--&nbsp;投递8.28&nbsp;--&nbsp;笔试（200+/600飘过）8.31&nbsp;--&nbsp;测评9.14&nbsp;--&nbsp;一面9.26&nbsp;--&nbsp;线下二三面最终结果：应该是寄了，对接人主动降温，建议我签一个保底。只能说大概率是一面面评抽象了，无缘华为了一面（50min左右）抽象至极的一面，面试官感觉完全不懂SLAM，我说我是图优化框架，面试官问我图是怎么处理的呢。我说是指图有哪些节点么，面试官说“就是你的图是怎么处理的，图像处理”；然后线上手撕要求白纸写，复盘笔试不告诉你题让你自己想，讲了半天说你做的都是开发，真的有被抽象到，不过就这样都不挂，看来华子一面真不挂人二面（50min左右）二面线下面，明显感受好多了回...
查看6道真题和解析 华为求职进展汇总
点赞 评论 收藏
分享
11-14 17:25
门头沟学院 数字IC前端设计
华为&nbsp;这是保温吗
球球别再泡了：坏，我单9要了14
点赞 评论 收藏
分享
11-24 15:00
Columbia University Java
北美字节oc
bg：水硕，一段大厂一段中厂实习碎碎念：秋招一直处于半摆烂的状态，本来都打算回国直接当团小子了，结果最后开奖开了个挺低的包，感觉有点侮辱人，就重新捡起了好几个月没看的八股和算法重新开始投，但确实有点晚了所以基本也没面上几家。每天熬到凌晨三四点面试，早上六七点爬起来笔试，虽然好几家都走到了最后的hr面，但搞了这么久也就拿了个阿里云边缘部门的小sp，属实有点不甘心。不过幸运的是，朋友帮我找人推了个北美tt的开发岗，之前我自己投都是做完笔试就直接没消息了，没想到这次内推了下还真被捞起来进面了，三轮技术面+一轮hr面也都比较顺利，不得不感叹找工真的是9分看运气1分看实力（这里真得吐槽下sb淘天...
安多纳德：恭喜老哥 这是以后留在北美了吗
点赞 评论 收藏
分享
评论
1
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
237785次浏览 2040人参与
# ai智能作图 #
29611次浏览 354人参与
# 北方华创开奖 #
67182次浏览 553人参与
# 25届秋招总结 #
412970次浏览 4147人参与
# 实习，投递多份简历没人回复怎么办 #
2441651次浏览 34746人参与
# 地方国企笔面经互助 #
7039次浏览 17人参与
# 阿里云管培生offer #
63042次浏览 1763人参与
# 我在牛爱网找对象 #
74918次浏览 555人参与
# 机械求职避坑tips #
23728次浏览 249人参与
# 虾皮求职进展汇总 #
92758次浏览 758人参与
# 发工资后，你做的第一件事是什么 #
9381次浏览 43人参与
# 我的实习求职记录 #
6135528次浏览 84026人参与
# 25届机械人为了秋招做了哪些准备？ #
26347次浏览 363人参与
# 机械人怎么评价今年的华为 #
158032次浏览 1352人参与
# 投格力的你，拿到offer了吗？ #
47425次浏览 334人参与
# 华为工作体验 #
111795次浏览 867人参与
# 如果再来一次，你还会选择这个工作吗？ #
116371次浏览 1147人参与
# 国央企笔面经互助 #
88604次浏览 897人参与
# 在职场上，你最讨厌什么样的同事 #
6154次浏览 92人参与
# 软件开发投递记录 #
1482076次浏览 23949人参与
# 产运销实习日记 #
28260次浏览 326人参与
# 硬件兄弟们 甩出你的华为奖状 #
78657次浏览 629人参与
牛客网
牛客企业服务