「uoj #5」怎样提高智商

2015年1月18日3,4010

大力水手最近和他的女朋友奥利弗分手了，他感到人生非常灰暗，于是上山来找禅师解惑。

大力水手问禅师：“大师，奥利弗以前经常说我是个笨蛋，让我觉得很生气。大概是因为我真的太笨了她才这么说吧。请问，怎样才能提高智商？”

禅师浅笑，答：“方法很简单，不过若想我教你，你先看看这张试卷。”

大力水手拿到试卷，共有 n 道选择题，编号为 1 到 n。第 i 道题形如：（hi 为 “A” 或 “B” 或 “C” 或 “D”，ai,bi,ci,di都是整数）

i. 编号小于 i 的题目中你一共选了几个 hi？
- A. ai 个
- B. bi 个
- C. ci 个
- D. di 个

大力水手问禅师：“是要我做这张试卷吗？”。禅师摆摆手，答：“多想想。”

大力水手注意到一张试卷可能有很多种正确答案（两种正确答案被认为是不同的当且仅当存在一道题这两份正确答案选的选项不同），于是问禅师：“是要我求这张试卷有多少种正确答案吗？”。禅师摆摆手，答：“多想想。”

大力水手想到，一张试卷要是正确答案有很多种，就很容易蒙对，于是问禅师：“是要我求出所有 n 道选择题的试卷中，正确答案最多的试卷吗？”。禅师点点头，转身离去。

例子

1. 编号小于 1 的题目中你一共选了几个 B？
- A. 0 个
- B. 7 个
- C. 1 个
- D. 4 个
2. 编号小于 2 的题目中你一共选了几个 A？
- A. 3 个
- B. 2 个
- C. 1 个
- D. 4 个
3. 编号小于 3 的题目中你一共选了几个 D？
- A. 0 个
- B. 2 个
- C. 1 个
- D. 0 个

共有两种正确答案。一种可能的正确答案为：第一题选 A 第二题选 C 第三题选 D。

输入格式

共一行，包含一个正整数 n，表示试卷中选择题的个数。

输出格式

第一行一个整数，表示正确答案最多的试卷的正确答案数。你只用输出答案对 998244353（7×17×223+1，一个质数）取模后的值。

接下来 n 行输出一种正确答案最多的试卷。如果有多种你可以输出任意一种。

这 n 行中的第 i 行包含 hi,ai,bi,ci,di，表示第 i 道选择题。hi 为 “A” 或 “B” 或 “C” 或 “D”，ai,bi,ci,di 都是整数且 0≤ai,bi,ci,di≤109。

样例一

input

1

output

4
A 0 0 0 0

1 2	4 A 0 0 0 0

explanation

n=1 时正确答案最多的试卷的正确答案数为 4，四种正确答案分别为：第一题选 A、第一题选 B、第一题选 C、第一题选 D。

样例二

n=2 时正确答案最多的试卷的正确答案数为 12，但是你以为我会告诉你这张试卷长什么样吗？

限制与约定

测试点编号	n
1	n=2
2	n=3
3	n=4
4	n=5
5	n=6
6	n≤1000
7	n≤1000
8	n≤105
9
10

时间限制：1

UOJ有详细题解

#include<iostream>
#include<set>
#include<map>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#define p 998244353
#define inf 2000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,ans;
int qpow(ll a,int b)
{
	ll ans=1;
	for(int i=b;i;i>>=1,a=a*a%p)
		if(i&1)ans=ans*a%p;
	return ans;
}
int main()
{
	n=read();
	ans=qpow(3,n-1);
    ans=(ll)ans*4%p;
	printf("%d\n",ans);
	for(int i=1;i<=n;i++)
		printf("A 0 0 0 0\n");
	return 0;
}

#include<iostream>

#include<set>

#include<map>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<cmath>

#define p 998244353

#define inf 2000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,ans;

int qpow(ll a,int b)

{

ll ans=1;

for(int i=b;i;i>>=1,a=a*a%p)

if(i&1)ans=ans*a%p;

return ans;

}

int main()

{

n=read();

ans=qpow(3,n-1);

ans=(ll)ans*4%p;

printf("%d\n",ans);

for(int i=1;i<=n;i++)

printf("A 0 0 0 0\n");

return 0;

}

« 「codechef」January Challenge 2015 「CF508E」Arthur and Brackets »

hzwer.com _ Home | http://hzwer.com

「uoj #5」怎样提高智商

i. 编号小于 i 的题目中你一共选了几个 hi？

例子

1. 编号小于 1 的题目中你一共选了几个 `B`？

2. 编号小于 2 的题目中你一共选了几个 `A`？

3. 编号小于 3 的题目中你一共选了几个 `D`？

输入格式

输出格式

样例一

input

output

explanation

样例二

限制与约定

分类目录

热门文章

Myfriends

近期评论

hzwer.com _ Home | http://hzwer.com

「uoj #5」怎样提高智商

i. 编号小于 i 的题目中你一共选了几个 hi？

例子

1. 编号小于 1 的题目中你一共选了几个 B？

2. 编号小于 2 的题目中你一共选了几个 A？

3. 编号小于 3 的题目中你一共选了几个 D？

输入格式

输出格式

样例一

input

output

explanation

样例二

限制与约定

分类目录

热门文章

Myfriends

近期评论

1. 编号小于 1 的题目中你一共选了几个 `B`？

2. 编号小于 2 的题目中你一共选了几个 `A`？

3. 编号小于 3 的题目中你一共选了几个 `D`？