学步园

嗯，今晚状态不错，除了卡最后一题以外没有什么太大的问题。

最后一题到最后还是wa了，估计卡精度卡的不够好。

A Reconnaissance 2

好吧，水题，直接暴力，枚举相邻元素即可，注意一下最后一个和第一个相邻就好了。

我的代码：

#include <cstdio><br /> #include <cstring><br /> #include <cstdlib><br /> #include <algorithm> </p> <p>using namespace std; </p> <p>int ar[1100]; </p> <p>int main()<br /> {<br /> int n;<br /> int ret=0;<br /> int a,b;<br /> int now; </p> <p> scanf("%d",&n);<br /> for(int i=1;i<=n;i++)<br /> {<br /> scanf("%d",&ar[i]);<br /> }<br /> ret=abs(ar[n]-ar[1]);<br /> a=1;<br /> b=n;<br /> for(int i=1;i<n;i++)<br /> {<br /> now=abs(ar[i]-ar[i+1]);<br /> if(now<ret)<br /> {<br /> ret=now;<br /> a=i;<br /> b=i+1;<br /> }<br /> }<br /> printf("%d %d/n",a,b);<br /> return 0;<br /> }<br />  

B Sale

这题还是水，贪心，直接找到最小的m个加起来，注意要小于0的，大于等于0的就break，先排序。

注意n和m双重限制，i<n&&j<m

我的代码：

#include <cstdio><br /> #include <cstring><br /> #include <cstdlib><br /> #include <algorithm> </p> <p>using namespace std; </p> <p>int ar[1100]; </p> <p>int main()<br /> {<br /> int n,m;<br /> int ret=0; </p> <p> scanf("%d%d",&n,&m);<br /> for(int i=0;i<n;i++)<br /> {<br /> scanf("%d",&ar[i]);<br /> }<br /> sort(ar,ar+n);<br /> for(int i=0,j=0;i<n&&j<m;i++)<br /> {<br /> if(ar[i]<0)<br /> {<br /> j++;<br /> ret-=ar[i];<br /> }<br /> else<br /> {<br /> break;<br /> }<br /> } </p> <p> printf("%d/n",ret); </p> <p> return 0;<br /> } 

C Page Numbers

这题直接排序，找相邻的两个数字是不是连在一起的，是就归在一起，否则新开一个区间，把原来的区间打印出来。

我的代码：

#include <cstdio><br /> #include <cstring><br /> #include <cstdlib><br /> #include <algorithm> </p> <p>using namespace std; </p> <p>char s[11000]={0};<br /> int ar[120],n=0; </p> <p>void hash()<br /> {<br /> int now; </p> <p> for(int i=0;s[i];i++)<br /> {<br /> now=0;<br /> while(s[i]&&s[i]!=',')<br /> {<br /> now=now*10+s[i++]-'0';<br /> }<br /> ar[n++]=now;<br /> }<br /> } </p> <p>int main()<br /> {<br /> gets(s);<br /> hash();<br /> int fi,se;<br /> bool flag=false; </p> <p> sort(ar,ar+n);<br /> fi=se=ar[0];<br /> for(int i=1;i<n;i++)<br /> {<br /> if(ar[i]==ar[i-1]||ar[i]==ar[i-1]+1)<br /> {<br /> se=ar[i];<br /> }<br /> else<br /> {<br /> if(flag)<br /> putchar(',');<br /> else<br /> flag=true;<br /> if(fi==se)<br /> printf("%d",fi);<br /> else<br /> printf("%d-%d",fi,se);<br /> fi=se=ar[i];<br /> }<br /> }<br /> if(flag)<br /> putchar(',');<br /> else<br /> flag=true;<br /> if(fi==se)<br /> printf("%d",fi);<br /> else<br /> printf("%d-%d",fi,se);<br /> puts(""); </p> <p> return 0;<br /> }<br />  

D Road Map

基础图论，建立一颗树，注意根是r1，第一步就是连边，然后直接从r2开始DFS，记录父亲就可以了，由于n很大，开成邻接表。

我的代码：

#include <cstdio><br /> #include <cstring><br /> #include <cstdlib><br /> #include <algorithm> </p> <p>using namespace std; </p> <p>const int MAX=51000;<br /> struct Edge<br /> {<br /> int num,ne;<br /> }e[2*MAX];<br /> int p[MAX],K;<br /> int val[MAX],vis[MAX]={0}; </p> <p>void add(const int& u,const int& v)<br /> {<br /> e[K].num=v;<br /> e[K].ne=p[u];<br /> p[u]=K++;<br /> } </p> <p>void dfs(int k,int fa)<br /> {<br /> val[k]=fa; </p> <p> for(int i=p[k];i!=-1;i=e[i].ne)<br /> {<br /> if(!vis[e[i].num])<br /> {<br /> vis[e[i].num]=true;<br /> dfs(e[i].num,k);<br /> }<br /> }<br /> } </p> <p>int main()<br /> {<br /> int n,r1,r2;<br /> int x; </p> <p> scanf("%d%d%d",&n,&r1,&r2);<br /> for(int i=1;i<=n;i++)<br /> p[i]=-1;<br /> K=0;<br /> for(int i=1;i<=n;i++)<br /> {<br /> if(i==r1)<br /> continue;<br /> scanf("%d",&x);<br /> add(i,x);<br /> add(x,i);<br /> } </p> <p> vis[r2]=true;<br /> dfs(r2,0);<br /> bool done=false;<br /> for(int i=1;i<=n;i++)<br /> {<br /> if(i==r2)<br /> continue;<br /> if(done)<br /> putchar(' ');<br /> else<br /> done=true;<br /> printf("%d",val[i]);<br /> }<br /> puts(""); </p> <p> return 0;<br /> } 

总结：恶心模拟还是没写够- -，计算几何太薄弱- -