2020ブルーブリッジカップ第1ラウンドの省試合B組の問題解

2020ブルーブリッジカップ第1ラウンドの省試合B組

前言

Aランニングトレーニング

B記念日

C併合検出

D REPEATプログラム

E行列

F除去シーケンス

G復号

H走方格

I整数接合

Jネットワーク分析

前言
4日の省試合、今日まで依然として1篇の問題解がなくて、いっそ自分で1つ書いて、もちろん標準的な答えではありませんて、純粋に個人の理解で、間違いがあるかもしれなくて、指摘を歓迎します.個人的には今回の省試合の問題の質は悪くないと思います.すべて書ける問題で、難易度の勾配も悪くありません.最後の問題は簡単かもしれません.空欄の答えは保存されていないので、考え方だけを書きます.プログラミングの問題は後でコードを補充します.
Aランニングトレーニング
カタツムリが木に登ったり、井戸に登ったりするなど、似たような問題が多い.直接計算したり、シミュレーションをプログラミングしたりすることができます.最後のランニングの1分の残りの体力は100ではなく400であることに注意しなければならない.
B記念日
何も言うことはありません.手で計算しましょう.EXcelには直接日数を得る関数があるそうです.
C連結検査
全体が1であると仮定すると、合併検出には1/Kカートリッジの試薬が消費され、そのうち0.01の感染者が0.01*Kカートリッジの試薬を追加的に消費する必要がある.すなわち、合計1/K+K/100カートリッジの試薬が必要であり、基本不等式に従ってKを10とする.
D REPEATプログラム
翻訳プログラムを書くこともできますし、巧みに取って、テキストを交換してコードに変えて、直接走ることもできます.翻訳プログラムを書くとdfsを書くことができて、repeatを発見するたびに新しい呼び出しが起きて、伝達するパラメータは私が使っているインデントで、これによって優先度を得て、インデントが長いのは優先的に計算して結果を得る必要があります.この行のインデントがパラメータより小さい場合は、上位レベルに戻ります.
E行列
観察したところ、左上と右下は12020しか取れないことが分かった.1に隣接する2つの格子、すなわち1行2列と2行1列は、2,3しか取れない.さらに1列後ろに移動します.つまり、1行3列と2行2列は、4、5しか取れません.推定では1009というグループがありますが、答えは2^1009 mod 2020です.
F整除シーケンス
問題がある場合は、入力に対して直接ループ除去2を実行すればよい.
Gデコード
2文字ずつ読んで、2番目のビットが数字かどうかを見て、そうでなければ現在のビット文字を出力し、指定した数字の個数の現在の文字を出力し、位置+1を出力する.直接順番に出力し、数字を読むたびに前のビットを補償することもできます.
H走方格
簡単なdpでよい、dp[i][j]=dp[i-1][j]+dp[i][j-1].dfsで解くこともできますが、数値が30に近づくとタイムアウトする可能性があります.表を打ってみました.
I整数接合
接合数は2つの部分から構成され、第1の部分はa*10^b、第2の部分はcと見なすことができるので、第1の部分を前処理し、各cに対して第1の部分のような数が2つの部分の和modK=0を満たすかを調べ、ansを加えることができる.
具体的には、2次元配列modを作成し、1次元は10のべき乗を表し、2次元はmodKの残数を表す.各数と101001000…10^9の積modKの残数を計算し、対応する2次元配列のセルを+1します.処理後mod[a][b]は、1つの数の後にa個0、modK残数bが続く数(すなわち、前述の第1の部分)の個数を表す.そして、この数が前述の接合数の第2の部分であると仮定すると、条件に合致する第1の部分modKがこの数modKに加算され、Kのモデリング結果は0となる.
処理を容易にするために、私は2つの関数、1つのgetlを書いて、入力値の桁数を返しました.getllは、10のべき乗を返します.これにより,各数aを処理する際に,前処理で得られたmod配列に直接アクセスできる.1次元はgetl(a)であり、第1の部分がどれだけ0に続くかを示し、第2の部分が(K-a modK)modKであり、2つの部分の和modKが0であることを示す.得られた結果は、条件を満たすa*10^bの個数である.
第1の部分のaと第2の部分のcは同じ数であることに注意しなければならない.処理時に現在数aにgetll(a)を乗じてKをモデリングすることで、私たちが必要とする残高(K-a modK)modKと同じかどうかを確認できます.同じ場合、この残高の数に現在の処理を含むこの数が含まれていることを示す場合は、ansは-1です.

#include 
#include 
#include 
using namespace std;

const int maxn = 100010;
int mod[10][maxn];
long long a[maxn];
int getl(long long a)
{
	int r = 0;
	while(a>0)
	{
		r++;
		a/=10;
	}
	return r;
}
long long getll(int a)
{
	long long r = 1;
	while(a--)r*=10;
	return r;
}
int main()
{
	int n,k;
	long long ans = 0;
	cin >> n >> k;
	for(int i = 0;i < n;i++)
	{
		cin >> a[i];
		long long p = 0,q = 1;
		while(p<10)
		{
			long long t = (a[i]*q)%k;
			mod[p][t]++;
			p++;
			q*=10;
		}
	}
	//cout << mod[1][0] << ' ' << mod[1][1];
	for(int i = 0;i < n;i++)
	{
		//cout << getl(a[i]) << ' ' << (k-a[i]%k)%k << endl;
		ans+=mod[getl(a[i])][(k-a[i]%k)%k];
		//cout << a[i]*getll(getl(a[i]))%k;
		if((a[i]*getll(getl(a[i])) + a[i])%k == 0)ans--;
	}
	cout << ans;
	return 0;
	
}

Jネットワーク分析
セットを並べて解くことで,最後に各点の重みを求めるだけであるため,セットを調べるには各ルート値を更新するだけでよい.具体的には、各union集合のポイントの増分値を保存する増分配列を設定し、集合がマージされるたびに、マージされる集合のルートの増分値から、マージされる集合のルートの増分値を減算します.これにより、最後にポイントウェイトを求めるときに、下から上へルートを探すだけで、増分値を加えるたびにポイントの最終ウェイトが得られます.コレクションをマージするときは、ルートノードの親ノードのみが更新され、他のノードの親ノードはルートノードのままであり、増分値もルートノードのみが更新され、ツリーが生成されるように類比することができ、リーフノードの重み値を求めるのがルート探索プロセスである.

#include 
#include 
#include 
using namespace std;

const int maxn = 10010;
int ans[maxn];
int add[maxn];
int fa[maxn];
int v[maxn];
int f(int i)
{
	if(fa[i]!=i)return f(fa[i]);
}
void uni(int a,int b)
{
	if(f(a) == f(b)) return;
	else
	{
		a = f(a),b = f(b);
		if(v[a]>=v[b])
		{
			add[b]-=add[a];
			fa[b] = a;
			v[a]+=v[b];
		}
		else
		{
			add[a]-=add[b];
			fa[a] = b;
			v[b]+=v[a];
		}
	}
}
int main()
{
	int n,m;
	int c = n;
	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		fa[i] = i;v[i] = 1;
	}
 	for(int i = 0;i < m;i++)
	{
		int a,b,c;
		cin >> a >> b >> c;
		if(a == 1)
		{
			uni(b,c);
		}
		else
		{
			add[f(b)]+=c;
		}
	}
	for(int i = 1;i <= n;i++)
	{
		int t = i;
		ans[i]+=add[i];
		while(fa[t]!=t)
		{
			ans[i]+=add[fa[t]];
			t=fa[t];
		}
	}
	for(int i = 1;i <= n;i++)
	cout << ans[i] << endl;
	return 0;
}