Codeforces Round #772 (Div. 2)
VP
| A | B | C |
|---|---|---|
| 3min | 12min | 52min |
| +4 |
排名：rk3893
基准分：\(\color{ForestGreen}{1362}\)
从天选到天崩
A
\(\color{Gray}{800}\)
简要分析可知，其实答案就是对于所有数取或运算和(具体懒得管)
时间复杂度：\(O(n)\)
int n,x;
void work(){
int ans=0;cin>>n;
L(i,1,n) cin>>x,ans|=x;
cout<<ans<<'\n';
}
B
\(\color{Gray}{800}\)
就是个贪心，如果能左右两个一起解决就一起干。
构造起来不难。
int n,c;
const int N=2e5+100,INF=1e9;
int a[N];bool f[N];
void work(){
cin>>n;L(i,1,n) cin>>a[i];
me(f,0);vector <int>p;c=0;
L(i,2,n-1) if(a[i]>a[i-1]&&a[i]>a[i+1])
p.push_back(i),f[i]=1;
for(int i=0;i<p.size();i++){
if(p[i]==p[i+1]-2){
a[p[i]+1]=max(a[p[i]],a[p[i+1]]);
i++;c++;
}else a[p[i]-1]=a[p[i]],c++;
}cout<<c<<'\n';
L(i,1,n) cout<<a[i]<<" \n"[i==n];
}
C
\(\color{ForestGreen}{1200}\)
先想几个特殊情况：
- 如果 \(a_n,a_{n-1}\) 之间不满足，则必然无解。
- 如果 \(a_n<0\)，则原序列必须单减，否则无解。
至于证明，可以看官方题解。
又懒得证
时间复杂度：\(O(n)\)
#define F(i) (i).first
#define S(i) (i).second
#define pb push_back
int n;
const int N=2e5+100,INF=1e9;
int a[N],sum[N];bool f[N];
vector<pair<pi,int>>ans;
void work(){
cin>>n;L(i,1,n) cin>>a[i];a[n+1]=INF;
if(a[n]<a[n-1]) return cout<<-1<<'\n',void();
L(i,1,n) f[i]=0;
ans.clear();int flag=0;
int k=0;
L(i,1,n-1) if(a[i]>a[i+1]) f[i]=1,flag++;
if(a[n]<0){
bool t=0;L(i,1,n-1)
if(a[i]>a[i+1]){t=1;break;}
return cout<<(t?-1:0)<<'\n',void();
}if(!flag) return cout<<0<<'\n',void();
L(i,1,n-2) ans.pb({{i,n-1},n});
cout<<(int)ans.size()<<'\n';
for(auto i:ans)
cout<<F(F(i))<<' '<<S(F(i))<<' '<<S(i)<<'\n';
}
四次法师，代码巨丑。
D
\(\color{Blue}{1800}\)
在二进制下考虑问题。
对于数 \(x\)，\(x \times 2 + 1\) 相当于 \(x<<1|1\)，\(x \times 4\) 相当于 \(x<<2\)。
尝试推导每个数的贡献值。
设 \(f_i\) 表示用上述方法推得能产生的 \(i\) 位数的个数。
很容易想到转移 \(f_i = \begin{cases}1&i\leqslant1\\f_{i-1}+f_{i-2}&x>1\end{cases}\)
其实就是斐波那契数列。
直接统计显然是 \(O(n)\)，这个部分可以用前缀和优化到 \(O(1)\)。
之后考虑可能出现的重复计算贡献的情况。
其实出现重复就是某个数会在另一个数在递推时产生。
对于这种情况，我们每循环一个数就丢进 std::set() 中，之后的数如果在拆分时的“子集”在 std::set() 中出现，跳过即可。
时间复杂度：\(O(n \log_2 A \log_2 n + p)\)
int n,p,ans;
const int N=2e5+100,mod=1e9+7;
int f[N],a[N];set<int>s;
bool check(int x){
bool f=1;
while(x>0){
if(s.count(x)){f=0;break;}
if(x&1) x>>=1;
else if(x%4==0) x>>=2;
else break;
}return f;
}void work(){
cin>>n>>p;f[0]=1;
L(i,1,p)
f[i]=(f[i-1]+(i>1?f[i-2]:0))%mod;
L(i,1,p)
(f[i]+=f[i-1])%=mod;
L(i,1,n) cin>>a[i];
sort(a+1,a+1+n);
L(i,1,n) if(check(a[i])){
s.insert(a[i]);
int g=__lg(a[i])+1;
if(g<=p) (ans+=f[p-g])%=mod;
}cout<<ans;
}
E
\(\color{Orange}{2200}\)
转化下题意，相当于每个限制是两车方向必须相反，且存在位置相对关系。
可以先连边，跑二分图染色，判断是否有解。
如果有解按照每辆车的朝向和已知信息建新图跑拓扑排序，分配每辆车的位置。
注意拓扑排序之后要判断车的位置是否合法，如果重叠也是无解。
时间复杂度：\(O(n+m)\)
#define L(i,j,k) for(int i=(j);i<=(k);i++)
int n,m;bool tp;
const int N=5e5+100,mod=1e9+7;
int cl[N],o[N],u[N],v[N],ans[N],in[N];
vector<int>g[N];queue<int>q;
void dfs(int u,int c){
cl[u]=c;
for(int v:g[u]){
if(cl[v]==cl[u]){tp=1;return ;}
if(!cl[v]) dfs(v,-c);
}
}void top(){
int tot=0;
while(!q.empty()){
int u=q.front();q.pop();ans[u]=++tot;
for(int v:g[u]) if(!(--in[v])) q.push(v);
}
}void work(){
cin>>n>>m;
L(i,1,m){
cin>>o[i]>>u[i]>>v[i];
g[u[i]].pb(v[i]);g[v[i]].pb(u[i]);
}L(i,1,n) if(!cl[i]) dfs(i,1);
if(tp) return cout<<"NO",0;
L(i,1,n) g[i].clear();
L(i,1,m)
if((o[i]==2&&cl[u[i]]==-1)||(o[i]==1&&cl[u[i]]==1))
g[u[i]].pb(v[i]),in[v[i]]++;
else g[v[i]].pb(u[i]),in[u[i]]++;
L(i,1,n) if(!in[i]) q.push(i);
top();map<int,int>mp;L(i,1,n) mp[ans[i]]++;
L(i,1,n) if(mp[ans[i]]>1) return cout<<"NO",0;
cout<<"YES"<<'\n';
L(i,1,n) cout<<(cl[i]==1?'L':'R')<<' '<<ans[i]<<'\n';
}
