自定义菜单-弹出式菜单_舒展树(splay tree) 学习二：poj3468：A Simple Problem with Integers_苏州户籍准入登记暂行办法__脚本百事通
稍等，加载中……
^_^请注意，有可能下面的2篇文章才是您想要的内容：
自定义菜单-弹出式菜单
舒展树(splay tree) 学习二：poj3468：A Simple Problem with Integers
苏州户籍准入登记暂行办法
自定义菜单-弹出式菜单
自定义菜单--弹出式菜单
===================================================================
package com.wjq.
import java.util.ArrayL
import java.util.HashM
import android.app.A
import android.app.AlertD
import android.content.DialogI
import android.content.DialogInterface.OnKeyL
import android.os.B
import android.view.KeyE
import android.view.M
import android.view.V
import android.widget.AdapterV
import android.widget.GridV
import android.widget.SimpleA
import android.widget.AdapterView.OnItemClickL
public class CustomizeMenu extends Activity {
private boolean isMore =// menu菜单翻页控制
AlertDialog menuD// menu菜单Dialog
GridView menuG
View menuV
private final int ITEM_SEARCH = 0;// 搜索
private final int ITEM_FILE_MANAGER = 1;// 文件管理
private final int ITEM_DOWN_MANAGER = 2;// 下载管理
private final int ITEM_FULLSCREEN = 3;// 全屏
private final int ITEM_MORE = 11;// 菜单
/** 菜单图片 **/
int[] menu_image_array = { R.drawable.menu_search,
R.drawable.menu_filemanager, R.drawable.menu_downmanager,
R.drawable.menu_fullscreen, R.drawable.menu_inputurl,
R.drawable.menu_bookmark, R.drawable.menu_bookmark_sync_import,
R.drawable.menu_sharepage, R.drawable.menu_quit,
R.drawable.menu_nightmode, R.drawable.menu_refresh,
R.drawable.menu_more };
/** 菜单文字 **/
String[] menu_name_array = { "搜索", "文件管理", "下载管理", "全屏", "网址", "书签",
"加入书签", "分享页面", "退出", "夜间模式", "刷新", "更多" };
/** 菜单图片2 **/
int[] menu_image_array2 = { R.drawable.menu_auto_landscape,
R.drawable.menu_penselectmodel, R.drawable.menu_page_attr,
R.drawable.menu_novel_mode, R.drawable.menu_page_updown,
R.drawable.menu_checkupdate, R.drawable.menu_checknet,
R.drawable.menu_refreshtimer, R.drawable.menu_syssettings,
R.drawable.menu_help, R.drawable.menu_about, R.drawable.menu_return };
/** 菜单文字2 **/
String[] menu_name_array2 = { "自动横屏", "笔选模式", "阅读模式", "浏览模式", "快捷翻页",
"检查更新", "检查网络", "定时刷新", "设置", "帮助", "关于", "返回" };
protected void onCreate(Bundle savedInstanceState) {
// TODO Auto-generated method stub
super.onCreate(savedInstanceState);
setContentView(R.layout.main);
menuView = View.inflate(this, R.layout.gridview_menu, null);
// 创建 菜单对话框
menuDialog = new AlertDialog.Builder(this).create();
menuDialog.setView(menuView);
menuDialog.setOnKeyListener(new OnKeyListener() {
public boolean onKey(DialogInterface dialog, int keyCode,
KeyEvent event) {
if (keyCode == KeyEvent.KEYCODE_MENU)// 监听按键
dialog.dismiss();
menuGrid = (GridView) menuView.findViewById(R.id.gridview);
menuGrid.setAdapter(getMenuAdapter(menu_name_array, menu_image_array));
/** 监听menu选项 **/
menuGrid.setOnItemClickListener(new OnItemClickListener() {
public void onItemClick(AdapterView&?& arg0, View arg1, int arg2,
long arg3) {
switch (arg2) {
case ITEM_SEARCH:// 搜索
case ITEM_FILE_MANAGER:// 文件管理
case ITEM_DOWN_MANAGER:// 下载管理
case ITEM_FULLSCREEN:// 全屏
case ITEM_MORE:// 翻页
if (isMore) {
menuGrid.setAdapter(getMenuAdapter(menu_name_array2,
menu_image_array2));
} else {// 首页
menuGrid.setAdapter(getMenuAdapter(menu_name_array,
menu_image_array));
menuGrid.invalidate();// 更新menu
menuGrid.setSelection(ITEM_MORE);
public boolean onCreateOptionsMenu(Menu menu) {
menu.add("menu");// 必须创建一项
return super.onCreateOptionsMenu(menu);
private SimpleAdapter getMenuAdapter(String[] menuNameArray,
int[] imageResourceArray) {
ArrayList&HashMap&String, Object&& data = new ArrayList&HashMap&String, Object&&();
for (int i = 0; i & menuNameArray. i++) {
HashMap&String, Object& map = new HashMap&String, Object&();
map.put("itemImage", imageResourceArray[i]);
map.put("itemText", menuNameArray[i]);
data.add(map);
SimpleAdapter simperAdapter = new SimpleAdapter(this, data,
R.layout.item_menu, new String[] { "itemImage", "itemText" },
new int[] { R.id.item_image, R.id.item_text });
return simperA
public boolean onMenuOpened(int featureId, Menu menu) {
if (menuDialog == null) {
menuDialog = new AlertDialog.Builder(this).setView(menuView).show();
menuDialog.show();
// 返回为true 则显示系统menu
========================================================================
package com.wjq.
import android.app.A
import android.os.B
import android.view.M
import android.view.MenuI
import android.widget.T
public class DefaultMenu extends Activity {
public void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.main);
public boolean onCreateOptionsMenu(Menu menu) {
* add()方法的四个参数，依次是：
* 1、组别，如果不分组的话就写Menu.NONE,
* 2、Id，这个很重要，Android根据这个Id来确定不同的菜单
* 3、顺序，那个菜单现在在前面由这个参数的大小决定
* 4、文本，菜单的显示文本
// setIcon()方法为菜单设置图标，这里使用的是系统自带的图标，同学们留意一下,以
// android.R开头的资源是系统提供的，我们自己提供的资源是以R开头的
menu.add(Menu.NONE, Menu.FIRST + 1, 5, "删除").setIcon(
android.R.drawable.ic_menu_delete);
menu.add(Menu.NONE, Menu.FIRST + 2, 2, "保存").setIcon(
android.R.drawable.ic_menu_edit);
menu.add(Menu.NONE, Menu.FIRST + 3, 6, "帮助").setIcon(
android.R.drawable.ic_menu_help);
menu.add(Menu.NONE, Menu.FIRST + 4, 1, "添加").setIcon(
android.R.drawable.ic_menu_add);
menu.add(Menu.NONE, Menu.FIRST + 5, 4, "详细").setIcon(
android.R.drawable.ic_menu_info_details);
menu.add(Menu.NONE, Menu.FIRST + 6, 3, "发送").setIcon(
android.R.drawable.ic_menu_send);
public boolean onOptionsItemSelected(MenuItem item) {
switch (item.getItemId()) {
case Menu.FIRST + 1:
Toast.makeText(this, "删除菜单被点击了", 2000).show();
case Menu.FIRST + 2:
Toast.makeText(this, "保存菜单被点击了", 2000).show();
case Menu.FIRST + 3:
Toast.makeText(this, "帮助菜单被点击了", 2000).show();
case Menu.FIRST + 4:
Toast.makeText(this, "添加菜单被点击了", 2000).show();
case Menu.FIRST + 5:
Toast.makeText(this, "详细菜单被点击了", 2000).show();
case Menu.FIRST + 6:
Toast.makeText(this, "发送菜单被点击了", 2000).show();
public void onOptionsMenuClosed(Menu menu) {
// Toast.makeText(this, "选项菜单关闭了", 2000).show();
public boolean onPrepareOptionsMenu(Menu menu) {
// Toast.makeText(this,
// "选项菜单显示之前onPrepareOptionsMenu方法会被调用，你可以用此方法来根据当时的情况调整菜单", 2000)
// .show();
// 如果返回false，此方法就把用户点击menu的动作给消费了，onCreateOptionsMenu方法将不会被调用
舒展树(splay tree) 学习二：poj3468：A Simple Problem with Integers
伸展树(splay tree) 学习二：poj3468：A Simple Problem with Integers
A Simple Problem with Integers
Time Limit: 5000MS
Memory Limit: 131072K
Total Submissions: 54991
Accepted: 16540
Case Time Limit: 2000MS
Description
Sample Input
1 2 3 4 5 6 7 8 9 10
Sample Output
带区间操作的splay，要用lazy标记，对于区间[a,b]，我们可以通过Splay操作将a-1伸展到根，将b+1伸展到根的右子结点，b+1的左子结点代表的就是区间[a,b]。就如同线段树的成段更新一样，用Splay进行区间操作的时候，也要利用lazy标记
注意！！建树时，中间结点为父结点，区间左端为左子树，区间右端为右子树，这样就保证始终有序，之后的旋转不改变。
区间可能靠近两端点，当减1加1时可能溢出，不方便处理，可以在两端加入冗余结点。
#include&cstdio&
#include&cstring&
#include&algorithm&
#include&iostream&
#define INF 1&&30
#define LL long long
#define N 100005
int pre[N],key[N],ch[N][2],root,tot,n;
父节点 、键值、左右子节点(0为左孩子，1为右孩子) 、根节点 、节点数目
int size[N],s[N],stot,val[N];
//分别表示子树规模，内存池，内存池容量
int add[N];
LL sum[N]; //延迟标记，子树结点和
void Newnode(int &p,int fa,int keyy) //新建一个节点
p=s[--stot];
size[p]=1;
ch[p][0]=ch[p][1]=0;
void Push_Down(int r)//将延迟标记更新到孩子结点
if (add[r])
val[r]+=add[r];
add[ch[r][0]] += add[r];
add[ch[r][1]] += add[r];
sum[ch[r][0]] += (LL) add[r] * size[ch[r][0]];
sum[ch[r][1]] += (LL) add[r] * size[ch[r][1]];
void Push_Up(int r)//通过孩子结点更新父结点
size[r]=size[ch[r][0]] + size[ch[r][1]] + 1;
sum[r] =sum [ch[r][0]] + sum [ch[r][1]] + add[r] + val[r];
void Rotate(int x, int kind)//k为1时右旋, k为0时左旋
int y=pre[x];
Push_Down(x);
Push_Down(y);
ch[y][!kind]=ch[x][kind];
pre[ch[x][kind]]=y;
if (pre[y])//如果父节点不是根结点，则要和父节点的父节点连接起来
ch[pre[y]][ch[pre[y]][1]==y]=x;
pre[x]=pre[y];
ch[x][kind]=y;
Push_Up(y);
void Splay(int r,int goal)////Splay调整，将根为r的子树调整为goal
Push_Down(r);
while (pre[r]!=goal)
if (pre[pre[r]]==goal)
Rotate(r,ch[pre[r]][0]==r);
int y=pre[r];
int kind=ch[pre[y]][0]==y;
if (ch[y][kind]==r)
Rotate(r,!kind);
Rotate(r,kind);
Rotate(y,kind);
Rotate(r,kind);
Push_Up(r);
if (goal==0) root=r;
int Insert(int k)
while (ch[root][key[root]&k])
root=ch[root][key[root]&k];
Newnode(ch[root][k&key[root]],root,k);
Splay(ch[root][k&key[root]],0);
void RotateTo(int k,int goal) //把第k位的数转到goal下边
Push_Down(r);
while (size[ch[r][0]]!=k)
if (k & size[ch[r][0]])
r=ch[r][0];
k-=(size[ch[r][0]]+1);
r=ch[r][1];
Push_Down(r);
Splay(r,goal);
int get_pre(int x)
int tmp=ch[x][0];
if (tmp == 0) return INF;
while (ch[tmp][1]) tmp=ch[tmp][1];
return key[tmp];
int get_next(int x)
int tmp=ch[x][1];
if (tmp == 0) return INF;
while (ch[tmp][0]) tmp=ch[tmp][0];
return key[tmp];
LL Query(int l,int r)//查询[l,r]的和
RotateTo(l-1,0);
RotateTo(r+1,root);
return sum[ch[ch[root][1]][0]];
void Updata(int l,int r)
scanf("%d",&k);
RotateTo(l-1,0);
RotateTo(r+1,root);
add[ch[ch[root][1]][0]] +=
sum[ch[ch[root][1]][0]] += k * size[ch[ch[root][1]][0]];
int a[100000];
void Build(int &x,int l,int r,int fa)
int mid=(l + r) / 2;
Newnode(x,fa,a[mid]);
if (l & mid)
Build(ch[x][0],l,mid-1,x);
if (r & mid)
Build(ch[x][1],mid+1,r,x);
Push_Up(x);
void Init()
for (int i=0; i&n; i++)
scanf("%d",&a[i]);
ch[0][0]=ch[0][1]=pre[0]=size[0]=add[0]=sum[0]=root=tot=0;
Newnode(root,0,-1);
Newnode(ch[root][1],root,-1);
size[root]=2;
Build(ch[ch[root][1]][0],0,n-1,ch[root][1]);
Push_Up(ch[root][1]);
Push_Up(root);
int main()
while (scanf("%d%d",&n,&query)!=EOF)
while (query--)
char st[10];
scanf("%s%d%d",st,&x,&y);
if (st[0] == 'Q')
printf("%I64d\n",Query(x,y));
Updata(x,y);
苏州户籍准入登记暂行办法
苏州市户籍准入登记暂行办法
各市、区人民政府，苏州工业园区、苏州高新区、太仓港口管委会;市各委办局，各直属单位：
《苏州市户籍准入登记暂行办法》（修订）已经市政府第74次常务会议讨论通过，现予印发，请认真贯彻执行。
二OO七年八月二十七日
苏州市户籍准入登记暂行办法（修订）
为适应苏州市经济社会发展需要，根据国家和省政府有关文件精神，结合实际，制定本办法。
在全市范围内取消农业户口、非农业户口性质，凡居民在我市登记的户口，统称为“居民户口”。
在本市申请户口迁移实行条件准入制。凡在本市具有合法固定住所、稳定职业或生活来源基本条件的人员，要求将户口从外市迁入本市市区和县级市或从本市县级市迁往市区的，经有关部门受理，符合本办法的准予迁入。在迁入地无直系亲属的18周岁以下人员，不予准迁。凡迁入人员需符合国家计划生育相关政策，违反规定超生的必须经市人口计生部门核准。
在本市市区或县级市范围内申请迁移的，实行以具有合法固定住所为基本条件的准入登记制度。
本办法所称合法固定住所是指：申请迁移人在本市居住房屋属于自己的产权房屋或租住属公有产权并领取使用权证的房屋。
本办法所称稳定职业或生活来源是指：申请迁移人在本市通过合法手续取得的各类工作，且签订劳动合同、参加社会养老保险，有一定的经济来源，包括退休人员退休工资等其他合法的社会保障，人均收入不低于苏州市最低生活保障线。
下列人员户口准入，由市或县级市人事局受理：
（一）具有高级专业技术职务任职资格或硕士及以上学位的人员；
（二）在国外、境外取得学位的留学人员；
（三）具有中级职称或本科学历，且年龄男性40周岁以下、女性35周岁以下的专业技术和管理人员；
（四）被单位合法聘用（经劳动和社会保障部门备案并办理特聘工作证），连续工作满2年以上，同时段交纳社保、医保、公积金，具有大专或中专学历且年龄在30周岁以下，并拥有合法固定住所的人员;
（五）按照毕业生就业政策，接收安置的毕业研究生、本科生、专科生及苏州市生源的大中专毕业生；
（六）因家庭实际困难需要照顾父母、配偶而调动的在职干部及符合随迁条件的配偶和未成年或待业未婚子女；
（七）需人事局审批准入的其他人员；
上述（一）至（三）项人员除本人户口准迁外，允许其配偶及未成年或待业未婚子女随迁。
下列人员户口准入，由市或县级市劳动和社会保障局受理：
（一）因家庭实际困难需要照顾父母、配偶而调动的在职职工及符合随迁条件的配偶和未成年或待业未婚子女；
（二）生产急需，经考核符合要求引进的技术、管理人员；
（三）按照毕业生就业政策，接收安置毕业的苏州市生源技（职）校毕业生；
（四）往届技（职）校毕业生被单位合法录用，参加社保、医保、公积金，年龄在30周岁以下，工作满2年，并拥有合法固定住所的；
（五）需劳动和社会保障局审批准入的其他人员。
下列人员户口准入，由公安机关受理：
（一）在市区个人投资实收资本人民币100万元以上，并合法经营3年以上，或近3年累计纳税人民币20万元以上，按规定参加社保3年以上，并拥有合法固定住所的人员，允许其本人、配偶及其未成年子女整户迁入；
（二）购买市区成套商品住房75平方米以上，取得房屋所有权证3年以上，且被单位合法聘录用3年以上，按规定参加社保3年以上，具有合法稳定经济收入的，允许其本人、配偶及其未成年子女整户迁入；
（三）购买市区成套商品住房75平方米以上，取得房屋所有权证3年以上，在市区经商、兴办企业3年以上，近3年累计纳税5万元以上，按规定参加社保3年以上，允许其本人、配偶及其未成年子女整户迁入；
（四）投靠父亲或母亲的未成年子女；
（五）结婚后需投靠的外市无业城镇或农村配偶；
（六）需投靠子女的城镇退休（无业）父母或农村男60周岁、女50周岁以上的父母；
（七）符合准入迁移后的人员申请父母投靠的，需自迁入后满5年以上方可提出投靠子女申请迁移，且迁入后人均住房面积和生活保障水平不低于苏州市最低标准；
（八）需公安机关审批准入的其他人员。
凡被本市各类院校录取的本市籍学生，入学时不再迁移户口，被外地院校录取的，允许不迁户口的可不迁，均待其毕业后根据分配去向直接将户口迁往工作单位所在地或实际居住地。被本市各类院校录取的外市籍学生，户口迁移仍按照国家有关规定办理。
凡本办法第五至第七条中所涉及的年龄、工作年限、投资纳税金额或购房面积，各县级市可根据本地实际确定。
凡涉及国家指令性计划安置的人员，由相关部门按国家有关政策办理。
本市居民在市区范围内的户口迁移和农民子女出生、录取学生办理的迁移登记，只作户籍变更登记，不与经济利益挂钩，如涉及经济、土地分配和计划生育等问题的，按国家有关规定办理。
凡提出申请要求的人员，应根据申请的理由，提供相应的证明材料。提供证明材料要求由相关受理部门公示。凡以虚假证明材料骗取户口的，注销其已迁入的户口退还原籍，并依照国家相关法规作出处理。
经人事、劳动和社会保障部门批准迁入苏州市区或县级市的人员，统一凭《调动人员情况登记表》至迁入地公安分局或县级市公安局开具《户口准予迁入证明》；经公安机关批准的，由公安分局或县级市公安局开具《户口准予迁入证明》；当年大中专以上毕业生，凭加盖市或县级市人事部门专用章的《户口迁移证》至迁入地公安派出所办理落户手续。
本办法自公布之日起施行。原《苏州市户籍准入登记暂行办法》（苏府〔2003〕67号）同时废止。
如果您想提高自己的技术水平，欢迎加入本站官方1号QQ群：&&，&&2号QQ群：，在群里结识技术精英和交流技术^_^
本站联系邮箱：PKU第二篇：取模运算_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
98页免费35页免费76页免费76页免费9页免费 30页免费38页免费26页免费34页2下载券34页免费
喜欢此文档的还喜欢20页1下载券9页1下载券9页免费3页免费37页免费
PKU第二篇：取模运算|本​程​序​功​能​ ​ ​实​现​两​个​整​数​的​取​模​运​算​ ​ ​ ​主​要​考​查​编​程​者​字​符​串​拆​分​及​转​换​!
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢10. 微软面试题：标题：求1+2+…+n_IOS7学习之路十（百度mapAPI环境搭建）_usaco 月赛 2003 Fall Popular Cows 受欢迎的乳牛 题解__脚本百事通
稍等，加载中……
^_^请注意，有可能下面的2篇文章才是您想要的内容：
10. 微软面试题：标题：求1+2+…+n
IOS7学习之路十（百度mapAPI环境搭建）
usaco 月赛 2003 Fall Popular Cows 受欢迎的乳牛 题解
10. 微软面试题：标题：求1+2+…+n
10. 微软面试题：题目：求1+2+…+n，
题目：求<span style="color:#+2+…+n，
要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A?B:C）。
这题本来有很多思路，直接使用公式1+2+...+n = n*(n+1)/2 这样直接可以得出结果。
或者使用循环遍历方法，1+2+...也很好实现，
但是不能使用乘除法，或者for,while语句。这就比较难了。
可以换这思路，使用递归思想，f(n) = f(n-1) + n 并且f(1) = 1, f(2) = f(1) + 2， 但这里面也有个问题，递归时，什么时候结束递归呢，就需要使用if语句，题目中要求不能使用if，那咋办呢？
有没有一个语句，不适用题目要求中提到的关键字来实现呢？
有个运算符，有这个功能：&& ， A&&B
如果A为0或者false的话，B就不执行。
<span style="color:#+2+...+10 = 55
那我们可以实现下：
#include&iostream&
int add(int n, int& sum)
(n-1)&&add(n-1, sum);
int main()
int sum = 0;
cout && "1+2+...+10 = " &&
add(10, sum) &&
运行结果为：
<span style="color:#+2+...+n = 55
IOS7学习之路十（百度mapAPI环境搭建）
IOS7学习之路十（百度地图API环境搭建）百度地图官网的API开发教程链接：点击打开链接
我按照他的教程做的总出现“Apple
Mach-O linker command failed with exit code 1”的错误，于是只好自己上网搜了。
下面说说自己的搭建环境的方法吧
：我错误的原因是引入静态库的时候路径错误导致的
1.下载链接点击打开链接
2。解压后如下：
3.把以上三个inc
mapapi.bundle文件复制粘贴到项目根目录下
点击Xcode中项目名。原则add projects to"XXX" 把inc文件夹、mapapi.bundle文件和libs/Release-iphoneos文件夹中的libbaidumapapi.a添加到项目中。
4 几乎所有的第三方地图sdk都是依赖于apple自有的几个framework，所以这一步需要我们导入：CoreLocation.framework和QuartzCore.framework、OpenGLES.framework、SystemConfiguration.framework、CoreGraphics.framework。导入方法如下：
1）.在XCode的Project -& Edit Active Target -& Build -& Linking -& Other Linker Flags中添加-ObjC
2）.设置静态库的链接路径，在XCode的Project -& Edit Active Target -& Build -& Search Path -& Library Search Paths中添加您的静态库目录，$(SRCROOT)/libs/Release$(EFFECTIVE_PLATFORM_NAME)
Library Search Paths中这一个就够了把其他的删除
注:静态库中采用ObjectC++实现，因此需要您保证您工程中至少有一个.mm后缀的源文件(您可以将任意一个.m后缀的文件改名为.mm)，或者在工程属性中指定编译方式，即将XCode的Project -& Edit Active Target -& Build -& GCC4.2 - Language -& Compile Sources As设置为"Objective-C++"
选中工程，target，切换到Build Setting标签，定位到other link flag，
输入：-all_load
7.剩下的就只有代码工作了，由于需要key的验证，所以我们先需要使用BMKMapManager类，配置申请到的key，以得到授权。选中AppDelegate.h
[plain] view
选中AppDelegate.m，修改成.mm，（注:静态库中采用ObjectC++实现，因此需要您保证您工程中至少有一个.mm后缀的源文件(您可以将任意一个.m后缀的文件改名为.mm)）【注意：如果没有mm，运行会大量报错的】在AppDelegate.mm中的didFinishLaunchingWithOptions,加入如下代码：
[plain] view
8 在需要显示地图的viewcontroller.m中加入如下代码：
[plain] view
导入BMKMapView.h后，实例化BMKMapView类。
自2.0.0起，BMKMapView新增viewWillAppear、viewWillDisappear方法来控制BMKMapView的生命周期，并且在一个时刻只能有一个BMKMapView接受回调消息，因此在使用BMKMapView的viewController中需要在viewWillAppear、viewWillDisappear方法中调用BMKMapView的对应的方法，并处理delegate，代码如下：
源码复制打印关于
(void)viewWillAppear:(BOOL)animated
[_mapView viewWillAppear];
_mapView.delegate =
-(void)viewWillDisappear:(BOOL)animated
[_mapView viewWillDisappear];
_mapView.delegate =
编译，运行，效果如下图所示：
usaco 月赛 2003 Fall Popular Cows 受欢迎的乳牛 题解
usaco 月赛 2003 Fall Popular Cows 受欢迎的奶牛 题解
Popular Cows题解
Time Limit: 2000MS
Memory Limit: 65536K
Total Submissions: 21696
Accepted: 8859
Description
Sample Input
Sample Output
【大意】给定N（N&=10000)个点和M（M&=50000)条边（注意：是有向边），求有多少个“受欢迎的点”。所谓的“受欢迎的点”当且仅当任何一个点出发都能到达它。
【首先发现】99%的人都会想到直接用floyed来求。可惜的是，N太大了。我们再考虑新的算法。
【分析】让人厌烦的是，这道题可能会有环，即A--B,B--C,C--A。
先考虑无环的情况。定理1：若有向无环图是连通的，只有出度为0的点才是“受欢迎的点”。
伪证明：设某点X是“受欢迎的点”，且该点仍有出度。不妨设它能到达Y点。因为是有向无环图，那么Y是一定不能到达X点了！即X点并不是“受欢迎的点”——与条件矛盾，命题得证。
定理2：若有向无环图是连通的，当存在大于1个出度为0的点，则图中没有“受欢迎的点”。
伪证明：设点X和点Y是出度为0的点，那么X不能到达Y。命题得证。
【小结】太容易了吧！我们只要寻找出度为0的点，如果不止一个，就没有答案，否则就是那个点！
【深入思考】下面我们的任务就是要缩环成点。著名的Tarjan算法跳出来了！它的效率是O（N+M），太厉害了！（如果不知道Tarjan的实现过程，点击这里）那么只要在找到每一个强连通分量之后，对它中的每一个点并查集维护一下，就能缩成一个点了。
【注意点】①数量大，要用边表来记录。
②调用Tarjan算法时，要循环每一个点。一开始我一直WA，就是因为只从1号点进入递归。
#include&stdio.h&
#include&cstring&
const int v=10000+5;const int e=50000+5;
struct arr{int went,}a[e];
int begin[v],end[v],b[v],dfs[v],low[v],f[v];
bool flag[v],zhan[v],bre,ff[v];
int deep,step,n,m,i,x,y,cnt,j,go,temp,
void make_up(int u,int v)
a[++cnt].went=v;
if (begin[u]==0) {begin[u]=end[u]=}
else {a[end[u]].next=end[u]=}
int get(int u){if (u==f[u])return f[u]=get(f[u]);}
void Union(int u,int v){int uu=get(u);int vv=get(v);f[vv]=}
void print(int k)
int fa=b[deep];zhan[fa]=
deep--;if (fa==k)
int i=b[deep];
Union(fa,i);
void find(int k)
dfs[k]=low[k]=++
flag[k]=b[++deep]=k;zhan[k]=
for (int i=begin[k];i!=0;i=a[i].next)
int go=a[i].
if (!flag[go])
find(go);if (low[go]&low[k]) low[k]=low[go];
if ((zhan[go])&&(dfs[go]&low[k])) low[k]=dfs[go];
if (dfs[k]==low[k]) print(k);
int main()
freopen("popular.in","r",stdin);
freopen("popular.out","w",stdout);
scanf("%ld%ld",&n,&m);
for (i=1;i&=m;i++)
scanf("%ld%ld",&x,&y);
make_up(x,y);
step=0;deep=1;b[1]=1;zhan[1]=
for (i=1;i&=n;i++) f[i]=i;
for (i=1;i&=n;i++)
if (!flag[i]) find(i);
for (i=1;i&=n;i++)
j=begin[i];bre=
while (j!=0)
if (get(i)!=get(go)) {bre=}
if (bre) ff[get(i)]=
for (i=1;i&=n;i++)
if ((f[i]==i)&&(!ff[i]))
cnt++;temp=i;
if (cnt!=1) {printf("0");return 0;}
for (i=1;i&=n;i++)
if (get(i)==temp) ans++;
printf("%ld",ans);
如果您想提高自己的技术水平，欢迎加入本站官方1号QQ群：&&，&&2号QQ群：，在群里结识技术精英和交流技术^_^
本站联系邮箱：