Before Read
Solve 4 of 7 Rank:1120 Rating Change:+29 1735 → 1764 Contest Link
A. Two Rabbits
Describe
两只可爱的兔子分别从$x,y$出发，相向而行，其中，左边的兔子一次跳$a$个单位，右边的兔子一次跳$b$个单位，数据保证$x<y$。 现有$t(0 \leq t\leq 1000)$组，保证$(0\leq x< y \leq {10}^9 ,1\leq a ,b\leq {10}^9)$。 问每组兔子是否能相遇（都跳$ans$次使其在同一点），若可以输出$ans$否则输出$-1$。
Solution
Codeforces的A题一般都是比较简单的qwq 这就是大名鼎鼎的小学相遇问题。 那么直接路程差除以速度和是否是整数即可。
Code
（请忽略窝比赛时随手定义的变量名qwq）
1
2
3
4
5
6
7
8
9
10
11
12
13
| int T,x,y,a,b;
signed main(){
T=I.read();
while(T
x=I.read();y=I.read();a=I.read();b=I.read();
int sb=y-x,nc=b+a;
if(sb%nc==0){
I.write(sb/nc);putchar('\n');
} else{
puts("-1");
}
}
}
|
B. Longest Palindrome
Describe
有$n(1\leq n\leq 100)$个字符串，每个字符串长度均为$m(1\leq m \leq 50)$，你可以选取其中的几个字符串，任意顺序组合，使其为一个回文字符串，输出最长的字符串长度与这个字符串。
Solution
由于所有字符串的长度均为$m$，所以要将两两互相回文的字符串组合即可，比如说样例1（这个bat蝙蝠是不是预示着什么…）
我们可以$O(N^2 \times M)$的求出两个字符串是否互相回文，比如说$\texttt{tab}$与$\texttt{bat}$互相回文。 那么我们可以将其组合起来。 设我们已经组合出来了$s_i,t_i$是互相回文的，那么答案就是$s_1,s_2,s_3…s_k,t_k,t_{k-1},t_{k-2}…t_1$。 当然这种方法是不完美的。 比如说这个数据：
那么显然$xxx$可以放在中间。 所以我们在最后特判一下即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| int n,m,dp[110][110],vis[110],ans;//dp[i][j]表示i与j两个字符串是否互相回文,vis[i]表示i是否使用
char a[110][60],stk[110],sbk[110],cnt;//stk,sbk均为输出使用
int kkk[110],tot;//kkk表示可以放在中间的串
signed main(){
n=I.read();m=I.read();
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
int ff=0;
for(int k=0;k<m;k++){
if(a[i][k]==a[j][m-k-1]){
//ff=0;
}else ff=1;
}
dp[i][j]=(ff==0);
}
}
for(int i=1;i<=n;i++){
int ff=0;
for(int j=0;j<m/2;j++){
if(a[i][j]==a[i][m-j-1]) ;
else ff=1;
}
if(ff==0){
++tot;
kkk[tot]=i;
}
}
// cout<<tot<<endl;
for(int i=1;i<=n;i++){
if(vis[i]==0){
for(int j=i+1;j<=n;j++){
if(vis[j]==0&&dp[i][j]==1){
vis[i]=vis[j]=1;
ans+=2;
stk[++cnt]=i;
sbk[cnt]=j;
break;
}
}
}
}
int sss=-1;
for(int i=1;i<=tot;i++){
if(vis[kkk[i]]==0){
sss=kkk[i];
ans++;
break ;
}
}
ans*=m;//别忘记乘上长度
I.write(ans);putchar('\n');
for(int i=1;i<=cnt;i++){
for(int j=0;j<m;j++){
cout<<a[stk[i]][j];
}
}
if(sss==-1 ) ;
else{
for(int i=0;i<m;i++) {
cout<<a[sss][i];
}
}
for(int i=cnt;i>=1;i--){
for(int j=0;j<m;j++){
cout<<a[sbk[i]][j];
}
}
cout<<endl;
}
|
C. Air Conditioner
Describe
餐厅里有个空调，在任意一个时刻，空调可以关（温度不变），加热（温度$+1$），降温（温度$-1$）。 给出$n(1\leq n\leq 100)$个限制，在$t(1\leq t\leq {10}^9)$时，温度要在$[l,r](-{10}^9 \leq l \leq r \leq {10}^9)$区间之内。 一开始时间为$0$，温度为$m(-{10}^9\leq m \leq {10}^9)$，问能否满足全部限制。 总共$q(1\leq q\leq 500)$组数据。
Solution
显然可以用区间乱搞。 设$L,R$表示当前可以到达的温度区间。 一开始$L=R=m$。 那么在接下来的时间可以到达$[L-(t_i-t_{i-1}),R-(t_i-t_{i-1})]$内任意一个温度，只要判断是否与$[l_i,r_i]$有相交即可。别忘记最后要更新区间呦~
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| int q,n,m,dp[110],nowt,L,R;
struct node{
int t,l,r;
}a[110];
inline int cmp(node x,node y){
return x.t<y.t;
}
signed main(){
q=I.read();
while(q--){
n=I.read();m=I.read();
for(int i=1;i<=n;i++){
a[i].t=I.read(),a[i].l=I.read(),a[i].r=I.read();
}
sort(a+1,a+n+1,cmp);
re int now=m;nowt=0;L=m;R=m;
int ff=1;
for(int i=1;i<=n;i++){
L-=a[i].t-nowt;
R+=a[i].t-nowt;
nowt=a[i].t;
if(a[i].l<=RL<=a[i].r) ;
else{
ff=0;
break ;
}
L=max(L,a[i].l);R=min(R,a[i].r);
if(L>R){
ff=0;
break ;
}
}
if(ff==0){
puts("NO");
}else{
puts("YES");
}
}
}
|
D. Shortest and Longest LIS
Describe
给出一个由$<$和$>$组成的序列，第$i$个表示$a_i$和$a_{i+1}$的大小关系，求出两个满足这个条件的序列，其中一个$LIS$最长，一个$LIS$最短，多组询问，询问的序列长度和不超过$2\times {10}^5$。 P.S:LIS是最长不下降子序列长度
Solution
构造题。 最长构造： 
最短构造： 
那么构造就好了
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| int T,n,m,now;
char a[200010];
signed main(){
T=I.read();
while(T--){
n=I.read();
cin>>a+1;m=n;
for(int j,i=1;i<=n;i=j+1){
j=i;
while(j<n&&a[j]=='<') ++j;
m-=j-i+1;
for(int k=m+1;k<=m+j-i+1;k++) I.write(k),putchar(' ');
}
putchar('\n');
m=n;now=1;
for(int j,i=1;i<=n;i=j+1){
j=i;
while(j<n&&a[j]=='<') ++j;
for(int k=i;k<j;k++) I.write(now),putchar(' '),now++;
I.write(m);putchar(' ');
m--;
}
putchar('\n');
}
}
|
E. 1-Trees and Queries
Describe
给定树，$q$此询问如果加入边$(a,b)$,$x$到$y$是否有长度为$k$的路径（不一定是简单路径）。
Solution
先$LCA$预处理，$logN$求任意两点间距离。 那么加入$(a,b)$边，$x$到$y$的路径只有$3$种情况： - x–> y - x–>a–>b–>y - x–>b–>a–>y 所以乱搞就好了（注意可以走重复点所以直接%2即可）。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| int n,m,s;
int Dep[MAXN],f[MAXN][25];
int fir[MAXN],nxt[MAXN*2],son[MAXN*2],tot;
void add(int x,int y){
++tot;
nxt[tot]=fir[x];
fir[x]=tot;
son[tot]=y;
}
void init(int u,int fa){
Dep[u]=Dep[fa]+1;
for(int i=0;i<=21;i++){
f[u][i+1]=f[f[u][i]][i];
}
for(int i=fir[u];i;i=nxt[i]){
int to=son[i];
if(to==fa) continue ;
f[to][0]=u;
init(to,u);
}
}
int lca(int x,int y){
if(Dep[x]<Dep[y]) swap(x,y);
for(int i=22;i>=0;i--){
if(Dep[f[x][i]]>=Dep[y]) x=f[x][i];
if(x==y) return x;
}
for(int i=22;i>=0;i--){
if(f[x][i]!=f[y][i]){
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
int dist(int x,int y){
return Dep[x]+Dep[y]-2*Dep[lca(x,y)];
}
int main(){
n=I.read();s=1;
for(int i=1;i<=n-1;i++){
int x=I.read(),y=I.read();
add(x,y);add(y,x);
}
init(s,0);
m=I.read();
for(int x,y,a,b,k,i=1;i<=m;i++){
x=I.read(),y=I.read(),a=I.read(),b=I.read(),k=I.read();
swap(x,a);
swap(y,b);
int ans=dist(x,y);
int ff=0;
if(ans<=k&&(k-ans)%2==0) ff=1;
ans=dist(x,a)+dist(b,y)+1;
if(ans<=k&&(k-ans)%2==0) ff=1;
ans=dist(x,b)+dist(a,y)+1;
if(ans<=k&&(k-ans)%2==0) ff=1;
if(ff==1) puts("YES");
else puts("NO");
}
return 0;
}
|
F. Animal Observation
太难了不会qwq 挂个题解链接：戳这里