正文 

当前位置： 首页 > java > java教程

vijos1016北京2008的挂钟

author author     2022-09-03     786

关键词：

北京2008的挂钟

描述

技术分享

在2008北京奥运会雄伟的主会场的墙上，挂着如上图所示的3*3的九个挂钟（一开始指针即时针指向的位置请根据输入数据调整）。然而此次奥运会给与了大家一个机会，去用最少的移动操作改变上面的挂钟的时间全部为12点正（我们只考虑时针）。然而每一次操作并不是任意的，我们必须按照下面给出的列表对于挂钟进行改变。每一次操作我们给而且必须给指定的操作挂钟进行，每一个挂钟顺时针转动90度。列表如下：

操作 指定的操作挂钟
1 ABDE
2 ABC
3 BCEF
4 ADG
5 BDEFH
6 CFI
7 DEGH
8 GHI
9 EFHI

格式

输入格式

你的程序按照标准的3*3格式读入，一共9个0-3的数。0代表12点，1代表3点，2代表6点，3代表9点。

Your program is to read from standard input. Nine numbers give the start positions of the dials. 0=12 o‘clock, 1=3 o‘clock, 2=6 o‘clock, 3=9 o‘clock.

输出格式

你的程序需要写出标准的输出。输出一个最短的能够使所有挂钟指向12点的移动操作序列，中间以空格隔开，最后有空格，加回车。这一条最短操作需要是所有最短操作中最小的，也就是说选择最小的第一个操作数，如果第一个操作数相等，那么选择最小的第二个操作数……以此类推。值得肯定的是，这一条操作序列是唯一的。

Your program is to write to standard output. Output a shortest sorted sequence of moves (numbers), which returns all the dials to 12 o‘clock. You are convinced that the answer is unique.

样例1

样例输入1

3 3 0
2 2 2
2 1 2
Copy

样例输出1

4 5 8 9
Copy

限制

各个测试点1s

提示

Description

技术分享
(Figure 1)

There are nine clocks in a 3*3 array (figure 1). The goal is to return all the dials to 12 o‘clock with as few moves as possible. There are nine different allowed ways to turn the dials on the clocks. Each such way is called a move. Select for each move a number 1 to 9. That number will turn the dials 90‘ (degrees) clockwise on those clocks which are affected according to figure 2 below.

Move Affected clocks

1 ABDE
2 ABC
3 BCEF
4 ADG
5 BDEFH
6 CFI
7 DEGH
8 GHI
9 EFHI

(Figure 2)

Input 
Your program is to read from standard input. Nine numbers give the start positions of the dials. 0=12 o‘clock, 1=3 o‘clock, 2=6 o‘clock, 3=9 o‘clock.

Output 
Your program is to write to standard output. Output a shortest sorted sequence of moves (numbers), which returns all the dials to 12 o‘clock. You are convinced that the answer is unique.

来源

Vivian Snow
IOI 1994 The Clocks, From PKU 1166

 

优先队列优化的bfs.

喜闻乐见的Code

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int op[10][10]={{0},
					  {1,2,4,5},
					  {1,2,3},
					  {2,3,5,6},
					  {1,4,7},
					  {2,4,5,6,8},
					  {3,6,9},
					  {4,5,7,8},
					  {7,8,9},
					  {5,6,8,9}};
bool v[4][4][4][4][4][4][4][4][4]={0};
struct Clock {
	int t[10],st,o[100];
	bool operator < (const Clock &b)const {
		return st>b.st;
	}
}s;
void bfs() {
	priority_queue<Clock>Q;
	v[s.t[1]][s.t[2]][s.t[3]][s.t[4]][s.t[5]][s.t[6]][s.t[7]][s.t[8]][s.t[9]]=1;
	s.st=0;Q.push(s);
	while(!Q.empty()) {
		Clock T=Q.top();Q.pop();
		for(int i=1;i<=9;i++) {		//9种操作;
			int sum=0;s=T;
			for(int j=0;op[i][j];j++) {
				s.t[op[i][j]]++;
				s.t[op[i][j]]%=4;
			}
			if(v[s.t[1]][s.t[2]][s.t[3]][s.t[4]][s.t[5]][s.t[6]][s.t[7]][s.t[8]][s.t[9]]) continue;
			v[s.t[1]][s.t[2]][s.t[3]][s.t[4]][s.t[5]][s.t[6]][s.t[7]][s.t[8]][s.t[9]]=1;
			s.o[++s.st]=i;Q.push(s);
			if(s.t[1]||s.t[2]||s.t[3]||s.t[4]||s.t[5]||s.t[6]||s.t[7]||s.t[8]||s.t[9]) continue;
			sort(s.o+1,s.o+s.st+1);
			for(int j=1;j<=s.st;j++)
				printf("%d ",s.o[j]);
			return;
		}
	}
}
int main() {
	for(int i=1;i<=9;i++) scanf("%d",&s.t[i]);
	bfs();
	return 0;
}

　　

