网易有道内推笔试解题报告【非官方】

今晚有道在线笔试解题报告，仅供参考。

（感谢某ACM队长提供解题报告）

洗牌

分析:

根据题目描述的，开辟一个数组模拟一下过程就好了。

参考代码：

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;
int n, k, a[N], b[N];

int main(){
    int t; scanf("%d", &t);
    while(t --) {
        scanf("%d %d", &n, &k); n *= 2;
        for(int i = 1; i <= n; i ++)
            scanf("%d", &a[i]);
        while(k--){
            for(int i = 1; i <= n; i++) 
                b[i] = a[i];            
            for(int i = 1, j = n / 2 + 1; i <= n / 2; i ++, j ++) {
                a[2 * i - 1] = b[i];
                a[2 * i] = b[j]; 
            }
        }
        for(int i = 1; i <= n; i ++) {
            printf("%d%c", a[i], " \n"[i == n]);
        }
    }
    return 0;
}

构造队列

分析：

分析题目可以发现原始序列和之后的序列有一个对应关系。 比如队列的第二个数是第一个被输出的，所以输出是 1 2 ... n的话，对应的第二个数就是1 依次内推。我们可以从之后的序列出发进行同样的操作然后做个对应关系的映射还原回原始的序列

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100005;
int n, a[N], b[N];

int main(){
    int t; scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        queue<int> q;
        for(int i = 1; i <= n; i ++) q.push(i);
        int cnt = 0;
        while(!q.empty()){
            int x=q.front();           
            q.pop();                 
            q.push(x);               
            x = q.front();              
            a[++cnt] = x;         
            q.pop();   
        }
        for(int i = 1; i <= n; i++) b[a[i]] = i;
        for(int i = 1; i <= n; i++)
            printf("%d%c", b[i], " \n"[i == n]); 
    }
    return 0;
}

查找矩形

分析

题目给的数据量小，最多只有25条线段。 于是我们4层循环枚举所有可能，然后去check一下是否是矩形。 如何判矩形呢，主要就是判4个角是否分别是直角，用向量的点积判一下就好了。 在枚举过程中如果判断是矩形，维护答案即可。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

int xx[9],yy[9];
typedef pair<double, double> pii;
struct line {
    double x1, x2, y1, y2;
}a[30];
map<pii, int> mp;
int n;
int angle(double x,double y,double m,double n,double p,double q){
    if((p-x)*(m-x)+(q-y)*(n-y)==0){
        return 1;
    }
    return 0;
}
int judge(double a,double b,double x,double y,double p,double q,double m,double n){
    if(angle(a,b,x,y,m,n)==0||angle(x,y,a,b,p,q)==0||angle(m,n,a,b,p,q)==0||angle(p,q,x,y,m,n)==0){
        return 0;
    }
    return 1;
}
map<pii ,int>::iterator it;

bool equal(int x, int y) {
    if(a[x].x1 == a[y].x1 && a[x].y1 == a[y].y1 && a[x].x2 == a[y].x2 && a[x].y2 == a[y].y2) return true;
    if(a[x].x1 == a[y].x2 && a[x].y1 == a[y].y2 && a[x].x2 == a[y].x1 && a[x].y2 == a[y].y1) return true;
    return false;
}

void check(int x, int y, int z, int w) {
    if(equal(x, y)) return;
    if(equal(x, z)) return;
    if(equal(x, w)) return;
    if(equal(z, y)) return;
    if(equal(w, y)) return;
    if(equal(z, w)) return;

    mp.clear();
    pii p = make_pair(a[x].x1, a[x].y1);
    mp[p] ++;
    p = make_pair(a[x].x2, a[x].y2);
    mp[p] ++;

    double minx = min(a[x].x1, a[x].x2);
    double maxx = max(a[x].x1, a[x].x2);
    double miny = min(a[x].y1, a[x].y2);
    double maxy = max(a[x].y1, a[x].y2);

    p = make_pair(a[y].x1, a[y].y1);
    mp[p]++;
    p = make_pair(a[y].x2, a[y].y2);
    mp[p]++;

    minx = min(minx, min(a[y].x1, a[y].x2));
    maxx = max(maxx, max(a[y].x1, a[y].x2));
    miny = min(miny, min(a[y].y1, a[y].y2));
    maxy = max(maxy, max(a[y].y1, a[y].y2));

    p = make_pair(a[z].x1, a[z].y1);
    mp[p]++;
    p = make_pair(a[z].x2, a[z].y2);
    mp[p]++;

    minx = min(minx, min(a[z].x1, a[z].x2));
    maxx = max(maxx, max(a[z].x1, a[z].x2));
    miny = min(miny, min(a[z].y1, a[z].y2));
    maxy = max(maxy, max(a[z].y1, a[z].y2));

    p = make_pair(a[w].x1, a[w].y1);
    mp[p]++;
    p = make_pair(a[w].x2, a[w].y2);
    mp[p]++;

    minx = min(minx, min(a[w].x1, a[w].x2));
    maxx = max(maxx, max(a[w].x1, a[w].x2));
    miny = min(miny, min(a[w].y1, a[w].y2));
    maxy = max(maxy, max(a[w].y1, a[w].y2));

    if(mp.size() != 4) return;

    int cnt = 0;
    for(it = mp.begin(); it != mp.end(); it ++) {
        xx[cnt] = it->first.first;
        yy[cnt++] = it->first.second;
    }

    if(judge(xx[0],yy[0],xx[1],yy[1],xx[2],yy[2],xx[3],yy[3])||judge(xx[0],yy[0],xx[2],yy[2],xx[1],yy[1],xx[3],yy[3])||judge(xx[0],yy[0],xx[2],yy[2],xx[3],yy[3],xx[1],yy[1]))
    printf("%.0f %.0f %.0f %.0f\n", minx, miny, maxx, maxy);
}

int main(){
    while(~scanf("%d", &n)) {
        for(int i = 0; i < n; i ++) {
            scanf("%lf %lf %lf %lf", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2);
        }
        for(int i = 0; i < n; i ++) {
            for(int j = i + 1; j < n; j ++) {
                for(int k = j + 1; k < n; k ++) {
                    for(int l = k + 1; l < n; l ++) {
                        check(i, j, k ,l);
                    }
                }
            }
        }
    }
    return 0;
}