默认分类 – 第 63 页

[JSOI2010 满汉全席]2-sat

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1823
【算法分析】
对于每种材料，有做成满式和汉式两种情况，然后两者取且必须取一种。
而且约束条件是，(A做成XX式 or B做成yy式) = true。
逻辑运算符。。。很容易想到2-sat。
回想2-sat的建图，一条边(A，B)的意义是：如果你选了A，那么就必须选B。
恩，这个题目的逻辑式子转化成：加入你选了A的对立面，那么一定要选B啊。
恩，就这样。。。
【其它】很久没2-sat了，1Y。
【CODE】
#include #include #include const int N=1000;
const int E=1000000;
int n,m,e,times,ct,tot;
int lx[N],ly[N];
int fa[N],order[N];
bool v[N],Type;

struct Graph_t{
struct edge{int x,y;edge *next;}g[E],*ls[N];
void clr(){e=0; memset(ls,0,sizeof(ls));}
void addedge(int x,int y){
g[++e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=&g[e];
}

void op(){
int tmp=e;
clr();
for (int i=1;i<=tmp;i++) addedge(g[i].y,g[i].x);
}

void dfs(int p){
v[p]=true;
for (edge *t=ls[p];t;t=t->next)
if (!v[t->y]) dfs(t->y);
if (Type) fa[p]=ct;
else order[++tot]=p;
}
}G;

int Get(){
char ch[20];
int x;
scanf("%s",ch);
sscanf(ch+1,"%d",&x);
if (ch[0]==’h’) x+=n;
return x;
}

void init(){
int i;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++){
lx[i]=Get();
ly[i]=Get();
}
}

void build(){
G.clr();
int i,j;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++){
if (lx[j]==i+n) G.addedge(i,ly[j]);
if (ly[j]==i+n) G.addedge(i,lx[j]);
}
for (i=n+1;i<=n*2;i++)
for (j=1;j<=m;j++){
if (lx[j]==i-n) G.addedge(i,ly[j]);
if (ly[j]==i-n) G.addedge(i,lx[j]);
}
}

void SCC(){
memset(v,false,sizeof(v));
tot=0;
Type=false;
for (int i=1;i<=2*n;i++)
if (!v[i]) G.dfs(i);
Type=true;
G.op();
memset(v,false,sizeof(v));
for (int i=tot;i>=1;i–)
if (!v[order[i]]){
ct=order[i];
G.dfs(order[i]);
}
}

void output(){
bool ans=true;
for (int i=1;i<=n;i++)
if (fa[i]==fa[i+n]) ans=false;
if (ans) puts("GOOD");
else puts("BAD");
}

int main(){
int Tc,i;
scanf("%d",&Tc);
for (i=1;i<=Tc;i++){
init();
build();
SCC();
output();
}
}

[ZJOI2010 base 基站选址]线段树优化的动态规划★★

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1835
【算法分析】
首先第一直觉就能写出一个状态和方程。
F[i][j]表示第i个地点建站，然后前i个村庄一共建了j个站时的前i个村庄需要的最小费用。
于是顺理成章的方程：
F[i][j]=min(F[l][j-1]+w[l][i])+c[i]
其中w[l][i]是这样定义的：
从l+1到i-1这些点p里，所有满足d[p]+s[p]当然，这还是其次，最重要的是我们可能可以对每一层建立一个数据结构降低转移的复杂度。

让我们来观察假设i+1以后，方程里的东西有什么变化。

