第1题 瞌睡
尺取法滑动窗口
时间复杂度O(n)
第2题 丰收
前缀和后二分
时间复杂度O(mlogn)
第3题 整理房间
暴力枚举每团杂物4 ^ 4次旋转
时间复杂度O(256*n)
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 6 struct point { 7 int x, y; 8 9 point(int _x = 0, int _y = 0) : x(_x), y(_y) {} 10 11 point operator+(const point &rhs) const { 12 return point(x + rhs.x, y + rhs.y); 13 } 14 15 point operator-(const point &rhs) const { 16 return point(x - rhs.x, y - rhs.y); 17 } 18 19 bool operator==(const point &rhs) const { 20 return x==rhs.x&&y==rhs.y; 21 } 22 23 point rotate() // 原点旋转 24 { 25 return point(-y, x); 26 } 27 28 point rotate(const point &o) const { 29 return (*this - o).rotate() + o; 30 } 31 }; 32 33 // 判断是否合法的正方形 34 bool check(const point& a, const point& b) {//两条对角线向量 35 if(a.x==0&&a.y==0||b.x==0&&b.y==0)return false; 36 if(a.x*a.x+a.y*a.y!=b.x*b.x+b.y*b.y)return false;//对角线不等长 37 if(a.x*b.x+a.y*b.y!=0)return false;//对角线不垂直 38 return true; 39 } 40 41 int main() 42 { 43 int n; 44 cin>>n; 45 while(n--) 46 { 47 point p[4],o[4]; 48 for(int i=0;i<4;i++) 49 { 50 cin>>p[i].x>>p[i].y; 51 cin>>o[i].x>>o[i].y; 52 } 53 int ans=-1; 54 int x,y,z,w; 55 for(x=0;x<4;x++) 56 { 57 for(y=0;y<4;y++) 58 { 59 for(z=0;z<4;z++) 60 { 61 for(w=0;w<4;w++) 62 { 63 int cost = x+y+z+w; 64 //是否对角线，并且构成正方形 65 if(p[0]+p[1]==p[2]+p[3]&& 66 check(p[0]-p[1],p[2]-p[3])|| 67 p[0]+p[2]==p[1]+p[3]&& 68 check(p[0]-p[2],p[1]-p[3])|| 69 p[0]+p[3]==p[1]+p[2]&& 70 check(p[0]-p[3],p[1]-p[2])) 71 { 72 if(ans==-1||ans>cost)ans=cost; 73 } 74 p[3].rotate(o[3]); 75 } 76 p[2].rotate(o[2]); 77 } 78 p[1].rotate(o[1]); 79 } 80 p[0].rotate(o[0]); 81 } 82 cout<<ans<<endl; 83 } 84 85 return 0; 86 }