牛客竞赛第三届越杯程序设计团体赛题解

比赛链接：第三届超越杯程序设计团体赛重现赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJhttps://www.nowcoder.com/acm/contest/31374

A.红红找蓝蓝.

题目描述

 信大校园很大很大很大，红红和蓝蓝最近玩上了捉迷藏。具体来说，信大可以抽象成一个 n×n的方格矩阵，`x` 表示不能行走的楼房（可能是教学楼、实验楼、食堂等地方），`.` 表示可以行走的道路。红红的初始位置在 A 点，而蓝蓝的初始位置在 B 点。红红想从 A 点出发去寻找在 B 点的蓝蓝。红红和蓝蓝都是训练有素的军人，所以他们不会斜着走，只会沿着前、后、左、右四个方向行走。学过广度优先搜索的你，一定很容易求得 A 到 B 的最少步数。红红突发奇想，想知道从 A 到 B 的所有路径之中，请问，最少需要拐弯几次。

开始时与结束时的方向任意，不做要求。

输入描述:

共T(1≤T≤10)组数据。
每组第一行一个整数：n(1≤n≤100)，下面 nnn 行，每行n个字符，只出现字符：`.`，`x`，`A`，`B` （保证 `A,B` 出现）
表示上面所说的矩阵道路。每行的字符中除了题中描述的字符和末尾的换行符之外，没有多余字符。

输出描述:

一个整数：红红所需的最少转弯次数。如果不能到达，输出 -1 。

示例1

输入：

1
3
.xA
...
Bx.

输出：

2

_____________________________________________________________________________

思路：

本题用bfs，因为要求最少转弯，搜索的时候应该按照转弯次数逐层搜索。注意本题数据会卡掉dfs。

代码：

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   const int N=110;
4.  
   char s[N][N];
5.  
   int n,sx,sy,dir[4][2]={1,0,-1,0,0,1,0,-1},st[N][N]; /*st为选择数组*/
6.  
   struct node{
7.  
   int x,y; //坐标
8.  
   int step; //转弯数
9.  
   int state; //状态，分别用1，2，3，4对应左右上下
10.  
    };
11.  
    bool isopp(int a,int b) //判断两个方向是不是反向的
12.  
    {
13.  
    if(a>b) swap(a,b);
14.  
    if(a==1&&b==2) return true;
15.  
    if(a==3&&b==4) return true;
16.  
    return false;
17.  
    }
18.  
    void bfs()
19.  
    {
20.  
    memset(st,0,sizeof(st));
21.  
    queue<node>q;
22.  
    node p;
23.  
    p.x=sx,p.y=sy,p.state=0,p.step=0;
24.  
    q.push(p);
25.  
    st[sx][sy]=1;
26.  
    while(!q.empty()){
27.  
    node t=q.front();
28.  
    q.pop();
29.  
    if(s[t.x][t.y]=='B'){ //找到了
30.  
    cout<<t.step<<endl;
31.  
    return;
32.  
    }
33.  
    for(int i=0;i<4;i ){
34.  
    int nx=t.x dir[i][0],ny=t.y dir[i][1];
35.  
    if(nx<0||nx>=n||ny<0||ny>=n||s[nx][ny]=='x') continue; //出界了，或者为障碍
36.  
    if(t.state==0){ //开始状态
37.  
    while(1){ /*把一个方向都搜到底*/
38.  
    if(nx<0||nx>=n||ny<0||ny>=n||s[nx][ny]=='x') break;
39.  
    node nw;
40.  
    nw.x=nx,nw.y=ny,nw.step=0,nw.state=i 1;
41.  
    if(!st[nx][ny]) q.push(nw),st[nx][ny]=1;
42.  
    nx =dir[i][0],ny =dir[i][1];
43.  
    }
44.  
    }
45.  
    else{
46.  
    while(1){ //垂直方向入队
47.  
    if(nx<0||nx>=n||ny<0||ny>=n||s[nx][ny]=='x'||isopp(i 1,t.state)) break; //如果在同一直线的方向不需要搜
48.  
    node nw;
49.  
    nw.x=nx,nw.y=ny,nw.step=t.step 1,nw.state=i 1;
50.  
    if(!st[nx][ny]) q.push(nw),st[nx][ny]=1;
51.  
    nx =dir[i][0],ny =dir[i][1];
52.  
    }
53.  
    }
54.  
    }
55.  
    }
56.  
    cout<<-1<<endl; //没找到
57.  
    }
58.  
    int main()
59.  
    {
60.  
    int t;
61.  
    cin>>t;
62.  
    while(t--){
63.  
    cin>>n;
64.  
    for(int i=0;i<n;i )
65.  
    for(int j=0;j<n;j ){
66.  
    cin>>s[i][j];
67.  
    if(s[i][j]=='A') sx=i,sy=j;
68.  
    }
69.  
    bfs();
70.  
    }
71.  
    return 0;
72.  
    }

B. 红红蓝蓝在争论.

题目描述

 红红和蓝蓝都是信大的学生，他们最近对二进制 0 和 1 字符串特别感兴趣。红红总喜欢把 1 变成 0 ，而蓝蓝总喜欢把 0 变成 1 。他们在争吵之中，定义一个 01 字符串的最大有效值为该字符串中最长连续的 0 的个数与最长连续的 1 的个数的较大值。

现在给定了一个长度为 n 的 01 串 s ，红红和蓝蓝合计可以执行最多 m 次操作。

对于每次操作，蓝蓝把某一位的 0 改成 1 ，或者红红把 1 改成 0 。

