程序设计实践-201601期末题解

题目 类型 难度
Alice and Bob 数学
Completed String 统计,执行
Duplicate Elements 查找,执行
Fish 贪心,优先队列 ★★
Rectangle Union 几何,容斥 ★★
Unique Characters String 动态规划 ★★★★

Alice and Bob

题意

求n位数中能整除m的数有多少个?

思路

$g(n,m)$为题目所求,其中$f(x,m) = \lfloor x/m \rfloor + 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
#include <iostream>
#include <cmath>
typedef unsigned long long ULL;
ULL get(unsigned int n,ULL m){
ULL x = 1;
for(unsigned int i = 0; i<n; i++)
x *= 10ULL;
x--;
return x/m + 1ULL;
}
int main()
{
unsigned int n,k;
ULL m;
std::cin >> k;
while(k--){
std::cin >> n >> m;
if(n>1)
std::cout << get(n,m) - get(n-1,m) << std::endl;
else
std::cout << get(1,m) << std::endl;
}
return 0;
}

Completed String

题意

判断字符串是否含所有英文字母(不区分大小写)

思路

直接统计即可,数组或者位运算都可以。

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <string>
#include <iostream>
bool check(std::string &s){
unsigned int tag = 0;
for(unsigned int i=0;i<s.length();i++){
if(s[i]>='a' && s[i] <= 'z')
tag |= (1 << (s[i] - 'a'));
else
tag |= (1 << (s[i] - 'A'));
}
return tag == 0x3ffffff;
}
int main(){
std::string s;
while(std::cin >> s){
std::cout << (check(s)?"Yes":"No") << std::endl;
}
return 0;
}

Duplicate Elements

题意

给一个数字序列,求去重之后的序列(要保持原序列的相对顺序)

思路

每得到一个数,查之前是否出现过,出现过就丢弃,没出现过就按顺序存下来。查找可以用set,hash,二分等。

标程

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
#include <cstdio>
#include <set>
using namespace std;
const int N = 10011;
int a[N];
int main()
{
int k,n,i,t,m;
scanf("%d",&k);
while(k--){
scanf("%d",&n);
set<int> s;
for(i=0,m=0;i<n;i++) {
scanf("%d",&t);
if(s.insert(t).second)
a[m++] = t;
}
for(i=0;i<m-1;i++){
printf("%d ",a[i]);
}
printf("%d\n",a[m-1]);
}
return 0;
}

Fish

题意

题目来源于 POJ 1042 Go Fish, 简化了题目,只是要求贪心的部分。

在$n$个池塘钓鱼,每个池塘单位时间能钓$a_i$条鱼,池塘每钓1次,下次钓鱼的数目会减少$b_i$,最多可以钓多少条鱼?

思路

贪心是很明显的,每次都取鱼数最多的池塘钓就可以了。
因为池塘鱼数是动态的,所以利用优先队列维护一下即可。
另外,如果发现队头元素$a_i = 0$或者$b_i = 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
#include <iostream>
#include <queue>
#include <utility>
#include <algorithm>
int main()
{
int ca,n,m,a,b,i,s;
std::pair<int,int> t;
std::cin >> ca;
while(ca--){
std::cin >> n >> m;
std::priority_queue<std::pair<int,int> > pool;
for(i=0;i<n;i++){
std::cin >> a >> b;
pool.push(std::make_pair(a,-b));
}
for(i=0,s=0;i<m&&!pool.empty();i++){
t = pool.top();
if(t.first == 0) break;
pool.pop();
if(t.second == 0){
s += (m-i)*t.first;
break;
} else {
s += t.first;
t.first += t.second;
if(t.first > 0)
pool.push(t);
}
}
std::cout << s << std::endl;
}
return 0;
}

Rectangle Union

题意

求两个平行于坐标轴的矩形面面积并。

思路

由于矩形是平行于坐标轴的,所以矩形的交可以分别投影到$X$和$Y$轴,两个坐标轴上投影区间交的乘积即为矩形面积交。

标程

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
#include <bits/stdc++.h>
using namespace std;
class Rect{
public:
int x1,y1,x2,y2;
int area(){
return (x2-x1)*(y2 -y1);
}
Rect(int x1,int y1,int x2,int y2){
if(x1 < x2)
this->x1 = x1,this->x2 = x2;
else
this->x2 = x1,this->x1 = x2;
if(y1 < y2)
this->y1 = y1,this->y2 = y2;
else
this->y2 = y1,this->y1 = y2;
};
};
int overlap(const int L1,const int R1,const int L2,const int R2){
int L,R;
L = R = 0;
if(L1 <= L2 && L2 <= R1){
L = L2;
if( R2 < R1)
R = R2;
else
R = R1;
} else if(L2 <= L1 && L1 <= R2) {
L = L1;
if( R1 < R2)
R = R1;
else
R = R2;
}
return R - L;
}
int area_join(const Rect &a,const Rect &b){
int x,y;
x = overlap(a.x1,a.x2,b.x1,b.x2);
y = overlap(a.y1,a.y2,b.y1,b.y2);
//cout << "overlap:" << x << ' ' << y << endl;
return x*y;
}
int area_union(Rect &a,Rect &b){
return a.area() + b.area() - area_join(a,b);
}
int main(){
int x1,y1,x2,y2;
while(~scanf("%d %d %d %d",&x1,&y1,&x2,&y2)){
//assert(x1>0 && x2>0 && y1>0 && y2>0);
Rect a(x1,y1,x2,y2);
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
//assert(x1>0 && x2>0 && y1>0 && y2>0);
Rect b(x1,y1,x2,y2);
printf("%d\n",area_union(a,b));
}
return 0;
}

Unique Characters String

题意

求一个字符串中不重复字符最长的子串。

思路

$dp[i]$ 表示以字符i为后缀的不重复字符子串的最大长度。

所以记录下每个字符最后出现的位置,然后动态规划,$max\{dp[i] \mid i = 1,2,\ldots,n\}$即为不重复字符子串的最大长度。
然后再扫描$dp[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
#include <bits/stdc++.h>
using namespace std;
const unsigned int N = 10011;
int main()
{
char str[N]="";
int last[26],left[N],i,len,j,ans;
while(gets(str+1)){
memset(last,0,sizeof(last));
memset(left,0,sizeof(left));
ans = 0;
len = strlen(str+1);
for(i=1;i<=len;i++){
j = last[str[i] - 'a'];
left[i] = i - j;
if(left[i] > left[i-1] + 1) left[i] = left[i-1] + 1;
if(left[i] > ans )
ans = left[i];
last[str[i] - 'a'] = i;
}
set<string> ss;
set<string>::iterator is;
for(i=1;i<=len;i++){
if(left[i] == ans){
string s(str+i-ans+1,str+i+1);
ss.insert(s);
}
}
cout << ans << '\n';
for(is = ss.begin(); is != ss.end(); is++)
cout << *is << '\n';
}
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!