笔试-滴滴-180918（算法）求大佬指点迷津

1. 排列小球（C++，67%，TLE） #include <iostream> #include <vector> using namespace std; int bs[3]; int n; int ans; vector<int> tmp; void dfs(int step) { if (tmp.size() == n) { ans += 1; return; } for (int i = 0; i < 3; i++) { if (bs[i] > 0 && i != tmp.back()) { tmp.push_back(i); bs[i] -= 1; dfs(step + 1); bs[i] += 1; tmp.pop_back(); } } } void solve() { cin >> bs[0] >> bs[1] >> bs[2]; n = bs[0] + bs[1] + bs[2]; ans = 0; for (int i = 0; i < 3; i++) { if (bs[i] > 0) { tmp.push_back(i); bs[i] -= 1; dfs(1); bs[i] += 1; tmp.pop_back(); } } cout << ans; } int main() { solve(); //cout << endl; //system("PAUSE"); return 0; }

第二题好像给的样例有问题啊，第一个样例里的test2最后没带换行符，所以用raw_input会一直等着继续输入……

交通轨迹，想到一个暴力版，复杂度O（n^2） #include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e5+233; const double eps = 0.00000001; struct node { double x1; double y1; double x2; double y2; int id; int sum; }sa[N],sb[N]; struct node2 { double x; double y; }; node2 a,b,c,d; node2 aa,bb,cc,dd; bool judge(node s,node t) { a.x=s.x1; a.y=s.y1; b.x=s.x2; b.y=s.y2; c.x=t.x1; c.y=t.y1; d.x=t.x2; d.y=t.y2; if(min(a.x,b.x) <= max(c.x,d.x) && min(c.x,d.x) <= max(a.x,b.x) && min(a.y,b.y) <= max(c.y,d.y) &&min(c.y,d.y)<=max(a.y,b.y)) { double u,v,w,z;//保存叉乘 u=(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y); v=(d.x-a.x)*(b.y-a.y)-(b.x-a.x)*(d.y-a.y); w=(a.x-c.x)*(d.y-c.y)-(d.x-c.x)*(a.y-c.y); z=(b.x-c.x)*(d.y-c.y)-(d.x-c.x)*(b.y-c.y); return (u*v<=eps && w*z<=eps); //浮点数判断大小 } return false; } int T,n,m; int main() { //freopen("in.txt","r",stdin); cin>>T; while(T--) { memset(sa,0,sizeof(sa)); cin>>n; int cnt=0; for(int i=1; i<=n; ++i) { char op; cin>>op; if(op=='T') { cnt++; // cout<<"cnt="<<cnt<<endl; cin>>sa[cnt].x1>>sa[cnt].y1>>sa[cnt].x2>>sa[cnt].y2; sa[cnt].id=cnt; sa[cnt].sum=0; } else { int q; cin>>q; //cout<<"cnt="<<cnt<<endl; for(int j=1; j<=cnt; ++j) { for(int k=j+1; k<=cnt; ++k) { if(judge(sa[j],sa[k])) { //cout<<"j="<<j<<" "<<"k="<<k<<endl; sa[j].sum++; sa[k].sum++; } } } //cout<<endl; cout<<sa[q].sum+1<<endl; } } cout<<endl; } return 0; }

第二题并查集。。。手残党居然没敲完。。。