求字符串 S 在最多 m 次操作的最大有效值。

输入描述:

 共 T(1≤T≤20)组数据。
每组数据包括 2个整数n(1≤n≤100000)和m(1≤m≤1000)。n 为字符串长度，m 为操作次数。
以下一行，为长度为 n 的字符串 S 。

输出描述:

 一个整数，表示题面描述的最大有效值。

示例1

输入：

2
5 1
00101
2 1
01

输出：

4
2

_____________________________________________________________________________

思路：

本来想用背包模型动态规划dp[n][m]来刻画，滚动数组空间优化到n*2赌一赌，结果还是超时了qwq.

这道题方法很多，很多大牛用前缀和 二分，本菜鸡介绍一下用双指针的做法。

 以求最长连续1为例，首先可以用一个数组记录一下0出现的位置（可以被修改的），然后考虑某个位置i，判断修改次数<=m，修改本位置，更新最大值，i指针后移。否则考虑j指针的位置不修改，i指针位置修改，更新最大值，两个指针后移。

上述方法分别对1和0求最长连续序列即可。

代码：

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   char s[100010];
4.  
   int main()
5.  
   {
6.  
   int t,n,m;
7.  
   cin>>t;
8.  
   while(t--){
9.  
   int ans=0;
10.  
    vector<int>z,o; //z代表0出现的位置，o代表1出现的位置
11.  
    cin>>n>>m>>s;
12.  
    for(int i=0;i<n;i ){
13.  
    if(s[i]=='0') z.push_back(i);
14.  
    else o.push_back(i);
15.  
    }
16.  
    int j=0;
17.  
    for(int i=0;i<z.size();i ){
18.  
    if(i 1<=m){ //修改位置
19.  
    if(i 1==z.size()) ans=n; //如果是最后一个，直接和尾部连接成最长连续序列。
20.  
    else ans=max(ans,z[i 1]); //从0到下一个断点的前一位
21.  
    continue;
22.  
    }
23.  
    /*考虑i修改，j不修改*/
24.  
    if(i 1==z.size()) ans=max(ans,n-1-z[j ]-1);
25.  
    else ans=max(ans,z[i 1]-z[j ]-1);
26.  
    }
27.  
    j=0;
28.  
    for(int i=0;i<o.size();i ){
29.  
    if(i 1<=m){
30.  
    if(i 1==o.size()) ans=n;
31.  
    else ans=max(ans,o[i 1]);
32.  
    continue;
33.  
    }
34.  
    if(i 1==o.size()) ans=max(ans,n-1-o[j ]-1);
35.  
    else ans=max(ans,o[i 1]-o[j ]-1);
36.  
    }
37.  
    cout<<ans<<endl;
38.  
    }
39.  
    return 0;
40.  
    }

C.合法的IP地址.

题目描述

 红红和蓝蓝是一个合格的本科生了。这一天，他们在学习计算机网络中的 IP 地址。他们对 IP 地址的使用场景很感兴趣，但是，由于刚接触 IP 地址，他们无法判断一个给定的字符串，是否为一个合法的 IP 地址。
你能帮帮他们吗？
一个合法的 IP 地址，需要满足以下条件：
（1）该 IP 地址，为 A.B.C.D的形式
（2）A,B,C,D均为十进制数值，即字符范围为 0∼9，不会出现其他字符
（3）0<A≤255
（4）0≤B,C,D≤255

输入描述:

 该输入文件提供 T(1≤T≤100)组数据，每组数据为一个长度不超过15的字符串。

输出描述:

若该字符串为一个合法的 IP 地址，则输出 `YES`（不带引号）；否则，输出 `NO` 。末尾带一个换行符。

示例1

输入：

3
1.1.1.1
255.255.255.0
256.255.255.0

输出：

YES
YES
NO

_____________________________________________________________________________

思路：

模拟题，不多解释，注意数据有多个'.'连续出现的情况。

代码：

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   int main()
4.  
   {
5.  
   int t;
6.  
   cin>>t;
7.  
   while(t--){
8.  
   string s,a;
9.  
   cin>>s;
10.  
    int cnt=0,flag=1;
11.  
    for(int i=0;i<s.size();i ){
12.  
    if(i==0&&s[i]=='.'){
13.  
    flag=0;
14.  
    break;
15.  
    }
16.  
    else if(i==s.size()-1&&s[i]=='.'){
17.  
    flag=0;
18.  
    break;
19.  
    }
20.  
    else if(s[i]=='.'){
21.  
    if(a==""){
22.  
    flag=0;
23.  
    break;
24.  
    }
25.  
    int sum=0;
26.  
    cnt ;
27.  
    if(cnt>3){
28.  
    flag=0;
29.  
    break;
30.  
    }
31.  
    for(int j=0;j<a.size();j ){
32.  
    sum=sum*10 a[j]-'0';
33.  
    if(sum>255){
34.  
    flag=0;
35.  
    break;
36.  
    }
37.  
    }
38.  
    if(flag==0) break;
39.  
    if(cnt==1&&sum==0){
40.  
    flag=0;
41.  
    break;
42.  
    }
43.  
    a="";
44.  
    }
45.  
    else if(!isdigit(s[i])){
46.  
    flag=0;
47.  
    break;
48.  
    }
49.  
    else if(s[i]!='.') a.push_back(s[i]);
50.  
    }
51.  
    if(cnt!=3) flag=0;
52.  
    if(flag){
53.  
    int sum=0;
54.  
    for(int j=0;j<a.size();j ){
55.  
    sum=sum*10 a[j]-'0';
56.  
    if(sum>255){
57.  
    flag=0;
58.  
    break;
59.  
    }
60.  
    }
61.  
    }
62.  
    if(flag) puts("YES");
63.  
    else puts("NO");
64.  
    }
65.  
    return 0;
66.  
    }

