比赛链接

2022—SWJTU寒假选拔赛第一场

题目列表

| | Stat | # | Title | | :-----| ----: | :----: | :-------: | | Solved | 21/90| A | 惠老板观星 | | Solved | 26/54 | B | Asuka大战兔子 | | Attempted | 2/44 | C |我不会debug| | Solved | 39/51 | D| 我要吃饭| | |2/6 | E |删删删| | Solved |12/27| F |大水题| | |0/17 |G| 你一定会种树吧| | Attempted |3 / 17| H |货车| | |9/28 |I|超级打字大师| | |1/3 |J |简单数学| | Attempted |5/23 |K |小游戏| | Solved |36/72| L |cold玩真人cs| | | |M |杰哥打怪|

A-惠老板观星

题目搬运

题目描述

惠老板最近迷上了星空摄影，为了更好的出片，惠老板需要在山地中找到四个位置。从空中看，这四个位置必须是一个正方形的四个顶点。在惠老板的理论中这四个点必须有三个点的高度相同。而另外一个点的高度要高于这三个点。惠老板去了蒙德的龙脊雪山。对于惠老板来说龙脊雪山可以看成由n*n个小平台组成的地区。每个平台都有其独立的整数高度。现在他想找出高度相同的三个观测点中最高的观测位置的高度。

输入格式

第一行一个整数表示$n*n$的矩阵, $2<=n<=3002<=n<=300$

接下来n行每行个数表示当前位置的高度。$1<=ht[i,j]<=10^9 1<=ht[i,j]<=10^9$

输出格式

一个整数表示能找的的最高的观测位置（注意你需要输出的是那三个高度相同的点的高度而不是第四个最高顶点的高度）。若没有符合条件的观测位置则输出-1.

样例

Input	Output
`3 2 2 3 2 2 2 3 2 3`	`2`

Input	Output
`3 2 2 2 2 2 2 1 2 1`	`-1`

B-Asuka大战兔子

题目搬运

题目描述

Asuka养了在他的农场养了许多兔子，他的农场由无数个方格构成的，农场行数为x,列数为y。现在Asuka的农场中有许多兔子还有许多萝卜。兔子能够不断向上下左右四个方向移动从而到达农场各个位置，若移动之后的放个有萝卜那么兔子可以将其吃掉。注意，兔子不能移动到已经有兔子的方格中。若兔子的上下左右四块田地中有萝卜，那么它也能够吃到。Asuka为了阻止他的兔子吃萝卜，他决定用围栏将将农场中的兔子和萝卜分开。他有足够多的围栏，但是围栏只能建造在空田地中。 Auska想问你他能不能将所有的兔子和萝卜都分开。如果能请输出任意一种方案。否则输出No.

Asuka有非常的多的栅栏，你可以不输出使用最少栅栏的方案。

输入格式

第一行两个整数x和y表示农场的行数和列数，1<=x,y<=5001<=x,y<=500。接下来是一个x*y的字符串C表示萝卜R表示兔子。而空田地表示为"."。

输出格式

若可以将所有兔子和围栏分开则第一行输出“Yes”接下来输出任意一种方案。栅栏用"#"表示。空田地表示为"."。否则输出No.

样例

Input	Output
`4 5 .C.RR C..RR .C..R .....`	`Yes .C#RR C.#RR .C#.R ..#..`

C-我不会debug

题目搬运

题目描述

cold正在进行c语言考试，他提交程序之后，老师会告诉cold他对于每个测试点的结果是正确的（P）还是错误的（F），他将会得到一个只由P和F组成的字符串。他想让你帮他调试程序，你可以花一分钟删除首个或者最后一个字母，或者花两分钟删除字符串中间任何一个字母，删除之后将剩下的两端拼接起来。现在，他想问你将该字符串变成一个只存在P的字符串需要多少时间。

输入格式

第一行一个整数n，表示字符串长度$(1<=n<=10^6)(1<=n<=10^6)$

第二行一个由P和F组成的字符串。

