Codeforces Round #620 (Div. 2)
A. Two Rabbits
题意
两只兔子相向而跳，一只一次跳距离a，另一只一次跳距离b，每次同时跳，问是否可能到同一位置
题解
每次跳相对距离减少Δ=(a+b)\Delta=(a+b)Δ=(a+b)，如果总距离是Δ\DeltaΔ的倍数，就证明可以到同一位置
代码
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{ long N,x,y,a,b;
scanf("%ld",&N);
while(N--){
scanf("%ld%ld%ld%ld",&x,&y,&a,&b);
if((y-x)%(a+b)==0)
printf("%ld\n",(y-x)/(a+b));
else
printf("-1\n");
}
return 0;
}
B. Longest Palindrome
题意
给定n个字符串，选择其中的若干个重新排列，找出能得到的最长回文串
题解
将每个串记录下来，如果一个串颠倒后和另一个串相等，就证明可取，放在答案串的两边；如果一个串本身就是回文串，就可以放在答案串的中间
代码
#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
set<string>st;
int main()
{ long n,m,i,j;
string s,s1,ans="",ans_mid;
bool t=false;
scanf("%ld%ld",&n,&m);
for(i=1;i<=n;i++){
cin>>s;
s1="";
for(j=0;j<m;j++)
s1=s[j]+s1;
if(s==s1){
if(!t){
t=true;
ans_mid=s;
}
}
else if(st.find(s1)!=st.end())
ans=s+ans+s1;
st.insert(s);
}
if(t)
ans.insert(ans.length()/2,ans_mid);
cout<<ans.length()<<endl<<ans<<endl;
return 0;
}
C. Air Conditioner
题意
店里的空调可开可关，开着每分钟温度可以上升或者下降1度，每位顾客有个满意温度范围，已知所有顾客的访问时间和温度范围，问是否可能做到满足所有顾客
题解
记录下能调到的最大最小温度，如果跟顾客的满意温度有交集，就把温度范围变成交集的范围，否则就无法满足
代码
#include<cstdio>
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define def 110
long t[def],x[def],y[def];
int main()
{ long N,n,m,l,r,i;
bool ans;
scanf("%ld",&N);
while(N--){
scanf("%ld%ld",&n,&m);
l=r=m;
ans=true;
for(i=1;i<=n;i++){
scanf("%ld%ld%ld",&t[i],&x[i],&y[i]);
l-=t[i]-t[i-1];
r+=t[i]-t[i-1];
if(l<=y[i]&&r>=x[i]){
l=max(l,x[i]);
r=min(r,y[i]);
}else
ans=false;
}
if(ans)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
D. Shortest and Longest LIS
题意
给定数列的相邻数之间的大小关系，求出满足给定的大小关系的所有数列中，最长上升子序列最大和最小的两个数列
题解
最长上升子序列一定出现在所有<的左右，那么只用构造<左边的数（右边的不能构造，会导致可能不能满足后面可能存在的>），剩下的按大小关系递增或递减填充即可
代码
#include<iostream>
#include<cstdio>
#define min(a,b) (((a)<(b))?(a):(b))
#define def 200010
using namespace std;
long l[def],r[def],ans[2][def];
int main()
{ long N,n,now,i,minn,j,q,k;
string s;
scanf("%ld",&N);
while(N--){
cin>>n>>s;
s+="<";
now=1;
for(i=0;i<n;i++)//正向从小到大填充 <
if(s[i]=='<')
ans[1][i]=now++;
q=now;
for(i=0;i<n;i++)//正向从小到大填充 >
if(s[i]=='<')
for(j=i-1;j>=0&&s[j]=='>';j--)
ans[1][j]=now++;
now=q-1;
for(i=0;i<n;i++)//反向从小到大填充 <
if(s[i]=='<'){
if(s[i+1]!='<')
ans[0][i]=now--;
else{
for(j=i+1;s[j]=='<'&&j<n;j++);
j--;
for(k=j;k>=i;k--)
ans[0][k]=now--;
i=j;
}
}
now=q;
for(i=n-1;i>=0;i--)//反向从小到大填充 >
if(s[i]=='<')
for(j=i-1;j>=0&&s[j]=='>';j--)
ans[0][j]=now++;
for(i=0;i<n;i++)
printf("%ld ",ans[0][i]);
printf("\n");
for(i=0;i<n;i++)
printf("%ld ",ans[1][i]);
printf("\n");
}
return 0;
}
E. 1-Trees and Queries
题意
给定一棵树，每次询问加一条从x到y的边，问是否可能满足从a点到b点的路径长度恰好等于k（可重复走一条边）
题解
因为可以重复走，所以可以反复横跳，这里长度为偶数，所以只需要判断走或者不走新的一条边后，剩下的需求长度是否为偶数即可。
ps：树上距离可以用深度和lca快速计算，新边长度为1，所以不需要真正把边加上去
代码
#include<cstdio>
#include<cstring>
#include<vector>
#define def 100010
using namespace std;
vector<long>mp[def];
long dep[def],fa[def][20];
inline void swap(long &a,long &b)
{ long tmp=a;
a=b;
b=tmp;
}
void dfs(long now,long d)
{ long i;
dep[now]=d;
for(i=0;(1<<i)<=def;i++)
fa[now][i+1]=fa[fa[now][i]][i];
for(auto next:mp[now])
if(!dep[next]){
fa[next][0]=now;
dfs(next,d+1);
}
}
long lca(long x,long y)
{ long i;
if(dep[x]<dep[y])
swap(x,y);
for(i=19;i>=0;i--)
if(dep[fa[x][i]]>dep[y])
x=fa[x][i];
if(dep[x]!=dep[y])
x=fa[x][0];
for(i=19;i>=0;i--)
if(fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
}
return (x==y)?x:fa[x][0];
}
long calc(long x,long y)
{
return dep[x]+dep[y]-dep[lca(x,y)]*2;
}
bool check(long q,long k)
{
return q<=k&&(k-q)%2==0;
}
int main()
{ long n,i,x,y,a,b,k,m;
scanf("%ld",&n);
for(i=1;i<n;i++){
scanf("%ld%ld",&x,&y);
mp[x].push_back(y);
mp[y].push_back(x);
}
dfs(1,1);
scanf("%ld",&m);
for(i=1;i<=m;i++){
scanf("%ld%ld%ld%ld%ld",&x,&y,&a,&b,&k);
if(check(calc(a,b),k)||
check(calc(a,x)+calc(b,y)+1,k)||
check(calc(a,y)+calc(b,x)+1,k))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}