天津建设厅官方网站,承接app网站开发的广告,资讯网站如何做聚合,docker 部署wordpress正题
题目链接:https://www.luogu.com.cn/problem/P7045?contestId36089 题目大意 nnn个物品有一些颜色#xff0c;可以询问QQQ次两个物品的颜色是否相同#xff0c;求一个排列是的相邻的物品颜色不同。其中Q≥2n−2Q\geq 2n-2Q≥2n−2 解题思路
对于每一个不在头尾的物品…正题
题目链接:https://www.luogu.com.cn/problem/P7045?contestId36089 题目大意
nnn个物品有一些颜色可以询问QQQ次两个物品的颜色是否相同求一个排列是的相邻的物品颜色不同。其中Q≥2n−2Q\geq 2n-2Q≥2n−2 解题思路
对于每一个不在头尾的物品我们需要求出两个与其颜色不同的物品当我们判断两个物品颜色是否相同时如果不同那么我们就各为一个物品找到了一个颜色不同的。如果相同假设有kkk个颜色相同的物品那么只需要找到k1k1k1个颜色与他们不同的物品也就是没浪费一个询问找到相同的物品后面就可以少用一次询问找不同的物品。所以可以证明如果有解的话那么一定在2n−22n-22n−2次可以询问出答案。
考虑如何实现我们开一个栈如果新的物品和栈顶的颜色相同那么压入栈中。否则在序列后面填入一个栈顶元素如果此时栈为空那么将新的物品压入栈中否则直接填在后面。
对于剩下栈中的元素我们从前面往后开始找位置填入即可。
时间复杂度O(Tn)O(Tn)O(Tn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includestack
using namespace std;
const int N5e410;
int T,n,Q,v[N],z[N],a[N],cnt;
stackint s;
int Ask(int x,int y){int ans;printf(%d %d\n,x-1,y-1);fflush(stdout);scanf(%d,ans);return ans;
}
int main()
{scanf(%d,T);v[0]1;while(T--){scanf(%d%d,n,Q);for(int i1;in;i)v[i]z[i]0;while(!s.empty())s.pop(); cnt0;s.push(1);int lim1;for(int i2;in;i){bool zAsk(s.top(),i);if(z){a[cnt]s.top();s.pop();if(s.empty())s.push(i),limi;else a[cnt]i;}else s.push(i);}a[cnt]s.top();s.pop();if(s.empty()){printf(%d\n,n); for(int i1;icnt;i)printf(%d ,a[i]-1);putchar(\n);fflush(stdout);continue;}for(int i1;ilim;i){v[i]Ask(a[i],s.top());if(v[i]v[i-1]){z[i]s.top();s.pop();if(s.empty())break;}}if(!s.empty()){printf(-1\n);fflush(stdout);continue;}printf(%d\n,n);for(int i1;icnt;i){if(z[i])printf(%d ,z[i]-1);printf(%d ,a[i]-1);}putchar(\n);fflush(stdout);}
}
