sgu 304

这道题还是有点难的拉。。(我太沙茶了。。)
首先可以看成有依赖的背包问题。。
把牙齿和牙龈都看成物品。。牙齿若要被选则放他的牙龈也要被选。。不就是依赖么。。
首先把物品重新排一下位置(我是用dfs的。。看成树的话。。dfs序正好满足要求俄)。。把牙齿都放在它依赖的牙龈的后面。。
再在开头放个虚拟物品。。方便编程。。。
这样不选的话就可以往后跳过那些牙齿。。就可以DP了
有两种做法。。之间的对比还是很有意义的。。
1:沙茶做法(50分)
设DP[pos,have]为从第pos个物品开始,还有have的money最多能选几个。。
则pos可以选或不选。。然后就可以列出方程了。。很好列。。就不写了。。
时间复杂度(money*N)。。注意到真正有用的money只有72000。。那么就要600*72000的空间。。400多MB!!
(我一开始的沙茶做法)。。
2:Best做法(100分)
既然不行就只好优化阿。。
可以发现前面是有浪费的。。因为如果从因为如果DP[pos,have-1]=DP[pos,have]的话。。后一个根本没必要存阿。。
(位置一样。。钱还多一点。。最多能选的反而一样。。丢人不。。存了有X用阿。。)..
所以只需要存what呢?只需要存DP[pos,have-1]<DP[pos,have]的那些have就可以了(也就是选X个的话最少的钱。。因为再少就不够了)。。
那样的have最多有N个。。因为每个最多能选的都不等嘛。。。
故设DP[pos,X]为从pos个开始。。选X个最少的钱。。。
故DP[pos,X]=min(DP[pos+1,X-(pos是牙齿么?1:0)]+pos的价值,DP[pos+不选pos而跳过的][X]);
用记忆化搜索要方便一些。。。
那么就可以一个个X试过去。。直到在总共中选X个的钱大于P。。然后X-1就OK了。。
P.S
一开始我写第一个发现MLE。。我以为空间可能实际用到的不多。。于是开hash。。结果SB掉了。。
看来抓住问题的本质的能力还不够阿。。
要记录和输出路径阿。。有点麻烦的。。
所以动规中一个重要的思想一定要熟记阿。。只保留有用的状态!!!
写了我N久。。郁闷死了。。
Code。。。
#include<iostream>
#include<ctype.h>
#include<string.h>
using namespace std;
//main data
const int maxn=601,inf=~0U>>2;
int N,K,P;
int S[maxn*2],C[maxn*2]={0};
struct edge
{
int t;edge* next;
edge(int tt,edge*nn):t(tt),next(nn){}
}*E[maxn];
void init()
{
cin>>N>>K>>P;
for(int i=1;i<=K;i++)
{
E[0]=new edge(i,E[0]);
cin>>C[i];
}
for(int i=1;i<=N;i++)
{
int f;
cin>>C[i+maxn]>>f;
E[f]=new edge(i+maxn,E[f]);
}
}
int ord[maxn],cnt=0;
int dfs(int t)
{
ord[cnt++]=t;
if(t>maxn) return S[t]=1;
for(edge*i=E[t];i;i=i->next)
S[t] += dfs(i->t);
return ++S[t];
}
//hash
int DP[2*maxn][maxn+1];
bool Ch[2*maxn][maxn+1];
int dp(int pos,int ch)
{           
if(DP[pos][ch]!=0)
return DP[pos][ch];   
if(ch==0)
return 0;
if(pos>=cnt)
return DP[pos][ch]=inf;
int ind=ord[pos];
int a=dp(pos+1,ch-(ind>maxn?1:0) )+C[ind],b=dp(pos+S[ind],ch);     
if(a<b){Ch[pos][ch]=true;DP[pos][ch]=a;}
else{Ch[pos][ch]=false;DP[pos][ch]=b;}
return DP[pos][ch];
}
int main()
{
init();
dfs(0);
memset(DP,0,sizeof(DP));
int i;
for(i=0;i<=N;i++)
if(dp(0,i)>P) break;
i–;
cout<<i<<endl;
if(i==N)
{
cout<<1;
for(int j=2;j<=N;j++)
cout<<" "<<j;
cout<<endl;
return 0;
}
int now=0,m=i;
bool first=true;
while(m)
{
if(Ch[now][m])
{
if(ord[now]>maxn)
{
m–;if(!first)cout<<" ";
cout<<ord[now]-maxn;first=false;
}
now++;
}
else
{
now+=S[ord[now]];
}
}
}

sgu 242

