# Codeforces Round #615 (Div. 3)
標簽（空格分隔）： ACM
---
# D. MEX maximizing
## Description:
Recall that MEX of an array is a minimum non-negative integer that does not belong to the array. Examples:
? for the array $[0, 0, 1, 0, 2]$ MEX equals to $3$ because numbers $0, 1$ and $2$ are presented in the array and $3$ is the minimum non-negative integer not presented in the array;? for the array $[1, 2, 3, 4]$ MEX equals to $0$ because $0$ is the minimum non-negative integer not presented in the array;? for the array $[0, 1, 4, 3]$ MEX equals to $2$ because $2$ is the minimum non-negative integer not presented in the array. You are given an empty array $a=[]$ (in other words, a zero-length array). You are also given a positive integer $x$.
You are also given $q$ queries. The $j$-th query consists of one integer $y_j$ and means that you have to append one element $y_j$ to the array. The array length increases by $1$ after a query.
In one move, you can choose any index $i$ and set $a_i := a_i + x$ or $a_i := a_i - x$ (i.e. increase or decrease any element of the array by $x$). The only restriction is that $a_i$ cannot become negative. Since initially the array is empty, you can perform moves only after the first query.
You have to maximize the MEX (minimum excluded) of the array if you can perform any number of such operations (you can even perform the operation multiple times with one element).
You have to find the answer after each of $q$ queries (i.e. the $j$-th answer corresponds to the array of length $j$).
Operations are discarded before each query. I.e. the array $a$ after the $j$-th query equals to $[y_1, y_2, \dots, y_j]$.
## Input:
The first line of the input contains two integers $q, x$ ($1 \le q, x \le 4 \cdot 10^5$) — the number of queries and the value of $x$.
The next $q$ lines describe queries. The $j$-th query consists of one integer $y_j$ ($0 \le y_j \le 10^9$) and means that you have to append one element $y_j$ to the array.
## Output
Print the answer to the initial problem after each query — for the query $j$ print the maximum value of MEX after first $j$ queries. Note that queries are dependent (the array changes after each query) but operations are independent between queries.
## Sample Input:
7 3
0
1
2
2
0
0
10
## Sample Output:
1
2
3
3
4
4
7
## Sample Input:
4 3
1
2
1
2
## Sample Output:
0
0
0
0
####題解
本題看著比較復雜登舞，看起來比較像模擬題，其實是一道數(shù)學題萝究，仔細理解題意，可以看出驯妄，將序列中的每一個元素對x取模可以得到0-x-1的數(shù)（記為M序列）合砂，所以MEX取決于M序列的個數(shù)和多余出來的那部分數(shù)青扔，我們只需要對每次讀取的數(shù)字進行更新和維護，記錄此時M序列的個數(shù)和多出來的那部分數(shù)翩伪，此時M序列的個數(shù)應該為M序列中最少數(shù)量的那個元素的個數(shù)微猖，此時這個元素必定已經(jīng)用完，所以在新多出來的序列中這個元素必然缺少缘屹，所以這個元素就是多出來序列的MEX励两，更新ans=s.begin()->first * x+s.begin()->second,本題使用的set相關知識應該掌握。
代碼1：
```C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
? ? int q,x;
? ? scanf("%d %d",&q,&x);
? ? vector<int> v(x);
? ? //set<pair<int, int> > vals;
? ? set<pair<int, int> > s;
? ? for(int i=0;i<x;i++)
? ? {
? ? ? ? s.insert(make_pair(v[i],i));
? ? }
? ? for(int i=0;i<q;i++)
? ? {
? ? ? ? int cus;
? ? ? ? scanf("%d",&cus);
? ? ? ? cus%=x;
? ? ? ? s.erase(make_pair(v[cus], cus));
? ? ? ? v[cus]++;
? ? ? ? s.insert(make_pair(v[cus],cus));
? ? ? ? //cout << s.begin()->first * x + s.begin()->second << endl;
? ? ? ? printf("%d\n",s.begin()->first * x+s.begin()->second);
? ? }
? ? return 0;
}
```
代碼2：
```C++
#include <bits/stdc++.h>
using namespace std;
const int maxn=400005;
int cnt[maxn];
int main()
{
? ? int q,x;
? ? scanf("%d %d",&q,&x);
? ? int ans=0;
? ? int j=0;
? ? for(int i=0;i<q;i++)
? ? {
? ? ? ? int cur;
? ? ? ? scanf("%d",&cur);
? ? ? ? cnt[cur%x]++;
? ? ? ? while(true)
? ? ? ? {
? ? ? ? ? ? if(cnt[j]>0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? cnt[j]--;
? ? ? ? ? ? ? ? ans++;
? ? ? ? ? ? ? ? j=(j+1)%x;
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? ? ? break;
? ? ? ? }
? ? ? ? printf("%d\n",ans);
? ? }
? ? //cout << "Hello world!" << endl;
? ? return 0;
}
```
### [題目鏈接](https://codeforces.com/contest/1294/problem/D)
# E. Obtain a Permutation
## Description:
You are given a rectangular matrix of size $n \times m$ consisting of integers from $1$ to $2 \cdot 10^5$.
In one move, you can:
? choose any element of the matrix and change its value to any integer between $1$ and $n \cdot m$, inclusive;? take any column and shift it one cell up cyclically (see the example of such cyclic shift below). A cyclic shift is an operation such that you choose some $j$ ($1 \le j \le m$) and set $a_{1, j} := a_{2, j}, a_{2, j} := a_{3, j}, \dots, a_{n, j} := a_{1, j}$ simultaneously.
? Example of cyclic shift of the first column You want to perform the minimum number of moves to make this matrix look like this:
? In other words, the goal is to obtain the matrix, where $a_{1, 1} = 1, a_{1, 2} = 2, \dots, a_{1, m} = m, a_{2, 1} = m + 1, a_{2, 2} = m + 2, \dots, a_{n, m} = n \cdot m$ (i.e. $a_{i, j} = (i - 1) \cdot m + j$) with the minimum number of moves performed.
## Input:
The first line of the input contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5, n \cdot m \le 2 \cdot 10^5$) — the size of the matrix.
The next $n$ lines contain $m$ integers each. The number at the line $i$ and position $j$ is $a_{i, j}$ ($1 \le a_{i, j} \le 2 \cdot 10^5$).
## Output
Print one integer — the minimum number of moves required to obtain the matrix, where $a_{1, 1} = 1, a_{1, 2} = 2, \dots, a_{1, m} = m, a_{2, 1} = m + 1, a_{2, 2} = m + 2, \dots, a_{n, m} = n \cdot m$ ($a_{i, j} = (i - 1)m + j$).
## Sample Input:
3 3
3 2 1
1 2 3
4 5 6
## Sample Output:
6
## Sample Input:
4 3
1 2 3
4 5 6
7 8 9
10 11 12
## Sample Output:
0
## Sample Input:
3 4
1 6 3 4
5 10 7 8
9 2 11 12
## Sample Output:
2
### [題目鏈接](https://codeforces.com/contest/1294/problem/E)
###題解
首先將問題分解囊颅，要使整個矩陣滿足要求，我們使矩陣的每一列滿足要求即可傅瞻，下面求解每一列對應的最少步數(shù)踢代，我們需要保證結果的正確行所以每一列的所有元素都要考慮，以第一列為例子嗅骄，我們用cnt數(shù)組表示每個循環(huán)移位計算不用替換的元素個數(shù)胳挎，所以每進行一次移位我們需要的操作次數(shù)為n-cnt[i]+i，記為cur溺森，我們只需要找到每一列cur的最小值并把它累加到ans上就可以求解這個問題慕爬。
AC代碼:
```C++
#include <bits/stdc++.h>
using namespace std;
const int maxn=200001;
//int mp[maxn][maxn];
//int cnt[maxn];
int main()
{
? ? int n,m;
? ? scanf("%d %d",&n,&m);
? ? vector<vector<int> > mp(n, vector<int>(m));
? ? for(int i=0;i<n;i++)
? ? {
? ? ? ? for(int j=0;j<m;j++)
? ? ? ? {
? ? ? ? ? ? scanf("%d",&mp[i][j]);
? ? ? ? ? ? mp[i][j]--;
? ? ? ? }
? ? }
? ? long long ans=0;
? ? for(int j=0;j<m;j++)
? ? {
? ? ? ? vector<int> cnt(n);
? ? ? ? //memset(cnt,0,sizeof(cnt));
? ? ? ? for(int i=0;i<n;i++)
? ? ? ? {
? ? ? ? ? ? if(mp[i][j] % m == j)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? int pos = mp[i][j] / m;
? ? ? ? ? ? ? ? if(pos<n)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? cnt[(i-pos+n)%n]++;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? int cur = n-cnt[0];
? ? ? ? for(int i=1; i<n; i++)
? ? ? ? {
? ? ? ? ? ? cur = min(cur, n - cnt[i] + i);
? ? ? ? }
? ? ? ? ans+=cur;
? ? }
? ? printf("%lld\n",ans);
? ? //cout << "Hello world!" << endl;
? ? return 0;
}
```
