这么早的CF已经很少见了，不过我还是大力掉分。
我好菜啊.jpg
CF1131A
观察题意，随便推个式子提交就AC了。
打卡题。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int a,b,c,d,ans=0;
void init(){
scanf("%d%d%d%d",&a,&b,&c,&d);
ans=a+b*2+c+d*2+std::abs(a-c)+4;
printf("%d\n",ans);
}
int main(){
init();
return 0;
}
CF1131B
一道比较简单的题，但是如果脑残了会非常难。
反正我脑残以后是瞎jb写了二十七个特判死活PP不了。
当然仔细理解题意会发现还是比较简单的——当且仅当上一个的终止状态是平局态的时候，答案会有额外的统计。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int n,a[100005],b[100005],ans=1;
void init(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d%d",&a[i],&b[i]);
ans+=max(0,min(a[i],b[i])-max(a[i-1],b[i-1])+1);
if(a[i-1]==b[i-1]){
--ans;
}
}
printf("%d\n",ans);
}
int main(){
init();
return 0;
}
CF1131C
比B简单，普通构造题。
第一个直观的感觉是从小到大排列，但是仔细想想觉得那样不一定更优。
所以考虑到FJ省冬令营ZZQ讲的构造技巧，可以上一个奇偶排序。
于是AC此题。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int n,a[100005];
void init(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i+=2){
printf("%d ",a[i]);
}
for(int i=n;i>=1;--i){
if(!(i&1)){
printf("%d ",a[i]);
}
}
}
int main(){
init();
return 0;
}
CF1131D
一道细节题，车站分级弱化版。
如果没有等于号，直接拓扑排序就可以通过。
但是等于号比较蛋疼。
会发现等于号得到的东西都是相同等级的，所以可以考虑用并查集维护。
两个坑点：首先要考虑记录访问过的点的次数来判是否无解，因为可能存在一个独立的环。
然后更新答案应该要按照最后一个更新，而非第一个。这是由这个解法的基本特性，也就是解集是所有约束条件的并集这一特性决定的。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int n,m,in[2005];
char ch[1005][1005];
int f[2005];
inline int fa(int X){
return f[X]==X?X:f[X]=fa(f[X]);
}
inline void uni(int X,int Y){
X=fa(X),Y=fa(Y);
f[X]=Y;
}
bool mp[2005][2005];
queue<int> q;
bool vis[2005];
int ans[2005];
inline bool srt(){
for(int i=1;i<=n+m;++i){
if(!in[i]){
q.push(i);
ans[i]=1;
vis[i]=1;
}
}
int cnt=0;
int p;
while(!q.empty()){
p=q.front();
q.pop();
++cnt;
for(int i=1;i<=n+m;++i){
if(mp[p][i]){
if(!in[fa(i)]){
return 0;
}else{
--in[fa(i)];
if(!in[fa(i)]){
q.push(fa(i));
ans[fa(i)]=min(ans[p]+1,ans[fa(i)]);
}
}
}
}
}
return cnt==n+m;
}
void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
std::cin>>ch[i]+1;
}
for(int i=1;i<=n+m;++i){
f[i]=i,ans[i]=0x3f3f3f3f;
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(ch[i][j]=='<'){
mp[i][n+j]=1;
}
if(ch[i][j]=='>'){
mp[n+j][i]=1;
}
if(ch[i][j]=='='){
uni(i,n+j);
}
}
}
for(int i=1;i<=n+m;++i){
if(fa(i)!=i){
for(int j=1;j<=n+m;++j){
mp[fa(i)][j]|=mp[i][j];
mp[i][j]=0;
}
for(int j=1;j<=n+m;++j){
if(mp[j][i]){
mp[j][fa(i)]=1;
mp[j][i]=0;
}
}
}
}
for(int i=1;i<=n+m;++i){
for(int j=1;j<=n+m;++j){
if(mp[i][j]){
++in[j];
}
}
}
if(!srt()){
puts("No");
return;
}else{
puts("Yes");
for(int i=1;i<=n;++i){
printf("%d ",ans[fa(i)]);
}
puts("");
for(int i=n+1;i<=n+m;++i){
printf("%d ",ans[fa(i)]);
}
}
}
int main(){
init();
return 0;
}
CF1131F
这道题和D题有一点神似。
我们维护每一个已经弄好的连续块的左端点和右端点，每次访问到这个块就直接连接到它的父亲。
这个过程用并查集完成，使得可以直接搜索到整个块的端点。每一次直接把前一个块接在后一个块的左边就好了。
把每个连接记录一下最后输出即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
struct ee{
int v;
int nxt;
}e[300005];
int h[150005],et=0;
inline void add(int U,int V){
e[++et]=(ee){V,h[U]};
h[U]=et;
}
int n,l[150005],r[150005];
int f[150005];
inline int fa(int X){
return X==f[X]?X:f[X]=fa(f[X]);
}
inline void uni(int X,int Y){
X=fa(X),Y=fa(Y);
f[X]=Y;
}
void init(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
l[i]=r[i]=i,f[i]=i;
}
int a,b;
for(int i=1;i<n;++i){
scanf("%d%d",&a,&b);
a=fa(a),b=fa(b);
add(r[a],l[b]);
uni(a,b);
l[b]=l[a];
}
a=l[fa(1)],b=0;
printf("%d ",a);
for(int i=1;i<n;++i){
for(int j=h[a];j;j=e[j].nxt){
if(e[j].v!=b){
printf("%d ",e[j].v);
b=a,a=e[j].v;
break;
}
}
}
}
int main(){
init();
return 0;
}