D.石头剪刀布.

题目描述

 又到了每周扫大环的时间，这周的安排是小红。可到了正要下去扫的时候，小红给班长说她胃疼，扫不了地了。班长只好让小蓝去扫。小蓝不愿意，小红就说咱俩玩剪刀石头布，谁输了谁去。小蓝知道第一次小红会出石头，第二次小红会出剪刀，第三次小红会出布，之后小红会按照：石头、剪刀、布、石头、剪刀、布的顺序一直循环。蓝蓝，想请问你，你需要以怎么样的应对策略来面对小红，才能达到 100% 的胜率呢？

输入描述:

共T(1≤T≤100)组数据。
每组数据为一个整数 n(1≤n≤1000)，表示蓝蓝正在与小红进行第n次游戏。

输出描述:

对每组数据，输出一行字符串。
石头输出 `Rock` ，剪刀输出 `Scissors`，布输出 `Paper` 。
末尾只带有一个换行符。

示例1

 输入：

1
1

输出：

Paper

_____________________________________________________________________________

思路：

本场签到题。

代码:

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   int main()
4.  
   {
5.  
   int t,n;
6.  
   cin>>t;
7.  
   while(t--){
8.  
   cin>>n;
9.  
   if(n%3==1) puts("Paper");
10.  
    else if(n%3==2) puts("Rock");
11.  
    else puts("Scissors");
12.  
    }
13.  
    return 0;
14.  
    }

E.填充游戏

题目描述

 小红和小蓝在玩一个游戏。有一个边长为m的正方形，两人依次在正方形中放下圆。规则为：在正方形中放下的圆不能与正方形的边框有任何交点，也不能与已经放入正方形中的其他圆的边框有任何交点。不能再放入圆的选手失败。红红先行动，蓝蓝后行动。两人的博弈论都学得非常好，都是100分，且小红知道小蓝博弈水平很好，小蓝也知道小红水平很好。请问，在两人都是采用最优操作的条件下，红红和蓝蓝谁能获胜呢？

输入描述:

 共T(1≤T≤100)组数据。
每组数据为在一行之中，用空格隔开的两个正整数，第一个正整数为正方形的边长m，第二个正整数为圆的半径n（10≤n≤100,10≤m≤400）。

输出描述:

 如果红红获胜，输出 `honghong yyds`，末尾带一个换行符。
如果蓝蓝获胜，输出`lanlan yyds`，末尾带一个换行符。

示例1

 输入：

2
2 10
3 1

输出：

lanlan yyds
honghong yyds

_____________________________________________________________________________

思路：

思想头脑风暴，代码简单粗暴。

如果第一个圆都放不下，后手胜。否则先手有必胜策略：第一次放中间，根据图形对称性，先手可以放和后手中心对称的位置。所以最后放不下一定是后手遇到。

代码：

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   int main()
4.  
   {
5.  
   int t,n,m;
6.  
   cin>>t;
7.  
   while(t--){
8.  
   cin>>m>>n;
9.  
   if(m<=2*n) puts("lanlan yyds");
10.  
    else puts("honghong yyds");
11.  
    }
12.  
    return 0;
13.  
    }

F.RickLee And 540

题目描述

 RickLee 和 540 报名参加了网络知识技能竞赛。他们以为模拟考试和真实考试是一样的，只要记下答案就可以乱杀考试，于是他们决定先做一套模拟题。出乎意料的是两个人的模拟题题目并不相同，这下他们意识到原来每套题目都是随机从题库里抽几道题组成的。这可难不倒优秀的 xd 学生，他们立马想到多找几个人一起参加模拟考试（因为每个人只有一次模拟的机会），记录下每个人的题目及答案，只要人数够多就一定可以还原出题库来。
 假设题库有 n 道题，每套题是随机选出其中的 m 道（可能重复）， RickLee 和 540 一共找来了 k个人，他们可以还原出题库的概率是多少?

输入描述:

 第一行一个整数 T代表询问组数

之后每行为三个正整数 n(1≤n≤1e5),m(1≤m≤n),k(1≤k≤1e9)

数据保证 ∑n≤1e6

输出描述:

 T 行每行一个整数，表示还原出的概率，答案对 998244353 取模。（假设答案为 p/q，那么就是 p 乘上 q 的逆元再模 998244353 ）。

示例1

输入：

1
2 1 2

输出：

499122177

Hint: 找来的两个人选出的有如下四种情况：11 ，12，21，22。有两种是可行的，概率为 1/2 。2 在模 998244353 下的逆元为 499122177 。

_____________________________________________________________________________

思路：

本题难点在于求出概率表达式，取模数为素数，求逆元可以用费马定理。

 先看总的方案个数，注意每套题m可以重复选择，相当于n个不同的球，每一次有n种选法，总共选m*k次。

分母：

合法的情况，目的是要从n种球种选m*k个，且方案有n种球。从i种球选m*k个的方案数为，容斥原理可得： 

有n种颜色的球，用集合Si表示方案颜色为i色的方案，以n=3为，如图

蓝色合法区域可以表示为：S1 S2 S3-S1*S2-S1*S3-S2*S3 S1*S2*S3

