2014北郵網研機試験
5680 ワード
注意:すべてのコードはテーマの説明に基づいてローカルテストを行い、北郵ojでテストしていないので、ACが必ずできるとは保証されません.
リンクをクリックして、過去の試験問題の要約を表示します.
2^(-a)+2^(-b)を求めて、そのうちaとbはすべて正の整数で、結果は最も簡単な点数で表してください.フォーマット第1動作試験データのセット数T(1<=T<=400)を入力する.いずれかの2つのテストデータのセットは互いに独立していることに注意してください.各テストデータのセットは、2つの整数aおよびb(2<=a、b<=20)を含む1行である.出力フォーマットは、各テストデータのセットについて、結果を1行に出力し、分子と分母を「/」で区切ります.
2 2 4 3 2
5/16 3/8
2^a 2^bは必ず互いに除去することができて、2つの数が等しい時だけ約分(2で割る)を必要として、2つの数が等しくない時商は必ず偶数で、それでは分子はきっと奇数で、約分できません.
権限付き二叉木を1本与えて、最小の山かどうかを判断してください.1本のツリーは最小スタックであり、ツリー上の任意のノードに対してのみ、その重み値がルートのサブツリーの所有権値以下または等しい場合.入力フォーマット入力データの最初の行は、テストデータのグループ数を表す整数T(1<=T<=100)である.各テストデータのセットについて、最初の行は整数N(1<=N<=100)であり、ツリーのノード数を表す.次の行にはN個の正の整数が含まれ、i番目の整数valuei(1<=valuei<=1000)は番号iの点の重み値を表す.次のN−1行は、各行の2つの整数uおよびv(1<=u,v<=N,u!=v)であり、ノードuがノードvの親ノードであることを示す.テストデータは、所与のツリーが必ず1本であり、ノード1がツリーのルートノードであることを保証する.出力フォーマットは、各テストデータのセットについて、与えられたツリーが最小スタックである場合はYesを出力し、そうでない場合はNoを出力する.
3 1 10 3 10 5 3 1 2 1 3 5 1 2 3 4 5 1 3 1 2 2 4 2 5
Yes No Yes
最小ヒープの判断:各ノードの値がサブノードの値以下です.
オペレーティングシステムでは、プロセス管理は非常に重要な作業であり、各プロセスには一意のプロセスID(PID)があります.各プロセスはサブプロセスを開始できます.このとき、PIDが0のプロセスを除いて、各プロセスには親プロセスが1つしかありません.このタスクでは、オペレーティングシステムの実行中の3つの基本的な操作をリアルタイムで維持する必要があります.1.FORK PID 1 PID 2:PID 1と識別されるプロセスは、PID 2と識別されるサブプロセスを開始する.2.KILL PID:PIDとして識別されたプロセスを終了します.同時にすべてのPIDのサブプロセスも同時に終了することに注意してください.PIDが存在しないか終了したプロセスの場合は、何もしません.3.QUERY PID:クエリがPIDとして識別するプロセスがまだ存在するかどうか.初期状態では、PIDが0のプロセスのみが開始され、いずれの場合もプロセスは終了しません.入力フォーマット入力の最初の行は、入力されたデータ群数を示す整数T(T<=50)である.各試験データの最初の行は、動作の数を表す整数N(1<=N<=100)である.N行が下りていない場合、各行は上記の説明に従って各操作を与え、入力はすべてのプロセスのPIDが異なり、1つのプロセスが終了した後に再起動されないことを保証し、すべてのPIDは[1100]間の整数である.
5 FORK 0 1 QUERY 1 KILL 1 QUERY 1 QUERY 2
Yes No No
シミュレーション.
ネットワークの効率的な相互接続とインテリジェントな伝送は、大量のユーザーサービス要求のマッピング効率を向上させる重要な措置である.このタスクでは、特定のデータ・ソースを指定したネットワーク・ノードに送信するために、最小限の転送時間を使用します.私が与えたネットワークには、ノード1がデータソースであるN個のノード(1からN番号まで)が含まれています.ネットワークにはM本の無方向エッジ(u,v,w)があり、1本の伝送路接続ノードuとノードvを表し、データがこの伝送路を通過する平均時間はwである.転送メカニズムの制限により、1つのノードがデータを受信すると、相互接続された1つのノードしか選択できず、データをノードに転送することができます.ノード1は、初期化時に1回しかデータを送信しないが、転送中に転送ノードとして使用することができる.ネットワークにはk個のターゲットノードがあり、ノード1からすべてのK歌ノードにデータを転送するのに要する最短時間を計算する必要があります.注意ターゲットノードは任意の順序で転送することができ、データは同じノードを複数回通過することもできる.入力フォーマット入力データの最初の行は整数T(T<=5)であり、テストデータのグループ数を表す.各試験データのセットについて、1行目は、ノード数、エッジ数、およびターゲットノード数をそれぞれ表す3つの正の整数N,M,K(2<=N<=1000、1<=M<=N(N−1)/2、K<=10)である.次にM行は、1行あたり3つの整数u,v,w(1<=u,v<=N,0<=w<=1000,u!=v)である.上述したように、各伝送路が与えられる.2つのネットワークノードの間には、最大1つのエッジしか接続されていません.最後の行はK個の整数であり、すべてのターゲットノードの番号が与えられ、すべてのターゲットノードの番号は2からNの間にある.出力フォーマットは、各テストデータのセットについて、すべてのK個のターゲットノードに送信される最短時間である.
2 3 2 2 1 3 1 1 2 3 2 3 6 6 4 1 5 1 5 6 2 2 1 20 2 3 5 3 4 5 6 3 1 2 3 4 6
5 19
説明:第1のサンプル群において、最短ルートは、1−>3−>1−>2の第2のサンプル群において、最短ルートは、1−>5−>6−>3−>2−>3−>4、または1−>5−>6−>3−>4−>2である
この問題は全配列で、next_permutation(a,a+n)
リンクをクリックして、過去の試験問題の要約を表示します.
A分数加算
タイトルの説明
2^(-a)+2^(-b)を求めて、そのうちaとbはすべて正の整数で、結果は最も簡単な点数で表してください.フォーマット第1動作試験データのセット数T(1<=T<=400)を入力する.いずれかの2つのテストデータのセットは互いに独立していることに注意してください.各テストデータのセットは、2つの整数aおよびb(2<=a、b<=20)を含む1行である.出力フォーマットは、各テストデータのセットについて、結果を1行に出力し、分子と分母を「/」で区切ります.
サンプル入力
2 2 4 3 2
サンプル出力
5/16 3/8
解析
2^a 2^bは必ず互いに除去することができて、2つの数が等しい時だけ約分(2で割る)を必要として、2つの数が等しくない時商は必ず偶数で、それでは分子はきっと奇数で、約分できません.
#include
using namespace std;
int ans1,ans2;
int main()
{
int n,a,b;
cin>>n;
while(n--)
{
ans1=1;
ans2=1;
cin>>a>>b;
while(a--) ans1*=2;
while(b--) ans2*=2;
if(ans1==ans2) cout< B行列連乗
タイトルの説明
権限付き二叉木を1本与えて、最小の山かどうかを判断してください.1本のツリーは最小スタックであり、ツリー上の任意のノードに対してのみ、その重み値がルートのサブツリーの所有権値以下または等しい場合.入力フォーマット入力データの最初の行は、テストデータのグループ数を表す整数T(1<=T<=100)である.各テストデータのセットについて、最初の行は整数N(1<=N<=100)であり、ツリーのノード数を表す.次の行にはN個の正の整数が含まれ、i番目の整数valuei(1<=valuei<=1000)は番号iの点の重み値を表す.次のN−1行は、各行の2つの整数uおよびv(1<=u,v<=N,u!=v)であり、ノードuがノードvの親ノードであることを示す.テストデータは、所与のツリーが必ず1本であり、ノード1がツリーのルートノードであることを保証する.出力フォーマットは、各テストデータのセットについて、与えられたツリーが最小スタックである場合はYesを出力し、そうでない場合はNoを出力する.
サンプル入力
3 1 10 3 10 5 3 1 2 1 3 5 1 2 3 4 5 1 3 1 2 2 4 2 5
サンプル出力
Yes No Yes
解析
最小ヒープの判断:各ノードの値がサブノードの値以下です.
#include
#include
using namespace std;
struct TreeNode
{
int val;
TreeNode* left;
TreeNode* right;
/*
TreeNode(int x): val(x),left(NULL),right(NULL) {
}
*/
}node[101];
int main()
{
int T;
cin>>T;
while(T--)
{
int N,x,y;
int ok=1;
cin>>N;
int fa[101];
for(int i=1;i<=N;i++) cin>>node[i].val;
for(int i=1;i<=N-1;i++)
{
cin>>x>>y;
if(node[x].val>node[y].val)
{
ok=0;
}
}
if(ok) cout< Cハッシュマッピング
タイトルの説明
オペレーティングシステムでは、プロセス管理は非常に重要な作業であり、各プロセスには一意のプロセスID(PID)があります.各プロセスはサブプロセスを開始できます.このとき、PIDが0のプロセスを除いて、各プロセスには親プロセスが1つしかありません.このタスクでは、オペレーティングシステムの実行中の3つの基本的な操作をリアルタイムで維持する必要があります.1.FORK PID 1 PID 2:PID 1と識別されるプロセスは、PID 2と識別されるサブプロセスを開始する.2.KILL PID:PIDとして識別されたプロセスを終了します.同時にすべてのPIDのサブプロセスも同時に終了することに注意してください.PIDが存在しないか終了したプロセスの場合は、何もしません.3.QUERY PID:クエリがPIDとして識別するプロセスがまだ存在するかどうか.初期状態では、PIDが0のプロセスのみが開始され、いずれの場合もプロセスは終了しません.入力フォーマット入力の最初の行は、入力されたデータ群数を示す整数T(T<=50)である.各試験データの最初の行は、動作の数を表す整数N(1<=N<=100)である.N行が下りていない場合、各行は上記の説明に従って各操作を与え、入力はすべてのプロセスのPIDが異なり、1つのプロセスが終了した後に再起動されないことを保証し、すべてのPIDは[1100]間の整数である.
サンプル入力
5 FORK 0 1 QUERY 1 KILL 1 QUERY 1 QUERY 2
サンプル出力
Yes No No
解析
シミュレーション.
#include
#include
#include
#include
using namespace std;
int fa[101];
void kill(int t)
{
fa[t]=-1;
for(int i=1;i<101;i++)
{
if(fa[i]==t) kill(i);
}
}
int main()
{
int T;
cin>>T;
while(T--)
{
int N,x,y;
fill(fa,fa+101,-1);
cin>>N;
while(N--)
{
string s;
cin>>s;
if(s=="FORK")
{
cin>>x>>y;
fa[y]=x;
}
else if(s=="QUERY")
{
cin>>x;
if(fa[x]!=-1||x==0) cout<>x;
kill(x);
}
}
}
return 0;
} Dネットワーク転送
タイトルの説明
ネットワークの効率的な相互接続とインテリジェントな伝送は、大量のユーザーサービス要求のマッピング効率を向上させる重要な措置である.このタスクでは、特定のデータ・ソースを指定したネットワーク・ノードに送信するために、最小限の転送時間を使用します.私が与えたネットワークには、ノード1がデータソースであるN個のノード(1からN番号まで)が含まれています.ネットワークにはM本の無方向エッジ(u,v,w)があり、1本の伝送路接続ノードuとノードvを表し、データがこの伝送路を通過する平均時間はwである.転送メカニズムの制限により、1つのノードがデータを受信すると、相互接続された1つのノードしか選択できず、データをノードに転送することができます.ノード1は、初期化時に1回しかデータを送信しないが、転送中に転送ノードとして使用することができる.ネットワークにはk個のターゲットノードがあり、ノード1からすべてのK歌ノードにデータを転送するのに要する最短時間を計算する必要があります.注意ターゲットノードは任意の順序で転送することができ、データは同じノードを複数回通過することもできる.入力フォーマット入力データの最初の行は整数T(T<=5)であり、テストデータのグループ数を表す.各試験データのセットについて、1行目は、ノード数、エッジ数、およびターゲットノード数をそれぞれ表す3つの正の整数N,M,K(2<=N<=1000、1<=M<=N(N−1)/2、K<=10)である.次にM行は、1行あたり3つの整数u,v,w(1<=u,v<=N,0<=w<=1000,u!=v)である.上述したように、各伝送路が与えられる.2つのネットワークノードの間には、最大1つのエッジしか接続されていません.最後の行はK個の整数であり、すべてのターゲットノードの番号が与えられ、すべてのターゲットノードの番号は2からNの間にある.出力フォーマットは、各テストデータのセットについて、すべてのK個のターゲットノードに送信される最短時間である.
サンプル入力
2 3 2 2 1 3 1 1 2 3 2 3 6 6 4 1 5 1 5 6 2 2 1 20 2 3 5 3 4 5 6 3 1 2 3 4 6
サンプル出力
5 19
説明:第1のサンプル群において、最短ルートは、1−>3−>1−>2の第2のサンプル群において、最短ルートは、1−>5−>6−>3−>2−>3−>4、または1−>5−>6−>3−>4−>2である
解析
この問題は全配列で、next_permutation(a,a+n)
#include
#include
#include
#define INF 0x3fffffff
#define MAXV 1005
using namespace std;
int G[MAXV][MAXV],vis[MAXV],d[MAXV],num[MAXV];
int T,n,m,k;
void floyd()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
if(G[i][k]!=INF&&G[k][j]!=INF&&G[i][k]+G[k][j]>T;
while(T--)
{
fill(G[0],G[0]+MAXV*MAXV,INF);
fill(vis,vis+MAXV,0);
fill(d,d+MAXV,INF);
cin>>n>>m>>k;
for(int i=1;i<=n;i++) G[i][i]=0;
int u,v,w;
for(int i=0;i>u>>v>>w;
if(w>num[i];
floyd();
int min=INF,sum=0,pre;
do
{
sum=0;
pre=1;
for(int i=0;i