2023冲刺清北营11
T1 一瓶消毒液
由于数据范围是 \(200\) 而不是 \(1000\) ，因此可以直接 \(O(n^3)\) 暴力枚举判断，假设当前枚举 \(i,j,k\) ，考虑判断移动 \(k\) 线段是否能使 \(i,j\) 联通，此时我们的问题变成了求解两条线段的最短距离。
首先判断线段相交的情况，容易发现这等价于选择一条线段为分割线，判断另一个线段的两个端点位于该线段所在直线的两侧，可以简单使用向量叉积进行判断，由于是线段相交，因此每条线段都要判一次。
此时考虑求解线段距离，考虑通过几种情况简单取 \(\min\) 得到答案：首先线段端点进行组合构成线段，其次线段端点向另一条线段做垂线构成线段。考虑判断一个点关于一条线段的垂线是否在线段上，由于不在线段上时线段与点构成钝角三角形，因此可以使用向量点积进行判断。之后通过三角形的面积可以求解点到线段的距离。
然而此题严重卡精，因此使用 __int128_t 进行运算，此时距离公式无法进行开根，因此计算点到直线的距离的公式为 \(\tfrac{S^2}{dis}\) ，然而 \(S^2\) 会使得 __int128_t 溢出，因此上述计算使用龟速乘解决，与求解 \(A\times B\operatorname{mod} P\) 写法类似。
code
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <bitset>
using namespace std;
const int max1 = 242;
const __int128_t inf = 1e38;
int T, n;
struct Point
{
long long x, y;
Point () {}
Point ( long long __x, long long __y )
{ x = __x, y = __y; }
__int128_t operator * ( const Point &A ) const
{ return (__int128_t) x * A.y - (__int128_t) y * A.x; }
__int128_t operator & ( const Point &A ) const
{ return (__int128_t) x * A.x + (__int128_t) y * A.y; }
};
__int128_t Get_Dis ( const Point &A, const Point &B )
{
return (__int128_t) ( A.x - B.x ) * ( A.x - B.x ) + (__int128_t) ( A.y - B.y ) * ( A.y - B.y );
}
struct Line
{
Point A, B; __int128_t dis;
Line () {}
Line ( Point __A, Point __B, __int128_t __dis )
{ A = __A, B = __B, dis = __dis; }
bool operator < ( const Line &A ) const
{ return dis < A.dis; }
bool operator < ( const __int128_t &A )
{ return dis < A; }
};
Line L[max1 + 5];
__int128_t Across ( const Point &A, const Point &B, const Point &C )
{
return Point(B.x - A.x, B.y - A.y) * Point(C.x - A.x, C.y - A.y);
}
__int128_t Cross ( const Point &A, const Point &B, const Point &C )
{
return Point(B.x - A.x, B.y - A.y) & Point(C.x - A.x, C.y - A.y);
}
__int128_t Quick_Mul ( __int128_t A, __int128_t B, __int128_t mod )
{
__int128_t k1 = A / mod, k2 = 0, val = 0; A %= mod;
while ( B )
{
if ( B & 1 )
{
k2 += k1;
val += A;
k2 += val / mod;
val %= mod;
}
B >>= 1;
k1 = k1 + k1 + ( A + A ) / mod;
A = ( A + A ) % mod;
}
if ( val )
++k2;
return k2;
}
__int128_t Get_Dis ( const Line &P, const Point &Q )
{
__int128_t S = Across(Q, P.A, P.B);
if ( S < 0 )
S = -S;
return Quick_Mul(S, S, Get_Dis(P.A, P.B));
}
__int128_t Get_Dis ( const Line &P, const Line &Q )
{
int p1 = Across(P.A, P.B, Q.A) >= 0 ? 1 : -1, p2 = Across(P.A, P.B, Q.B) >= 0 ? 1 : -1;
int q1 = Across(Q.A, Q.B, P.A) >= 0 ? 1 : -1, q2 = Across(Q.A, Q.B, P.B) >= 0 ? 1 : -1;
if ( p1 * p2 < 0 && q1 * q2 < 0 )
return 0;
__int128_t ans = inf;
if ( Cross(P.A, P.B, Q.A) > 0 && Cross(P.B, P.A, Q.A) > 0 )
ans = min(ans, Get_Dis(P, Q.A));
if ( Cross(P.A, P.B, Q.B) > 0 && Cross(P.B, P.A, Q.B) > 0 )
ans = min(ans, Get_Dis(P, Q.B));
if ( Cross(Q.A, Q.B, P.A) > 0 && Cross(Q.B, Q.A, P.A) > 0 )
ans = min(ans, Get_Dis(Q, P.A));
if ( Cross(Q.A, Q.B, P.B) > 0 && Cross(Q.B, Q.A, P.B) > 0 )
ans = min(ans, Get_Dis(Q, P.B));
ans = min(ans, Get_Dis(P.A, Q.A));
ans = min(ans, Get_Dis(P.A, Q.B));
ans = min(ans, Get_Dis(P.B, Q.A));
ans = min(ans, Get_Dis(P.B, Q.B));
return ans;
}
bitset <max1 + 5> bit[max1 + 5][max1 + 5];
void Work ()
{
scanf("%d", &n);
for ( int i = 1; i <= n; i ++ )
{
scanf("%lld%lld%lld%lld", &L[i].A.x, &L[i].A.y, &L[i].B.x, &L[i].B.y);
L[i].dis = Get_Dis(L[i].A, L[i].B);
}
sort(L + 1, L + 1 + n);
for ( int i = 1; i <= n; i ++ )
for ( int j = i + 1; j <= n; j ++ )
bit[i][j].reset();
for ( int i = 1; i <= n; i ++ )
{
for ( int j = i + 1; j <= n; j ++ )
{
__int128_t dis = Get_Dis(L[i], L[j]);
int pos = lower_bound(L + 1, L + 1 + n, dis) - L;
for ( int k = pos; k <= n; k ++ )
{
if ( i == k || j == k )
continue;
if ( k < i )
bit[k][i][j] = 1;
else if ( k < j )
bit[i][k][j] = 1;
else
bit[i][j][k] = 1;
}
}
}
int ans = 0;
for ( int i = 1; i <= n; i ++ )
for ( int j = i + 1; j <= n; j ++ )
ans += bit[i][j].count();
printf("%d\n", ans);
return;
}
int main ()
{
freopen("dis.in", "r", stdin);
freopen("dis.out", "w", stdout);
scanf("%d", &T);
while ( T -- )
Work();
return 0;
}
T2 一张桌子
简单推一下式子：
\[\begin{aligned}
f(x,y,z)-f(z,y,x)
&=a_xb_y+a_yb_z+a_zb_x-a_zb_y-a_yb_x-a_xb_z\\
&=a_x(b_y-b_z)+b_x(a_z-a_y)+a_yb_z-a_zb_y\\
&=a_x(b_y-b_z)+b_x(a_z-a_y)-a_y(b_y-b_z)-b_y(a_z-a_y)\\
&=(a_x-a_y)(b_y-b_z)-(b_x-b_y)(a_y-a_z)
\end{aligned}
\]
发现这是一个叉积的形式，等价于线段 \(XY\) 到线段 \(YZ\) 的过程为向左弯曲，因此直接对整张图每一层求解凸包，然后简单合并即可。
code
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int max1 = 3000;
const int inf = 0x3f3f3f3f;
struct Point
{
int x, y;
vector <int> id;
Point () {}
Point ( int __x, int __y )
{ x = __x, y = __y; }
long long operator * ( const Point &A ) const
{ return 1LL * x * A.y - 1LL * A.x * y; }
bool operator < ( const Point &A ) const
{
if ( x == A.x )
return y < A.y;
return x < A.x;
}
bool operator != ( const Point &A ) const
{ return x != A.x || y != A.y; }
};
int n, len, p[max1 + 5], s[max1 + 5], top;
bool vis[max1 + 5]; Point A[max1 + 5], B[max1 + 5];
long long Across ( const Point &A, const Point &B, const Point &C )
{ return Point(B.x - A.x, B.y - A.y) * Point(C.x - A.x, C.y - A.y); }
int main ()
{
freopen("table.in", "r", stdin);
freopen("table.out", "w", stdout);
scanf("%d", &n);
for ( int i = 1; i <= n; i ++ )
{
scanf("%d%d", &A[i].x, &A[i].y);
A[i].id.clear();
A[i].id.push_back(i);
}
sort(A + 1, A + 1 + n);
len = 0; B[0] = Point(-inf, -inf);
for ( int i = 1; i <= n; i ++ )
{
if ( !len || B[len] != A[i] )
B[++len] = A[i];
else
B[len].id.push_back(A[i].id.back());
}
p[0] = 0; int now = 0;
for ( int T = 1; T <= len; T ++ )
{
top = 0;
s[++top] = p[now];
for ( int i = 1; i <= len; i ++ )
{
if ( vis[i] )
continue;
while ( top > 1 && Across(B[s[top]], B[i], B[s[top - 1]]) < 0 )
--top;
s[++top] = i;
}
for ( int i = 2; i <= top; i ++ )
p[++now] = s[i], vis[s[i]] = true;
top = 0;
s[++top] = p[now];
for ( int i = len; i >= 1; i -- )
{
if ( vis[i] )
continue;
while ( top > 1 && Across(B[s[top]], B[i], B[s[top - 1]]) < 0 )
--top;
s[++top] = i;
}
for ( int i = 2; i <= top; i ++ )
p[++now] = s[i], vis[s[i]] = true;
if ( now == n )
break;
}
for ( int i = 1; i <= n; i ++ )
for ( auto v : B[p[i]].id )
printf("%d ", v);
printf("\n");
return 0;
}
T3 11:23
题解说手玩即可……
然而我太废物了根本不会玩。
大家有兴趣的去玩一下吧！
简单写了一个模拟器，可以判断不合法字符，房屋选址重复，房屋相邻，剩余资源不够的情况，道路相邻的判断比较麻烦，没有写。
code
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int max1 = 10, max2 = 1e4;
int n, m, S[max1 + 5][max1 + 5], D[max1 + 5][max1 + 5];
int h1, h2, h3, h4, l1, l2, l3, l4, a1, a2, a3, a4;
int K, G, V[max2 + 5];
int kind[max1 + 5][max1 + 5], road[2][max1 + 5][max1 + 5];
int day, now1, now2, now3, now4;
struct Option
{
char opt; int A, B, C, D;
Option () {}
Option ( char __opt, int __A, int __B, int __C, int __D )
{ opt = __opt, A = __A, B = __B, C = __C, D = __D; }
};
vector <Option> ans;
void PrintAll ()
{
printf("\n\n\n\n\n\n\n\n\n\n");
printf("Day %d Number %d K %d\n", day, V[day], K);
printf("\n\n");
printf("Resource : %d %d %d %d\n", now1, now2, now3, now4);
printf("\n\n");
printf("house cost : %d %d %d %d\n", h1, h2, h3, h4);
printf("up cost : %d %d %d %d\n", l1, l2, l3, l4);
printf("road cost : %d %d %d %d\n", a1, a2, a3, a4);
printf("\n\n");
printf("Future : ");
for ( int i = day + 1; i <= G; i ++ )
printf("%d ", V[i]);
printf("\n");
int count = 0;
for ( int i = 0; i <= n; i ++ )
for ( int j = 0; j <= m; j ++ )
count += kind[i][j];
printf("count = %d\n", count);
printf("-------");
for ( int i = 0; i <= m + m; i ++ )
printf("-------");
printf("\n");
printf("| |");
for ( int i = 0; i <= m + m; i ++ )
{
if ( i & 1 )
printf("| |");
else
{
if ( ( i >> 1 ) / 10 )
printf("| |");
else
printf("| |");
}
}
printf("\n");
printf("| |");
for ( int i = 0; i <= m + m; i ++ )
{
if ( i & 1 )
printf("| |");
else
{
if ( ( i >> 1 ) / 10 )
printf("| %d |", i >> 1);
else
printf("| %d |", i >> 1);
}
}
printf("\n");
printf("| |");
for ( int i = 0; i <= m + m; i ++ )
{
if ( i & 1 )
printf("| |");
else
{
if ( ( i >> 1 ) / 10 )
printf("| |");
else
printf("| |");
}
}
printf("\n");
for ( int i = 0; i <= n + n; i ++ )
{
printf("-------");
for ( int k = 0; k <= m + m; k ++ )
printf("-------");
printf("\n");
printf("| |");
for ( int j = 0; j <= m + m; j ++ )
printf("| |");
printf("\n");
if ( i & 1 )
printf("| |");
else
{
if ( ( i >> 1 ) / 10 )
printf("| %d |", i >> 1);
else
printf("| %d |", i >> 1);
}
for ( int j = 0; j <= m + m; j ++ )
{
if ( i & 1 )
{
if ( j & 1 )
{
printf("|[%d,%d]|", S[i + 1 >> 1][j + 1 >> 1], D[i + 1 >> 1][j + 1 >> 1]);
}
else
{
if ( road[0][i >> 1][j >> 1] )
printf("|+++++|");
else
printf("| |");
}
}
else
{
if ( j & 1 )
{
if ( road[1][i >> 1][j >> 1] )
printf("|+++++|");
else
printf("| |");
}
else
{
if ( !kind[i >> 1][j >> 1] )
printf("| |");
else if ( kind[i >> 1][j >> 1] == 1 )
printf("| H |");
else
printf("| C |");
}
}
}
printf("\n");
printf("| |");
for ( int j = 0; j <= m + m; j ++ )
printf("| |");
printf("\n");
}
printf("-------");
for ( int i = 0; i <= m + m; i ++ )
printf("-------");
printf("\n\n\n\n");
return;
}
bool Check ( int A, int B, int C, int D )
{
return now1 >= A && now2 >= B && now3 >= C && now4 >= D;
}
int main ()
{
scanf("%d%d", &n, &m);
for ( int i = 1; i <= n; i ++ )
for ( int j = 1; j <= m; j ++ )
scanf("%d", &S[i][j]);
for ( int i = 1; i <= n; i ++ )
for ( int j = 1; j <= m; j ++ )
scanf("%d", &D[i][j]);
scanf("%d%d%d%d", &h1, &h2, &h3, &h4);
scanf("%d%d%d%d", &l1, &l2, &l3, &l4);
scanf("%d%d%d%d", &a1, &a2, &a3, &a4);
scanf("%d%d", &K, &G);
for ( int i = 1; i <= G; i ++ )
scanf("%d", &V[i]);
PrintAll();
printf("Please find a position to start.\n");
printf("\n\n\n\n");
int x, y;
scanf("%d%d", &x, &y);
kind[x][y] = 1;
ans.push_back(Option('B', x, y, 0, 0));
ans.push_back(Option('E', 0, 0, 0, 0));
now1 = now2 = now3 = now4 = 0;
for ( day = 1; day <= G; day ++ )
{
for ( int i = 1; i <= n; i ++ )
{
for ( int j = 1; j <= m; j ++ )
{
if ( D[i][j] == V[day] )
{
if ( S[i][j] == 1 )
{
now1 += kind[i - 1][j - 1];
now1 += kind[i - 1][j];
now1 += kind[i][j - 1];
now1 += kind[i][j];
}
else if ( S[i][j] == 2 )
{
now2 += kind[i - 1][j - 1];
now2 += kind[i - 1][j];
now2 += kind[i][j - 1];
now2 += kind[i][j];
}
else if ( S[i][j] == 3 )
{
now3 += kind[i - 1][j - 1];
now3 += kind[i - 1][j];
now3 += kind[i][j - 1];
now3 += kind[i][j];
}
else
{
now4 += kind[i - 1][j - 1];
now4 += kind[i - 1][j];
now4 += kind[i][j - 1];
now4 += kind[i][j];
}
}
}
}
char opt[3];
int A, B, C, D;
while ( true )
{
PrintAll();
scanf("%s", opt);
if ( opt[0] == 'E' )
{
ans.push_back(Option('E', 0, 0, 0, 0));
break;
}
else if ( opt[0] == 'B' )
{
scanf("%d%d", &A, &B);
if ( Check(h1, h2, h3, h4) )
{
if ( kind[A][B] || ( A > 1 && kind[A - 1][B] ) || ( A < n && kind[A + 1][B] ) || ( B > 1 && kind[A][B - 1] ) || ( B < m && kind[A][B + 1] ) )
printf("warning : There is a building in this place!\n");
else
{
kind[A][B] = 1;
now1 -= h1;
now2 -= h2;
now3 -= h3;
now4 -= h4;
ans.push_back(Option('B', A, B, 0, 0));
}
}
else
printf("Money is not enough.\n");
}
else if ( opt[0] == 'U' )
{
scanf("%d%d", &A, &B);
if ( Check(l1, l2, l3, l4) )
{
if ( kind[A][B] != 1 )
printf("warning : This is not a simple house!\n");
else
{
++kind[A][B];
now1 -= l1;
now2 -= l2;
now3 -= l3;
now4 -= l4;
ans.push_back(Option('U', A, B, 0, 0));
}
}
else
printf("Money is not enough.\n");
}
else if ( opt[0] == 'C' )
{
scanf("%d%d", &A, &B);
if ( Check(h1 + l1, h2 + l2, h3 + l3, h4 + l4) )
{
if ( kind[A][B] || ( A > 1 && kind[A - 1][B] ) || ( A < n && kind[A + 1][B] ) || ( B > 1 && kind[A][B - 1] ) || ( B < m && kind[A][B + 1] ))
printf("warning : There is a building in this place!\n");
else
{
kind[A][B] = 2;
now1 -= h1 + l1;
now2 -= h2 + l2;
now3 -= h3 + l3;
now4 -= h4 + l4;
ans.push_back(Option('C', A, B, 0, 0));
}
}
else
printf("Money is not enough.\n");
}
else if ( opt[0] == 'R' )
{
scanf("%d%d%d%d", &A, &B, &C, &D);
if ( Check(a1, a2, a3, a4) )
{
if ( A == C )
{
if ( B == D - 1 )
{
road[1][A][B] = 1;
now1 -= a1;
now2 -= a2;
now3 -= a3;
now4 -= a4;
ans.push_back(Option('R', A, B, C, D));
}
else if ( B == D + 1 )
{
road[1][A][D] = 1;
now1 -= a1;
now2 -= a2;
now3 -= a3;
now4 -= a4;
ans.push_back(Option('R', A, B, C, D));
}
else
printf("warning : This is an illegal option !\n");
}
else if ( B == D )
{
if ( A == C - 1 )
{
road[0][A][B] = 1;
now1 -= a1;
now2 -= a2;
now3 -= a3;
now4 -= a4;
ans.push_back(Option('R', A, B, C, D));
}
else if ( A == C + 1 )
{
road[0][C][B] = 1;
now1 -= a1;
now2 -= a2;
now3 -= a3;
now4 -= a4;
ans.push_back(Option('R', A, B, C, D));
}
else
printf("warning : This is an illegal option !\n");
}
else
printf("warning : This is an illegal option !\n");
}
else
printf("Money is not enough.\n");
}
else if ( opt[0] == 'X' )
{
scanf("%d%d", &A, &B);
bool flag = true;
if ( A == 1 && now1 < K )
flag = false;
if ( A == 2 && now2 < K )
flag = false;
if ( A == 3 && now3 < K )
flag = false;
if ( A == 4 && now4 < K )
flag = false;
if ( !flag )
printf("Money is not enough.\n");
else
{
if ( A == 1 )
now1 -= K;
if ( A == 2 )
now2 -= K;
if ( A == 3 )
now3 -= K;
if ( A == 4 )
now4 -= K;
if ( B == 1 )
++now1;
if ( B == 2 )
++now2;
if ( B == 3 )
++now3;
if ( B == 4 )
++now4;
ans.push_back(Option('X', A, B, 0, 0));
}
}
else
printf("warning : This is an illegal option !\n");
}
int count = 0;
for ( int i = 0; i <= n; i ++ )
for ( int j = 0; j <= m; j ++ )
count += kind[i][j];
if ( count >= 10 )
{
printf("You win !\n");
printf("%d\n", day);
for ( auto v : ans )
{
if ( v.opt == 'E' )
printf("%c\n", v.opt);
else if ( v.opt == 'R' )
printf("%c %d %d %d %d\n", v.opt, v.A, v.B, v.C, v.D);
else
printf("%c %d %d\n", v.opt, v.A, v.B);
}
return 0;
}
}
printf("You Fail!");
return 0;
}