UCF Local Programming Contest 2012(Practice)2020/03/04 计蒜客

题目地址 https://www.jisuanke.com/contest/7332?view=challenges

H. Ordered Numbers

就三个数的排序,原样和排序后的输出一遍。

printf("   Original order: %d %d %d\n", a, b, c);
if (a > b) swap(a, b);
if (a > c) swap(a, c);
if (b > c) swap(b, c);
printf("   Smallest to largest: %d %d %d\n\n", a, b, c);

B. How Old Are You Mr.String?

两个字符串比大小,只不过是先看z出现次数,再y出现次数,以此类推,具体看题,自己被getline坑,应该是他们行末的空格?<-这个坑回来再填

string a,b;
cin>>a;
sort(a.begin(),a.end(),cmp);
cin>>b;
sort(b.begin(),b.end(),cmp);
cout<<"Data set #"<<i<<": ";
if (a>b) cout<<"First string is older\n\n";
else if (a<b) cout<<"First string is younger\n\n";
else cout<<"The two strings are the same age\n\n";

C. Clean Up the Powers that Be

题目说了因子已经是素了的,所以拿map加一下幂就好了,就是格式化得注意一下

void space(int a){
// 算空格个数
	int s=0;
	while(a>0){
		a=a/10;
		s++;
	}
	for (int i=0;i<s;i++) printf(" ");
}
int main(){
	//..
	map<int,int> mymap;
	for (int i=0;i<n;i++){
		int a,b;
		scanf("%d %d",&a,&b);
                // 真就拿map加一加
		if (mymap.find(a)==mymap.end()) mymap[a]=b;
		else mymap[a]+=b;
	}
	printf("Prime Factorization #%d:\n",k);
	for (auto &item:mymap){  // C++11 auto 迭代STL容器
	// 没有&是值传递,不能修改 加了&是引用就可以改啦 虽然我这里没有修改
		space(item.first);
		printf("%d",item.second);
	}
	printf("\n");
	for (auto &item:mymap){
		printf("%d",item.first);
		space(item.second);
	}
	printf("\n\n");
	//..
}

G. Lifeform Detector

<s> 有 三种模式 : a<t>b<s>  或者 c<s> 或者 空
<t> 有两种模式: a<t>b<s> 或者 c<s>

将<t>,<s> 多带一带就会发现它其实是个括号匹配问题 c随意,a 左括号,b 右括号
根据题解少考虑了ab不能连起来的问题

bool judge(string s){
	int top=0;
	for (int i=0;i<s.size();i++){
		if (s[i]=='c') continue;
		if (s[i]=='a') top++;
		else top--;
		if (top<0) return false;
	}
	if (top>0) return false;
	return true;
}

D. The Clock Algorithm

操作系统页面置换算法LRU变种Clock算法,就模拟,题目大致翻译可以参考。

操作系统设计中有一项技术叫做虚拟内存,允许计算机运行一个需要内存大于可用物理内存的程序,内存被分成页(pages),是固定大小的。
程序申请访问一个没有被加载到内存的页,会出现缺页中断(page falut) (意味着每页的第一次访问必然出现缺页)
如果程序需要访问另外一个内存可以容纳的页(假设它原本不在其中),之前加载的某一页必须被换出(swap),写到磁盘上,这个问题中我们讨论一种LRU的变体 时钟算法 Clock algo.
这种算法这样工作:
最初内存里n个 page cell 都是空的 (可以放page的格子,最多放n页的意思) 可以想象成一个大小为n的数组
另外,时钟算法持有一个 “hand pointer” 最初指向 cell 1(第一个空格子),我们后面就管他叫指针

现在我们假设每一页还有一个flag,程序需要访问某一页的时候,他检查这页有没有在内存里(有没有在这些格子里),如果在内存里,这一页的flag变成new;如果没有在内存里,把这一页加载到下一个为空的cell里面,并设置新加载的这页的flag为new

如果没有空的cell (因为只有n个cell,放满了) 我们就找hand pointer 指向的那个cell,如果那一页的标记是old。我们就把他换成我现在请求的这一页,新加载的flag标记成new,指针向前移动一位(循环的 n的一下一位就是1,可以用0..n-1)

所以新加载进来的一定的flag是new。

然后这个算法给了一个单元个两次机会 也就是本来是new 变成old 转回来他还是old的时候他就要换出去了

然后如果他被标记成old,但没有被换出(有之前的old被换)再一次请求他就会变成new

(最后实现了LRU的变体 LRU指的就是 最久没被访问的换掉,LRU中文翻译很蠢就不说了)

输入
n,r;n是可用的内存块(page cell) r 是请求内存的次数
接下来是r个整数 代表着请求的页号
以 0 0结束

输出
一开始是Program p
对于每个请求
如果 ri 没有在内存里,输出 Page ri loaded into cell c
如果在内存里 输入Access page ri in cell c
最后输出 There are a total of k page faluts k次缺页
换行

