09题
这题竟然卡STL，真是sb。不解释。
用map+string映射人名和点，对于每个查询的点bfs，并且记录每个点在bfs中被访问的次数，只要搜索完离当前查询点距离为2的点就break。然后遍历所有人的距离，找出其中恰等于2的点被访问的最多次数，把这些访问次数相同且最多的点都放到一个数组里面，排序再输出就好。
卡就卡在，输出和排序用string就TLE了；然后还没给出总人数，竟然和N不同，RE了一次。唉，反正我觉得卡STL属于有病，哪怕string很慢。
03题
水二分，二分边长就好，判定内角和是否等于2*pi以及判定是否每边都能组成三角形。
但是被精度卡到死。亏着claire大神的二分过了，我的二分给我们队贡献了将近一场比赛的罚时。
数据有误的可能性有待查证。
其他题的solution什么的就不放了，因为不想做了；卡人题比坑题恶心多了。题目的想法有坑属于出题人有水平，数据卡其他做法的精度就属于2B了。不解释。
总罚时一天，伤不起。弱爆了。
附代码吧：09题
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
#include <map>
#include <algorithm>
#include <queue>
#define maxm 4500
#define maxn 2550
#define inf 20000
struct edge
{
int p,next;
edge(){}
edge(int a,int b):p(a),next(b){}
}e[maxm];
int st[maxn];
int d[maxn+5];
int tot,cnt;
int what[maxn];
int n;
struct stu
{
char str[20];
}name[maxn],sol[maxn];
bool operator <(stu a,stu b)
{
return strcmp(a.str,b.str) < 0;
}
void init()
{
tot = 0;
memset(st,-1,sizeof(st));
}
void add(int p,int q)
{
e[tot] = edge(q,st[p]);
st[p] = tot++;
}
void bfs(int tar)
{
fill(what,what + cnt + 1,0);
fill(d,d + cnt + 1,inf);
queue <int> Q;
Q.push(tar);
d[tar] = 0;
while(!Q.empty())
{
int now = Q.front();
Q.pop();
if(d[now] == 2)
break;
for(int k = st[now];~k;k = e[k].next)
{
what[e[k].p] ++;
if(d[e[k].p] > d[now] + 1)
{
d[e[k].p] = d[now] + 1;
Q.push(e[k].p);
}
}
}
}
void gao()
{
string a,b,opt;
int q;
map <string,int> M;
cnt = 1;
scanf("%d %d",&n,&q);
init();
for(int i = 0;i < n;i++)
{
cin >> a >> b;
if(M[a] == 0)
{
M[a] = cnt++;
strcpy(name[cnt-1].str,a.c_str());
}
if(M[b] == 0)
{
M[b] = cnt++;
strcpy(name[cnt-1].str,b.c_str());
}
int u = M[a],v = M[b];
add(u,v);
add(v,u);
}
for(int i = 0;i < q;i++)
{
cin >> opt;
int want = M[opt];
bfs(want);
bool mark = false;
int mmm = 0;
for(int j = 1;j < cnt;j++)
{
if(d[j] == 2)
{
mark = true;
mmm = max(what[j],mmm);
}
}
if(!mark)
puts("-");
else
{
int solution = 0;
for(int j = 1;j < cnt;j++)
if(d[j] == 2 && mmm == what[j])
strcpy(sol[solution++].str,name[j].str);
sort(sol,sol + solution);
for(int j = 0;j < solution;j++)
{
printf("%s%c",sol[j].str,(j==solution-1?'\n':' '));
}
}
}
}
int main()
{
int t;
scanf("%d",&t);
for(int i = 1;i <= t;i++)
{
printf("Case %d:\n",i);
gao();
}
}
Backspace
03题：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
double ans,a[105];
const double pi=acos(-1.0);
const double eps=1e-10;
int comp(double x)
{
if(fabs(x) < eps)
return 0;
else if(x < -eps)
return -1;
else
return 1;
}
int f(double x)
{
double res=0,a1,a2;
for (int i=1; i<=n; i++)
{
a1=a[i];
if (i<n) a2=a[i+1]; else a2=a[1];
if (comp(x - a1 - a2) >= 0) return 1;
if (comp(x - fabs(a1-a2)) <= 0) return -1;
res+=acos((a1*a1+a2*a2-x*x)/(2*a1*a2));
}
if (fabs(res-pi*2)<1e-8) return 0;
if (comp(res - pi*2) > 0) return 1; else return -1;
}
double bs(double l,double r)
{
double mid;
for (int k=1; k<=200; k++)
{
mid=(l+r)/2;
int t=f(mid);
if (t==0) return mid;
if (t>0) r=mid; else l=mid;
}
return -1;
}
int main()
{
int o,i,cas=0;
double r;
scanf("%d",&o);
while (o--)
{
scanf("%d",&n);
r=0;
for (i=1; i<=n; i++)
{
scanf("%lf",&a[i]);
if (a[i]>r) r=a[i];
}
ans=bs(0,r*2);
if (ans<0) printf("Case %d: impossible\n",++cas);
else printf("Case %d: %.3lf\n",++cas,ans);
}
}