-----------------------前面的两场感觉质量不高，就没写题解-----------------------------
A .Around the Track
pro：给定内多边形A和外多边形B，求最短路径，蛮子路径再A之外，B之内。
sol：如果没有B，就是求凸包，有了B，我们在做凸包的时候，有形如“a-b-c，b在内部，删去b，连接a-c的操作”，如果a-c和B不相交，直接删去b，否则用B的凸包代替b处。
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> Point;
typedef long long LL;
const int maxn=;
bool operator != (Point b, Point c)
{
return (b.x!=c.x || b.y!=c.y);
}
double dis(Point b, Point c);
struct polygon
{
int n;
bool cannotdel[maxn];
Point p[maxn]; polygon():n(){} void read()
{
scanf("%d", &n);
for (int i=; i<=n; ++i)
scanf("%d%d", &p[i].x, &p[i].y);
p[]=p[n];
p[n+]=p[];
for (int i=; i<=n; ++i) cannotdel[i]=false;
} double track()
{
double ans=;
for (int i=; i<=n; ++i)
ans+=dis(p[i], p[i+]);
return ans;
} void del(int pos)
{
for (int i=pos; i<n; ++i)
{
p[i]=p[i+];
cannotdel[i]=cannotdel[i+];
}
--n;
p[n+]=p[];
p[]=p[n];
} void insert(int posl, int posr, vector<Point> &newp)
{
int m=posl+n-posr++newp.size();
for (int i=; i<(n-posr+); ++i)
{
p[m-i]=p[n-i];
cannotdel[m-i]=cannotdel[n-i];
}
n=m; m=newp.size();
for (int i=; i<m; ++i)
{
p[posl++i]=newp[i];
cannotdel[posl++i]=true;
}
p[n+]=p[];
p[]=p[n];
} void print()
{
puts("======================");
for (int i=; i<=n+; ++i)
printf("%d %d\n", p[i].x, p[i].y);
}
};
polygon inner, outer;
Point pp[maxn];
Point globalps;
set<Point> innerpoint;
vector<Point> newp;
inline LL sqr(LL x)
{
return x*x;
}
LL det(Point b, Point c, Point o)
{
return (b.x-o.x)*(c.y-o.y)-(b.y-o.y)*(c.x-o.x);
}
double dis(Point b, Point c)
{
return sqrt(sqr(b.x-c.x)+sqr(b.y-c.y));
}
LL sdis(Point b, Point c)
{
return (sqr(b.x-c.x)+sqr(b.y-c.y));
}
bool intriangle(Point &b, Point &c, Point &d, Point &o)
{
return (abs(det(b, c, o))+abs(det(b, d, o))+abs(det(c, d, o)))==abs(det(b, c, d));
}
bool cmp(Point b, Point c)
{
LL tmp=det(b, c, globalps);
if (tmp!=) return tmp<;
return sdis(b, globalps)<sdis(c, globalps);
}
void convex(vector<Point> &p, Point &ps, Point &pf)
{
globalps=ps;
sort(p.begin(), p.end(), cmp);
int n=p.size();
for (int i=; i<=n; ++i) pp[i]=p[i-];
pp[++n]=pf;
pp[]=ps;
int m=;
for (int i=; i<=n; ++i)
{
while (m> && det(pp[i], pp[m], pp[m-])<) --m;
pp[++m]=pp[i];
}
p.resize(m-);
for (int i=; i<m; ++i) p[i-]=pp[i];
}
void solve()
{
for (int i=; i<=inner.n; ++i)
innerpoint.insert(inner.p[i]); while ()
{
bool flag=false;
for (int i=; i<=inner.n; ++i)
if (!inner.cannotdel[i] && det(inner.p[i+], inner.p[i-], inner.p[i])<)
{
newp.clear();
for (int j=; j<=outer.n; ++j)
if (intriangle(inner.p[i-], inner.p[i], inner.p[i+], outer.p[j]))
if (innerpoint.count(outer.p[j])==)
newp.push_back(outer.p[j]); for (int j=; j<=inner.n; ++j)
if (inner.p[j]!=inner.p[i-] && inner.p[j]!=inner.p[i] && inner.p[j]!=inner.p[i+]
&& intriangle(inner.p[i-], inner.p[i], inner.p[i+], inner.p[j]))
newp.push_back(inner.p[j]); if (newp.size()==) { flag=true; inner.del(i); break; }
convex(newp, inner.p[i-], inner.p[i+]); flag=true;
for (auto &p:newp)
if (innerpoint.count(p)) { flag=false; break; } if (!flag) continue;
for (auto &p:newp) innerpoint.insert(p);
inner.insert(i-, i+, newp);
}
if (!flag) break;
}
printf("%.7lf\n", inner.track());
}
int main()
{
inner.read();
outer.read();
solve();
return ;
}
B .Biking Duck
pro：给定二维平面，已知有N个位置有自行车站，以及地图边界都是自行车站，自行车可以从一个站到另一个站。在地图上走路或者骑自行车都是走直线。给定终点起点，求从从起点到终点的最小时间。
sol：路径不可能是曲曲折折的，这样性价比不高。 只有几种情况：
1：骑车可能要绕路，没必要骑车， 直接走路，起点->终点。
2：骑一次，起点走路->到站->到站->走路到终点。
而骑车要考虑边界上的车站，我们可以利用对称的知识，知道以边界为直线对称后，两点间直线最短，与对称轴的交点，是凹函数的分界线，这个可以用三分求。
...写起来应该很烦，告辞。
C .Cent Savings
pro：按顺序给定N个商品，相邻的可以分到同一组，你可以最多分成D+1组，每一组的价格四舍五入，求最小价格。N<2e3，D<20;
sol：由于的相邻的分组，就DP即可，O(N^2*D)。 单调队列优化O(N*D);
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int dp[maxn][];//dp[i][j]
int a[maxn], sum[maxn];
inline f(int x){return (x / * + (x % <= ? : ));}
int main()
{
int n, d;
cin >> n >> d;
for(int i = ; i <= n; i++)cin >> a[i], sum[i] = a[i] + sum[i - ];
for(int i = ; i <= n; i++)dp[i][] = f(sum[i]);
for(int j = ; j <= d + ; j++)
{
for(int i = j; i <= n; i++)
{
int tmp = 1e9 + ;
for(int k = j - ; k <= i - ; k++)
{
tmp = min(tmp, dp[k][j - ] + f(sum[i] - sum[k]));
}
dp[i][j] = tmp;
}
}
int ans = 1e9 + ;
for(int i = ; i <= d + && i <= n; i++)ans = min(ans, dp[n][i]);
cout<<ans<<endl;
return ;
}
D .Digi Comp II
pro：给定M个开关，每个开关有初始状态(L或者R)，每个开关有两个走向，分别指向左边对应的开关和右边对应的开关。 一个球走到当前开关，会走向当前状态指向的方向，并且使当前的状态改变。 问N个球从1号出发，最终每个开关的状态。 给定的关系是个DAG，除了0号都有两个出度，可以看成左右儿子。
sol：模拟一下，不难发现，如果X个球经过i节点，那么将会有X/2+X&1次走向初始方向，X/2次走向另外一个方向。即是topo排序一下可以搞。
这题WA的蛮多的，有两个注意；
1：不一定只要1号点入度为0，题目只保证了除0之外，出度为2；没保证入度（这一点感觉题目的确误导了很多读题人）。 所以必须开始把入度为0的都加进queue去，不然有的点跑不到。
2：左右儿子一样的情况下，如果先减左右儿子的入度，再入队，会加两次，导致错误。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int ind[maxn],ans[maxn];
int a[maxn],b[maxn],q[maxn],head,tail;
ll Now[maxn],N; char c[maxn][];
int main()
{
int M,u,v;
scanf("%lld%d",&N,&M);
rep(i,,M){
scanf("%s%d%d",c[i],&a[i],&b[i]);
ind[a[i]]++; ind[b[i]]++;
}
Now[]=N; rep(i,,M) if(!ind[i]) q[++head]=i;
while(tail<head){
u=q[++tail];
if(u==) break;
if(Now[u]%==) ans[u]=;
if(c[u][]=='L'){
Now[a[u]]+=(Now[u]-Now[u]/);
Now[b[u]]+=Now[u]/;
}
else {
Now[b[u]]+=(Now[u]-Now[u]/);
Now[a[u]]+=Now[u]/;
}
ind[a[u]]--;
if(ind[a[u]]==) q[++head]=a[u];
ind[b[u]]--;
if(ind[b[u]]==) q[++head]=b[u];
}
rep(i,,M) {
if(ans[i]) {
if(c[i][]=='L') putchar('R');
else putchar('L');
}
else {
if(c[i][]=='R') putchar('R');
else putchar('L');
}
}
return ;
}
E :Euclidean TSP
pro：虽然题目是TSP，但是和TSP没什么大关系。 就是给定飞机上升的时间和直线飞行的时间，二者和C的关系，求最小时间。
sol：飞机飞高需要时间，飞高之后飞得快，不难想到总时间随高度先增后减，三分即可。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
double n, p, s, v;
const double eps = 1e9;
const double t = sqrt(2.0);
double f(double x)
{
double tmp = n * pow(log(n) / log(2.0), t * x);
tmp = tmp /(eps * p);
tmp = tmp + s / v * (x + 1.0) / x;
return tmp;
}
int main(){
cin >> n >> p >> s >> v;
double l =, r = , ans=1e60, c;
int T = ;
while(T--)
{
double lmid = l + (r - l) / 3.0;
double rmid = r - (r - l) / 3.0;
double Lans=f(lmid),Rans=f(rmid);
if(Rans> Lans){
r=rmid;
if(ans>Lans) ans =Lans, c = lmid;
}
else{
l = lmid;
if(ans>Rans) ans =Rans, c = rmid;
}
}
printf("%.9f %.9f\n", ans, c);
return ;
}
F .Finding Lines
pro：给定N个点，P； 问是否有超过P%的点在一条直线上。
sol：随机两个点，看多少点在直线上。（上海大都会原题）
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int maxn = 1e5 + ;
struct node
{
ll x, y;
}c[maxn];
node a, b;
bool judge(node c)
{
return (b.y - a.y) * (c.x - b.x) == (b.x - a.x) * (c.y - b.y);
}
int main()
{
srand(time());
int n, p;
cin >> n >> p;
for(int i = ; i <= n; i++)cin >> c[i].x >> c[i].y;
if(n <= )
{
cout<<"possible\n";
return ;
}
int T = ;
bool flag = ;
while(T--)
{
int x = (ll)rand() * rand() % n + ;
int y = (ll)rand() * rand() % n + ;
if(x == y)continue;
a = c[x], b= c[y];
int tot = ;
for(int i = ; i <= n; i++)if(judge(c[i]))tot++;
if(1.0 * tot / n + 1e- >= 0.01 * p){flag = ;break;}
}
if(flag)cout<<"possible"<<endl;
else cout<<"impossible"<<endl;
return ;
}
G .Gathering
pro：给定二维平面上N个点，以及D。要求找一个点X，满足X到N个点的曼哈顿距离都不超过D，而总距离最小。 不存在合法的输出"impossible"
sol：因为我们知道中位数这个位置比较关键，X和Y可以分开考虑，分别是取中位数时最小，对X和Y都是凹函数。
比赛的时候大方向想对了。大概是曼哈顿距离转化切比雪夫，然后套二分或者三分。 （但是居然求公共矩形不会了。。。赛后想不就是对R和U取min，对取L和U取max吗。。。 然后我们在合法的多边形里三分套三分即可。 也可以三分之后直接找最接近中位数的Y即可。
曼哈顿转切比雪夫: 原点A(X,Y)---->逆时针旋转45度后，长度*sqrt2的点A‘(X+Y,X-Y)；
切比雪夫转曼哈顿: L<=x<=R ; D<=y<=U ； 现在：(L+D)/2<=x<=(R+U)/2，且x一定时满足，L<=x+y<=R,D<=y<=U;
三分套三分：O(N(log1e9)^2~=9e7)，会超时T37.
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
const ll inf=1e30;
ll x[maxn],y[maxn],D,ans=1e30,midy;
ll up=inf,dn=-inf,le=-inf,ri=inf; int N;
ll solvey(ll midx,ll Y)
{
ll res=;
rep(i,,N) res+=abs(midx-x[i])+abs(Y-y[i]);
return res;
}
ll solvex(ll midx)
{
ll yu=min(midx-dn,ri-midx);
ll yd=max(midx-up,le-midx);
if(yu<yd) return inf;
ll res=inf,mid;
while(yd<yu-){
ll l=yd+(yu-yd)/,ans1=solvey(midx,l);
ll r=yu-(yu-yd)/,ans2=solvey(midx,r);
if(ans1>ans2) yd=l,res=min(res,ans2);
else yu=r,res=min(res,ans1);
}
rep(i,yd,yu) res=min(res,solvey(midx,i));
return res;
}
int main()
{
scanf("%d",&N);
rep(i,,N) scanf("%lld%lld",&x[i],&y[i]);
scanf("%lld",&D);
rep(i,,N){
dn=max(dn,x[i]-y[i]-D);
up=min(up,x[i]-y[i]+D);
le=max(le,x[i]+y[i]-D);
ri=min(ri,x[i]+y[i]+D);
}
if(dn>up||le>ri) return puts("impossible"),;
sort(y+,y+N+); midy=(y[(N+)/]);
ll L=(le+dn)/,R=(up+ri)/;
while(L<R-){
ll l=L+(R-L)/,ans1=solvex(l);
ll r=R-(R-L)/,ans2=solvex(r);
if(ans1>ans2) L=l,ans=min(ans,ans2);
else R=r,ans=min(ans,ans1);
}
rep(i,L,R) ans=min(ans,solvex(i));
printf("%lld\n",ans);
return ;
}
三分+中位数逼近：没必要取三分y，直接用结论即可，取靠近y[]的中位数。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
const ll inf=1e30;
ll x[maxn],y[maxn],D,ans=1e30,midy;
ll up=inf,dn=-inf,le=-inf,ri=inf; int N;
ll solve(ll midx)
{
ll yu=min(midx-dn,ri-midx);
ll yd=max(midx-up,le-midx);
if(yu<yd) return inf;
ll Y,res=;
rep(i,,N) res+=abs(midx-x[i])+abs(Y-y[i]);
return res;
}
int main()
{
scanf("%d",&N);
rep(i,,N) scanf("%lld%lld",&x[i],&y[i]);
scanf("%lld",&D);
rep(i,,N){
dn=max(dn,x[i]-y[i]-D);
up=min(up,x[i]-y[i]+D);
le=max(le,x[i]+y[i]-D);
ri=min(ri,x[i]+y[i]+D);
}
if(dn>up||le>ri) return puts("impossible"),;
sort(y+,y+N+); midy=(y[(N+)/]);
ll L=(le+dn)/,R=(up+ri)/;
while(L<R-){
ll l=L+(R-L)/,ans1=solve(l);
ll r=R-(R-L)/,ans2=solve(r);
if(ans1>ans2) L=l,ans=min(ans,ans2);
else R=r,ans=min(ans,ans1);
}
rep(i,L,R) ans=min(ans,solve(i));
printf("%lld\n",ans);
return ;
}
H .Hyacinth
pro：看不懂。
sol：by队友
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
struct edge{
int d,nex;
}e[];
struct node{
int x,y;
bool a,b;
}a[];
int q[],efree,n,cnt;
inline void add(int x,int y){e[++efree]=(edge){y,q[x]},q[x]=efree;}
void dfs(int x,int y){
if(a[x].a==)a[x].x=++cnt;
if(a[x].b==)a[x].y=++cnt;
int v=q[x];while(e[v].d==y)v=e[v].nex;
if(!v)return;
if(a[x].a)a[e[v].d].x=a[x].y,a[e[v].d].a=a[x].b=;
else a[e[v].d].x=a[x].x,a[e[v].d].a=a[x].a=;
dfs(e[v].d,x);
for(int i=e[v].nex;i;i=e[i].nex)
if(e[i].d!=y){
if(a[x].a)a[e[i].d].x=a[x].y,a[e[i].d].a=a[x].b=;
else a[e[i].d].x=a[x].x,a[e[i].d].a=a[x].a=;
dfs(e[i].d,x);
}
}
int main(){
scanf("%d",&n);
if(n==){
puts("1 2");
puts("2 1");
return ;
}
for(int i=;i<n;i++){
int x,y;scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs(,);
for(int i=;i<=n;i++)printf("%d %d\n",a[i].x,a[i].y);
return ;
}
I. Indoorienteering
题意：找长度为L的哈密尔顿回路，N<=14;
思路：N!太大，我们可以折半枚举
J .Judging Troubles
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
map<string, int>Map1, Map2;
int main()
{
int n, ans = ;
string s;
cin >> n;
for(int i = ; i <= n; i++)cin >> s, Map1[s]++;
for(int i = ; i <= n; i++)cin >> s, Map2[s]++;
for(map<string, int>::iterator it = Map1.begin(); it != Map1.end(); it++)
ans += min(Map1[it->first], Map2[it->first]);
cout<<ans<<endl;
return ;
}
Knapsack Collection
队友写了，但是代码没给我啊。。。