C
https://codeforces.com/contest/1130/problem/C
题意
给你一个(n*m)（n,m<=50)的矩阵，每个格子代表海或者陆地，给出在陆地上的起点终点，只允许挖一条穿越海的隧道，假设隧道连接的两个陆地分别为(x1,y1),(x2,y2),则挖隧道的花费为((y1-x1)*(y1-x1)+(y2-x2)*(y2-x2))
题解
- 分别找出和起点，和终点连接的陆地（找联通块），枚举两个点维护最小值
代码
#include<bits/stdc++.h>
#define pii pair<int,int>
#define se second
#define ft first
#define mk make_pair
using namespace std;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int dis(pii a,pii b){
return (a.ft-b.ft)*(a.ft-b.ft)+(a.se-b.se)*(a.se-b.se);
}
vector<pii>st,ed;
int n,sx,sy,ex,ey,i,vi[55][55],ans;
char g[55][55];
void dfs(int x,int y,int fg){
vi[x][y]=1;
if(fg)st.push_back(mk(x,y));
else ed.push_back(mk(x,y));
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(nx<1||ny<1||nx>n||ny>n||g[nx][ny]=='1'||vi[nx][ny])continue;
dfs(nx,ny,fg);
}
return;
}
int main(){
cin>>n;
cin>>sx>>sy>>ex>>ey;
for(i=1;i<=n;i++)scanf("%s",g[i]+1);
dfs(sx,sy,0);
memset(vi,0,sizeof(vi));
dfs(ex,ey,1);
ans=1e9;
for(auto i:st)
for(auto j:ed)
ans=min(ans,dis(i,j));
cout<<ans;
}
D
https://codeforces.com/contest/1130/problem/D2
题意
给你一个有n(<=5000)个点的环，m颗糖果(m<=20000),有一辆车在这个环上顺时针跑，然后在每个点上有糖果，他们需要你用车将他们运到另一个点，限制是你在每一个点只能拿一个糖果,从一个点到另一个点需要一秒，分别输出从每个点开始运送完全部糖果最少需要多少时间
题解
- 每个点只能拿一个糖果
- 对于每个点，先拿距离远的，再拿距离近的（这样保证最后半圈的距离最小）
- 然后拿完每个点需要的最短时间，维护最大时间就是答案
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,x,y,ans;
vector<int>a[5005];
int dis(int x,int y){
if(x<=y)return y-x;
else return y-x+n;
}
bool cmp(int a,int b){
return dis(i,a)<dis(i,b);
}
int main(){
cin>>n>>m;
for(i=1;i<=m;i++){
cin>>x>>y;
a[x].push_back(y);
}
for(i=1;i<=n;i++)sort(a[i].begin(),a[i].end(),cmp);
for(i=1;i<=n;i++){
ans=0;
for(j=1;j<=n;j++){
if(a[j].size())ans=max((int)(n*(a[j].size()-1)+dis(j,a[j][0])+dis(i,j)),ans);
}
cout<<ans<<" ";
}
}
E
https://codeforces.com/contest/1130/problem/E
题意
一个长度为n的序列（n<=2000)，找出a[l,r]*(r-l+1)最大的连续子序列(a[i]<=1e6)，下面给你一个别人错误的程序
function find_answer(n, a)
# Assumes n is an integer between 1 and 2000, inclusive
# Assumes a is a list containing n integers: a[0], a[1], ..., a[n-1]
res = 0
cur = 0
k = -1
for i = 0 to i = n-1
cur = cur + a[i]
if cur < 0
cur = 0
k = i
res = max(res, (i-k)*cur)
return res
这时候给你一个x（x<=1e9), 你要构造一个上述要求的序列，使得标准程序和上述程序算出的答案相差x
题解
- 上述程序算法大概是一遇到和<0,就更新答案,并清零当前值,这个算法假如没有(r-l+1)这个加权是对的,这样可能存在a[l,r]比较小的正数,但是(r-l+1)比较大的区间没有考虑到
- 并不用去考虑标准程序是怎么写的,只需要专注于构造出符合答案的数据就行
- 假设第一项为-1,后面的和s保证>=1(直接令第二项为2,就可以保证),那么上述程序算出来的答案一定是(s*(n-1)),正确答案是((s-1)*n),得到等式((s-1)*n-s*(n-1)=x),化简得(s-n=x)
- 可以贪心+暴力找到n和a[]
代码
#include<bits/stdc++.h>
using namespace std;
int k,s,x;
vector<int>ans;
int main(){
cin>>k;
ans.push_back(-1);ans.push_back(2);
s=1;
while(1){
x=k-s+ans.size();
if(abs(x)<=1e6){ans.push_back(x);break;}
else {ans.push_back(1e6);s+=1e6;}
}
cout<<ans.size()<<endl;
for(auto x:ans)printf("%d ",x);
}