西南合同訓練5[Source from NK]問題解&まとめ
6240 ワード
Problem 1
数正方形(count.cpp/c/pas)
タイトルの説明
n*nのドットマトリクスの中で4つのドットを取って、質問1:この4つのドットがちょうど「正放」の正方形の4つの頂点のシナリオ数はいくらですか?質問2:この4つの点がちょうど正方形(正と斜めを含む)の4つの頂点のシナリオ数はいくらですか?下図は4*4のドットマトリクスで、左図は「正放」のシナリオを示し、右図は「斜め放」のシナリオを示しています.
入力フォーマット
2つの整数nとk,nはドットマトリクスのサイズを表し,k=1は質問に答える必要がある1,k=2は質問に答える必要がある2を表す.
出力フォーマット
答えを表す整数.(模1000000007再出力)
入力サンプル
入力サンプル1:4 1
入力サンプル2:4 2
出力サンプル
出力サンプル1:14
出力サンプル2:20
データ範囲
10%のデータに対して、n=5はk=1とk=2がそれぞれ半分を占めて30%のデータに対して、1<=n<=50はk=1とk=2がそれぞれ半分を占めて100%のデータに対して、1<=n<=100000はk=1とk=2がそれぞれ半分を占めている
サンプルの説明
なし
この問題は実は何も言うことがなくて、1つの法則を探すだけで、唯一注意しなければならないところは型を取る順序で、この地方はもっといくつかの大きい例を試すだけで問題を発見することができます
期待得点:100、実績得点:100
Problem 2
取数(choose.cpp/c/pas)
タイトルの説明
n個の整数からなるリングで、今からm個の数を取り出すと、1つの数字を取ると隣接する数字を取ることができません(隣接する数は同時に取ることができません).取り出した数字の総和をできるだけ大きくすることを要求して、この最大和はいくらですか?解かない場合は「Error!」を出力してください.
入力フォーマット
最初の行には、2つの正の整数n、mが含まれます.第2の動作n個の整数Ai.
出力フォーマット
求めた結果を表す整数は1つだけです.「Error!」を出力しないと、引用符は含まれません.
入力サンプル
入力サンプル1
入力サンプル2
サンプル入力3
7 3 1 2 3 4 5 6 7
7 4 1 2 3 4 5 6 7
8 4 8 5 6 2 3 4 8 9
出力サンプル
出力サンプル1
出力サンプル2
サンプル出力3
15
Error!
25
データ範囲
すべてのデータについて:m<=n;-1000<=Ai<=1000
データ番号
Nの大きさ
データ番号
Nの大きさ
1
40
11
2013
2
45
12
5000
3
50
13
10000
4
55
14
49999
5
200
15
111111
6
200
16
148888
7
1000
17
188888
8
2010
18
199999
9
2011
19
199999
10
2012
20
200000
サンプルの説明
なし
この問題は少し難易度があって、当初試験の時ただ暴力のdpだけを思い付いて、もとは55点の差が多くなくて、更に最適化して60点を過ぎることができて、しかし配列は1000*1000に開いて、直接8,9,10,11組のもとの本能の過ぎたデータを掛けました
正解:まず、各数字とその番号をスタックに入れます.大根を築く.各数の左右の要素の番号を記録します.L[k],R[k]. 最後に出力する答えはansです.0に初期化します.そして毎回スタックからスタックトップ要素、ans+というスタック要素の値を取り出します.現在取り出したスタックトップ要素の番号をkとします.ここで,P[i]=P[L[k]+P[R[k]−P[k]の数を新たに生成する.番号iの数左の数の番号をL[L[k]]とする.右側の数はR[R[k]]として与えられる.そしてR[R[k]]の左側はiである.L［L［k］の右側はiである.(チェーンテーブルのような操作)
なぜこんなことを?毎回最大の数を選ぶと最適解が得られる保証はないことを知っているからだ.だから私たちは自分に退路を残して、新しく生成した数は、前の選択を取り消して、彼の両側の数(いわゆる悔い改め)を選ぶことです.
期待得点:55、実績得点:20
Problem 3
ワイン取引(wine.cpp/c/pas)
タイトルの説明
ある地域にはNの村が分布しており、番号0からN-1で、村ごとに酒を買うか、酒を売る必要がある.第iの村のワインに対する需要をAiとし、そのうちAi>0は同村が酒を買う必要があることを示し、Ai<0は同村が酒を売る必要があることを示した.すべての村の需給バランス、すなわちすべてのAiの和は0(ΣAi=0)に等しい.しかし、M対村の間だけは貿易往来があり、そのうちi対村の間にはワインがいくら運ばれてもTiの運賃がかかる.最低いくらの運賃が必要か計算してください.すべての村の酒に対する需要を満たすことができます.
入力フォーマット
1行目の2つの整数N、M.2行目N個目の整数Ai.次にM行は行ごとに3つの整数pi,qi,Tiであり,piとqiの番号の村間で酒を運ぶのにTiの費用がかかることを示した.データはpi、qiのペアごとに最大1回発生することを保証します.
出力フォーマット
答えを表す整数を出力します.無出力Impossible
入力サンプル
3 3 50 -20 -30 0 1 10 1 2 20 0 2 100
出力サンプル
30
データ範囲
50%のデータ:2<=N<=8.100%のデータについて:2<=N<=16 0<=M<=N*(N-1)/20<=pi,qi-1000<=Ai<=1000 0<=Ti<=1000
サンプルの説明
なし
この问题のデータは比较的に不思议で、直接最小生成木+解があるかどうかを判断することができますA、解があるかどうかを判断しないで1组を间违えて、最初は明らかに最小生成木の诈欺点を书きたいと思っていました......、それから抜け穴が百出することを発见して放弃して、直接cout“impossible”は10点を得て、とっくに直接最小生成木をすることを知っています
正解:
1.すべての酒量と0の集合を見つける.この集合の点が連通ならば、その集合の最小生成木を求める、生成木の値は、その集合の酒量移動に必要な最小代価である.各酒量総和が0の集合を一つの物と見なし,リュックサックゲージを用いて最適解を求める.
状態をバイナリで圧縮し,1はノードが集合中,0は不在を表す.例えば、デジタルsのバイナリ形式は100111であり、0,1,2,5番ノードがsで表される集合にあることを示す.題目は最大n(n<=16)個のノードがあるので、sの範囲は0から(2^n)-1つまり(1<配列Sum[s]で、集合sに含まれるノードの酒量の和を記録する.酒量毎と0の集合x(Sum[x]=0)について、最小生成木が1本得られると、この生成木の対価f[i]を配列Cost[x]で記録し、平衡集合i中のノードの酒量値を記録し、必要最小対価は集合iおよびjに対してSum[i]=0およびSum[j]=0を満たすとf[i|j]=min(f[i|j],f[i]+Cost[j])となる.i|jは、集合iが集合jとマージされた後の集合所望得点:90、実得点:10を示す
総得点:130、ランキング:18
まとめ:コードの细かい処理はまだ足りない、不注意な欠点はまだ直していない、次の试験の10分前に必ず真剣に自分のコードを検査して、过失性の点数をなくす确率を减らしなければならない
数正方形(count.cpp/c/pas)
タイトルの説明
n*nのドットマトリクスの中で4つのドットを取って、質問1:この4つのドットがちょうど「正放」の正方形の4つの頂点のシナリオ数はいくらですか?質問2:この4つの点がちょうど正方形(正と斜めを含む)の4つの頂点のシナリオ数はいくらですか?下図は4*4のドットマトリクスで、左図は「正放」のシナリオを示し、右図は「斜め放」のシナリオを示しています.
入力フォーマット
2つの整数nとk,nはドットマトリクスのサイズを表し,k=1は質問に答える必要がある1,k=2は質問に答える必要がある2を表す.
出力フォーマット
答えを表す整数.(模1000000007再出力)
入力サンプル
入力サンプル1:4 1
入力サンプル2:4 2
出力サンプル
出力サンプル1:14
出力サンプル2:20
データ範囲
10%のデータに対して、n=5はk=1とk=2がそれぞれ半分を占めて30%のデータに対して、1<=n<=50はk=1とk=2がそれぞれ半分を占めて100%のデータに対して、1<=n<=100000はk=1とk=2がそれぞれ半分を占めている
サンプルの説明
なし
この問題は実は何も言うことがなくて、1つの法則を探すだけで、唯一注意しなければならないところは型を取る順序で、この地方はもっといくつかの大きい例を試すだけで問題を発見することができます
期待得点:100、実績得点:100
#include
#include
#define LL long long
using namespace std;
const LL mod=1000000007;
LL n,k;
int main(){
cin>>n>>k;
LL i,j,sum;
sum=(((n-1)*n)*(2*n-1)/6)%mod;
if(k==1){
cout< Problem 2
取数(choose.cpp/c/pas)
タイトルの説明
n個の整数からなるリングで、今からm個の数を取り出すと、1つの数字を取ると隣接する数字を取ることができません(隣接する数は同時に取ることができません).取り出した数字の総和をできるだけ大きくすることを要求して、この最大和はいくらですか?解かない場合は「Error!」を出力してください.
入力フォーマット
最初の行には、2つの正の整数n、mが含まれます.第2の動作n個の整数Ai.
出力フォーマット
求めた結果を表す整数は1つだけです.「Error!」を出力しないと、引用符は含まれません.
入力サンプル
入力サンプル1
入力サンプル2
サンプル入力3
7 3 1 2 3 4 5 6 7
7 4 1 2 3 4 5 6 7
8 4 8 5 6 2 3 4 8 9
出力サンプル
出力サンプル1
出力サンプル2
サンプル出力3
15
Error!
25
データ範囲
すべてのデータについて:m<=n;-1000<=Ai<=1000
データ番号
Nの大きさ
データ番号
Nの大きさ
1
40
11
2013
2
45
12
5000
3
50
13
10000
4
55
14
49999
5
200
15
111111
6
200
16
148888
7
1000
17
188888
8
2010
18
199999
9
2011
19
199999
10
2012
20
200000
サンプルの説明
なし
この問題は少し難易度があって、当初試験の時ただ暴力のdpだけを思い付いて、もとは55点の差が多くなくて、更に最適化して60点を過ぎることができて、しかし配列は1000*1000に開いて、直接8,9,10,11組のもとの本能の過ぎたデータを掛けました
正解:まず、各数字とその番号をスタックに入れます.大根を築く.各数の左右の要素の番号を記録します.L[k],R[k]. 最後に出力する答えはansです.0に初期化します.そして毎回スタックからスタックトップ要素、ans+というスタック要素の値を取り出します.現在取り出したスタックトップ要素の番号をkとします.ここで,P[i]=P[L[k]+P[R[k]−P[k]の数を新たに生成する.番号iの数左の数の番号をL[L[k]]とする.右側の数はR[R[k]]として与えられる.そしてR[R[k]]の左側はiである.L［L［k］の右側はiである.(チェーンテーブルのような操作)
なぜこんなことを?毎回最大の数を選ぶと最適解が得られる保証はないことを知っているからだ.だから私たちは自分に退路を残して、新しく生成した数は、前の選択を取り消して、彼の両側の数(いわゆる悔い改め)を選ぶことです.
期待得点:55、実績得点:20
#include
#include
#include
#define PAIR pair
#define xx first
#define yy second
using namespace std;
const int maxn=4e5+5;
int n,m,a[maxn],L[maxn],R[maxn],tot,ans;
bool vis[maxn];
priority_queueq;
int main(){
scanf("%d%d",&n,&m);
int i,j;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
L[i]=i-1;
R[i]=i+1;
q.push(make_pair(a[i],i));
tot++;
}
L[1]=n,R[n]=1;
if(m>n/2){
puts("Error!");
return 0;
}
while(m!=0){
int id=q.top().yy;q.pop();
if(vis[id])continue;
ans+=a[id];
a[++tot]=a[L[id]]+a[R[id]]-a[id];
vis[id]=vis[L[id]]=vis[R[id]]=1;
L[tot]=L[L[id]];
R[tot]=R[R[id]];
L[R[R[id]]]=tot;
R[L[L[id]]]=tot;
q.push(make_pair(a[tot],tot));
m--;
}
cout< Problem 3
ワイン取引(wine.cpp/c/pas)
タイトルの説明
ある地域にはNの村が分布しており、番号0からN-1で、村ごとに酒を買うか、酒を売る必要がある.第iの村のワインに対する需要をAiとし、そのうちAi>0は同村が酒を買う必要があることを示し、Ai<0は同村が酒を売る必要があることを示した.すべての村の需給バランス、すなわちすべてのAiの和は0(ΣAi=0)に等しい.しかし、M対村の間だけは貿易往来があり、そのうちi対村の間にはワインがいくら運ばれてもTiの運賃がかかる.最低いくらの運賃が必要か計算してください.すべての村の酒に対する需要を満たすことができます.
入力フォーマット
1行目の2つの整数N、M.2行目N個目の整数Ai.次にM行は行ごとに3つの整数pi,qi,Tiであり,piとqiの番号の村間で酒を運ぶのにTiの費用がかかることを示した.データはpi、qiのペアごとに最大1回発生することを保証します.
出力フォーマット
答えを表す整数を出力します.無出力Impossible
入力サンプル
3 3 50 -20 -30 0 1 10 1 2 20 0 2 100
出力サンプル
30
データ範囲
50%のデータ:2<=N<=8.100%のデータについて:2<=N<=16 0<=M<=N*(N-1)/20<=pi,qi-1000<=Ai<=1000 0<=Ti<=1000
サンプルの説明
なし
この问题のデータは比较的に不思议で、直接最小生成木+解があるかどうかを判断することができますA、解があるかどうかを判断しないで1组を间违えて、最初は明らかに最小生成木の诈欺点を书きたいと思っていました......、それから抜け穴が百出することを発见して放弃して、直接cout“impossible”は10点を得て、とっくに直接最小生成木をすることを知っています
正解:
1.すべての酒量と0の集合を見つける.この集合の点が連通ならば、その集合の最小生成木を求める、生成木の値は、その集合の酒量移動に必要な最小代価である.各酒量総和が0の集合を一つの物と見なし,リュックサックゲージを用いて最適解を求める.
状態をバイナリで圧縮し,1はノードが集合中,0は不在を表す.例えば、デジタルsのバイナリ形式は100111であり、0,1,2,5番ノードがsで表される集合にあることを示す.題目は最大n(n<=16)個のノードがあるので、sの範囲は0から(2^n)-1つまり(1<配列Sum[s]で、集合sに含まれるノードの酒量の和を記録する.酒量毎と0の集合x(Sum[x]=0)について、最小生成木が1本得られると、この生成木の対価f[i]を配列Cost[x]で記録し、平衡集合i中のノードの酒量値を記録し、必要最小対価は集合iおよびjに対してSum[i]=0およびSum[j]=0を満たすとf[i|j]=min(f[i|j],f[i]+Cost[j])となる.i|jは、集合iが集合jとマージされた後の集合所望得点:90、実得点:10を示す
#include
#include
#include
#include
using namespace std;
const int maxn=18,inf=0x3f3f3f3f;
int n,m,a[maxn],f[1<>i)&1)tot++;
}
for(i=1;i<=m;i++){
x=s[i].a,y=s[i].b;
if(((s0>>x)&1)&&((s0>>y)&1)){
fx=getfa(x),fy=getfa(y);
if(fx!=fy){
fa[fx]=fy;
cnt++,ans+=s[i].c;
}
}
}
if(cnt+1!=tot)return inf;
return ans;
}
int main(){
scanf("%d%d",&n,&m);
int i,j;
for(i=0;i>j)&1)sum[i]+=a[j];
for(i=0;i<=all;i++)
if(sum[i]==0)p[i]=kruscal(i);
else p[i]=inf;
memset(f,inf,sizeof(f));
f[0]=0;
for(i=0;i<=all;i++){
if(sum[i]!=0)continue;
for(j=1;j<=all;j++){
if(sum[j]!=0)continue;
f[i|j]=min(f[i|j],f[i]+p[j]);
}
}
if(f[all] 総得点:130、ランキング:18
まとめ:コードの细かい処理はまだ足りない、不注意な欠点はまだ直していない、次の试験の10分前に必ず真剣に自分のコードを検査して、过失性の点数をなくす确率を减らしなければならない