Codeforces Round#553(Div.2)題解

57738 ワード

_。ダイナミック企画_ _。数学数論_ Codeforces 欲が深いマトリックス最適化アナログ組み合わせの数複雑度の分析貢献する

タイトルリンク
A. Maxim and Biology
連続してACTGに変更する最小コストを取る

#include 
#include 
#define fst first
#define sed second
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
char s[100], c[] = "ACTG";

int dis(char a, char b)
{
	a = a - 'A', b = b - 'A';
	return min((a - b + 26) % 26, (b - a + 26) % 26);
}
int main()
{
#ifdef LOCAL
	//freopen("C:/input.txt", "r", stdin);
#endif
	int n;
	cin >> n >> s;
	int ans = INF;
	for (int i = 0; i < n - 3; ++i)
	{
		int cnt = 0;
		for (int j = 0; j < 4; ++j)
			cnt += dis(s[i + j], c[j]);
		ans = min(ans, cnt);
	}
	cout << ans << endl;

	return 0;
}

B. Dima and a Bad XOR
行列行ごとに0以外の数値を選択

#include 
#include 
#define fst first
#define sed second
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int N = 510;
int g[N][N];

int main()
{
#ifdef LOCAL
	//freopen("C:/input.txt", "r", stdin);
#endif
	int n, m, x = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
			scanf("%d", &g[i][j]);
		x ^= g[i][1];
	}
	if (x)
	{
		cout << "TAK" << endl;
		for (int i = 1; i <= n; ++i)
			cout << "1 ";
		cout << endl, exit(0);
	}
	for (int i = 1; i <= n; ++i)
		for (int j = 2; j <= m; ++j)
		{
			x ^= g[i][j - 1] ^ g[i][j];
			if (x)
			{
				cout << "TAK" << endl;
				for (int k = 1; k < i; ++k)
					cout << "1 ";
				cout << j << " ";
				for (int k = i + 1; k <= n; ++k)
					cout << "1 ";
				cout << endl, exit(0);
			}
		}
	cout << "NIE" << endl;

	return 0;
}

C. Problem for Nazar
シーケンス1/24/3 5 7 9/6 8 10が与えられる.奇数の偶数は交替してしかも長さは2倍になって第lからr項の和を聞きます

#include 
#include 
#define fst first
#define sed second
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;

ll calc(ll x) //logn  1~x  
{
	ll res = 0;
	ll v[2] = { 2, 1 }, w = 1; //         
	for (int i = 1; x; i = (i + 1) % 2, w *= 2)
	{
		res = (res + (v[i] + v[i] + (min(x, w) - 1) * 2LL) % MOD * (min(x, w) % MOD) % MOD * 500000004LL) % MOD; //              ll
		v[i] = (v[i] + w * 2LL) % MOD;
		x -= min(x, w);
	}
	return res;
}
int main()
{
#ifdef LOCAL
	//freopen("C:/input.txt", "r", stdin);
#endif
	ll l, r;
	cin >> l >> r;
	cout << (calc(r) - calc(l - 1) + MOD) % MOD << endl;

	return 0;
}

D. Stas and the Queue at the Buffet
各人は2つのパラメータaとbを持っていますこの人の不満度は彼の前の人の数a+後ろの人の数bのために列全体の最小の不満度を聞きます

#include 
#include 
#define fst first
#define sed second
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 10;

struct node
{
	ll a, b, i;
	bool operator < (const node &o) const
	{
		return a - b > o.a - o.b;
	}
}a[N];
int main()
{
#ifdef LOCAL
	//freopen("C:/input.txt", "r", stdin);
#endif
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i)
		scanf("%I64d%I64d", &a[i].a, &a[i].b), a[i].i = i;
	sort(a + 1, a + n + 1);
	ll ans = 0;
	for (int i = 1; i <= n; ++i)
		ans += a[i].a * (i - 1) + a[i].b * (n - i);
	cout << ans << endl;

	return 0;
}

E. Number of Components
n個の数値位置に隣接する2個の数値の間に1本の結線f(l,r)は、数値範囲[l,r]ノードのみを保持する強連通成分数関数f(1<=l<=r<=n)のすべての値をとることと、各点に寄与する区間[l,r]を計算することを表し、現在の点値がa[i]の場合1<=l<=a[i]<=r<=nとなるが、左側の点にlとrの値範囲が存在すると若干制限される.lrを調整した後,lとrの値範囲を乗算することが現在の点の寄与である.

