Codeforces Round 948 (Div. 2) E. Tensor（思维题-交互）

题目

n(3<=n<=100)个点的有向图，

图的边的关系未知，但保证以下两点：

1. 只存在j->i（i<j）的边

2. 对于任意三个点i、j、k（i<j<k），要么k可以到达i，要么k可以到达j，要么j可以到达i

每次你可以询问两个点，? i j（i<j），如果j可以到达i，返回YES，否则返回NO

你需要将图染成黑白两色，

使得黑色的任意两个点x、y（x<y），都满足y可到达x，

且白色的任意两个点x、y（x<y），都满足y可到达x

你有最多2n次询问机会，可以证明答案一定存在

最终输出n个点染色的情况，输出0表示染黑色，为1表示染白色

图不是交互式的，也就是说图一开始是固定下来的，不会随询问的改变而动态变更

实际t(t<=100)组样例，但保证sumn不超过1000

思路来源

乱搞ac

题解

其实也不完全是算乱搞，一开始wa了，后来看了下数据的反例修了下就过了

首先原图肯定可以拆分成两条链，这样对于三个点，一定存在两点共链，就满足题意了

然后考虑这个图的形状可能是怎样的，一开始是想的双螺旋结构的

维护两条链，开始只有点n，然后点n-1如果在点n下游就接上去，否则就新开一条链，

然后这两条链可以汇集在一点，后续在这点之后继续扩，类似Y型，

然后Y型后续还能拆成两个分支，再成两条链，后续两条链再能合并成一个点，重复若干次

然后输出的话，就沿着点n，往下找一个下游，直接找齐一条链，这样另一条链就自然另一种颜色

但是，遇到了一个反例

可以发现，在点5形成Y字型，后接点4之后，新来的点3并没有续到点4上，

也没有续到点5上，而是续到了点6上，

此时我找的链是10->9->6->5->4->1，就使得另一条链8->7和3->2不连通

而此时应该是10->9->6->3->2，另一条链8->7->5->4->1

这表明，当出现Y形状的交点时（也就是图中的5点）后，代表两条链合成了一条链（合并）

这时候这条链往下接了点4，

新来的点3，可以接在点4后，也可以接在点5后，也可以接在点6后，也可以接在点7后，

这四种情况，都能使原图被划分成两条链，

对于5->4链上有多个点的情况，不妨只视为有Y字形交点（点5）、Y字形尾部点（点4）两个点

因为在链中间的点后面续新的点，都可以看成是在交点后面续新的点，不影响两条链的性质

此外注意到，点3的出现，使得一条链又变成了两条链（拆分）

这两条链后续仍然可能再形成新的Y字形，也就是分分合合的过程可能出现若干次

所以，做法是：

1. 初始时，点n当第一条链的链尾

2. 当前如果有两条链，记他们的链尾分别为f和s，当前要续的点是i，

（1）i如果能同时往f和s后面续，代表两条链合成了一条

（2）否则，如果能往第一条链后面续，就往第一条后面续

（3）否则，如果能往第二条链后面续，就往第二条后面续

（4）否则，两条链都续不了，记两条链上一次合并成Y字形交点（也就是上图的点5）为las，如果能往las后面续，就往las后面续

（5）否则，记las的两个父亲为f1、f2（也就是上图的点6、点7），如果能往f1后面续，就往f1后面续

（6）否则往f2后面续

3. 如果当前只有一条链，能续则续，不能续的时候，新开一条链即可

代码里加了如果不存在则为-1的情况，以及加了询问的记忆化，统一了部分情况的分类讨论

询问次数想了一下，是不超过2n的，因为最极端的情况是上图点3不能续到点4后面的情况

此时有4种情况，需要最多询问3次才能确认是哪种情况，

而这种情况的出现，说明前面有一个只询问了1次的点，也就是在点5下面的点4，

这两个点均摊一下，平均次数就不超过2了

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=105;
int t,n,col[N];
vector<int>e[N];
int mp[N][N];
char s[10];
void clr(int x){if(x<0)return;e[x].clear();
}
void add(int x,int y){if(x<0)return;e[x].pb(y);
}
bool ask(int i,int j){if(i>j)return 0;if(~mp[i][j])return mp[i][j];printf("? %d %d\n",i,j);fflush(stdout);scanf("%s",s);return mp[i][j]=(strcmp(s,"YES")==0);
}
void out(){printf("! ");rep(i,1,n){printf("%d%c",col[i]," \n"[i==n]);}fflush(stdout);
}
int main(){sci(t);while(t--){memset(col,0,sizeof col);memset(mp,-1,sizeof mp);sci(n);rep(i,1,n)e[i].clear();int f=n,s=-1,las=-1,f1=-1,f2=-1;bool x,y;per(i,n-1,1){x=ask(i,f),y=ask(i,s);if(x && y){add(f,i);add(s,i);las=i,f1=f,f2=s;f=i,s=-1;}else if(x){add(f,i);f=i;}else if(y){add(s,i);s=i;}else{if(las==-1)s=i;else{y=ask(i,las);if(y){add(las,i);s=i;continue;}y=ask(i,f1);if(y){clr(f1);add(f1,i);s=i;}else{clr(f2);add(f2,i);s=i;}}}}for(int i=n;;i=e[i][0]){col[i]=1;if(e[i].empty())break;}out();}return 0;
}