比赛链接：第三届超越杯程序设计团体赛重现赛_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。
代码：
#include
using namespace std;
const int N=110;
char s[N][N];
int n,sx,sy,dir[4][2]={1,0,-1,0,0,1,0,-1},st[N][N]; /*st为选择数组*/
struct node{
int x,y; //坐标
int step; //转弯数
int state; //状态，分别用1，2，3，4对应左右上下
};
bool isopp(int a,int b) //判断两个方向是不是反向的
{
if(a>b) swap(a,b);
if(a==1&&b==2) return true;
if(a==3&&b==4) return true;
return false;
}
void bfs()
{
memset(st,0,sizeof(st));
queueq;
node p;
p.x=sx,p.y=sy,p.state=0,p.step=0;
q.push(p);
st[sx][sy]=1;
while(!q.empty()){
node t=q.front();
q.pop();
if(s[t.x][t.y]=='B'){ //找到了
cout<=n||ny<0||ny>=n||s[nx][ny]=='x') continue; //出界了，或者为障碍
if(t.state==0){ //开始状态
while(1){ /*把一个方向都搜到底*/
if(nx<0||nx>=n||ny<0||ny>=n||s[nx][ny]=='x') break;
node nw;
nw.x=nx,nw.y=ny,nw.step=0,nw.state=i+1;
if(!st[nx][ny]) q.push(nw),st[nx][ny]=1;
nx+=dir[i][0],ny+=dir[i][1];
}
}
else{
while(1){ //垂直方向入队
if(nx<0||nx>=n||ny<0||ny>=n||s[nx][ny]=='x'||isopp(i+1,t.state)) break; //如果在同一直线的方向不需要搜
node nw;
nw.x=nx,nw.y=ny,nw.step=t.step+1,nw.state=i+1;
if(!st[nx][ny]) q.push(nw),st[nx][ny]=1;
nx+=dir[i][0],ny+=dir[i][1];
}
}
}
}
cout<<-1<>t;
while(t--){
cin>>n;
for(int i=0;i>s[i][j];
if(s[i][j]=='A') sx=i,sy=j;
}
bfs();
}
return 0;
} 红红和蓝蓝都是信大的学生，他们最近对二进制 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求最长连续序列即可。
代码：
#include
using namespace std;
char s[100010];
int main()
{
int t,n,m;
cin>>t;
while(t--){
int ans=0;
vectorz,o; //z代表0出现的位置，o代表1出现的位置
cin>>n>>m>>s;
for(int i=0;i
C.合法的IP地址.
题目描述
红红和蓝蓝是一个合格的本科生了。这一天，他们在学习计算机网络中的 IP 地址。他们对 IP 地址的使用场景很感兴趣，但是，由于刚接触 IP 地址，他们无法判断一个给定的字符串，是否为一个合法的 IP 地址。
你能帮帮他们吗？
一个合法的 IP 地址，需要满足以下条件：
（1）该 IP 地址，为 A.B.C.D的形式
（2）A,B,C,D均为十进制数值，即字符范围为 0∼9，不会出现其他字符
（3）0 （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
_____________________________________________________________________________
思路：
模拟题，不多解释，注意数据有多个'.'连续出现的情况。
代码：
#include
using namespace std;
int main()
{
int t;
cin>>t;
while(t--){
string s,a;
cin>>s;
int cnt=0,flag=1;
for(int i=0;i3){
flag=0;
break;
}
for(int j=0;j255){
flag=0;
break;
}
}
if(flag==0) break;
if(cnt==1&&sum==0){
flag=0;
break;
}
a="";
}
else if(!isdigit(s[i])){
flag=0;
break;
}
else if(s[i]!='.') a.push_back(s[i]);
}
if(cnt!=3) flag=0;
if(flag){
int sum=0;
for(int j=0;j255){
flag=0;
break;
}
}
}
if(flag) puts("YES");
else puts("NO");
}
return 0;
}
D.石头剪刀布.
题目描述
又到了每周扫大环的时间，这周的安排是小红。可到了正要下去扫的时候，小红给班长说她胃疼，扫不了地了。班长只好让小蓝去扫。小蓝不愿意，小红就说咱俩玩剪刀石头布，谁输了谁去。小蓝知道第一次小红会出石头，第二次小红会出剪刀，第三次小红会出布，之后小红会按照：石头、剪刀、布、石头、剪刀、布的顺序一直循环。蓝蓝，想请问你，你需要以怎么样的应对策略来面对小红，才能达到 100% 的胜率呢？
输入描述:
共T(1≤T≤100)组数据。
每组数据为一个整数 n(1≤n≤1000)，表示蓝蓝正在与小红进行第n次游戏。
输出描述:
对每组数据，输出一行字符串。
石头输出 `Rock` ，剪刀输出 `Scissors`，布输出 `Paper` 。
末尾只带有一个换行符。
示例1
输入：
1
1
输出：
Paper
_____________________________________________________________________________
思路：
本场签到题。
代码:
#include
using namespace std;
int main()
{
int t,n;
cin>>t;
while(t--){
cin>>n;
if(n%3==1) puts("Paper");
else if(n%3==2) puts("Rock");
else puts("Scissors");
}
return 0;
}
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
_____________________________________________________________________________
思路：
思想头脑风暴，代码简单粗暴。
如果第一个圆都放不下，后手胜。否则先手有必胜策略：第一次放中间，根据图形对称性，先手可以放和后手中心对称的位置。所以最后放不下一定是后手遇到。
代码：
#include
using namespace std;
int main()
{
int t,n,m;
cin>>t;
while(t--){
cin>>m>>n;
if(m<=2*n) puts("lanlan yyds");
else puts("honghong yyds");
}
return 0;
}
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)）
代码：
#include
using namespace std;
const int mod=998244353,N=100010;
int fact[N],infact[N]; //分别表示n!%mod和n!在%mod下的逆元
inline int qp(int a,int b,int m) //快速幂
{
int res=1;
while(b){
if(b&1) res=1ll*res*a%m;
b>>=1;
a=1ll*a*a%m;
}
return res%m;
}
inline int C(int a,int b) //计算组合数
{
if(a<0||b<0||a>t;
while(t--){
cin>>n>>m>>k;
int ans=0,sig=1,inv_n=qp(n,mod-2,mod); //inv_n表示n的逆元
for(int i=n;i>=1;i--){
ans=(1ll*sig*C(n,i)*qp(1ll*i*inv_n%mod,1ll*m*k%(mod-1),mod)%mod+ans+mod)%mod;
sig*=-1;
}
cout<
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
输出描述:
一个整数，表示可获得的最大经验值。
示例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]的所有值（维护当前能跳到的点的最大值）
以样例为例，如图：
i a[i] 区间 查询值 更新后的值，从1-6 1 7 2 3 0 0 7 7 0 0 0 2 9 5 6 7 0 7 7 0 16 16 3 1 4 6 7 0 7 7 8 16 16 4 1 6 6 8 0 7 7 8 16 16 5 3 6 6 16 0 7 7 8 16 19 6 7
最后的答案即为query(1,n)+a[n]（最后一步会得到a[n]的值）
Code:
#include
using namespace std;
const int N=2e5+10;
int a[N];
struct tree{
int l,r,s,tag; //s为最小值,tag为更新标记
}T[N*4];
inline void up(int p)
{
T[p].s=min(T[2*p].s,T[2*p+1].s);
}
inline void down(int p) //标记下移
{
if(T[p].tag){
T[2*p].tag=max(T[2*p].tag,T[p].tag);
T[2*p+1].tag=max(T[2*p+1].tag,T[p].tag);
T[2*p].s=T[2*p].tag;
T[2*p+1].s=T[2*p+1].tag;
T[p].tag=0;
}
}
inline void build_tree(int p,int l,int r) //建树
{
T[p].l=l,T[p].r=r,T[p].tag=0;
if(l==r){
T[p].s=0;
return;
}
int m=l+r>>1;
build_tree(2*p,l,m),build_tree(2*p+1,m+1,r);
up(p);
}
inline void update(int p,int l,int r,int c) //用c更新l,r（维护每个可跳跃点的最大值）
{
if(T[p].l>r||T[p].r=l&&T[p].r<=r){ //打上懒惰标记
T[p].tag=max(T[p].tag,c);
T[p].s=T[p].tag;
return;
}
down(p);
if(T[2*p].r>=l) update(2*p,l,r,c);
if(T[2*p+1].l<=r) update(2*p+1,l,r,c);
up(p);
}
int query(int p,int k) //查询k的值
{
if(T[p].l==T[p].r) return T[p].s;
down(p); //必须做一次标记下移操作
if(T[2*p].r>=k) return query(2*p,k);
else if(T[2*p+1].l<=k) return query(2*p+1,k);
else return 0;
}
int main()
{
int n;
scanf("%d",&n);
build_tree(1,1,n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i
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]。比较一下选最小值即可。
代码：
#include
using namespace std;
int a[100010];
int main()
{
int t,n;
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
if(n==1) cout<2;i-=2){
if(a[i-1]+a[1]<2*a[2]) sum+=a[i]+a[1]+a[i-1]+a[1];
else sum+=a[1]+a[2]+a[i]+a[2];
}
if(n%2) sum+=a[3]+a[1]+a[2];
else sum+=a[2];
cout<
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次，判断合法的搭子。
代码：
#include
using namespace std;
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幺
unordered_mapmp; //牌型对应到数字
unordered_mapunmp; //数字映射到牌型
inline void init() //初始化
{
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;
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";
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;
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";
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;
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";
mp["1c"]=28,mp["2c"]=29,mp["3c"]=30,mp["4c"]=31,mp["5c"]=32,mp["6c"]=33,mp["7c"]=34;
unmp[28]="1c",unmp[29]="2c",unmp[30]="3c",unmp[31]="4c",unmp[32]="5c",unmp[33]="6c",unmp[34]="7c";
}
inline bool find(int n) //S(13幺)中找到n
{
for(int i=0;i<13;++i) if(n==S[i]) return true;
return false;
}
inline bool dfs(int s) //判断合法的搭子，搜索4次，每次除去3个搭子牌
{
if(s==4){ //边界，如果a都为0就合法了
for(int i=1;i<=34;++i) if(a[i]) return false;
return true;
}
for(int i=1;i<=34;++i)
if(a[i]){
if(a[i]>=3){
a[i]-=3; //拿掉搭子AAA
if(dfs(s+1)){
a[i]+=3; //复原
return true;
}
a[i]+=3;
}
if(i<28){
if(a[i]&&a[i+1]&&a[i+2]&&unmp[i][1]==unmp[i+1][1]&&unmp[i+1][1]==unmp[i+2][1]){
a[i]--,a[i+1]--,a[i+2]--; //拿掉ABC搭子
if(dfs(s+1)){
a[i]++,a[i+1]++,a[i+2]++; //复原
return true;
}
a[i]++,a[i+1]++,a[i+2]++;
}
}
return false;
}
return false;
}
inline void seven_pair(int &f) //七小对
{
int cnt=0,t; //cnt记录奇数个数，只能有一个奇数
for(int i=1;i<=34;++i){
if(a[i]&1) cnt++,t=i;
if(cnt>1) return;
}
b[t]=1,f=1;
}
inline void thirteen_yao(int &f) //13幺
{
for(int i=1;i<=34;++i){
if(!a[i]) continue;
if(!find(i)) return; //i不在13幺中不合法
}
int cnt=0,t;
for(int i=0;i<13;++i){
if(a[S[i]]>2||cnt>1) return; //同一个牌数等于2的个数不大于1，不能有大于2的
if(a[S[i]]==2) cnt++;
if(a[S[i]]==0) t=S[i];
}
f=1;
if(cnt==0) for(int i=0;i<13;++i) b[S[i]]=1; //如果拿到的13幺都出现了，都可以胡
else b[t]=1; //否则胡掉没出现的那个牌
}
inline void jjh(int &f) //将将胡
{
if(a[2]+a[5]+a[8]+a[11]+a[14]+a[17]+a[20]+a[23]+a[26]<13) return;
for(int i=2;i<=8;i+=3){ //胡之前判断个数
if(a[i]<4) b[i]=1;
if(a[i+9]<4) b[i+9]=1;
if(a[i+18]<4) b[i+18]=1;
}
f=1;
}
inline void pih(int &f) //屁胡
{
for(int i=1;i<=34;++i){ //枚举可能胡的牌
if(a[i]==4||b[i]) continue;
int flg=0;
a[i]++;
for(int j=1;j<=34;++j)
if(a[j]>=2){ //a[j]选做对子
a[j]-=2;
if(dfs(0)){ //判断有没有搭子结构
flg=1;
a[j]+=2;
break;
}
a[j]+=2; //还原
}
if(flg) f=1,b[i]=1;
a[i]--; //还原
}
}
int main()
{
int t;
char ch[5];
init();
scanf("%d",&t);
while(t--){
int flag=0;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(int i=0;i<13;++i) scanf("%s",ch),a[mp[ch]]++;
seven_pair(flag);
thirteen_yao(flag);
jjh(flag);
pih(flag);
if(flag){
int cnt=0;
for(int i=1;i<=34;++i) if(b[i]) cnt++;
printf("%d",cnt);
for(int i=1;i<=34;++i) if(b[i]) printf(" %s",unmp[i].c_str());
printf("\n");
}
else puts("Ohno");
}
return 0;
}
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:
#include
using namespace std;
typedef long long ll;
int main()
{
ll p,q;
vectorv;
cin>>p>>q;
while(1){
v.push_back(p/q);
if(p%q==0) break;
ll t=p;
p=q;
q=t%q;
}
cout<
K.最小整数问题
题目描述
红红最近对超大整数非常感兴趣，可是超大整数已经超过了C语言中整数的可表示范围。而蓝蓝觉得这个问题很简单，他甚至提出了一个更难的问题：给定一个超大整数，在其各位置上的数字可以打乱重新排序的情况下，能够生成许多个不同大小的超大整数。那么请问，在这些超大整数之中，最小的那个是多少？请告诉红红，这个最小的超大整数。（不可出现前导零）
输入描述:
共 T(1≤1≤100)组数据。
每组数据为一个超大整数，用十进制表示，该数的数位不超过 200 位。输入一定合法。
输出描述:
每组数据输出一行，为题意中的最小的超大整数。末尾带一个换行符。
示例1
输入：
2
13425
9876543210
输出：
12345
1023456789
_____________________________________________________________________________
思路：
签到题，sort一遍即可。如果有前导0，找到第一个非零元素，交换即可。
#include
using namespace std;
int main()
{
int t;
cin>>t;
string s;
while(t--){
cin>>s;
sort(s.begin(),s.end());
int i=0;
while(i
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)。
代码：
#include
using namespace std;
typedef long long ll;
const int mod=998244353;
ll mul(ll a,ll b,ll m) //大数相乘取模，防止溢出
{
ll res=0;
a%=m,b%=m;
for(;b;a=(a+a)%m,b>>=1) if(b&1) res=(res+a)%m;
return res;
}
ll qp(ll x,ll n,ll m) //快速幂
{
ll res=1;x%=m;
for(;n;x=mul(x,x,m),n>>=1) if(n&1) res=mul(res,x,m);
return res%m;
}
bool Miller_Robin(ll a,ll n) //robin判素
{
ll x=n-1,y;
int t=0;
while((x&1)==0) x>>=1,t++;
x=qp(a,x,n);
for(int i=1;i<=t;++i){
y=mul(x,x,n);
if(y==1&&x!=1&&x!=n-1) return true;
x=y;
}
return y!=1?true:false;
}
bool isprime(ll x)
{
if(x==2||x==3||x==7||x==61||x==24251) return true;
if(!(x&1)||!(x%3)||!(x%61)||!(x%24251)) return false;
if(x%6!=1&&x%6!=5) return false;
int a[5]={2,3,7,61,24251};
for(int i=0;i<5;++i){
if(a[i]>=x) break;
if(Miller_Robin(a[i],x)) return false;
}
return true;
}
int main()
{
int t,y;
ll x;
scanf("%d",&t);
while(t--)
{
scanf("%lld%d",&x,&y);
++x;
while(!isprime(x)) ++x;
ll ans=0;
x=11;
while(x) ans=(ans+x/y)%mod,x/=y;
printf("%lld\n",ans);
}
return 0;
}
这道题卡常数，上面代码交了10多次才AC。。。
可以加快读快写优化。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）