codeforces 1106题解

发表于 2019-02-01 分类于算法阅读次数：本文字数： 17k 阅读时长 ≈ 15 分钟

A. Lunar New Year and Cross Counting

Description:

Lunar New Year is approaching, and you bought a matrix with lots of "crosses". This matrix $M$ of size $n \times n$ contains only 'X' and '.' (without quotes). The element in the $i$-th row and the $j$-th column $(i, j)$ is defined as $M(i, j)$, where $1 \leq i, j \leq n$. We define a cross appearing in the $i$-th row and the $j$-th column ($1 < i, j < n$) if and only if $M(i, j) = M(i - 1, j - 1) = M(i - 1, j + 1) = M(i + 1, j - 1) = M(i + 1, j + 1) = $ 'X'. The following figure illustrates a cross appearing at position $(2, 2)$ in a $3 \times 3$ matrix. X.X.X.X.X Your task is to find out the number of crosses in the given matrix $M$. Two crosses are different if and only if they appear in different rows or columns. ## Input: The first line contains only one positive integer $n$ ($1 \leq n \leq 500$), denoting the size of the matrix $M$. The following $n$ lines illustrate the matrix $M$. Each line contains exactly $n$ characters, each of them is 'X' or '.'. The $j$-th element in the $i$-th line represents $M(i, j)$, where $1 \leq i, j \leq n$.

Output

Output a single line containing only one integer number $k$ — the number of crosses in the given matrix $M$.

Sample Input:

5 ..... .XXX. .XXX. .XXX. .....

Sample Output:

Sample Input:

2 XX XX

Sample Output:

Sample Input:

6 ...... X.X.X. .X.X.X X.X.X. .X.X.X ......

Sample Output:

题目链接

##题解:

$O(n^2)$暴力数一下就好了

AC代码:

#include <bits/stdc++.h>
using namespace std;


char g[510][510];

int n, ans;

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) 
		scanf("%s", &g[i][1]);
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= n; ++j) {
			if(g[i][j] == 'X' && g[i - 1][j - 1] == 'X' && g[i - 1][j + 1] == 'X' && g[i + 1][j - 1] == 'X' && g[i + 1][j + 1] == 'X')
				ans++;
		}
	}
	printf("%d\n", ans);
	return 0;
}

B. Lunar New Year and Food Ordering

Description:

Lunar New Year is approaching, and Bob is planning to go for a famous restaurant — "Alice's". The restaurant "Alice's" serves $n$ kinds of food. The cost for the $i$-th kind is always $c_i$. Initially, the restaurant has enough ingredients for serving exactly $a_i$ dishes of the $i$-th kind. In the New Year's Eve, $m$ customers will visit Alice's one after another and the $j$-th customer will order $d_j$ dishes of the $t_j$-th kind of food. The $(i + 1)$-st customer will only come after the $i$-th customer is completely served. Suppose there are $r_i$ dishes of the $i$-th kind remaining (initially $r_i = a_i$). When a customer orders $1$ dish of the $i$-th kind, the following principles will be processed. If $r_i > 0$, the customer will be served exactly $1$ dish of the $i$-th kind. The cost for the dish is $c_i$. Meanwhile, $r_i$ will be reduced by $1$. Otherwise, the customer will be served $1$ dish of the cheapest available kind of food if there are any. If there are multiple cheapest kinds of food, the one with the smallest index among the cheapest will be served. The cost will be the cost for the dish served and the remain for the corresponding dish will be reduced by $1$. If there are no more dishes at all, the customer will leave angrily. Therefore, no matter how many dishes are served previously, the cost for the customer is $0$.If the customer doesn't leave after the $d_j$ dishes are served, the cost for the customer will be the sum of the cost for these $d_j$ dishes. Please determine the total cost for each of the $m$ customers.

Input:

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 10^5$), representing the number of different kinds of food and the number of customers, respectively. The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^7$), where $a_i$ denotes the initial remain of the $i$-th kind of dishes. The third line contains $n$ positive integers $c_1, c_2, \ldots, c_n$ ($1 \leq c_i \leq 10^6$), where $c_i$ denotes the cost of one dish of the $i$-th kind. The following $m$ lines describe the orders of the $m$ customers respectively. The $j$-th line contains two positive integers $t_j$ and $d_j$ ($1 \leq t_j \leq n$, $1 \leq d_j \leq 10^7$), representing the kind of food and the number of dishes the $j$-th customer orders, respectively.