最大流。。很好构图。。实际上不用上下界的。。
源到每个学生联一条容量1的边。。学生到每个能去的学校连一条容量1的边。。学校到汇连一条容量为2的边。。然后判断流量是否是学校的2倍就OK了。。。
Code。。
#include<iostream>
#include<string.h>
using namespace std;
const int maxn=200+10,maxk=200+10,maxV=maxn+maxk,inf=~0U>>1;
int vs,vt;
int n,k;
struct edge
{
int t,c;
edge*next,*op;
edge(int t,int c,edge*n):t(t),c(c),next(n){}
}*E[maxV];
int H[maxV],VH[maxV];
void addedge(int s,int t,int c)
{
E[s]=new edge(t,c,E[s]);
E[t]=new edge(s,0,E[t]);
E[s]->op=E[t];E[t]->op=E[s];
}
inline int stu(int n){return n;}
inline int sch(int n){return n+maxn;}
int aug(int no,int m)
{
if(no==vt) return m;
int l=m;
for(edge*i=E[no];i;i=i->next) if(i->c&&H[i->t]+1==H[no])
{
int d=aug(i->t,min(i->c,l));
l-=d;i->c-=d;i->op->c+=d;
if(H[vs]==n||l==0) return m-l;
}
int minh=n;            for(edge*i=E[no];i;i=i->next) if(i->c)
if(H[i->t]+1<minh) minh=H[i->t]+1;
if(!–VH[H[no]]) H[vs]=n;else ++VH[H[no]=minh];
return m-l;
}
void init()
{
cin>>n>>k;vs=0;vt=maxV-1;
for(int i=1;i<=n;i++)
{
int t,s;cin>>t;
addedge(vs,stu(i),1);
for(int j=0;j<t;j++)
{
cin>>s;addedge(stu(i),sch(s),1);
}
}   
n+=2+k;
for(int i=1;i<=k;i++)
addedge(sch(i),vt,2);
memset(H,0,sizeof(H));
memset(VH,0,sizeof(VH));
VH[0]=n;
}
void solve()
{   
int ans=0;
while(H[vs]<n) ans+=aug(vs,inf);   
if(ans<2*k)
cout<<"NOn";
else
{
cout<<"YESn";int ans[maxn];
for(int i=1;i<=k;i++)
{
int num=0;           
for(edge*j=E[sch(i)];j;j=j->next)
if(j->t!=vt&&j->c==1)
{
ans[num++]=j->t;
}
cout<<num;
for(int o=0;o<num;o++)
cout<<" "<<ans[o];
cout<<endl;
}
}
}
int main()
{
init();
solve();
}

sgu103

就是最短路。。没有任何难点。。就是折磨你和你的键盘的。。
感觉我写的很不错阿。。思路很清晰阿。。(小自恋一下。。。)
跟最短路一样用D[X]表示到X的最短路。。
从X更新有两种办法。。
一是直接上(两边颜色要same)
二是等等上。。。(也可能等不到阿。。)
直接上自然没有花头。。等等上就跟泡妞的迂回战术一样。。
很复杂阿。。很BT阿。。懒得写。。看程序吧。。。
我一开始就写了两个函数来简化思维。。实际上这两个函数也不是那么好写的。。
感觉这两个函数做了很多重复的工作阿。。不该分开阿(不过懒得改了)。。
//important function
bool Colour(int n,int time)
{
if(time<Start[n]) return First[n];
time-=Start[n];
time%=(Dur[n][1]+Dur[n][0]);
if(time<Dur[n][ !First[n] ]) return !First[n];
return First[n];
}
int Next(int n,int time)
{
if(time<Start[n]) return Start[n]-time;
time-=Start[n];
time%=(Dur[n][1]+Dur[n][0]);
if(time<Dur[n][!First[n]]) return Dur[n][!First[n]]-time;
return Dur[n][0]+Dur[n][1]-time;
}
P.S这明明是个稠密图我居然沙茶到些Heap+Dij。。结果慢的要死。。
Code。。
#include<iostream>
#include<string.h>
using namespace std;
//main data
const int maxn=301;
const bool Blue=1,Purple=0;
const int inf=~0U>>1;
int Start[maxn],Dur[maxn][2],First[maxn];
//important function
bool Colour(int n,int time)
{
if(time<Start[n]) return First[n];
time-=Start[n];
time%=(Dur[n][1]+Dur[n][0]);
if(time<Dur[n][ !First[n] ]) return !First[n];
return First[n];
}
int Next(int n,int time)
{
if(time<Start[n]) return Start[n]-time;
time-=Start[n];
time%=(Dur[n][1]+Dur[n][0]);
if(time<Dur[n][!First[n]]) return Dur[n][!First[n]]-time;
return Dur[n][0]+Dur[n][1]-time;
}
//graph
int N,M;
int vs,vt;
struct edge
{
int t,c;
edge* next;
edge(int tt,int cc,edge* nn):t(tt),c(cc){next=nn;}
}*E[maxn];
inline void add(int s,int t,int c)
{
E[s]=new edge(t,c,E[s]);
E[t]=new edge(s,c,E[t]);
}
//heap

