T1：卡门（kamen）
思路：
模拟。
据说可以用线段树和分块，但是咱还是选择最朴素的叽里呱啦一大坨子的预处理方式。
可以发现 \(c\) 极小，所以我们可以预处理出从第 \(x\) 列丢下去的石头能掉到的位置。
但是这里的部分石头会滚下去怎么办？
我们可以在每次投下石头以后更新一下从该列投下石头的路径。
因为这些路径的上面一些部分是重合的，所以我们可以从上一次的位置往上跳，一直跳到一个空的地方，然后继续模拟题意就好了。
具体实现见代码
代码：
$code$
#include<iostream>
using namespace std;
const int R=3e4+1,C=35;
int r,c,n,x,a[R][C],cnt[C],to[C][R][2];
char ch;
inline void work(int id){while(cnt[id]>1&&a[to[id][cnt[id]][0]][to[id][cnt[id]][1]]){to[id][cnt[id]][0]=to[id][cnt[id]][1]=0;cnt[id]--;}//跳到一个空位置 int x=to[id][cnt[id]][0],y=to[id][cnt[id]][1];while(1){bool f=0;while(!a[x][y]) x++;//往下跳 x--;cnt[id]++;to[id][cnt[id]][0]=x;to[id][cnt[id]][1]=y;//记录下来 if(a[x+1][y]==1){//到底了 a[x][y]=2;break;}if(y>1&&!a[x+1][y-1]&&!a[x][y-1]){//先左 y--;}else if(y<c&&!a[x+1][y+1]&&!a[x][y+1]){//后右 y++;}else{//再中间 f=1;a[x][y]=2;}if(f) break;}
}
int main(){
// freopen("kamen.in","r",stdin);
// freopen("kamen.out","w",stdout);ios::sync_with_stdio(false);cin>>r>>c;for(int i=0;i<=r+1;i++){for(int j=0;j<=c+1;j++){a[i][j]=1;}}//初始化（给边界框个框框） for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){cin>>ch;a[i][j]=(ch=='X');}}//输入 for(int i=1;i<=c;i++){cnt[i]=1;to[i][cnt[i]][0]=1;to[i][cnt[i]][1]=i;}//初始化*2 cin>>n;for(int i=1;i<=n;i++){cin>>x;work(x);}for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){if(a[i][j]==0) cout<<'.';if(a[i][j]==1) cout<<'X';if(a[i][j]==2) cout<<'O';}cout<<'\n';}//输出 return 0;
} /*
5 5
3 1 4 0
2 1 3 0
1 3 1 1
3 2 3 1
4 2 0 2*/
T2：商人（merchant）
思路：
\(topo\) 排序+贪心。
先摆个小结论：一个出度为 \(0\) 的点不会对其他点造成干扰。
对于一个点来讲，把它初始状态设为最大的 \(r\) 一定是可行的（但是不一定最优）。
所以我们可以给所有的边按边权进行一下排序，假设这条边的起点为 \(x\) ，则我们可以使用这条边来更新 \(ans_x\)
若这条边没有别的出边了，那这个点的答案就已经固定了。
此时我们可以删掉这个点，然后可能会有新的没有出边的点产生，然后继续上述操作。
每一轮入队的点，在处理下一条边之前先处理。
取出这个点的每一条进入的边 \(e_i\) ，设其起点为 \(u\)，终点为 \(v\)，更新 \(u\) 的答案 \(ans_u=min(ans_u,max(r_i,ans_v−p_i))\)。
代码：
$code$
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=3e5+5,inf=0x3f3f3f3f;
int n,m,cnt,head[N],ans[N],du[N];
queue<int> q;
bool vis[N];
struct flower{int a,b,r,p;bool operator < (const flower &css)const{return r<css.r;}
}a[N];
struct node{int to,nxt;
}e[N];
inline void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;
}
int main(){
// freopen("merchant.in","r",stdin);
// freopen("merchant.out","w",stdout);ios::sync_with_stdio(false);cin>>n>>m;for(int i=1;i<=m;i++){cin>>a[i].a>>a[i].b>>a[i].r>>a[i].p;du[a[i].a]++;}sort(a+1,a+1+m);memset(ans,0x3f,sizeof(ans));for(int i=1;i<=m;i++) add(a[i].b,i);for(int i=1;i<=n;i++) if(!du[i]) q.push(i);//topo for(int i=m;i;i--){while(!q.empty()){int x=q.front();q.pop();for(int i=head[x];i;i=e[i].nxt){int y=e[i].to;if(vis[y]) continue;vis[y]=1;du[a[y].a]--;if(!du[a[y].a]) q.push(a[y].a);if(ans[x]!=inf) ans[a[y].a]=min(ans[a[y].a],max(a[y].r,ans[x]-a[y].p));}}if(!vis[i]){vis[i]=1;du[a[i].a]--;if(!du[a[i].a]) q.push(a[i].a);ans[a[i].a]=min(ans[a[i].a],a[i].r);}}for(int i=1;i<=n;i++){if(ans[i]==inf) cout<<-1<<' ';else cout<<ans[i]<<' ';}return 0;
}/*
5 5
3 1 4 0
2 1 3 0
1 3 1 1
3 2 3 1
4 2 0 25 7
1 2 0 1
2 1 10 2
2 3 1 3
3 4 5 2
4 2 2 4
3 5 1 5
4 5 0 3*/