输出格式

一个整数，你调试程序所需要的最小时间。

样例

Input	Output
`6 FPPFPP`	`3`

D-我要吃饭

题目搬运

题目描述

dki在考完cet—6之后非常愤怒，表示自己啥也不会，并且这次分数大概率比上次random的还低，他准备点一顿外卖来犒劳自己。

他打开某团，有七种菜品可以选择，价格分别是7,27,41,49,63,78,108元。

dki有三张满减券，分别是：

1、当总价达到69元可减15元。

2、当总价达到89元可减30元。

3、当总价达到120元可减50元。

但是dki只能使用一张优惠券。当他先但是系统自动为他选择了最优的优惠券。例如他总过点了400元的晚餐，他总共需要付350元。

dki总共点了n个菜，每个菜的单价分别为a1,a2,a3...an。他想知道他总共需要付多少钱。

输入格式

本题包含多组测试样例

第一行一个整数t, 表示有t组测试样例。$1<=t<=10^61<=t<=10^6$

对于每组测试样例

第一行一个整数n表示总共点了n个菜$1<=t<=10^61<=t<=10^6$。

输出格式

对于每组测试样例输出一个数字，表示dki所需要支付的总价

样例

Input	Output
`5 2 1 2 3 3 4 2 6 1 3 1 2 1 3 1 1 7 1 1 4 5 1 4 1`	`34 87 80 7 139`

E-删删删

题目搬运

题目描述

给你一颗有n个结点的树，你可以删除这个树上任意数量的结点，如果在树的剩余每个结点部分仍然有至少一个结点与它相连，那么我们边成这种删除方式是漂亮的。Hertz想问你总共有多少种删除方式是美丽的。由于方案可能非常多，他希望你再计算的时候对998244353取模。

如果删除的结点集合相同，那么认为是相同的方式。

输入格式

本题含有多组测试样例，第一行输入一个整数t，表示总共有t组测试样例。

对于每组测试样例

第一行一个整数n，1<=t<=10^51<=t<=10 5

接下来n-1行，每行两个整数 x,y $(1≤x,y≤n,x≠y)(1≤x,y≤n,x≠y)$。表示x和y之间有一条边。

数据保证$∑n≤10^6∑n≤10^6$

输出格式

共有t行每行一个整数。

样例

Input	Output
`1 7 1 2 4 2 1 3 3 6 1 7 5 2`	`37`

F-大水题

题目搬运

题目描述

vc++最近在玩简单的数学题，他想给你分享一道简单的数学题.

一个数等于他所有真因子之和那么我们可以称指为完美数，例如$1+2+4+7+14=28$，$1+2+4+8+16+31+62+124+248=496$。

vc++觉得这不好玩，所以他自己创造一个半完美数的定义，令 S 为自然数 X 的所有真因子的集合。如果存在 S 的子集，使得子集中的数字之和等于数字本身，则称该数字是半完美的。

显然，所有完美数都是半完美数。此外，还有一些不完美的数字，它们也属于金成的半完美数字。例如，24的真实因子集是${1,2,3,4,6,8,12}$，我们可以选择一个子集${2,4,6,12}$，满足$24=2+4+6+12$。所以24可以称为半完美数。

vc++想知道他是否能找到一个整数 k，它是正整数 x 的倍数，使得 k 是一个半完美数。

由于 vc++不擅长数学，他希望 k 不能太大$（k≤2×10^{18}）（k≤2×10^18 ）$，并且子集的大小不大于 1000。他希望你给你选择的子集。

输入格式

本题含有多组测试样例，第一行输入一个整数t，表示总共有t组测试样例。$1<=t<=40001<=t<=4000$.

接下来t行每行一个正整数x，$ 1<=x<=10^91<=x<=109$

输出格式

总共2t行

每组第一行输出两个正整数k和l，k为你所找到的整数$(k<=10^{18})(k<=10^18)$，l为你所选择的子集的大小$(l<=1000)(l<=1000)$。