vijos2008愤怒的小鸟

先枚举两点，预处理这条抛物线能到达的所有点，随后状压dp。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#definemaxn20#defineeps1e-6usingnamespacestd;intt,n,m,f[1<<maxn],tab[ma 查看详情

测试基于挂钟时间的算法

】测试基于挂钟时间的算法【英文标题】：Testingwallclocktimebasedalgorithms【发布时间】：2013-04-2008:24:42【问题描述】：我目前正在维护一种算法，该算法使用挂钟时间来做出各种决定（例如，哪些解决方案可以快速计算，哪些解决... 查看详情

vijos1605noip2008提高组t4双栈排序bfs

...出处——博客园-zhouzhendong去博客园看该题解题目传送门-Vijos1605题意概括　　有1个1~n的排列，有2个栈，现在通过以下操作，使得出栈序列有序。　　操作a当前元素入栈<S1>　　操作b弹出S1栈顶元素　　操作c当前元素入栈<S... 查看详情

1016:[jsoi2008]最小生成树计数

1016:[JSOI2008]最小生成树计数TimeLimit:1Sec  MemoryLimit:162MBSubmit:6200  Solved:2518[Submit][Status][Discuss]Description　　现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的... 查看详情

bzoj1016:[jsoi2008]最小生成树计数

二次联通门: BZOJ1016:[JSOI2008]最小生成树计数    /*BZOJ1016:[JSOI2008]最小生成树计数对原图做一遍Kruskal最小生成树，统计不同边使用的次数每次暴力统计一下答案乘一乘就好了*/#include<cstdio>#include<iostream>#in... 查看详情

bzoj1016:[jsoi2008]最小生成树计数

http://www.lydsy.com/JudgeOnline/problem.php?id=1016题意： 思路：一个无向图所有的最小生成树中某种权值的边的数目均相同。引用一篇大牛的证明：我们证明以下定理：一个无向图所有的最小生成树中某种权值的边的数目均相同。开... 查看详情

bzoj1016jsoi2008最小生成树计数

1016:[JSOI2008]最小生成树计数TimeLimit: 1Sec  MemoryLimit: 162MBSubmit: 6643  Solved: 2711[Submit][Status][Discuss]Description　　现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个 查看详情

bzoj1016[jsoi2008]最小生成树计数

[JSOI2008]最小生成树计数Description现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不... 查看详情

bzoj1016：[jsoi2008]最小生成树计数

思路：模拟kruskal的过程，可以发现对于所有权值相同的边，有很多种选择的方案，而且权值不同的边并不会相互影响，因为先考虑权值较小的边，权值比当前权值大的边显然不在考虑范围之内，而权值比当前权值小的边所组成... 查看详情

bzoj-1016:[jsoi2008]最小生成树计数(kruscal+搜索)

1016:[JSOI2008]最小生成树计数TimeLimit: 1Sec  MemoryLimit: 162MBSubmit: 6429  Solved: 2611[Submit][Status][Discuss]Description　　现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个 查看详情

bzoj1016[jsoi2008]最小生成树计数

Description　　现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同... 查看详情

bzoj1016[jsoi2008]最小生成树计数

Description　　现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同... 查看详情

bzoj1016[jsoi2008]最小生成树计数

问一个图最小生成树的个数，n<100,m<1000，规定相同权值的边不超过10条。每天午觉起来很长一段时间都仿佛活在梦中。上午看的下午来打，狂RE不止，发现一种边只有一条的情况没有r会GG。。//Twenty#include<cstdio>#include<cs... 查看详情

bzoj1016[jsoi2008]最小生成树计数

Description现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最... 查看详情

bzoj1016:[jsoi2008]最小生成树计数(kruskal+dfs)

1016:[JSOI2008]最小生成树计数题目：传送门 题解：　　神题神题%%%　　据说最小生成树有两个神奇的定理：　　1、权值相等的边在不同方案数中边数相等　　　 就是说如果一种方案中权值为1的边有n条　　 　 那么... 查看详情

bzoj1016:[jsoi2008]最小生成树计数

sort改成qsort就A了？？？玄学操作。。其实觉得好像这题是暴力。。但是波老师好像做了半早上。。首先肯定是先把最小生成树求出来，然后弄个结构体，表示l~r这些边值相等，v表示用了多少这样的值的边，然后爆搜可能的情况... 查看详情

vijos1426背包+hash

背景北京奥运会开幕了，这是中国人的骄傲和自豪，中国健儿在运动场上已经创造了一个又一个辉煌，superpig也不例外………………描述虽然兴奋剂是奥运会及其他重要比赛的禁药，是禁止服用的。但是运... 查看详情

bzoj1016jsoi2008最小生成树计数生成树+dfs

题意：求最小生成树的方案数，保证每个边权出现的次数小于十次。题解：首先我们需要知道：一张图对于一个确定的边权，在任意最小生成树中出现的次数是相同的（请不要问我为什么QAQ）。所以我们先求出每一种边权在MST中... 查看详情