第二题用的dfs，代码好他妈长！！！ #include<iostream> #include<string>  #include<cmath> #include<vector>  #include<algorithm> #include<queue> #include "stdlib.h" #include<limits.h> #include <iomanip> #include<map> #include <queue> #include<set> #include <sstream> using namespace std; typedef struct point       {           float x;           float y;       }Point;   bool lineIntersectSide(Point A, Point B, Point C, Point D)       {             float fC = (C.y - A.y) * (A.x - B.x) - (C.x - A.x) * (A.y - B.y);          float fD = (D.y - A.y) * (A.x - B.x) - (D.x - A.x) * (A.y - B.y);                if(fC * fD > 0){             return false;          }                             return true;     }       bool sideIntersectSide(Point A, Point B, Point C, Point D)       {           if(!lineIntersectSide(A, B, C, D)) {             return false;           }                       if(!lineIntersectSide(C, D, A, B)){             return false;           }                        return true;       } int query(int num,vector<vector<point> > qu){    queue <int > q;    int vis[qu.size()];    for(int i=0;i<qu.size();i++){        vis[i]=0;    }           int zu=1;    for(int t=0;t<qu.size();t++){        if(vis[t]==0){             vis[t]=zu;            q.push(t);    while(!q.empty()){        for(int i=0;i<qu.size();i++){            if(vis[i]==0){                bool t1=sideIntersectSide(qu[i][0],qu[i][1],qu[q.front()][0],qu[q.front()][1]);             if(t1){                 q.push(i);                 vis[i]=zu;                 //cout<<i<<endl;             }            }                      }     q.pop();    }        }             zu+=1;    }    int count=0;  num=vis[num-1];  for(int i=0;i<qu.size();i++){     if(vis[i]==num){         count++;     } }      return count;     }   int main() { int t; cin>>t; while(t--){     int n;     cin>>n; vector<vector<point> > qu;     for(int i=0;i<n;i++){         char m;         cin>>m;         if(m=='T'){             float x1,y1,x2,y2;             cin>>x1>>y1>>x2>>y2;             point p1;             p1.x=x1;             p1.y=y1;             point p2;             p2.x=x2;             p2.y=y2;             vector<point > line;             line.push_back(p1);             line.push_back(p2);             qu.push_back(line);         }         if(m=='Q'){             int w;             cin>>w;             cout<<query(w,qu)<<endl;         }     } } } 

第二题谁TM知道还要用叉乘来做.....用叉乘也就算了，还要套层并查集，哪有时间写，唧唧了

class point():     def __init__(self,x,y):         self.x = x         self.y = y def isxiangjiao(a,b,c,d):     fc = (c.y-a.y)*(a.x-b.x)-(c.x-a.x)*(a.y-b.y)     fd = (d.y-a.y)*(a.x-b.x)-(d.x-a.x)*(a.y-b.y)     if(fc*fd>0):         return False     return  True import sys  import collections if __name__ == "__main__":     t = int(sys.stdin.readline().strip())     for i in range(t):         n = int(sys.stdin.readline().strip())         roaddict = collections.defaultdict(set)         roadpos = []         count = 1         for j in range(n):             line = sys.stdin.readline().strip().split()             if(line[0]=='T'):                 x1,y1,x2,y2 = int(line[1]),int(line[2]),int(line[3]),int(line[4])                 pointa = point(x1,y1)                 pointb = point(x2,y2)                 roadpos.append([pointa,pointb])                 if(count==1):                     roaddict[count].add(count)                     count+=1                 else:                     visited = set()                     for tmpi in range(1,len(roadpos)+1):                         pointc = roadpos[tmpi-1][0]                         pointd = roadpos[tmpi-1][1]                         if(tmpi not in visited and isxiangjiao(pointa, pointb, pointc, pointd)):                             visited.add(tmpi)                             roaddict[tmpi].add(count)                             roaddict[count].add(count)                             for tmp in roaddict[tmpi]:                                 visited.add(tmp)                                 roaddict[tmp].add(count)                                 roaddict[count].add(tmp)                     for tmp in roaddict[count]:                         roaddict[tmp] = roaddict[count]                     count+=1             if(line[0]=='Q'): #                 print(roaddict)                 queryvale = int(line[1])                 print(len(roaddict[queryvale]))         print()

把第一题写AC了然后第二题实在太麻烦了写不完

交通轨迹用并查集，判断线段相交可以通过判断四端点是不是互在对方两侧