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 5 of 512345