uoj60 怎样提高智商

题意：你需要构造n个四项选择题。格式为：问在前i个问题中选了几个hi字母？

输出有最多正确答案的构造方案。

标程：

 #include<cstdio>

 using namespace std;

 typedef long long ll;

 const int mod=;

 int ksm(int x,int y)

 {

     int res=;

     while (y) {if (y&) res=(ll)res*x%mod; x=(ll)x*x%mod; y>>=;}

     return res;

 }

 int main()

 {

     int n;

     scanf("%d",&n);

     printf("%d\n",(ll)ksm(,n-)*%mod);

     for (int i=;i<n;i++) puts("A 1 0 0 0");

     puts("A 0 0 0 0");

     return ;

 }

题解：构造

大力猜结论

考虑怎样让答案之间的影响最小，不然到后面难以构造。

不管什么字母，第一局的答案一定是0。所以我们可以给第一局设一个错误答案，该选项一定不会被选。

第二局就询问这个选项被选了几次，答案也一定是0，于是再在同一位置设错误答案。以此类推。

最后一行不用顾忌下一行，四个都是0即可。

正确答案数有3^(n-1)*4.

巴特西

uoj60 怎样提高智商

最新文章

热门文章