$Stay$ $hungry$ $Stay$ $foolish$

6832

_Alang

zhangas2

Kirito_

Noir

ffffffffffffffffffffffffffffff
Ashoka
wzc1998
wwwzz

xYang_a0a1
binaryfinding

zhangxc

1个月前

### 题目描述

Phoenix loves beautiful arrays. An array is beautiful if all its subarrays of length $k$ have the same sum. A subarray of an array is any sequence of consecutive elements.

Phoenix currently has an array $a$ of length $n$. He wants to insert some number of integers, possibly $zero$, into his array such that it becomes beautiful. The inserted integers must be between $1$ and $n$ inclusive. Integers may be inserted anywhere (even before the first or after the last element), and he is not trying to minimize the number of inserted integers.

### C++ Code

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 110;

#define endl "\n"

void solve()
{
int n,k,a[N];
cin >> n >> k;
set<int> s;

for(int i = 1; i <= n ; ++i)
{
cin >> a[i];
s.insert(a[i]);
}

if(s.size() > k)cout <<"-1"<<endl;
else
{
int idx = 1;
while(s.size() < k)s.insert(idx ++);
cout << n*k <<endl;
for(int i = 1; i <= n ; ++i)
{
for(int x:s)cout << x<<" ";
}
cout <<endl;
}
}

int main()
{

int t ; cin >>t;
while(t -- )
{
solve();
}
return 0;
}



2个月前

### 题目描述

Hemose has an array of $n$ integers. He wants Samez to sort the array in the non-decreasing order. Since it would be a too easy problem for Samez, Hemose allows Samez to use only the following operation:

Choose indices $i$ and $j$ such that $1≤i,j≤n$, and $|i−j|≥x$. Then, swap elements $a_i$ and $a_j$.

Can you tell Samez if there’s a way to sort the array in the non-decreasing order by using the operation written above some finite number of times (possibly $0$)?

### 思路分析

$x < n - x + 1 <=> 2x - 1 < n <=> n >= 2x$，在这个条件下区间不存在，一定有解，否则我们可以先将原序列排序，然后将对应区间进行对比，如果有不同元素则误解，否则有解。

### C++ Code

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

const int N = 1e5+10;

typedef long long LL;

void solve()
{
int n,x;
int a[N],b[N];
cin >> n >> x;
for(int i = 1; i <= n; ++i)
{
cin >> a[i];
b[i] = a[i];
}
if(n >=  2 * x)
{
cout <<"YES" << endl;
return;
}
sort(b + 1, b + 1 + n);
for(int i = n - x + 1; i <= x; ++i)
{
if(a[i] != b[i])
{
cout << "NO" << endl;
return;
}
}
cout <<"YES" << endl;
}
int main()
{
int t;
cin >> t;
while(t -- )
{
solve();
}
return 0;
}


2个月前

### 题目描述

You are given two matrices $A$ and $B$. Each matrix contains exactly $n$ rows and $m$ columns. Each element of $A$ is either $0$ or $1$; each element of $B$ is initially $0$.

You may perform some operations with matrix $B$. During each operation, you choose any submatrix of $B$ having size $2×2$, and replace every element in the chosen submatrix with $1$. In other words, you choose two integers $x$ and $y$ such that $1≤x<n$ and $1≤y<m$, and then set $B_{x,y}, B_{x,y+1}, B_{x+1,y} and B_{x+1,y+1}$ to $1$.

Your goal is to make matrix $B$ equal to matrix $A$. Two matrices $A$ and $B$ are equal if and only if every element of matrix $A$ is equal to the corresponding element of matrix $B$.

Is it possible to make these matrices equal? If it is, you have to come up with a sequence of operations that makes $B$ equal to $A$. Note that you don’t have to minimize the number of operations.

### C++ Code

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

const int N = 60;

typedef long long LL;

void solve()
{
int n,m,cnt = 0;
vector<pair<int,int> >res;
int a[N][N],b[N][N];
memset(a,0,sizeof a);
cin >> n >> m;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
cin >> a[i][j];
}
}

for(int i = 1; i <= n ; ++i)
{
for(int j = 1; j <= m ; ++j)
{
if(a[i][j] && a[i + 1][j] && a[i][j + 1] && a[i + 1][j + 1])
{
a[i][j] = a[i + 1][j] = a[i][j + 1] = a[i + 1][j + 1] = 2;
res.push_back({i,j});
}
}
}

for(int i = 1; i <= n ;++i)
{
for(int j = 1; j <= m ; ++j)
{
if(a[i][j] == 1)
{
cout <<"-1" <<endl;
return;
}
}
}

cout << res.size() << endl;
for(auto [k,v]: res)cout << k <<" "<< v <<endl;
}
int main()
{
//int t;cin >> t;
//while(t -- )
//{
solve();
//}
return 0;
}


