@KirinBill
2017-10-05T20:35:27.000000Z
字数 4859
阅读 1204
题解
套题
目录
#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 <algorithm>
using std::max;
using std::sort;
const int MAXN=100005;
int n;
int hi[MAXN];
bool cmp(int a,int b){return a>b;}
inline long long cal(){
sort(hi+1,hi+n+1,cmp);
int h=hi[1],w=1;
long long ret=h;
for(int i=2;i<=n;++i){
h=hi[i];
++w;
ret=max(ret,(long long)h*w);
}
return ret;
}
int main(){
setIO("rectangle");
int T;
read(T);
while(T--){
read(n);
for(int i=1;i<=n;++i)
read(hi[i]);
write(cal(),'\n');
}
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 <cstring>
#include <climits>
#include <algorithm>
using std::min;
const int MAXN=1005;
int n;
int ans[MAXN];
inline int lim(int x){return min(2,x);}
inline bool jud(){
//f[i]=前i个人的方案数
static int f[MAXN];
memset(f,0,sizeof(f));
f[0]=1;
for(int i=1;i<=n;++i){
for(int j=i,belong_cnt=0;j;--j){
if(ans[j]){
if(belong_cnt && belong_cnt!=ans[j])
break;
else belong_cnt=ans[j];
}
if(!belong_cnt || i-j+1==belong_cnt)
f[i]=lim(f[i]+f[j-1]);
}
}
return f[n]==1;
}
int main(){
setIO("group");
int T;
read(T);
while(T--){
read(n);
for(int i=1;i<=n;++i)
read(ans[i]);
if(jud()) puts("1");
else puts("0");
}
return 0;
}
long long
里;
#include <cstdio>
#include <queue>
#include <set>
using std::queue;
using std::set;
const int MAXN=7,MAXTP=9,n=5,m=4;
int type[MAXTP];
struct Graph{
static const int mod=7;
int c[MAXN][MAXN];
int* operator[] (int i){return c[i];}
long long hash(){
long long ret=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)
ret=ret<<3|type[c[i][j]];
}
return ret;
}
long long zip(){
long long ret=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)
ret=ret<<3|c[i][j];
}
return ret;
}
void unzip(long long a){
for(int i=n;i;--i){
for(int j=m;j;--j){
c[i][j]=a&mod;
a>>=3;
}
}
}
}G;
inline bool win(Graph &G){
return G[5][2]==2 && G[5][3]==2;
}
inline int BFS(){
static int dirx[]={0,1,0,-1},diry[]={1,0,-1,0};
static int judx[5][4]={{},{0,0,0,0},{1,1,0,0},{1,1,0,0},{0,0,0,0}};
static int judy[5][4]={{},{0,0,0,0},{1,0,1,0},{0,0,0,0},{1,0,1,0}};
static queue<int> step;
static queue<long long> que;
static set<long long> se;
if(win(G)) return 0;
se.clear();
while(que.size()) que.pop(),step.pop();
se.insert(G.hash());
que.push(G.zip()),step.push(0);
bool can;
int now;
long long hs;
while(que.size()){
G.unzip(que.front());
que.pop();
now=step.front();
step.pop();
for(int i=1;i<=n;++i){
for(int j=1,id,col;j<=m;++j){
col=G[i][j],id=type[G[i][j]];
if(id==0) continue;
can=true;
for(int k=0;k<4;++k)
can&=(G[i+judx[id][k]][j+judy[id][k]]==G[i][j]);
if(!can) continue;
for(int k=0;k<4;++k)
G[i+judx[id][k]][j+judy[id][k]]=0;
for(int k=0,x,y;k<4;++k){
x=i+dirx[k],y=j+diry[k];
can=true;
for(int l=0;l<4;++l)
can&=(G[x+judx[id][l]][y+judy[id][l]]==0);
if(!can) continue;
for(int l=0;l<4;++l)
G[x+judx[id][l]][y+judy[id][l]]=col;
if(win(G)) return now+1;
hs=G.hash();
if(!se.count(hs)){
que.push(G.zip());
se.insert(hs);
step.push(now+1);
}
for(int l=0;l<4;++l)
G[x+judx[id][l]][y+judy[id][l]]=0;
}
for(int k=0;k<4;++k)
G[i+judx[id][k]][j+judy[id][k]]=col;
}
}
}
return -1;
}
inline void prepare(){
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(G[i][j]>=3){
if(G[i-1][j]==G[i][j] || G[i+1][j]==G[i][j])
type[G[i][j]]=3;
else if(G[i][j-1]==G[i][j] || G[i][j+1]==G[i][j])
type[G[i][j]]=4;
}
else type[G[i][j]]=G[i][j];
}
}
}
int main(){
freopen("huarong.in","r",stdin);
freopen("huarong.out","w",stdout);
for(int i=0,lim=n+1,tmp=m+1;i<=lim;++i)
G[i][0]=G[i][tmp]=-1;
for(int i=0,lim=m+1,tmp=n+1;i<=lim;++i)
G[0][i]=G[tmp][i]=-1;
int T;
scanf("%d",&T);
while(T--){
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)
scanf("%d",&G[i][j]);
}
prepare();
printf("%d\n",BFS());
}
return 0;
}