15.10.03【前缀和、Dijkstra、BFS+Kruskal+Lca】

  1. 1.NOIONI
  2. 2.蜜袋鼯
  3. 3.水壶

30+25+0

1.NOIONI

【题目描述】 NOIONI是NOI的叔叔。NOIONI先生很受欢迎,因为他的名字中N,O,I 各重复了两遍。最近NOIONI先生生了一个孩子(吓)。现在NOIONI先生打算给他的孩子取名字,他希望他的孩子的名字也由N,O,I 组成,而且每个字母重复的次数相同。NOIONI 先生找来了一个世代相传的手卷,手卷里写着一首由N,O,I组成的N个字符的诗,NOIONI先生打算从这个手卷里找出一个最长的子串,使得这个子串符合每个字母出现次数相同,并且尽可能的长,以此作为儿子的名字。

我开始想的就是把N、O、I各赋一个值,然后前缀和相差三数和的倍数的话就表示可以了,然而我还是用了n^2的算法 后来查了查,每个前缀和都mod(N、O、I的和)这样数一样就行,用map存下来前缀和第一次出现的位置,以后再出现就减去第一次就行了

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
int n,ans,sum[200001];
map<int,int> m;
char c;
int main()
{
freopen("noioni.in","r",stdin);
freopen("noioni.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>c;
if(c=='N') sum[i]=(sum[i-1]+1)%40000200001;
else if(c=='O') sum[i]=(sum[i-1]+200000)%40000200001;
else sum[i]=(sum[i-1]+40000000000)%40000200001;
if(m[sum[i]]==0) m[sum[i]]=i;
else if(i-m[sum[i]]>ans) ans=i-m[sum[i]];
}
printf("%d",ans);
}

正解: 考虑任意一个串都是两个前缀之差. 如果这个串要满足num(N)=num(O)=num(I),那么两个前缀num(N),num(O),num(I)的相对大小关系必须是相同的. 我们对于每个前缀记下num(N)-num(O),num(N)-num(I),然后利用map随便搞搞就行了.(什么叫随便搞搞。。。)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef pair<int,int> pii;
#define mp make_pair
#define N 200010
char s[N];
map<pii,int>M;
int main(){
int n;
scanf("%d",&n);
scanf("%s",s+1);
M[mp(0,0)]=0;
int J=0,O=0,I=0,ans=0;
for(int i=1;i<=n;++i){
if(s[i]=='J')
++J;
if(s[i]=='O')
++O;
if(s[i]=='I')
++I;
if(M.count(mp(J-O,J-I)))
ans=max(ans,i-M[mp(J-O,J-I)]);
else
M[mp(J-O,J-I)]=i;
}
cout<<ans<<endl;
return 0;
}

2.蜜袋鼯

【题目描述】 蜜袋鼯居住的森林里有N棵树。树从1标号到N,其中第i棵树的高度是Hi米。蜜袋鼯可以在其中M对树之间跳来跳去,在这些树之间跳跃需要花费Tj的时间。 而当蜜袋鼯在两棵树之间跳跃的时候,蜜袋鼯会以每秒1 米的速度下降,也就是说如果这次跳跃花了t的时间,跳之前的高度是h,跳之后的高度就是h-t. 显然,这个数值应该在0到目标树的高度之间。 蜜袋鼯可以在树上爬来爬去,也就是说如果这棵树的高度是Hi,这时候蜜袋鼯离地面的高度就可以在0到Hi之间变化。蜜袋鼯每秒可以爬1米。 最开始的时候,蜜袋鼯在第1棵树的X米处,他想知道,爬到第N棵树顶需要的最少时间是多少? 【输入格式】 第一行输入三个整数N,M,X, 分别表示树的数量,有M组树之间可以跳跃,最开始的高度是X. 接下来N行,其中第i行一个整数Hi表示第i棵树的高度。 接下来M行,其中第j行有三个整数Aj,Bj,Tj表示可以在树Aj和树Bj之间跳跃,需要花费Tj的时间。输入保证没有Aj=Bj , 也不会有重边。 【输出格式】 输出一个整数,表示从第i 棵树跳到第N 棵树的最短时间,无解输出-1.

暴力:每一棵树上的每一个高度建了一个点,过了25。。。

正解: 分3种情况: 1. 当到达目标后高度比树高的时候,先向下移动到移动后的高度是目标树的高度再过去 2. 当到达目标的高度在目标树的高度范围内,直接移动 3. 当到达目标的高度小于0的时候,调整当前高度使得移动后的高度大于等于0,再过去(如果不管怎么调整都移动不了就放弃)

