CF习题集二
一、CF507E Breaking Good
题目描述
\(Breaking Good\)这个游戏对于有经验的玩家来说也有一定的难度。
游戏的主角小明希望加入一个叫斧头帮的犯罪团伙。这个团伙控制着整个国家\(n\)个城市间的\(m\)条双向道路，这些道路保证没有自环和重边，任何城市可以通过这些道路到达任何其他城市。
然而道路并不全都能通行，有些道路是需要修复。
现在这个团伙要搞一个大新闻！搞事地点位于城市\(1\)。像往常一样，这个行动最难的部分是搞事后如何逃到他们在城市n的总部。为了获得该团伙的信任，小明决定负责这项搞事行动，而且他提出了一个看起来很明智的计划。
首先，他们将在从城市1返回途中使用的路径总长度必须尽可能短；然后，为了让搞的大新闻更加刺激，他们必须炸毁所有不在这条路径上的其他道路。但是他们不必炸掉不能通行的道路。
如果选择的道路有一些不能通行的道路，他们将不得不在行动之前修复那些道路。
小明发现，有很多路径满足了条件\(1\)（即尽可能短），所以他决定在其中选择一条路径，使受影响道路的总数最小化。
你能帮助小明完成搞事并获得该团伙的信任吗？
分析
首先，我们要选择一条最短的路径
在路径最短的基础上，我们要尽量使受影响的道路数更少
因此我们要在跑\(Dij\)的结构体里存储三个东西
即当前节点的编号，当前节点距离起点的最短路径，当前路径下更改的道路条数
在进行松弛操作时，如果\(dis[u]>dis[now]+b[i].val\)
那么我们像之前那样更新\(dis\)值即可
如果\(dis[u]=dis[now]+b[i].val\)但是新的路径更改的道路条数更少
此时我们也需要更新
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int head[maxn],tot=1;
struct asd{
int from,to,next,val,jud;
}b[maxn];
void ad(int aa,int bb,int cc,int dd){
b[tot].from=aa;
b[tot].to=bb;
b[tot].next=head[aa];
b[tot].val=cc;
b[tot].jud=dd;
head[aa]=tot++;
}
struct jie{
int num,jl,hf;
jie(int aa,int bb,int cc){
num=aa,jl=bb,hf=cc;
}
bool operator < (const jie& A) const{
if(jl==A.jl) return hf>A.hf;
return jl>A.jl;
}
};
priority_queue<jie> q;
bool viss[maxn];
int dis[maxn],jl[maxn],hf[maxn];
void dij(){
memset(dis,0x3f,sizeof(dis));
memset(hf,0x3f,sizeof(hf));
dis[1]=0;
hf[1]=0;
q.push(jie(1,0,0));
while(!q.empty()){
int now=q.top().num;
int nhf=q.top().hf;
q.pop();
if(viss[now]) continue;
viss[now]=1;
for(int i=head[now];i!=-1;i=b[i].next){
int u=b[i].to;
if(dis[u]>dis[now]+b[i].val){
dis[u]=dis[now]+b[i].val;
jl[u]=i;
hf[u]=nhf+b[i].jud;
q.push(jie(u,dis[u],hf[u]));
} else if(dis[u]==dis[now]+b[i].val){
if(hf[u]>nhf+b[i].jud){
jl[u]=i;
hf[u]=nhf+b[i].jud;
q.push(jie(u,dis[u],hf[u]));
}
}
}
}
}
vector<int> g;
bool vis[maxn];
int main(){
memset(head,-1,sizeof(head));
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int aa,bb,cc;
scanf("%d%d%d",&aa,&bb,&cc);
ad(aa,bb,1,cc^1);
ad(bb,aa,1,cc^1);
}
dij();
int ans=0;
int now=n;
while(jl[now]){
if(jl[now]%2==0) g.push_back(jl[now]-1);
else g.push_back(jl[now]);
now=b[jl[now]].from;
}
for(int i=0;i<g.size();i++){
vis[g[i]]=1;
}
for(int i=1;i<tot;i+=2){
if(vis[i]){
if(b[i].jud==1){
ans++;
}
} else {
if(b[i].jud==0){
ans++;
}
}
}
printf("%d\n",ans);
for(int i=1;i<tot;i+=2){
if(vis[i]){
if(b[i].jud==1){
printf("%d %d %d\n",b[i].from,b[i].to,1);
}
} else {
if(b[i].jud==0){
ans++;
printf("%d %d %d\n",b[i].from,b[i].to,0);
}
}
}
return 0;
}
二、CF467C George and Job
题目描述
新款手机 \(iTone6\) 近期上市，\(George\) 很想买一只。不幸地，\(George\) 没有足够的钱，所以 \(George\) 打算当一名程序猿去打工。现在\(George\)遇到了一个问题。 给出一组有 \(n\) 个整数的数列\(p_1,p_2,...,p_n\),你需要挑出 \(k\) 组长度为 \(m\) 的数，要求这些数互不重叠 即$ [l_{1},r_{1}],[l_{2},r_{2}],...,[l_{k},r_{k}] (1<=l_{1}<=r_{1}<l_{2}<=r_{2}<...<l_{k}<=r_{k}<=n;r_{i}-l_{i}+1=m)[l1,r1],[l2,r2],...,[lk,rk]$
使选出的数的和值最大，请你帮助George码出这份代码
分析
我们设\(f[i][j]\)为前\(i\)个数选出了\(j\)组，其中第\(i\)个数必须选的最大值
那么我们就可以写出如下的状态转移方程
f[i][k]=max(f[i][k],f[j][k-1]+sum[i]-sum[i-m]);
时间复杂度为\(O(n^3)\)
实际上，我们可以用单调队列对于每一个\(i\)维护\(f[j][k-1]\)的最大值
这样时间复杂度就降到了\(O(n^2)\)
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5;
#define int long long
int sum[maxn],a[maxn],f[maxn][maxn],q[maxn],head,tail;
signed main(){
int n,m,p;
scanf("%lld%lld%lld",&n,&m,&p);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
sum[i]=sum[i-1]+a[i];
}
int ans=0;
for(int j=1;j<=p;j++){
head=1,tail=1;
memset(q,0,sizeof(q));
for(int i=m;i<=n;i++){
if(head<=tail)f[i][j]=max(f[i][j],f[q[head]][j-1]+sum[i]-sum[i-m]);
while(head<=tail && f[i-m+1][j-1]>f[q[tail]][j-1]) tail--;
q[++tail]=i-m+1;
ans=max(ans,f[i][p]);
}
}
printf("%lld\n",ans);
return 0;
}
三、CF333E Summer Earnings
题目描述
在一个平面内给出\(n\)个点的坐标，任选其中三个为圆心作半径相同的圆，要求这三个圆不能相交但可以相切，求能画出的圆中的最大半径。
分析
对于平面上的三个点，我们可以将其分为两种情况
一种情况是三个点都位于一条直线上
此时我们的最大直径只能是三点当中距离最小的两点的距离
还有一种情况是三个点不在同一条直线上
此时我们的最大直径也只能是三点当中距离最小的两点的距离
因为我们要保证圆只能相切，不能相交
如果直径再大一点，势必会出现相交的情况
所以我们可以先预处理出任意两点间的距离，然后按距离从小到大排好序
每次取出两个点，我们就判断一下它们是否和同一个点已经连到一起
如果已经连到一起，我们就输出当前答案，否则继续寻找
而判断两个点是否和同一个点连到一个我们可以用\(bitset\)解决
代码
#include<bits/stdc++.h>
using namespace std;
typedef double dd;
const int maxn=3005;
dd jlx[maxn],jly[maxn];
bitset<maxn> g[maxn];
struct asd{
int from,to;
dd da;
}b[maxn*maxn];
dd solve(int aa,int bb){
return (dd)sqrt((jlx[aa]-jlx[bb])*(jlx[aa]-jlx[bb])+(jly[aa]-jly[bb])*(jly[aa]-jly[bb]));
}
bool cmp(asd aa,asd bb){
return aa.da>bb.da;
}
int main(){
int n,cnt=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf%lf",&jlx[i],&jly[i]);
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(i==j) continue;
b[++cnt].da=solve(i,j);
b[cnt].from=i;
b[cnt].to=j;
}
}
sort(b+1,b+1+cnt,cmp);
for(int i=1;i<=cnt;i++){
int aa=b[i].from,bb=b[i].to;
g[aa][bb]=1,g[bb][aa]=1;
if((g[aa] & g[bb]).count()){
printf("%.20lf\n",b[i].da/2.0);
exit(0);
}
}
return 0;
}
四、CF132C Logo Turtle
题目描述
很多人把\(LOGO\)编程语言和海龟图形联系起来。在这种情况下，海龟沿着直线移动，接受命令“T”（“转向180度”）和“F”（“向前移动1单元”）。
你会收到一份给海龟的命令清单。你必须从列表中精确地改变N个命令（一个命令可以被改变多次）。要求出海龟在遵循修改后的所有命令后，会从起点最远可以移到多远？
分析
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
char s[maxn];
int f[maxn][maxn][3],wz[maxn];
int main(){
for(int i=0;i<maxn;i++){
for(int j=0;j<maxn;j++){
f[i][j][1]=f[i][j][0]=-0x3f3f3f3f;
}
}
scanf("%s",s+1);
int n;
scanf("%d",&n);
int len=strlen(s+1);
f[0][0][0]=0;
f[0][0][1]=0;
for(int i=1;i<=len;i++){
for(int j=0;j<=n;j++){
for(int k=0;k<=j;k++){
if(s[i]=='F'){
if(k&1){
f[i][j][0]=max(f[i][j][0],f[i-1][j-k][1]);
f[i][j][1]=max(f[i][j][1],f[i-1][j-k][0]);
} else {
f[i][j][0]=max(f[i][j][0],f[i-1][j-k][0]+1);
f[i][j][1]=max(f[i][j][1],f[i-1][j-k][1]-1);
}
} else {
if(k&1){
f[i][j][0]=max(f[i][j][0],f[i-1][j-k][0]+1);
f[i][j][1]=max(f[i][j][1],f[i-1][j-k][1]-1);
} else {
f[i][j][0]=max(f[i][j][0],f[i-1][j-k][1]);
f[i][j][1]=max(f[i][j][1],f[i-1][j-k][0]);
}
}
}
}
}
printf("%d\n",max(f[len][n][0],f[len][n][1]));
return 0;
}