2026 牛客寒假集训营-4
1. A-本场比赛灵感来源于树状数组出题组
题目描述
怎么出一场区域赛题目？简单，放 2 道签到题和 8 道构造题就行了。
个数字
，如果其他数字中有至少
的数字小于等于
输入描述
第一行输入一个正整数
，表示数组大小。
第二行输入
个整数
，表示数组。
输出描述
输出一个整数表示答案。
解题思路
要注意一下，计算一个值是否在A组时，要考虑和这个值相同的所有数，一个数值算一次，找到临界值就行。
AC 代码
void solve(){
int n;cin>>n;
vector<int>a(n+1,0);
for(int i=1;i<=n;i++)cin>>a[i];
vector<int>b(a);
sort(b.begin()+1,b.begin()+1+n);
int minn;
for(int i=1;i<=n;i++){
if(b[i]!=b[i+1]){
double k=(i-1)*1.0/((n-1)*1.0);
if(k>=0.8){
minn=b[i];
break;
}
}
}
int ans=0;
for(int i=1;i<=n;i++)if(a[i]>=minn)ans+=a[i];
cout<<ans<<"\n";
}
2. B-构造部落
题目描述
位首领，第
位部落首领在位的第
年，还知道第
位首领在位时间
，在此我们假设每一位首领的在位时间都恰好为整数年。
位首领立即即位。
件文物，每件文物上记录了在第
年发生的事件，你需要帮***古学家确定每个事件发生在公元多少年。
输入描述
第一行输入三个整数
，表示部落首领数量，文物数量，第一位部落首领在位的第一年的公元年份。
第二行输入
个正整数
，表示每一位首领在位的年数。
此后
行，第
行输入两个整数
表示第
件文物记录的是第
位首领在位的第
年。
输出描述
对于每一件文物，新起一行输出一个整数，表示该事件发生在公元多少年。
解题思路
从第一个部落首领开始的时间， 处理出每一个部落首领在位的最后一年是哪一年，每一次询问，都在上一个首领在位的最后一年加上后面的时间。
AC 代码
void solve(){
cin>>n>>q>>s;
vector<int>v(n+1,0);
vector<int>end(n+1,s-1);
for(int i=1;i<=n;i++)cin>>v[i];
end[1]=s+v[1]-1;
for(int i=1;i<=n;i++){
end[i]=end[i-1]+v[i];
}
while(q--){
int x,y;cin>>x>>y;
cout<<end[x-1]+y<<"\n";
}
}
3. I-初华的扭蛋机
题目描述
种小球的扭蛋机，小球的颜色分别是白色（
）、绿色（
）、蓝色（
）、粉色（
）、黄色（
）、橙色（
），每种颜色的小球数量都是相等的且无穷多的。
次独立随机抽取，每次等概率地摇出
）。
分别计算：设
枚筹码；若有
颗小球的颜色为
枚筹码；若有
枚筹码。最终我们的筹码数量为在游戏中获得的筹码数量 + 手上的筹码数量。
，表示我们将第
，摇出的小球颜色分别为
枚筹码；有
枚筹码；手上剩余
。
输入描述
本题不需要处理输入。
输出描述
在一行上输出一个长度为
的字符串，表示你所构造的下注方案。
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
解题思路
计算出每一个筹码下注获得的收获期望是205/216， 可以得到不去下注的收获期望是1.0, 直接输出######就行 或者写一个状态压缩，也就只有7^6个状态
AC 代码
void solve(){
string ans="";
double maxx=-inf;
int M=1;
for(int i=0;i<6;i++)M*=7;
for(int i=0;i<M;i++){
int temp=i;
double res=0;
string s="";
for(int j=0;j<6;j++){
int id=temp%7;
temp/=7;
s+=mp[id];
if(id==6)res+=1.0;
else res+=205.0/216.0;
}
if(res>maxx){
maxx=res;
ans=s;
}
}
cout<<ans<<"\n";
}
4. C-墨提斯的排列
题目描述
的排列
，使得相邻两项异或值之和最小。换句话说，最小化：
【名词解释】
这
是一个长度为
的排列，而
和
都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
：指位运算中的按位异或（Bitwise XOR），对两个整数的二进制表示按位进行异或运算。如果您需要更多位运算相关的知识，可以参考 OI-Wiki的相关章节。
输入描述
输入一个正整数
。
输出描述
在一行中输出
个整数，表示构造的排列。
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
解题思路
结论就是格雷码（在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码），构造方式是 i ^ ( i >> 1 )
PS
猜了一个二进制分段倒序的思路，WA了之后，打表发现倒序的方式错误了，下面代码中正确的倒序构造也是格雷码的一种构造方式
AC 代码
void solve(){
cin>>n;
vector<int>a;
a.push_back(0);
for(int i=0;i<n;i++){
int temp=1ll<<i;
for(int j=a.size()-1;j>=0;j--){
a.push_back(a[j]|temp);
}
}
for(auto &x:a)cout<<x<<" ";
}
5. H-时不时使使用玉米加农炮掩饰害羞的邻座艾莉同学
题目描述
的方格，“玉米加农炮”会消灭与方格
列的地图上，我们使用
表示网格中从上往下数第
列的单元格，单元格内有
名敌人。敌方会进行
名敌人。
【名词解释】
和
，其曼哈顿距离为
。
输入描述
第一行输入三个正整数
，表示地图的行数、列数、增援次数。
此后
行，第
行输入
个整数
，表示地图。
此后
行，第
行输入三个正整数
，表示第
次增援。
输出描述
对于每一次增援，新起一行输出两个整数，表示所选方格的坐标。
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
解题思路
先把所有的点作为中心点的结果都找出来，然后每一次增援后，再更新增援点5X5的格子的结果，维护最大的值
AC 代码
void solve(){
cin>>n>>m>>q;
g.assign(n+1,vector<int>(m+1,0));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
check(i,j);
}
}
while(q--){
int x,y,val;cin>>x>>y>>val;
g[x][y]+=val;
for(int i=x-2;i<=x+2;i++){
for(int j=y-2;j<=y+2;j++){
if(safe(i,j))check(i,j);
}
}
auto [res,ansx,ansy]=Q.top();
cout<<ansx<<" "<<ansy<<'\n';
}
}
6. F-爱音的01串构造
题目描述
个
和
个
之和最大。
、
、
。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数
代表数据组数，每组测试数据描述如下：
在一行上输入两个整数
，表示字符串中
的个数、
的个数。
除此之外，保证单个测试文件的
之和、
之和均不超过
。
输出描述
对于每一组测试数据，新起一行输出一个 01 串，表示你所构造的字符串。
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
解题思路
01的贡献是2 ，11的贡献是0 ，00的贡献是1
当1比较多的时候，要减少连续的1的最大长度， 把0平均分在1中就好
当0比较多的时候，00的贡献要小于01，把1平均分在连续的0中会更优
PS
我觉得我的代码都是最基础的思路实现，并不优美
AC 代码
void solve(){
cin>>a>>b;
if(a==b){
for(int i=1;i<=a;i++)cout<<"01";
cout<<"\n";
}
else if(a>b){
int temp=a/(b+1);
int p=a%(b+1);
for(int i=1;i<=b;i++){
if(i<=p)for(int j=1;j<=temp+1;j++)cout<<0;
else for(int j=1;j<=temp;j++)cout<<0;
cout<<1;
}
for(int j=1;j<=temp;j++)cout<<0;
cout<<"\n";
}
else {
int temp=b/(a+1);
int p=b%(a+1);
for(int i=1;i<=a;i++){
if(i<=p)for(int j=1;j<=temp+1;j++)cout<<1;
else for(int j=1;j<=temp;j++)cout<<1;
cout<<0;
}
for(int j=1;j<=temp;j++)cout<<1;
cout<<"\n";
}
}
7. G-真白的幻觉
题目描述
为将
、
、
、
等等。
为
可以执行的次数，即重复执行操作“当
时令
”，直到出现
为止需要的执行次数。
的正整数
，最大化
的值，且
。
输入描述
本题不需要处理输入。
输出描述
在一行上输出两个正整数，表示答案。
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
解题思路
由题可知 123 和 321 的结果是一致的，我们为了减少重复查询，每一次DFS查询时都记录上次选择的添加在末尾的数字，这一次就从上一次开始变的更大，会导致选择方案的急剧减少，再由于1和0对答案没有贡献，所以一开始从2开始枚举往末尾添加的数字，DFS查询到结果{记录次数、原数的下一次运算数、原数},然后排序取前两个下一次运算数不同的原数字
PS
题目理解的有问题，比较f(a) f(b) ，比较的是只有一次的运算数，并非是最后的不动点。
AC 代码
array<int,3>check(int x){
if(x<=10)return {0,x,x};
int pre=x;
int res=0;
while(x!=f(x)){
x=f(x),res++;
}
return {res,f(pre),pre};
}
vector<array<int,3>>v;
void dfs(int p,int pre){
if(p>1e18)return;
if(p>0)v.push_back(check(p));
for(int i=pre;i<=9;i++)dfs(p*10+i,i);
}
void solve(){
dfs(0,2);
sort(v.begin(),v.end(),greater<>());
cout<<v[0][2]<<" ";
for(int i=1;i<v.size();i++){
if(v[i][1]!=v[0][1]){
cout<<v[i][2]<<"\n";
return ;
}
}
}
8. D-东风谷早苗与博丽灵梦
题目描述
，分别表示早苗的移动次数和灵梦的移动次数，且最小化
。如果不存在符合条件的方案，直接输出
。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数
代表数据组数，每组测试数据描述如下：
在一行上输入三个正整数
，表示线段长度，早苗移动速度，灵梦移动速度。
输出描述
对于每一组测试数据，新起一行。如果不存在符合条件的方案，直接输出
，否则：
第一行输出
；
第二行输出两个非负整数
，分别表示早苗、灵梦的移动次数；
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
解题思路
设 a ，b为速度，len为总长度
题意为二元一次方程：x a + y b = len
根据裴蜀定理 : 只有当sum % gcd（a,b）== 0 时 x , y 才有整数解
下面需要解决的 如何最小化 max(x,y) ，同时 x >= 0 && y >= 0
使用扩展欧几里得算法，（对于互质的a，b，找到ax+by=1 的一组特解（x，y））
找出一组特解 （t1,t2）*len 为原方程的一组特解： ans1（ans1=t1 * len），ans2（ans2=t2 * len）
对于原方程 通解为 x = x0 + k * ( b / g ) ，y = y0 - k * ( a / g )
先把 ans1 - n * b，ans2 + n * a（ans1缩小到非负最小），此时ans2应该是最大的，如果ans2 < 0，则没有两个非负整数解
ans1 + temp * b = ans2 - temp * a 转化为：
。
由于 要保证ans2>=0, 所以 temp 的取值还要保证 temp<=( /
)
我们找到的最接近的两个解的运算： ans1 =ans1 + temp * b ， ans2 = ans2 - temp * a ，由于 我们找的是整数解， 要在最低点附近各找一个点，temp ，temp + 1 都要算一次，找到两次计算的最优解
PS
扩欧也忘得有点干净了，使用format输出int128 很好用
AC 代码
void solve(){
cin>>sum>>a>>b;
int g=__gcd(a,b);
if(sum%g!=0){cout<<"No\n"; return;}
a/=g,b/=g,sum/=g;
__int128 t1;
__int128 t2;
__int128 ans1;
__int128 ans2;
__int128 k;
exgcd(a,b,t1,t2);
ans1=t1*sum,ans2=t2*sum;
k=ans1/b;
ans1-=k*b;
ans2+=k*a;
while(ans1<0){ans1+=b;ans2-=a;}
if(ans2<0){cout<<"No\n";return;}
cout<<"Yes\n";
__int128 ans111=ans1,ans222=ans2;
__int128 maxx=ans222/a;
__int128 temp=(ans222-ans111)/(a+b);
__int128 minn=max(ans111,ans222);
__int128 tempk=temp+0;
if(tempk<0)tempk=0;
if(tempk>maxx)tempk=maxx;
__int128 ans11=tempk*b+ans111;
__int128 ans22=ans222-tempk*a;
if(minn>max(ans11,ans22)){
ans1=ans11;
ans2=ans22;
minn=min(max(ans11,ans22),minn);
}
tempk=temp+1;
if(tempk<0)tempk=0;
if(tempk>maxx)tempk=maxx;
ans11=tempk*b+ans111;
ans22=ans222-tempk*a;
if(minn>max(ans11,ans22)){
ans1=ans11;
ans2=ans22;
minn=min(max(ans11,ans22),minn);
}
cout<<format("{} {}",ans1,ans2)<<"\n";
}
9. E-立希的扫雷构造
题目描述
个格子中“地雷”的个数；“地雷”格子的危险值为
的网格图中布置
个地雷，使得所有格子的危险值之和最大。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数
代表数据组数，每组测试数据描述如下：
在一行上输入三个整数
，表示网格图的长宽、地雷数量。
输出描述
对于每一组测试数据，第一行输出一个整数，表示所有网格的危险值之和；此后
行，每行输出一个长度为
，仅由字符
和
组成的字符串
，表示你所构造的网格图。其中，第
个字符
表示第
行第
列的格子为“地雷”；否则表示为“空地”。
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
解题思路
dp[i][j][k][cnt]
表示第i列，第j行，第k种状态（状态压缩），已经使用了cnt个地雷，所形成的最大危险值
先预处理n==9,m==9 的行与行之间的所有状态转移
再进行计算DP转移，算每一种状态的最大危险值
并且可以发现 k个雷产生的危险值实际上等价于将所有位置取反后 n*m-k 个雷产生的危险值（本质上就是在全是雷的地图上放空格产生的”危险值“）,在处理时，可以减少雷数的枚举。
最后记录一下每一个状态的上一个状态，回溯方案
PS
确实一道比较好的状态压缩dp的板子，多理解
AC 代码
void solve(){
n=9;
int kk = n*n/2;
vector dp(n+1,vector(n+1,vector(1<<n,vector<int>(kk+1,-inf))));
vector pre(n+1,vector(n+1,vector(1<<n,vector<int>(kk+1,-1))));
for(int col=1;col<=n;col++){
vector dis(1<<col,vector<int>(1<<col));
int kmax = col * n / 2;
for(int i=0;i< 1<<col;i++){
for(int j=0;j<1<<col;j++){
auto &it=dis[i][j];
for(int p=0;p<col;p++){
if(!(i>>p&1)){
it+=j>>p&1;
if(p>0)it+=j>>(p-1)&1;
if(p<col-1)it+=j>>(p+1)&1;
}
if(!(j>>p&1)){
it+=i>>p&1;
if(p>0)it+=i>>(p-1)&1;
if(p<col-1)it+=i>>(p+1)&1;
if(p>0)it+=j>>(p-1)&1;
if(p<col-1)it+=j>>(p+1)&1;
}
}
}
}
for(int i=0;i<1<<col;i++){
int cnt=__builtin_popcount(i);
dp[col][1][i][cnt]=0;
for(int p=0;p<col;p++){
if(!(i>>p&1)){
if(p>0) dp[col][1][i][cnt] += (i>>(p-1)&1);
if(p<col-1) dp[col][1][i][cnt] += (i>>(p+1)&1);
}
}
}
for(int i=2;i<=n;i++){
for(int j=0;j<1<<col;j++){
int cnt=__builtin_popcount(j);
for(int p=0;p<1<<col;p++){
for(int q=cnt;q<=kmax;q++){
int val = dp[col][i-1][p][q-cnt] + dis[p][j];
if(dp[col][i][j][q] < val){
dp[col][i][j][q] = val;
pre[col][i][j][q] = p;
}
}
}
}
}
}
int T=1;
cin>>T;
while(T--){
cin>>n>>m>>k;
bool flag=0;
if(k*2>=n*m){
k=n*m-k;
flag=1;
}
int maxx=-1,last=-1;
for(int i=0;i<1<<m;i++){
if(dp[m][n][i][k] > maxx){
maxx=dp[m][n][i][k];
last=i;
}
}
vector<int>st(n);
st[n-1]=last;
int temp=k;
for(int i=n-1;i>=1;i--){
int prev=pre[m][i+1][st[i]][temp];
temp -= __builtin_popcount(st[i]);
st[i-1]=prev;
}
cout<<maxx<<"\n";
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if((st[i]>>j&1) ^ flag)
cout<<'*';
else
cout<<'.';
}
cout<<'\n';
}
}
}
10. J-立希坐地铁
题目描述
条环形的地铁构成了一个
的正方形网格（保证
水平方向的地铁有东（
，即
，即
，即
）、逆时针（
）两条线路运行，第
条环形线路经过所有满足
的地铁站，并按方形边界顺时针/逆时针依次连接相邻站点，形成闭环。
表示。并且因为地铁站修得非常不合理，导致同站不同线路的换乘距离非常长，每次站内换乘都需要步行
的起点地铁站，她要去坐标为
的终点地铁站。初始时，立希可以选择任意方向、任意路线的地铁乘坐。
输入描述
第一行输入两个正整数
，表示地铁线路数量，换乘站数量。
第二行输入四个正整数
，表示起点地铁站
、终点地铁站
的横纵坐标。
此后
行，第
行输入两个正整数
，表示第
个换乘站的横纵坐标。
数据保证
一定为偶数，换乘站坐标两两不同，起点地铁站坐标不等于终点地铁站坐标。
输出描述
如果无法构造方案，直接输出
。否则，请参考下方的格式输出。
第一行输出一个整数，表示最短的用时。
第二行输出一个整数
，表示要乘坐的地铁数量。
第三行输出两个整数
，表示立希乘坐地铁的起点站
的横纵坐标。
此后
行：
第一行输出一个字符
，表示立希乘坐地铁的方向。
第二行输出两个整数
，表示立希乘坐地铁的换乘/终点站
的横纵坐标。
注意：除最后一段外，每段乘车的终点
必须是一个可换乘站，地铁乘坐方向存在且可以按顺序连接前后两个地铁站，不允许同站同方向换乘，最后一行出站坐标必须为
。
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
解题思路
1. 分层图建模与离散化
采用分层图最短路思想解决换乘代价问题。将每个物理站点 拆分为 3 个图上节点，分别代表水平（层0）、竖直（层1）、环形（层2）线路状态。由于坐标范围很大但关键点（起点、终点、换乘站）稀疏，利用
map 对坐标进行离散化，只建立 个关键点。对于层内连边，将点按行、列或环编号排序后连接相邻站点，边权为
（环形线需特殊处理首尾相连及一维坐标映射）；对于层间连边，同一物理站点的不同层之间连边权为
（起终点特判为
）。
2. 最短路计算 (Dijkstra)
使用 Dijkstra 算法 计算从起点到终点的最短时间。起点的三个分层节点初始距离均设为 入堆，终点取三个分层节点中
dist 最小者作为最终答案。在处理环形线路时，利用公式 确定环层，并将二维坐标映射为环上的相对一维位置
，以此计算环上两点的顺/逆时针最短距离，确保建图的准确性。
3. 路径还原与指令合并
利用 pre 前驱数组从终点回溯至起点得到原始点序列，随后进行路径合并以生成输出指令。遍历序列时，若连续节点处于同一层且在移动（非同站换乘），则将其合并为同一段行程；仅当发生换乘（层号改变）或到达终点时才结算当前指令。方向判定通过比较前后节点的坐标（E, W, S, N）或环上顺/逆时针代价（C, I）来确定，最终按题目格式输出。
PS
被防AK防住了，我确实不是算法糕手可以了吧
AC 代码
void solve(){
cin>>n>>m;
cin>>sx>>sy>>fx>>fy;
mp.clear();pt.clear();
total=0;
addpt(sx,sy);addpt(fx,fy);
for(int i=0;i<m;i++){
int u,v;cin>>u>>v;
addpt(u,v);
}
int maxx=total*3+5;
for(int i=0;i<=maxx;i++){
E[i].clear();
dist[i]=inf;pre[i]=0;vis[i]=false;
}
int sid=mp[{sx,sy}];
int fid=mp[{fx,fy}];
for(auto &p:pt){
int u0=p.id;
int u1=p.id+total;
int u2=p.id+2*total;
int cost=1;
if(p.id==sid||p.id==fid)cost=0;
add(u0,u1,cost);
add(u1,u2,cost);
add(u0,u2,cost);
}
sort(pt.begin(),pt.end(),[](const node &a,const node &b){
if(a.x!=b.x)return a.x<b.x;
return a.y<b.y;
});
for(int i=0;i<((int)pt.size())-1;i++){
if(pt[i].x==pt[i+1].x){
int res=abs(pt[i].y-pt[i+1].y)*2;
add(pt[i].id,pt[i+1].id,res);
}
}
sort(pt.begin(),pt.end(),[](const node &a,const node &b){
if(a.y!=b.y)return a.y<b.y;
return a.x<b.x;
});
for(int i=0;i<((int)pt.size())-1;i++){
if(pt[i].y==pt[i+1].y){
int res=abs(pt[i].x-pt[i+1].x)*2;
add(pt[i].id+total,pt[i+1].id+total,res);
}
}
sort(pt.begin(),pt.end(),[](const node &a,const node &b){
if(a.k!=b.k)return a.k<b.k;
return a.pos<b.pos;
});
for(int i=0;i<((int)pt.size());){
int j=i;
while(j<pt.size()&&pt[j].k==pt[i].k)j++;
int len=calround(pt[i].k);
if(!len){i=j;continue;}
for(int k=i;k<j-1;k++){
int d=rdist(pt[k].pos,pt[k+1].pos,len)*2;
add(pt[k].id+2*total,pt[k+1].id+2*total,d);
}
int d=rdist(pt[i].pos,pt[j-1].pos,len)*2;
add(pt[i].id+2*total,pt[j-1].id+2*total,d);
i=j;
}
priority_queue<array<int,2>,vector<array<int,2>>,greater<>>q;
int s0=sid,s1=sid+total,s2=sid+total*2;
dist[s0]=dist[s1]=dist[s2]=0;
q.push({0,s0}); q.push({0,s1}); q.push({0,s2});
while(q.size()){
auto x=q.top();q.pop();
int u=x[1],dis=x[0];
if(dis>dist[u])continue;
for(auto e:E[u]){
int v=e[0],w=e[1];
if(dist[v]>dist[u]+w){
dist[v]=dist[u]+w;
pre[v]=u;
q.push({dist[v],v});
}
}
}
int ans=inf;
int best=-1;
int f0=fid;
int f1=fid+total;
int f2=fid+total*2;
if(dist[f0]<ans){
ans=dist[f0];
best=f0;
}
if(dist[f1]<ans){
ans=dist[f1];
best=f1;
}
if(dist[f2]<ans){
ans=dist[f2];
best=f2;
}
if(ans>=inf){
cout<<"Impossible!\n";
return ;
}
vector<int>path;
int now=best;
while(now!=-1){
path.push_back(now);
int nowid=now%total;
if(nowid==sid||dist[now]==0)break;
now=pre[now];
}
reverse(path.begin(),path.end());
vector<node>nodeid(total);
for(auto &p:pt){
nodeid[p.id]=p;
}
vector<cmd>c;
cout<<ans<<"\n";
for(int i=0;i<path.size();){
int u=path[i];
int cnum=u/total;
int uid=u%total;
if(i+1<path.size()){
int v=path[i+1];
int vid=v%total;
if(uid==vid){
i++;
continue;
}
}else{
break;
}
int next=path[i+1];
int nextid=next%total;
char nowdir;
node &S=nodeid[uid];
node &N=nodeid[nextid];
if(cnum==0){
nowdir=(N.y>S.y)?'E':'W';
}
else if(cnum==1){
nowdir=(N.x>S.x)?'S':'N';
}
else{
int len=calround(S.k);
int dist1=(N.pos-S.pos+len)%len;
int dist2=(S.pos-N.pos+len)%len;
if(dist1<=dist2){
nowdir='C';
}
else{
nowdir='I';
}
}
int j=i+1;
while(j+1<path.size()){
int v=path[j];
int nv=path[j+1];
int vid=v%total;
int nvid=nv%total;
int vc=v/total;
int nvc=nv/total;
if(vc!=cnum||nvc!=cnum)break;
node &p1=nodeid[vid];
node &p2=nodeid[nvid];
char ndir;
if(cnum==0){
ndir=(p2.y>p1.y)?'E':'W';
}
else if(cnum==1){
ndir=(p2.x>p1.x)?'S':'N';
}
else{
int len=calround(p1.k);
int dist1=(p2.pos-p1.pos+len)%len;
int dist2=(p1.pos-p2.pos+len)%len;
if(dist1<=dist2){
ndir='C';
}
else{
ndir='I';
}
}
if(ndir!=nowdir)break;
j++;
}
int dest=path[j];
int did=dest%total;
c.push_back({nowdir,nodeid[did].x,nodeid[did].y});
i=j;
}
cout<<c.size()<<"\n";
cout<<sx<<" "<<sy<<"\n";
for(auto &temp:c){
cout<<temp.dir<<"\n";
cout<<temp.px<<" "<<temp.py<<"\n";
}
}
京公网安备 11010502036488号