class heap
{
int Q[maxn],s,index[maxn],rdex[maxn];
void exch(int&x,int&y)
{int t=x;x=y;y=t;}
void swap(int x,int y)
{
exch(Q[x],Q[y]);exch(index[x],index[y]);
rdex[index[x]]=x;rdex[index[y]]=y;
}
void sink(int x)   
{
int t=2*x;
while(t<=s)
{
if(t+1<=s&&Q[t+1]<Q[t]) t++;
if(Q[x]<Q[t]) break;
swap(x,t);x=t;t=2*x;
}
}   
void swim(int x)
{
int t=x/2;
while(t)
{
if(Q[t]>Q[x]) swap(x,t);
else break;
x=t;t=x/2;
}
}
public:
void set(int n)
{
s=n;
for(int i=1;i<=s;i++)
{
index[i]=rdex[i]=i;
Q[i]=inf;
}
}
int Pop()
{       
int t=index[1];
swap(1,s);s–;
sink(1);   
return t;
}
void Lower(int x,int d)
{       
Q[ rdex[x] ]=d;
swim( rdex[x] );
}   
bool Empty(){return s==0;}
int operator[](int v)
{ return Q[ rdex[v] ]; }
};
void init()
{
cin>>vs>>vt;
cin>>N>>M;
for(int i=1;i<=N;i++)
{
char t;cin>>t;First[i]=(t==’B’);
cin>>Start[i]>>Dur[i][1]>>Dur[i][0];
}
for(int i=0;i<M;i++)
{
int s,t,c;cin>>s>>t>>c;
add(s,t,c);
}
}
int P[maxn];
heap H;
bool dijstra()
{
H.set(N);
H.Lower(vs,0);P[vs]=0;   
bool Cal[maxn]={0};
while( !H.Empty() )
{
int v=H.Pop();
if(H[v]==inf) return false;
Cal[v]=true;
if(v==vt) return true;
int nextv=Next(v,H[v]);
bool colourv=Colour(v,H[v]);
for(edge*i=E[v];i;i=i->next)
if(!Cal[i->t])
{
int p=H[v]+i->c,w=i->t;
if( Colour(w,H[v]) != colourv )           
{
int nextw=Next(w,H[v]);
bool colourw=Colour(w,H[v]);
p+=min(nextv,nextw);
if( nextw==nextv )
{
if(Dur[v][!colourv]!=Dur[w][!colourw])
p+=min(Dur[v][!colourv],Dur[w][!colourw]);
else
{
if(Dur[v][colourv]==Dur[w][colourw]) continue;
p+=min(Dur[v][colourv],Dur[w][colourw]);
}
}
}
if(p<H[w])
{
H.Lower(w,p);
P[w]=v;
}
}
}
return false;
}
int main()
{
init();
if(!dijstra() )
{
cout<<0<<endl;
return 0;
}
cout<<H[vt]<<endl;
int x=vt;
int ans[maxn],cnt=0;
while(P[x])
{
ans[cnt++]=x;
x=P[x];
}
ans[cnt++]=vs;
cout<<ans[cnt-1];
for(int i=cnt-2;i>=0;i–)
cout<<" "<<ans[i];
cout<<endl;
}

sgu 318

http://acm.sgu.ru/problem.php?contest=0&problem=318
看上去有点小难度。。实际上很水。。
一开始还想DP什么。。真是沙茶。。。
有两种方法。。一种从user的角度考虑。。每个user都有需要的快。。只要用类似矩形切割的办法。。不断取交集就OK了。。
还有一种从resource角度考虑。。两个resource可以合并成一组当且仅当需要他们的人是一样的。。用并差集实现就OK了。。当然要尽可能多的合并。。
PS为了实现方便。。可以利用集合pascal里面是set。。C++里面是bitset。。很方便的。。
Code。。。
#include<bitset>
#include<iostream>
using namespace std;
const int maxn=100+10;
int n,m,ans=0;
bitset<100> Q[maxn];
int F[maxn];
int find(int x)
{
if(F[x]!=x) F[x]=find(F[x]);
return F[x];
}
void Union(int x,int y)
{
x=find(x);y=find(y);
if(x!=y)
ans–;
F[x]=y;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) F[i]=i;
for(int i=0;i<m;i++)
{
int t,s;cin>>t;
while(t–)
{
cin>>s;s–;
Q[s][i]=true;
}
}
for(int i=0;i<n;i++) if(Q[i].count())
{
ans++;
for(int j=i+1;j<n;j++)
if(Q[i]==Q[j])
Union(i,j);
}
cout<<ans<<endl;
}      