#include 
#include 
#define fst first
#define sed second
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 10;
ll a[N];

int main()
{
#ifdef LOCAL
	//freopen("C:/input.txt", "r", stdin);
#endif
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i)
		scanf("%I64d", &a[i]);
	ll ans = 0;
	for (int i = 1; i <= n; ++i)
	{
		ll l = a[i], r = n - a[i] + 1;
		if (a[i - 1] <= a[i])
			l = min(l, a[i] - a[i - 1]);
		else
			r = min(r, a[i - 1] - a[i]);
		ans += l * r;
	}
	cout << ans << endl;

	return 0;
}

F. Sonya and Informatics
1つの01列などの確率はランダムに2つの異なる位置を選んでk回の操作を交換した後に非減算シーケンスの確率を尋ねて大物のブログを参考にします

#include 
#include 
#define fst first
#define sed second
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
const int N = 110;
int C[N][N];
int a[N];
//ll f[N][N]; //f[i][j]  i   j 0         

ll qpow(ll a, ll n, ll m)
{
	ll res = 1;
	while (n)
	{
		if (n & 1)
			res = res * a % m;
		a = a * a % m;
		n >>= 1;
	}
	return res;
}
struct Matrix
{
	ll m[N][N];
	static const int N = 50; //  
	Matrix(int v = 0)
	{
		memset(m, 0, sizeof(m));
		if (v)
			for (int i = 0; i < N; i++)
				m[i][i] = v;
	}
	Matrix operator * (const Matrix &b)
	{
		Matrix t;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				for (int k = 0; k < N; k++)
					t.m[i][j] = (t.m[i][j] + m[i][k] * b.m[k][j]) % MOD;
		return t;
	}
	friend Matrix operator ^ (Matrix a, int n)
	{
		Matrix t(1);
		while (n)
		{
			if (n & 1)
				t = t * a;
			a = a * a;
			n >>= 1;
		}
		return t;
	}
}tran, x; //x[0][i]       i 0/1         
int main()
{
#ifdef LOCAL
	freopen("C:/input.txt", "r", stdin);
#endif
	C[0][0] = 1;
	for (int i = 1; i < N; i++)
	{
		C[i][0] = 1;
		for (int j = 1; j < N; j++)
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
	}
	int n, k, z = 0; //0  
	cin >> n >> k; 
	for (int i = 1; i <= n; ++i)
		scanf("%d", &a[i]), z += !a[i];
	int p = 0; //             1=     0
	for (int i = 1; i <= z; ++i)
		p += a[i];
	/*
	f[0][p] = 1;
	int m = min(z, n - z), den = qpow(C[n][2], MOD - 2, MOD); //den   
	for (int i = 0; i < k; ++i) //  
		for (int j = 0; j <= m; ++j) //              
		{
			if (j) //         -1
				f[i + 1][j - 1] = (f[i + 1][j - 1] + f[i][j] * j * j * den) % MOD; //0  *1  
			if (j < m) //  +1
				f[i + 1][j + 1] = (f[i + 1][j + 1] + f[i][j] * (z - j) * (n - z - j) * den) % MOD; //0 *1 
			f[i + 1][j] = (f[i + 1][j] + f[i][j] * (C[z][2] + C[n - z][2] + (z - j) * j + (n - z - j) * j) * den) % MOD;
		}
	cout << f[k][0] << endl;
	*/
	x.m[0][p] = 1; //    100%
	ll m = min(z, n - z), den = qpow(C[n][2], MOD - 2, MOD); //den   
	for (int i = 0; i <= m; ++i) //               
	{
		int j;
		if (i) // i-1  1    
		{
			j = i - 1; //    
			tran.m[i - 1][i] = (z - j) * (n - z - j) * den % MOD; //0 *1 
		}
		tran.m[i][i] = (C[z][2] + C[n - z][2] + (z - i) * i + (n - z - i) * i) * den % MOD; //0/1     01/10  
		if (i < m) // i+1  1    
		{
			j = i + 1;
			tran.m[i + 1][i] = j * j * den % MOD; //0  *1  
		}
	}
	x = x * (tran ^ k);
	cout << x.m[0][0] << endl; //      

	return 0;
}

Automation Anywhere Enterpriseを使う際に役立つサイト等をまとめてみた（リンク集）

【Automation Anywhere】初回レコーディングでのみ作成できるコマンドのまとめ