分类目录归档：算法

洛谷 P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

今后需要改良一下拓扑排序，不要一遍一遍扫。只要抓到一个入度为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

#include<iostream>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int nxt[100005];
bool visited[100005];
int allocated[100005];
int alloc_ptr = 0;
int allocate_dis[100005];
int chainDis[100005];
int inDegree[100005];
inline void removeInDegree(int node) {
if (inDegree[node] != 0)return;
inDegree[node]--;
inDegree[nxt[node]]--;
removeInDegree(nxt[node]);
}
inline int dfsRing(int alloc, int node) {
if (visited[node])return 0;
visited[node] = true;
allocated[node] = alloc;
return 1 + dfsRing(alloc, nxt[node]);
}
inline int dfsToRing(int node) {
if (chainDis[node] != 0)return chainDis[node];
if (allocated[node])return chainDis[node] = allocate_dis[allocated[node]];
else return chainDis[node] = 1 + dfsToRing(nxt[node]);
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> nxt[i];
inDegree[nxt[i]]++;
}
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0)removeInDegree(i);
}
for (int i = 1; i <= n; i++) {
if (inDegree[i] <= 0 || allocated[i]) continue;
alloc_ptr++;
allocate_dis[alloc_ptr] = dfsRing(alloc_ptr, i);
}
for (int i = 1; i <= n; i++) {
if (allocated[i])cout << allocate_dis[allocated[i]] << endl;
else cout << dfsToRing(i) << endl;
}
}

洛谷 P2661 信息传递

发表评论

小小的激动一下，自己做出来的。。
然后有个警醒，如果不是顺其自然简化的条件判断表达式（例如!flag，是flag==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

#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int To[200005];
int inDegree[200005];
int getRing(int node) {
if (!inDegree[node])return 0;
inDegree[node] = 0;
return 1 + getRing(To[node]);
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> To[i];
inDegree[To[i]]++;
}
int flag = 0;
do {
flag = 0;
for (int i = 1; i <= n; i++) {
if (inDegree[i]==0) {
inDegree[i]--;
inDegree[To[i]]--;
flag++;
}
}
} while (flag!=0);
int mmin = 0x7fffffff;
for (int i = 1; i <= n; i++) {
if (inDegree[i] > 0)mmin = min(mmin, getRing(i));
}
cout << mmin;
}

洛谷 P1108 低价购买

发表评论

头一回自己写出来个这么难的动规，小小的激动一下。。
如果直接把100分的代码贴出来，也没啥用。我把分数逐渐增长的所有代码都贴出来，万一自己以后又做到这道题没有思路可作参考。
确实很麻烦。如果直接看100分的会一头雾水，还写不出来注释，思想太复杂了。只可意会。
想看简单题解的OIer可以去洛谷题解上看。
63分：

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

#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int price[5005];
int dp[5005];
int ways[5005];
bool visited[65537];
int main() {
cin >> n;
for (int i = 1; i <= n; i++)cin >> price[i];
for (int i = 1; i <= n+1; i++) {
int mDpV = 0, cWays = 1;
for (int j = 1; j < i; j++) {
if (price[j] > price[i]) {
if (dp[j] > mDpV) {
mDpV = dp[j];
cWays = ways[j];
memset(visited, false, sizeof(visited));
visited[price[j]] = true;
}
if (dp[j] == mDpV && !visited[price[j]]) {
cWays += ways[j];
visited[price[j]] = true;
}
}
}
dp[i] = mDpV + 1;
ways[i] = cWays;
}
cout << dp[n+1]-1 << " " <<ways[n+1];
}

73分：把memset的范围调小了

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

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int price[5005];
int dp[5005];
int ways[5005];
bool visited[65537];
int main() {
cin >> n;
price[0] = 65537;
ways[0] = 1;
int vmax = 0, vmin = 65537;
for (int i = 1; i <= n; i++) {
cin >> price[i];
vmax = max(vmax, price[i]);
vmin = min(vmin, price[i]);
}
for (int i = 1; i <= n+1; i++) {
int mDpV = dp[0], cWays = 1;
for (int j = 1; j < i; j++) {
if (price[j] > price[i]) {
if (dp[j] > mDpV) {
mDpV = dp[j];
cWays = ways[j];
memset(visited + vmin, false, sizeof(int)*(vmax - vmin + 1));
visited[price[j]] = true;
}
if (dp[j] == mDpV && !visited[price[j]]) {
cWays += ways[j];
visited[price[j]] = true;
}
}
}
dp[i] = mDpV + 1;
ways[i] = cWays;
}
cout << dp[n+1]-1 << " " <<ways[n+1];
}

