ICPC North Central NA Contest 2017
C. Urban Design
解题方法：这一题其实也不难，只要你画几个例子就很容易找到规律，但要注意的是我们用直线的一般式来判断两条直线是否相交，因为如果直接比较两条直线的斜率，会存在斜率求不出来的情况，这样比较复杂
#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;
} 
