(牛客2021)第1回河北工業大学プログラム設計コンテスト(一部題解)
A.WELCOME!
ちょくせつしゅつりょく
B.POOLING
題意:n*mサイズの図を与え、その図の各サイズがk*kのサブ図の最大数を求める.
考え方:nとmは小さいので、直接暴力的に書くことができます.
C.槍投げゲーム
**题意:**1人1回槍投げ、現在槍投げの点数は1+(槍投げ距離が現在槍投げ距離以下の槍投げ数)-(槍投げ距離が現在槍投げ距離以上の槍投げ数)で、最後の2人の得点を求め、点数によって結果を出力します.
考え方:スコア計算式に基づいて、毎回前の数が自分の数より大きいか、自分の数より小さいかを算出する必要があることを知っています.そこで、数状配列を使用して、前の数が自分の数より小さいかkを求めることができます.(逆シーケンスペアの処理と同様)次いでi−kを用いて自分より大きい数を得た.投擲距離のデータ範囲が大きすぎますが、総数は100000しかありませんので、数値配列を使用するにはデータを離散化する必要があります.この問題の和はintより大きい可能性があるのでlong longで処理する必要があります.
D.公園で遊ぶ
标题:1つのn*mのメッシュの中で、k個の点を与えて、(1,1)から順にk個の点を通って(n,m)、総距離と最短を保証する前提の下で何種類の移動案があって、あなたは毎回上下左右のある方向に1格を移動することができます.
考え方:(1,1)から(X 1,Y 1)までの移動シナリオ数に(X 1,Y 1)から(X 2,Y 2)までのシナリオ数に(Xk,Yk)から(n,m)までのシナリオ数を乗じて、答えを求める.
(1,1)から(n,m)までのシナリオ数の方程式をC(n＋m,n)C(n＋m,n)C(n＋m,n)C(n＋m,n)C(n＋m,n)から(X 1,Y 1)から(X 2,Y 2)までのシナリオ数をC(a b s(X 1−X 2)＋a b s(Y 1−Y 2),a b s(X 1−X 2)C(abs(X 1−X 1−X 2)＋abs(Y 1−Y 2),abs(X 1−Y 2),abs(X 1−X 2))C(abs(X 1−X 2)＋abs(Y 1−Y 2),abs(X 1−Y 2),abs(X 1−Y 2),ab−X 2)).
E.単純数論
先に穴をあけておいて,まだ補充していない.
F.回文列
題意:1つの文字列を与えて、順序を乱すことができて、少なくともいくつかの文字列に分割しなければならないことを聞いて、分割した文字列がすべて回文列になることができます.
考え方:1つの文字列に奇数文字が1つしか現れないので、奇数文字の個数を計算すればいい.
G.データ構造が難しいですね
考え方:この問題は1つの領域の値を迅速に修正する必要があります.差分アルゴリズムを使用して処理し、接頭辞積を計算しますが、nの範囲が大きすぎて、セグメントツリーを使用して区間の最大値をクエリーすることはできません.しかし、この問題にはいくつかの性質があるので、他の方法で計算することができます.
性質1:配列に0が現れないと、配列全体の接頭辞積の絶対値が徐々に大きくなります.
性質2:配列に0が現れると、後続のすべての接頭辞積が0になります.
したがって,配列を用いて,i i i i点に最も近い接頭辞積が0より大きい下付きスケールを前処理することができる.(この下付き文字はi i i i点以下である必要がある)
次に、クエリー位置LとRを入力するたびに、まずRをクエリーして、下表がLより大きい場合は、その点がL,Rの間にあることを説明し、その点座標を直接出力することができ、小さい場合は合法ではなく、R点の接頭辞積が0であるかどうかを判断し、もしそうであれば直接0を出力する.L、R区間には0より大きい接頭辞積が存在しないため、R点の接頭辞積が0でない場合、説明L,R区間数はすべて負数であり,また絶対値が逓増状態であるため,L点の接頭辞積が最大値となる.(この問題は2つの配列しか開けません.そうしないとメモリがオーバーします)
J.ちょっと複雑なgcd問題
考え方:(公式の問題解を見て初めて知った)
f ( a 1 , a 2 , a 3 , . . . , a k ) = f(a1,a2,a3,...,ak)= f(a1,a2,a3,...,ak)= ∑ a 1 = 1 n\sum_{a1=1}^n ∑a1=1n ∑ a 2 = 1 a 1\sum_{a2=1}^{a1} ∑a2=1a1 ∑ a 3 = 1 a 2\sum_{a3=1}^{a2} ∑a3=1a2… ∑ a k = 1 a k − 1\sum_{ak=1}^{ak-1} ∑ak=1ak−1[ g c d ( a 1 , a 2 , a 3 , . . . , a k ) = = a 1 gcd(a1,a2,a3,...,ak)==a1 gcd(a1,a2,a3,...,ak)==a1]
a 1≧a 2≧a 3≧.≥ a k a1≥a2≥a3≥...≥ak a1≥a2≥a3≥...≥ak,またg c d(a 1,a 2,a 3,.,a k)==a 1 gcd(a 1,a 2,a 3,...,ak)=a 1 gcd(a 1,a 2,a 3,...,ak)=a 1なのでa 1=a 2=a 3=.=a k a1=a2=a3=...=ak a1=a2=a3=...=ak
すなわちg(a 1,a 2,a 3,..a k a 1,a 2,a 3,...ak a 1,a 2,a 3,...ak)はΣa i=1 nsum_に簡略化できる{ai=1}^{n} ∑ai=1n a 1 a1 a1
k.星拝年
标题:n 1個の始点とn 2個の終点を与え、始点から終点までの最小費用の経路上の最小点数がいくらであるかを求め、k-最小点数を出力する.
構想:最低費用k、すなわち起点から終点までの最短ルートkが与えられている以上、建図は1つの仮想ソース点とすべての起点を接続するだけで、もう1つの仮想終点とすべての終点を接続し、ソース点から1回の最短ルートを走って、過程の中で経た点数を更新して、このように得られた点数はきっと最小である.
ちょくせつしゅつりょく
#include
using namespace std;
int main(){
printf("Welcome to The First Programming Competition of Hebei University of technology!");
return 0;
}
B.POOLING
題意:n*mサイズの図を与え、その図の各サイズがk*kのサブ図の最大数を求める.
考え方:nとmは小さいので、直接暴力的に書くことができます.
#include
using namespace std;
int n,m,k;
int p[60][60],pp[60][60];
int get(int x,int y){
int ans=-1;
for(int i=x;i C.槍投げゲーム
**题意:**1人1回槍投げ、現在槍投げの点数は1+(槍投げ距離が現在槍投げ距離以下の槍投げ数)-(槍投げ距離が現在槍投げ距離以上の槍投げ数)で、最後の2人の得点を求め、点数によって結果を出力します.
考え方:スコア計算式に基づいて、毎回前の数が自分の数より大きいか、自分の数より小さいかを算出する必要があることを知っています.そこで、数状配列を使用して、前の数が自分の数より小さいかkを求めることができます.(逆シーケンスペアの処理と同様)次いでi−kを用いて自分より大きい数を得た.投擲距離のデータ範囲が大きすぎますが、総数は100000しかありませんので、数値配列を使用するにはデータを離散化する必要があります.この問題の和はintより大きい可能性があるのでlong longで処理する必要があります.
#include
using namespace std;
#define ll long long
ll tt[101000];
int lowbit(int x){
return x&(-x);
}
void add(int x){
while(x<=100010){
tt[x]++;
x+=lowbit(x);
}
}
ll sum(int x){
ll k=0;
while(x>0){
k+=tt[x];
x-=lowbit(x);
}
return k;
}
int a[100100];
int p[100100];
int main(){
int n;
scanf("%d",&n);
for(int i=0;ians2){
printf("Calculus is hebei king!
");
}
else if(ans1 D.公園で遊ぶ
标题:1つのn*mのメッシュの中で、k個の点を与えて、(1,1)から順にk個の点を通って(n,m)、総距離と最短を保証する前提の下で何種類の移動案があって、あなたは毎回上下左右のある方向に1格を移動することができます.
考え方:(1,1)から(X 1,Y 1)までの移動シナリオ数に(X 1,Y 1)から(X 2,Y 2)までのシナリオ数に(Xk,Yk)から(n,m)までのシナリオ数を乗じて、答えを求める.
(1,1)から(n,m)までのシナリオ数の方程式をC(n＋m,n)C(n＋m,n)C(n＋m,n)C(n＋m,n)C(n＋m,n)から(X 1,Y 1)から(X 2,Y 2)までのシナリオ数をC(a b s(X 1−X 2)＋a b s(Y 1−Y 2),a b s(X 1−X 2)C(abs(X 1−X 1−X 2)＋abs(Y 1−Y 2),abs(X 1−Y 2),abs(X 1−X 2))C(abs(X 1−X 2)＋abs(Y 1−Y 2),abs(X 1−Y 2),abs(X 1−Y 2),ab−X 2)).
#include
using namespace std;
#define ll long long
const ll mod=1e9+7;
ll fac[1000007];
ll ksm(ll x,ll p){
ll res=1;
while(p){
if(p%2==1) res=res*x%mod;
p/=2;
x=x*x%mod;
}
return res;
}
ll inv(ll a) {
return ksm(a,mod-2)%mod;
}
void solve() {
fac[0] = 1;
for(int i = 1;i<1000006; i++) {
fac[i] = (fac[i-1]*i)%mod;
}
}
ll comb(ll n,ll k){
if(k>n)return 0;
if(k==1)return n;
return (fac[n]*inv(fac[k])%mod*inv(fac[n-k])%mod)%mod;
}
int main(){
ll n,m,k;
solve();
scanf("%lld%lld%lld",&n,&m,&k);
ll x=1,y=1;
ll ans=1;
ll a,b;
for(int i=1;i<=k;i++){
scanf("%lld%lld",&a,&b);
ans=(ans*comb(abs(x-a)+abs(y-b),abs(x-a)))%mod;
y=b,x=a;
}
ans=(ans*comb(abs(n-x+m-y),abs(m-y)))%mod;
printf("%lld
",ans);
return 0;
}
E.単純数論
先に穴をあけておいて,まだ補充していない.
F.回文列
題意:1つの文字列を与えて、順序を乱すことができて、少なくともいくつかの文字列に分割しなければならないことを聞いて、分割した文字列がすべて回文列になることができます.
考え方:1つの文字列に奇数文字が1つしか現れないので、奇数文字の個数を計算すればいい.
#include
using namespace std;
string str;
int p[30];
int main(){
cin>>str;
int k=str.size();
for(int i=0;i G.データ構造が難しいですね
考え方:この問題は1つの領域の値を迅速に修正する必要があります.差分アルゴリズムを使用して処理し、接頭辞積を計算しますが、nの範囲が大きすぎて、セグメントツリーを使用して区間の最大値をクエリーすることはできません.しかし、この問題にはいくつかの性質があるので、他の方法で計算することができます.
性質1:配列に0が現れないと、配列全体の接頭辞積の絶対値が徐々に大きくなります.
性質2:配列に0が現れると、後続のすべての接頭辞積が0になります.
したがって,配列を用いて,i i i i点に最も近い接頭辞積が0より大きい下付きスケールを前処理することができる.(この下付き文字はi i i i点以下である必要がある)
次に、クエリー位置LとRを入力するたびに、まずRをクエリーして、下表がLより大きい場合は、その点がL,Rの間にあることを説明し、その点座標を直接出力することができ、小さい場合は合法ではなく、R点の接頭辞積が0であるかどうかを判断し、もしそうであれば直接0を出力する.L、R区間には0より大きい接頭辞積が存在しないため、R点の接頭辞積が0でない場合、説明L,R区間数はすべて負数であり,また絶対値が逓増状態であるため,L点の接頭辞積が最大値となる.(この問題は2つの配列しか開けません.そうしないとメモリがオーバーします)
#include
",sum[d[y]]);
else if(sum[y]==0)printf("0
");
else printf("%lld
",sum[x]);
}
return 0;
}
J.ちょっと複雑なgcd問題
考え方:(公式の問題解を見て初めて知った)
f ( a 1 , a 2 , a 3 , . . . , a k ) = f(a1,a2,a3,...,ak)= f(a1,a2,a3,...,ak)= ∑ a 1 = 1 n\sum_{a1=1}^n ∑a1=1n ∑ a 2 = 1 a 1\sum_{a2=1}^{a1} ∑a2=1a1 ∑ a 3 = 1 a 2\sum_{a3=1}^{a2} ∑a3=1a2… ∑ a k = 1 a k − 1\sum_{ak=1}^{ak-1} ∑ak=1ak−1[ g c d ( a 1 , a 2 , a 3 , . . . , a k ) = = a 1 gcd(a1,a2,a3,...,ak)==a1 gcd(a1,a2,a3,...,ak)==a1]
a 1≧a 2≧a 3≧.≥ a k a1≥a2≥a3≥...≥ak a1≥a2≥a3≥...≥ak,またg c d(a 1,a 2,a 3,.,a k)==a 1 gcd(a 1,a 2,a 3,...,ak)=a 1 gcd(a 1,a 2,a 3,...,ak)=a 1なのでa 1=a 2=a 3=.=a k a1=a2=a3=...=ak a1=a2=a3=...=ak
すなわちg(a 1,a 2,a 3,..a k a 1,a 2,a 3,...ak a 1,a 2,a 3,...ak)はΣa i=1 nsum_に簡略化できる{ai=1}^{n} ∑ai=1n a 1 a1 a1
#include
using namespace std;
#define ll long long
const ll mod=1e9+7;
int main(){
ll n,k,ans=0;
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++){
ans=(ans+i)%mod;
}
printf("%lld
",ans);
return 0;
}
k.星拝年
标题:n 1個の始点とn 2個の終点を与え、始点から終点までの最小費用の経路上の最小点数がいくらであるかを求め、k-最小点数を出力する.
構想:最低費用k、すなわち起点から終点までの最短ルートkが与えられている以上、建図は1つの仮想ソース点とすべての起点を接続するだけで、もう1つの仮想終点とすべての終点を接続し、ソース点から1回の最短ルートを走って、過程の中で経た点数を更新して、このように得られた点数はきっと最小である.
#include
using namespace std;
#define pii pair
#define mk make_pair
#define ll long long
ll n,m,x,y,k;
vectorG[100010];
ll dist[100010],vis[100010],cnt[100010];
void dij(){
for(int i=0;i<=n+1;i++){
dist[i]=0x3f3f3f3f;
cnt[i]=0x3f3f3f3f;
}
priority_queueq;
dist[0]=0;
cnt[0]=0;
q.push(mk(0,0));
while(!q.empty()){
int t=q.top().second;
q.pop();
if(vis[t])continue;
vis[t]=1;
int k=G[t].size();
for(int i=0;i dist[t] + w) {
dist[v] = dist[t] + w;
cnt[v]=cnt[t]+1;//
q.push(mk(-dist[v],v));
}
else if(dist[v]==dist[t] + w){
cnt[v]=min(cnt[v],cnt[t]+1);
q.push(mk(-dist[v],v));
}
}
}
}
int main(){
scanf("%lld%lld%lld%lld%lld",&n,&m,&x,&y,&k);
ll a,b,c;
for(int i=1;i<=x;i++){
scanf("%lld",&a);
G[0].push_back(mk(a,0));
}
for(int i=1;i<=y;i++){
scanf("%lld",&a);
G[a].push_back(mk(n+1,0));
}
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld",&a,&b,&c);
G[a].push_back(mk(b,c));
}
dij();
if(cnt[n+1]-1>=k){
printf("we break up
");
}
else printf("%lld
",k-cnt[n+1]+1);
return 0;
}