最后，在计算时，mk比较大，需要用欧拉降幂公式。（mod为素数，指数降为mk%(mod-1)）

代码：

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   const int mod=998244353,N=100010;
4.  
   int fact[N],infact[N]; //分别表示n!%mod和n!在%mod下的逆元
5.  
   inline int qp(int a,int b,int m) //快速幂
6.  
   {
7.  
   int res=1;
8.  
   while(b){
9.  
   if(b&1) res=1ll*res*a%m;
10.  
    b>>=1;
11.  
    a=1ll*a*a%m;
12.  
    }
13.  
    return res%m;
14.  
    }
15.  
    inline int C(int a,int b) //计算组合数
16.  
    {
17.  
    if(a<0||b<0||a<b) return 0;
18.  
    return 1ll*fact[a]*infact[b]%mod*infact[a-b]%mod;
19.  
    }
20.  
    inline void init() //预处理出fact和infact，保障后面算组合数复杂度为O(1)，避免超时
21.  
    {
22.  
    fact[0]=infact[0]=1;
23.  
    for(int i=1;i<N;i ){
24.  
    fact[i]=1ll*fact[i-1]*i%mod;
25.  
    infact[i]=1ll*infact[i-1]*qp(i,mod-2,mod)%mod;
26.  
    }
27.  
    }
28.  
    int main()
29.  
    {
30.  
    init();
31.  
    int t,n,m,k;
32.  
    cin>>t;
33.  
    while(t--){
34.  
    cin>>n>>m>>k;
35.  
    int ans=0,sig=1,inv_n=qp(n,mod-2,mod); //inv_n表示n的逆元
36.  
    for(int i=n;i>=1;i--){
37.  
    ans=(1ll*sig*C(n,i)*qp(1ll*i*inv_n%mod,1ll*m*k%(mod-1),mod)%mod ans mod)%mod;
38.  
    sig*=-1;
39.  
    }
40.  
    cout<<ans%mod<<endl;
41.  
    }
42.  
    return 0;
43.  
    }

G.Jump.

题目描述

 Ruri 正在玩一个游戏。现在 Ruri 正站在一个数轴的 1 号位置，他的目标是走到 n号位置。当 Ruri 走到位置 i 时，会得到 ai 的经验值。在位置i时，下一步可以跳到 [li,Ri] 这些位置（位置 n 就不能跳了）。请问 Ruri 可以获得的最大经验是多少？

输入描述:

 第一行为一个正整数 n(1≤n≤2e5)。
第二行有 n 个数表示 a1,a2,⋯ ,an(1≤ai≤1e4)
后面的 n−1 行表示 [Li,Ri](i<Li≤Ri≤n)

输出描述:

 一个整数，表示可获得的最大经验值。

示例1

输入：

6
7 9 1 1 3 7
2 3
5 6
4 6
6 6 
6 6

输出：

26
 Hint:
开始位于 1 号位置，此时经验值为 7 ，下一步能跳到 [2,3]
之后跳到 2 号位置，此时经验值为 7 9=16 ，下一步能跳到 [5,6]
之后跳到 5 号位置，此时经验值为 7 9 3=19，下一步能跳到 [6,6]
最后跳到 6 号位置，此时经验值为 7 9 3 7=26，结束。
显然找不到更优的方案。

_____________________________________________________________________________

思路：

用线段树维护区间最小值，初始化为0.之后查询[i,i]的值t，若不为0，用a[i] t更新区间[li,ri]的所有值（维护当前能跳到的点的最大值）

以样例为例，如图：

最后的答案即为query(1,n) a[n]（最后一步会得到a[n]的值） 

Code:

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   const int N=2e5 10;
4.  
   int a[N];
5.  
   struct tree{
6.  
   int l,r,s,tag; //s为最小值,tag为更新标记
7.  
   }T[N*4];
8.  
   inline void up(int p)
9.  
   {
10.  
    T[p].s=min(T[2*p].s,T[2*p 1].s);
11.  
    }
12.  
    inline void down(int p) //标记下移
13.  
    {
14.  
    if(T[p].tag){
15.  
    T[2*p].tag=max(T[2*p].tag,T[p].tag);
16.  
    T[2*p 1].tag=max(T[2*p 1].tag,T[p].tag);
17.  
    T[2*p].s=T[2*p].tag;
18.  
    T[2*p 1].s=T[2*p 1].tag;
19.  
    T[p].tag=0;
20.  
    }
21.  
    }
22.  
    inline void build_tree(int p,int l,int r) //建树
23.  
    {
24.  
    T[p].l=l,T[p].r=r,T[p].tag=0;
25.  
    if(l==r){
26.  
    T[p].s=0;
27.  
    return;
28.  
    }
29.  
    int m=l r>>1;
30.  
    build_tree(2*p,l,m),build_tree(2*p 1,m 1,r);
31.  
    up(p);
32.  
    }
33.  
    inline void update(int p,int l,int r,int c) //用c更新l,r（维护每个可跳跃点的最大值）
34.  
    {
35.  
    if(T[p].l>r||T[p].r<l) return; //不相关
36.  
    if(c<T[p].s) return; //c比最小值都小，不用更新
37.  
    if(T[p].l>=l&&T[p].r<=r){ //打上懒惰标记
38.  
    T[p].tag=max(T[p].tag,c);
39.  
    T[p].s=T[p].tag;
40.  
    return;
41.  
    }
42.  
    down(p);
43.  
    if(T[2*p].r>=l) update(2*p,l,r,c);
44.  
    if(T[2*p 1].l<=r) update(2*p 1,l,r,c);
45.  
    up(p);
46.  
    }
