网易8.21通用技术A卷

A

送分题

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int main (){
    vector<long long> V;
    long long n;
    while(cin>>n) {V.push_back(n);}
    n=V.back();V.pop_back();
    sort(V.begin(),V.end());
    long long res=0;
    for(int i=1;i<V.size();i++) {
        res+=upper_bound(V.begin(),V.begin()+i,n-V[i])-V.begin();
    }
    cout<<res<<endl;
}

B

就递归一下？

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
char getKth(int n,int k,bool inv) {
    int mid=1<<(n-1);
    char res;
    if(k==mid) res='a'+n-1;
    else if(k<mid) res=getKth(n-1,k,0);
    else res=getKth(n-1,(1<<(n-1))-(k-mid),1);
    if(inv) {
        return 25-(res-'a')+'a';
    }
    return res;
}
char findKthBit(int n, int k) {
    return getKth(n,k,0);
}
int main (){
    // for(int i=1;i<10;i++) cout<<findKthBit(4,i);
}

C

拓扑排序,如果一个人比另外一个小就建边，复杂度O(n)

#include <iostream>
#include <queue>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;
struct EDGE{
    int v,nex;
}edge[maxn];
int deg[maxn],head[maxn],ecnt,res[maxn];
inline void add_edge(int u,int v) {
    edge[++ecnt]={v,head[u]};head[u]=ecnt;
    deg[v]++;
}
int main (){
    vector<int> V;
    int n;
    while(cin>>n) V.push_back(n);
    n=V.size();
    for(int i=0;i<n;i++) {
        int l=(i+n-1)%n,r=(i+1)%n;
        if(V[i]<V[l]) add_edge(i+1,l+1);
        if(V[i]<V[r]) add_edge(i+1,r+1);
    }
    queue<int> Q;
    for(int i=1;i<=n;i++) {
        if(deg[i]==0) {
            Q.push(i),res[i]=1;
        }
    }
    int tot=0;
    while(!Q.empty()) {
        int u=Q.front();Q.pop();
        tot+=res[u];
        for(int i=head[u];i;i=edge[i].nex) {
            int v=edge[i].v;
            res[v]=res[u]+1;
            deg[v]--;
            if(deg[v]==0) Q.push(v);
        }
    }
    cout<<tot<<endl;
}

D

感觉正解其实是把花费为2的点拆成上下左右四个点，然后相邻的点连接他伸出来的点，这样进行bfs得到的就是最短路，复杂度O(n*m) 。但是我嫌麻烦，直接写的SPFA，跑得飞快。

#include <iostream>
#include <queue>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int minSailCost(vector<vector<int> >& input) {
    int n=input.si***put[0].size();
    const int INF=100000000;
    vector<vector<int>> dis(n,vector<int>(m,INF));
    vector<vector<int>> inq(n,vector<int>(m,0));
    int dx[]={0,1,0,-1};
    int dy[]={1,0,-1,0};
    queue<pair<int,int>> Q;
    Q.push({0,0});dis[0][0]=0;inq[0][0]=1;
    while(!Q.empty()) {
        auto u=Q.front();Q.pop();
        int y=u.first,x=u.second;
        inq[y][x]=0;
        for(int i=0;i<4;i++) {
            int ny=y+dy[i],nx=x+dx[i];
            if(ny<0||ny>=n||nx<0||nx>=m||input[ny][nx]==2) continue;
            if(dis[y][x]+2-input[ny][nx]<dis[ny][nx]) {
                dis[ny][nx]=dis[y][x]+2-input[ny][nx];
                if(!inq[ny][nx]) {
                    inq[ny][nx]=1;
                    Q.push({ny,nx});
                }
            }
        }
    }
    if(dis[n-1][m-1]==INF) return -1;
    return dis[n-1][m-1];
}
int main (){
    int n,m;cin>>n>>m;
    vector<vector<int>> V(n,vector<int>(m));
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>V[i][j];
    cout<<minSailCost(V);
}