第二行输出你所选择的子集中的所有元素。

样例

Input	Output
`2 10 2`	`60 3 10 20 30 24 4 2 4 6 12`

G-你一定会种树吧

题目搬运

题目描述

cyh有一个长度为n的可操作序列a1,a2,a3,.......an。现在他可以对序列进行如下操作

1、 1 l r 对区间[l,r]的所有数加上$lowbit(a[i])$

2、2 l r 询问区间[l,r]中的和。

cyh需要你给出每次询问值对998244353取模的结果。

输入格式

第一行一个整数t, 1<=t<=201<=t<=20, 表示有t组测试样例。

对于每组测试样例，第一行一个整数n,1<=n<=10^51<=n<=10 5 ,表示序列的长度。

接下来一行有有n个整数，表示该序列。

第三行一个整数m，表示需要进行操作的数量。$ (1≤m≤10^{5)(1≤m≤10}5)$

接下来m行，每行三个正整数x, l, r. x代表操作类型，l，r代表操作的区间。$1<=x<=2,1<=l,r<=n1<=x<=2,1<=l,r<=n$

输出格式

对于每次询问输出对998244353取模的结果

样例

Input	Output
`1 5 5 5 5 5 5 5 2 2 4 2 2 5 1 1 2 1 2 5 2 4 5`	`15 20 12`

H-货车

题目搬运

题目描述

有nn个城市被mm条路连接，每条路都有一个最大承重能力kk，如果货车总重量pp大于kk，则货车不能通过该条路。

如果一辆货车能从城市xx一直开到yy，则称城市x,yx,y对于该货车而言是“互通的”。

现在每次询问给定一个数pp表示货车总重量，请问有多少对城市对于这辆货车是“互通的”？

输入格式

$T(1≤T≤10)$组样例。

每组样例第一行包含三个整数$n,m,q(2\le n\le 1e5,1\le m\le 2e5,1\le q\le 2e5)n,m,q(2≤n≤1e5,1≤m≤2e5,1≤q≤2e5)$分别表示城市的数量，路的数量，以及询问的数量。

然后是mm行，每行包含三个整数$x,y,k(1\le x,y\le n,1\le k\le 1e9)x,y,k(1≤x,y≤n,1≤k≤1e9)$表示城市x,yx,y之间有一条直接相连的路，最大承重能力为kk。

最后qq行，每行一个整数$p(1\le p\le 1e9)p(1≤p≤1e9)$表示货车总重量。

输出格式

每组样例输出qq行，每行包含一个整数，表示询问答案。

样例

Input	Output
`1 5 5 4 1 2 2 3 2 2 4 3 2 4 5 4 1 5 3 3 2 1 4`	`3 10 10 1`

最开始用了个dfs，然后超时？之后才明白是（最小生成树）建边并查集，离线。

改了好久还是没调出来。

I-超级打字大师

题目搬运

题目描述

众所周知，双拼是一种非常高效的打字手段,因为使用双拼，您只需按两次键即可输入任何中文单词。

表
拼音	双拼	拼音	双拼
q, iu	q	f, en	f
w, ei	w	g, eng	g
r, uan	r	j, an	j
e	e	h, ang	h
t, ue	t	k, uai, ing	k
y, un	y	l, uang, iang	l
u, sh	u	z, ou	z
i, ch	i	x, ia, ua	x
o, uo	o	c, ao	c
p, ie	p	v, zh, ui	v
a	a	b, in	b
d, ai	d	m, ian	m
s, ong, iong	s	n, iao	n

$ColdCold$最近在研究双拼打字 ,现在想请你帮忙将给定的句子以双拼的方式输出。比如说, "ni hao shi jie"那么你需要输出的是,"ni hc ui jp"。

Tips:

对于长度为 11 的拼音,为了满足双拼的语法要求,你应该输出两个相同的该字符。
对于长度为 22 的拼音,不作改动,直接输出该拼音
对于像 angang 这样的拼音如果独立出现,你应该先输出他的第一个字母,然后在表-格中查找整个拼音以获得第二个键ex. ("ang" 会变成"ah")。而rang则会输出rh
为简化起见，任何输入中都没有字符 vv

