紀中 Day15&Day16
T1：
暴力解決
T2：
純粹蒙分
跟正解有些偏差
T3：
經ZZL大佬指點
快排+二分
T4：
不知什麼東東
T1
找路
題目：
M i r k o Mirko Mirko 剛開始學車，是以他還不會在一個很狹窄的地方掉頭，是以他想找一個不需要掉頭的地方學車。 M i r k o Mirko Mirko馬上發現他想找的地方必須沒有死胡同，因為死胡同是不可能出來的，除非掉頭（假設 M i r k o Mirko Mirko也不會倒車）。現在，你需要寫一個程式，來分析一個地方的地圖，研究是否這個地方适合 M i r k o Mirko Mirko練習開車。
這張地圖是包含 R R R* C C C個單元格的，單元格中的“X”代表一個建築物，單元格中的“.”代表路面。從一個路面單元格， M i r k o Mirko Mirko可以向旁邊上下左右四個方向的單元格開去，隻要開過去的地方同樣也是路面。
最後，我們要得出這個地圖是否包含死胡同，假如從任意一個路面單元格出發，沿着任何一個可以行駛的方向，我們可以不用掉頭就能傳回到出發點，那麼這個地圖就是沒有死胡同的。
輸入：
第一行包括兩個整數 R R R和 C C C（3<= R R R, C C C<=10),表示這個地圖的大小。
接下來 R R R行，每行有 C C C個字元，每個字元可能是“X”和“.”。地圖中至少有兩個路面單元格，并且所有的路面都是相連的（互相可達的）。
輸出：
輸出隻有一行，輸出0表示這個地圖沒有死胡同，輸出1表示這個地圖存在死胡同。
樣例：
解題思路：
暴力判斷每一個路面是否有2個方向可走
代碼：
#include<iostream>
#include<cstdio>
using namespace std;
int fx[5]={0,1,0,-1,0},fy[5]={0,0,1,0,-1};
int n,m,a[20][20];
char c;
int main()
{
freopen("okret.in","r",stdin);
freopen("okret.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
cin>>c;
if (c=='X')
a[i][j]=1;
else a[i][j]=0;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (a[i][j]==0)
{
int ans=0;
for (int k=1;k<=4;k++)
if (a[i+fx[k]][j+fy[k]]==0&&i+fx[k]<=n&&i+fx[k]>0&&j+fy[k]>0&&j+fy[k]<=m) //可走
ans++;
if (ans<2) //死胡同
{
cout<<1<<endl;
return 0;
}
}
cout<<0<<endl;
fclose(stdin);
fclose(stdout);
return 0;
}
T2
家庭作業
題目：
M i r k o Mirko Mirko最近收到了一個家庭作業，作業的任務是計算兩個數A和B的最大公約數。由于這兩個數太大了，我們給出了 N N N個數，他們的乘積是 A A A，給出 M M M個數，他們的乘積是 B B B。
M i r k o Mirko Mirko想要驗算自己的答案，是以他想找你寫一個程式來解決這個問題。如果這個最大公約數超過了9位數，那麼隻需要輸出最後9位就可以了。
輸入：
第一行包含一個正整數 N N N，範圍是1到1000。第二行是 N N N個用空格隔開的正整數(小于10億），他們的乘積是 A A A。第三行包含一個正整數 M M M，範圍是1到1000。第四行是 M M M個用空格隔開的正整數（小于10億），他們的乘積是 B B B。
輸出：
輸出有且隻有一行，表示 A A A和 B B B的最大公約數，如果結果超過了9位數，輸出最後9位數就可以了。
樣例：
解題思路：
先輸入 N N N個數
再輸入 k k k
然後跟 N N N個數找最大公約數
答案相乘
k k k和這個數都除于他們都最大公約數
代碼：
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long n,m,c,t,a[1200],b[10];
long long ans=1;
bool p=false;
int gy(int x,int y)
{
int r=1;
while (r!=0)
{
r=x%y;
x=y;
y=r;
}
return x;
}
int main()
{
freopen("zadaca.in","r",stdin);
freopen("zadaca.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
scanf("%d",&c);
long long x;
for (int j=1;j<=n;j++)
{
x=gy(c,a[j]);
if (ans*x>10000000000) //相乘時超過9位，标記
p=true;
ans=ans*x%10000000000; //相乘
c=c/x;
a[j]=a[j]/x; //相除
}
}
while (ans>0)
{
b[++t]=ans%10;
ans=ans/10;
} //倒序存儲
if (p)
for (int i=9;i>0;i--) //超過9位，會有前導0的可能
cout<<b[i];
else for (int i=t;i>0;i--) //沒有超過，直接輸出
cout<<b[i];
fclose(stdin);
fclose(stdout);
return 0;
}
T3
算法學習
題目：
自從學習了動态規劃後， F a m e r Famer Famer K X P KXP KXP對動态規劃的熱愛便一發不可收拾，每天都想找點題做，一天，他找到了一道題，但是不會做，于是，他找到了你。題目如下：
給出 N N N個無序不重複的數，再有 M M M個詢問，每次詢問一個數是否在那 N N N個數中，若在，則 a n s ans ans增加2^ K K K, K K K為該數在原數列中的位置。
由于 a n s ans ans過大，是以隻要求你輸出 a n s ans ans m o d mod mod 10^9+7。
輸入：
第一行，兩個數 N N N, M M M，第二行 N N N個數，第三行 M M M個數。
輸出：
輸出最終答案。
樣例：
input
5 5
1 3 4 6 5
1 8 1 3 6
output
24
資料範圍限制：
30% 0<N,M<100
50% 0<N,M<10000
100% 0<N,M<100000
輸入的數均在2^31 以内
解題思路：
快排+二分
代碼：
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
const int mo=1000000007;
int n,m,x,b[100010];
long long ans;
struct hhx{
int x,s;
}a[100010];
bool cmp(hhx t,hhx x)
{
return (t.s<x.s);
}
void jc()
{
b[1]=2;
for (int i=2;i<=n;i++)
b[i]=b[i-1]*2%mo;
}
int main()
{
freopen("sfxx.in","r",stdin);
freopen("sfxx.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i].s);
a[i].x=i;
}
sort(a+1,a+n+1,cmp); //快排
jc(); //提前做2的n次方的積
for (int i=1;i<=m;i++)
{
scanf("%d",&x);
int l=1,r=n;
while (l<=r) //二分在數組裡找x
{
int mid=(l+r)/2;
if (a[mid].s==x) //找到
{
ans=(ans+b[a[mid].x])%mo;
break;
}
if (a[mid].s>x) //繼續找
r=mid-1;
else l=mid+1;
}
}
cout<<ans<<endl;
fclose(stdin);
fclose(stdout);
return 0;
}
T4
友好數對
題目：
在順利完成家庭作業以後， M i r k o Mirko Mirko感到非常的厭倦。是以，他列出了 N N N個數，這些數中有些數對他是喜歡的，有些數對他是不喜歡的。
他喜歡的數對叫做友好數對，如果兩個數至少有一個相同的數字(不要求在相同的位置），那麼這兩個數就是友好數對。請幫助 M i r k o Mirko Mirko在這 N N N個數找出有多少友好數對。
輸入：
第一行一個正整數 N N N（1<= N N N<=1000000）。
接下來 N N N行，每行一個正整數,範圍在1到1018之間。 N N N個數中任意兩個數都是不同的。
輸出：
隻有一行一個整數，表示友好數對的個數。
樣例：
解題思路：
利用二進制存儲
再轉為十進制， f f f[ y y y]++
進行&位運算
如果結果不為0
說明有相同的位
a n s ans ans= a n s ans ans+ f f f[ i i i] * f f f[ j j j];
最後 a n s ans ans= a n s ans ans+ f f f[ i i i] * ( f f f[ i i i]-1)
因為不一樣的數有相同的數，可能轉成同一個二進制
自己也要乘自己
代碼：
#include<iostream>
#include<cstdio>
using namespace std;
long long n,x,ans,c;
long f[1200];
int main()
{
freopen("kompici.in","r",stdin);
freopen("kompici.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%lld",&x);
int y=0,c=0;
while (x>0)
{
c=x%10;
x=x/10;
y=y|(1<<c); //利用二進制存儲，<<左移
}
f[y]++; //标記
}
for (int i=1;i<=1023;i++)
{
if (f[i]==0) continue; //沒有數，就不用做
for (int j=1;j<=1023;j++)
{
if ((i&j)&&(i!=j)) //不相等且i和j有相同的位
ans=ans+f[i]*f[j];
}
ans=ans+f[i]*(f[i]-1);
}
printf("%lld\n",ans/2);
fclose(stdin);
fclose(stdout);
return 0;
}