82分：不在每个j处都memset，而是利用版本号的想法，改为在i处更新。

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

#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int price[10000];
long long dp[10000];
long long ways[10000];
int visited[65540]; //[price][version()]
int main() {
cin >> n;
int vmax = 0, vmin = 65537;
for (int i = 1; i <= n; i++) {
cin >> price[i];
vmax = max(vmax, price[i]);
vmin = min(vmin, price[i]);
}
for (int i = 1; i <= n+1; i++) {
long long mDpV = 0;
long long cWays = 1;
memset(visited, 0, sizeof(visited));
for (int j = 1; j < i; j++) {
if (price[j] > price[i]) {
if (dp[j] > mDpV) {
mDpV = dp[j];
cWays = ways[j];
visited[price[j]] = mDpV;
}
if (dp[j] == mDpV && visited[price[j]]<mDpV) {
cWays += ways[j];
visited[price[j]] = mDpV;
}
}
}
dp[i] = mDpV + 1;
ways[i] = cWays;
}
cout << dp[n+1]-1 << " " <<ways[n+1];
}

100分：参考别人题解发现了用后面替代前面的重要问题。

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

#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int price[10000];
long long dp[10000]; //DP 数组
long long ways[10000]; //方法数数组
long long visited[65540][2]; // [price][0]代表当前最长降序子序列长度，[price][1]代表在此情况下的方法数
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> price[i];
for (int i = 1; i <= n+1; i++) {
long long mDpV = 0;
long long cWays = 1;
memset(visited, 0, sizeof(visited));
for (int j = 1; j < i; j++) {
if (price[j] > price[i]) {
//当visited[price[j]][0]有更新时，用后面的替代前面的，因为相应的方法数也会有更新
if (dp[j] == mDpV && visited[price[j]][0]==mDpV) {
cWays += ways[j];
cWays -= visited[price[j]][1];
visited[price[j]][1] = ways[j];
}
else if (dp[j] == mDpV && visited[price[j]][0]<mDpV) {
cWays += ways[j];
visited[price[j]][0] = mDpV;
visited[price[j]][1] = ways[j];
}
else if (dp[j] > mDpV) {
mDpV = dp[j];
cWays = ways[j];
visited[price[j]][0] = mDpV;
visited[price[j]][1] = ways[j];
}

}
}
dp[i] = mDpV + 1;
ways[i] = cWays;
}
cout << dp[n+1]-1 << " " <<ways[n+1];
}

洛谷 P1058 立体图

发表评论

虽然写的时间很长，但是AC之后随便画图可是很好玩的哦。。。

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<functional>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int m, n, am, an;
int arr[55][55];
char output[500][500];
int calM(int m, int mh, int tm) { //每行挑最大的执行一次
return (tm - m + 1) * 2 + max(1 + 3 * mh, 1 + 2 * (m - 1));
}
inline int calN(int m, int n) { //整体执行一次
return 1 + 4 * n + 2 * m;
}
inline void printLine(int x, int y) {
output[x][y] = output[x][y + 4] = '+';
output[x][y + 1] = output[x][y + 2] = output[x][y + 3] = '-';
}
inline void printRow(int x, int y) {
output[x][y] = output[x + 2][y - 2] = '+';
output[x + 1][y - 1] = '/';
}
inline void printHeight(int x, int y) {
output[x][y] = output[x + 3][y] = '+';
output[x + 1][y] = output[x + 2][y] = '|';
}
inline void printSpace(int x, int y) {
output[x + 1][y] = output[x + 1][y + 1] = output[x + 1][y + 2] = ' ';
output[x + 3][y - 1] = output[x + 3][y] = output[x + 3][y + 1] = ' ';
output[x + 4][y - 1] = output[x + 4][y] = output[x + 4][y + 1] = ' ';
output[x + 2][y + 3] = output[x + 3][y + 3] = ' ';
}
inline void printCube(int x, int y) { //左上角坐标
printLine(x, y);
printLine(x + 2, y - 2);
printLine(x + 5, y - 2);
printRow(x, y);
printRow(x, y + 4);
printRow(x + 3, y + 4);
printHeight(x + 2, y - 2);
printHeight(x + 2, y + 2);
printHeight(x, y + 4);
printSpace(x, y);
}
inline void printCube2(int l, int r, int h) {
printCube(am - 3 * h - 2 * (m-l+1), 1+2 * (m - l + 1) + (r - 1) * 4);
}
inline void printAns() {
for (int i = 1; i <= am; i++) {
cout << output[i] + 1 << endl;
}
cout << endl;
}
int main() {
cin >> m >> n;
an = calN(m, n);
for (int i = 1; i <= m; i++) {
int mmax = 0;
for (int j = 1; j <= n; j++) {
cin >> arr[i][j];
mmax = max(mmax, arr[i][j]);
}
am = max(am, calM(i, mmax, m));
}
for (int i = 1; i <= am; i++) {
for (int j = 1; j <= an; j++) {
output[i][j] = '.';
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= arr[i][j]; k++) {
printCube2(i, j, k);
//printAns();
}
}
}
printAns();
}