不如看看代码?

int pageincell[60];  // cell里存放的page的编号
int page2cell[60];   // page对应的cell 如果page 不存在就是-1
bool flag[60];       // cell的标记
int main(){
	int n,r;
	int t=0;
	while (~scanf("%d%d",&n,&r)){
		if (n==0 && r==0) break;
		printf("Program %d\n",++t);
		for (int i=0;i<60;i++) {
			pageincell[i]=55;
			page2cell[i]=-1;
			flag[i] = false;
		}
		int page;
		int hand=0;   // 指针
		int falut=0;  // 缺页次数
		for (int i=0;i<r;i++){
			scanf("%d",&page);
			if (page2cell[page]!=-1){ // 如果没缺页
				int cell = page2cell[page];   // 找到它的cell
				flag[cell] = true;            // 刷新成new
				printf("Access page %d in cell %d.\n",page,cell+1);  //输出
			}
			else{  // 缺页的话 找一个可以放的 一开始空的n个可以认为n个old的格子
				while(flag[hand]){
					flag[hand]=false;
					hand=(hand+1)%n;
				}
				page2cell[pageincell[hand]]=-1;  // 原来cell对应的page的置换出去
				pageincell[hand] = page;         // cell 放入这个page
				page2cell[page] = hand;          // 当前page 指向cell的位置
				flag[hand]=true;                 // flag刷新成new
				falut++;                         // 中断次数+1
				hand=(hand+1) % n;               // 指向下一个
				printf("Page %d loaded into cell %d.\n",page,hand+1);
			}
		}
		printf("There are a total of %d page faults.\n\n", falut);
	}	
}

A. Wall Street Monopoly

就区间DP,很明显,找一点区间DP的题先练练

struct node
{
	int length,depth,cost;  // 长 深 花费
};
node dp[25][25];  //dp[i][j] 表示的是i到j合并 所需要最小的花费,以及他们合并后的方块的长 深
int calc(int n){
	for (int len=1;len<n;len++){  //有len+1个相邻的格子合并,len=0 也就是一个格子自己合并初始话的时候就做了
		for (int i=0;i<n-len;i++){  // 枚举左端点
			int j = i+len;      // 确定右端点
			node &res = dp[i][j];  // 只要胆子大,引用爽到家,注意引用不能再次指向到另一个对象
			res.cost = -1;   // 一开始做个标记
			for (int k=i;k<j;k++){ // 确定中间谁分开
				// 左边合并的费用 加上右边合并的费用 加上这次合并的费用
				int val = dp[i][k].cost + dp[k+1][j].cost;
				// 这次合并的费用是左右两方块 各自比较长的边的积
				int val += min(dp[i][k].length,dp[i][k].depth)*
					min(dp[k+1][j].length,dp[k+1][j].depth);
				// 如果是第一次算出的结果,或者是比最小值小 那么
				if (res.cost==-1 || res.cost>val){
					// 根据题意,新合成的格子 长度相加 深度取二者较大的
					res.length = dp[i][k].length + dp[k+1][j].length;
					res.depth = max(dp[i][k].depth,dp[k+1][j].depth);
					res.cost = val;
				}
			}
		}
	}
	return dp[0][n-1].cost;
}
int main(){
	int t;
	cin>>t;
	for (int k=1;k<=t;k++){
		int n;
		cin>>n;
		for (int i=0;i<n;i++) {
			cin>>dp[i][i].length>>dp[i][i].depth;
			dp[i][i].cost=0;   //初始化,自己合并自己的不要钱
		}
		cout<<"The minimum cost for lot #"<<k<<" is $"<<100ll*calc(n)<<".\n\n"; 
		// 
	}	
}

F. Metallic Equipment Rigid

c个圆,p个点组成的路径,问路径接触了哪些圆圈,判断圆心到线段的距离就行,注意判断下面这种情况,周花的图(代码也是根据周的思路)

高虽然比半径小,但线段没有接触圆
double dis(point a, point b, circle o) {
	double ab = sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
	double oa = sqrt((a.x - o.x) * (a.x - o.x) + (a.y - o.y) * (a.y - o.y));
	double ob = sqrt((o.x - b.x) * (o.x - b.x) + (o.y - b.y) * (o.y - b.y));
	if ((oa * oa + ab * ab - ob * ob) / oa / ab / 2 <= 0) return  oa;  // 余弦定理,cos小于0说明是钝角
	if ((ob * ob + ab * ab - oa * oa) / ob / ab / 2 <= 0) return  ob;
	double p = (ab + oa + ob) / 2;  
	return sqrt(p * (p - ab) * (p - oa) * (p - ob)) * 2 / ab; // 这个是海伦公式,算面积的,把面积乘以2除以bc来算高
}

E. Pete’s Pantry

大模拟

Leave a comment

Your email address will not be published. Required fields are marked *