Codeforces Round #407 (Div. 1)
A. Functions again
题意：
给定长度为n的数组a 区间[L,R]的权值 f 为： 求所有区间中最大的 f 值
数据范围：n<=1e5
解法：
令b[i]=abs(a[i]-a[i+1]) 那么答案一定在{b[1],-b[2],b[3],-b[4]…}或者{b[2],-b[3],b[4]…}中 对两者计算最大子段和取max就是答案
code：
#include<bits/stdc++.h>
using namespace std
;
#define int long long
const int maxm
=1e5+5;
int a
[maxm
];
int b
[maxm
];
int n
;
signed main(){
cin
>>n
;
for(int i
=1;i
<=n
;i
++){
cin
>>a
[i
];
}
int ans
=-1e18;
for(int i
=1;i
<=n
-1;i
++){
b
[i
]=abs(a
[i
]-a
[i
+1]);
}
int ma
=-1e18;
for(int i
=1;i
<=n
-1;i
++){
int v
=b
[i
]*(i
%2?1:-1);
if(ma
+v
>v
){
ma
=ma
+v
;
}else{
ma
=v
;
}
ans
=max(ans
,ma
);
}
ma
=0;
for(int i
=2;i
<=n
-1;i
++){
int v
=b
[i
]*(i
%2?-1:1);
if(ma
+v
>v
){
ma
=ma
+v
;
}else{
ma
=v
;
}
ans
=max(ans
,ma
);
}
cout
<<ans
<<endl
;
return 0;
}
B. Weird journey
题意：
给定n个点m条边的无向图，可能存在自环和重边，但是保证每个点的自环最多一个
先将定义good path为m-2条路径经过两次，剩下2条路径经过一次 问图中有多少条不同的good path 两条good path不同当前仅当经过一次的路径集不同
数据范围：n,m<=1e6
解法：
题目可以转换为将图中的所有边复制一次，然后删除两条边，判断是否存在欧拉路
去掉没有边的孤立点之后，要保证图连通，这是欧拉路存在的前提 复制之后每个点的度数翻倍，所以所有点的度数一定是偶数，现在只需要判断删边之后是否能构造出欧拉路。
1.如果删掉的是不相邻且都不是自环的两条边，会出现4个奇数度，不存在欧拉路 2.如果删掉的是相邻且都不是自环的两条边，会出现2个奇数度，存在欧拉路 3.如果删掉的是两个自环，不会出现奇数度，存在欧拉路 4.如果删掉的一个是自环，一个不是自环，会出现两个奇数度，存在欧拉路
1的情况不好计算，考虑计算2，3，4的情况累加 3，4可以合并成自环可以和任意边配对
遇到自环(x,x)则ans+=m-1 否则(x,v)则ans+=(d[x]-1)+(d[v]-1)+（d[x]和d[v]之外的自环数） 发现（d[x]和d[v]之外的自环数）不好统计 改变一下写法，统计的度数的时候自环不增加度数，设自环数量为cir 则(x,v)时变为ans+=(d[x]-1)+(d[v]-1)+cir
因为存在重复计算，最后需要除以2
code：
#include<bits/stdc++.h>
using namespace std
;
#define int long long
const int maxm
=1e6+5;
int u
[maxm
],v
[maxm
];
int mark
[maxm
];
int d
[maxm
];
int pre
[maxm
];
int n
,m
;
int ffind(int x
){
return pre
[x
]==x
?x
:pre
[x
]=ffind(pre
[x
]);
}
signed main(){
ios
::sync_with_stdio(0);
cin
>>n
>>m
;
for(int i
=1;i
<=n
;i
++)pre
[i
]=i
;
int cir
=0;
for(int i
=1;i
<=m
;i
++){
cin
>>u
[i
]>>v
[i
];
mark
[u
[i
]]=mark
[v
[i
]]=1;
if(u
[i
]==v
[i
]){
cir
++;
}else{
d
[u
[i
]]++,d
[v
[i
]]++;
pre
[ffind(u
[i
])]=ffind(v
[i
]);
}
}
int cnt
=0;
for(int i
=1;i
<=n
;i
++){
if(mark
[i
]&&pre
[i
]==i
){
if(++cnt
>1)break;
}
}
if(cnt
!=1){
cout
<<0<<endl
;return 0;
}
int ans
=0;
for(int i
=1;i
<=m
;i
++){
if(u
[i
]==v
[i
]){
ans
+=m
-1;
}else{
ans
+=(d
[u
[i
]]-1)+(d
[v
[i
]]-1)+cir
;
}
}
ans
/=2;
cout
<<ans
<<endl
;
return 0;
}
C. The Great Mixing
题意：
给定n，和一个长度为k的数组a，表示有k种不同浓度的可乐，a(i)表示第i种可乐的浓度为a(i)/1000 现在要调配出浓度为n/1000的可乐，问最少需要多少杯可乐混合， 混合的时候不仅浓度相加，总体积也要相加（显然） 每种可乐有无限杯，且每次只能整杯整杯混合。 如果无解则输出-1
数据范围：n<=1e3，k<=1e6
解法：
假设需要m杯，第i杯的浓度是b(i)，那么(b(1)+b(2)+…b(m))/(1000m)=n/1000 将式子去分母变为b(1)+b(2)+…b(m)=m*n 再转化一下变为(b(1)-n)+(b(2)-n)+…(b(m)-n)=0 问题就变为计算最小需要多少个b(i)-n，使得他们相加等于0
可以用bfs计算 注意题中k<=1e6,但是每种可乐无限杯且浓度范围只有1000，所以去重一下将k缩小到1e3（否则bfs的时候会炸）
总结： 因为原式存在除法，可能会出现小数，因此应该先想是否能通过转化式子将除法转化为乘法
code：
#include<bits/stdc++.h>
using namespace std
;
#define int long long
const int maxm
=1e6+5;
int a
[maxm
];
int n
,k
;
signed main(){
ios
::sync_with_stdio(0);
cin
>>n
>>k
;
for(int i
=1;i
<=k
;i
++){
cin
>>a
[i
];
a
[i
]=a
[i
]-n
;
}
sort(a
+1,a
+1+k
);
k
=unique(a
+1,a
+1+k
)-a
-1;
map
<int,int>mark
;
queue
<int>q
;
for(int i
=1;i
<=k
;i
++){
mark
[a
[i
]]=1;
q
.push(a
[i
]);
}
int now
=0;
while(!q
.empty()){
now
++;
int len
=q
.size();
while(len
--){
int x
=q
.front();q
.pop();
if(x
==0){
cout
<<now
<<endl
;return 0;
}
for(int i
=1;i
<=k
;i
++){
int t
=x
+a
[i
];
if(t
<-500||t
>500)continue;
if(!mark
.count(t
)){
mark
[t
]=1;
q
.push(t
);
}
}
}
}
cout
<<-1<<endl
;
return 0;
}