47.  
    int query(int p,int k) //查询k的值
48.  
    {
49.  
    if(T[p].l==T[p].r) return T[p].s;
50.  
    down(p); //必须做一次标记下移操作
51.  
    if(T[2*p].r>=k) return query(2*p,k);
52.  
    else if(T[2*p 1].l<=k) return query(2*p 1,k);
53.  
    else return 0;
54.  
    }
55.  
    int main()
56.  
    {
57.  
    int n;
58.  
    scanf("%d",&n);
59.  
    build_tree(1,1,n);
60.  
    for(int i=1;i<=n; i) scanf("%d",&a[i]);
61.  
    for(int i=1;i<n; i){
62.  
    int l,r,t;
63.  
    scanf("%d%d",&l,&r);
64.  
    t=query(1,i);
65.  
    if(i!=1&&t==0) continue; //第一次要直接更新
66.  
    update(1,l,r,a[i] t);
67.  
    }
68.  
    printf("%d\n",query(1,n) a[n]);
69.  
    return 0;
70.  
    }

H.信大学子要过河

题目描述

 在这一天，阳光明媚，是一个适合春游的好日子。信大学子共 n个人一齐出发，走啊走，走到一条河的岸边，想要过河到另一边岸上继续游玩，但是却没有桥。岸边有一个只能坐两个人的船。

就像大家过题的手速不一样，大家摆渡渡河的时间也各不相同，船划到对岸的时间等于船上渡河时间较长的人所用的时间。

现在已知每一个信大学子的渡河时间 t ，信大队干部想知道，最少要花费多少时间，才能使所有人都过河。

输入描述:

 共 T(1≤T≤40)组数据。

每组数据第一行为人数 n(1≤n≤100000)。以下有 n 行，每行 1 个数。第 i 1行的数为第 i个人渡河时间。 

输出描述:

 每组数据输出一行。

表示所有人渡过河最少渡河时间。

示例1

输入：

1
4
6
7
10
15

输出：

42

Hint：

初始：A岸：1，2，3，4；B岸：空

第一次：A岸：3，4；B岸：1，2；时间7

第二次：A岸：1，3，4；B岸：2；时间6

第三次：A岸：1；B岸：2，3，4；时间15

第四次：A岸：1，2；B岸：3，4；时间7

第五次：对岸1，2，3，4；时间7

总时间为 7 6 15 7 7=42

_____________________________________________________________________________

思路：

贪心算法。贪心策略：要尽量让送船的人在路上花费时间最短，当然尽量选择时间短的把船送回来。先把时间按从小到大排序，有两种局部最优策略：对于两个耗时最大的人，可以用最小的送两次，消耗的时间是a[1] a[n] a[n-1] a[1];或者是和样例的策略一样，先1，2过河，1送回船，n和n-1过河，2送回船，消耗时间是a[2] a[1] a[n] a[2]。比较一下选最小值即可。

代码：

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   int a[100010];
4.  
   int main()
5.  
   {
6.  
   int t,n;
7.  
   cin>>t;
8.  
   while(t--){
9.  
   cin>>n;
10.  
    for(int i=1;i<=n;i ) cin>>a[i];
11.  
    sort(a 1,a 1 n);
12.  
    if(n==1) cout<<a[1];
13.  
    else if(n==2) cout<<a[2];
14.  
    else{
15.  
    int sum=0;
16.  
    for(int i=n;i-1>2;i-=2){
17.  
    if(a[i-1] a[1]<2*a[2]) sum =a[i] a[1] a[i-1] a[1];
18.  
    else sum =a[1] a[2] a[i] a[2];
19.  
    }
20.  
    if(n%2) sum =a[3] a[1] a[2];
21.  
    else sum =a[2];
22.  
    cout<<sum;
23.  
    }
24.  
    cout<<endl;
25.  
    }
26.  
    return 0;
27.  
    }

I.中国国粹

题目描述

 众所周知，中国国粹是我们伟大的京剧。但本题，我们需要解决的问题是民间国粹：麻将。麻将是一项易学难精的游戏。

下面简要介绍一下麻将的游戏规则。请注意，一定要按照本题设置的麻将游戏规则进行游戏，不要带入自己了解的规则。

 （1）牌型：
牌型分为四种：万；条；饼；字。
一万到九万分别用 1m 到 9m 表示；
一条到九条用 1s 到 9s 表示；
一饼到九饼用 1p 到 9p 表示；
字牌为东西南北中发白，分别用 1c 到 7c 表示。
共34 种牌型，每种牌型 4 个，共 136 张牌。
（2）当手里的 13 张牌，与摸上来的牌或别人打出的牌，组成如下的牌型，即为胡牌。
**牌型组合介绍** 
对子：34种牌型，任意一种有两个，可以算作对子。如两个一万，可算作一对一万；两个发财，可算作一对白板。即AA结构。
搭子：34种牌型，任意一种有三个，可以算作搭子。如三个东风，算作东风搭子；三个二条，算作二条搭子。即AAA结构。除字牌外，三个连续的万牌、条牌、饼牌，也可以算作搭子。如123万，678条等。即ABC结构。
**胡牌方式** 
a）七小对：14 张牌组成了七个对子。如：13 张牌为 1 万 ×1 2万×2 3万×2 4万×2 5万×2 7万×2 8万×2，再摸一张 1 万或者别人打出 1 万，可胡牌。
b）十三幺：1 万 9 万 1 饼 9 饼 1 条 9 条东西南北中发白，各一张。剩下那一张是上述 13 张中任意一张。如 13 张牌为 1 万 9 万 1 饼 9 饼 1 条 9  条东西南北中发白，各一张。再拿到这十三张牌的任意一张就胡。
c）将将胡：14 张牌，都是 2 万 5 万 8 万 2 条 5 条 8 条 2 饼 5 饼 8 饼的某一张。
d）屁胡：除一对牌做对子之外，其余每种牌型都是搭子结构。