Output

Print $m$ lines. In the $j$-th line print the cost for the $j$-th customer.

Sample Input:

8 5 8 6 2 1 4 5 7 5 6 3 3 2 6 2 3 2 2 8 1 4 4 7 3 4 6 10

Sample Output:

22 24 14 10 39

Sample Input:

6 6 6 6 6 6 6 6 6 66 666 6666 66666 666666 1 6 2 6 3 6 4 6 5 6 6 66

Sample Output:

36 396 3996 39996 399996 0

Sample Input:

6 6 6 6 6 6 6 6 6 66 666 6666 66666 666666 1 6 2 13 3 6 4 11 5 6 6 6

Sample Output:

36 11058 99996 4333326 0 0

题目链接

##题解:

模拟一下，$O((n+m)log(n))$

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, m, a[N], c[N], t, d, cnt;

struct node {
	int cost, id;
	bool operator<(const node &rhs) const {
		if(cost == rhs.cost)
			return id < rhs.id;
		return cost < rhs.cost;
	}
}temp;

map<node, int> mp;


int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);	
	}
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &c[i]);
		temp.cost = c[i];
		temp.id = i;
		mp[temp] = a[i];
	}
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d", &t, &d);
		long long ans = 0;
		temp.cost = c[t], temp.id = t;
		if(mp.find(temp) != mp.end()) {
			cnt = min(mp[temp], d);
			d -= cnt;
			mp[temp] -= cnt;
			ans += 1LL * cnt * temp.cost;
			if(mp[temp] == 0)
				mp.erase(temp);
		}
		while(d > 0) {
			if(mp.empty()) break;
			temp = mp.begin()->first;
			cnt = min(mp[temp], d);
			d -= cnt;
			mp[temp] -= cnt;
			ans += 1LL * cnt * temp.cost;
			if(mp[temp] == 0)
				mp.erase(temp);
		};
		if(d != 0)
			ans = 0;
		printf("%lld\n", ans);
	}
	return 0;
}

C. Lunar New Year and Number Division

Description:

Lunar New Year is approaching, and Bob is struggling with his homework – a number division problem. There are $n$ positive integers $a_1, a_2, \ldots, a_n$ on Bob's homework paper, where $n$ is always an even number. Bob is asked to divide those numbers into groups, where each group must contain at least $2$ numbers. Suppose the numbers are divided into $m$ groups, and the sum of the numbers in the $j$-th group is $s_j$. Bob's aim is to minimize the sum of the square of $s_j$, that is $\sum_{j = 1}^{m} s_j^2.$ Bob is puzzled by this hard problem. Could you please help him solve it?

Input:

The first line contains an even integer $n$ ($2 \leq n \leq 3 \cdot 10^5$), denoting that there are $n$ integers on Bob's homework paper. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^4$), describing the numbers you need to deal with.

Output

A single line containing one integer, denoting the minimum of the sum of the square of $s_j$, which is $\sum_{i = j}^{m} s_j^2,$ where $m$ is the number of groups.

Sample Input:

4 8 5 2 3

Sample Output:

164

Sample Input:

6 1 1 1 2 2 2

Sample Output:

题目链接

题解:

显然两个两个一起最小，不难看出最小的和最大的匹配总和最小，$O(nlog(n))$

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 10;

int a[N], n, tmp;
long long ans;

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	sort(a + 1, a + n + 1);
	for(int i = 1; 2 * i <= n; ++i) {
		tmp = a[i] + a[n + 1 - i];
		ans += 1LL * tmp * tmp;
	}
	printf("%lld\n", ans);
	return 0;
}

D. Lunar New Year and a Wander

Description:

Lunar New Year is approaching, and Bob decides to take a wander in a nearby park. The park can be represented as a connected graph with $n$ nodes and $m$ bidirectional edges. Initially Bob is at the node $1$ and he records $1$ on his notebook. He can wander from one node to another through those bidirectional edges. Whenever he visits a node not recorded on his notebook, he records it. After he visits all nodes at least once, he stops wandering, thus finally a permutation of nodes $a_1, a_2, \ldots, a_n$ is recorded. Wandering is a boring thing, but solving problems is fascinating. Bob wants to know the lexicographically smallest sequence of nodes he can record while wandering. Bob thinks this problem is trivial, and he wants you to solve it. A sequence $x$ is lexicographically smaller than a sequence $y$ if and only if one of the following holds: $x$ is a prefix of $y$, but $x \ne y$ (this is impossible in this problem as all considered sequences have the same length); in the first position where $x$ and $y$ differ, the sequence $x$ has a smaller element than the corresponding element in $y$. ## Input: The first line contains two positive integers $n$ and $m$ ($1 \leq n, m \leq 10^5$), denoting the number of nodes and edges, respectively. The following $m$ lines describe the bidirectional edges in the graph. The $i$-th of these lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$), representing the nodes the $i$-th edge connects. Note that the graph can have multiple edges connecting the same two nodes and self-loops. It is guaranteed that the graph is connected.