提示：把79行的注释符号去掉可以看到图形生成全过程哦；
写了个好玩的小程序，随机生成数组中的高度哦。。。
各位OIer可以随便试试。。。

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<functional>
#include<ctime>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int m, n, am, an;
int arr[55][55];
char output[500][500];
int calM(int m, int mh, int tm) { //每行挑最大的执行一次
return (tm - m + 1) * 2 + max(1 + 3 * mh, 1 + 2 * (m - 1));
}
inline int calN(int m, int n) { //整体执行一次
return 1 + 4 * n + 2 * m;
}
inline void printLine(int x, int y) {
output[x][y] = output[x][y + 4] = '+';
output[x][y + 1] = output[x][y + 2] = output[x][y + 3] = '-';
}
inline void printRow(int x, int y) {
output[x][y] = output[x + 2][y - 2] = '+';
output[x + 1][y - 1] = '/';
}
inline void printHeight(int x, int y) {
output[x][y] = output[x + 3][y] = '+';
output[x + 1][y] = output[x + 2][y] = '|';
}
inline void printSpace(int x, int y) {
output[x + 1][y] = output[x + 1][y + 1] = output[x + 1][y + 2] = ' ';
output[x + 3][y - 1] = output[x + 3][y] = output[x + 3][y + 1] = ' ';
output[x + 4][y - 1] = output[x + 4][y] = output[x + 4][y + 1] = ' ';
output[x + 2][y + 3] = output[x + 3][y + 3] = ' ';
}
inline void printCube(int x, int y) { //左上角坐标
printLine(x, y);
printLine(x + 2, y - 2);
printLine(x + 5, y - 2);
printRow(x, y);
printRow(x, y + 4);
printRow(x + 3, y + 4);
printHeight(x + 2, y - 2);
printHeight(x + 2, y + 2);
printHeight(x, y + 4);
printSpace(x, y);
}
inline void printCube2(int l, int r, int h) {
printCube(am - 3 * h - 2 * (m - l + 1), 1 + 2 * (m - l + 1) + (r - 1) * 4);
}
inline void printArray() {
cout << "Printing each element of the array:" << endl;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= m; j++) {
cout << arr[i][j] << " ";
}
cout << endl;
}
}
inline void printAns() {
for (int i = 1; i <= am; i++) {
cout << output[i] + 1 << endl;
}
cout << endl;
}
int main() {
srand((unsigned)time(NULL));
cout << "Please input the side length "n" of the cube array (n<=50):";
int len;
cin >> len;
m = n = len;
an = calN(m, n);
cout << "Please input the max height "mh" of cubes in each array item (1<=mh<=100):";
int mh;
cin >> mh;
cout << "Do you want to show the whole process of filling?(Answer with 0[No] or 1[Yes]):";
bool flag;
cin >> flag;
for (int i = 1; i <= m; i++) {
int mmax = 0;
for (int j = 1; j <= n; j++) {
arr[i][j] = rand() % mh + 1;
mmax = max(mmax, arr[i][j]);
}
am = max(am, calM(i, mmax, m));
}
for (int i = 1; i <= am; i++) {
for (int j = 1; j <= an; j++) {
output[i][j] = '.';
}
}
cout << "Automatically generated an array,printed in the following.Press ENTER to continue." << endl;
printArray();
cin.get(); cin.get();
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= arr[i][j]; k++) {
if (flag)cout << "Printing cube on postion(" << i << "," << j << "," << k << ")." << endl;
printCube2(i, j, k);
if (flag)printAns();
}
}
}
cout << "Printing Final Result:" << endl;
printAns();
}

洛谷 P1541 乌龟棋

发表评论

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

