【恢复计划】CF ROUND 620 div2 简要题解
找神腮要了一个简单场
A - Two Rabbits
判断((a+b)|(x-y))就行了
//@winlere
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int qr(){
int ret=0,c=getchar();
while(!isdigit(c)) c=getchar();
while( isdigit(c)) ret=ret*10+c-48,c=getchar();
return ret;
}
ll gcd(ll a,ll b){
if(!b) return a;
return gcd(b,a%b);
}
int main(){
int T=qr();
while(T--){
ll x=qr(),y=qr(),a=qr(),b=qr();
ll z=y-x,d=gcd(z,a+b);
if(d==a+b) cout<<z/(a+b)<<endl;
else cout<<"-1"<<endl;
}
return 0;
}
B - Longest Palindrome
因为保证的所有字符串长度都是m，因此贪心的能放就放就行(对于一个串，找是否存在它的reverse之后的串，如果有就直接放)。
但是有一个特殊情况，就是自我对称的串，这个直接放在中间就行
//@winlere
#include<iostream>
#include<set>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=105;
string data[maxn],ans,self;
multiset<string> s;
int main(){
int n,m;
cin>>n>>m;
for(int t=1;t<=n;++t) {
cin>>data[t];
string f=data[t];
reverse(f.begin(),f.end());
auto it=s.find(f);
if(it!=s.end()) ans=data[t]+ans+f,s.erase(it);
else s.insert(data[t]);
}
for(auto t:s){
auto f=t;
reverse(f.begin(),f.end());
if(f==t){
int siz=ans.size();
if(siz==0) ans=t;
else ans.insert(siz/2,f);
break;
}
}
cout<<ans.size()<<endl<<ans<<endl;
return 0;
}
C - Air Conditioner
容易证明，任何一个时间点，可以达到的温度是一个连续的区间，因此维护这个可行区间就行。时间会延伸这个可行区间，顾客的要求会限制这个可行区间，复杂度(O(n))
//@winlere
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
int qr(){
int ret=0,c=getchar(),f=0;
while(!isdigit(c)) f=c=='-',c=getchar();
while( isdigit(c)) ret=ret*10+c-48,c=getchar();
return f?-ret:ret;
}
const int maxn=505;
struct Peroid{
int l,r;
Peroid(int a=-1e9,int b=1e9):l(a),r(b){}
Peroid operator + (Peroid f){
int L=max(l,f.l),R=min(r,f.r);
if(L>R) return Peroid(1e9,-1e9);
return Peroid(L,R);
}
Peroid operator + (int d){
return Peroid(l-d,r+d)+Peroid();
}
};
int main(){
int T=qr();
while(T--){
int n=qr(),m=qr(),tim=0;
Peroid now(m,m);
for(int t=1;t<=n;++t){
int cur=qr(),l=qr(),r=qr();
Peroid cur1(l,r);
now=now+(cur-tim)+cur1;
tim=cur;
}
if(now.l<=now.r) puts("YES");
else puts("NO");
}
return 0;
}
D - Shortest and Longest LIS
虽然退役多年，但还是记得一些套路。
构造一个最长的LIS，理论上界是所有连续的(<)号连接的数字都是LIS的一部分，这是上界，下面我将构造出这个上界:
初始有一个(1 2 3 dots)，然后将所有(>)的连续段reverse就行了。
同样的方法，构造一个最小的LIS，理论下界是最长的连续(>)号，这是下界，下面我将构造出这个下界
初始有一个(n n-1 dots 3 2 1)
然后把所有的(<)的连续段reverse就行了。
//@winlere
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=2e5+5;
int qr(){
int ret=0,c=getchar();
while(!isdigit(c)&&c!='<'&&c!='>') c=getchar();
if(c=='<') return 0;
if(c=='>') return 1;
while( isdigit(c)) ret=ret*10+c-48,c=getchar();
return ret;
}
int data[maxn],ans[maxn];
int main(){
int T=qr();
while(T--){
int n=qr();
for(int t=1;t<n;++t) data[t]=qr();
for(int t=1;t<=n;++t) ans[t]=n-t+1;
for(int t=1,r=1;t<n;t=++r){
while(r<n&&data[r]==0) ++r;
reverse(ans+t,ans+r+1);
}
for(int t=1;t<=n;++t) printf("%d ",ans[t]);
putchar('
');
for(int t=1;t<=n;++t) ans[t]=t;
for(int t=1,r=1;t<=n;t=++r) {
while(r<n&&data[r]==1) ++r;
reverse(ans+t,ans+r+1);
}
for(int t=1;t<=n;++t) printf("%d ",ans[t]);
putchar('
');
}
return 0;
}
E - 1-Trees and Queries
由于可以重复走一个边，因此可行性之和两点之间的最短路的奇偶性有关了
//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int qr(){
int ret=0,c=getchar(),f=0;
while(!isdigit(c)) f=c=='-',c=getchar();
while( isdigit(c)) ret=ret*10+c-48,c=getchar();
return f?-ret:ret;
}
const int maxn=1e5+5;
vector<int> e[maxn];
void add(int a,int b){e[a].push_back(b);e[b].push_back(a);}
int lg[maxn],r[21][maxn],dep[maxn],n,m;
void dfs(int now,int last){
r[0][now]=last; dep[now]=dep[last]+1;
for(int t=1;t<=lg[dep[now]];++t)
r[t][now]=r[t-1][r[t-1][now]];
for(auto t:e[now])
if(t^last)
dfs(t,now);
}
int LCA(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
for(int t=lg[dep[u]];~t;--t)
if(dep[r[t][u]]>=dep[v])
u=r[t][u];
if(u==v) return u;
for(int t=lg[dep[u]];~t;--t)
if(r[t][u]!=r[t][v])
u=r[t][u],v=r[t][v];
return r[0][u];
}
int getLen(int a,int b){
int L=LCA(a,b);
return dep[a]+dep[b]-dep[L]-dep[L];
}
int getAns(int a,int b,int x,int y,int k){
int L1=getLen(a,b),L2=getLen(a,x)+getLen(y,b)+1;
if( (!((L1^k)&1))&&L1<=k ) return 1;
if( (!((L2^k)&1))&&L2<=k ) return 1;
return 0;
}
int main(){
for(int t=2;t<maxn;++t) lg[t]=lg[t>>1]+1;
n=qr();
for(int t=1;t<n;++t) add(qr(),qr());
dfs(1,0);
m=qr();
for(int t=1;t<=m;++t){
int x=qr(),y=qr(),a=qr(),b=qr(),k=qr();
puts(getAns(a,b,x,y,k)||getAns(a,b,y,x,k)?"YES":"NO");
}
return 0;
}