Output

Output a line containing the lexicographically smallest sequence $a_1, a_2, \ldots, a_n$ Bob can record.

Sample Input:

3 2 1 2 1 3

Sample Output:

1 2 3

Sample Input:

5 5 1 4 3 4 5 4 3 2 1 5

Sample Output:

1 4 3 2 5

Sample Input:

10 10 1 4 6 8 2 5 3 7 9 4 5 6 3 4 8 10 8 9 1 10

Sample Output:

1 4 3 7 9 8 6 5 2 10

题目链接

题解:

一开始在点1, 每次第一次到达一个点记录到答案，求字典序最小的答案序列

类似Prim的思想，每次取最小的，用优先队列实现，$O(nlog(m))$

AC代码:

#include <bits/stdc++.h>
using namespace std;

priority_queue<int, vector<int>, greater<int>> pq;
const int N = 1e5 + 10;

int head[N], vis[N], pnt[N << 1], nxt[N << 1], cnt, n, m, x, y;

vector<int> ans;

void add(int x, int y) {
	pnt[cnt] = y;
	nxt[cnt] = head[x];
	head[x] = cnt++;
}

int main() {
	memset(head, -1, sizeof(head));
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d", &x, &y);
		add(x, y);
		add(y, x);
	}
	pq.push(1);
	while(!pq.empty()) {
		int t = pq.top();
		pq.pop();
		if(vis[t]) continue;
		vis[t] = 1;
		ans.push_back(t);
		for(int i = head[t]; ~i; i = nxt[i]) {
			int j = pnt[i];
			if(vis[j]) continue;
			pq.push(j);
		}
	}
	for(int i = 0; i < ans.size(); ++i)
		printf("%d%c", ans[i], " \n"[i == ans.size() - 1]);
	return 0;
}

E. Lunar New Year and Red Envelopes

Description:

Lunar New Year is approaching, and Bob is going to receive some red envelopes with countless money! But collecting money from red envelopes is a time-consuming process itself. Let's describe this problem in a mathematical way. Consider a timeline from time $1$ to $n$. The $i$-th red envelope will be available from time $s_i$ to $t_i$, inclusive, and contain $w_i$ coins. If Bob chooses to collect the coins in the $i$-th red envelope, he can do it only in an integer point of time between $s_i$ and $t_i$, inclusive, and he can't collect any more envelopes until time $d_i$ (inclusive) after that. Here $s_i \leq t_i \leq d_i$ holds. Bob is a greedy man, he collects coins greedily — whenever he can collect coins at some integer time $x$, he collects the available red envelope with the maximum number of coins. If there are multiple envelopes with the same maximum number of coins, Bob would choose the one whose parameter $d$ is the largest. If there are still multiple choices, Bob will choose one from them randomly. However, Alice — his daughter — doesn't want her father to get too many coins. She could disturb Bob at no more than $m$ integer time moments. If Alice decides to disturb Bob at time $x$, he could not do anything at time $x$ and resumes his usual strategy at the time $x + 1$ (inclusive), which may lead to missing some red envelopes. Calculate the minimum number of coins Bob would get if Alice disturbs him optimally.

Input:

The first line contains three non-negative integers $n$, $m$ and $k$ ($1 \leq n \leq 10^5$, $0 \leq m \leq 200$, $1 \leq k \leq 10^5$), denoting the length of the timeline, the number of times Alice can disturb Bob and the total number of red envelopes, respectively. The following $k$ lines describe those $k$ red envelopes. The $i$-th line contains four positive integers $s_i$, $t_i$, $d_i$ and $w_i$ ($1 \leq s_i \leq t_i \leq d_i \leq n$, $1 \leq w_i \leq 10^9$) — the time segment when the $i$-th envelope is available, the time moment Bob can continue collecting after collecting the $i$-th envelope, and the number of coins in this envelope, respectively.