#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<cstring>
using namespace std;
int n,m;
int a[355],b[6];
int f[45][45][45][45];
int safeF(int i,int j,int k,int l){
if(i<0||j<0|k<0||l<0)return 0;
else return f[i][j][k][l];
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++){
int t;
cin>>t;
b[t]++;
}
for(int i=0;i<=b[1];i++)for(int j=0;j<=b[2];j++)for(int k=0;k<=b[3];k++)for(int l=0;l<=b[4];l++){
f[i][j][k][l]=max(max(safeF(i-1,j,k,l),safeF(i,j-1,k,l)),max(safeF(i,j,k-1,l),safeF(i,j,k,l-1)))+a[i+2*j+3*k+4*l+1];
}
cout<<f[b[1]][b[2]][b[3]][b[4]];
}

洛谷 P1880 [NOI1995]石子合并

发表评论

转移方程是看别人的……
参考：易懂https://www.luogu.org/blog/user45556/solution-p1880
区间动规经典题目？

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

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int arr[205];
int presum[205];
int fMax[205][205], fMin[205][205];
int dfsMax(int l, int r) {
if (l == r)return 0;
if (fMax[l][r] != 0)return fMax[l][r];
int dIJ = presum[r] - presum[l - 1];
int mmax = 0;
for (int k = l; k < r; k++) mmax = max(mmax, dfsMax(l, k) + dfsMax(k + 1, r) + dIJ);
return fMax[l][r] = mmax;
}
int dfsMin(int l, int r) {
if (l == r)return 0;
if (fMin[l][r] != 0)return fMin[l][r];
int dIJ = presum[r] - presum[l - 1];
int mmin = 0x7fffffff;
for (int k = l; k < r; k++)mmin = min(mmin, dfsMin(l, k) + dfsMin(k + 1, r) + dIJ);
return fMin[l][r] = mmin;
}
int main(){
cin >> n;
for (int i = 1; i <= n; i++)cin >> arr[i];
for (int i = n + 1; i <= 2*n; i++)arr[i] = arr[i - n];
for (int i = 1; i <= 2 * n; i++)presum[i] = presum[i - 1] + arr[i];
int mmin = 0x7fffffff;
for (int i = 1; i <= n; i++) {
mmin = min(mmin, dfsMin(i, i + n - 1));
}
cout << mmin << endl;
int mmax = 0;
for (int i = 1; i <= n; i++) {
mmax = max(mmax, dfsMax(i, i + n - 1));
}
cout << mmax << endl;

}

洛谷 P3383 【模板】线性筛素数

发表评论

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

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m;
bool prime[10000005];

int main(){
memset(prime, true, sizeof(prime));
cin >> n >> m;
prime[0] = prime[1] = false;
for (int i = 2; i <= n; i++) {
if (!prime[i])continue;
for (int j = 2 * i; j <= n; j += i) {
prime[j] = false;
}
}
for (int i = 1; i <= m; i++) {
int tmp;
cin >> tmp;
cout << (prime[tmp]?"Yes":"No") << endl;
}
}

洛谷 P1020 导弹拦截

发表评论

又是自己改了半天的一道题，忘了……

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

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int n=1;
int arr[100005];
int f[100005];
int f2[100005];
int main() {
while (cin >> arr[n])n++;
n--;
arr[0] = 50001;
f[0] = 0;
for (int i = 1; i <= n; i++) {
int m = f[0];
for (int j = 1; j < i; j++) {
if (f[j]>m&&arr[j]>=arr[i]) {
m = f[j];
}
}
f[i] = m + 1;
}
cout << *max_element(f+1,f+n+1) << endl;
arr[0] = 0;
f2[0] = 0;
for (int i = 1; i <= n; i++) {
int m = f2[0];
for (int j = 1; j < i; j++) {
if (f2[j]>m&&arr[j]<arr[i]) {
m = f2[j];
}
}
f2[i] = m + 1;
}
cout << *max_element(f2+1,f2+n+1) << endl;
}

洛谷 P1233 木棍加工

发表评论

不好做啊……想不出来……看题解……

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

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int n;
struct node {
int l, w;
bool operator < (const node& n2) const {
if (l != n2.l)return l > n2.l;
if (w != n2.w)return w > n2.w;
return false;
}
}arr[5005];
bool visited[5005];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i].l >> arr[i].w;
}
sort(arr + 1, arr + n + 1);
bool flag = false;
int cnter = 0, ptr = 0;
do {
flag = false;
for (ptr=1;ptr <= n; ptr++) {
if (!visited[ptr]) {
flag = true;
visited[ptr] = true;
break;
}
}
if (!flag)break;
cnter++;
for (int i = ptr+1; i <= n; i++) {
if (visited[i] || arr[i].l > arr[ptr].l || arr[i].w > arr[ptr].w) continue;
visited[i] = true;
ptr = i;
}
} while (flag);
cout << cnter;
}

