专业题1
一个k（1<=k<=80）位的十进制整数n，我们称其为大整数。现在的问题是，请你设计一个程序，对于给出的某个大整数，找到满足条件p^3+p^2+3 * p<=n的p的最大值。
一个大整数n。
一个符合条件的答案值。
1908
12
8620110
204
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #偷懒的Python代码
def f(x):
return x*x*x+x*x+3*x
num=int(input())
left=0;
right=num;
mid=0;
mark=0
while left<right:
mid=int((left+right)/2)
#print("midzhi ",mid)
fx=f(mid)
if fx==num:
ans=mid
mark=1
break
elif fx>num:
right=mid
else:
left=mid+1
if mark==0:
ans=left-1
print(ans)
|
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
| #include<bits/stdc++.h>
using namespace std;
const int MAXN = 2000;
struct bign {
int len, s[MAXN];
bign () {
memset(s, 0, sizeof(s));
len = 1;
}
bign (int num) {
*this = num;
}
bign (const char *num) {
*this = num;
}
int operator [] (int a) {
return s[a];
}
bign operator = (const int num) {
char s[MAXN];
sprintf(s, "%d", num);
*this = s;
return *this;
}
bign operator = (const char *num) {
for(int i = 0; num[i] == '0'; num++) ;
len = strlen(num);
for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';
return *this;
}
bign operator + (const bign &b) const {
bign c;
c.len = 0;
for(int i = 0, g = 0; g || i < max(len, b.len); i++) {
int x = g;
if(i < len) x += s[i];
if(i < b.len) x += b.s[i];
c.s[c.len++] = x % 10;
g = x / 10;
}
return c;
}
bign operator += (const bign &b) {
*this = *this + b;
return *this;
}
void clean() {
while(len > 1 && !s[len-1]) len--;
}
bign operator * (const bign &b)
{
bign c;
c.len = len + b.len;
for(int i = 0; i < len; i++) {
for(int j = 0; j < b.len; j++) {
c.s[i+j] += s[i] * b.s[j];
}
}
for(int i = 0; i < c.len; i++) {
c.s[i+1] += c.s[i]/10;
c.s[i] %= 10;
}
c.clean();
return c;
}
bign operator *= (const bign &b) {
*this = *this * b;
return *this;
}
bign operator - (const bign &b) {
bign c;
c.len = 0;
for(int i = 0, g = 0; i < len; i++) {
int x = s[i] - g;
if(i < b.len) x -= b.s[i];
if(x >= 0) g = 0;
else {
g = 1;
x += 10;
}
c.s[c.len++] = x;
}
c.clean();
return c;
}
bign operator -= (const bign &b) {
*this = *this - b;
return *this;
}
bign operator / (const bign &b) {
bign c, f = 0;
for(int i = len-1; i >= 0; i--) {
f = f*10;
f.s[0] = s[i];
while(f >= b) {
f -= b;
c.s[i]++;
}
}
c.len = len;
c.clean();
return c;
}
bign operator /= (const bign &b) {
*this = *this / b;
return *this;
}
bign operator % (const bign &b) {
bign r = *this / b;
r = *this - r*b;
return r;
}
bign operator %= (const bign &b) {
*this = *this % b;
return *this;
}
bign operator ++() {
return *this+=1;
}
bign operator --() {
return *this-=1;
}
bool operator < (const bign &b) {
if(len != b.len) return len < b.len;
for(int i = len-1; i >= 0; i--) {
if(s[i] != b.s[i]) return s[i] < b.s[i];
}
return false;
}
bool operator > (const bign &b) {
if(len != b.len) return len > b.len;
for(int i = len-1; i >= 0; i--) {
if(s[i] != b.s[i]) return s[i] > b.s[i];
}
return false;
}
bool operator == (const bign &b) {
return !(*this > b) && !(*this < b);
}
bool operator != (const bign &b) {
return !(*this == b);
}
bool operator <= (const bign &b) {
return *this < b || *this == b;
}
bool operator >= (const bign &b) {
return *this > b || *this == b;
}
bign operator !() {
bign s=1;
for(bign i=1;i<=*this;++i)
s*=i; return s;
}
bign operator ^ (const bign& b) {
bign s=1;
for(bign i=0;i<b;++i)
s*=*this;return s;
}
bign sqrt() {
bign c=*this/2;
while((c*c)>*this) c/=2;
while((c*c)<=*this) ++c;
return c-1;
}
/*string operator *(){
string op="Hello World";
return op;
}*/
string str() const {
string res = "";
for(int i = 0; i < len; i++) res = char(s[i]+'0') + res;
return res;
}
};
istream& operator >> (istream &in, bign &x) {
string s;
in >> s;
x = s.c_str();
return in;
}
ostream& operator << (ostream &out, const bign &x) {
out << x.str();
return out;
}
int main() {
// bign a,b;
// cin>>a>>b;
// cout<<a+b;
bign left=0,n,mid,value,ans;
int mark=0;
cin>>n;
bign right=n;
while(left<right) {
mid=(left+right)/2;
value=mid*mid*mid+mid*mid+(bign)3*mid;
if(value==n) {
ans=mid;mark=1;break;
}else if(value>n) {
right=mid;
}else {
left=mid+1;
}
}
if(mark==0) ans=left-1;
cout<<ans;
return 0;
}
|
专业题2
在一个棋盘上有N个处于不同位置的棋子，每个棋子所在的位置都可以用坐标(X,Y)来表示，并且任一棋子每次可以向上、下、左、右移动单位长度。如果想让所有棋子进入一个水平线，彼此靠近，即它们最后的位置是(X,Y)、(X+1,Y)、……、(X+N,Y)，水平线上棋子的最后顺序是任意的，那么最少需要移动多少次棋子？
注意：两个或两个以上的棋子不能在同一时间处于同一位置。
第一行是一个整数N，表示棋子数，1<=N<=10000。后面的N行分别是每个棋子的初始位置，包含空格分开的整数x、y，-10000<=x,y<=10000。
仅有一行一个值，表示使棋子移到水平线彼此相邻位置的最小移动次数。
5
1 2
2 2
1 3
3 -2
3 3
8
解题思路：中位数、贪心
- 先将棋子移动到同一水平线，这一水平线的位置应该是它们纵坐标的中位数，可通过排序后得到中位数b，这样就能使得移动的总步数$\sum_{i=1}^{n}abs(y_i-b)$最少。
- 然后要让棋子彼此靠近，先对横坐标从小到大排序，假设起点是a，那么要求$\sum_{i=1}^{n}abs(a+i-x_i)$，即$\sum_{i=1}^{n}abs(a-(x_i-i))$，也即$\sum_{i=1}^{n}abs((x_i-i)-a)$。当a是$x_i-i$序列的中位数时，可使移动步数最少，同样地，这个中位数可以通过排序后得到。
- 将上述两步的结果相加，得到的就是最后结果了。
参考代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include<bits/stdc++.h>
using namespace std;
int a[10010],b[10010],n,i,x,y,ans;
int main() {
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
sort(b+1,b+n+1);
y=b[n+1>>1];
sort(a+1,a+n+1);
for(i=1;i<=n;i++) a[i]-=i;
sort(a+1,a+n+1);
x=a[n+1>>1];
for(i=1;i<=n;i++) ans+=abs(a[i]-x)+abs(b[i]-y);
printf("%d\n",ans);
return 0;
}
|