写在前面：
将这两场比赛放在一起是想总结一下写巨复杂的模拟题的心得
比较好的题解博客：
《7-1 冒险者分队》
这是题目比较重要的一点，同时可以发现不管是加还是减，都是20的倍数
明显，如果原值与目的值的差值 不能整除20，则必然会失败
同时我们还可以得到：
通过两次操作 +40 -20 -20 与 +20 +20 -40
我们可以得到一种新的赋值方式：+60 +0 -60
想要得到最小次数，必须分析性质了
假设三个原值和目的值的差值 分别为 a b c
我们的操作当然是通过给 a b c 进行 +40 -20 -20 / +20 +20 -40 ....的操作
将其变成 0 0 0
同时我们可以发现，要想能成功，必然 a+b+c=0
而且有
a=b=c=0
a<=b<0<c
c<0<a<=b
这三种情况（我们假设abs（c）> abs(b) > abs(a) ）
显然
a=b=c=0的情况最小操作次数为0
a<=b<0<c 和 c<0<a<=b的情况，我们发现可以让
c<0<a<=b的情况对a b c 同时取反，变成 a<=b<0<c的情况
取反后最小操作次数是不变的
于是接下来讨论的就只有a<=b<0<c的情况了
根据我们上面的推测：无论什么时候，都有a+b+c=0
既然是最小操作次数，我们贪心地让c每次都-40，其余的+20
这个过程中b一定先会变成0
为何？
假设c==0了，还有a+b+c=0存在，必然是b>=0 && a<=0
同时因为a b c都是20的倍数，同时a+b+c=0
必然不存在当b>0时，b-=40后 b<0的情况存在
当b==0时，有c=-a
这个时候我们用 +60 +0 -60 这个操作来修正
（具体证明最优不会......）
当然因为是a b c是20的倍数，我们从一开始便可以简化
a/=20 b/=20 c/=20
操作变成+2 -1 -1 / +1 +1 -2
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
void solve()
{
int a,b,c,ta,tb,tc;
cin>>a>>b>>c>>ta>>tb>>tc;
int ca=ta-a,cb=tb-b,cc=tc-c;
if (ca+cb+cc!=0)
{
cout<<"-1"<<endl;
return ;
}
if (ca%20!=0 || cb%20!=0 || cc%20!=0)
{
cout<<"-1"<<endl;
return ;
}
ca/=20,cb/=20,cc/=20;
int cnt=(ca<0)+(cb<0)+(cc<0);
vector<int>arr;
arr.push_back(ca),arr.push_back(cb),arr.push_back(cc);
sort(arr.begin(),arr.end());
int a1,a2,a3;
if (cnt==1)
a1=-arr[2],a2=-arr[1],a3=-arr[0];
else
a1=arr[0],a2=arr[1],a3=arr[2];
int ans=abs(a2);
a3-=ans*2;
if (a3%3!=0)
{
cout<<-1<<endl;
return ;
}
ans+=(a3/3)*2;
cout<<ans<<endl;
}
int main()
{
int t;
cin>>t;
while (t--)
solve();
return 0;
}
《7-2 拼题A打卡奖励》
这道题如果普通地设
dp[i][j]：在前i个物品中选，体积不超过j的最大金币数
会超时
发现金币数范围很少，我们可以设
dp[i][j]:在前i个物品中选，得到金币数恰好为j的最小体积
然后用给的体积范围在dp[i][j]中找哪个符合
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=30*1e3+5,N=1e3+5;
int dp[M],w[N],v[N],n,m;
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
cin>>w[i];
int maxv=0;
for (int i=1;i<=n;i++)
{
cin>>v[i];
maxv+=v[i];
}
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for (int i=1;i<=n;i++)
for (int j=maxv;j>=v[i];j--)
dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
int ans;
for (int i=maxv;i>=0;i--)
if(dp[i]<=m)
{
ans=i;
break;
}
cout<<ans<<endl;
return 0;
}
《7-3 快递装箱》
复杂模拟题，具体看上面的题解博客
这道题目，在模拟流水线的时候有环
即难点在于：我如何模拟出在流水线上各个点之间是并行执行的这个过程？
因为流水线上的每一次都是从入口进入一个物品
接着推动整个流水线上开始运作
可以for 循环 流水线上的物品
for循环里面 是各个点之间的操作流程
但是上面说到这个流水线是个环，如：
点A和点B是流水线上的工作点
A和B是同时执行的，他们同时生产出gA 和 gB货物
gA是给B处理的，gB是给C处理的
因为在写程序时我们并不能真的达到并行
所以如果我执行A（）在执行 B（）
那么执行A（）时给B的gA
会在B（）中处理掉
但是因为逻辑上A（）与 B（）是同时执行的
在B执行的时候A的gA应该还没有出来才对
解决这个环的方法是：
假设这个环的工作方式是：
A B C D A B.....
我们可以将A点功能拆除两个部分 A1，A2
A1是D对A造成影响的部分，A2是A对B造成影响的部分
然后我们按照
A1 D C B A2 A1 D.....
这样的顺序进行下去，各个点之间环的影响就没了
《7-4 塔防游戏》
还是超级复杂模拟题
这个题的难处也是在并发
如何模拟僵尸同时发生动作？
我们for循环给出的时间T
在for循环里面是执行一遍全部僵尸的状态点
让全部僵尸进入到下一个状态点
这道题还有意思的地方在于：
如何在网格图上跑Dijkstra算法？
同时看到：僵尸可能从任何边界出发，但是他们的目的地都是大本营
我们从大本营为起点，开始跑Dijkstra
网格图上点多，用堆优化版Dijkstra
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <unistd.h>
using namespace std;
const int N = 105;
typedef pair<int, int> PII;
int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1};
int n, m, T, g[N][N], dist[N][N], tim[N][N];
bool st[N][N];
PII fin, path[N][N];
vector<PII> team;
int nums[4*N];
vector<PII> road[N*4];
struct Ta{
int y,x,id,pos;
};
struct info
{
int id, pos;
};
struct node
{
int di, y, x;
bool operator<(const node &t) const
{
return di > t.di;
}
};
void init()
{
cin >> n >> m >> T;
for (int i = 0; i <= n + 1; i++)
for (int j = 0; j <= m + 1; j++)
{
cin >> g[i][j];
if (g[i][j] < 0)
{
fin = {i, j};
continue;
}
if (i == 0 && j == 0)
continue;
if (i == 0 && j == m + 1)
continue;
if (i == n + 1 && j == 0)
continue;
if (i == n + 1 && j == m + 1)
continue;
if ((i < 1 || i > n || j < 1 || j > m) && g[i][j] > 0)
{
team.push_back({i, j});
nums[team.size()-1]=g[i][j];
}
}
}
void Dijkstra()
{
memset(st, false, sizeof(st));
memset(dist, 0x3f, sizeof(dist));
memset(tim, 0x3f, sizeof(dist));
priority_queue<node> pq;
pq.push({0, fin.first, fin.second});
dist[fin.first][fin.second] = 0,
tim[fin.first][fin.second] = 0;
st[fin.first][fin.second] = true;
while (pq.size())
{
node t = pq.top();
pq.pop();
bool edge1=false,edge2=false;
if (t.y<1 || t.y>n || t.x<1 || t.x>m)
edge1=true;
for (int i = 0; i < 4; i++)
{
int ny = t.y + dy[i], nx = t.x + dx[i];
if (ny < 0 || ny > n+1 || nx < 0 || nx > m+1 || st[ny][nx])
continue;
if (ny<1 || ny>n || nx<1 || nx>m)
edge2=true;
//边界不能转移到边界去
if (edge1 && edge2)
continue;
st[ny][nx] = true;
if (dist[t.y][t.x] + g[ny][nx] < dist[ny][nx])
{
dist[ny][nx] = dist[t.y][t.x] + g[ny][nx];
tim[ny][nx] = tim[t.y][t.x] + 1;
path[ny][nx] = {t.y, t.x};
}
else if (dist[ny][nx] == dist[t.y][t.x] + g[ny][nx])
{
if (tim[ny][nx] < tim[t.y][t.x] + 1)
{
tim[ny][nx] = tim[t.y][t.x] + 1;
path[ny][nx] = {t.y, t.x};
}
}
pq.push({dist[ny][nx], ny, nx});
}
}
}
void getRoad()
{
for (int i = 0; i < team.size(); i++)
{
PII pos = team[i];
road[i].push_back(pos);
while (pos != fin)
{
pos = path[pos.first][pos.second];
road[i].push_back(pos);
}
}
}
void solve()
{
//既然是要在同一段时间内是并行地行动，那么我们就需要枚举时间
//这样可以使得在同一时间段同时行动
queue<info>q;
int num=team.size();
for (int i = 0; i < team.size(); i++)
q.push({i, 0});
for (int i=1;i<=T;i++)
{
queue<Ta>ta;
for (int j=0;j<num;j++)
{
info t=q.front();q.pop();
int ny=road[t.id][t.pos+1].first,
nx=road[t.id][t.pos+1].second;
if (g[ny][nx]==0)
q.push({t.id,t.pos+1});
else
ta.push({ny,nx,t.id,t.pos});
}
while (ta.size())
{
Ta t=ta.front();ta.pop();
if (g[t.y][t.x]>0)
g[t.y][t.x]--;
else if (g[t.y][t.x]<0)
g[t.y][t.x]++;
nums[t.id]--;
if (nums[t.id]>0)
q.push({t.id,t.pos});
else
num--;
}
if (g[fin.first][fin.second]>=0)
break;
}
}
int main()
{
init();
Dijkstra();
getRoad();
solve();
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cout << g[i][j];
if (j!=m)
cout<<" ";
}
cout << endl;
}
if (g[fin.first][fin.second] >= 0)
cout << "Game Over" << endl;
return 0;
}
《RC-u4 攻略分队》
超级复杂模拟题
首先要面临的问题是：
我咋知道分组是咋分的？
dfs（）解决
通过dfs来得到全部分组的情况，通过记录最优分组方式
每一次得到的分组方式 与 最优分组进行比较
最终得到真正的最优分组
正如大佬博客里写的：
#include<iostream> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N=8; int V[N],A[N],B[N],C[N]; vector<int>tm1,tm2,ans1,ans2; //记录当前最优解的组队，对于规则是否满足 bool R0,R1,R2; void judge() { //判断是否满足条件R0：每组必须至少有一个MT bool r0=false; bool he1=false,he2=false; for (int i=0;i<tm1.size();i++) { int id=tm1[i]; if (A[id]==1) { he1=true; break; } } for (int i=0;i<tm2.size();i++) { int id=tm2[i]; if (A[id]==1) { he2=true; break; } } r0=(he1 && he2); if (!r0) return ; //表示之前都没有解，当前有了最优解 if (r0 && !R0) { ans1=tm1,ans2=tm2,R0=r0; return ; } //再接下去说明当前这一种分配方式和最优解都满足规则R0 //从规则1中分出唯一解 bool r1=false,r2=false; bool hB[3],hC[3]; //先看最优解： memset(hB,false,sizeof(hB)); memset(hC,false,sizeof(hC)); for (int i=0;i<ans1.size();i++) { int id=ans1[i]; if (B[id]==1) hB[1]=true; if (C[id]==1) hC[1]=true; } for (int i=0;i<ans2.size();i++) { int id=ans2[i]; if (B[id]==1) hB[2]=true; if (C[id]==1) hC[2]=true; } if (hB[1] && hB[2] && hC[1] && hC[2]) R1=true; if (hC[1] && hC[2]) R2=true; //再看当下的 memset(hB,false,sizeof(hB)); memset(hC,false,sizeof(hC)); for (int i=0;i<tm1.size();i++) { int id=tm1[i]; if (B[id]==1) hB[1]=true; if (C[id]==1) hC[1]=true; } for (int i=0;i<tm2.size();i++) { int id=tm2[i]; if (B[id]==1) hB[2]=true; if (C[id]==1) hC[2]=true; } if (hB[1] && hB[2] && hC[1] && hC[2]) r1=true; if (hC[1] && hC[2]) r2=true; //最优解满足，但是当下的不满足 if (!r1 && R1) return ; //说明当前的才是最优解 if (r1 && !R1) { ans1=tm1,ans2=tm2,R0=r0,R1=r1; return ; } //两种方式都不满足规则1，则用规则2来分出唯一 if (!r1 && !R1) { //当前不满足，但是最优解满足 if (!r2 && R2) return ; if (r2 && !R2) { ans1=tm1,ans2=tm2,R0=r0,R1=r1,R2=r2; return ; } } //下面就是规则1或者规则2两者都满足/或都不满足，则用规则3来分出唯一 int sum1=0,sum2=0; bool ansBg=false,tBg=false; for (int i=0;i<ans1.size();i++) sum1+=V[ans1[i]]; for (int i=0;i<ans2.size();i++) sum2+=V[ans2[i]]; int ansC=abs(sum1-sum2); ansBg=(sum1>sum2); sum1=0,sum2=0; for (int i=0;i<tm1.size();i++) sum1+=V[tm1[i]]; for (int i=0;i<tm2.size();i++) sum2+=V[tm2[i]]; int tC=abs(sum1-sum2); tBg=(sum1>sum2); if (ansC<tC) return ; if (ansC>tC) { ans1=tm1,ans2=tm2,R0=r0,R1=r1,R2=r2; return ; } //要用规则4分出唯一 if (ansBg && !tBg) return ; if (!ansBg && tBg) { ans1=tm1,ans2=tm2,R0=r0,R1=r1,R2=r2; return ; } //用规则5来分出唯一 int i=0; while (i<ans1.size() && i<tm1.size()) { if (ans1[i]<tm1[i]) return ; if (ans1[i]>tm1[i]) { ans1=tm1,ans2=tm2,R0=r0,R1=r1,R2=r2; return ; } i++; } if (tm1.size()<ans1.size()) { ans1=tm1,ans2=tm2,R0=r0,R1=r1,R2=r2; return ; } } void dfs(int i) { if (i>6) { judge(); return ; } if (V[i]==0) { dfs(i+1); return ; } tm1.push_back(i); dfs(i+1); tm1.pop_back(); tm2.push_back(i); dfs(i+1); tm2.pop_back(); } int main() { for (int i=1;i<=6;i++) cin>>V[i]; for (int i=1;i<=6;i++) { string str; cin>>str; A[i]=str[0]-'0',B[i]=str[1]-'0',C[i]=str[2]-'0'; } dfs(1); if (!(ans1.size() && ans2.size())) { cout<<"GG"<<endl; return 0; } for (int i=0;i<ans1.size();i++) { cout<<ans1[i]; if (i!=ans1.size()-1) cout<<" "; } cout<<endl; for (int i=0;i<ans2.size();i++) { cout<<ans2[i]; if (i!=ans2.size()-1) cout<<" "; } cout<<endl; return 0; }