现在，给定你手里的 13 张牌，你能迅速算出，你能胡 34 种牌型的哪些牌么？

输入描述:

 共 T(1≤T≤100)组数据。
每组数据为 13 张牌。每张牌为 1m 到 9m、1s 到 9s、1p 到 9p、1c 到 7c的某一张，且不会出现其他不符合麻将牌型的输入，也不会出现牌多或者牌少或每种牌型数量超过 4 张的情况。（保证输入合法）每张牌之间有一个空格，行末尾除换行符外无多余字符。

输出描述:

 每组数据输出一行。如果34种牌型中无牌可胡，则输出 `Ohno` 。否则，先输出总共可胡多少种牌型的数目，然后一个空格与后面的牌型隔开。再按照 1m 到 9m、1s 到 9s、1p 到 9p、1c 到 7c 的顺序，把能胡的牌输出出来。每张牌之间有一个空格，行末尾除换行符外无多余字符。

示例1

输入：

2
1s 2s 3s 2c 2c 2c 2p 3p 5m 6m 7m 1p 1p
1p 1p 2p 3p 4s 5s 6s 7c 7c 3s 3s 2m 2m

输出：

2 1p 4p
Ohno

_____________________________________________________________________________

思路：

模拟题，比较繁琐，注意细节问题要考虑全面，不太容易AC.

预处理：把1m-7c牌型映射成1-34，还需要一个反函数。用b数组存放可以胡掉的牌（能胡掉设为1），最后扫一遍b数组，通过反函数转换即可得到答案。

1.7小对最简单，13张排只能有一个奇数牌，可以胡掉那张牌。

2.将将胡：先统计所有合法牌型个数，如果<13,说明有其他牌，不和要求，否则可以胡掉个数<4的合法牌。

3.13幺：易错。注意14张牌中有一种牌要出现两次，拿到的13张牌不一定是13幺的牌各一个。比如拿两个1万，缺一个9万，就可以胡掉9万。用一个集合表示13幺的牌出现的个数，不能出现13幺以外的牌，且每张不能大于2.

4.屁胡：这个最麻烦，搭子的类型多。出了字牌以外，其他牌还有ABC结构。每个牌都可能作为对子，其他为搭子结构。首先枚举可能胡掉的牌，再枚举对子结构，除去对子结构，14张牌除去对子，还有12张牌，dfs搜索4次，判断合法的搭子。

代码：

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   int a[40],b[40],S[20]={1,9,10,18,19,27,28,29,30,31,32,33,34}; //a[i]i牌出现的个数,b[i]表示i能否被胡，能被胡值为1 S集合为13幺
4.  
   unordered_map<string,int>mp; //牌型对应到数字
5.  
   unordered_map<int,string>unmp; //数字映射到牌型
6.  
   inline void init() //初始化
7.  
   {
8.  
   mp["1m"]=1,mp["2m"]=2,mp["3m"]=3,mp["4m"]=4,mp["5m"]=5,mp["6m"]=6,mp["7m"]=7,mp["8m"]=8,mp["9m"]=9;
9.  
   unmp[1]="1m",unmp[2]="2m",unmp[3]="3m",unmp[4]="4m",unmp[5]="5m",unmp[6]="6m",unmp[7]="7m",unmp[8]="8m",unmp[9]="9m";
10.  
    mp["1s"]=10,mp["2s"]=11,mp["3s"]=12,mp["4s"]=13,mp["5s"]=14,mp["6s"]=15,mp["7s"]=16,mp["8s"]=17,mp["9s"]=18;
11.  
    unmp[10]="1s",unmp[11]="2s",unmp[12]="3s",unmp[13]="4s",unmp[14]="5s",unmp[15]="6s",unmp[16]="7s",unmp[17]="8s",unmp[18]="9s";
12.  
    mp["1p"]=19,mp["2p"]=20,mp["3p"]=21,mp["4p"]=22,mp["5p"]=23,mp["6p"]=24,mp["7p"]=25,mp["8p"]=26,mp["9p"]=27;
13.  
    unmp[19]="1p",unmp[20]="2p",unmp[21]="3p",unmp[22]="4p",unmp[23]="5p",unmp[24]="6p",unmp[25]="7p",unmp[26]="8p",unmp[27]="9p";
14.  
    mp["1c"]=28,mp["2c"]=29,mp["3c"]=30,mp["4c"]=31,mp["5c"]=32,mp["6c"]=33,mp["7c"]=34;
15.  
    unmp[28]="1c",unmp[29]="2c",unmp[30]="3c",unmp[31]="4c",unmp[32]="5c",unmp[33]="6c",unmp[34]="7c";
16.  
    }
17.  
    inline bool find(int n) //S(13幺)中找到n
18.  
    {
19.  
    for(int i=0;i<13; i) if(n==S[i]) return true;
20.  
    return false;
21.  
    }
22.  
    inline bool dfs(int s) //判断合法的搭子，搜索4次，每次除去3个搭子牌
