[LibreOJ 2316][NOIP2017]逛公园
给你一张\(n\)个点\(m\)条边的有向图，设从\(1\)到\(n\)的最短路为\(d\)，那么请问有多少\(1\)到\(n\)的路径（可以是非简单路径）满足其长度在\([d, d + K]\)中，如果答案为无限大的话输出\(-1\)。
\(1\leq n\leq 10^5, 1\leq m\leq 2\times 10^5, 0\leq K\leq 50\)。
[UOJ 333][NOIP2017]宝藏
啊啊啊爽到力，，，
过去太池沼力，没有做出来惹。现在看了看可能比较简单罢……
定义状态\(d_{i, S}\)表示当前已经被覆盖的点集为\(S\)，然后当前的生成树已经考虑到了第\(i\)层，转移看起来很毒……
所以预处理一个点集到另一个点集只走一步边来扩展，最优解是多少，然后转移就方便力……
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
const int maxn = 12;
int G[15][15];
const int INF = 0x3f3f3f3f;
void add_edge(int u, int v, int d) {
G[u][v] = std::min(G[u][v], d);
G[v][u] = std::min(G[v][u], d);
}
int n;
int g1[(1 << maxn)][15], g2[(1 << maxn)][(1 << maxn)];
void process() {
for(int s = 1; s < (1 << n); s ++) {
for(int i = 1; i <= n; i ++) {
g1[s][i] = INF;
for(int j = 0; j < n; j ++) {
if((1 << j) & s) {
g1[s][i] = std::min(g1[s][i], G[j + 1][i]);
}
}
}
}
for(int s = 1; s < (1 << n); s ++) {
int k = (1 << n) - 1; k = k & (~s);
for(int t = k; t > 0; t = (t - 1) & k) {
g2[s][t] = 0;
for(int i = 1; i <= n; i ++) {
if((1 << (i - 1)) & t) {
if(g1[s][i] == INF) {
g2[s][t] = INF; break;
}
g2[s][t] += g1[s][i];
}
}
}
}
}
using ll = long long;
ll d[14][(1 << maxn)];
ll dp() {
for(int s = 0; s < (1 << n); s ++) {
d[1][s] = INF;
}
for(int i = 0; i < n; i ++) {
d[1][(1 << i)] = 0;
}
for(int i = 2; i <= n; i ++) {
for(int s = 1; s < (1 << n); s ++) {
d[i][s] = INF;
for(int t = (s - 1) & s; t != 0; t = (t - 1) & s) {
d[i][s] = std::min(d[i][s], d[i - 1][t] + (ll(i - 1)) * g2[t][s ^ t]);
}
}
}
ll ans = INF;
for(int i = 1; i <= n; i ++) {
ans = std::min(ans, d[i][(1 << n) - 1]);
}
return ans;
}
int main() {
memset(G, 0x3f, sizeof(G));
int m; scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
add_edge(u, v, w);
}
process(); printf("%lld\n", dp());
return 0;
}
[CodeVS 1217]借教室
很容易想到线段树水过。
很可惜，这样估计也就70分。
然后这个问题是符合单调性的……可以二分答案哒。不过怎么判定？
不知道诸位还记得差分序列？记得就好，用差分序列的方法维护即可。
等等，我怎么感觉你这个做法是[tex]O(nlogn)[/tex]的，能过？
推荐一个行之有效的优化：注意一下每一次修改都是在之前的基础上反悔或前进几次，所以就可以直接在原基础上修改差分序列辣~这样效率是很高滴~
代码：
#include <cstdio>
const int maxn=1e6+5;
typedef long long ll;
ll A[maxn];
int l[maxn],r[maxn];
ll d[maxn];
ll C[maxn];
int n,m,last=0;
bool Check(int x){
register int i,cnt=0;
if(x>last)
for(i=last+1;i<=x;i++){
C[l[i]]+=d[i];
C[r[i]+1]-=d[i];
}
if(x<last)
for(i=x+1;i<=last;i++){
C[l[i]]-=d[i];
C[r[i]+1]+=d[i];
}
last=x;
for(i=1;i<=n;i++){
cnt+=C[i];
if(cnt>A[i])
return false;
}
return true;
}
int main(){
register int i,L,M,R;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%lld",&A[i]);
}
for(i=1;i<=m;i++){
scanf("%lld%d%d",&d[i],&l[i],&r[i]);
}
L=1;
R=m+1;
while(L<R){
M=L+(R-L)/2;
if(Check(M)){
L=M+1;
}else{
R=M;
}
}
if(L==m+1)
puts("0");
else
printf("-1\n%d\n",L);
return 0;
}
[CodeVS 3729]飞扬的小鸟
论如何把一个完全背包出的高大上……
这个题啊……细节特别多……
首先，不建议开滚动数组，细节处理就会疯。
然后呢……真的不太好说了……还是看代码吧（尽管代码还是有明显的滚动数组痕迹）。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=1005;
const int INF=0x7f7f7f7f;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
int GZ[maxn][2];
bool haveGZ[maxn];
int A[maxn][2];
int d[maxn][maxm];
int main(){
int n,m,k,temp;
register int i,j,v,now,pre,ans=INF,cnt;
scanf("%d%d%d",&n,&m,&k);
cnt=k;
REP(i,n){
scanf("%d%d",&A[i][0],&A[i][1]);
}
for(i=0;i<=n;i++){
GZ[i][0]=0;
GZ[i][1]=m+1;
}
REP_B(i,k){
scanf("%d",&temp);
haveGZ[temp]=true;
scanf("%d%d",&GZ[temp][0],&GZ[temp][1]);
}
memset(d,0x7f,sizeof(d));
memset(d[0],0,sizeof(d[0]));
d[0][0]=INF;
REP_B(i,n){
now=i;
pre=i-1;
d[now][0]=INF;
int& X=A[i-1][0];
int& Y=A[i-1][1];
REP_B(j,m){
if(j-X>0 && d[pre][j-X]<INF)
d[now][j]=min(d[now][j],d[pre][j-X]+1);
if(j-X>0 && d[now][j-X]<INF)
d[now][j]=min(d[now][j],d[now][j-X]+1);
if(j==m)
for(v=j-X;v<=m;v++){
if(d[pre][v]<INF)
d[now][j]=min(d[now][j],d[pre][v]+1);
if(d[now][v]<INF)
d[now][j]=min(d[now][j],d[now][v]+1);
}
}
for(j=GZ[i][0]+1;j<GZ[i][1];j++){
if(j+Y<=m && d[pre][j+Y]<INF)
d[now][j]=min(d[now][j],d[pre][j+Y]);
}
if(haveGZ[i]){
REP_B(j,GZ[i][0])
if(d[now][j]<INF){
d[now][j]=INF;
}
for(j=GZ[i][1];j<=m;j++)
if(d[now][j]<INF){
d[now][j]=INF;
}
}
}
for(i=n;i>=1;i--){
for(j=m;j>=1;j--){
ans=min(ans,d[i][j]);
}
if(ans<INF)
break;
if(haveGZ[i])
cnt--;
}
if(cnt==k){
printf("1\n%d\n",ans);
}else{
printf("0\n%d\n",cnt);
}
return 0;
}
[BZOJ 4326]运输计划
很容易想到树剖直接搞一发的玩法。估计复杂度是[tex]O(nlog^2n)[/tex]的，有点吃不消，再加上会被卡常，咔嚓掉。
考虑二分答案。我们可以直接二分最终答案，那么如何验证？
假设验证谓词为[tex]C(t)[/tex]，表示通过把一条边清零可以使得用时为[tex]t[/tex]。那么所有用时大于[tex]t[/tex]的计划都要被清掉一条边。可见我们需要清零的边是所有用时大于[tex]t[/tex]的计划的边的交集中的最大边。
那么如何求交集呢？可以考虑树上差分，对于每次计划[tex](u,v)[/tex]，我们求出其最近公共祖先[tex]L[/tex]，然后对[tex]d[u][/tex]和[tex]d[v][/tex]分别加一，对[tex]d[L][/tex]则减二。随后将d上标记上推，可以求出每个点连向父亲的边被几个计划经过。易求交集。
至此方向已明确：二分答案，树上差分验证，同时我们还要用到LCA。LCA建议使用总计[tex]O(n)[/tex]的TarjanLCA离线算法，倍增也可。
代码：
/**************************************************************
Problem: 4326
User: danihao123
Language: C++
Result: Accepted
Time:4756 ms
Memory:62188 kb
****************************************************************/
#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=300001,maxm=300001*2;
const int BUFSIZE=10000001;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CUS_REP(i,a,b) for(i=(a);i<=(b);i++)
int n;
namespace FastIO{
char buf[BUFSIZE];
int IO_tot=0;
inline void InitFastIO(){
fread(buf,sizeof(char),BUFSIZE-1,stdin);
}
inline char GetC(){
return buf[IO_tot++];
}
inline int readint(){
register int x=0;
register char c=GetC();
while(!isdigit(c))
c=GetC();
while(isdigit(c)){
x=10*x+c-'0';
c=GetC();
}
return x;
}
int bf[10];
inline void putint(int x){
register int siz=0,i;
if(!x){
bf[siz++]=0;
}else{
while(x){
bf[siz++]=x%10;
x/=10;
}
}
for(i=siz-1;i>=0;i--)
putchar(bf[i]+'0');
putchar('\n');
}
};
namespace Tree{
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int tot=0;
inline void Add_Edge(int u,int v,int d){
tot++;
next[tot]=first[u];
first[u]=tot;
to[tot]=v;
dist[tot]=d;
}
int d[maxn],father[maxn];
vector<int> hx;
void dfs_1(int x,int fa,int dis){
d[x]=dis;
father[x]=fa;
int i;
GRAPH_REP(i,x){
if(to[i]!=fa)
dfs_1(to[i],x,dis+dist[i]);
}
hx.push_back(x);
}
int lazy[maxn];
inline void ClearLazy(){
memset(lazy,0,sizeof(lazy));
}
inline int DealCheck(int x){
register int i,v,ans=0;
REP_B(i,n){
v=hx[i-1];
lazy[father[v]]+=lazy[v];
}
REP_B(i,n){
if(lazy[i]==x){
ans=max(ans,d[i]-d[father[i]]);
}
}
return ans;
}
// Djoin Set
int p[maxn];
int find_set(int x){
if(p[x]==x)
return x;
else
return p[x]=find_set(p[x]);
}
inline void union_set(int x,int y){
p[find_set(y)]=find_set(x);
}
inline void make_set(int x){
p[x]=x;
}
// LCA
struct Query{
int u,v,b;
};
bool vis[maxn];
vector<Query> qs;
vector<int> querys[maxn];
inline void Add_Query(int x,int y,int b){
querys[x].push_back(qs.size());
qs.push_back((Query){x,y,b});
}
int res[maxn][3];
int n;
void LCA(int u){
make_set(u);
vis[u]=true;
int i,temp;
REP(i,querys[u].size()){
Query& tep=qs[querys[u][i]];
if(vis[tep.v])
res[tep.b][2]=find_set(tep.v);
}
for(i=first[u];i;i=next[i]){
temp=to[i];
if(!vis[temp]){
LCA(temp);
union_set(u,temp);
}
}
}
};
using namespace FastIO;
struct Deal{
int u,v,lca,d;
bool operator <(const Deal& x) const{
return d<x.d;
}
};
vector<Deal> V;
int m;
inline bool Check(int x){
register int i,ideal=0,yh=V[m-1].d;
Tree::ClearLazy();
for(i=m-1;i>=0;i--){
int& u=V[i].u,v=V[i].v,lca=V[i].lca,d=V[i].d;
if(d>x){
ideal++;
Tree::lazy[u]++;
Tree::lazy[v]++;
Tree::lazy[lca]-=2;
}else{
break;
}
}
yh-=Tree::DealCheck(ideal);
return yh<=x;
}
int main(){
register int i,u,v,lca,d;
FastIO::InitFastIO();
n=readint();
m=readint();
REP(i,n-1){
u=readint();
v=readint();
d=readint();
Tree::Add_Edge(u,v,d);
Tree::Add_Edge(v,u,d);
}
REP(i,m){
u=readint();
v=readint();
Tree::Add_Query(u,v,i);
Tree::Add_Query(v,u,i);
Tree::res[i][0]=u;
Tree::res[i][1]=v;
}
Tree::dfs_1(1,0,0);
Tree::LCA(1);
REP(i,m){
u=Tree::res[i][0];
v=Tree::res[i][1];
lca=Tree::res[i][2];
d=Tree::d[u]+Tree::d[v]-2*Tree::d[lca];
V.push_back((Deal){u,v,lca,d});
}
sort(V.begin(),V.end());
u=0;
v=V[m-1].d+1;
while(u<v){
d=u+(v-u)/2;
if(Check(d))
v=d;
else
u=d+1;
}
putint(u);
return 0;
}
[洛谷 P2679]子串
DP神题……
第一眼都能看出来是DP，然后大约构思就出来了，但细节很复杂啊……
看完第一眼后大家大约都能想出来[tex]d[i][j][k][/tex]这样的状态，但是注意[tex]A[i]=B[j][/tex]（字符数组细节此处未予考虑）的情况和整体情况要独立对待，否则这题只能233
然后下面就不难想了。但是注意直接开数组会233，要开滚动数组防MLE。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1001,maxm=201,maxk=201;
const int MOD=1e9+7;
int d[2][maxm][maxk][2];
char A[maxn];
char B[maxm];
int main(){
register int i,j,p,now,pre;
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
scanf("%s%s",A,B);
d[0][0][0][1]=1;
for(i=1;i<=n;i++){
now=i%2;
pre=1-now;
d[now][0][0][1]=1;
for(j=1;j<=m;j++){
if(A[i-1]==B[j-1])
for(p=1;p<=min(k,j);p++){
d[now][j][p][0]=(d[pre][j-1][p][0]+d[pre][j-1][p-1][1])%MOD;
d[now][j][p][1]=(d[pre][j][p][1]+d[now][j][p][0])%MOD;
}
else
for(p=1;p<=min(k,j);p++){
d[now][j][p][0]=0;
d[now][j][p][1]=d[pre][j][p][1];
}
}
}
printf("%d\n",d[n%2][m][k][1]);
return 0;
}
[BZOJ 4325]斗地主
是的你没有看错！就是这道坑提！
这题基本是个半成品，歧义真的，真的，真的很大。
至于方法？我们注意到同样的牌能一起出就尽可能避免拆开。例如，四带二分成炸弹加两单点（对子）肯定不好。三带一或者三带二也如此。先考虑不出顺子的最优解，并据此进行深度限制，再考虑出顺子。
然后，DFS暴搜即可。
顺便讲一下坑点：
- 顺子可以有A。
- 三带一，三带二，四代二都可以有头。但是大小头要区别开。
代码：
/**************************************************************
Problem: 4325
User: danihao123
Language: C++
Result: Accepted
Time:24 ms
Memory:820 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int ans;
int cnt[5],hand[15];
void dfs(int x){
if(x>ans)
return;
int i,j,rest=0;
memset(cnt,0,sizeof(cnt));
for(i=0;i<=14;i++){
cnt[hand[i]]++;
}
while(cnt[4]>0){
cnt[4]--;
rest++;
if(cnt[2]>=2)
cnt[2]-=2;
else
if(cnt[1]>=2)
cnt[1]-=2;
}
while(cnt[3]>0){
cnt[3]--;
rest++;
if(cnt[2]>0)
cnt[2]--;
else
if(cnt[1]>0)
cnt[1]--;
}
if(hand[0] && hand[1] && cnt[1]>=2)
rest--;
ans=min(ans,cnt[1]+cnt[2]+rest+x);
for(i=3;i<=10;i++){
for(j=i;j<=14 && hand[j];j++){
hand[j]--;
if(j-i+1>=5)
dfs(x+1);
}
while(j>i)
hand[--j]++;
}
for(i=3;i<=12;i++){
for(j=i;j<=14 && hand[j]>=2;j++){
hand[j]-=2;
if(j-i+1>=3)
dfs(x+1);
}
while(j>i)
hand[--j]+=2;
}
for(i=3;i<=13;i++){
for(j=i;j<=14 && hand[j]>=3;j++){
hand[j]-=3;
if(j-i+1>=2)
dfs(x+1);
}
while(j>i)
hand[--j]+=3;
}
}
int main(){
int T,u,v;
register int i;
scanf("%d%d",&T,&n);
while(T--){
ans=n;
memset(hand,0,sizeof(hand));
for(i=1;i<=n;i++){
scanf("%d%d",&u,&v);
if(!u){
if(v==2)
hand[1]++;
else
hand[0]++;
}else{
if(u==1)
hand[14]++;
else
hand[u]++;
}
}
dfs(0);
printf("%d\n",ans);
}
return 0;
}
[洛谷 P1967]货车运输
倍增LCA经典题……
这题的做法就是求最大生成树，然后用倍增LCA法求瓶颈路……
注意一下，两点不连通时输出-1（其实这个用并查集判断不就行了……）！！！
代码：