用Dijkstra,SPFA有20分过不了。。。 好像是因为如果两种转移方式转移到同一棵树上的最小值相等时,两种情况都要考虑,但SPFA做不到。

#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N=100001;
vector<int> to[N],cost[N];
int n,m,X,a,b,tt,h[N],now;
long long ans,ds[N],inf;
struct node{
int x,g;long long d;
inline node(int a,int b,long long c):x(a),g(b),d(c){}
inline bool operator<(const node&t) const{return d>t.d;}
};
priority_queue<node> q;
int main()
{
freopen("sugar.in","r",stdin);
freopen("sugar.out","w",stdout);
scanf("%d%d%d",&n,&m,&X);
for(int i=1;i<=n;i++) scanf("%d",&h[i]);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&tt);
to[a].push_back(b);cost[a].push_back(tt);
to[b].push_back(a);cost[b].push_back(tt);
}
memset(ds,0x7f,sizeof(ds));inf=ds[0];ans=inf;
q.push(node(1,X,0));
while(!q.empty()){
node x=q.top(); q.pop();
if(ds[x.x]<inf) continue;
ds[x.x]=x.d;now=x.g;
if(x.x==n)
{long long a=h[n]-now+ds[n];if(a<ans) ans=a;}
for(int j=0;j<to[x.x].size();j++)
{
int y=to[x.x][j],t=cost[x.x][j],next=0,c=0;
if(now-t>=0&&now-t<=h[y]) c=t,next=now-t;
else if(now-t>h[y]) c=now-h[y],next=h[y];
else if(h[x.x]>=t) c=2*t-now,next=0;
else continue;
q.push(node(y,next,ds[x.x]+c));
}
}
/*while(!q.empty()) SPFA
{
int x=q.front(); q.pop(); vis[x]=0;
int now=q2.front(); q2.pop();
int maxx=0x7fffffff;
for(int i=0;i<to[x].size();i++)
{
int y=to[x][i],t=cost[x][i],next=0,c=0;
if(now-t>=0&&now-t<=h[y]) c=t,next=now-t;
else if(now-t>h[y]) c=now-h[y],next=h[y];
else if(h[x]>=t) c=2*t-now,next=0;
else continue;
if(ds[y]>ds[x]+c)
{
ds[y]=ds[x]+c;
if(y==n)
{long long a=h[n]-next+ds[n];if(a<ans) ans=a;}
if(!vis[y])
{
vis[y]=1;
q.push(y);q2.push(next);
}
}
}
}*/
if(ds[n]==inf) printf("-1");
else printf("%lld",ans);
}

3.水壶

【题目描述】 NOI所居住的IOI城全年都很热。IOI城是一个高H宽W的长方形城区,城区中有建筑物或者原野或者墙壁。有P个从1开始编号的建筑物。NOI只能在建筑和原野之间移动,如果两个建筑或者原野之间有共享的边,NOI就可以直接移动过去,NOI不能走出地图。 NOI需要在地图上跑来跑去。建筑物内是有空调的,但是,由于太阳太热了,所以在原野到原野之间行走时,每一步都需要喝1的水。此外,IOI 城的建筑物里有很多的饮水机或者自动售货机。而如果你拿着一个最大容积是x的水壶,你就可以在建筑物内把它装满。 带着水壶跑来跑去是很累的一件事情。所以,NOI希望能带着尽可能小的水壶。关于在一些建筑物之间移动的问题,我希望你写一个程序来寻找NOI 所需要的最小的水壶的容积大小。 【输入格式】 第一行四个整数H; W; P; Q, 用空格间隔。表示IOI 市的大小,建筑物的个数和询问个数。 接下来H行,第r行有W个字符,'.'表示建筑或者原野,'#'表示墙,其中第c个字符表示第r行第c列的地图。 接下来P行,第j行有两个整数Aj和Bj表示第Aj行,第Bj列这块空地是一个建筑物,保证这个位置在上面给出的地图是个'.'。 接下来Q行,第i行两个整数Si和Ti表示询问从第Si个建筑物到第Ti个建筑物需要的最小的水壶的容积。 【输出格式】 输出Q行,第i行一个整数表示从Si到Ti需要的最小的水壶的容积是多少,如果不能从Si到Ti则输出1, 类似,如果不需要在原野之间移动,那就输出0.

恕我暂且不会写。。。 题解:

