[COGS 729]圆桌聚餐
第一次做这种”大型“网络流题（抱歉我是炒鸡大局若）。
注意同一个单位的人不可同桌聚餐，说明同一单位的人最多只能往某一桌子派一人！然后建图就很简单了：源点往每个单位连流量为[tex]r_i[/tex]的边，每个单位分别向每一个桌连一条流量为1的边，每个桌向汇点连一条流量为[tex]c_i[/tex]的边。跑一遍网络流即可。
这题坑点在于要输出解。输出解的时候注意不要把反向弧和正常的弧搞混。
代码：
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=425;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
struct Edge{
int u,v,cap,flow;
};
namespace Dinic{
vector<Edge> edges;
vector<int> G[maxn];
int m;
inline void AddEdge(int u,int v,int cap){
edges.push_back((Edge){u,v,cap,0});
edges.push_back((Edge){v,u,0,0});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool vis[maxn];
int d[maxn],cur[maxn];
int s,t;
inline bool BFS(){
register int i,u;
queue<int> Q;
CL_ARR(vis,0);
Q.push(s);
d[s]=0;
vis[s]=true;
while(!Q.empty()){
u=Q.front();
Q.pop();
REP(i,G[u].size()){
Edge& e=edges[G[u][i]];
if(!vis[e.v] && e.cap>e.flow){
vis[e.v]=1;
d[e.v]=d[u]+1;
Q.push(e.v);
}
}
}
return vis[t];
}
int DFS(int x,int a){
if(x==t || a==0)
return a;
int flow=0,temp;
for(int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(d[e.v]==d[x]+1){
temp=DFS(e.v,min(a,e.cap-e.flow));
if(temp>0){
e.flow+=temp;
edges[G[x][i]^1].flow-=temp;
flow+=temp;
a-=temp;
if(a==0)
break;
}
}
}
return flow;
}
inline int Maxflow(int S,int T){
s=S;
t=T;
register int ans=0;
while(BFS()){
CL_ARR(cur,0);
ans+=DFS(s,0x7f7f7f7f);
}
return ans;
}
};
int main(){
int n,m,temp;
bool flag;
register int i,j,tag,end,Expect=0;
freopen("roundtable.in","r",stdin);
freopen("roundtable.out","w+",stdout);
scanf("%d%d",&n,&m);
end=n+m+1;
REP_B(i,n){
scanf("%d",&temp);
Expect+=temp;
Dinic::AddEdge(0,i,temp);
}
REP_B(i,m){
scanf("%d",&temp);
tag=i+n;
Dinic::AddEdge(tag,end,temp);
REP_B(j,n){
Dinic::AddEdge(j,tag,1);
}
}
temp=Dinic::Maxflow(0,end);
if(temp<Expect){
puts("0");
return 0;
}
puts("1");
REP_B(i,n){
vector<int> V;
REP(j,Dinic::G[i].size()){
Edge& e=Dinic::edges[Dinic::G[i][j]];
if(e.v>n && e.v<=m+n && e.cap==e.flow)
V.push_back(e.v);
}
sort(V.begin(),V.end());
flag=false;
REP(j,V.size()){
if(flag)
putchar(' ');
flag=true;
printf("%d",V[j]-n);
}
putchar('\n');
}
return 0;
}
[BZOJ 1196]公路修建问题
挺简单的二分答案题……然而到现在才A
思路很明显，直接二分最终答案。那么判定如何做呢？
假设判定谓词为[tex]C(x)[/tex]，那么我们首先考虑选白边。贪心加入边权小于[tex]x[/tex]的边（当然是否有必要就要用并查集判定了。并且这样就算加的超过了[tex]k[/tex]条也不会对答案造成影响）。然后白边加的不够[tex]k[/tex]谓词就是假了。
然后再考虑黑边，接下来的事情就很简单了。
代码：
/**************************************************************
Problem: 1196
User: danihao123
Language: C++
Result: Accepted
Time:672 ms
Memory:1212 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=0;i<(n);i++)
#define RAP(i,n) for(i=1;i<=(n);i++)
const int maxn=10001,maxm=20001;
struct Edge{
int u,v,d1,d2;
};
bool cmp1(const Edge& x,const Edge& y){
return x.d1<y.d1;
}
bool cmp2(const Edge& x,const Edge& y){
return x.d2<y.d2;
}
int n;
int p[maxn],rank[maxn];
int find_set(int x){
if(p[x]==x)
return x;
else
return p[x]=find_set(p[x]);
}
inline void link_set(int x,int y){
if(rank[x]>rank[y]){
p[y]=x;
}else{
p[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
inline void union_set(int x,int y){
link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
return find_set(x)==find_set(y);
}
inline void init_set(){
register int i;
for(i=1;i<=n;i++)
p[i]=i;
memset(rank,0,sizeof(rank));
}
int k,m;
Edge E[maxm];
inline bool check(int x){
register int i,first_cnt=0,cnt=0;
init_set();
sort(E,E+m,cmp1);
REP(i,m){
if(E[i].d1>x){
break;
}else{
if(!is_same(E[i].u,E[i].v)){
first_cnt++;
cnt++;
union_set(E[i].u,E[i].v);
}
}
if(cnt==n-1){
return true;
}
}
if(first_cnt<k)
return false;
sort(E,E+m,cmp2);
REP(i,m){
if(E[i].d2>x){
break;
}else{
if(!is_same(E[i].u,E[i].v)){
cnt++;
union_set(E[i].u,E[i].v);
}
}
if(cnt==n-1)
return true;
}
return false;
}
int main(){
register int i,L=1,M,R=0;
scanf("%d%d%d",&n,&k,&m);
m--;
REP(i,m){
scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].d1,&E[i].d2);
R=max(R,E[i].d1);
}
R++;
while(L<R){
M=L+(R-L)/2;
if(check(M))
R=M;
else
L=M+1;
}
printf("%d\n",L);
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;
}
[BZOJ 1787]紧急集合
这个题需要一些脑洞。
给出任意三点，如果我们两两求LCA，肯定有两组相同，剩下那一组就是最优集合点了。为啥？画图理解一下吧……
代码：
/**************************************************************
Problem: 1787
User: danihao123
Language: C++
Result: Accepted
Time:4068 ms
Memory:80900 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#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 TWO_POW(n) (1<<(n))
const int maxn=500001,maxm=1000001;
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int graph_cnt=0;
inline void Add_Edge(int u,int v,int d){
graph_cnt++;
next[graph_cnt]=first[u];
first[u]=graph_cnt;
to[graph_cnt]=v;
dist[graph_cnt]=d;
}
int d[maxn];
int dep[maxn];
int anc[maxn][32];
void dfs(int x,int father,int depth,int dis){
d[x]=dis;
anc[x][0]=father;
dep[x]=depth;
int i;
GRAPH_REP(i,x){
if(to[i]!=father)
dfs(to[i],x,depth+1,dis+dist[i]);
}
}
int n;
inline void InitLCA(){
register int i,j;
for(j=1;TWO_POW(j)<n;j++){
REP_B(i,n){
if(anc[i][j-1]!=-1){
anc[i][j]=anc[anc[i][j-1]][j-1];
}
}
}
}
int QueryLCA(int x,int y){
register int j,log;
if(dep[x]<dep[y])
swap(x,y);
for(log=1;TWO_POW(log)<=dep[x];log++);
log--;
for(j=log;j>=0;j--)
if(dep[x]-TWO_POW(j)>=dep[y])
x=anc[x][j];
if(x==y)
return y;
for(j=log;j>=0;j--){
if(anc[x][j]!=-1 && anc[x][j]!=anc[y][j]){
x=anc[x][j];
y=anc[y][j];
}
}
return anc[x][0];
}
inline int make_dis(int x,int y){
return d[x]+d[y]-2*d[QueryLCA(x,y)];
}
int main(){
int u,v,D;
int x,y,z,QinDing;
int m;
register int i,j;
scanf("%d%d",&n,&m);
REP(i,n-1){
scanf("%d%d",&u,&v);
Add_Edge(u,v,1);
Add_Edge(v,u,1);
}
memset(anc,-1,sizeof(anc));
dfs(1,-1,0,0);
InitLCA();
REP(i,m){
scanf("%d%d%d",&u,&v,&D);
x=QueryLCA(u,v);
y=QueryLCA(u,D);
z=QueryLCA(v,D);
if(x==y){
QinDing=z;
}else{
if(x==z){
QinDing=y;
}else{
QinDing=x;
}
}
printf("%d %d\n",QinDing,make_dis(QinDing,u)+make_dis(QinDing,v)+make_dis(QinDing,D));
}
return 0;
}
[BZOJ 1901]Dynamic Rankings
终于A了！
做了4个月了，终于A了！
这个题其实不难。只要用树状数组维护主席树即可。不过请注意，此题的实际数据范围远比10000大！
代码：
/**************************************************************
Problem: 1901
User: danihao123
Language: C++
Result: Accepted
Time:540 ms
Memory:32712 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=120051;
const int maxlogn=31;
const int maxnode=maxn*20;
// ChairTree
int sumv[maxnode];
int lc[maxnode],rc[maxnode];
int ct_cnt=0;
int build_tree(int L,int R){
int ans=++ct_cnt;
if(R>L){
int M=L+(R-L)/2;
lc[ans]=build_tree(L,M);
rc[ans]=build_tree(M+1,R);
}
return ans;
}
int p,v;
int update(int o,int L,int R){
int ans=++ct_cnt;
sumv[ans]=sumv[o];
lc[ans]=lc[o];
rc[ans]=rc[o];
if(R>L){
int M=L+(R-L)/2;
if(p<=M)
lc[ans]=update(lc[ans],L,M);
else
rc[ans]=update(rc[ans],M+1,R);
}
sumv[ans]+=v;
return ans;
}
int LT_siz,RT_siz;
int LT[maxlogn],RT[maxlogn];
int query(int L,int R,int k){
if(L==R)
return L;
int i;
int LT_ans=0,RT_ans=0,the_ans,M=L+(R-L)/2;
for(i=1;i<=LT_siz;i++)
LT_ans+=sumv[lc[LT[i]]];
for(i=1;i<=RT_siz;i++)
RT_ans+=sumv[lc[RT[i]]];
the_ans=RT_ans-LT_ans;
if(k<=the_ans){
for(i=1;i<=LT_siz;i++)
LT[i]=lc[LT[i]];
for(i=1;i<=RT_siz;i++)
RT[i]=lc[RT[i]];
return query(L,M,k);
}else{
for(i=1;i<=LT_siz;i++)
LT[i]=rc[LT[i]];
for(i=1;i<=RT_siz;i++)
RT[i]=rc[RT[i]];
return query(M+1,R,k-the_ans);
}
}
int rt[maxn];
int siz;
inline int lowbit(int x){
return x&(-x);
}
int n;
void change(int pos,int value,int delta){
p=value;
v=delta;
while(pos<=n){
rt[pos]=update(rt[pos],1,siz);
pos+=lowbit(pos);
}
}
int get_ans(int l,int r,int k){
int temp=l-1;
LT_siz=RT_siz=0;
while(temp>0){
LT[++LT_siz]=rt[temp];
temp-=lowbit(temp);
}
while(r>0){
RT[++RT_siz]=rt[r];
r-=lowbit(r);
}
return query(1,siz,k);
}
int pre[maxn];
int A[maxn],A2[maxn];
int real_siz=0;
void init_CT(){
register int i,pos;
sort(A2+1,A2+1+real_siz);
siz=unique(A2+1,A2+1+real_siz)-A2-1;
rt[0]=build_tree(1,siz);
for(i=1;i<=n;i++)
rt[i]=rt[0];
for(i=1;i<=n;i++){
pos=lower_bound(A2+1,A2+1+siz,pre[i])-A2;
change(i,pos,1);
}
}
inline int get_lsh(int x){
return lower_bound(A2+1,A2+1+siz,x)-A2;
}
int Query[maxn][4];
int main(){
int m,u,v,d;
char buf[3];
register int i;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d",&pre[i]);
A2[++real_siz]=pre[i];
}
for(i=1;i<=m;i++){
scanf("%s%d%d",buf,&u,&v);
Query[i][1]=u;
Query[i][2]=v;
if(buf[0]=='C'){
Query[i][0]=1;
A2[++real_siz]=v;
}else{
Query[i][0]=0;
scanf("%d",&Query[i][3]);
}
}
init_CT();
for(i=1;i<=m;i++){
if(Query[i][0]){
change(Query[i][1],get_lsh(pre[Query[i][1]]),-1);
pre[Query[i][1]]=Query[i][2];
change(Query[i][1],get_lsh(Query[i][2]),1);
}else{
printf("%d\n",A2[get_ans(Query[i][1],Query[i][2],Query[i][3])]);
}
}
return 0;
}
[BZOJ 1029]建筑抢修
废了。
我彻底废了。
就一个贪心水体。按截止时间排序然后遍历，当前花时间能干完就干，不能的话看能不能把更劣的选择换。仅此而已。
代码：
/**************************************************************
Problem: 1029
User: danihao123
Language: C++
Result: Accepted
Time:396 ms
Memory:2764 kb
****************************************************************/
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
const int maxn=150001;
struct Node{
int a,b;
bool operator <(const Node& x) const{
return b<x.b;
}
bool operator >(const Node& x) const{
return b>x.b;
}
};
Node T[maxn];
priority_queue<ll> Q;
int main(){
int n;
register int i,ans=0;
register ll cur=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",&T[i].a,&T[i].b);
sort(T+1,T+1+n);
for(i=1;i<=n;i++){
if(cur+T[i].a<=T[i].b){
cur+=T[i].a;
Q.push(T[i].a);
}else{
if(Q.size() && Q.top()>T[i].a){
cur-=Q.top();
Q.pop();
cur+=T[i].a;
Q.push(T[i].a);
}
}
}
printf("%d\n",Q.size());
return 0;
}
[BZOJ 1034]泡泡堂
这题其实就是一个田忌赛马类问题。贪心即可。
如果你不知道田忌赛马怎么贪，可以看《骗分导论》相关介绍（然而那个贪心不是骗分算法哦）。
代码：
/**************************************************************
Problem: 1034
User: danihao123
Language: C++
Result: Accepted
Time:256 ms
Memory:1604 kb
****************************************************************/
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=100001;
int a[maxn],b[maxn];
int n;
inline int solve(int *A,int *B){
register int L1=1,R1=n,L2=1,R2=n,ans=0;
while(L1<=R1 && L2<=R2){
if(A[L1]>B[L2]){
ans+=2;
L1++;
L2++;
}else{
if(A[R1]>B[R2]){
ans+=2;
R1--;
R2--;
}else{
if(A[L1]==B[R2])
ans++;
L1++;
R2--;
}
}
}
return ans;
}
int main(){
register int i,ans;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
scanf("%d",&b[i]);
sort(a+1,a+1+n);
sort(b+1,b+1+n);
printf("%d %d\n",solve(a,b),2*n-solve(b,a));
return 0;
}
[BZOJ 2662]冻结
又是一道分层图最短路水题……
我估计会卡SPFA（或许可能不卡？），所以再次写了pb_ds优化Dijkstra。
代码：
/**************************************************************
Problem: 2662
User: danihao123
Language: C++
Result: Accepted
Time:4 ms
Memory:868 kb
****************************************************************/
#include <cstdio>
#include <cctype>
#include <cstring>
#include <utility>
#include <ext/pb_ds/priority_queue.hpp>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=51,maxk=51,maxm=2005;
int cnt=0;
int first[maxn];
int to[maxm],next[maxm];
int dist[maxm];
inline void Add_Edge(int x,int y,int z){
cnt++;
next[cnt]=first[x];
first[x]=cnt;
to[cnt]=y;
dist[cnt]=z;
}
int d[maxn][maxk];
bitset<maxn> vis[maxk];
struct Node{
int x,k,d;
bool operator <(const Node& itt) const{
return d<itt.d;
}
bool operator >(const Node& itt) const{
return d>itt.d;
}
};
typedef __gnu_pbds::priority_queue<Node,greater<Node> > Heap;
Heap::point_iterator ite[maxn][maxk];
Heap Q;
int n,k;
inline void relax(int x,int y,int p){
d[x][y]=p;
if(ite[x][y]!=0)
Q.modify(ite[x][y],(Node){x,y,p});
else
ite[x][y]=Q.push((Node){x,y,p});
}
int dij(){
register int i,u,v,ans=0x7f7f7f7f;
memset(d,0x7f,sizeof(d));
d[1][0]=0;
ite[1][0]=Q.push((Node){1,0,0});
while(!Q.empty()){
u=Q.top().x;
v=Q.top().k;
Q.pop();
if(vis[u][v])
continue;
vis[u][v]=true;
for(i=first[u];i;i=next[i]){
if(v<k){
if(d[to[i]][v+1]>(d[u][v]+dist[i]/2)){
relax(to[i],v+1,d[u][v]+dist[i]/2);
}
}
if(d[to[i]][v]>d[u][v]+dist[i]){
relax(to[i],v,d[u][v]+dist[i]);
}
}
}
for(i=0;i<=k;i++)
ans=min(ans,d[n][i]);
return ans;
}
// I/O优化
inline int readint(){
char c=getchar();
register int x=0;
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return x;
}
int bf[10];
inline void writeint(int x){
register int p=0;
if(x==0){
bf[p++]=0;
}else{
while(x){
bf[p++]=x%10;
x/=10;
}
}
for(register int i=p-1;i>=0;i--)
putchar('0'+bf[i]);
}
int main(){
int m;
register int i,u,v,d;
n=readint();
m=readint();
k=readint();
for(i=1;i<=m;i++){
u=readint();
v=readint();
d=readint();
Add_Edge(u,v,d);
Add_Edge(v,u,d);
}
writeint(dij());
putchar('\n');
return 0;
}
[CF 710E]Generate a String
很不错的题。
很容易想到大爆搜：每搜索一个点，预处理只插入的深度，然后限制之。之后再加一些其他的剪枝。不过估计会炸。
然后有同学就想：那个删除操作真特么棘手啊……因为这个就用不了DP了……哎
不过，删除的目的是什么？下一步干啥？再插入？那就有病了。肯定是要复制。所以说我们可以想出如下状态转移方程（i11r的TeX插件好像不能排版多行公式，所以分两部分写吧）：
[tex]i[/tex]为偶数时[tex]f[i]=min(f[i-1]+x,f[i/2]+y)[/tex]
[tex]i[/tex]为奇数时[tex]f[i]=min(f[i-1]+x,f[(i+1)/2]+x+y)[/tex]
然后问题就迎刃而解了。
代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e7+2;
typedef long long ll;
#define REP(i,n) for(i=1;i<=(n);i++)
ll d[maxn];
int main(){
ll n,x,y;
cin>>n>>x>>y;
register ll i;
d[0]=0;
REP(i,n+1)
d[i]=x*i;
REP(i,n){
if(1&i){
d[i]=min(d[i-1]+x,d[(i+1)/2]+x+y);
}else{
d[i]=min(d[i-1]+x,d[i>>1]+y);
}
}
cout<<d[n]<<endl;
return 0;
}
[VIJOS P1037]搭建双塔
很不错的题啊……
很容易想到构造三维的状态，但无论时间还是空间都不好。我们可以构造[tex]f[i][delta][/tex]这种状态，表示用前[tex]i[/tex]块水晶，搭建出的双塔高度差为[tex]delta[/tex]时较大塔的高度。显然答案为[tex]f[n][0][/tex]。
转移的时候，要考虑放到高塔上还是低塔上，以及是否会导致高低塔地位对调。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=101,maxV=2001;
int d[2][maxV];
int V[maxn];
int main(){
int n,maxj=0;
register int i,j,now,pre;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&V[i]);
maxj+=V[i];
}
memset(d,-1,sizeof(d));
d[0][0]=0;
for(i=1;i<=n;i++){
now=i%2;
pre=1-now;
for(j=0;j<=maxj;j++){
if(d[pre][j]>=0)
d[now][j]=d[pre][j];
if(V[i]<=j){
if(d[pre][j-V[i]]>=0){
d[now][j]=max(d[now][j],d[pre][j-V[i]]+V[i]);
}
}
if(V[i]>j && d[pre][V[i]-j]>=0){
d[now][j]=max(d[now][j],d[pre][V[i]-j]+j);
}
if(j+V[i]<=maxj && d[pre][j+V[i]]>=0)
d[now][j]=max(d[now][j],d[pre][j+V[i]]);
}
}
if(d[1&n][0]<=0)
puts("Impossible");
else
printf("%d\n",d[1&n][0]);
return 0;
}
