@KirinBill
2017-10-05T14:15:14.000000Z
字数 5641
阅读 1379
题解
套题
目录
#include <cstdio>
#include <cctype>
#include <string>
#include <ctime>
using namespace std;
inline void setIO(string file){
string in=file+".in",out=file+".out";
freopen(in.c_str(),"r",stdin);
freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
int pm=1; char c;
do{
c=getchar();
if(c=='-') pm=-1;
}while(!isdigit(c));
x=c^'0';
while(c=getchar(),isdigit(c))
x=x*10+(c^'0');
x*=pm;
}
template<typename type>
void write(type x,char c=0){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10|'0');
if(c) putchar(c);
}
#include <algorithm>
#include <iostream>
#include <cmath>
using std::sort;
using std::unique;
using std::cin;
using std::istream;
using std::cout;
using std::ostream;
using std::abs;
int cur;
long long a[5],b[5],c[5],d[5][2];
struct frac{
int up,dwn;
friend istream& operator>> (istream &in,frac &a){
read(a.up),read(a.dwn);
return in;
}
}hm,hs,ms;
struct clk{
int h,m,s;
friend bool operator< (const clk &a,const clk &b){
if(a.h!=b.h) return a.h<b.h;
else if(a.m!=b.m) return a.m<b.m;
else return a.s<b.s;
}
friend bool operator== (const clk &a,const clk &b){
return a.h==b.h && a.m==b.m && a.s==b.s;
}
friend ostream& operator<< (ostream &out,clk &a){
if(a.h<10) putchar('0');
write(a.h,':');
if(a.m<10) putchar('0');
write(a.m,':');
if(a.s<10) putchar('0');
write(a.s,'\n');
return out;
}
}ans[50005];
inline bool jud(int x,int y,int z){
long long tmp;
for(int i=1;i<=3;++i){
tmp=abs(a[i]*x+b[i]*y+c[i]*z);
if(tmp==d[i][0]) continue;
if(tmp!=d[i][1]) return false;
}
return true;
}
//ax+by+cz=d
inline void solve(){
for(int x=0;x<=11;++x){
for(int y=0;y<=59;++y){
for(int z=0;z<=59;++z){
if(jud(x,y,z)) ans[++cur]=(clk){x,y,z};
}
}
}
}
int main(){
setIO("clock");
int T;
read(T);
while(T--){
cur=0;
cin>>hm>>hs>>ms;
//h->m
a[1]=(long long)3600*hm.dwn;
b[1]=(long long)-660*hm.dwn;
c[1]=(long long)-11*hm.dwn;
d[1][0]=abs((long long)120*hm.up);
d[1][1]=abs((long long)360*120*hm.dwn-d[1][0]);
//h->s
a[2]=(long long)3600*hs.dwn;
b[2]=(long long)60*hs.dwn;
c[2]=(long long)-719*hs.dwn;
d[2][0]=abs((long long)120*hs.up);
d[2][1]=abs((long long)360*120*hs.dwn-d[2][0]);
//s->m
a[3]=0;
b[3]=(long long)60*ms.dwn;
c[3]=(long long)-59*ms.dwn;
d[3][0]=abs((long long)10*ms.up);
d[3][1]=abs((long long)360*10*ms.dwn-d[3][0]);
solve();
sort(ans+1,ans+cur+1);
cur=unique(ans+1,ans+cur+1)-ans-1;
write(cur,'\n');
for(int i=1;i<=cur;++i)
cout<<ans[i];
}
return 0;
}
#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
string in=file+".in",out=file+".out";
freopen(in.c_str(),"r",stdin);
freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
int pm=1; char c;
do{
c=getchar();
if(c=='-') pm=-1;
}while(!isdigit(c));
x=c^'0';
while(c=getchar(),isdigit(c))
x=x*10+(c^'0');
x*=pm;
}
template<typename type>
void write(type x,char c=0){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10|'0');
if(c) putchar(c);
}
#include <queue>
#include <cstring>
using std::queue;
const int MAXN=50005,MAXM=200005;
int n,m,cnt,k,tot;
int he[MAXN],dis[MAXN],rk[MAXN];
bool use[MAXN];
struct line{int to,nex;}ed[MAXM<<1];
inline void addE(int u,int v){
ed[++cnt]=(line){v,he[u]};
he[u]=cnt;
}
inline int BFS(){
static queue<int> que;
while(que.size()) que.pop();
memset(dis,-1,sizeof(dis));
dis[1]=0;
que.push(1);
int u;
while(que.size()){
u=que.front();
que.pop();
for(int i=he[u],v;i;i=ed[i].nex){
v=ed[i].to;
if(rk[v]>rk[u] && dis[v]==-1 && use[v]){
dis[v]=dis[u]+1;
if(v==n) return dis[v];
que.push(v);
}
}
}
}
int main(){
setIO("seqpath");
int T;
read(T);
int u;
while(T--){
cnt=tot=0;
memset(use,false,sizeof(use));
memset(he,0,sizeof(he));
memset(ed,0,sizeof(ed));
read(n),read(m),read(k);
read(u),use[u]=true,rk[u]=++tot;
for(int i=1,v;i<=k;++i){
read(v),use[v]=true,rk[v]=++tot;
addE(u,v),addE(v,u);
u=v;
}
for(int i=1,lim=m-k,v;i<=lim;++i){
read(u),read(v);
addE(u,v),addE(v,u);
}
write(BFS(),'\n');
}
return 0;
}
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <climits>
using std::sort;
using std::min;
using std::abs;
using std::next_permutation;
const int MAXN=7;
int n,mx,my;
int dirx[]={1,0,-1,0},diry[]={0,1,0,-1},sx[MAXN],sy[MAXN],tx[MAXN],ty[MAXN],canx[MAXN<<2],cany[MAXN<<2];
long long ans;
bool vis[MAXN<<1][MAXN<<1];
inline int lim(int x){
static int dta=MAXN;
return x+dta;
}
inline void cal_mid(){
static int tmpx[MAXN],tmpy[MAXN];
memcpy(tmpx,sx,sizeof(tmpx));
memcpy(tmpy,sy,sizeof(tmpy));
sort(tmpx+1,tmpx+n+1);
sort(tmpy+1,tmpy+n+1);
mx=(tmpx[(n>>1)+1]+tmpx[n+1>>1])>>1;
my=(tmpy[(n>>1)+1]+tmpy[n+1>>1])>>1;
}
inline long long cal(){
static int pmt[MAXN];
long long ret=LLONG_MAX;
for(int i=1;i<=n;++i)
pmt[i]=i;
long long dis;
do{
dis=0;
for(int i=1;i<=n;++i)
dis+=(long long)abs(sx[pmt[i]]-tx[i])+abs(sy[pmt[i]]-ty[i]);
ret=min(ret,dis);
}while(next_permutation(pmt+1,pmt+n+1));
return ret;
}
void DFS(int now,int l,int r){
if(now>n){
ans=min(ans,cal());
return;
}
for(int i=l,nr;i<=r;++i){
tx[now]=canx[i],ty[now]=cany[i];
nr=r;
for(int j=0,x,y;j<4;++j){
x=canx[i]+dirx[j],y=cany[i]+diry[j];
if(!vis[lim(x)][lim(y)]){
++nr,canx[nr]=x,cany[nr]=y;
vis[lim(x)][lim(y)]=true;
}
}
DFS(now+1,i+1,nr);
for(int j=r+1;j<=nr;++j)
vis[lim(canx[j])][lim(cany[j])]=false;
}
}
inline void solve(){
cal_mid();
for(int i=1;i<=n;++i)
sx[i]-=mx,sy[i]-=my;
memset(vis,false,sizeof(vis));
vis[lim(0)][lim(0)]=true;
ans=LLONG_MAX;
for(int i=0,x,y;i<4;++i){
x=dirx[i],y=diry[i];
canx[i+1]=x,cany[i+1]=y;
vis[lim(x)][lim(y)]=true;
}
DFS(2,1,4);
}
int main(){
freopen("meet.in","r",stdin);
freopen("meet.out","w",stdout);
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d%d",&sx[i],&sy[i]);
solve();
printf("%lld\n",ans);
}
return 0;
}