F[l][j-1]和c[i]显然不变。那么变得只是w[l][i]。
他怎么变呢？
围观一下上面红色的w[l][i]的定义，容易发现，唯一边的就是：
d[p]+s[p]而与它的w有关的转移范围显然是所有满足d[j]（具体求那个范围可以在一开始就二分出来。然后用一个邻接表起结束位置的点）
【时间复杂度】O(nk lg n)
【其它】2Y。第一次错是因为看错了一点题目，题目要求是<=k个站，而不是必须建k个站。。。
ZJOI2010 Day1 Finished。
【CODE】
#include #include #include const int N=25555;
const int INF=1000000005;
int n,k;
int pF[N],F[N],c[N],d[N],s[N],w[N],st[N],ed[N];
inline int min(int x,int y){return xstruct Segment_Type{
struct Node{int l,r,key,delta;}Tr[N*6];

void pushdown(int p){
if (!Tr[p].delta) return;
if (Tr[p].l!=Tr[p].r){
Tr[p<<1].delta+=Tr[p].delta;
Tr[(p<<1)+1].delta+=Tr[p].delta;
}
Tr[p].key+=Tr[p].delta;
Tr[p].delta=0;
}

void update(int p){
pushdown(p<<1);
pushdown((p<<1)^1);
Tr[p].key=min(Tr[p<<1].key,Tr[(p<<1)^1].key);
}

void build(int p,int l,int r){
Tr[p].l=l; Tr[p].r=r; Tr[p].delta=0;
if (l==r){
Tr[p].key=pF[l];
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build((p<<1)^1,mid+1,r);
update(p);
}

void add(int p,int l,int r,const int delta){
if (l>r) return;
if (l<=Tr[p].l && Tr[p].r<=r)
Tr[p].delta+=delta;
else{
pushdown(p);
int mid=(Tr[p].l+Tr[p].r) >> 1;
if (l<=mid) add(p<<1,l,r,delta);
if (r> mid) add((p<<1)^1,l,r,delta);
update(p);
}
}

int solve(int p,int l,int r){
if (l>r || r pushdown(p);
if (l<=Tr[p].l && Tr[p].r<=r) return Tr[p].key;
return min(solve(p<<1,l,r),solve((p<<1)^1,l,r));
}
}Segment_Tree;

struct edge{int x,y;edge *next;};
struct Lint_t{
edge g[N],*ls[N];
int e;
void init(){e=0;memset(ls,0,sizeof(ls));}
void add(int x,int y){g[++e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=&g[e];}
}Ed_Link;

int Findl(int x){
int l=1,r=n,mid;
while (l mid=(l+r)>>1;
if (x<=d[mid]) r=mid;
else l=mid+1;
}
return l;
}

int Findr(int x){
int l=1,r=n,mid;
while (l+1 mid=(l+r)>>1;
if (d[mid]<=x) l=mid;
else r=mid-1;
}
if (d[r]<=x) l=r;
return l;
}

void input(){
scanf("%d%d",&n,&k);
int i;
for (i=2;i<=n;i++) scanf("%d",&d[i]);
for (i=1;i<=n;i++) scanf("%d",&c[i]);
for (i=1;i<=n;i++) scanf("%d",&s[i]);
for (i=1;i<=n;i++) scanf("%d",&w[i]);
d[n+1]=d[n]+INF; c[n+1]=w[n+1]=s[i]=0;
n++;
Ed_Link.init();
for (i=1;i<=n;i++){
st[i]=Findl(d[i]-s[i]);
ed[i]=Findr(d[i]+s[i]);
Ed_Link.add(ed[i],i);
}
}

void dp(){
if (k==0){
int Sum=0;
for (int i=1;i<=n;i++) Sum+=w[i];
printf("%dn",Sum);
return;
}
int i,j,Sum=0,ans=INF;
for (i=1;i<=n;i++){
F[i]=Sum+c[i];
for (edge *t=Ed_Link.ls[i];t;t=t->next)
Sum+=w[t->y];
}
for (j=1;j<=k;j++){
ans=min(ans,F[n]);
memcpy(pF,F,sizeof(F));
for (i=1;i<=n;i++) F[i]=INF;
Segment_Tree.build(1,1,n);
for (i=1;i<=n;i++){
F[i]=min(F[i],Segment_Tree.solve(1,1,i-1)+c[i]);
for (edge *t=Ed_Link.ls[i];t;t=t->next)
Segment_Tree.add(1,1,st[t->y]-1,w[t->y]);
}
}
ans=min(ans,F[n]);
printf("%dn",ans);
}

int main(){
input();
dp();
}

[ZJOI2010 count 数字计数]统计

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1833
【算法分析】
就是从高到低枚举每一位，然后试填比它原位小的数，然后后面的位就可以随便填。这个随便填的话，显然000…000到999…999这一连串中，0-9的数量肯定是一样的。
所以每一位分别+上 (999..999+1)*log (999.999+1)/10。
利用这个快速算，很容易就得解。
【其它】比较繁琐= =，WA了几次。。。
【CODE】
#include #include #include #include using namespace std;
typedef long long lld;
lld L[10];
lld a[10],b[10];
void f(lld x,lld *res){
int i,j,Log=0;
memset(L,0,sizeof(L));
lld mul=1;
while (mul<=x){
mul*=10;
Log++;
}
mul/=10; Log–;
while (mul){
for (i=1;i res[i]+=mul;
for (j=0;j<10;j++){
res[j]+=L[j]*mul;
res[j]+=mul*Log/10;
}
}
L[x/mul%10]++;
mul/=10;
Log–;
if (mul){
for (i=1;i<10;i++){
res[i]+=mul;
for (j=0;j<10;j++)
res[j]+=mul*Log/10;
}
if (x/mul%10){
for (i=0;i<10;i++){
res[i]+=mul*Log/10;
res[i]+=L[i]*mul;
}
res[0]+=mul;
}
}
}
}

int main(){
lld x,y;
cin >> x >> y;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
f(x,a);
f(y+1,b);
for (int i=0;i<10;i++)
cout << b[i]-a[i] << " ";
cout << endl;
}

[ZJOI2010 network 网络扩容]费用流

【题目地址】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1834
【算法分析】
很裸啊。
第一问直接最大流，但是我写得是边权全部为0的费用流= =，方便第二问。。。
第二问的话，就是每条边加多一条容量无限，费用为给定费用的边。
然后加多一个超汇点，n向它连一个maxflow+K的边。
最后输出费用即可。
【其它】1Y，水过留痕。。。
【CODE】
#include #include const int N=1555;
const int E=5555*4;
const int INF=0x7FFFFFFF/2-55;
struct edge{int x,y,c,w;edge *next,*op;}g[E],*ls[N],*fa[N];
int n,m,q,e,flow,cost;
int lx[E],ly[E],lc[E],lw[E],L[N],d[N],v[N];

void add(int x,int y,int c,int w){
g[++e].x=x; g[e].y=y; g[e].c=c; g[e].w=w;
g[e].next=ls[x]; ls[x]=&g[e]; g[e].op=&g[e+1];
g[++e].x=y; g[e].y=x; g[e].c=0; g[e].w=-w;
g[e].next=ls[y]; ls[y]=&g[e]; g[e].op=&g[e-1];
}

void push_back(){
for (int i=2;i<=e;i+=2){
edge *t=&g[i];
t->op->c+=t->c;
t->c=0;
}
}

bool spfa(){
int head=0,tail=1;
for (int i=1;i<=n;i++){
v[i]=0;
d[i]=INF;
}
v[1]=1; d[1]=0; L[1]=1;
while (head!=tail){
head++; if (head>=N) head=0;
for (edge *t=ls[L[head]];t;t=t->next)
if (t->c && d[t->x]+t->w d[t->y]=d[t->x]+t->w;
fa[t->y]=t;
if (!v[t->y]){
v[t->y]=1;
tail++; if (tail>=N) tail=0;
L[tail]=t->y;
}
}
v[L[head]]=0;
}
if (d[n]==INF) return false;
return true;
}

void change(){
int nf=INF;
for (int i=n;i!=1;i=fa[i]->x)
if (fa[i]->c flow+=nf; cost+=d[n]*nf;
for (int i=n;i!=1;i=fa[i]->x){
fa[i]->c-=nf;
fa[i]->op->c+=nf;
}
}

void mincost_maxflow(){
flow=cost=0;
while (spfa()) change();
}

int main(){
scanf("%d%d%d",&n,&m,&q);
for (int i=1;i<=m;i++){
scanf("%d%d%d%d",&lx[i],&ly[i],&lc[i],&lw[i]);
add(lx[i],ly[i],lc[i],0);
}
mincost_maxflow();
printf("%d ",flow);
for (int i=1;i<=m;i++)
add(lx[i],ly[i],INF,lw[i]);
add(n,n+1,flow+q,0);
n++;
push_back();
mincost_maxflow();
printf("%dn",cost);
}

[HDOJ3418 Beautiful Dream]二分答案+判定 or 松弛

【题目大意】
给定n种玩具，他们分别有a[1]…a[n]个，如果一个人获得了m种不同的玩具，那么他就会高兴，问最多能让多少个人高兴。
【算法分析】
算法1:
二分答案，然后把a[i]比答案大的都变成答案。
然后判Sum(a[i])是否大于等于m*ans。如果是则可行，否则不可行。
算法2:
每次求和，然后和/m得到一个上界，然后把a[i]>Sum/m都变成Sum/m。
然后继续求，直到没有a[i]改变。

【其它】
还有O(n)的算法。不过没想出来= =
LCC这有，不过没看懂：http://hi.baidu.com/pojoflcc/blog/item/a5e757816511ccdb9123d9b4.html
然后郭神牛给了个提示，拍个序从大到小搞。能n lg n。
我还是没YY到。。。继续YY一下。想到了更新。
【CODE】
#include using namespace std;
typedef long long lld;
lld n,m,Sum;
lld a[155];

bool can(lld Limit){
Sum=0;
lld i;
for (i=1;i<=n;i++)
if (a[i]>Limit) Sum+=Limit;
else Sum+=a[i];
if (Sum>=m*Limit) return true;
return false;
}

int main(){
lld l,r,mid,i;
while (cin >> n >> m){
for (i=1;i<=n;i++) cin >> a[i];
l=0; r=1000000000*n;
while (l+1 mid=(l+r)/2;
if (can(mid)) l=mid;
else r=mid-1;
}
if (can(r)) l=r;
cout << l << endl;
}
return 0;
}