【组队赛#9】USACO 2006 January Bronze

【组队赛#9】USACO 2006 January Bronze

【A题】A. Stump Removal 链接​​click here~~​​

【题目大意】一排高低不平的树桩，需要用炸弹全部炸掉，如果一个树桩的前面和后面的树桩高度都比它小，炸弹爆炸的时候会同时炸掉，求尽可能少的放置炸弹的数目，输出树桩的编号​​。​​

【解题思路】 理解题意，从左往右扫，如果当前位置右边或左边的比它低了或相等，那么就把这个位置炸掉，然后把能炸的都炸掉，判断当前树桩前面的和后面的高度比较，

核心代码

for(int i=1;i<=n+1;i++) { if(a[i]>=a[i-1]&&a[i]>=a[i+1]) cout<

【F题】F. Dollar Dayz BNU 14323

【题目大意】大数！求解钱币组合问题，坑题一道~~

代码：

/*Author:HRW大数！*/#include #include #include #include #include using namespace std;const int maxn = 1001;struct bign{ int len,s[maxn]; bign() { memset(s,0,sizeof(s)); len = 1; } bign operator = (const char *num) { len = strlen(num); for(int i=0; i 1 && !s[len-1]) len--; } bign operator += (const bign& b) { *this = *this + b; return *this; }};istream& operator >>(istream &in, bign& x){ string s; in>>s; x = s.c_str(); return in;}ostream& operator << (ostream &out, const bign& x){ out << x.str(); return out;}bign AC[1002];int main(){ int n,k; while(cin>>n>>k) { AC[0] = 1; for(int i=1; i<=k; i++) for(int j=i; j<=n; j++) AC[j]+=AC[j-i]; cout<

【E题】E. Redundant Paths BNU14319

【题目大意】给你一个连通的无向图G，至少要添加几条边，才能使其变为双连通图，和POJ 3177一样

【解题思路】一个有桥的连通图要变为双连通图的话，把双连通图收缩为一个点，形成一颗树，需要加的边为（L+1）/2，L为叶子节点个数

ps:BNU竟然加外挂会超时~~orz,以后还是得多注意。。

代码：

/**/#includeusing namespace std;const int maxn=5010;//点数const int maxm=20100;//边数,无向struct Edge{ int to,next; bool cut;//是否是桥标记} edge[maxm];int head[maxn],tot;int Low[maxn],DFN[maxn],Stack[maxn],Belong[maxn];int Index,top;int block;//边双连通块数bool instack[maxn];int bridge;//桥的数目void addedge(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; edge[tot].cut=false; head[u]=tot++;}void Tarjan(int u,int pre){ int v; Low[u]=DFN[u]=++Index; Stack[top++]=u; instack[u]=true; for(int i=head[u];i!=-1;i=edge[i].next) { v=edge[i].to; if(v == pre) continue; if(!DFN[v]) { Tarjan(v,u); if(Low[u]>Low[v]) Low[u]=Low[v]; if(Low[v]>DFN[u]) { bridge ++; edge[i].cut = true; edge[i^1].cut = true; } } else if(instack[v]&&Low[u]>DFN[v]) Low[u]=DFN[v]; } if(Low[u]==DFN[u]) { block++; do { v=Stack[--top]; instack[v]=false; Belong[v]=block; } while(v!=u); }}void init(){ tot=0; memset(head,-1,sizeof(head));}int du[maxn];//缩点后形成树，每个点的度数void solve(int n){ memset(DFN,0,sizeof(DFN)); memset(instack,false,sizeof(instack)); Index=top=block=0; Tarjan(1,0); int res=0; memset(du,0,sizeof(du)); for(int i=1; i<=n; i++) for(int j=head[i]; j!=-1; j=edge[j].next) if(edge[j].cut) du[Belong[i]]++; for(int i=1; i<=block; i++) if(du[i]==1) res++;//找叶子节点个数为res,构造边双连通图需要加边（res+1）/2 printf("%d\n",(res+1)/2);}int shuru(){ int sum=0; char ch; while((ch=getchar())<='0'||ch>='9');sum=ch-'0'; while((ch=getchar())>='0'&&ch<='9') sum=sum*10+ch-'0'; return sum;}int main(){ //freopen("1.txt","r",stdin); int n,m,u,v; while(scanf("%d%d",&n,&m)==2) { init(); while(m--) { //scanf("%d%d",&u,&v); u=shuru(); v=shuru(); addedge(u,v); addedge(v,u); } solve(n); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。