Codeforces Round#553(Div.2)題解

タイトルリンク
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;
}