LCCUP 2021被虐

# LCP 28. 采购方案

我的代码：

class Solution {
public:
    int binarySearch(const vector<int>& nums, int l, int r, int target){
      if (l >= r)  return l;
      int mid = (r - l)/2 + l;
      if(nums[mid] > target)  return binarySearch(nums, l, mid, target);
      else  return binarySearch(nums, mid + 1, r, target);
    }
    int purchasePlans(vector<int>& nums, int target) {
      int n = nums.size();
      int ret = 0;
      const int mod =1e9 + 7;
      sort(nums.begin(), nums.end());
      for(int i = 0 ; i < nums.size() ; ++i){
        if(nums[i] > target/2)  return ret;
        int j = binarySearch(nums, i + 1, n, target - nums[i]);
        // cout<<i<<" "<<j<<endl;
        ret = (ret + j - i - 1) % mod;
      }
      return ret;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

ACRush代码

#include <bits/stdc++.h>

using namespace std;

#define POW2(X) (1<<(X))
#define CKBIT(S,X) (((S)&POW2(X))!=0)
const double pi=acos(-1.0);
const double eps=1e-11;
template<class T> inline void ckmin(T &a,T b){ a=min(a,b); }
template<class T> inline void ckmax(T &a,T b){ a=max(a,b); }
template<class T> inline T sqr(T x){ return x*x; }
#define SIZE(A) ((int)A.size())
#define LENGTH(A) ((int)A.length())
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,a) for(int i=0;i<(a);++i)
#define ALL(A) A.begin(),A.end()
template<class T> int CMP(T a[],const T b[],int n) { return memcmp(a,b,n*sizeof(T)); }
template<class T> void COPY(T a[],const T b[],int n) { memcpy(a,b,n*sizeof(T)); }
template<class T> void SET(T a[],int val,int n) { memset(a,val,n*sizeof(T)); }
using uint=unsigned int;
using int64=long long;
using uint64=unsigned long long;
using ipair=pair<int,int>;
using VI=vector<int>;
using VD=vector<double>;
using VVI=vector<VI>;
using VS=vector<string>;

class Solution
{
public:
    int purchasePlans(vector<int>& a, int target) 
	{
		const int MOD=1000000007;
		int ret=0;
		sort(ALL(a));
		int n=SIZE(a);
		for (int j=n-1,i=0;i<n;i++)
		{
			for (;j>i && a[i]+a[j]>target;--j);
			if (j<=i) break;
			ret=(ret+j-i)%MOD;
		}
		return ret%MOD;
	}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

这里可以学习的一些点：

二分难写可以利用类似的思路，比暴力强
一些define和using的方法

# LCP 30. 魔塔游戏

我的代码：

using ll = long long;
class Solution {
public:
    int magicTower(vector<int>& nums) {
      if(accumulate(nums.begin(), nums.end(), ll(0)) < 0)  return -1;
      priority_queue<ll, vector<ll>, greater<ll>> min_heap;
      int ret = 0;
      ll sum = 0;
      for(int x : nums){
        sum += x;
        if(x < 0)  min_heap.push(x);
        if(sum < 0){
          ++ret;
          sum -= min_heap.top();
          min_heap.pop();
        }
      }
      return ret;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

ACRush的代码：

#include <bits/stdc++.h>

using namespace std;

#define POW2(X) (1<<(X))
#define CKBIT(S,X) (((S)&POW2(X))!=0)
const double pi=acos(-1.0);
const double eps=1e-11;
template<class T> inline void ckmin(T &a,T b){ a=min(a,b); }
template<class T> inline void ckmax(T &a,T b){ a=max(a,b); }
template<class T> inline T sqr(T x){ return x*x; }
#define SIZE(A) ((int)A.size())
#define LENGTH(A) ((int)A.length())
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,a) for(int i=0;i<(a);++i)
#define ALL(A) A.begin(),A.end()
template<class T> int CMP(T a[],const T b[],int n) { return memcmp(a,b,n*sizeof(T)); }
template<class T> void COPY(T a[],const T b[],int n) { memcpy(a,b,n*sizeof(T)); }
template<class T> void SET(T a[],int val,int n) { memset(a,val,n*sizeof(T)); }
using uint=unsigned int;
using int64=long long;
using uint64=unsigned long long;
using ipair=pair<int,int>;
using VI=vector<int>;
using VD=vector<double>;
using VVI=vector<VI>;
using VS=vector<string>;

class Solution
{
public:
    int magicTower(vector<int>& nums) 
	{
		int64 s=0;
		int64 w=0;
		int64 d=0;
		priority_queue<int> q;
		int ret=0;
		for (int val:nums)
			if (val>0)
				s+=val;
			else
			{
				val=-val;
				q.push(val);
				w+=val;
				while (!q.empty() && s<w)
				{
					int key=q.top();
					q.pop();
					w-=key;
					d+=key;
					++ret;
				}
			}
		return (s>=w+d)?ret:-1;
	}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

自我感觉这个题写得还可以，其实就是个简单的模拟。

# LCP31. 变换的迷宫

ACRush代码：

#include <bits/stdc++.h>

using namespace std;

#define POW2(X) (1<<(X))
#define CKBIT(S,X) (((S)&POW2(X))!=0)
const double pi=acos(-1.0);
const double eps=1e-11;
template<class T> inline void ckmin(T &a,T b){ a=min(a,b); }
template<class T> inline void ckmax(T &a,T b){ a=max(a,b); }
template<class T> inline T sqr(T x){ return x*x; }
#define SIZE(A) ((int)A.size())
#define LENGTH(A) ((int)A.length())
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,a) for(int i=0;i<(a);++i)
#define ALL(A) A.begin(),A.end()
template<class T> int CMP(T a[],const T b[],int n) { return memcmp(a,b,n*sizeof(T)); }
template<class T> void COPY(T a[],const T b[],int n) { memcpy(a,b,n*sizeof(T)); }
template<class T> void SET(T a[],int val,int n) { memset(a,val,n*sizeof(T)); }
using uint=unsigned int;
using int64=long long;
using uint64=unsigned long long;
using ipair=pair<int,int>;
using VI=vector<int>;
using VD=vector<double>;
using VVI=vector<VI>;
using VS=vector<string>;

int dx[]={-1,1,0,0,0};
int dy[]={0,0,-1,1,0};

class Solution
{
public:
	bool visited[102][52][52][2][3];
	int a[102][52][52];
	int sx;
	int sy;
	int depth;

