排位赛#13题解
2024-10-21 16:02:03
发布于：上海
排位赛 #13 题解
写在前面
难了好多！第四题提交 2 次才 AC，呜呜呜，我菜得模拟都不会了。
个人评分：红红黄黄黄绿蓝紫。
T1
年龄分为今年之前的和今年之后的，直接处理比较麻烦。不妨将出生年移到今年，相应的下一场流星的时间也要修改，即 。然后把寿命的起点移到下一场流星，也就是 。最后的答案当然就是 。注意多测。
int T;scanf("%d",&T);
while(T--){
int b,l,e;scanf("%d%d%d",&b,&l,&e);
e=(e+b)%50;
b=0;
l-=e;
if(l>=0)printf("%d\n",max(0,l/50+1));
else puts("0");
}
T2
因为这是一道不卡时间的字符串处理，所以我们可以使用 Python 解题。注意特判越界。
t=int(input())
for i in range(t):
s=input()
if s in('o','co','rco','arco','marco'): # 防止越界
print("MARCO")
elif s[0:1]=='o':
print("MARCO"+s[1:])
elif s[0:2]=='co':
print("MARCO"+s[2:])
elif s[0:3]=='rco':
print("MARCO"+s[3:])
elif s[0:4]=='arco':
print("MARCO"+s[4:])
elif s[0:5]=='marco':
print("MARCO"+s[5:])
else:
print(s)
T3
首先是无解的情况：，因为这样可以直接跳过去。
排除这种情况，我们考虑如何求出人数。发现“在每个长度 的连续区间内都有至少 个 TNT”是“至少 人可以通过”的充分必要条件，否则将不会有足够的 TNT 支撑玩家通过。因此，我们求出每一个长 的区间中 TNT 的数量，取最小值，这就是最多能成功通过 TNT 路径的玩家人数。
求数量的过程可以选择滑动窗口或前缀和，时空复杂度 。
char s[10005];
int main(){
int T;scanf("%d",&T);
while(T--){
int n,k;
scanf("%d%d%s",&n,&k,s+1);
if(n<=k){
puts("-1");
continue;
}
k++;
int cnt1=0,cnt2=0,ans=0x3f3f3f3f;
for(int i=1;i<=k;i++){
if(s[i]=='#')cnt1++;
else cnt2++;
}
ans=cnt1;
int l=1,r=k+1;
while(r<=n){
if(s[r]=='#')cnt1++;
else cnt2++;
if(s[l]=='#')cnt1--;
else cnt2--;
l++,r++;
ans=min(ans,cnt1);
}
printf("%d\n",ans);
}
return 0;
}
T4
典中典之，大模拟。。。特别坑！
我们考虑把每一个牌用一个结构体存起来。存放点数时，我们按序用 map 映射点数，方便排序。然后，我们将牌按照第一点数，第二花色的顺序排序。最后按题意由优先级高到低判断——先判断三种顺子，如果不是顺子，就在桶排序后按照点数出现次数判断牌型。大坑：五张牌相同属于 High Card（高牌），而不是其它奇奇怪怪的牌型！被坑了一次提交23333。
代码可能比较抽象，凑合着看吧。
struct pai{
int num;
string col;
};
bool cmp(pai x,pai y){
if(x.num==y.num)return x.col<y.col;
return x.num<y.num;
}
map<string,int>ctoin;
bool cmp2(int x,int y){
return x>y;
}
int main(){
ctoin["2"]=1;
ctoin["3"]=2;
ctoin["4"]=3;
ctoin["5"]=4;
ctoin["6"]=5;
ctoin["7"]=6;
ctoin["8"]=7;
ctoin["9"]=8;
ctoin["10"]=9;
ctoin["J"]=10;
ctoin["Q"]=11;
ctoin["K"]=12;
ctoin["A"]=13;
int T;cin>>T;
while(T--){
string ch,s;
pai a[10];
for(int i=1;i<=5;i++){
cin>>ch>>s;
a[i].num=ctoin[ch];
a[i].col=s;
}
sort(a+1,a+6,cmp);
#define q(i)(a[i].num)
#define w(i)(a[i].col)
if(q(1)==9&&q(2)==10&&q(3)==11&&q(4)==12&&q(5)==13&&
w(1)==w(2)&&w(2)==w(3)&&w(3)==w(4)&&w(4)==w(5)){
puts("Royal Flush");
}else if(q(2)==q(1)+1&&q(3)==q(2)+1&&q(4)==q(3)+1&&q(5)==q(4)+1&&
w(1)==w(2)&&w(2)==w(3)&&w(3)==w(4)&&w(4)==w(5)){
puts("Straight Flush");
}else if(q(2)==q(1)+1&&q(3)==q(2)+1&&q(4)==q(3)+1&&q(5)==q(4)+1){
puts("Straight");
}else{
int buc[15]={0};
buc[q(1)]++;buc[q(2)]++;buc[q(3)]++;buc[q(4)]++;buc[q(5)]++;
sort(buc+1,buc+15,cmp2);
if(buc[1]==3&&buc[2]==2)puts("Full House");
else if(buc[1]==4&&buc[2]==1)puts("Four of a Kind");
else if(buc[1]==3)puts("Three of a Kind");
else if(buc[1]==2&&buc[2]==2)puts("Two Pairs");
else if(buc[1]==2)puts("One Pair");
else puts("High Card");
}
}
return 0;
}
T5
如果 T4 是大模拟，这题就是小模拟。加一条边最多在两边各加一个小正方形，判断两边的正方形四边是不是都被加了即可。可以用简单的位运算技巧方便判断。注意分类讨论。
int vis[505][505];
int main(){
int n,m,q;scanf("%d%d%d",&n,&m,&q);
int x=0,y=0;
while(q--){
{
int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
if(a!=c){
if(a>c)swap(a,c);
// left
vis[a][b-1]|=1;
// right
vis[a][b]|=2;
if(vis[a][b-1]==15)x++;
if(vis[a][b]==15)x++;
}else{
if(b>d)swap(b,d);
// up
vis[a-1][b]|=4;
// down
vis[a][b]|=8;
if(vis[a-1][b]==15)x++;
if(vis[a][b]==15)x++;
}
}
{
int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
if(a!=c){
if(a>c)swap(a,c);
// left
vis[a][b-1]|=1;
// right
vis[a][b]|=2;
if(vis[a][b-1]==15)y++;
if(vis[a][b]==15)y++;
}else{
if(b>d)swap(b,d);
// up
vis[a-1][b]|=4;
// down
vis[a][b]|=8;
if(vis[a-1][b]==15)y++;
if(vis[a][b]==15)y++;
}
}
}
printf("%d %d\n",x,y);
return 0;
}
T6
直接看比较麻烦，因为答案似乎被两个维度所限制。但是我们观察式子：
可以直接拆开：
要使其最小，就要使加号左右最小，而两边均只关于 和 。权值 很碍眼，由于 不大，不妨把每一个 拆分成 个 。设拆分后有 对坐标，则上式可改写为：
要使加号左边最小， 应该取什么呢？由绝对值性质得：
代入 得
求和得
等号成立，当且仅当 。所以要使原式最小， 的取值范围当然就是 。
当然右边关于 也是一样的。所以代码实现很简单，时间复杂度为 。log 可以用 nth_element 求中位数去掉，当然直接排也没事。
int w[50005];
double x[50005],y[50005];
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",w+i);
double ansx=0,ansy=0;
int nn=1;
for(int i=1;i<=n;i++){
scanf("%lf%lf",x+nn,y+nn);
nn++;
for(int j=2;j<=w[i];j++){
x[nn]=x[nn-1];
y[nn]=y[nn-1];
nn++;
}
}
nn--;
sort(x+1,x+1+nn);
sort(y+1,y+1+nn);
ansx=x[(nn+1)/2],ansy=y[(nn+1)/2];
double ans=0;
for(int i=1;i<=nn;i++){
ans+=fabs(ansx-x[i])+fabs(ansy-y[i]);
}
printf("%.5lf\n",ans);
return 0;
}
T7
如果你比较熟悉 FJ，你应该对一道典题不陌生——Corn Fields，是状压 DP 的板题。而这道题类似于本题，区别在于 变大了（），模数变了，同时不可以一只乌龟都不养。看起来 变大时间复杂度不行了，但是状压作法的复杂度略低于 ， 变大的影响不大，所以还是状压板题。
设 是在第 行，当前行状态为 时的方案数，0 为不放，1 为放。我们知道不合法的方案有：行内有连续的 1，有 1 出现在养殖设备的位置。如果该行合法，我们枚举状态 。 同样需要满足上述条件，同时 与 不能有同位 1，因为行间也不能有连续的 1。如果一切都符合规则，则可以转移：。
别忘了边界条件：当 且 合法时，。
细节看注释。
int f[505][1<<11];
int a[505],st[1<<11];
#define Mod 1000000007
int main(){
int n,m;scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int x;
scanf("%d",&x);
a[i]|=(!x)<<j; // 取反存数组
}
}
for(int i=0;i<1<<m;i++){
if(i&(i<<1))st[i]=1; // 每行二进制中不可以有两个连续的 1
}
for(int i=0;i<n;i++){
for(int j=0;j<1<<m;j++){
if(j&a[i]||st[j])continue; // 每行二进制中不可以有两个连续的 1，并且每一位都要是水池
if(i!=0)for(int k=0;k<1<<m;k++){
if(j&k||st[k])continue; // 每行每列二进制中不可以有两个连续的 1
f[i][j]=(f[i][j]+f[i-1][k])%Mod; // 转移
}else f[i][j]=1; // 初始化
}
}
int ans=0;
for(int i=0;i<1<<m;i++)ans=(ans+f[n-1][i])%Mod; // 统计答案
if(ans==0)puts("0"); // 输出的一些小细节，自行理解
else printf("%d\n",max(0,((ans-1)%Mod+Mod)%Mod));
return 0;
}
T8
一道毒瘤的数据结构题。（数据结构题！）
数据范围是 ，暴力显然不行，可以考虑 的分块作法或者 的线段树作法。如果您很强，那么还有可能用一堆树状数组以优雅的小常数完成此题，不过我不会。这里用线段树作法。
首先是线段树的每个节点要存什么。显而易见的是加法懒标记和区间立方和的值。除此之外，由于高次和需要低次和推导而来，所以我们需要再维护区间平方和与区间和的值。
struct node{int l,r;ll sum1/*和*/,sum2/*平方和*/,sum3/*立方和*/,tag;}t[4*MAXN+5];
然后是线段树的核心——懒标记下传。
设当前区间的长度为 ，加法标记的值为 ， 分别是修改前的 次方和， 分别是修改后的 次方和。
从最简单的说起：区间和当然增加了 ，也就是 。
然后是平方和：
最后是立方和：
(t[s(p)].sum3+=3*x*t[s(p)].sum2%Mod+3*x*x%Mod*t[s(p)].sum1%Mod+len*x%Mod*x%Mod*x%Mod)%=Mod;
(t[s(p)].sum2+=2*x*t[s(p)].sum1+len*x%Mod*x)%=Mod;
(t[s(p)].sum1+=x*len)%=Mod;
(t[s(p)].tag+=t[p].tag)%=Mod;
代码实现时，不要忘记上传节点信息的时候三种区间信息都要更新。为了防止负数出现，我们在输入的时候把所有负数取模成正数即可。
完整代码（稍有压行）。
#define MAXN 100000
#define Mod 1000000007
#define m(l,r) ((l+r)>>1)
#define ls(k) (k<<1)
#define rs(k) ((k<<1)|1)
struct node{int l,r;ll sum1,sum2,sum3,tag;}t[4*MAXN+5];
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r)return;
int mid=m(l,r);
build(ls(p),l,mid);
build(rs(p),mid+1,r);
}
void down(int p){
if(t[p].tag){
ll x=t[p].tag;
int lenl=t[ls(p)].r-t[ls(p)].l+1;
int lenr=t[rs(p)].r-t[rs(p)].l+1;
#define len lenl
#define s ls
(t[s(p)].sum3+=3*x*t[s(p)].sum2%Mod+3*x*x%Mod*t[s(p)].sum1%Mod+len*x%Mod*x%Mod*x%Mod)%=Mod;
(t[s(p)].sum2+=2*x*t[s(p)].sum1+len*x%Mod*x)%=Mod;
(t[s(p)].sum1+=x*len)%=Mod;
(t[s(p)].tag+=t[p].tag)%=Mod;
#undef len
#undef s
#define len lenr
#define s rs
(t[s(p)].sum3+=3*x*t[s(p)].sum2%Mod+3*x*x%Mod*t[s(p)].sum1%Mod+len*x%Mod*x%Mod*x%Mod)%=Mod;
(t[s(p)].sum2+=2*x*t[s(p)].sum1+len*x%Mod*x)%=Mod;
(t[s(p)].sum1+=x*len)%=Mod;
(t[s(p)].tag+=t[p].tag)%=Mod;
#undef len
#undef s
t[p].tag=0;
}
}
void change(int p,int x,int y,int z){
if(x<=t[p].l && y>=t[p].r){
int len=(t[p].r-t[p].l+1);
ll x=z;
(t[p].sum3+=3*x*t[p].sum2%Mod+3*x*x%Mod*t[p].sum1%Mod+len*x%Mod*x%Mod*x%Mod)%=Mod;
(t[p].sum2+=2*x*t[p].sum1+len*x%Mod*x)%=Mod;
(t[p].sum1+=x*len)%=Mod;
(t[p].tag+=z)%=Mod;
return;
}
down(p);
int mid=m(t[p].l,t[p].r);
if(x<=mid) change(ls(p),x,y,z);if(y>mid) change(rs(p),x,y,z);
(t[p].sum1=t[ls(p)].sum1+t[rs(p)].sum1)%=Mod; (t[p].sum2=t[ls(p)].sum2+t[rs(p)].sum2)%=Mod; (t[p].sum3=t[ls(p)].sum3+t[rs(p)].sum3)%=Mod;
}
int ask(int p,int x,int y){
if(x<=t[p].l && y>=t[p].r) return t[p].sum3;
down(p);
int mid=m(t[p].l,t[p].r);
int ans=0;
if(x<=mid) ans+=ask(ls(p),x,y);
if(y>mid) ans+=ask(rs(p),x,y);
ans%=Mod;
return ans;
}
int main(){
int n,m;scanf("%d%d",&n,&m);
build(1,1,n);
for(int i=1;i<=n;i++){int x;scanf("%d",&x);change(1,i,i,(x%Mod+Mod)%Mod);}
while(m--){
int op,l,r,k;scanf("%d%d%d",&op,&l,&r);
if(op==1){scanf("%d",&k);k=(k%Mod+Mod)%Mod;change(1,l,r,k);}
else printf("%d\n",ask(1,l,r));
}
return 0;
}
尾
祝大家 CSP-J2/S2 rp++！
unsigned long long rp=0;
rp--;
有帮助，赞一个