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

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

Alice and Bob

题意

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

思路

$$\begin{array} \,f(x,m)&=&\Big|\{i \mid i \in [0,x],\, m | i\,\}\Big| \\ \\ g(n,m)&=&\bigg\{ \begin{array} \,f(x,m)&\quad n = 1 \\ f(10^n -1,m) - f(10^{n-1}-1,m) &\quad n \gt 1 \end{array} \end{array}$$

$g(n,m)$为题目所求，其中$f(x,m) = \lfloor x/m \rfloor + 1$。

标程

#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

题意

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

思路

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

标程

#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，二分等。

标程

#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$都可以立刻得到最后结果。

标程

#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

题意

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

思路

$$S_{A \cup B} = S_A + S_B - S_{A \cap B}$$

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

标程

#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为后缀的不重复字符子串的最大长度。

$$dp[i] = min\Big\{ \begin{array}dp[i-1]+1 \\ i-k \mid k \lt i , s[i] = s[k] \end{array}$$

所以记录下每个字符最后出现的位置，然后动态规划，$max\{dp[i] \mid i = 1,2,\ldots,n\}$即为不重复字符子串的最大长度。
然后再扫描$dp[i]$，求得所有的不重复字符最长的子串。

标程

#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;
}