模拟
T1 4682 粒子运动
因为题目数据不大，所以直接枚举两个点，看看哪两个点是距离最近的两个点。然后用一个结构体来存储点的坐标，然后里面的运算就和平面向量的计算是一样的。
这里要注意的是这里的所有基本都是 \(double\) ，不要忘记了把结构体里面重载运算符的地方改成 \(double\) 。
首先开始的时候我们先将所有点都平移一下，使圆心与原点重合。然后我们存粒子的时候，还预处理一下这个点距离下一次碰壁是什么时候，还有这个点移动完这一整个割线需要多久的时间。然后这个就用平面向量的数学知识来计算就可以了。然后这里还有一点叉乘没有学，没太看懂，找个时间问问小 \(S\) 好了。
然后我们就枚举是哪两个点距离最近，在枚举的时候，我们再遍历每一次碰撞，因为每一次碰撞之间的运动状态都是相对固定的，所以可以直接计算。
那个式子我找个时间看看打不打，我先贴一贴。
每一次碰撞结束的时候，我们都看一看这一段之中这两个点的最近距离是多少然后更新一下答案，碰撞那里还用了一下二倍角公式和平面向量来求 \(sin\) 和 \(cos\) 的值。
每一次碰撞结束后都改变一下这个点距离他的下次碰撞还要多久，因为这个角度是固定的，其实他就是走过对应的割线所需的时间，也就是前面存的那个值。然后还改变一下当前点的 \(cnt\) 值，就可以了。
我愿称之为我在oi学数学
还要注意的一点就是不要习惯性就用快读输入了, \(double\) 不能用快读!!
// 坐标的结构体
struct point{
double x,y;
point operator + (const point &t) const {
// 加
return {x + t.x,y + t.y};
}
point operator - () const {
// 变成负的
return {-x,-y};
}
point operator - (const point &t) const {
// 减
return *this + - t;
}
point operator * (const double &t) const {
// 数乘
return {x * t,y * t};
}
point operator / (const double &t) const {
// 数除
return {x / t,y / t};
}
double operator * (const point &t) const {
// 点乘
return x * t.x + y * t.y;
}
double operator % (const point &t) const {
// 叉乘
return x * t.y - y * t.x;
}
double lenf() { // 长度的平方
return (*this) * (*this);
}
double len() { // 长度
return sqrt((*this) * (*this));
}
void xuan(double cosa,double sina) { // 旋转a度
(*this) = {x * cosa - y * sina,x * sina + y * cosa};
}
point dwxl() {
return (*this) / (*this).len();
}
void read() {
scanf("%lf%lf",&x,&y);
}
};
struct node{
point st; // start
point v; // velocity
double t,T; // 碰撞所需的时间，走过割线所需时间
int cnt; // 碰撞次数
}w[N];
int n,k;
point ori;
double R;
double ans = dinf;
void fww(point a) {
cout << a.x << ' ' << a.y << endl;
}
void init(node &t) {
t.st = t.st - ori; // 平移到原点
double v = t.v.len(); // 速率
double d = fabs(t.st % t.v) / v;
double len = sqrtl(R * R - d * d);
t.T = 2 * len / v;
t.t = (len + t.v.dwxl() * (-t.st)) / v;
}
void peng(node &t) { // 碰撞
double len = t.st.len() * t.v.len();
double bansin = t.st * t.v / len;
double bancos = (t.st % t.v) / len;
// 二倍角公式
double sin = 2 * bansin * bancos;
double cos = bancos * bancos - bansin * bansin;
t.v.xuan(cos,sin);
}
void update(point ua,point ub,point va,point vb) {
if ((ua - ub) * (vb - va) > 0 && (ua + va - ub - vb) * (va - vb) > 0)
// 特判不相交
ans = min(ans,fabs((ua - ub) % (vb - va)) / (vb - va).len());
ans = min(ans,min((ua - ub).len(),(ua - ub + va - vb).len()));
}
void get(node a,node b) {
double t; // 距离下次碰还有多久时间
point dis1,dis2;
while (a.cnt < k && b.cnt < k) {
t = min(a.t,b.t);
dis1 = a.v * t;
dis2 = b.v * t;
a.t -= t,b.t -= t;
update(a.st,b.st,dis1,dis2);
a.st = a.st + dis1,b.st = b.st + dis2;
if (a.t < zero) peng(a),a.t = a.T,++ a.cnt;
if (b.t < zero) peng(b),b.t = b.T,++ b.cnt;
}
}
int main(){
ori.read(),cin >> R;
n = fr(),k = fr();
for (int i = 1; i <= n; i ++) {
w[i].st.read();
w[i].v.read();
init(w[i]);
}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j < i; j ++) {
get(w[i],w[j]);
}
}
printf("%.3lf",ans);
return 0;
}
练习
评价是 \(C\) 题是个烂题！
A.华容道
这一题卡常卡的人要死了,还找了郭总和潇潇帮我卡常,后来把 \(dis\) 数组改掉了,然后把 \(piiii\) 改成了结构体之后过了。
然后整体思路还是直接 \(bfs\) 爆搜，然后这个队列里面要存五个数（如果存四个数的话就会洛谷上面 \(TLE\) ，但是信友队上面可以过），五个数前面两个就是空白点的坐标，第三个和第四个就是目标点的坐标，第五个点就是用了多少步，如果这个单独存一个的话会 \(TLE\)，有可能是因为一开始初始化的时候这个数组有一点打，或者什么别的。
然后就是比较常规的 \(bfs\) ，要注意的就是更新目标点的判断。
然后这里的手写循环队列是错误的！这题能过是因为这个队列是没有循环的，如果循环了的话那里要写 \(\ne\)
struct node{
int a,b,c,d,e;
};
int n,m,Q;
bool w[N][N];
int bex,bey,enx,eny,kbx,kby;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
bool flag[N][N][N][N];
vector<int> e[N * N];
node q[10000005];
int main(){
n = fr(),m = fr(),Q = fr();
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
w[i][j] = fr();
}
}
while (Q --) {
memset(flag,0,sizeof flag);
kbx = fr(),kby = fr();
bex = fr(),bey = fr();
enx = fr(),eny = fr();
if (bex == enx && bey == eny) {
fw(0);
ch;
continue;
}
int hh = 0,tt = 0;
q[0] = {kbx,kby,bex,bey,0};
int dist;
bool st = false;
while (hh <= tt) {
node t = q[hh ++];
if (hh == 10000000) hh = 0;
dist = t.e;
for (int i = 0; i < 4; i ++) {
int x = t.a + dx[i];
int y = t.b + dy[i];
if (!w[x][y]) continue;
if (x > n || y > m || !x || !y) continue;
int ux = t.c,uy = t.d;
if (x == t.c && y == t.d) {
ux = t.a,uy = t.b;
}
if (flag[x][y][ux][uy]) continue;
flag[x][y][ux][uy] = true;
if (ux == enx && uy == eny) {
fw(dist + 1);
ch;
st = true;
break;
}
if (tt == 10000000) tt = 0;
q[++ tt] = {x,y,ux,uy,dist + 1};
}
if (st) break;
}
if(!st) wj;
}
return 0;
}
B.围栏问题
这一题就是单纯的爆搜，这个爆搜的理论复杂度本来感觉应该是 \(16!\) 的，但是这里是可以过的，爆搜的复杂度就是玄学。然后这里优化的话就用了最优性优化，好像就没有什么别的优化了。
下面那一大堆是我一开始没想到怎么爆搜的时候写的部分分代码，有点点长，但是可以拿 \(30\) 分部分分。
然后爆搜的时候不 \(sort\) 也是可以过掉的，但是我是先写的 \(sort\) 再写的爆搜，所以就懒得删了。
int m,k,n;
pii w[N];
int dfn[N];
int maxx[N],may[N],mix[N],miy[N];
int ans;
bool cmp(pii a,pii b) {
return a.se < b.se;
}
int get(int i) {
return (maxx[i] - mix[i] + 1) * 2 + (may[i] - miy[i] + 1) *2;
}
void dfs(int u,int cnt,int sum) {
if (sum > ans) return ;
if (u > n) {
ans = min(ans,sum);
return ;
}
if (cnt > k) return ;
int a,b,c,d;
for (int i = 1; i <= cnt; i ++) {
a = maxx[i],b = mix[i],c = may[i],d = miy[i];
maxx[i] = max(maxx[i],w[u].fi);
may[i] = max(may[i],w[u].se);
miy[i] = min(miy[i],w[u].se);
mix[i] = min(mix[i],w[u].fi);
dfs(u + 1,cnt,sum - (a - b + 1) * 2 - (c - d + 1) * 2 + get(i));
maxx[i] = a,mix[i] = b,may[i] = c,miy[i] = d;
}
if (cnt == k) return ;
maxx[cnt + 1] = w[u].fi,mix[cnt + 1] = w[u].fi;
may[cnt + 1] = w[u].se,miy[cnt + 1] = w[u].se;
dfs(u + 1,cnt + 1,sum + 4);
maxx[cnt + 1] = 0,mix[cnt + 1] = 0;
may[cnt + 1] = 0,miy[cnt + 1] = 0;
}
int main(){
m = fr(), k = fr(),n = fr();
for (int i = 1; i <= n; i ++) {
w[i].fi = fr();
w[i].se = fr();
}
int maxx = 0,minx = m;
int maxy = 0,miny = m;
for (int i = 1; i <= n; i ++) {
maxx = max(maxx,w[i].fi);
maxy = max(maxy,w[i].se);
minx = min(minx,w[i].fi);
miny = min(miny,w[i].se);
}
if (k == 1) {
fw((maxx - minx + 1) * 2 + (maxy - miny + 1) * 2);
return 0;
}
sort(w + 1,w + 1 + n);
if (k == 2) {
int ans = inf;
for (int i = 1; i <= n; i ++) {
int t = 0;
int maxx = 0,minx = m;
int maxy = 0,miny = m;
for (int l = 1; l <= i; l ++) {
maxx = max(maxx,w[l].fi);
maxy = max(maxy,w[l].se);
minx = min(minx,w[l].fi);
miny = min(miny,w[l].se);
}
t += (maxx - minx + 1) * 2 + (maxy - miny + 1) *2;
maxx = 0,minx = m;
maxy = 0,miny = m;
for (int r = i + 1; r <= n; r ++) {
maxx = max(maxx,w[r].fi);
maxy = max(maxy,w[r].se);
minx = min(minx,w[r].fi);
miny = min(miny,w[r].se);
}
if (i != n)
t += (maxx - minx + 1) * 2 + (maxy - miny + 1) *2;
ans = min(ans,t);
}
sort(w + 1,w + 1 + n,cmp);
for (int i = 1; i <= n; i ++) {
int t = 0;
int maxx = 0,minx = m;
int maxy = 0,miny = m;
for (int l = 1; l <= i; l ++) {
maxx = max(maxx,w[l].fi);
maxy = max(maxy,w[l].se);
minx = min(minx,w[l].fi);
miny = min(miny,w[l].se);
}
t += (maxx - minx + 1) * 2 + (maxy - miny + 1) *2;
maxx = 0,minx = m;
maxy = 0,miny = m;
for (int r = i + 1; r <= n; r ++) {
maxx = max(maxx,w[r].fi);
maxy = max(maxy,w[r].se);
minx = min(minx,w[r].fi);
miny = min(miny,w[r].se);
}
if (i != n)
t += (maxx - minx + 1) * 2 + (maxy - miny + 1) *2;
ans = min(ans,t);
}
fw(ans);
return 0;
}
ans = inf;
dfs(1,0,0);
fw(ans);
return 0;
}
C.立体图
这题是个烂题！！！不想多说，这题洛谷上面是黄色，但是我觉得这明明就是黑色！！模拟一生之敌！！
回来后去洛谷讨论区捞了一个代码借鉴借鉴。
int n,m;
int h[N][N];
char wdwx[10][10] = {
";;+---+",
";/ /|",
"+---+ |",
"| | +",
"| |/",
"+---+",
};
char ans[5005][5005];
pii cfx[6005]; // 长方形坐标
void get(int i) {
pii t = cfx[i];
n = max(n,cfx[i].fi + 5);
m = max(m,cfx[i].se + 6);
for (int i = 0; i < 10; i ++) {
for (int j = 0; j < 10; j ++) {
if (wdwx[i][j] == '+' || wdwx[i][j] == '|' ||
wdwx[i][j] == '/' || wdwx[i][j] == ' ' ||
wdwx[i][j] == '-')
ans[t.fi + i][t.se + j] = wdwx[i][j];
}
}
}
int main(){
n = fr(),m = fr();
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
h[i][j] = fr();
}
}
memset(ans,'.',sizeof ans);
int idx = 0;
int yidong = 0;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
for (int k = 1; k <= h[i][j]; k ++) {
cfx[++ idx].se = (j - 1) * 4 + (n - i) * 2 + 1;
cfx[idx].fi = 1 + (i - 1) * 2 - (k - 1) * 3;
yidong = max(yidong ,1 - cfx[idx].fi);
}
}
}
for (int i = 1; i <= idx; i ++) {
cfx[i].fi += yidong;
get(i);
}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
cout << ans[i][j];
}
cout << endl;
}
return 0;
}