标程:

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAXH = 2010;
const int MAXW = 2010;
const int MAXP = 200010;
const int HEIGHT = 20;
const int INF = 1000000000;
int H, W, P, Q;
int field[MAXH][MAXW];
char in[MAXW + 10];
int ax[] = {-1, 0, 0, 1}, ay[] = {0, -1, 1, 0};
pair<int, int> reg[MAXH][MAXW];
int uf[MAXP];
vector<int> tree[MAXP], dist[MAXP];
int depth[MAXP], up[MAXP][HEIGHT], upd[MAXP][HEIGHT];
int root(int p)
{
return uf[p] < 0 ? p : (uf[p] = root(uf[p]));
}
bool join(int p, int q)
{
p = root(p); q = root(q);
if(p == q) return false;
uf[p] += uf[q];
uf[q] = p;
return true;
}
void bfs()
{
queue<pair<int, int> > qu;
for(int i=0;i<H;i++) for(int j=0;j<W;j++){
if(field[i][j] < 0) reg[i][j] = make_pair(-1, -1);
else{
reg[i][j] = make_pair(0, field[i][j]);
qu.push(make_pair(i, j));
}
}
while(!qu.empty()){
pair<int, int> tmp = qu.front(); qu.pop();
int y = tmp.first, x = tmp.second;
for(int i=0;i<4;i++){
int y2 = y + ay[i], x2 = x + ax[i];
if(y2 < 0 || x2 < 0 || y2 >= H || x2 >= W) continue;
if(reg[y2][x2].first != -1 || field[y2][x2] == -2) continue;
reg[y2][x2] = make_pair(reg[y][x].first + 1, reg[y][x].second);
qu.push(make_pair(y2, x2));
}
}
}
void add_edge(int x, int y, int d)
{
tree[x].push_back(y);
tree[y].push_back(x);
dist[x].push_back(d);
dist[y].push_back(d);
}
void visit(int p, int r, int d)
{
if(r == -1){
for(int i=0;i<HEIGHT;i++){
up[p][i] = -1;
}
depth[p] = 0;
}else{
up[p][0] = r; upd[p][0] = d;
depth[p] = depth[r] + 1;
for(int i=1;i<HEIGHT;i++){
if(up[p][i-1] == -1) up[p][i] = -1;
else{
up[p][i] = up[up[p][i-1]][i-1];
upd[p][i] = max(upd[p][i-1], upd[up[p][i-1]][i-1]);
}
}
}
for(int i=0;i<tree[p].size();i++) if(tree[p][i] != r) visit(tree[p][i], p, dist[p][i]);
}
void make_MST()
{
vector<pair<int, pair<int, int> > > cand;
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(field[i][j] == -2) continue;
if(i < H-1 && field[i+1][j] != -2 && reg[i][j].second != reg[i+1][j].second)
cand.push_back(make_pair(reg[i][j].first + reg[i+1][j].first, make_pair(reg[i][j].second, reg[i+1][j].second)));
if(j < W-1 && field[i][j+1] != -2 && reg[i][j].second != reg[i][j+1].second)
cand.push_back(make_pair(reg[i][j].first + reg[i][j+1].first, make_pair(reg[i][j].second, reg[i][j+1].second)));
}
}
sort(cand.begin(), cand.end());
for(int i=0;i<P;i++) uf[i] = -1;
for(int i=0;i<cand.size();i++){
int x=cand[i].second.first, y=cand[i].second.second, d=cand[i].first;
if(join(x, y)){
add_edge(x, y, d);
}
}
for(int i=1;i<P;i++){
if(join(i-1, i)) add_edge(i-1, i, INF);
}
visit(0, -1, 0);
}
int solve(int p, int q)
{
if(depth[p] > depth[q]) swap(p, q);
int ret = 0;
for(int i=HEIGHT-1;i>=0;i--) if(depth[q] - (1<<i) >= depth[p]){
ret = max(ret, upd[q][i]);
q = up[q][i];
}
if(p == q) return ret;
for(int i=HEIGHT-1;i>=0;i--){
if(up[p][i] != up[q][i]){
ret = max(ret, max(upd[p][i], upd[q][i]));
p = up[p][i];
q = up[q][i];
}
}
ret = max(ret, max(upd[p][0], upd[q][0]));
return ret;
}
int main()
{
freopen("bottle.in", "r", stdin);
freopen("bottle.out", "w", stdout);
scanf("%d%d%d%d", &H, &W, &P, &Q);
for(int i=0;i<H;i++){
scanf("%s", in);
for(int j=0;j<W;j++){
if(in[j] == '.') field[i][j] = -1;
else field[i][j] = -2;
}
}
for(int i=0;i<P;i++){
int a, b;
scanf("%d%d", &a, &b);
--a; --b;
field[a][b] = i;
}
bfs();
make_MST();
for(int i=0;i<Q;i++){
int s, t;
scanf("%d%d", &s, &t);
--s; --t;
int ret = solve(s, t);
if(ret == INF) ret = -1;
printf("%d\n", ret);
}
return 0;
}