输入格式

有多个测试用例。每行包含一个。数据保证测试用例个数不超过10001000个，

每一行都是由空格分隔的拼音序列。

数据保证测试用例个数不超过10001000个，一个测试用例的拼音个数不超过 500500 个，所有测试用例的拼音个数不超过 50005000 个。

输出格式

由空格分隔的双拼序列。

样例

Input	Output
`ji zhe ti mian shen me wan yi beng bu zhu le yuan lai ni ye wan yuan shen`	`ji ve ti mm uf me wj yi bg bu vu le yr ld ni ye wj yr uf`

J-简单数学

题目搬运

题目描述

郑老板非常喜欢数学题，今天他给了你下面一个方程。 \[ f(n) = \begin{cases} 1, & n \in \{1\} \bigcup \operatorname{质数} \\ p\,f(p^{k-2}), & n = p^k ~ (p \in \operatorname{质数}; ~ k > 1) \\ f(p_1^{e_1})\prod_{i=2}^r {p_i}^{e_i}, & n = \prod_{i=1}^r {p_i} ^ {e_i} ~ (p_1 < p_2 < \cdots < p_r; ~ p_i \in \operatorname{质数}; ~ r \ge 2) \end{cases} \]

现在郑老板想问你$\sum_{i=1}^n f(i)$的结果，你能告诉他吗？

输入格式

一行一个正整数n $(1 \le n \le {10}^{7})n (1≤n≤10^7)$.

输出格式

一个正整数，代表结果。

样例

Input	Output
`50`	`370`

Node

对于第一个样例, $f(1) = 1f(1)=1, f(2) = 1f(2)=1, f(3) = 1f(3)=1, f(4) = 2f(4)=2, f(5) = 1f(5)=1, f(6) = 3f(6)=3, f(7) = 1f(7)=1, f(8) = 2f(8)=2, f(9) = 3f(9)=3, f(10) = 5f(10)=5$.

题目保证答案小于 2^{64}-12 64 −1.

K-小游戏

题目搬运

题目描述

dqhl76最近在玩一个游戏，他会给你一个长度为n的序列，序列中的元素为ai。他需要你对序列中的元素进行n-1次合并操作，每次合并操作你可以选择序列中的了两个相邻的元素，将a[x]和a[x+1]合并成一个元素值为$(a[x]*a[x+1])mod1000003$并且得到$(a[x]-a[x+1])^2$分。你将一直持续这个游戏，知道序列只剩下一个元素为止。

现在dqhl76想问你你能获得的最大积分是多少。

输入格式

第一行一个整数n表示序列的长度$1<=n<=3001<=n<=300$

T接下来一行n个整数，$a[1],a[2],a[3]....a[n]1<=ai<=10^61<=ai<=10^6$

输出格式

一个整数，表示你能达到的最大积分。

样例

Input	Output
`4 1 2 3 4`	`630`

一道本应该AC的题目。

错误原因是 w 忘了开 LL 。最重要的又看错了题，得分结果不用取 MOD ，只对 a[i][j] 的合并结果取 MOD！！！

#include<bits/stdc++.h>
using namespace std;
#define ll long long

inline ll read(){
    ll sum=0,flag=1;char c;
    for(;c>'9'||c<'0';c=getchar()) if(c=='-') flag=-1;
    for(;c<='9'&&c>='0';c=getchar()) sum=(sum<<3)+(sum<<1)+c-'0';
    return flag*sum;
}


#define FOR(i,a,b) for(int i=(a);i<=(b);i++)


ll a[330][330];
ll dp[330][330];

