ICPC North Central NA Contest 2017

C. Urban Design

https://nanti.jisuanke.com/t/43370

解题方法:这一题其实也不难,只要你画几个例子就很容易找到规律,但要注意的是我们用直线的一般式来判断两条直线是否相交,因为如果直接比较两条直线的斜率,会存在斜率求不出来的情况,这样比较复杂


#include<iostream>
using namespace std;
struct node{
	double a;
	double b;
	double c;
}st[100010];
int n;
bool is_region(double x1,double y1,double x2,double y2){
	int cnt=0;
	for(int i=0;i<n;i++){
		double a=st[i].a;
		double b=st[i].b;
		double c=st[i].c;
		if((a*x1+b*y1+c)*(a*x2+b*y2+c) > 0){
			continue;
		}else{
			cnt++;
		}
	}
	if(cnt%2==0){
		return false;
	}else{
		return true;
	}
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		double x1,y1,x2,y2;
		scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
		double A=y2-y1;
		double B=x1-x2;
		double C=x2*y1-x1*y2;
		st[i].a=A;
		st[i].b=B;
		st[i].c=C; 
	}
	int t;
	cin>>t;
	while(t--){
		double x3,y3,x4,y4;
		cin>>x3>>y3>>x4>>y4;
		if(is_region(x3,y3,x4,y4)){
			cout<<"different"<<endl;
		}else{
			cout<<"same"<<endl;
		}
	} 
	return 0;
}


G. Sheba's Amoebas  

 题意:本题就是要你判判断存在几个闭环
解题方法:dfs深搜即可,但要注意它找到起点的处理方法
#include<iostream>
#include<string.h>
using namespace std;
char ptr[150][150];
int vis[150][150];
int m,n;/*m行 n列*/
int ans=0;/*存储答案*/
int net[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,1},{-1,-1},{1,-1}};
bool check(int dx,int dy){
    if(dx<0||dx>=m||dy<0||dy>=n){
        return false;
    }
    if(ptr[dx][dy]=='#'&&vis[dx][dy]==0/*没有被访问过*/){//是黑色素 可行
        return true;
    }else{
        return false;
    }
}
bool check_c(int x,int y){//形成闭环
    if(ptr[x][y]=='K'){/*找到了*/
    	ptr[x][y]='Y'; 
        return true;
    }else{
        return false;
    }
}
void dfs(int x,int y){/*传进去的是现在的位置,我们现在要找它的下一个位置*/
	/*而且下一个位置它有 8 种可能*/
	//下面我们寻找下一个位置
	//判断是否形成闭环
	for(int i=0;i<8;i++){/*判断其余几个方向还有没有路可以走*/
        int dx=x+net[i][0];
        int dy=y+net[i][1];
        if(check(dx,dy)){//检测它是不是‘#’ 和坐标是否在合法范围内
            vis[dx][dy]=1;/*标记被访问*/
            ptr[dx][dy]='.';//标记该点被访问过 
            dfs(dx,dy);
        }
	}
	for(int i=0;i<8;i++){
        int dx1=x+net[i][0];
        int dy1=y+net[i][1];/*下一个位置的坐标*/
        if(check_c(dx1,dy1)){/*判断是否形成闭环的函数*/
            ans++;
            return ;
        }
	}
	return ;
}
int main(){
	cin>>m>>n;/*m行  n列*/
	memset(vis,0,sizeof(vis));
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			cin>>ptr[i][j];
		}/*图的数量输入完毕,下面开始DFS操作*/
	}
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			if(ptr[i][j]=='#'){//可以作为起点
                vis[i][j]=1;/*标记已经被访问*/
                ptr[i][j]='K';/*标记,这是开头,也就是起始点*/
				dfs(i,j);//传进去开始的起点
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

H. Zebras and Ocelots

解题方法:快速幂,找规律
#include<iostream>
#include<math.h>
#include<string.h>
using namespace std;
#define ll long long
ll quick_pow(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res*=a;
        a=a*a;
        b=b>>1;
    }
    return res;
}
int main(){
	ll n;/*动物的数量*/
	char t;  
	cin>>n;
	ll ans=0;
	string ptr;
	for(ll i=1;i<=n;i++){
		cin>>t;
		ptr=ptr+t;
	}
	string arr(ptr.rbegin(),ptr.rend());
	for(ll i=0;i<arr.length();i++){
		if(arr[i]=='O'){
			ans=ans+quick_pow(2,i);
		}
	}
	cout<<ans<<endl;
	return 0;
}