sgu 375

水题。。(我只会做水题。。)
http://acm.sgu.ru/problem.php?contest=0&problem=375
很明显一点要是奇数才有解。。然后倒过来看。奇数2N+1可以由N和N+1变成。。其中只有一个奇数。。直接推就可以了。。O(log n)。。。
#include<iostream>
#include<cstdlib>
#include<stack>
using namespace std;
stack<int> S;
void Cant()
{
cout<<"No solution"<<endl;
exit(0);
}
int main()
{
int n;cin>>n;
if(n%2==0)
Cant();
while(n!=1)
{
int x=(n-1)/2;
if(x%2)
S.push(2);
else
x++,S.push(1);
n=x;
}
cout<<S.size()<<endl;
while(S.size())
{ cout<<S.top()<<" ";S.pop();}
cout<<endl;
}

sgu 463

好水的题阿。。直接模拟就OK了。。不过也有一点麻烦。。一次AC了。。
http://acm.sgu.ru/problem.php?contest=0&problem=463
#include<iostream>
#define REP(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=100+10;
const int di[]={-1,0,1,0},dj[]={0,1,0,-1};
int B[maxn][maxn]={0};
bool pass[maxn][maxn]={0};
int Pass(int x,int y)
{
int ans=B[x][y];
if(pass[x][y]) ans/=2;
pass[x][y]=true;
return ans;
}
int value(int x,int y,int d)
{
int ans=0;
switch(d)
{
case 0:ans=Pass(x-1,y-1)+Pass(x-1,y);break;
case 1:ans=Pass(x-1,y)+Pass(x,y);break;
case 2:ans=Pass(x,y-1)+Pass(x,y);break;
case 3:ans=Pass(x-1,y-1)+Pass(x,y-1);break;
}
return ans;
}
int main()
{
int n,m;
cin>>n>>m;
REP(i,1,n)
REP(j,1,m)
{
char t;cin>>t;
B[i][j]=t-‘0′;
}
int d=1,x=1,y=1,ans=0;
char t;
while(cin>>t)
{
switch(t)
{
case ‘M':ans+=value(x,y,d);
x+=di[d],y+=dj[d];break;
case ‘L':d–;if(d<0) d=3;break;
case ‘R’ :d++;if(d>3) d=0;
}
}
cout<<ans<<endl;
}

写在前面。。

好不容易快搞定USACO了。。开始做sgu了。。
做了半天感觉没动力阿。。于是开个博客发题解。。就有动力了。。
本来我亡命是WJMZBMR的。。不知怎么回事注册不了。。只好改成WJBZBMR了感觉差不多。。

sgu 479题解

这是这次比赛中最简单的。。也是我唯一做出的一道。。
题目在http://acm.sgu.ru/problem.php?contest=0&problem=479
很明显最后一个肯定是1。。没1肯定每解。。然后把最后一个拿掉。。那么周围的都要-1。。然后再找倒数第二个就可以了。。注意如果某个数被-成0的话。。肯定也没解。。可以用类似拓扑排序的方式。。
Code。。偷懒效率写得很低。。。
#include<queue>
#include<stack>
#include<iostream>
#include<cstdlib>
#define REP(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=200+10;
const int di[]={-1,0,1,0},dj[]={0,1,0,-1};
int map[maxn][maxn],n,m;
bool mark[maxn][maxn]={0};
struct node
{
int x,y;
node(int x,int y):x(x),y(y){}
void show()
{
cout<<x<<" "<<y<<endl;
}
};
void Cant()
{
cout<<"No solution"<<endl;
exit(0);
}
int main()
{
cin>>n>>m;   
queue<node> Q;
stack<node> S;
REP(i,0,n+1) REP(j,0,m+1) map[i][j]=10;
REP(i,1,n)
REP(j,1,m)
{
cin>>map[i][j];   
if(map[i][j]==1)
Q.push(node(i,j));
}
while(Q.size())
{
node cur=Q.front();Q.pop();
S.push(cur);
mark[cur.x][cur.y]=true;       
REP(k,0,3)
{
int t=di[k]+cur.x,u=dj[k]+cur.y;
if(!mark[t][u]&&map[t][u]!=10)
{
map[t][u]–;
if(!map[t][u])
Cant();
if(map[t][u]==1)
Q.push(node(t,u));
}
}
}
if(S.size()!=n*m)
Cant();
while(S.size())
{
S.top().show();S.pop();
}
}

Page 54 of 54« First...102030...5051525354