	bool dfs(int t,int x,int y,int p0,int p1)
	{
		if (x==sx-1 && y==sy-1) return true;
		if (visited[t][x][y][p0][p1]) return false;
		visited[t][x][y][p0][p1]=true;
		if (t+1>=depth) return false;
		REP(dir,5)
		{
			int x2=x+dx[dir];
			int y2=y+dy[dir];
			if (x2>=0 && x2<sx && y2>=0 && y2<sy)
			{
				if (a[t+1][x2][y2])
				{
					if (dfs(t+1,x2,y2,p0,dir==4?p1:min(1,p1))) return true;
				}
				else
				{
					if (p0==0)
					{
						if (dfs(t+1,x2,y2,1,dir==4?p1:min(1,p1))) return true;
					}
					if (p1==0 || p1==2 && dir==4)
					{
						if (dfs(t+1,x2,y2,p0,2)) return true;
					}
				}
			}
		}
		return false;
	}
    bool escapeMaze(vector<vector<string>>& maze) 
	{
		depth=SIZE(maze);
		sx=SIZE(maze[0]);
		sy=SIZE(maze[0][0]);
		REP(i,depth) REP(x,sx) REP(y,sy) a[i][x][y]=(maze[i][x][y]=='.');
		memset(visited,false,sizeof(visited));
		return dfs(0,0,0,0,0);
	}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

编辑

上次更新: 2021/06/04, 12:04:55

← 剑指offer 07 重建二叉树 Leetcode 51 - N皇后→