E. Kojiro and Furrari
题意说的是 在一条直线上 有n个加油站， 每加一单位体积的汽油 可以走1km 然后每个加油站只有一种类型的汽油，汽油的种类有3种 求从起点出发到达终点要求使用最少的 1 号汽油的前提下使用最少的二号汽油，
我们可以这样考虑
当前在第i个加油站的时候 i个加油站 有3种情况
第一种 他是只有 1 号汽油 那么他必须携带 尽量少的 1号汽油到达离他最近的2号汽油点或者3号汽油点 更新这个点到达终点的代价 取最小值，因为他必须通过那个点到达其他点
第二种 他只有 2 号汽油， 那么他必须携带 尽量多的 2号汽油到达能达到的最远的1号汽油点，这样可以更少使用1号汽油，或者 带尽量少的汽油到达离他最近的3号汽油的点，或者最近的2号汽油的点
第三种 如果他是3号汽油 那么他必须携带尽量少的3号汽油到达离他最近的点，或者带尽量多的3号汽油到达离他能达到的最远的1 、2号汽油点
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;
typedef long long LL;
const int maxn=;
const int INF=;
struct point{
int x,t;
point(int cx=, int ct=){
x=cx; t=ct;
}
bool operator <(const point &rhs)const{
return x<rhs.x;
}
}P[maxn];
int D[][maxn],num[];
int dp[maxn][];
int e,s,n,m;
int bitlook1(int x,int *C, int n)
{
int L=,R=n-,ans=-;
while(L<=R)
{
int mid=(L+R)>>;
int id=C[mid];
if( P[id].x>=x ){
ans=mid;
R=mid-;
}else{
L=mid+;
}
}
return ans;
}
void cmp(int &A, int &B,int &V, int C, int D, int DV)
{
if(A>=C){
if(A==C){
if(B<D) return ;
if(B>D){
B=D;
V=DV;
}else{
V=min(V,DV);
}
}
else {
A=C; B=D;
V=DV;
}
}
}
void solve1(int id)
{
int loc=P[id].x;
int d1=bitlook1(loc+,D[],num[]);
int d2=bitlook1(loc+,D[],num[]);
int d3=bitlook1(loc+,D[],num[]);
if(d3!=-)d3=D[][d3];
if(d2!=-)d2=D[][d2];
if(d1!=-)d1=D[][d1];
if( d3!=- && P[d3].x <= loc+s )
{
int cp1 = dp[d3][]+P[d3].x-loc;
int cp2 = dp[d3][];
cmp(dp[id][],dp[id][],dp[id][],cp1,cp2,P[d3].x-loc);
}
if(d2!=- && P[d2].x<=loc+s)
{
int cp1 = dp[d2][]+P[d2].x-loc;
int cp2 = dp[d2][];
cmp(dp[id][],dp[id][],dp[id][],cp1,cp2,P[d2].x-loc);
}
if( d1!=- && P[d1].x<=loc+s)
{
int cp1 = dp[d1][]+P[d1].x-loc;
int cp2 = dp[d1][];
cmp(dp[id][],dp[id][],dp[id][],cp1,cp2,P[d1].x-loc);
}
}
int bitlook2(int x,int *C, int n)
{
int L=,R=n-,ans=-;
while(L<=R)
{
int mid=(L+R)>>;
int id=C[mid];
if( P[id].x<=x ){
ans=mid;
L=mid+;
}else{
R=mid-;
}
}
return ans;
}
void solve2(int id)
{
int loc=P[id].x;
int d1=bitlook2(loc+s,D[],num[]);
int d2=bitlook1(loc+,D[],num[]);
int d3=bitlook1(loc+,D[],num[]);
if(d3!=-)d3=D[][d3];
if(d2!=-)d2=D[][d2];
if(d1!=-)d1=D[][d1];
if( d3!=- && P[d3].x <= loc+s )
{
int cp1 = dp[d3][];
int cp2 = dp[d3][]+P[d3].x-loc;
cmp(dp[id][],dp[id][],dp[id][],cp1,cp2,P[d3].x-loc);
}
if(d2!=- && P[d2].x<=loc+s)
{
int cp1 = dp[d2][];
int cp2 = dp[d2][]+P[d2].x-loc;
cmp(dp[id][],dp[id][],dp[id][],cp1,cp2,P[d3].x-loc);
} if( d1!=-&&P[d1].x>loc)
{
int cp0=s;
int lit = s-(P[d1].x-loc);
int cp1 = dp[d1][]-min(lit,dp[d1][]);
int cp2 = dp[d1][]+cp0;
cmp(dp[id][],dp[id][],dp[id][],cp1,cp2,cp0);
}
}
void solve3(int id)
{
int loc=P[id].x;
int d1=bitlook2(loc+s,D[],num[]);
int d2=bitlook2(loc+s,D[],num[]);
int d3=bitlook1(loc+,D[],num[]);
if(d3!=-)d3=D[][d3];
if(d2!=-)d2=D[][d2];
if(d1!=-)d1=D[][d1]; if( d3!=- && P[d3].x<=loc+s )
{
cmp(dp[id][],dp[id][],dp[id][],dp[d3][],dp[d3][],);
}
if(d2!=-&&P[d2].x>loc)
{
int lit = s-(P[d2].x-loc);
int cp1 = dp[d2][];
int cp2 = dp[d2][]-min(dp[d2][],lit);
cmp(dp[id][],dp[id][],dp[id][],cp1,cp2,);
}
if(d1!=-&&P[d1].x>loc)
{
int lit = s-(P[d1].x-loc);
int cp1 = dp[d1][]-min(dp[d1][],lit);
int cp2 = dp[d1][];
cmp(dp[id][],dp[id][],dp[id][],cp1,cp2,);
}
}
void solve4(int loc, int &S1,int &S2)
{
int k;
int d1=bitlook2(loc+s,D[],num[]);
int d2=bitlook2(loc+s,D[],num[]);
int d3=bitlook1(loc+,D[],num[]);
if(d3!=-)d3=D[][d3];
if(d2!=-)d2=D[][d2];
if(d1!=-)d1=D[][d1];
if( d3!=- && P[d3].x<=loc+s &&dp[d3][]!=INF)
{
cmp(S1,S2,k,dp[d3][],dp[d3][],);
}
if(d2!=-&&P[d2].x>loc&&dp[d2][]!=INF)
{
int lit = s-(P[d2].x-loc);
int cp1 = dp[d2][];
int cp2 = dp[d2][]-min(dp[d2][],lit);
cmp(S1,S2,k,cp1,cp2,);
}
if(d1!=-&&P[d1].x>loc&&dp[d1][]!=INF)
{
int lit = s-(P[d1].x-loc);
int cp1 = dp[d1][]-min(dp[d1][],lit);
int cp2 = dp[d1][];
cmp(S1,S2,k,cp1,cp2,);
}
}
int main()
{
while(scanf("%d%d%d%d",&e,&s,&n,&m)==)
{
num[]=num[]=num[]=num[]=;
int k=;
for(int i=; i<n; i++) {
scanf("%d%d",&P[k].t,&P[k].x);
if(P[k].x<e)k++;
}
n=k;
sort(P,P+n);
if(P[n-].x!=e)
{
P[n]=point(e,);
n++;
}
for(int i=; i<n; i++)
if(P[i].t==) D[ ][num[]++ ] =i;
else if(P[i].t==) D[][ num[] ++ ]=i;
else D[][ num[]++ ]=i;
dp[n-][]=dp[n-][]=dp[n-][]=;
for(int i=n-; i>=;i--)dp[i][]=dp[i][]=dp[i][]=INF; for(int i=n-; i>=; i--)
{
if(P[i].t==)solve1(i);
else if(P[i].t==)solve2(i);
else solve3(i);
if(dp[i][]==INF)break;
}
for(int i=;i<m; i++)
{
int S1=INF,S2=INF;
int loc;
scanf("%d",&loc);
solve4(loc,S1,S2);
if(S1==INF){
printf("-1 -1\n");
}else{
printf("%d %d\n",S1,S2);
}
}
}
return ;
}
/*
386 20 1 1
2 369
351 */
F. Zublicanes and Mumocrates 树形dp
题意给了一棵树 要求使得这棵树所有的节点分为两个阵营，其中叶子节点要均分，求最少的两个阵营相邻， 也就是求 最少的边使得 这些边两头阵营不同
dp[cur][i][j] 表示当cur为i阵营的时候 有j个和i同阵营的方案
dp[cur][i][j+k] = min{dp[to][i^1][j=(叶子个数-d)]+dp[cur][i][k]+1,dp[to][i][j]+dp[cur][i][k]}
cnt为叶子节点的个数 最后答案是 min{ dp[root][0][cnt/2] ,dp[root][1][cnt/2]}
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn=;
int H[maxn],to[maxn*],nx[maxn*],numofE;
void add(int u, int v)
{
numofE++;
to[numofE]=v;
nx[numofE]=H[u];
H[u]=numofE;
}
int dp[maxn][][maxn];
int dp2[][maxn],sz[maxn];
int d[maxn];
void dfs(int cur ,int per)
{
if(d[cur]==){
sz[cur]=;
dp[cur][][]=dp[cur][][]=;
return ;
}
dp[cur][][]=dp[cur][][]=;
for(int i=H[cur]; i ; i=nx[i])
{
int tto = to[i];
if(tto==per)continue;
dfs(tto,cur);
for(int i=; i<=sz[cur]; i++)
for(int u=; u<; u++)
{
if( dp[cur][u][i] == - ) continue; for(int j=; j<=sz[tto]; j++)
for(int v=; v<; v++)
{
if(dp[tto][v][j]==-)continue;
if(u==v)
{
if(dp2[u][i+j]==-)
{
int k=dp[cur][u][i]+dp[tto][v][j];
dp2[u][i+j] = k; }else {
int k=min(dp[cur][u][i]+dp[tto][v][j],dp2[u][i+j]);
dp2[u][i+j]=k; }
}else
{
int nu=sz[tto];
if(dp2[u][i+nu-j]==-)
{
int k=dp[cur][u][i]+dp[tto][v][j]+;
dp2[u][i+nu-j]=k;
}
else
{
int k=min(dp[cur][u][i]+dp[tto][v][j]+,dp2[u][i+nu-j]);
dp2[u][i+nu-j]=k; }
}
}
}
sz[cur]+=sz[tto];
for(int i=; i<=sz[cur]; i++)
for(int j=; j<; j++)
{
dp[cur][j][i]=dp2[j][i];
dp2[j][i]=-;
}
}
}
int main()
{
int n;
while(scanf("%d",&n)==)
{
memset(d,,sizeof(d));
memset(dp,-,sizeof(dp));
memset(sz,,sizeof(sz));
memset(dp2,-,sizeof(dp2));
memset(H,,sizeof(H));
numofE=;
for(int i=; i<n; i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
d[a]++;d[b]++;
}
if(n==){
printf("%d\n",); continue;
}
int root;
int cnt=;
for(int i=; i<=n; i++){
if(d[i]==)cnt++;
else root=i;
}
dfs(root,-);
printf("%d\n",min(dp[root][][cnt/],dp[root][][cnt/]));
}
return ;
}
/*
6
1 2
2 5
2 3
3 4
3 6
*/