比较简单的题目。。。不过有几个地方不细心也是要错的。。
主要思想当然是用stack。。维护两个stack
遇到<DOWN>或<UP>就push进这个符号的位置。。遇到另外两种就pop
然后输出的时候比较最近的UP或DOWN的位置（肯定在stack顶上）。。
万一两个stack都空的话要按原样输出。。开头结尾也要按原样输出。。。
P.S 大小写转换可以用ctype.h里面的tolower或toupper。。。
今天看到了wy的照片。。pretty阿。。。
Code。。
#include<iostream>
#include<ctype.h>
#include<string.h>
using namespace std;
const int maxn=1000;
template<typename T>
struct stack
{
T Q[maxn];
int top;
stack(){top=0;}   
bool Empty(){return top==0;}
const T& Top()
{
if(Empty()) return -1;
return Q[top-1];
}
void Pop(){top–;}
void Push(T a)
{Q[top++]=a;}
};
stack<int> U,D;
char t;
string NOW;
char a[50];
bool first=true;
int main()
{
freopen("z.in","r",stdin);
int now=0;
while(scanf("%c",&t)!=EOF)
{
now++;
if(t=='<‘)
{
if(first){cout<<NOW;first=false;goto next;}
if(D.Empty()&&U.Empty())
{cout<<NOW;goto next;}
if(D.Top()>U.Top())
{               
for(int i=0;i<NOW.length();i++)
printf("%c",tolower( NOW[i] ) );
}
else
{
for(int i=0;i<NOW.length();i++)
printf("%c",toupper( NOW[i] ));
}
next:
NOW="";
scanf("%[^>]s",a);now++;
if(a[0]==’/’)
{
if(a[1]==’D’)
D.Pop();
else
U.Pop();
}
else
{
if(a[0]==’D’)
D.Push(now);
else
U.Push(now);
}
scanf(">");
}
else
NOW+=t;
}
cout<<NOW<<endl;
}   

有点小难的数论问题哦。。
aX＝b（mod n）很好求吧。。
怎么才能把这个问题化成这种呢？
首先序列A可以mod P。。
因为a和b可以组成gcd（a，b）的任何倍数。。反之也是。。
因为可以用扩展欧几里得算出ax+by=gcd(a,b)嘛。。
故可以把a和b换成gcd（a，b）。。。
然后就一个个处理。。
若k是之前的所有数的gcd。。当前处理t。。
得出kx+ty=gcd(k,t)。。
那么之前所有数的系数全部*x（然后再modP）。。t的系数就是y
就可以使系数没有问题了。。
无解就是gcd（all包括n）无法整除b。。
然后直接输出系数就可以了。。
P.S为了方便可以把P也带入方程写成…..+PXn+1=b..
Code。。。
#include<stdio.h>
#include<iostream>
using namespace std;
const int maxn=200;
long long N,P,B;
long long A[maxn];
long long X[maxn];
long long gcd(long long a,long long b)
{
while(b){int t=a;a=b;b=t%b;}
return a;
}
void get(long long a,long long b,long long&x,long long&y)
{
if(b==0)
{
x=1;y=0;
return;
}
get(b,a%b,y,x);
y-=(a/b)*x;
}
int main()
{
cin>>N>>P>>B;
cin>>A[0];long long k=A[0];
for(int i=1;i<N;i++)
{
cin>>A[i];   
A[i]%=P;
k=gcd(k,A[i]);
}
A[N]=P;
k=gcd(k,A[N]);
if(B%k!=0)
{
cout<<"NO"<<endl;
return 0;
}   
k=gcd(A[0],A[1]);
get(A[0],A[1],X[0],X[1]);
for(int i=2;i<=N;i++)
{
long long x;
get(k,A[i],x,X[i]);
for(int j=0;j<i;j++)
{
X[j]*=x;
X[j]%=P;
while(X[j]<0)
X[j]+=P;
}
k=gcd(k,A[i]);
}
cout<<"YES"<<endl;
for(int i=0;i<N;i++)
{
X[i]*=(B/k);
X[i]%=P;
while(X[i]<0) X[i]+=P;
cout<<X[i]<<" ";
}
}

首先可以发现选中的序列无论S还是B（SB。。寒阿。。）都不能有任何逆序（也就是全递增阿。。）。。DP不就是要有一个序么。。
于是先按S排序。。那么选中的S一定就是递增的了。。然后发现就是标准LIS了。。
不过N太大。。要用nlogn的算法并且还要注意不能选S或B一样的。。
P.S
sort和binary就是好用阿。。。
不过比赛的时候不能用。。
别到时候脸qsort都不会了就四定了。。。
Code找不到了。。

很SB的完全背包问题阿。。。
P.S
由于我沙茶。。素数判定居然写错了。。还调了半天。。
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=1000;
int Q,Ps[maxn],cnt=0,snt=0;
bool isprime(int p)
{
if(p==2) return true;
if(p%2==0) return false;
for(int i=3,j=9;j<=p;i+=2,j=i*i)
if(p%i==0) return false;
return true;
}
void init()
{
cin>>Q;
cnt=1;
for(int i=3;i<=Q;i++)
if( isprime(i) )
{
cnt++;
if(isprime(cnt))
{
Ps[snt++]=i;
}
}
}
bool G[maxn*10]={0};
int F[maxn*10]={0};
int P[maxn*10]={0};
int DP(int x)
{   
if(G[x]) return F[x];
G[x]=true;
for(int i=0;i<snt;i++) if(x>=Ps[i])
if(DP(x-Ps[i])<F[x])
{
F[x]=F[x-Ps[i]];
P[x]=Ps[i];
}
F[x]++;return F[x];
}
bool cmp(const int& x,const int& y)
{ return x>y;}
void print(int x)
{
int ans[maxn],cnt=0;
if(P[x]==0) {return;}
while(x)
{
ans[cnt++]=P[x];
x-=P[x];
}
sort(ans,ans+cnt,cmp);
cout<<ans[0];
for(int i=1;i<cnt;i++)
cout<<" "<<ans[i];
}
int main()
{
init();for(int i=0;i<=Q;i++) F[i]=~0U>>3;
F[0]=0;G[0]=true;
if( DP(Q)>10000 )
{
cout<<0<<endl;
}else
{
cout<<DP(Q)<<endl;
print(Q);
}
}

经典的有点水的树DP了。。
设S[x]为以节点x为跟的子树的大小。。
画个图便可知去掉x可割出的最大块是他的全体减去他自己的大小和他的最大子树的最大值。。。
P.S
一定要用前向星阿。。
我一直是邻接表的忠实拥护者。。不过这次我受挫了。。
我真不明白，前向星是要排序的。。我用stl是nlogn。。邻接表再怎么垃圾也是O（n）的阿！！。。
怎么一个52ms一个1600+ms。。天阿！！！！
Code。。。
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=16000;
int N,cnt=0;
int H[maxn+2]={0};
//graph
struct edge
{
int s,t;
}E[maxn*2];
bool cmp(const edge&x,const edge&y)
{ return x.s<y.s;}
void add(int s,int t)
{
E[cnt].s=s;E[cnt].t=t;cnt++;
E[cnt].s=t;E[cnt].t=s;cnt++;
}
void init()
{
scanf("%d",&N);
int s,t;
for(int i=1;i<N;i++)
{
scanf("%d %d",&s,&t);
add(s,t);
}
sort(E,E+cnt,cmp);
for(int i=0;i<cnt;i++)
H[E[i].s+1]++;
for(int i=2;i<=N+1;i++)
H[i]+=H[i-1];
}
//solve
int ans=maxn+1,acnt=0;
int Ans[maxn+1];
int S[maxn+1]={0};
bool Vis[maxn+1]={0};
int dfs(int x)
{
Vis[x]=true;int Max=0;
for(int i=H[x];i<H[x+1];i++)
{
int o=E[i].t;
if(!Vis[o])
{
S[x]+=dfs(o);
Max=max(Max,S[o]);
}
}   
S[x]++;
Max=max(Max,N-S[x]);
if(Max<ans)   
ans=Max,Ans[0]=x,acnt=1;
else if(Max==ans)
Ans[acnt++]=x;
return S[x];   
}
int main()
{
init();
dfs(1);
cout<<ans<<" "<<acnt<<endl;
sort(Ans,Ans+acnt);
cout<<Ans[0];
for(int i=1;i<acnt;i++)
cout<<" "<<Ans[i];
cout<<endl;
}

这道题还是有点难的拉。。（我太沙茶了。。）
首先可以看成有依赖的背包问题。。
把牙齿和牙龈都看成物品。。牙齿若要被选则放他的牙龈也要被选。。不就是依赖么。。
首先把物品重新排一下位置（我是用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]];
}
}
}

最大流。。很好构图。。实际上不用上下界的。。
源到每个学生联一条容量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();
}

就是最短路。。没有任何难点。。就是折磨你和你的键盘的。。
感觉我写的很不错阿。。思路很清晰阿。。（小自恋一下。。。）
跟最短路一样用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;
}

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;
}      

水题。。（我只会做水题。。）
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;
}