2个月前

Codeforces Round #772 (Div. 2) C. Differential Sorting

2个月前

### 题目描述

For an array $a$ of integers let’s denote its maximal element as $max(a)$, and minimal as $min(a)$. We will call an array a of $k$ integers interesting if $max(a)−min(a)≥k$. For example, array $[1,3,4,3]$ isn’t interesting as $max(a)−min(a)=4−1=3<4$ while array $[7,3,0,4,3]$ is as $max(a)−min(a)=7−0=7≥5$.

You are given an array $a$ of $n$ integers. Find some interesting nonempty subarray of $a$, or tell that it doesn’t exist.

An array $b$ is a subarray of an array $a$ if $b$ can be obtained from a by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

### 思路分析

（这里可以假设maxpos > minpos，如果实际情况为maxpos < minpos 只需要对正明式稍加改动，不影响证明的正确性。）
$b[maxpos] - b[minpos] >= maxpos - minpos + 1$

$(b[maxpos] - b[maxpos - 1]) + … … (b[minpos + 1] - b[minpos])$

### C++ Code

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

const int N = 2e5+10;

typedef long long LL;

void solve()
{
int n,a[N];
cin >> n;
for(int i = 1; i <= n; ++i)cin >> a[i];
for(int i = 2; i <= n ; ++i)
{
if(abs(a[i] - a[i - 1]) >= 2)
{
cout << "YES" <<endl;
cout << i - 1<<" " << i << endl;
return;
}
}
cout << "NO" <<endl;
}
int main()
{
int t;cin >> t;
while(t -- )
{
solve();
}
return 0;
}



2个月前

### 题目描述

Sherlock has a new girlfriend (so unlike him!). Valentine’s day is coming and he wants to gift her some jewelry.

He bought n pieces of jewelry. The i-th piece has price equal to i + 1, that is, the prices of the jewelry are $2, 3, 4, … n + 1.$

Watson gave Sherlock a challenge to color these jewelry pieces such that two pieces don’t have the same color if the price of one piece is a prime divisor of the price of the other piece. Also, Watson asked him to minimize the number of different colors used.

### C++ Code

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

const int N = 1e5+10;

bool st[N];
vector<int> prime;
void init()
{
for(int i = 2; i <= N ; ++i)
{
if(!st[i])prime.push_back(i);
for(int j = 0; prime[j] <= N/i ; ++j)
{
st[prime[j]* i] = true;
if(i % prime[j] == 0)break;
}
}
}

void solve()
{
int n;cin >> n;
cout << (n <= 2?"1":"2") <<endl;
for(int i = 2; i <= n + 1; ++i)
{
if(!st[i])cout << "1 ";
else cout << "2 ";
}
cout << endl;
}
int main()
{
init();
solve();
return 0;
}


2个月前

### 题目描述

You are given a string of n lowercase Latin letters, the word that Fischl just spoke. You think that the $MEX$ of this string may help you find the meaning behind this message. The $MEX$ of the string is defined as the shortest string that doesn’t appear as a contiguous substring in the input. If multiple strings exist, the lexicographically smallest one is considered the $MEX$. Note that the empty substring does NOT count as a valid $MEX$.

A string a is lexicographically smaller than a string b if and only if one of the following holds:

a is a prefix of b, but a≠b;
in the first position where a and b differ, the string a has a letter that appears earlier in the alphabet than the corresponding letter in b.

Find out what the $MEX$ of the string is!

### 输入

Each test contains multiple test cases. The first line contains the number of test cases $t (1≤t≤1000)$. Description of the test cases follows.

The first line of each test case contains an integer $n (1≤n≤1000)$ — the length of the word. The second line for each test case contains a single string of n lowercase Latin letters.

The sum of n over all test cases will not exceed 1000.

### C++ Code

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

const int N = 1010;
void solve()
{
int n; string s;
cin >> n >> s;
// 枚举所有长度小于等于 3的串 枚举找到字典序最小的串
// 预处理所有串
vector<string> l1,l2,l3;
for(int i = 0; i < 26; ++i)
{
string a;a.push_back('a' + i); l1.push_back(a);
for(int j = 0; j < 26; ++j)
{
string b; b.push_back('a' + i); b.push_back('a' + j);l2.push_back(b);
for(int k = 0; k < 26; ++k)
{
string c;c.push_back('a' + i); c.push_back('a' + j);c.push_back('a' + k); l3.push_back(c);
}
}
}

vector<string> v;
for(int i = 0; i < s.length(); ++i)
{
v.push_back(s.substr(i,1));
if(i + 1 < s.length())v.push_back(s.substr(i,2));
if(i + 2 < s.length())v.push_back(s.substr(i,3));
}

for(int i = 0; i < l1.size(); ++i)
{
if(!count(v.begin(),v.end(),l1[i]))
{
cout << l1[i] << endl;
return;
}
}
for(int i = 0; i < l2.size(); ++i)
{
if(!count(v.begin(),v.end(),l2[i]))
{
cout << l2[i] << endl;
return;
}
}
for(int i = 0; i < l3.size(); ++i)
{
if(!count(v.begin(),v.end(),l3[i]))
{
cout << l3[i] << endl;
return;
}
}

}
int main()
{
int t;
cin >> t;
while(t -- )
{
solve();
}
return 0;
}


