牛客小白月試合10 A,B,C,D
5323 ワード
トランスファゲート
リンク:https://ac.nowcoder.com/acm/contest/280/A出典:牛客網
タイトルはActciが偶然1つの鉱洞を発見したことを説明して、この鉱洞の構造は1本の二叉木に似ていて、Actciが発見した鉱洞はちょうど根のノードのところに位置して、できるだけ早く掘り起こすため、Actciは彼女の小さい仲間たちを探して助けに来て、地質の原因のため、毎日小さい仲間たちは1本の子ノードまでの道(時間を消費しません)を打つしかありません.つまり、毎日1つのノードが1つのサブノードにしか道路を建設できないということです.1つの道路を歩くには1日かかります.1つの道路を発見すると、一部のパートナーが残って探査を続けることを選択します.リンク:https://ac.nowcoder.com/acm/contest/280/A出典:牛客網
説明を入力:1行、1数n.出力説明:1行、1つの数は最大建設の道路数を表し、答えは100000007に対して型を取ります.例1入力
しゅつりょく
説明
例2入力
しゅつりょく
コメント:
法則を探る.
リンク:https://ac.nowcoder.com/acm/contest/280/B出典:牛客網
説明を入力:1行、1数a.出力説明:2行.最初の行はYesまたはNoを出力し、この数がこの4つの数のうちの1つまたは複数の数の倍数であるかどうかを示します.2行目、aはどの数の倍数であり、各数はスペースで区切られ(順序は小さいから大きい)、第1の動作Noであれば出力されない.例1入力
しゅつりょく
例2入力
しゅつりょく
例3入力
しゅつりょく
文字列シミュレーション大数演算{{もじれつ:アナログだいすうえんざん}}
リンク:https://ac.nowcoder.com/acm/contest/280/C出典:牛客網
题目描述Actci授业で一眠りして、授业が终わって数学の先生を探して补习して、先生に1つの题目を闻きました:2つの数a,bを与えて、aとbのすべての公约数は何ですか?数学の先生はこの問題を見ると簡単すぎて、答えたくないので、あなたに渡しました.入力記述:1行2個の数a,b.出力記述:aとbのすべての公約数、各数字の間にスペースが隔てられている.例1入力
しゅつりょく
例2入力
しゅつりょく
コメント:
2つの数の積は、この2つの数の最大公約数と最小公倍数の積に等しい.
2つの数がaおよびbであり、彼らの最大公約数がa/cであると仮定すると、彼らの最小公倍数は(a/c)a/(a/c)*b/(a/c)である.化簡後得:b!c従って最大公約数に最小公倍数=(a/c)*(bc)=a*bを乗じる
2つの数の最大公因数は必ずこの2つの数の因数であり、2つの数の最小公倍数は必ずこの2つの数の倍数であるため、2つの数の最小公倍数は必ずそれらの最大公因数の倍数である.
では、2つの数の公因数は必ず2つの数の因数であり、2つの数の最小公倍数は必ずこの2つの数の倍数である.だから2つの数の最小公倍数は彼らの因数の倍数に違いない.
リンク:https://ac.nowcoder.com/acm/contest/280/D出典:牛客網
テーマは夕日が西に沈んで、慌ただしく忙しくて、SSJの一日の课程はすでにすべて终わって、腹がグーグーと叫び始めて、家に帰るバスに乗って、しかしSSJは今日少し迷っているようで、今日昼ごはんの时に食堂に行かなかったと言って、歩いていて、外の景色は美しいですね、ああ?私はここを通ったことがないようです.終わったので、道に迷いたいです.バスは終点に着いて、SSJは降りて、内心はこの上なく緊張して、帰れなくて、ひとしきりの冷たい風が吹いて、瑟瑟は震えて、emm...、あれは1枚の地図ですか?地図の上で何がみんなはすべて知っていて、SSJは今すでに腹が減って考える力がなくて、彼に最も速く家に帰る道を設計してもらって、彼は早く家に帰ってxxxを食べます.説明を入力:最初の行の4つの数n,m,s,t.(地図上のn地点,m道路,SSJはs地点,他家はt地点)第2−m+1の3つの正の整数,f,u(ある道の起点),v(到達点),w(経路距離)をそれぞれ示す.(fは1または0,0はこの道に悪犬が道を塞いでいることを示し、SSJは悪犬と戦う力がないので、彼はこれらの道を避けなければならない.1はこの道に危険がないことを示している).出力説明:最初の行の1つの数は最短の経路の長さを表して、もし家に帰ることができないならば“My gold!!”を出力します(引用符なし)家に帰れるなら.例1入力
しゅつりょく
コメント:
優先キュー最適化dijkstraテンプレート
リンク:https://ac.nowcoder.com/acm/contest/280/A出典:牛客網
タイトルはActciが偶然1つの鉱洞を発見したことを説明して、この鉱洞の構造は1本の二叉木に似ていて、Actciが発見した鉱洞はちょうど根のノードのところに位置して、できるだけ早く掘り起こすため、Actciは彼女の小さい仲間たちを探して助けに来て、地質の原因のため、毎日小さい仲間たちは1本の子ノードまでの道(時間を消費しません)を打つしかありません.つまり、毎日1つのノードが1つのサブノードにしか道路を建設できないということです.1つの道路を歩くには1日かかります.1つの道路を発見すると、一部のパートナーが残って探査を続けることを選択します.リンク:https://ac.nowcoder.com/acm/contest/280/A出典:牛客網
説明を入力:1行、1数n.出力説明:1行、1つの数は最大建設の道路数を表し、答えは100000007に対して型を取ります.例1入力
2
しゅつりょく
3
説明
：
n n×2 n×2+1， 1.
1->2, 1，2 ， 1。
1->3,2->4, 2,3,4 ， 3.
例2入力
100
しゅつりょく
6531708670
コメント:
：
100% n ≤ 5×106
法則を探る.
#include
using namespace std;
typedef long long ll;
const ll mod=10000000007;
ll n,s1,s2,t;
ll f[10000010],ans;
int main() {
cin>>n;
f[1]=1;f[2]=2;
for(int i=3;i<=n;i++) f[i]=(f[i-1]+f[i-2])%mod;
for(int i=1;i<=n;i++) ans=(ans+f[i])%mod;
cout< リンク:https://ac.nowcoder.com/acm/contest/280/B出典:牛客網
説明を入力:1行、1数a.出力説明:2行.最初の行はYesまたはNoを出力し、この数がこの4つの数のうちの1つまたは複数の数の倍数であるかどうかを示します.2行目、aはどの数の倍数であり、各数はスペースで区切られ(順序は小さいから大きい)、第1の動作Noであれば出力されない.例1入力
123456789
しゅつりょく
Yes
3
例2入力
2341232402462055420
しゅつりょく
Yes
3 5
例3入力
9741427
しゅつりょく
No
文字列シミュレーション大数演算{{もじれつ:アナログだいすうえんざん}}
#include
using namespace std;
typedef long long LL;
const int maxn = 1e4 + 10;
const LL inf = 0x3f3f3f3f;
char s[maxn];
int a[11];
bool isok(int k){
int tem = 0;
for (int i=0; s[i]!='\0'; i++) tem = (tem * 10 + (s[i] - '0')) % k;
if (tem == 0) return true;
else return false;
}
int main(){
scanf("%s", s);
int k = 0;
for (int i=1; i<=4; i++){
int x;
if (i == 1) x = 3;
else if (i == 2) x = 5;
else if (i == 3) x = 8;
else if (i == 4) x = 11;
if (isok(x)) a[++k] = x;
}
if (k == 0) puts("No");
else {
puts("Yes");
for (int i=1; i リンク:https://ac.nowcoder.com/acm/contest/280/C出典:牛客網
题目描述Actci授业で一眠りして、授业が终わって数学の先生を探して补习して、先生に1つの题目を闻きました:2つの数a,bを与えて、aとbのすべての公约数は何ですか?数学の先生はこの問題を見ると簡単すぎて、答えたくないので、あなたに渡しました.入力記述:1行2個の数a,b.出力記述:aとbのすべての公約数、各数字の間にスペースが隔てられている.例1入力
25 37
しゅつりょく
1
例2入力
25 100
しゅつりょく
1 5 25
コメント:
100% ，1 ≤ a,b ≤ 1013
2つの数の積は、この2つの数の最大公約数と最小公倍数の積に等しい.
2つの数がaおよびbであり、彼らの最大公約数がa/cであると仮定すると、彼らの最小公倍数は(a/c)a/(a/c)*b/(a/c)である.化簡後得:b!c従って最大公約数に最小公倍数=(a/c)*(bc)=a*bを乗じる
2つの数の最大公因数は必ずこの2つの数の因数であり、2つの数の最小公倍数は必ずこの2つの数の倍数であるため、2つの数の最小公倍数は必ずそれらの最大公因数の倍数である.
では、2つの数の公因数は必ず2つの数の因数であり、2つの数の最小公倍数は必ずこの2つの数の倍数である.だから2つの数の最小公倍数は彼らの因数の倍数に違いない.
#include
using namespace std;
typedef long long ll;
const int maxn = 1e6+7;
ll gcd(ll a,ll b)
{
if(b==0) return a;
return gcd(b,a%b);
}
set ans;
ll a,b;
int main()
{
cin>>a>>b;
ll g = gcd(a,b);
for(ll i=1;i*i<=g;i++)
{
if(g%i==0)
{
ans.insert(i);
ans.insert(g/i);
}
}
for(auto it = ans.begin();it!=ans.end();++it)
{
cout< リンク:https://ac.nowcoder.com/acm/contest/280/D出典:牛客網
テーマは夕日が西に沈んで、慌ただしく忙しくて、SSJの一日の课程はすでにすべて终わって、腹がグーグーと叫び始めて、家に帰るバスに乗って、しかしSSJは今日少し迷っているようで、今日昼ごはんの时に食堂に行かなかったと言って、歩いていて、外の景色は美しいですね、ああ?私はここを通ったことがないようです.終わったので、道に迷いたいです.バスは終点に着いて、SSJは降りて、内心はこの上なく緊張して、帰れなくて、ひとしきりの冷たい風が吹いて、瑟瑟は震えて、emm...、あれは1枚の地図ですか?地図の上で何がみんなはすべて知っていて、SSJは今すでに腹が減って考える力がなくて、彼に最も速く家に帰る道を設計してもらって、彼は早く家に帰ってxxxを食べます.説明を入力:最初の行の4つの数n,m,s,t.(地図上のn地点,m道路,SSJはs地点,他家はt地点)第2−m+1の3つの正の整数,f,u(ある道の起点),v(到達点),w(経路距離)をそれぞれ示す.(fは1または0,0はこの道に悪犬が道を塞いでいることを示し、SSJは悪犬と戦う力がないので、彼はこれらの道を避けなければならない.1はこの道に危険がないことを示している).出力説明:最初の行の1つの数は最短の経路の長さを表して、もし家に帰ることができないならば“My gold!!”を出力します(引用符なし)家に帰れるなら.例1入力
5 7 1 5
0 1 4 4
1 1 3 2
1 1 5 7
1 2 5 10
0 2 3 1
1 3 5 2
1 4 3 7
しゅつりょく
4
コメント:
n≤10000,m≤200000,w≤5000000
優先キュー最適化dijkstraテンプレート
#include
using namespace std;
typedef long long LL;
const LL inf=1e18+5;
const int maxn=10005;
int n,m,s,t,f,u,v,x,y,z;
vector v1[maxn];
vector v2[maxn];
bool vis[maxn];LL w,dis[maxn];
priority_queue< pair > que;
void Dijkstra(){
while(!que.empty())que.pop();
memset(vis,false,sizeof(vis));
dis[s]=0;que.push(make_pair(-dis[s],s));
while(!que.empty()){
x=que.top().second;que.pop();
if(vis[x])continue;
vis[x]=true;
for(size_t j=0;j