23.  
    {
24.  
    if(s==4){ //边界，如果a都为0就合法了
25.  
    for(int i=1;i<=34; i) if(a[i]) return false;
26.  
    return true;
27.  
    }
28.  
    for(int i=1;i<=34; i)
29.  
    if(a[i]){
30.  
    if(a[i]>=3){
31.  
    a[i]-=3; //拿掉搭子AAA
32.  
    if(dfs(s 1)){
33.  
    a[i] =3; //复原
34.  
    return true;
35.  
    }
36.  
    a[i] =3;
37.  
    }
38.  
    if(i<28){
39.  
    if(a[i]&&a[i 1]&&a[i 2]&&unmp[i][1]==unmp[i 1][1]&&unmp[i 1][1]==unmp[i 2][1]){
40.  
    a[i]--,a[i 1]--,a[i 2]--; //拿掉ABC搭子
41.  
    if(dfs(s 1)){
42.  
    a[i] ,a[i 1] ,a[i 2] ; //复原
43.  
    return true;
44.  
    }
45.  
    a[i] ,a[i 1] ,a[i 2] ;
46.  
    }
47.  
    }
48.  
    return false;
49.  
    }
50.  
    return false;
51.  
    }
52.  
    inline void seven_pair(int &f) //七小对
53.  
    {
54.  
    int cnt=0,t; //cnt记录奇数个数，只能有一个奇数
55.  
    for(int i=1;i<=34; i){
56.  
    if(a[i]&1) cnt ,t=i;
57.  
    if(cnt>1) return;
58.  
    }
59.  
    b[t]=1,f=1;
60.  
    }
61.  
    inline void thirteen_yao(int &f) //13幺
62.  
    {
63.  
    for(int i=1;i<=34; i){
64.  
    if(!a[i]) continue;
65.  
    if(!find(i)) return; //i不在13幺中不合法
66.  
    }
67.  
    int cnt=0,t;
68.  
    for(int i=0;i<13; i){
69.  
    if(a[S[i]]>2||cnt>1) return; //同一个牌数等于2的个数不大于1，不能有大于2的
70.  
    if(a[S[i]]==2) cnt ;
71.  
    if(a[S[i]]==0) t=S[i];
72.  
    }
73.  
    f=1;
74.  
    if(cnt==0) for(int i=0;i<13; i) b[S[i]]=1; //如果拿到的13幺都出现了，都可以胡
75.  
    else b[t]=1; //否则胡掉没出现的那个牌
76.  
    }
77.  
    inline void jjh(int &f) //将将胡
78.  
    {
79.  
    if(a[2] a[5] a[8] a[11] a[14] a[17] a[20] a[23] a[26]<13) return;
80.  
    for(int i=2;i<=8;i =3){ //胡之前判断个数
81.  
    if(a[i]<4) b[i]=1;
82.  
    if(a[i 9]<4) b[i 9]=1;
83.  
    if(a[i 18]<4) b[i 18]=1;
84.  
    }
85.  
    f=1;
86.  
    }
87.  
    inline void pih(int &f) //屁胡
88.  
    {
89.  
    for(int i=1;i<=34; i){ //枚举可能胡的牌
90.  
    if(a[i]==4||b[i]) continue;
91.  
    int flg=0;
92.  
    a[i] ;
93.  
    for(int j=1;j<=34; j)
94.  
    if(a[j]>=2){ //a[j]选做对子
95.  
    a[j]-=2;
96.  
    if(dfs(0)){ //判断有没有搭子结构
97.  
    flg=1;
98.  
    a[j] =2;
99.  
    break;
100.  
     }
101.  
     a[j] =2; //还原
102.  
     }
103.  
     if(flg) f=1,b[i]=1;
104.  
     a[i]--; //还原
105.  
     }
106.  
     }
107.  
     int main()
108.  
     {
109.  
     int t;
110.  
     char ch[5];
111.  
     init();
112.  
     scanf("%d",&t);
113.  
     while(t--){
114.  
     int flag=0;
115.  
     memset(a,0,sizeof(a));
116.  
     memset(b,0,sizeof(b));
117.  
     for(int i=0;i<13; i) scanf("%s",ch),a[mp[ch]] ;
118.  
     seven_pair(flag);
119.  
     thirteen_yao(flag);
120.  
     jjh(flag);
121.  
     pih(flag);
122.  
     if(flag){
123.  
     int cnt=0;
124.  
     for(int i=1;i<=34; i) if(b[i]) cnt ;
125.  
     printf("%d",cnt);
126.  
     for(int i=1;i<=34; i) if(b[i]) printf(" %s",unmp[i].c_str());
127.  
     printf("\n");
128.  
     }
129.  
     else puts("Ohno");
130.  
     }
131.  
     return 0;
132.  
     }

J.Kabayashi And Three consciousness

Ruri 发现对于任意一个有理数  ，都可以不断按以下形式拆分。

    现在给定 p,q ，求 a1,a2,⋯ ,an，其中 a1,a2,⋯ ,an都是整数。

输入描述:

 第一行为两个正整数p(1≤p≤1e18),q(1≤q≤1e18) 。

保证 p,q互质。

输出描述:

 第一行一个整数 n 。第二行n个数，表示拆分结果。

示例1

输入：

17 3

输出：

3
5 1 2

Hint

_____________________________________________________________________________

思路：

把整数部分和小数部分拆开来看。比如a1是p/q的整数部分，即a1=p/q，后面为小数部分，记为b1，可知b1=(p%q)/q，取倒数可以得到递推式q/(p%q)=a2 b2。重复上面步骤，直到小数部分为0即可。

