快noip了就乱做一下历年的noip题目咯..
noip2014 飞扬的小鸟
其实这道题并不是很难，但是就有点难搞 听说男神错了一个小时..
就是$f_{i,j}$表示在第$i$个位置高度为$j$的时候最小点击次数
递推的话对于上升的情况只做一次，后面几次在后面再做..
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int Maxn = 10010;
const int Maxm = 1010;
const int inf = 1e9;
int f[2][Maxm];
int n, m, K;
int l[Maxn], u[Maxn]; bool p[Maxn];
int X[Maxn], Y[Maxn];
int _min ( int x, int y ){ return x < y ? x : y; }
int main (){
int i, j, k;
scanf ( "%d%d%d", &n, &m, &K );
l[0] = 0; u[0] = m+1;
for ( i = 1; i <= n; i ++ ){ scanf ( "%d%d", &X[i], &Y[i] ); l[i] = 0; u[i] = m+1; }
for ( i = 1; i <= K; i ++ ){
int x;
scanf ( "%d", &x );
p[x] = true;
scanf ( "%d%d", &l[x], &u[x] );
}
int st = 0;
for ( i = 0; i <= m; i ++ ) f[st][i] = 0;
int num = 0;
for ( i = 1; i <= n; i ++ ){
st = st^1;
for ( j = 0; j <= m; j ++ ) f[st][j] = inf;
bool bk = false;
for ( j = l[i-1]+1; j < u[i-1]; j ++ ){
if ( f[st^1][j] == inf ) continue;
bk = true;
f[st][_min(j+X[i],m)] = _min ( f[st][_min(j+X[i],m)], f[st^1][j]+1 );
}
for ( j = 0; j <= m; j ++ ){
if ( f[st][j] != inf ) f[st][_min(j+X[i],m)] = _min ( f[st][_min(j+X[i],m)], f[st][j]+1 );
}
for ( j = l[i-1]+1; j < u[i-1]; j ++ ){
if ( f[st^1][j] == inf ) continue;
if ( j-Y[i] > l[i] && j-Y[i] < u[i] ) f[st][j-Y[i]] = _min ( f[st][j-Y[i]], f[st^1][j] );
}
if ( bk == false ){ printf ( "0\n%d\n", num-1 ); return 0; }
if ( p[i] == true ) num ++;
}
int ans = inf;
for ( i = 1; i <= m; i ++ ) ans = _min ( ans, f[st][i] );
printf ( "1\n%d\n", ans );
return 0;
}
noip2013 货车运输
就是裸的最大瓶颈树..
通俗点说就是最大生成树再用st表维护一下路径最小值..
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int Maxn = 10010;
const int Maxm = 50010;
struct node {
int y, next, d;
}a[Maxn*2]; int first[Maxn], len;
void ins ( int x, int y, int d ){
len ++;
a[len].y = y; a[len].d = d;
a[len].next = first[x]; first[x] = len;
}
struct lnode {
int x, y, d;
}list[Maxm];
bool cmp ( lnode x, lnode y ){ return x.d > y.d; }
int n, m, q;
int fa[Maxn]; bool fw[Maxn];
int ff ( int x ){
if ( fa[x] == x ) return x;
return fa[x] = ff (fa[x]);
}
int minn[Maxn][15], fat[Maxn][15], dep[Maxn];
int _min ( int x, int y ){ return x < y ? x : y; }
void dfs ( int x, int f ){
fw[x] = true;
for ( int i = 1; i <= 14; i ++ ){
fat[x][i] = fat[fat[x][i-1]][i-1];
minn[x][i] = _min ( minn[x][i-1], minn[fat[x][i-1]][i-1] );
}
for ( int k = first[x]; k; k = a[k].next ){
int y = a[k].y;
if ( y == f ) continue;
fat[y][0] = x;
minn[y][0] = a[k].d;
dep[y] = dep[x]+1;
dfs ( y, x );
}
}
int lca ( int x, int y ){
int ret = 0x7fffffff;
if ( dep[x] < dep[y] ) swap ( x, y );
for ( int i = 14; i >= 0; i -- ){
if ( dep[fat[x][i]] >= dep[y] ){
ret = _min ( ret, minn[x][i] );
x = fat[x][i];
}
}
if ( x == y ) return ret;
for ( int i = 14; i >= 0; i -- ){
if ( fat[x][i] != fat[y][i] ){
ret = _min ( ret, minn[x][i] );
ret = _min ( ret, minn[y][i] );
x = fat[x][i]; y = fat[y][i];
}
}
return _min ( ret, _min ( minn[x][0], minn[y][0] ) );
}
int main (){
int i, j, k;
scanf ( "%d%d", &n, &m );
for ( i = 1; i <= m; i ++ ){
scanf ( "%d%d%d", &list[i].x, &list[i].y, &list[i].d );
}
sort ( list+1, list+m+1, cmp );
for ( i = 1; i <= n; i ++ ) fa[i] = i;
for ( i = 1; i <= m; i ++ ){
int fx = ff (list[i].x), fy = ff (list[i].y);
if ( fx != fy ){
fa[fy] = fx;
ins ( list[i].x, list[i].y, list[i].d );
ins ( list[i].y, list[i].x, list[i].d );
}
}
for ( i = 1; i <= n; i ++ ){
if ( fw[i] == false ){ dep[i] = 1; dfs ( i, 0 ); }
}
scanf ( "%d", &q );
for ( i = 1; i <= q; i ++ ){
int x, y;
scanf ( "%d%d", &x, &y );
int fx = ff (x), fy = ff (y);
if ( fx != fy ) printf ( "-1\n" );
else printf ( "%d\n", lca ( x, y ) );
}
return 0;
}
noip2015 跳石头
二分答案，然后找第一个距离超过这个答案的使用，扫一遍即可
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int Maxn = 50010;
int a[Maxn], n, m, L;
int main (){
int i, j, k;
scanf ( "%d%d%d", &L, &n, &m );
for ( i = 1; i <= n; i ++ ) scanf ( "%d", &a[i] );
a[++n] = L;
int l = 1, r = L, ret;
while ( l <= r ){
int mid = ( l + r ) >> 1;
int last = 0, sum = 0;
for ( i = 1; i <= n; i ++ ){
if ( a[i]-last >= mid ) last = a[i];
else sum ++;
}
if ( sum <= m ){ ret = mid; l = mid+1; }
else r = mid-1;
}
printf ( "%d\n", ret );
return 0;
}
noip2015 子串
哇我去年居然会做这道题 然而我现在好像不会了..
$f_{i,j,k}$表示现在在第$i$块，小串匹配到$j$，大串匹配到$k$的方案数
然后就可以这样搞：$$f_{i,j,k}=\sum\limits_{p=0}^{k-1}f_{i-1,j-1,p}+f_{i,j-1,k-1}\times (s2[j-1]==s1[k-1])$$
那么对于前面的只要维护一个前缀和就可以了..
再给一道题吧，也是前缀和相关：CodeForces 587B 记得当年就是从这题吸取了经验的（感谢胖涛..）
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int Maxn = 1010;
const int Maxm = 210;
const int Mod = 1000000007;
char a[Maxn], b[Maxm];
int n, m, K;
int f[2][Maxm][Maxn];
int main (){
int i, j, k;
scanf ( "%d%d%d", &n, &m, &K );
scanf ( "%s", a+1 );
scanf ( "%s", b+1 );
int st = 0;
for ( i = 0; i <= n; i ++ ) f[0][0][i] = 1;
for ( k = 1; k <= K; k ++ ){
st = st^1;
memset ( f[st], 0, sizeof (f[st]) );
for ( i = 1; i <= m; i ++ ){
for ( j = 1; j <= n; j ++ ){
if ( b[i] == a[j] ){
f[st][i][j] = ( f[st][i][j] + f[st^1][i-1][j-1] ) % Mod;
if ( b[i-1] == a[j-1] ) f[st][i][j] = ( f[st][i][j] + f[st][i-1][j-1] ) % Mod;
}
}
}
for ( i = 1; i <= m; i ++ ){
for ( j = 1; j <= n; j ++ ) f[st][i][j] = ( f[st][i][j] + f[st][i][j-1] ) % Mod;
}
}
printf ( "%d\n", f[st][m][n] );
return 0;
}
noip2015 运输计划
先预处理每条路径长度，找出最长的那条记为$ss$
二分答案，超过该答案的路径在树上差分标记一下，那么如果某个点子树所有标记和等于超过的路径数，证明该点与其父亲的边可能要割
然后在这些边中找到最大值，看$ss$减去这个值是否在二分的答案以内就行了
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int Maxn = 300010;
struct node {
int y, next, d;
}a[Maxn*2]; int first[Maxn], len;
void ins ( int x, int y, int d ){
len ++;
a[len].y = y; a[len].d = d;
a[len].next = first[x]; first[x] = len;
}
int n, m;
int fa[Maxn][23], sum[Maxn][23], dep[Maxn];
void dfs ( int x, int f ){
for ( int i = 1; i <= 22; i ++ ){
fa[x][i] = fa[fa[x][i-1]][i-1];
sum[x][i] = sum[x][i-1] + sum[fa[x][i-1]][i-1];
}
for ( int k = first[x]; k; k = a[k].next ){
int y = a[k].y;
if ( y == f ) continue;
fa[y][0] = x;
sum[y][0] = a[k].d;
dep[y] = dep[x]+1;
dfs ( y, x );
}
}
struct qnode {
int x, y, lca, dist;
}q[Maxn];
void get_lca ( qnode &p ){
int x = p.x, y = p.y;
p.dist = 0;
if ( dep[x] < dep[y] ) swap ( x, y );
for ( int i = 22; i >= 0; i -- ){
if ( dep[fa[x][i]] >= dep[y] ){
p.dist += sum[x][i];
x = fa[x][i];
}
}
if ( x == y ){ p.lca = x; return; }
for ( int i = 22; i >= 0; i -- ){
if ( fa[x][i] != fa[y][i] ){
p.dist += sum[x][i];
p.dist += sum[y][i];
x = fa[x][i];
y = fa[y][i];
}
}
p.dist += sum[x][0]+sum[y][0];
p.lca = fa[x][0];
}
int bj[Maxn];
int _max ( int x, int y ){ return x > y ? x : y; }
int DFS ( int x, int f, int mid ){
int ret = -1;
for ( int k = first[x]; k; k = a[k].next ){
int y = a[k].y;
if ( y == f ) continue;
ret = _max ( DFS ( y, x, mid ), ret );
if ( bj[y] == mid ) ret = _max ( ret, a[k].d );
bj[x] += bj[y];
}
return ret;
}
int main (){
int i, j, k;
scanf ( "%d%d", &n, &m );
for ( i = 1; i < n; i ++ ){
int x, y, d;
scanf ( "%d%d%d", &x, &y, &d );
ins ( x, y, d ); ins ( y, x, d );
}
dfs ( 1, 0 );
int ss = 0;
for ( i = 1; i <= m; i ++ ){
scanf ( "%d%d", &q[i].x, &q[i].y );
get_lca (q[i]);
ss = _max ( ss, q[i].dist );
}
int l = 1, r = ss, ret;
while ( l <= r ){
int mid = ( l + r ) >> 1;
int ssum = 0;
for ( i = 1; i <= n; i ++ ) bj[i] = 0;
for ( i = 1; i <= m; i ++ ){
if ( q[i].dist > mid ){
bj[q[i].x] ++; bj[q[i].y] ++;
bj[q[i].lca] -= 2;
ssum ++;
}
}
if ( ss-DFS ( 1, 0, ssum ) <= mid ){ ret = mid; r = mid-1; }
else l = mid+1;
}
printf ( "%d\n", ret );
return 0;
}
noip2013 华容道
记录f[i][j][k][l]为被标记的点在(i,j)，空白点在k方向，使其移动到l方向的最小步数
这个东西是可以在$O(n^4)$预处理出来的
那么对于每一个询问，先算出空白点移动到标记点4个方向上的步数，然后就是最短路的事情了
推荐使用dijkstra算法，能够保证在$O(qn^2logn^2)$内算出..
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
const int dx[4] = { 0, 1, -1, 0 };
const int dy[4] = { 1, 0, 0, -1 };
const int inf = 0x7fffffff;
int f[35][35][4][4], num[35][35][4], tot;
int dis[4010];
bool v[35][35];
int n, m, q;
int dist[35][35]; bool bo[35][35];
struct zb {
int x, y;
}e, s, t;
void bfs1 ( int xx, int yy, int k ){
queue <zb> q;
for ( int i = 0; i <= n+1; i ++ ) for ( int j = 0; j <= m+1; j ++ ) dist[i][j] = inf, bo[i][j] = false;
zb x;
x.x = xx+dx[k]; x.y = yy+dy[k];
q.push (x);
dist[x.x][x.y] = 0; bo[x.x][x.y] = true;
while ( !q.empty () ){
x = q.front (); q.pop ();
for ( int i = 0; i < 4; i ++ ){
zb y;
y.x = x.x+dx[i]; y.y = x.y+dy[i];
if ( v[y.x][y.y] == false || bo[y.x][y.y] == true ) continue;
dist[y.x][y.y] = dist[x.x][x.y]+1;
bo[y.x][y.y] = true;
q.push (y);
}
}
for ( int i = 0; i < 4; i ++ ){
f[xx][yy][k][i] = dist[xx+dx[i]][yy+dy[i]];
}
}
void bfs2 (){
queue <zb> q;
for ( int i = 0; i <= n+1; i ++ ) for ( int j = 0; j <= m+1; j ++ ) dist[i][j] = inf, bo[i][j] = false;
q.push (e);
dist[e.x][e.y] = 0; bo[e.x][e.y] = true;
while ( !q.empty () ){
zb x = q.front (); q.pop ();
for ( int i = 0; i < 4; i ++ ){
zb y;
y.x = x.x+dx[i]; y.y = x.y+dy[i];
if ( v[y.x][y.y] == false || bo[y.x][y.y] == true ) continue;
dist[y.x][y.y] = dist[x.x][x.y]+1;
bo[y.x][y.y] = true;
q.push (y);
}
}
}
struct node {
int y, next, d;
}a[160010]; int first[4010], len;
void ins ( int x, int y, int d ){
len ++;
a[len].y = y; a[len].d = d;
a[len].next = first[x]; first[x] = len;
}
struct knode {
int x, dis;
};
bool operator < ( knode x, knode y ){ return x.dis > y.dis; }
priority_queue <knode> Q;
void dij (){
while ( !Q.empty () ){
knode x = Q.top (); Q.pop ();
if ( dis[x.x] < x.dis ) continue;
for ( int k = first[x.x]; k; k = a[k].next ){
int y = a[k].y;
if ( dis[y] > dis[x.x]+a[k].d ){
dis[y] = dis[x.x]+a[k].d;
knode p;
p.x = y; p.dis = dis[y];
Q.push (p);
}
}
}
}
int _min ( int x, int y ){ return x < y ? x : y; }
int main (){
int i, j, k;
scanf ( "%d%d%d", &n, &m, &q );
for ( i = 1; i <= n; i ++ ){
for ( j = 1; j <= m; j ++ ){
int x;
scanf ( "%d", &x );
if ( x == 1 ) v[i][j] = true;
}
}
tot = 0;
for ( i = 1; i <= n; i ++ ){
for ( j = 1; j <= m; j ++ ){
if ( v[i][j] == false ) continue;
for ( k = 0; k < 4; k ++ ){
if ( v[i+dx[k]][j+dy[k]] == true ){
v[i][j] = false;
bfs1 ( i, j, k );
v[i][j] = true;
num[i][j][k] = ++tot;
}
else for ( int l = 0; l < 4; l ++ ) f[i][j][k][l] = inf;
}
}
}
while ( q -- ){
scanf ( "%d%d%d%d%d%d", &e.x, &e.y, &s.x, &s.y, &t.x, &t.y );
if ( s.x == t.x && s.y == t.y ){ printf ( "0\n" ); continue; }
v[s.x][s.y] = false;
bfs2 ();
v[s.x][s.y] = true;
for ( j = 1; j <= tot; j ++ ) first[j] = 0, dis[j] = inf;
len = 0;
for ( j = 0; j < 4; j ++ ){
if ( dist[s.x+dx[j]][s.y+dy[j]] != inf ){
knode p;
p.x = num[s.x][s.y][j]; p.dis = dist[s.x+dx[j]][s.y+dy[j]];
Q.push (p);
dis[num[s.x][s.y][j]] = dist[s.x+dx[j]][s.y+dy[j]];
}
}
for ( i = 1; i <= n; i ++ ){
for ( j = 1; j <= m; j ++ ){
for ( k = 0; k < 4; k ++ ){
if ( v[i+dx[k]][j+dy[k]] == true ){
for ( int l = 0; l < 4; l ++ ){
if ( f[i][j][k][l] != inf ) ins ( num[i][j][k], num[i][j][l], f[i][j][k][l] );
}
ins ( num[i][j][k], num[i+dx[k]][j+dy[k]][3-k], 1 );
}
}
}
}
dij ();
int ans = inf;
for ( i = 0; i < 4; i ++ ){
if ( num[t.x][t.y][i] != 0 ) ans = _min ( ans, dis[num[t.x][t.y][i]] );
}
if ( ans != inf ) printf ( "%d\n", ans );
else printf ( "-1\n" );
}
return 0;
}
noip2011 选择客栈
一开始看错题了.. 做法其实没啥区别就是强行解释一下
由于题目给出的$p$是不会变的，然后就可以瞎搞处理了，时间复杂度是$O(k*小于等于p的节点数)$
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int Maxc = 55;
int c[Maxc], ans[Maxc];
int n, K, p;
int main (){
int i, j, k;
scanf ( "%d%d%d", &n, &K, &p );
int anss = 0;
for ( i = 1; i <= n; i ++ ){
int fl, x;
scanf ( "%d%d", &fl, &x );
c[fl] ++;
if ( x <= p ){
for ( j = 0; j < K; j ++ ) ans[j] = c[j];
}
anss += ans[fl];
if ( x <= p ) anss --;
}
printf ( "%d\n", anss );
return 0;
}
noip2012 开车旅行
由于两人决策唯一性，那么可以预处理出从某点开始走$2^i$步到达的点..
讲道理的话其实也就只需要处理$f_{i,0}$和$f_{i,1}$，后面的都可以倍增求
第一问就枚举点倍增搞
其他问就直接跑..
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <set>
#define LL long long
using namespace std;
const int Maxn = 100010;
const int inf = 0x7fffffff;
struct no {
int x, h;
};
bool operator < ( no x, no y ){ return x.h < y.h; }
set <no> S;
set <no> :: iterator it;
int h[Maxn], n, m;
int fa[Maxn][22], fb[Maxn][22], f[Maxn][22];
no gob[Maxn];
void pre (){
int i, j, k;
no p;
p.x = n; p.h = h[n];
S.insert (p);
for ( i = n-1; i >= 1; i -- ){
p.x = i; p.h = h[i];
it = S.lower_bound (p);
no fir, sec;
fir.h = inf; sec.h = inf;
if ( it != S.end () ){
fir.x = (*it).x; fir.h = (*it).h-h[i];
it ++;
if ( it != S.end () ) sec.x = (*it).x, sec.h = (*it).h-h[i];
it --;
}
if ( it != S.begin () ){
it --;
if ( h[i]-(*it).h <= fir.h ){
sec = fir;
fir.x = (*it).x; fir.h = h[i]-(*it).h;
}
else if ( h[i]-(*it).h <= sec.h ){
sec.x = (*it).x; sec.h = h[i]-(*it).h;
}
if ( it != S.begin () ){
it --;
if ( h[i]-(*it).h <= sec.h ){
sec.x = (*it).x; sec.h = h[i]-(*it).h;
}
}
}
if ( sec.h != inf ){
f[i][0] = sec.x; f[i][1] = gob[sec.x].x;
fa[i][0] = fa[i][1] = sec.h;
fb[i][0] = 0; fb[i][1] = gob[sec.x].h;
for ( j = 2; j <= 21 && i+(1<<(j-1)) <= n; j ++ ){
f[i][j] = f[f[i][j-1]][j-1];
fa[i][j] = fa[i][j-1] + fa[f[i][j-1]][j-1];
fb[i][j] = fb[i][j-1] + fb[f[i][j-1]][j-1];
}
}
if ( fir.h != inf ) gob[i] = fir;
S.insert (p);
}
}
struct node {
int na, nb;
};
void gogogo ( int st, int xx, node &jl ){
jl.na = jl.nb = 0;
int i;
for ( i = 21; i >= 0; i -- ){
if ( fa[st][i]+fb[st][i] <= xx && f[st][i] != 0 ){
jl.na += fa[st][i];
jl.nb += fb[st][i];
xx -= fa[st][i]+fb[st][i];
st = f[st][i];
}
}
}
int main (){
int i, j, k;
scanf ( "%d", &n );
for ( i = 1; i <= n; i ++ ) scanf ( "%d", &h[i] );
pre ();
int x0, s0;
scanf ( "%d", &x0 );
s0 = n; node ans, po;
ans.na = ans.nb = 0;
for ( i = n-1; i >= 1; i -- ){
gogogo ( i, x0, po );
if ( (LL)po.na*ans.nb < (LL)ans.na*po.nb || ( (LL)po.na*ans.nb == (LL)ans.na*po.nb && h[i] > h[s0] ) || s0 == n || ( ans.nb == 0 && po.nb != 0 ) ){
s0 = i;
ans = po;
}
}
printf ( "%d\n", s0 );
scanf ( "%d", &m );
for ( i = 1; i <= m; i ++ ){
int ss, xx;
scanf ( "%d%d", &ss, &xx );
gogogo ( ss, xx, po );
printf ( "%d %d\n", po.na, po.nb );
}
return 0;
}
noip2011 观光公交
记录$time_i$是到达$i$点的最小时刻，$last_i$是最迟一个到达$i$点的人的时刻
那么$time_i=\max(time_{i-1},last_{i-1})+d_i$
可以处理出修改每一个$d_i$所影响的人数
每次贪心找一个最大的减去就好了
时间复杂度是$O(nk)$的..
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int Maxn = 100010;
int time[Maxn], d[Maxn], last[Maxn];
int n, m, K;
struct lnode {
int st, ed, t;
}list[Maxn];
int sum[Maxn], f[Maxn];
int _max ( int x, int y ){ return x > y ? x : y; }
int main (){
int i, j, k;
scanf ( "%d%d%d", &n, &m, &K );
for ( i = 2; i <= n; i ++ ) scanf ( "%d", &d[i] );
for ( i = 1; i <= m; i ++ ){
scanf ( "%d%d%d", &list[i].t, &list[i].st, &list[i].ed );
last[list[i].st] = _max ( last[list[i].st], list[i].t );
sum[list[i].ed] ++;
}
time[1] = 0;
for ( i = 2; i <= n; i ++ ){
time[i] = _max ( time[i-1], last[i-1] ) + d[i];
sum[i] += sum[i-1];
}
int ans = 0;
for ( i = 1; i <= m; i ++ ){
ans += time[list[i].ed] - list[i].t;
}
while ( K -- ){
f[n] = n;
for ( i = n-1; i >= 2; i -- ){
if ( time[i] > last[i] ) f[i] = f[i+1];
else f[i] = i;
}
int Max = 0, p;
for ( i = 2; i <= n; i ++ ){
if ( sum[f[i]]-sum[i-1] > Max && d[i] > 0 ){
Max = sum[f[i]]-sum[i-1];
p = i;
}
}
ans -= Max; d[p] --;
for ( i = 2; i <= n; i ++ ){
time[i] = _max ( time[i-1], last[i-1] ) + d[i];
}
}
printf ( "%d\n", ans );
return 0;
}