2个月前

### 题目描述

You are given an array $a_1,a_2,…,a_n$ consisting of n positive integers and $a$ positive integer $m$.

You should divide elements of this array into some arrays. You can order the elements in the new arrays as you want.

Let’s call an array $m-divisible$ if for each two adjacent numbers in the array (two numbers on the positions $i$ and $i+1$ are called adjacent for each i) their sum is divisible by m. An array of one element is m-divisible.

Find the smallest number of m-divisible arrays that $a_1,a_2,…,a_n$ is possible to divide into.

### C++ Code

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

const int N = 1e5+10;

void solve()
{
int n,m,res = 0,cnt[N];
cin >> n >> m;
vector<int> a;
memset(cnt,0,sizeof cnt);
for(int i = 1; i <= n ; ++i)
{
int x;cin >> x;
if(x % m)
{
a.push_back(x % m);
cnt[x % m] ++ ;
}
}
if(a.size() < n)res ++ ;

for(int i = 1; i < m; ++i)
{
if(!cnt[i])continue;
if(cnt[i] < cnt[m - i])
{
res += cnt[m - i] - cnt[i];
}
else if(cnt[i] > cnt[m - i])
{
res += cnt[i] - cnt[m - i];
}
else
{
res ++;
}
cnt[i] = cnt[m - i] = 0;
}
cout << res << endl;
}
int main()
{
int t;
cin >> t;
while(t -- )
{
solve();
}
return 0;
}


2个月前

### 题目描述

You are standing on the $OX-axis$ at point $0$ and you want to move to an integer point $x>0$.

You can make several jumps. Suppose you’re currently at point $y$ ($y$ may be negative) and jump for the $k-th$ time. You can:

either jump to the point $y+k$
or jump to the point $y−1$.
What is the minimum number of jumps you need to reach the point $x$?

### 思路分析

1. pos + (k + 1) = x，那么再跳一步刚好到x，那再向右跳一步得了。
2. pos + (k + 1) > x, 由于 1<= x - pos <= k, 因此1 <= pos + (k + 1) - x <= k,即我们再跳一次，向右跳k + 1的距离后我们超出x的距离在1到k之间。那么怎样向回走这个距离跳跃的次数最少呢？观察题目可以发现，我们在第i步选择向左跳1等价于向回跳了 $i + 1$步:

### C++ Code

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e6+5;

int s[N];

void solve()
{
int x;cin >> x;
int l = 1, r = 1450;
while(l < r)
{
int mid = l + r>> 1;
if(s[mid] < x)l = mid + 1;
else r = mid;
}
if(s[l] == x + 1)l++;
cout<< l << endl;
}

int main()
{

for(int i = 1; i <= 1450; ++i)
{
s[i] = s[i - 1] + i;
}
int t;cin >> t;
while(t -- )
{
solve();
}
return 0;
}



2个月前

### 题目描述

A $0-$indexed array $a$ of size $n$ is called good if for all valid indices $i (0≤i≤n−1)$, $a_i+i$ is a perfect square†.

Given an integer $n$. Find a permutation‡ $p$ of $[0,1,2,…,n−1]$ that is good or determine that no such permutation exists.

† An integer $x$ is said to be a perfect square if there exists an integer $y$ such that $x=y_2$.

‡ An array $b$ is a permutation of an array $a$ if $b$ consists of the elements of $a$ in arbitrary order. For example, $[4,2,3,4]$ is a permutation of $[3,2,4,4]$ while $[1,2,2]$ is not a permutation of $[1,2,3].$

### 思路分析

$for(i = n - 1; i >= 0; – i)$,
$s = \sqrt{2x}^2$ , $pos = s - i$：$res[pos] = i,res[i] = pos;$

### C++ Code

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

const int N = 101010;
int num[N];

void recurse(int r)
{
if (r < 0) { return; }
int tmp = sqrt(2 * r);
tmp *= tmp;
int l = tmp - r;
recurse(l - 1);
for (; l <= r; l++, r--)
{
num[l] = r;
num[r] = l;
}
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);

int cse;
cin >> cse;
while (cse--)
{
int n;
cin >> n;
recurse(n - 1);
for (int i = 0; i < n; i++)
{
cout << num[i] << " ";
}
cout << endl;
}

return 0;
}