Code:

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   typedef long long ll;
4.  
   int main()
5.  
   {
6.  
   ll p,q;
7.  
   vector<ll>v;
8.  
   cin>>p>>q;
9.  
   while(1){
10.  
    v.push_back(p/q);
11.  
    if(p%q==0) break;
12.  
    ll t=p;
13.  
    p=q;
14.  
    q=t%q;
15.  
    }
16.  
    cout<<v.size()<<endl;
17.  
    for(int i=0;i<v.size();i )
18.  
    printf("%lld ",v[i]);
19.  
    return 0;
20.  
    }

K.最小整数问题

题目描述

 红红最近对超大整数非常感兴趣，可是超大整数已经超过了C语言中整数的可表示范围。而蓝蓝觉得这个问题很简单，他甚至提出了一个更难的问题：给定一个超大整数，在其各位置上的数字可以打乱重新排序的情况下，能够生成许多个不同大小的超大整数。那么请问，在这些超大整数之中，最小的那个是多少？请告诉红红，这个最小的超大整数。（不可出现前导零）

输入描述:

 共 T(1≤1≤100)组数据。

每组数据为一个超大整数，用十进制表示，该数的数位不超过 200 位。输入一定合法。

输出描述:

 每组数据输出一行，为题意中的最小的超大整数。末尾带一个换行符。

示例1

输入：

2
13425
9876543210

输出：

12345
1023456789

_____________________________________________________________________________

思路：

签到题，sort一遍即可。如果有前导0，找到第一个非零元素，交换即可。

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   int main()
4.  
   {
5.  
   int t;
6.  
   cin>>t;
7.  
   string s;
8.  
   while(t--){
9.  
   cin>>s;
10.  
    sort(s.begin(),s.end());
11.  
    int i=0;
12.  
    while(i<s.size()&&s[i]=='0') i ;
13.  
    if(s[0]=='0') swap(s[0],s[i]);
14.  
    cout<<s<<endl;
15.  
    }
16.  
    return 0;
17.  
    }

L.Find And Cal 

题目描述

 Ruri 遇到了两个函数：f(x)表示大于 x的最小的质数。g(x,y) 表示x!包含质因子 y的个数。Ruri 想知道对于一个给定 (x,y)对， g(f(x),y)的大小。 

输入描述:

 第一行一个整数 T(1≤103)，表示询问组数。

后面 T 行为两个正整数 x,y(1≤x≤1e16,2≤y≤1e9)

保证y是素数。

输出描述:

 T行，每行一个整数，g(f(x),y)的大小。答案对 998244343 取模。

示例1

输入：

1
7 2

输出：

8
Hint: 大于 7 的最小质数为 11，11!=1×2×3×⋯×11 ，其中 2,6,10有 3 个 2的因子，4 有 2 个2 的因子，8有 3个 2的因子。

_____________________________________________________________________________

思路：

题目后来做了改动，保证y是素数。求出x后用阶乘分解即可。

本题考察大数判素，用robin判素求出f(x)。

代码：

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   typedef long long ll;
4.  
   const int mod=998244353;
5.  
   ll mul(ll a,ll b,ll m) //大数相乘取模，防止溢出
6.  
   {
7.  
   ll res=0;
8.  
   a%=m,b%=m;
9.  
   for(;b;a=(a a)%m,b>>=1) if(b&1) res=(res a)%m;
10.  
    return res;
11.  
    }
12.  
    ll qp(ll x,ll n,ll m) //快速幂
13.  
    {
14.  
    ll res=1;x%=m;
15.  
    for(;n;x=mul(x,x,m),n>>=1) if(n&1) res=mul(res,x,m);
16.  
    return res%m;
17.  
    }
18.  
    bool Miller_Robin(ll a,ll n) //robin判素
19.  
    {
20.  
    ll x=n-1,y;
21.  
    int t=0;
22.  
    while((x&1)==0) x>>=1,t ;
23.  
    x=qp(a,x,n);
24.  
    for(int i=1;i<=t; i){
25.  
    y=mul(x,x,n);
26.  
    if(y==1&&x!=1&&x!=n-1) return true;
27.  
    x=y;
28.  
    }
29.  
    return y!=1?true:false;
30.  
    }
31.  
    bool isprime(ll x)
32.  
    {
33.  
    if(x==2||x==3||x==7||x==61||x==24251) return true;
34.  
    if(!(x&1)||!(x%3)||!(x%61)||!(x%24251)) return false;
35.  
    if(x%6!=1&&x%6!=5) return false;
36.  
    int a[5]={2,3,7,61,24251};
37.  
    for(int i=0;i<5; i){
38.  
    if(a[i]>=x) break;
39.  
    if(Miller_Robin(a[i],x)) return false;
40.  
    }
41.  
    return true;
42.  
    }
43.  
    int main()
44.  
    {
45.  
    int t,y;
46.  
    ll x;
47.  
    scanf("%d",&t);
48.  
    while(t--)
49.  
    {
50.  
    scanf("%lld%d",&x,&y);
51.  
    x;
52.  
    while(!isprime(x)) x;
53.  
    ll ans=0;
54.  
    x=11;
55.  
    while(x) ans=(ans x/y)%mod,x/=y;
56.  
    printf("%lld\n",ans);
57.  
    }
58.  
    return 0;
59.  
    }

这道题卡常数，上面代码交了10多次才AC。。。

可以加快读快写优化。

这篇好文章是转载于：学新通技术网