假算法
假算法
假算法

重要的事情说三遍，第二三题用的都是假算法，本来是打算暴力混分的，没想到直接AK了，写完我自己都惊了，提前五分钟交卷。

第一题

模拟下就行了

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int que[200005];
int main(){
    int t;
    cin >> t;
    while(t--){
        int q;
        int len = 0,now = 0,back = 0;
        cin >> q;
        while(q--){
            char a[10];
            int x;
            cin >> a;
            if (a[0] == 'P' && a[1] == 'U'){
                cin >> x;
                que[back++] = x;
                len++;
            }
            else if (a[0] == 'T'){
                if (len == 0) cout << -1 << endl;
                else cout << que[now] << endl;
            }
            else if (a[0] == 'P'){
                if (now == back) cout << -1 << endl;
                else {
                    now++;
                    len--;
                }
            }
            else if (a[0] == 'S'){
                cout << len << endl;
            }
            else {
                len = now = back = 0;
            }
        }
    }
    return 0;
}

第二题

假算法

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
    ll x,y;
}a[100005],b[100005];
bool cmp(node q,node w){
    if (q.x == w.x) return q.y < w.y;
    return q.x < w.x;
}
int main(){
    int n,t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i = 0;i < n;i++)
            scanf("%lld%lld",&a[i].x,&a[i].y);
        for(int i = 0;i < n;i++)
            scanf("%lld%lld",&b[i].x,&b[i].y);

        sort(a,a+n,cmp);
        sort(b,b+n,cmp);

        double ans = -1;
        for(int i = 0;i < n;i++)
            for(int j = max(i-500,0);j < i+500 && j < n;j++){//原本过60%，取个范围，本来想防止超时混分，没想到直接AC
                double temp = pow(pow(a[i].x-b[j].x,2)+pow(a[i].y-b[j].y,2),0.5);
                if (ans < 0 || ans > temp) 
                    ans = temp;
                // else break;
            }

        printf("%.3f\n", ans);
    }
    return 0;
}

第三题

dfs暴力，假算法

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[50],b[50],now[50],n,ans;
int check;
void dfs(int value){
    check++;
    if (check >= 1e7) return;//递归超1e7后直接return，防超时（没加这个是过75%并超时，加完居然AC了）
    if (value >= ans) return;//剪枝
    bool flag = true;
    for(int i = 1;i <= n && flag;i++)
        if (now[i] < now[i-1])
            flag = false;
    if (flag){
        ans = min(ans,value);
        return ;
    }
    for(int i = 1;i <= n;i++)
        if (now[i] < now[i-1] ){ 
            swap(a[i],a[i-1]);
            swap(b[i],b[i-1]);
            swap(now[i],now[i-1]);
            if (now[i] == a[i]) now[i] = b[i];
            else now[i] = a[i];
            if (now[i-1] == a[i-1]) now[i-1] = b[i-1];
            else now[i-1] = a[i-1];
            dfs(value+1);
            swap(a[i],a[i-1]);
            swap(b[i],b[i-1]);
            swap(now[i],now[i-1]);
            if (now[i] == a[i]) now[i] = b[i];
            else now[i] = a[i];
            if (now[i-1] == a[i-1]) now[i-1] = b[i-1];
            else now[i-1] = a[i-1];
        }

}
int main(){
    cin >> n;
    ans = 1e6;
    check = 0;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        now[i] = a[i];
    }
    for(int i = 1;i <= n;i++)
        cin >> b[i];

    dfs(0);
    cout << (ans == 1e6?-1:ans) << endl;

    return 0;
}

第四题

我记得剑指Offer有原题？

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    stack<int> a;
    stack<int> b;
    while(n--){
        char c[10];
        scanf("%s",c);
        if (c[0] == 'a'){
            int x;
            scanf("%d",&x);
            a.push(x);
        }
        else if (c[0] == 'p' && c[1] == 'e'){
            if (b.empty()){
                while(!a.empty()){
                    b.push(a.top());
                    a.pop();
                }
            }
            printf("%d\n", b.top());
        }
        else {
            if (b.empty()){
                while(!a.empty()){
                    b.push(a.top());
                    a.pop();
                }
            }
            b.pop();
        }
    }
    return 0;
}

第五题

一个数除以2的值就是它的父节点

#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
ll num[70];
int main(){
    int q,len = 0;
    scanf("%d",&q);
    for(ll j = 1;j <= 2e18;len++,j<<=1){
        num[len] = j;
        // cout << j << endl;
    }

    // cout << num[len-1] << endl;
    while(q--){
        ll x;
        int k;
        cin >> x >> k;
        int i;
        for(i = 1;i < len;i++)
            if (x < num[i]) break;
        bool flag = true;
        // cout << len << ' ' <<i << endl;
        while(i){
            if (k > i || (k==i&&flag)){
                printf("-1\n");
                break;
            }
            else if (k == i) {
                printf("%lld\n", x);
                break;
            }
            else {
                x>>=1;
                flag = false;
            }
            i--;
        }
    }
    return 0;
}