洛谷 P1080 国王游戏

发表评论

这题不好写，一个问题在贪心怎么排序，再有的难点就是高精乘/除，都不好写。。
这次正经的写了个高精度乘/除。。留下来备用。

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int n;
struct bigInt { //For Non-negative Numbers
private:
string v;
static string & bIsort(string & v) { //each char has reduced '0'
for (int i = 0; i < v.length(); i++) {
if (v[i] > 9) {
if (i == v.length() - 1)v.append(1, v[i] / 10);
else v[i + 1] += v[i] / 10;
v[i] %= 10;
}
}
return v;
}
static string lng2str(long long v) {
string s = "";
while (v) {
s.append(1, v % 10 + '0');
v /= 10;
}
reverse(s.begin(), s.end());
return s;
}
static string& trimPre0(string& v3) {
while (v3.length() != 0 && (*v3.begin()) == '0')v3.erase(v3.begin());
if (v3.length() == 0)v3 = "0";
return v3;
}
public:
bigInt() {
v = "0";
}
bigInt(long long n) {
v = lng2str(n);
}
bigInt(string s) {
v = s;
}
bigInt& operator = (const bigInt & bI) {
this->v = bI.v;
return *this;
}
bigInt operator * (bigInt bI2) const {
string v1 = v, v2 = bI2.v;
if (v2.length() > v1.length())swap(v1, v2);
reverse(v1.begin(), v1.end());
reverse(v2.begin(), v2.end());
string v3 = "";
for (int i = 0; i < v1.length(); i++)v1[i] -= '0';
for (int i = 0; i < v2.length(); i++)v2[i] -= '0';
v3.resize(v1.length() + v2.length(), 0);
for (int i = 0; i < v2.length(); i++) {
for (int j = 0; j < v1.length(); j++) {
v3[i + j] += v2[i] * v1[j];
}
bIsort(v3);
}
for (int i = 0; i < v3.length(); i++)v3[i] += '0';
reverse(v3.begin(), v3.end());
trimPre0(v3);
return bigInt(v3);
}
bigInt operator / (long long bI2) const {
string v1 = v;
for (int i = 0; i < v1.length(); i++)v1[i] -= '0';
long long v2 = bI2;
string v3 = "";
long long div = 0;
for (int i = 0; i < v1.length(); i++) {
div *= 10;
div += v1[i];
if (div < v2) {
v3.append(1, '0');
continue;
}
v3.append(lng2str(div / v2));
div %= v2;
}
return bigInt(trimPre0(v3));
}
bool operator < (bigInt bI2) const {
if (v.length() != bI2.v.length())return v.length() < bI2.v.length();
for (int i = 0; i < v.length(); i++) {
if (v[i] != bI2.v[i])return v[i] < bI2.v[i];
}
return false;
}
friend istream& operator >> (istream& in, bigInt& bI) {
in >> bI.v;
return in;
}
friend ostream& operator << (ostream& out, bigInt& bI) {
out << bI.v;
return out;
}
};
struct p {
bigInt a;
int b;
bool operator < (const p& p2) {
return a * b < p2.a*p2.b;
}
}ps[1005];

int main() {
cin >> n;
for (int i = 1; i <= n + 1; i++) {
cin >> ps[i].a >> ps[i].b;
}
sort(ps + 2, ps + n + 2);
bigInt multiply = ps[1].a;
bigInt mmax("0");
for (int i = 2; i <= n + 1; i++) {
mmax = max(mmax, multiply / ps[i].b);
multiply =multiply* ps[i].a;
}
cout << mmax;
}

杰克部落

梦想本不会发光，发光的是追梦的你

分类目录归档：算法

洛谷 P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

洛谷 P2661 信息传递

洛谷 P1108 低价购买

洛谷 P1058 立体图

洛谷 P1541 乌龟棋

洛谷 P1880 [NOI1995]石子合并

洛谷 P3383 【模板】线性筛素数

洛谷 P1020 导弹拦截

洛谷 P1233 木棍加工

洛谷 P1080 国王游戏

2024 年 11 月
一	二	三	四	五	六	日
				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