I. Racing Around the Alphabet

https://nanti.jisuanke.com/t/43376
解题方法:简单模拟这个过程,每次取最短路径,注意pi的取值
#include<iostream>
using namespace std;
const double pi = 3.1415926535;
int main(){
	int n;
	cin>>n;
	getchar();
	while(n--){
		int ans=0;
		string s;
		getline(cin,s);
		for(int i=1;i<s.length();i++){
			int a=s[i-1]-'A'+1;
			int b=s[i]-'A'+1;
			if(s[i-1]==' '){
				a=27;
			}else if(s[i-1]=='\''){
				a=28;
			}
			if(s[i]==' '){
				b=27;
			}else if(s[i]=='\''){
				b=28;
			} 
			if(b<a){
				int z=b;
				b=a;
				a=z;
			}
			int x1 = b-a;
            int x2 = 28-(b-a);
            ans+=min(x1,x2);
		}
		double zc = pi*60;
        double jd = 1.0*zc/28*ans;
        double sum = 1.0*jd/15+s.length();
        printf("%.10f\n",sum);
	}
	return 0;
}

J. Lost Map

https://nanti.jisuanke.com/t/43380
解题方法:这一题主要考察最短路径的求法,只要你会这两个算法,并且还会熟练使用它,就不难
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
ll n;//村庄的数目
const ll max_n=3e10+10;
struct node{
	int from,to;
	ll cose;/*表示的是花费*/
}E[3000*3000];
int t; 
//并查集的标准模板
int father[2525];//定义父节点
void uint(){//数组的初始化 
	for(int i=1;i<2525;i++){
		father[i]=i;//认自己做父节点 
	}
} 
int find_f(int x){//寻找父节点 
	if(x==father[x]){
		return x;//返回父节点 
	}
	return father[x]=find_f(father[x]);
}
void merge(int x,int y){
	int p=find_f(x);
	int q=find_f(y);
	if(p!=q){
		father[p]=q;//点  p  以点   q 做父节点 
	}
}
bool same(int x,int y){
	return find_f(x)==find_f(y);//判断两者是否属于同一节点 
}

bool cmp(node a,node b){
	return a.cose<b.cose;//按花费的多少来排序 
}
void Kluskal(){//实现克鲁斯卡尔算法 
	sort(E,E+t,cmp);
	int num=0; 
	for(int i=0;i<t;i++){
		if(same(E[i].from,E[i].to)){//如果这两者是互联互通的 
//			cout<<E[i].from<<" "<<E[i].to<<endl;
		}else{//两者不是互通的 
			merge(E[i].from,E[i].to);
			cout<<E[i].from<<" "<<E[i].to<<endl;
			num++;
			if(num==n-1){
				break;
			}
		}
	} 
}
int main(){
	cin>>n;
	ll temp;
	t=0;
	uint();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			//下面的每个数输入的都是第  i  个城市与  第  j  个城市连接的代价 
			cin>>temp;
			if(temp!=0){//如果他不是等于0 
				E[t].from=i;
				E[t].to=j;
				E[t++].cose=temp;//存储花费 
			}
		}
	}
	Kluskal(); 
	return 0;
} 






全部评论

相关推荐

不愿透露姓名的神秘牛友
07-16 18:05
何尝不是一种学历歧视呢
码农索隆:楼主明确拒绝,并说明拒绝原因了,这hr倒是挺忠心护主的
点赞 评论 收藏
分享
代码飞升:别用口语,后端就写后端,前端就写前端,最后别光后悔
点赞 评论 收藏
分享
避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-18 18:23
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务