被打爆了。唉。自己蒟蒻啊。
随手写几句。
A 暴力竟然可过，worst-case难道不是O(N^2)？
B splay，yy半天并查集无果
C 区间DP？柯神orz，1Y
D 扫描线，回头写，我觉得可以做
E 矩形交转化成了DP，我弱爆了，想了半天扫描线＋线段树
F 神题吧？看得懂题，木有想法
G yy了半天费用流神马的，竟然是贪心，蒟蒻啊。
H 题都没看
I 最短路，建图真恶心
J orz claire_大神
K 神马？
A题
这题数据真奇葩，正着做TLE，倒着做109msAC。数据不够随机啊，我擦嘞。
n个物品m种资源，给出对应关系，每种物品已有每种资源多少，每种物品分别还需要每种资源多少，每种资源现有多少。且如果某种物品满足需求，则它所占用的资源全部释放给你。就问有没有方法满足所有需求。
就是暴力，最坏O(N^2)的暴力。
每次循环对于所有能够满足的物品进行标记，标记之后把资源释放；不断循环，直到全标记，或出现一次循环中没有办法标记的情况则break
判定是否全标记再输出就好。
我擦。虽然最多标记N次，但是最坏可是O(N^2)的循环啊，说明它这数据不够随机，只卡了正着做，没卡倒着做。。不过如果随机了，没准就均摊可过，然后正做倒做都卡不住了。
这要是真去现场赛，遇到这种题不就坑死爹了嘛。
附代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 50005
int n,m;
int a[4][maxn],b[4][maxn];
int res[4];
bool vis[maxn];
int main()
{
while(scanf("%d %d",&n,&m) == 2)
{
fill(vis,vis + n,0);
for(int i = 0;i < m;i++)
for(int j = 0;j < n;j++)
scanf("%d",&a[i][j]);
for(int i = 0;i < m;i++)
for(int j = 0;j < n;j++)
scanf("%d",&b[i][j]);
for(int i = 0;i < m;i++)
scanf("%d",&res[i]);
int cnt = n;
bool mark = false;
while(1)
{
for(int i = n-1;i >= 0;i--)
if(!vis[i])
{
bool fuck = true;
for(int j = 0;j < m;j++)
{
if(res[j] < b[j][i])
{
fuck = false;
break;
}
}
if(fuck)
{
for(int j = 0;j < m;j++)
res[j] += a[j][i];
cnt--;
vis[i] = true;
mark = true;
}
}
if(!mark || cnt == 0)
break;
mark = false;
}
printf("%s\n",cnt==0?"Yes":"No");
}
}
E题
我是蒟蒻啊。这题那么简单的DP竟然没看出来。
给你N个矩形，让你求其中任意N－1个矩形的交的面积的最大值。
X个矩形交可以O(X)求出，因为两个矩形的交还是矩形。
于是乎正着求一遍，可以得到正序任意个矩形的交；反序亦然。
然后再O(N)扫一遍,ans = max(ans, intersection(inorder(i-1),reorder(i+1)).square()) 求出每个拆掉之后的其他矩形的交的面积的最大值。
WA点两处，只有一个矩形输出0，因为初始化正序第一和逆序第一均为无穷大矩形，容易2掉；求面积时记得判矩形非法。
中间sb了，想半天扫描线和线段树，我能再2点么！！！
附代码：
#include <iostream>
#include <cstdio>
using namespace std;
#define maxn 100005
const int inf = 15000;
struct rec
{
int d,l,u,r;
rec(){}
rec(int _d,int _l,int _u,int _r):d(_d),l(_l),u(_u),r(_r){}
int sq()
{
return (u >= d && r >= l)?(u - d) * (r - l):0;
}
}in[maxn],re[maxn],a[maxn];
rec inter(rec a,rec b)
{
return rec(max(a.d,b.d),max(a.l,b.l),min(a.u,b.u),min(a.r,b.r));
}
void gao()
{
int n;
scanf("%d",&n);
for(int i = 1;i <= n;i++)
scanf("%d %d %d %d",&a[i].d,&a[i].l,&a[i].u,&a[i].r);
if(n == 1)
{
puts("0");
return ;
}
re[n+1] = in[0] = rec(-inf,-inf,inf,inf);
for(int i = 1;i <= n;i++)
in[i] = inter(in[i-1],a[i]);
for(int i = n;i >= 1;i--)
re[i] = inter(re[i+1],a[i]);
int ans = 0;
for(int i = 1;i <= n;i++)
ans = max(ans,inter(in[i-1],re[i+1]).sq());
printf("%d\n",ans);
}
int main()
{
int t;
scanf("%d",&t);
for(int i = 0;i < t;i++)
gao();
}
I题
给你个地图（带比例尺的那种），可缩放，有四个分区。
给一对起止坐标，是放大八次之后的地图上的坐标。
给N个点，是实际坐标，标号为字符串。
给m条公交路线，每条路线最多k个点。
给出两个约束：如果起止点距离<=2000m，则可以直接走过去；如果公交车站离起止点的距离<=1000m，则该车站为起止点可达。
可以在任意公交车站换乘公交路线。
问从起点到终点的最小换乘次数；走过去就是走过去；去不了就打的。
繁琐的建图：
首先是起止点的还原，放大的地图还原回去，每次都是x、y除2，并且要加上对应选区的偏移量，最后再乘上比例尺。
然后是公交车站的读入，map映射字符串，记录离起止点距离。
公交路线的读入，把公交路线抽象成图中实际的点，若路线中有站起止点可达，则和起止点连边；公交路线之间若有交叠部分，则连边。
dijkstra即可，最后结果－1即为答案。复杂度O(nlogn+m^2*k^2+m^2)=O(m^2*k^2)。。。。恶心题。。。尤其是地图放大那块，想半天想不清楚，手跑样例又真心无力。
附代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#define maxn 105
#include <string>
#define MAX 5005
using namespace std;
bool mac[maxn][maxn];
int d[maxn];
const double eps = 1e-8;
const int inf = 10000;
int sgn(double x)
{
return fabs(x) < eps?0:x < -eps?-1:1;
}
struct point
{
double x,y;
point(){}
point(double a,double b):x(a),y(b){}
point operator -(const point p)
{
return point(x - p.x,y - p.y);
}
double norm()
{
return sqrt(x * x + y * y);
}
}p[MAX];
char opt[20];
int n,m;
int rel[maxn][maxn];
double fuck[2][MAX];
bool vis[maxn];
void dij()
{
d[0] = 0;
memset(vis,0,sizeof(vis));
for(int i = 0;i <= m+1;i++)
{
int mmm = inf,mark = 0;
for(int j = 0;j <= m+1;j++)
{
if(!vis[j] && mmm > d[j])
{
mark = j;
mmm = d[j];
}
}
vis[mark] = true;
for(int j = 0;j <= m + 1;j++)
if(!vis[j] && mac[mark][j] && d[j] > d[mark] + 1)
d[j] = d[mark] + 1;
}
}
void gao()
{
double a,b;
map<string,int> M;
for(int k = 0;k < 2;k++)
{
scanf(" %s %lf %lf",opt,&a,&b);
for(int i = 7;i >= 0;i--)
{
a /= 2.0;
b /= 2.0;
if(opt[i] == '1')
b += 10;
else if(opt[i] == '2')
a += 10;
else if(opt[i] == '3')
{
a += 10;
b += 10;
}
}
a *= 512.0;
b *= 512.0;
p[k] = point(a,b);
}
memset(mac,0,sizeof(mac));
scanf("%d",&n);
n++;
for(int i = 2;i <= n;i++)
{
double a,b;
scanf(" %s %lf %lf",opt,&a,&b);
M[string(opt)] = i;
p[i] = point(a,b);
fuck[0][i] = (p[0] - p[i]).norm();
fuck[1][i] = (p[1] - p[i]).norm();
}
scanf("%d",&m);
if(sgn((p[0] - p[1]).norm() - 2000.0) <= 0)
mac[0][m+1] = true;
for(int i = 1;i <= m;i++)
{
scanf("%d",&rel[i][0]);
for(int j = 1;j <= rel[i][0];j++)
{
scanf(" %s",opt);
rel[i][j] = M[string(opt)];
if(sgn(fuck[0][rel[i][j]] - 1000.0) <= 0)
mac[0][i] = mac[i][0] = 1;
if(sgn(fuck[1][rel[i][j]] - 1000.0) <= 0)
mac[m+1][i] = mac[i][m+1] = 1;
}
}
if(mac[0][m+1])
puts("walk there");
else
{
for(int i = 1;i <= m;i++)
{
for(int j = i + 1;j <= m;j++)
{
bool mark = false;
for(int k = 1;k <= rel[i][0];k++)
{
for(int q = 1;q <= rel[j][0];q++)
{
if(rel[i][k] == rel[j][q])
{
mac[i][j] = mac[j][i] = 1;
mark = true;
break;
}
}
if(mark)
break;
}
}
}
fill(d,d + m + 2,inf);
dij();
if(d[m+1] == inf)
puts("take a taxi");
else
printf("%d\n",d[m+1]-1);
}
}
int main()
{
int t;
scanf("%d",&t);
for(int i = 0;i < t;i++)
gao();
}
其他题解题报告待更新。
Enter
backward paragraph