排位赛#13题解

leo120306

2024-10-21 16:02:03

发布于：上海

265阅读

0回复

0点赞

排位赛 #13 题解

写在前面

难了好多！~~第四题提交 2 次才 AC，呜呜呜，我菜得模拟都不会了。~~

个人评分：红红黄黄黄绿蓝紫。

T1

年龄分为今年之前的和今年之后的，直接处理比较麻烦。不妨将出生年移到今年，相应的下一场流星的时间也要修改，即 $E\gets(E+B)\bmod 50,B\gets 0$ 。然后把寿命的起点移到下一场流星，也就是 $L\gets L-E,E\gets 0$ 。最后的答案当然就是 $\max\{0,\lfloor\frac l{50}\rfloor+1\}$ 。注意多测。

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

首先是无解的情况： $N\leq K$ ，因为这样可以直接跳过去。

排除这种情况，我们考虑如何求出人数。发现“在每个长度 $K+1$ 的连续区间内都有至少 $P$ 个 TNT”是“至少 $P$ 人可以通过”的充分必要条件，否则将不会有足够的 TNT 支撑玩家通过。因此，我们求出每一个长 $K+1$ 的区间中 TNT 的数量，取最小值，这就是最多能成功通过 TNT 路径的玩家人数。

求数量的过程可以选择滑动窗口或前缀和，时空复杂度 $\Theta(n)$ 。

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

直接看比较麻烦，因为答案似乎被两个维度所限制。但是我们观察式子：

$\sum_{i=1}^n((\left|x_i-x\right|+\left|y_i-y\right|)\times\epsilon_i)$

可以直接拆开：

$\left(\sum_{i=1}^n(\left|x_i-x\right|\times\epsilon_i)\right)+\left(\sum_{i=1}^n(\left|y_i-y\right|\times\epsilon_i)\right)$

要使其最小，就要使加号左右最小，而两边均只关于 $x$ 和 $y$ 。权值 $\epsilon_i$ 很碍眼，由于 $\epsilon_i$ 不大，不妨把每一个 $(x_i,y_i,\epsilon_i)$ 拆分成 $\epsilon_i$ 个 $(x_i,y_i)$ 。设拆分后有 $m$ 对坐标，则上式可改写为：

$\left(\sum_{i=1}^m\left|x_i-x\right|\right)+\left(\sum_{i=1}^m\left|y_i-y\right|\right)$

要使加号左边最小， $x$ 应该取什么呢？由绝对值性质得：

$\left|x-x_i\right|+\left|x-x_{n-i+1}\right|\geq\left|x_i-x_{m-i+1}\right|$

代入 $i=1,2,\cdots,n$ 得

$\begin{cases} \left|x-x_1\right|+\left|x-x_m\right|&\geq\left|x_1-x_m\right|\\ \left|x-x_2\right|+\left|x-x_{m-1}\right|&\geq\left|x_2-x_{m-1}\right|\\ \vdots\\ \left|x-x_m\right|+\left|x-x_1\right|&\geq\left|x_m-x_1\right| \end{cases}$

求和得

$2\sum_{i=1}^m\left|x-x_i\right|\geq\sum_{i=1}^m\left|x_i-x_{m-i+1}\right|$

等号成立，当且仅当 $x_{\lfloor m/2\rfloor}\leq x\leq x_{\lceil m/2\rceil}$ 。所以要使原式最小， $x$ 的取值范围当然就是 $x_{\lfloor m/2\rfloor}\leq x\leq x_{\lceil m/2\rceil}$ 。

当然右边关于 $y$ 也是一样的。所以代码实现很简单，时间复杂度为 $\Theta((\sum\epsilon_i)\log(\sum\epsilon_i))$ 。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 的板题。而这道题类似于本题，区别在于 $N$ 变大了（ $12\to 500$ ），模数变了，同时不可以一只乌龟都不养。看起来 $N$ 变大时间复杂度不行了，但是状压作法的复杂度略低于 $O(n2^{2m})$ ， $n$ 变大的影响不大，所以还是状压板题。

设 $f_{i,j}$ 是在第 $i$ 行，当前行状态为 $j$ 时的方案数，0 为不放，1 为放。我们知道不合法的方案有：行内有连续的 1，有 1 出现在养殖设备的位置。如果该行合法，我们枚举状态 $k$ 。 $k$ 同样需要满足上述条件，同时 $k$ 与 $j$ 不能有同位 1，因为行间也不能有连续的 1。如果一切都符合规则，则可以转移： $f_{i,j}\gets f_{i,j}+f_{i-1,k}$ 。

别忘了边界条件：当 $i=0$ 且 $j$ 合法时， $f_{i,j}=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

一道毒瘤的数据结构题。（数据结构题！）

数据范围是 $10^5$ ，暴力显然不行，可以考虑 $m\sqrt n$ 的分块作法或者 $m\log n$ 的线段树作法。如果您很强，那么还有可能用一堆树状数组以优雅的小常数完成此题，不过我不会。这里用线段树作法。

首先是线段树的每个节点要存什么。显而易见的是加法懒标记和区间立方和的值。除此之外，由于高次和需要低次和推导而来，所以我们需要再维护区间平方和与区间和的值。

struct node{int l,r;ll sum1/*和*/,sum2/*平方和*/,sum3/*立方和*/,tag;}t[4*MAXN+5];

然后是线段树的核心——懒标记下传。

设当前区间的长度为 $l$ ，加法标记的值为 $x$ ， $s_1,s_2,s_3$ 分别是修改前的 $1,2,3$ 次方和， $s_1^\prime,s_2^\prime,s_3^\prime$ 分别是修改后的 $1,2,3$ 次方和。

从最简单的说起：区间和当然增加了 $lx$ ，也就是 $s_1^\prime\gets s_1+lx$ 。

然后是平方和：

$\begin{aligned} s_2^\prime&=\sum(a_i+x)^2\\ &=\sum(a_i)^2+2x\sum a_i+\sum x^2\\ &=s_2+2xs_1+lx^2\end{aligned}$

最后是立方和：

$\begin{aligned} s_3^\prime&=\sum(a_i+x)^3\\ &=\sum(a_i)^3+3x\sum(a_i)^2+3x^2\sum a_i+\sum x^3\\ &=s_3+3xs_2+3x^2s_1+lx^2\end{aligned}$

(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--;

有帮助，赞一个

去预览

0/2000

全部评论 8

leo120306
如果觉得好可否点个赞~

2024-10-08 来自上海
3
- key0213
  回复leo120306
  贺榜一！
  
  2024-10-08 来自福建
  1
- leo120306
  回复key0213
  谢谢！
  
  2024-10-08 来自上海
  0
- key0213
  回复leo120306
  秒回
  
  2024-10-08 来自福建
  0
Macw07
太牛了，点赞！

2024-10-08 来自加拿大
2
cjdstttttt
顶

2024-10-10 来自广东
0
cjdstttttt
顶

2024-10-09 来自广东
0
leo120306
顶

2024-10-09 来自上海
0
XXX
第一！！！

2024-10-09 来自天津
0
你好
看完后直接爽了

2024-10-08 来自广东
0
你好
顶

2024-10-08 来自广东
0

排位赛 #13 题解

写在前面

T1

T2

T3

T4

T5

T6

T7

T8

尾

全部评论 8

热门讨论