题目整体不难，很多都可以暴力直接做，但是除去比赛时做出来的五道题之外剩下的代码量都比较高，写的比较艰难。
A：Babs' Box Boutique
题意是问怎么塞盒子可以塞的数量最多（只考虑底边符合，三边可以旋转）
因为n<=10，所以果断排序后DFS暴搜，简单过
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
struct node
{
int a;
int b;
int c;
} s[1005];
int n;
int ans;
int used[1005];
void DFS(int ax,int ay,int k,int t)
{
if(t>ans)
{
ans=t;
}
for(int i=0; i<n; i++)
{
if(used[i]==0)
{
if(s[i].a>=ax&&s[i].b>=ay)
{
used[i]=1;
DFS(s[i].a,s[i].b,k+1,t+1);
used[i]=0;
}
else if(s[i].a>=ax&&s[i].c>=ay)
{
used[i]=1;
DFS(s[i].a,s[i].c,k+1,t+1);
used[i]=0;
}
else if(s[i].b>=ax&&s[i].c>=ay)
{
used[i]=1;
DFS(s[i].b,s[i].c,k+1,t+1);
used[i]=0;
}
}
}
}
int main()
{
int counter = 0;
while(scanf("%d",&n)!=EOF)
{
counter++;
if(n==0) break;
memset(used,0,sizeof(used));
int aa,bb,cc;
int t[4];
for(int i=0; i<n; i++)
{
for(int j=0; j<3; j++)
{
scanf("%d",&t[j]);
}
sort(t,t+3);
s[i].a=t[0];
s[i].b=t[1];
s[i].c=t[2];
}
ans=0;
DFS(0,0,0,0);
printf("Case %d: %d\n",counter,ans);
}
return 0;
}
B：Flash Mob
求离给出所有点的曼哈顿距离最近的点，因为是曼哈顿距离所以X，Y可以分开计算，并且最近的点必然在已有点中间，进一步能退出肯定是中间的点
这样子题目就很好写了。
我写的是狂搜，效率不是很高，回头改一下
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
int n;
int x[1005],y[1005];
int sumx,sumy,weix,weiy,xx,xy;
bool cmp(int a,int b)
{
return a < b;
}
int main()
{
int counter = 0;
while(scanf("%d",&n) != EOF)
{
counter++;
if(n == 0) break;
for(int i=0;i<n;i++)
{
scanf("%d%d",&x[i],&y[i]);
}
sort(x,x+n,cmp);
sort(y,y+n,cmp);
sumx = 0;
sumy = 0;
weix = x[0];
weiy = y[0];
for(int i=0;i<n;i++)
{
sumx += abs(x[i] - weix);
sumy += abs(y[i] - weiy);
}
xx = sumx;
xy = sumy;
//cout<<x[0]<<' '<<y[0]<<endl;
//cout<<sumx<<' '<<sumy<<endl;
for(int i=1;i<n;i++)
{
xx = xx + (i) * (x[i] - x[i-1]) - (n - i) * (x[i] - x[i-1]);
xy = xy + (i) * (y[i] - y[i-1]) - (n - i) * (y[i] - y[i-1]);
//cout<<x[i]<<' '<<y[i]<<endl;
//cout<<xx<<' '<<xy<<endl;
if(xx < sumx)
{
sumx = xx;
weix = x[i];
}
if(xy < sumy)
{
sumy = xy;
weiy = y[i];
}
}
printf("Case %d: (%d,%d) %d\n",counter,weix,weiy,sumx+sumy);
}
}
C：Hexagon Perplexagon
给出七个正六边形，要求能凑出左边哪个造型（相邻边上的数字相同）
因为给出限定最上面哪个和中间的那个相邻的必须是1，所以计算量直接压缩到7！
在加上相邻边之间有规律（与中间相邻的数其前面一个数必然属于后一个六边形，后一个必然属于前一个六边形
所以if一下很快就出来了
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
int s[20][20],f[20][20];
int k[20],l[20];
bool used[20];
bool usedans;
void dfs(int x)
{
for(int i=0; i<7;i++)
{
if(used[i] == false)
{
k[x]=i;
if(x==0)
{
l[0]=f[k[0]][1];
}
else
{
int t=s[k[0]][l[0]+x-1];
l[x]=f[k[x]][t];
if(x>1&&s[k[x-1]][l[x-1]+5]!=s[k[x]][l[x]+1])
{
continue;
}
if(x==6&&s[k[x]][l[x]+5]==s[k[1]][l[1]+1])
{
usedans=true;
}
}
used[i]=true;
if(x<6)
{
dfs(x+1);
}
used[i]=false;
if(usedans == true)
{
return ;
}
}
}
}
int main()
{
int T,counter = 0;
scanf("%d",&T);
while(T--)
{
counter++;
for(int i=0; i<7;i++)
{
for(int j=0; j<6;j++)
{
scanf("%d",&s[i][j]);
s[i][j+6]=s[i][j];
f[i][s[i][j]]=j;
}
}
usedans=false;
memset(used,false,sizeof(used));
dfs(0);
printf("Case %d:",counter);
if(usedans)
{
for(int i=0; i<=6;i++)
{
printf(" %d",k[i]);
}
printf("\n");
}
else
{
printf(" No solution\n");
}
}
return 0;
}
D：I've Got Your Back(gammon)
题目告诉我们不超过15504
那么就按照不超过15504打表
很快就过了
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
int s[10][16000];
void get()
{
s[1][0] = s[2][0] = s[3][0] = s[4][0] = s[5][0] = 0;
s[6][0] = 15;
for(int i = 1; i < 15504; i++)
{
for(int j=1; j<=5; j++)
{
s[j][i] = s[j][i-1];
}
if(s[6][i-1] != 0)
{
s[6][i] = s[6][i-1] - 1;
s[5][i] = s[5][i-1] + 1;
}
else
{
int t = 5;
while(s[t][i-1] == 0)
{
t--;
}
s[t][i] = 0;
s[t-1][i] = s[t-1][i-1] + 1;
s[6][i] = s[t][i-1] - 1;
}
}
}
int main()
{
get();
char c;
int q[10];
int a,counter = 0;
while(scanf("%c",&c) != EOF)
{
if(c == 'e') break;
counter++;
printf("Case %d: ",counter);
if(c == 'm')
{
for(int i=1; i<=6; i++)
{
scanf("%d",&q[i]);
}
int w;
for(int i=0;i<15504;i++)
{
w = 0;
for(int j=1;j<=6;j++)
{
if(s[j][i] != q[j])
{
w = 1;
break;
}
}
if(w == 0)
{
printf("%d\n",i);
break;
}
}
}
if(c == 'u')
{
scanf("%d",&a);
printf("%d",s[1][a]);
for(int i=2;i<=6;i++)
{
printf(" %d",s[i][a]);
}
printf("\n");
}
getchar();
}
}
E：Parencedence!
题目略麻烦
求两个人对一个已经有的式子加括号，A使式子变大B使式子变小，问谁胜
因为只有+-*三个符号，所以问题不是很大，单纯DFS计算就行了，就是代码量略长，含符号的数据记录问题略多，写的很伤心
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
#define INF 1000000007
int rval[11], n;
char ss[12][5];
int rop[11];
typedef pair<int, int> P;
int getval(int x, int y, char c)
{
if(c == '+')
{
return x + y;
}
if(c == '*')
{
return x * y;
}
return x - y;
}
P get(int val[], int op[], int deep, int flag)
{
P ans;
if(deep == 0)
{
ans.first = val[0];
ans.second = -1;
return ans;
}
if(flag)
{
ans.first = -INF;
}
else
{
ans.first = INF;
}
for(int i = 0; i < deep; i++)
{
int x = getval(val[i], val[i + 1], ss[op[i]][0]);
int cnt = 0;
int tmpop[11], tmpval[11];
for(int j = 0; j <= deep; j++)
{
if(j == i)
{
continue;
}
if(j == i + 1)
{
tmpval[cnt++] = x;
}
else
{
tmpval[cnt++] = val[j];
}
}
cnt = 0;
for(int j = 0; j < deep; j++)
{
if(j == i)
{
continue;
}
else
{
tmpop[cnt++] = op[j];
}
}
P tmp = get(tmpval, tmpop, deep - 1, !flag);
if(flag)
{
if(tmp.first > ans.first)
{
ans.first = tmp.first;
ans.second = i;
}
}
else
{
if(tmp.first < ans.first)
{
ans.first = tmp.first;
ans.second = i;
}
}
}
return ans;
}
int main()
{
int T, counter = 0;
scanf("%d", &T);
while(T--)
{
counter++;
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d%s", &rval[i], ss[i]);
for(int i = 0; i < n; i++) rop[i] = i;
scanf("%d", &rval[n]);
P ansx = get(rval, rop, n, 1);
P ansy = get(rval, rop, n, 0);
printf("Case %d:\n", counter);
printf("Player 1 (%d%s%d) leads to %d\n", rval[ansx.second], ss[ansx.second], rval[ansx.second + 1], ansx.first);
printf("Player 2 (%d%s%d) leads to %d\n", rval[ansy.second], ss[ansy.second], rval[ansy.second + 1], ansy.first);
if(ansx.first > -ansy.first)
{
printf("Player 1 wins\n");
}
else if(ansx.first < -ansy.first)
{
printf("Player 2 wins\n");
}
else
{
printf("Tie\n");
}
}
return 0;
}
G：Show Me the Money
当时看到这题目的时候第一反应是这竟然是星际1的加钱秘籍！（想太多了）
这题是要求一个最相近汇率，换个想法也就是求最短路，既然是最短路果断floyd上，注意一下数据全是整数就行了
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <map>
using namespace std;
map<string,int>q;
string ss[11];
long long a[33][33];
int ans,m;
string p1,p2,p;
void f()
{
int i,j,k,id,num,l;
long long sum=-1,in,aa,bb;
char h[22];
for(i=1; i<=ans; ++i)
{
for(j=1; j<=ans; ++j)
{
if(i!=j)
{
for(k=1; k<=ans; ++k)
{
if(i!=k&&j!=k)
{
if(a[j][i]==0||a[i][j]==0)
{
continue;
}
if(a[j][k]!=0)
{
continue;
}
a[j][k]=a[j][i]*a[i][k];
a[k][j]=a[k][i]*a[i][j];
}
}
}
}
}
id=q[p];
for(i=1; i<=ans; ++i)
{
if(i!=id&&a[i][id]!=0)
{
in=(long long)m*a[i][id]/a[id][i];
if(in*a[id][i]<(long long)m*a[i][id])
{
in++;
}
if(in<=100000)
{
if(sum==-1||in*a[id][i]*bb<sum*aa*a[i][id])
{
sum=in;
num=i;
aa=a[id][i];
bb=a[i][id];
}
}
}
}
l=ss[num].size();
for(i=0; i<l; ++i)
{
h[i]=ss[num][i];
}
h[l]=0;
printf("%lld %s\n",sum,h);
}
int main()
{
int t,i,cas=0,x,y;
char s[11],s1[11],s2[11];
while(scanf("%d",&t))
{
if(t==0)
{
break;
}
cas++;
q.clear();
ans=0;
memset(a,0,sizeof(a));
while(t--)
{
scanf("%d%s%s%d%s",&x,s1,s,&y,s2);
p1.assign(s1);
p2.assign(s2);
if(q[p1]==0)
{
q[p1]=++ans;
}
ss[q[p1]]=p1;
if(q[p2]==0)
{
q[p2]=++ans;
}
ss[q[p2]]=p2;
a[q[p1]][q[p2]]=x;
a[q[p2]][q[p1]]=y;
}
scanf("%d%s",&m,s);
printf("Case %d: ",cas);
p.assign(s);
f();
}
return 0;
}