sgu 339

传送门http://acm.sgu.ru/problem.php?contest=0&problem=339。。
看上去好像要用到线段树。。想了半天不知道怎么搞。。于是暴力。。居然过了。。

不过很满哎。。要2.5秒多。。
才200+的人过阿。。估计都被吓住了。。。
#include<cstdio>
using namespace std;
const int maxn=1000+10;
struct seg
{
int L,R;
}S[maxn];
int main()
{
char t;int L,R,cnt=0;
while(scanf("%c %d %dn",&t,&L,&R)==3)
{
if(t==’+’)
{
S[cnt].L=L;S[cnt].R=R;int ans=0;
for(int i=0;i<cnt;i++)
if(S[i].L>=S[cnt].L&&S[i].R<=S[cnt].R)
ans++;
cnt++;
printf("%dn",ans);
}
if(t==’-‘)
{
for(int i=cnt-1;i>=0;i–)
if(S[i].L==L&&S[i].R==R)
{
cnt–;
for(int k=i;k<cnt;k++)
S[k]=S[k+1];               
break;
}
}
}
}

sgu 484

水题。。绝对的水题。。暴力模拟就OK了。。
PS实现的时候可以对墙使用哨兵。。
Code。。
#include<iostream>
#define REP(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=102;
char map[maxn][maxn]={0};
int main()
{
int n,m,nowx,nowy;
cin>>n>>m;
REP(i,1,n) REP(j,1,m)
{
cin>>map[i][j];   
if(map[i][j]==’P’)
nowx=i,nowy=j;
}
char old=’P';   
bool fall=false;
while(true)
{               
if(nowx==n+1)
{
cout<<nowy;
break;
}
char t=map[nowx][nowy];
map[nowx][nowy]=0;
if(!t)
{
cout<<-1;
break;
}           
if(t==old&&!fall)
nowx++,fall=true;
else if(t==’/’)
nowy–,fall=false;
else if(t==’\’)
nowy++,fall=false;
else nowx++,fall=true;
old=t;
}   
}
遇见水题太激动居然交错了题号。。还连交了3边。。我的AC率阿。。      

sgu 130

好好好水的题目。。Catalan数或者暴力DP都可以阿。。
好短的代码。。。
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
int K,P;
long long H[40]={0};
cin>>K;
P=K+1;
H[0]=1;
for(int i=1;i<=K;i++)
for(int j=0;j<i;j++)
H[i]+=H[j]*H[i-j-1];
cout<<H[K]<<" "<<P<<endl;
}

sgu 302

比较简单的题目。。。不过有几个地方不细心也是要错的。。
主要思想当然是用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;
}   

sgu 140

有点小难的数论问题哦。。
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]<<" ";
}
}

sgu 199

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

sgu 116

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

sgu 134

经典的有点水的树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;
}

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

Page 4 of 512345