int main(){
    int n=read();

    FOR(i,1,n){
        a[i][i]=read();
    }
    FOR(k,1,n-1){ 
        FOR(i,1,n-k){//i - i+k
            FOR(j,0,k-1){
                ll w=(dp[i][i+j]+dp[i+j+1][i+k]+(a[i][i+j]-a[i+j+1][i+k])*(a[i][i+j]-a[i+j+1][i+k])); // 错误1
                if(dp[i][i+k]<=w){
                    dp[i][i+k]=w; //%MOD 错误2
                    a[i][i+k]=(a[i][i+j]*a[i+j+1][i+k])%1000003;
                }
            }
        }
    }
    cout<<dp[1][n]; //%MOD 错误2
}

L-cold玩真人cs

题目搬运

题目描述

cold最近迷上了射击游戏。在游戏中cold是一名狙击手。对于cold来说他有一个射击范围。在这个范围内的敌人它可以一发毙命。而在这个范围之外的敌人他需要两发。例如cold的射击范围是[30,90]，他每一次射击都能消灭一个在这个距离范围内的敌人。而不在这个距离之中的敌人,例如位置在95那么他则需要两发子弹。

现在cold倍困在山顶，有n个敌人围住了他，cold的枪里有m发子弹，并且cold知道每个敌人离他的距离。

输入格式

第一行四个整数n,m,s,f。分别表示n个敌人，m发子弹，cold能对[s,f]范围内的敌人一发毙命。$1≤n≤1,000,000; 1≤m≤1,000,000,000; 1≤s≤f≤1,000,000,0001≤n≤1,000,000;1≤m≤1,000,000,000;1≤s≤f≤1,000,000,000$

第二行n个整数，表示每个敌人距cold的距离。

输出格式

若cold能杀死全部的敌人则输出lzdak!否则输出cold能杀死敌人的数量。

样例

Input	Output
`2 10 1 10 2 9`	`lzdak!`

M-杰哥打怪

题目搬运

题目描述

现在森林中有 nn 个村庄，住着猎人与怪兽，有 mm 条路连接这些村庄且经过每条路都需要花费时间 11 。

第ii 个村庄的怪兽的防御力为$w_i$，当猎人的攻击力大于等于怪兽的防御力时，猎人能够猎杀到这个村庄的怪兽。

现在有qq次询问，每次询问包含两个整数分别为$a_i,p_ia$第$a_i$个村庄攻击力$p_i$的猎人要去打猎（可以打自家村庄的怪兽），请问猎人最少花费多少时间能打到怪兽？

每次询问时独立的，你只需要打到一个怪兽

输入格式

第一行给定三个整数 $n,m,q(1\le n,m\le 1e5,1\le q\le 5e5)n,m,q(1≤n,m≤1e5,1≤q≤5e5)$ 分别表示村庄，路以及询问的数量。

第二行nn个整数，期中第ii个整数表示第ii个村庄怪兽的防御力为$w_i(1\le w_i\le 1e2)$

接下来mm行，每行包含两个整数$u_i,v_i(1\le u_i,v_i\le n,u_i\not=v_i)$ 表示村庄$u_i,v_i$之间有一条路。

最后qq行，每行包含两个整数$p_i,a_i(1\le p_i\le n,1\le a_i\le 1e2)$表示第$p_i$个村庄攻击力为$a_i$的猎人要去打怪兽。

输出格式

每组样例输出qq行，每行包含一个整数，表示询问答案。如果无法打到怪兽则输出-1

样例

Input	Output
`4 4 5 5 2 4 3 1 2 2 3 3 4 4 1 1 5 1 4 1 3 1 2 1 1`	`0 1 1 1 -1`

一道简单的 BFS ，但是没来得及了。

ACM

日志 C++

模糊综合评价上一篇

2021年鉴 - 山河下一篇

2022—SWJTU寒假选拔赛第一场复盘

比赛链接

题目列表

A-惠老板观星

B-Asuka大战兔子

C-我不会debug

D-我要吃饭

E-删删删

F-大水题

G-你一定会种树吧

H-货车

I-超级打字大师

J-简单数学

Node

K-小游戏

L-cold玩真人cs

M-杰哥打怪