苏州网站建设联系电话,黑龙省建设厅网站,网页版传奇3,微信crm管理系统免费正题
题目链接:https://ac.nowcoder.com/acm/contest/11254/A 题目大意
现在有一个y∈[1,n]y\in[1,n]y∈[1,n]#xff0c;BobBobBob每次可以选择问AliceAliceAlice是否y≥xy\geq xy≥x#xff0c;AliceAliceAlice可以说一次谎。BobBobBob要在最少次数内确定yyy的值#xf…正题
题目链接:https://ac.nowcoder.com/acm/contest/11254/A 题目大意
现在有一个y∈[1,n]y\in[1,n]y∈[1,n]BobBobBob每次可以选择问AliceAliceAlice是否y≥xy\geq xy≥xAliceAliceAlice可以说一次谎。BobBobBob要在最少次数内确定yyy的值而AliceAliceAlice尽量使得次数最多。
现在已知第一次BobBobBob询问的是kkk且AliceAliceAlice回答了是对于k∈[1,n]k\in[1,n]k∈[1,n]求每个kkk BobBobBob需要的最少询问次数。
1≤n≤20001\leq n\leq 20001≤n≤2000 解题思路
dlsdlsdls 在 WC 讲的神仙题目。
对于一种情况假设yiyiyi时AliceAliceAlice说谎的次数是固定的记这个次数为aia_iai所以如果当1∼n1\sim n1∼n中只有一个数字满足ai≤1a_i\leq 1ai≤1时那么答案就是这个数字了。
然后看BobBobBob的操作它每次可以选择一个xxxAliceAliceAlice可以选择让≥x\geq x≥x的数字或者让xxx的数字的位置aiai1a_ia_i1aiai1BobBobBob需要用最少的次数使得只有一个位置ai≤1a_i\leq 1ai≤1。
发现因为每次都是覆盖一个前缀或者一个后缀所以如果只保留ai0/1a_i0/1ai0/1的话那么所有的状态肯定是若干个111若干个000若干个111分别记为a/b/ca/b/ca/b/c个我们就可以设状态为fa,b,cf_{a,b,c}fa,b,c进行转移。
考虑到随着ccc的增大我们肯定会尽量选择中间的位置也就是决策位置是单调递增的所以我们可以做到O(n3)O(n^3)O(n3)的转移。
然后注意到这个和猜数字的规则很像询问次数级别不会超过logn\log nlogn所以我们可以考虑交换次数和一个值域记fw,a,bf_{w,a,b}fw,a,b表示猜测了www次能够猜出来的aaa个000bbb个111ccc个000中最大的ccc然后用决策单调性转移。
时间复杂度O(n2logn)O(n^2\log n)O(n2logn) code #includecstdio#includecstring#includealgorithmusing namespace std;const int N2100;int n,inf,f[20][N][N];int calc(int u,int v){int ans19;while(ansf[ans-1][u][v]0)ans--;return ans;}int main(){scanf(%d,n);memset(f,0xcf,sizeof(f));inff[0][0][0];for(int i0;i1;i)for(int j0;j1-i;j)f[0][i][j]1-i-j;for(int i1;i19;i){for(int j0;jn;j)for(int k0;kj;k){int uf[i-1][j-k][k];int vf[i-1][k][j-k];if(u!infv!inf){umin(u,n-j);f[i][u][j]max(f[i][u][j],v);}}for(int j0;jn;j){int vf[i-1][j][0];if(v!inf){for(int k0;kn-j;k){int uf[i-1][k][j];if(uinf)break;f[i][min(u,n-j)][j]max(f[i][min(u,n-j)][j],vk);f[i][min(vk,n-j)][j]max(f[i][min(vk,n-j)][j],u);}}}for(int j0;jn;j)for(int kn-j-1;k0;k--)f[i][k][j]max(f[i][k][j],f[i][k1][j]);}for(int i0;in;i)printf(%d ,calc(i,n-i));return 0;}
