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
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
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
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
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
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
编辑 (opens new window)
上次更新: 2021/06/04, 12:04:55