Output

Output one integer — the minimum number of coins Bob would get if Alice disturbs him optimally.

Sample Input:

5 0 2 1 3 4 5 2 5 5 8

Sample Output:

13 ## Sample Input:

10 1 6 1 1 2 4 2 2 6 2 3 3 3 3 4 4 4 5 5 5 5 7 6 6 6 9

Sample Output:

2 ## Sample Input:

12 2 6 1 5 5 4 4 6 6 2 3 8 8 3 2 9 9 5 6 10 10 7 8 12 12 9

Sample Output:

11 ### 题目链接

题解:

$k$个红包，每个可以在$l_i到r_i的整点选取，价值为w_i, 选取后直到d_i不能选红包$，你的策略是任意时刻选价值最高的，有多个则选$d_i$最大的，还有多个则随机（其实是选什么都一样），你可以被人打扰m次，一次打扰则在一个时刻不能选红包，求选择红包总价值的最小值

$O(n \ast m)$dp即可

AC代码:

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 1e5 + 10;

LL dp[N][220], sum[N];

int l, r, d, w, nxt, val, n, m, k;
int vis[N];
pair<int, int> tmp;
vector<pair<int, int>> t[N], s[N];
multiset<pair<int, int>> mp;

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= k; ++i) {
		scanf("%d%d%d%d", &l, &r, &d, &w);
		tmp.first = -w, tmp.second = -d;
		s[r].push_back(tmp);
		t[l].push_back(tmp);
	}
	memset(dp[n + 1], 0, sizeof(dp[n + 1]));
	for(int i = n; i; --i) {
		for(auto &it: s[i])
			mp.insert(it);
		if(!mp.empty()) {
			tmp = *mp.begin();
			nxt = -tmp.second + 1;
			val = -tmp.first;
		}
		else {
			nxt = i + 1;
			val = 0;
		}
		for(int j = 0; j <= m; ++j) {
			dp[i][j] = dp[nxt][j] + val;
			if(j)
				dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
		}
		for(auto &it: t[i]) {
			mp.erase(mp.find(it));
		}
	}
	printf("%lld\n", dp[1][m]);
	return 0;
}

F. Lunar New Year and a Recursive Sequence

Description:

Lunar New Year is approaching, and Bob received a gift from his friend recently — a recursive sequence! He loves this sequence very much and wants to play with it. Let $f_1, f_2, \ldots, f_i, \ldots$ be an infinite sequence of positive integers. Bob knows that for $i > k$, $f_i$ can be obtained by the following recursive equation: $f_i = \left(f_{i - 1} ^ {b_1} \cdot f_{i - 2} ^ {b_2} \cdot \cdots \cdot f_{i - k} ^ {b_k}\right) \bmod p,$ which in short is $f_i = \left(\prod_{j = 1}^{k} f_{i - j}^{b_j}\right) \bmod p,$ where $p = 998\,244\,353$ (a widely-used prime), $b_1, b_2, \ldots, b_k$ are known integer constants, and $x \bmod y$ denotes the remainder of $x$ divided by $y$. Bob lost the values of $f_1, f_2, \ldots, f_k$, which is extremely troublesome – these are the basis of the sequence! Luckily, Bob remembers the first $k - 1$ elements of the sequence: $f_1 = f_2 = \ldots = f_{k - 1} = 1$ and the $n$-th element: $f_n = m$. Please find any possible value of $f_k$. If no solution exists, just tell Bob that it is impossible to recover his favorite sequence, regardless of Bob's sadness.

Input:

The first line contains a positive integer $k$ ($1 \leq k \leq 100$), denoting the length of the sequence $b_1, b_2, \ldots, b_k$. The second line contains $k$ positive integers $b_1, b_2, \ldots, b_k$ ($1 \leq b_i < p$). The third line contains two positive integers $n$ and $m$ ($k < n \leq 10^9$, $1 \leq m < p$), which implies $f_n = m$.

Output

Output a possible value of $f_k$, where $f_k$ is a positive integer satisfying $1 \leq f_k < p$. If there are multiple answers, print any of them. If no such $f_k$ makes $f_n = m$, output $-1$ instead. It is easy to show that if there are some possible values of $f_k$, there must be at least one satisfying $1 \leq f_k < p$.

Sample Input:

3 2 3 5 4 16

Sample Output:

