头像

灰人

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




离线:6天前


最近来访(129)
用户头像
_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.

思路分析

题目大意:对于一个给定的长度为 $n$的数列,是否能在任意的位置插入$1 - n$之间的数使得该数列所有长度为 $k$的子序列的和都相等。如果可以输出插入之后的长度 $m$($ 1<= m <= 10^4$)以及该序列。

考虑什么样的序列可以满足题意。假设k为4,序列前四个元素为a b c d,若要满足第二个长度为4的子数组和为(a + b + c + d),则第五个元素应为a,依次类推,我们可以发现题目要求的序列是一个长度为k的子数组循环组成的。

我们可以先统计给定序列中有多少不同的数字,如果不同的数字超过了k个,那么这个序列一定是不满足题意的;
如果不同的数字小于或等于k个,我们可以将所有的数字放在一个序列中,缺数的话将序列元素补成k个,然后将该序列循环输出n遍即可。这个解法等价于,对于原序列中的任何一个数,都在它周围插入k - 1个数补成已有序列。

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,n]$之间的元素和它们之后的元素是无法交换的;$[1,x]$之间的元素和它们之前的元素是无法交换的,如果两个区间有交集即 $[n - x + 1,x]$ 区间存在,那么这个区间内的元素是无法移动的,除此之外所有的元素都可以通过策略任意移动。

$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.

思路分析

题目大意:给定一个包含 $0$ 和 $1$ 的矩阵 $A$和全为 $0$的矩阵 $B$,提供一个操作:每次把 $B$ 中 $2×2$ 的子矩阵全部变成1,可以进行任意次操作,问是否能将 $B$ 变成 $A$。

做这个题又犯老毛病了,一开始的思路是先找不合法的矩阵,然后对于合法的矩阵根据0筛除不能进行操作的位置,将所有能操作的位置都操作一遍。但是在判断矩阵不合法时又开始枚举各种情况,枚举了7 8条最后还是WA。

正确思路应该是,先将能操作的地方全部对B进行操作,然后将A和B进行对比,如果一样则存在答案,否则为不合法方案。
这个查错的思路和 1592B. Hemose Shopping 有点相似。 先通过题目列出可能的正确答案,再将当前操作的对象与正确答案进行对比,有不相同的地方则NO。

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;
}


分享 Note

灰人
2个月前

如果一个数组是 non-decreasing 的,把它的每一个元素都变成一样的也许是一种思路。

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.

思路分析

题目大意: 对于一个给定数组 $a$,判断它是否存在这样一个子数组 $b$,$b$ 的最大值与最小值之差大于等于 $b$ 中元素的个数。

可以证明,如果一个数组 $b$ 为满足题目条件的数组,那么 $b$ 中至少存在连续的两个数差值大于等于2,下证:

设最大值下标为 $maxpos$ 最小值下标为 $minpos$,根据题目条件可知
(这里可以假设maxpos > minpos,如果实际情况为maxpos < minpos 只需要对正明式稍加改动,不影响证明的正确性。)
$ b[maxpos] - b[minpos] >= maxpos - minpos + 1$

我们将前式分解可得
$(b[maxpos] - b[maxpos - 1]) + … … (b[minpos + 1] - b[minpos])$

分解式中共有 $maxpos - (minpos + 1) + 1 = maxpos - minpos$ 项
由于 $maxpos - minpos$ > $maxpos - minpos + 1$,显然分解式中至少有一项大于等于2

综上,命题得证。
根据结论,我们只需要线性扫描一遍数组,判断是否存在相邻的两个数差值大于等于2即可。

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.

思路分析

题目大意: 对$2$ - $n+1$ 这n个数进行染色,每个数不能和它的质因子颜色相同

处理方式有点像 Codeforces Round #677 (Div. 3) D. Districts Connection
将多种状态根据题目条件映射到到少数状态中

筛一下1e5内的质数,将所有质数染成一个颜色 非质数染成另一个颜色即可。
注意特判n = 1和n = 2的情况

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.

思路分析

题目大意: 求一个字典序最小且不是给定字符串子串的字符串。
需要注意的是,根据样例我们可以推断此题的比较规则是长度相同的情况下比较字典序,长度不同的情况下长度越小串越小,与题目描述的比较规则有一点出入。

题目中给定的字符串长度不超过1000.
根据抽屉原理 我们可以得知本体的答案长度不会超过3,因为长度为3的字符串共有 $26^3$ = 17576个,而长度为1000的字符串中最多可以包含998个不同的长度为3的字符串

因此我们可以预处理出所有长度为1,2,3的字符串,然后与s进行匹配。第一个不包含在给定字符串中的即是答案。
代码写丑了 预处理可以放在主函数中

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.

思路分析

如果一个构造题,思维题被写的很麻烦 而且情况分支越想越多 那这个方法大概率是错的 最可能的原因是你的思路本来就是错的 或者就算思路是对的你也不能保证你一定考虑到了所有情况分支 这种题目 一定会有好写的写法 要从数学推导的角度去考虑

考虑将所有元素对m取模从而将a中的所有元素映射到$0$ - $m-1$ 的范围内,我们只需要处理连续两个数和等于m就可以了。

首先可以确定的是 所有模m等于0 的元素可以放到同一个子数组中。只要存在这样的元素我们就可以让res ++

对剩余元素的处理,首先考虑的是双指针从两端向中间扫,但是问题在于指针移动的决策不止被当前的元素所影响,需要考虑的因素过多,因此写了半天也没写对。

正确思路是对于$1$ - $m-1$中的每一个数$i$,考虑$m - i$的个数,当两者个数差一时可以组成一个满足条件的最长子数组。

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$?

思路分析

显然一直向右跳比先向左再向右可以让我们的坐标更快地变大。

假设我们一直跳,跳了 $k - 1$ 次,当前位置为 $pos$ ,再向右跳一次就会大于等于 $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$步:
由pos + i + (i + 1) 变成了 pos - 1 + (i + 1) = pos + i
根据定义i只能取到k - 1,因此我们可以花费一步向左跳 [2,k] 步。

分析到这里我们可以得出构造解法:
向右跳,一直跳到第一次大于或等于x,此时步数为k
如果当前位置等于x,答案为k
如果当前位置比x大[2,k]答案为k
如果当前位置比x大1 我们无法通过前面分析的方法向回跳,因此在跳k步之后再往回跳一步即可 答案为k+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].$

思路分析

首先需要记住一个结论:对于任意整数 $x$ ,都至少存在一个完全平方数 $s$满足 $x ≤ s ≤ 2x$。

知道这个结论后我们可以按照以下方式构造一个合法的序列:
$for(i = n - 1; i >= 0; – i)$,
$s = \sqrt{2x}^2$ , $pos = s - i$:$res[pos] = i,res[i] = pos;$

从 $pos$ 到 $i$ 之间的所有数都可以凑成 $s$,
例如 $res[pos + 1] = i - 1,res[i - 1] = pos + 1$;

接着我们以同样的方式从 $pos - 1$ 开始向前迭代直到填充满整个res序列。

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;
}