链接：http://codeforces.com/contest/1032/
是真的真的真的忍不住想吐槽这题意是真的真的真的读不懂……
A - Kitchen Utensils - [简单数学题]
题意：
国王开宴会，总共有编号为 $1 \sim 100$ 种餐具用来组成一套餐具。组成一套餐具的要求是，每种餐具最多出现一只。
现在给 $k$ 个宾客每个人若干套餐具，给的每套餐具都是一模一样的；同时，每个人收到的餐具套数也都是相同的。
现在知道宴会开完后，还剩下 $n$ 个餐具，以及这 $n$ 个餐具分别属于哪个编号的种类，求最少被偷走了多少只餐具。
题解：
只要某种餐具在剩下的餐具中出现了，说明每套餐具内必然包含该种餐具一只，因此可以算出每套餐具包含多少只餐具。
同时，剩余餐具里肯定有某个种类的餐具数目最多，可以通过这个数目判断每个人给了几套餐具。
AC代码：
#include<bits/stdc++.h>
using namespace std;
int n,k,a[];
int vis[];
int main()
{
scanf("%d%d",&n,&k);
int cnt=,mx=;
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
if(!vis[a[i]]) cnt++;
++vis[a[i]], mx=max(vis[a[i]],mx);
}
mx=mx/k+(mx%k!=);
printf("%d\n",mx*k*cnt-n);
}
B - Personalized Cup - [莫名其妙的题]
题意：
有一个 $a \times b$ 的网格，每个格子可以填入"*"（代表无意义的空格）或者一个大小写字母。现在给你一个字符串，要求你将该字符串按从左到右、从上到下的顺序填入网格。
必须满足 $a \le 5, b \le 20$，且任意相邻两行之间的 "*" 的数目差不能超过 $1$。要求你尽量使得 $a$ 小，求 $a,b$ 以及填网格的方案。
题解：
反正就行数尽量少，算一下就好了，除得尽就不用填星号了，除不尽就若干行填一个星号就行。说实话我是没看出来这道题有啥意义……
AC代码：
#include<bits/stdc++.h>
using namespace std;
int a,b;
string s;
void print(int a,int b,int p)
{
for(int i=;i<=a;i++)
{
for(int j=;j<=b;j++) printf("%c",s[p++]);
printf("\n");
}
}
int main()
{
cin>>s;
if(s.size()%==)
{
a=s.size()/, b=;
printf("%d %d\n",a,b);
print(a,b,);
}
else
{
a=s.size()/+;
if(s.size()%a==)
{
b=s.size()/a;
printf("%d %d\n",a,b);
print(a,b,);
}
else
{
b=s.size()/a+;
printf("%d %d\n",a,b);
int cnt=, flag=;
for(int i=;i<=a;i++)
{
if(flag== && (s.size()-cnt)%(b-)==) b--, flag=;
for(int j=;j<=b;j++) printf("%c",s[cnt++]);
if(flag) printf("*");
printf("\n");
}
}
}
}
C - Playing Piano - [特判+DFS]
题意：
给你一个数字序列 $a$，让你按照规则构造数字序列 $b(1 \le b_i \le 5)$，要求：
若 $a_i < a_{i+1}$，则 $b_i < b_{i+1}$；
若 $a_i > a_{i+1}$，则 $b_i > b_{i+1}$；
若 $a_i = a_{i+1}$，则 $b_i \neq b_{i+1}$。
题解：
显然连续上升或下降大于等于五次就不行（即 $1,2,3,4,5,6$ 或者 $6,5,4,3,2,1$），然后如果是四次上升一次平行再四次下降也是不行的（即 $1,2,3,4,5,5,4,3,2,1$）。
其余情况都是可行的，用一点贪心的思想直接暴力搜索，能很快找到答案。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+;
int n,a[maxn],b[maxn];
bool ok;
void dfs(int d)
{
if(ok) return;
if(d>n)
{
ok=;
return;
}
int st=,ed=,cant=;
if(a[d-]<a[d]) st=b[d-]+;
if(a[d-]>a[d]) ed=b[d-]-;
if(a[d-]==a[d]) cant=b[d-];
if(a[d]<=a[d+])
{
for(int i=st;i<=ed;i++)
{
if(i==cant) continue;
b[d]=i;
dfs(d+);
if(ok) return;
}
}
else
{
for(int i=ed;i>=st;i--)
{
if(i==cant) continue;
b[d]=i;
dfs(d+);
if(ok) return;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
ok=;
for(int l=,r=l+;r<=n;l++,r++)
{
bool flag=;
for(int i=l;i<r;i++) if(a[i]>=a[i+]) flag=;
if(flag) ok=;
}
for(int l=,r=l+;r<=n;l++,r++)
{
bool flag=;
for(int i=l;i<r;i++) if(a[i]<=a[i+]) flag=;
if(flag) ok=;
}
for(int l=,r=l+;r<=n;l++,r++)
{
bool flag=;
for(int i=l;i<l+;i++) if(a[i]>=a[i+]) flag=;
if(a[l+]!=a[r-]) flag=;
for(int i=r-;i<r;i++) if(a[i+]>=a[i]) flag=;
if(flag) ok=;
}
if(!ok)
{
printf("-1\n");
return ;
} ok=;
a[]=b[]=;
dfs();
for(int i=;i<=n;i++) printf("%d ",b[i]);
}
D - Barcelonian Distance - [分类讨论]
题意：
给出一个在二维平面直角坐标系第一象限内的，单位长度为 $1$ 的无限大网格，每条直线都代表道路。又给你一条直线 $ax+by+c=0$，也代表一条道路。
现在给你两个格点坐标 $(x_1,y_1)$ 和 $(x_2,y_2)$，让你求该两点间最短的道路距离。
题解：
一个矩形，它的四条边无限延长，跟另外一条直线，会产生两个（直线水平或竖直）或者四个交点（直线倾斜），计算出这个些点，然后算出所有可能的走法的长度即可。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef pair<double,double> pff;
const double eps=1e-;
double a,b,c;
pff p1,p2;
pff q1,q2,q3,q4;
double ans,ans1,ans2,ans3,ans4;
inline double dist(const pff& a,const pff& b) {
return sqrt(pow(a.first-b.first,)+pow(a.second-b.second,));
}
inline double min(double a,double b,double c,double d,double e)
{
double res=a;
res=min(res,b);
res=min(res,c);
res=min(res,d);
res=min(res,e);
return res;
}
int main()
{
ans=ans1=ans2=ans3=ans4=1e12;
cin>>a>>b>>c>>p1.first>>p1.second>>p2.first>>p2.second;
ans=fabs(p1.first-p2.first)+fabs(p1.second-p2.second);
if(fabs(a)<eps)
{
q1=make_pair(p1.first,-c/b);
q2=make_pair(p2.first,-c/b);
ans1=dist(p1,q1)+dist(q1,q2)+dist(q2,p2);
}
else if(fabs(b)<eps)
{
q1=make_pair(-c/a,p1.second);
q2=make_pair(-c/a,p2.second);
ans2=fabs(p1.first-q1.first)+dist(q1,q2)+fabs(p2.first-q2.first);
}
else
{
q1=make_pair(p1.first,-(a*p1.first+c)/b);
q3=make_pair(-(b*p1.second+c)/a,p1.second);
q2=make_pair(p2.first,-(a*p2.first+c)/b);
q4=make_pair(-(b*p2.second+c)/a,p2.second);
ans1=dist(p1,q1)+dist(q1,q2)+dist(q2,p2);
ans2=dist(p1,q1)+dist(q1,q4)+dist(q4,p2);
ans3=dist(p1,q3)+dist(q3,q2)+dist(q2,p2);
ans4=dist(p1,q3)+dist(q3,q4)+dist(q4,p2);
}
printf("%.10f\n",min(ans,ans1,ans2,ans3,ans4));
}
E - The Unbearable Lightness of Weights - []
题意：