Sample Input:

5 4 7 1 5 6 7 14187219

Sample Output:

Sample Input:

8 2 3 5 6 1 7 9 10 23333 1

Sample Output:

Sample Input:

1 2 88888 66666

Sample Output:

-1

Sample Input:

3 998244352 998244352 998244352 4 2

Sample Output:

-1

Sample Input:

10 283 463 213 777 346 201 463 283 102 999 2333333 6263423

Sample Output:

382480067

题目链接

题解:

把原式看成$f_k$的幂次的形式，设$f_n=f_k^{h_n}$, 则$h_1=h_2=...=h_{k-1}=0, h_k=1$, $h_i = \sum_{j = 1}^k(h_{i-j} \ast b_j) \ mod \ \phi(p), (i > k时)$,用矩阵快速幂可以求解出$h_n$, 时间复杂度为$O(k^3log(n))$,

然后要求解$f_k^{h_n} = m \ mod \ p$, 这个叫高次剩余，告辞！，可以利用$p=998244353$的性质利用原根求解，

令$m = g ^ x$, 其中g为p的原根3, 利用$BSGS$算法可以$O(\sqrt plog(p))$算出x(用哈希表代替map可以去掉一个log),

设$f_k = g^y$, 则$g^{y \ast h_n} = g^x \ mod \ p, 则y \ast h_n=x \ mod \ \phi(p)$,利用$EXGCD$解出y

总复杂度$O(k^3log(n) + \sqrt plog(p))$

AC代码:

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mod = 998244353, N = 110;
int n, m, k;
int b[N];


struct Mat {
	LL a[N][N];
	Mat(bool flag = 0) {
		memset(a, 0, sizeof(a));
		if(flag)
			for(int i = 0; i < N; ++i)
				a[i][i] = 1;
	}
	LL* operator[](unsigned id) {
		return a[id];
	}
	Mat operator*(Mat &rhs) {
		Mat res;
		for(int i = 0; i < k; ++i) {
			for(int j = 0; j < k; ++j) {
				for(int p = 0; p < k; ++p) {
					res[i][j] = (res[i][j] + a[i][p] * rhs[p][j]) % (mod - 1);
				}
			}
		}
		return res;
	}
}base;

Mat Mat_qp(Mat a, LL n) {
	Mat res(1);
	while(n) {
		if(n & 1)
			res = res * a;
		a = a * a;
		n >>= 1;
	}
	return res;
}

LL qp(LL a, LL n, LL m = mod) {
	LL res = 1;
	while(n) {
		if(n & 1)
			res = res * a % m;
		a = a * a % m;
		n >>= 1;
	}
	return res;
}

LL BSGS(LL A, LL B, LL C) { //find minium x satisfy A ** x % C = B % C 
	map<LL, LL> mp;
	if(A % C == 0) return -1;
	LL m = ceil(sqrt(C)); //x = i * m - j, A ** (i * m - j) = B, A ** (i * m) = B * A ** j
	LL ans = B % C;
	for(int j = 0; j <= m; ++j) { //enum j
		mp[ans] = j;
		ans = ans * A % C;		
	}
	LL t = qp(A, m, C);
	ans = t;
	for(int i = 1; i <= m; ++i) { //enum i, find j
		if(mp.count(ans)) 
			return ((i * m - mp[ans]) % C + C) % C;
		ans = ans * t % mod;
	}
	return -1;
}

LL exgcd(LL a, LL b, LL &x, LL &y) {//x, y must be reference, ax + by = gcd(a, b)
    if(b == 0) {
    	x = 1, y = 0;
    	return a;
    }
    LL d = exgcd(b, a % b, x, y);
    LL t = x;
    x = y, y = t - (a / b) * y;
    return d; //d = gcd(a, b)
}

LL solve(LL t, LL p) {
	LL x, y;
	LL d = exgcd(t, mod - 1, x, y);
	if(p % d) return -1;
	x = ((x * p / d) % (mod - 1) + (mod - 1)) % (mod - 1);
	return qp(3, x, mod);
}

int main() {
	scanf("%d", &k);
	for(int i = 0; i < k; ++i) {
		scanf("%lld", &base[0][i]);
		base[i + 1][i] = 1;
	}
	scanf("%d%d", &n, &m);
	Mat jar = Mat_qp(base, n - k);
	printf("%lld\n", solve(jar[0][0], BSGS(3, m, mod)));
	return 0;
}