CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!) A ~ D
阅读原文时间:2022年03月26日阅读:1

A.

给定一个序列,对于任意1<=k<=n 都满足|ai−ak|+|ak−aj|=|ai−aj|,

找满足条件的i和j并输出

思路:

观察样例,发现输出的是最大值和最小值,那么猜答案是最大值和最小值,进行证明

若答案不是最大值和最小值,则一定存在一个k使得|ak-ap|大于|aj-ai| 一定不满足|ai−ak|+|ak−aj|=|ai−aj| 与命题矛盾****

所以记录最大值和最小值 输出即可。

代码:

#include
using namespace std;
#define x first
#define y second
#define endl '\n'
#define int long long
#define debug(x) cout << "*" << x << endl; const int P = 13131; #define ll long long const int mod = 1E6 + 7; const int INF = 0x3f, sINF = 0x3f3f3f3f; typedef unsigned long long ULL; typedef pair PII;
typedef pair PLL;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 3e5 + 10;;
int T;
const int UN = 1e9 + 10;

signed main()
{
cin>>T;
while(T--)
{
int n;
int maxa = 0, mina = UN;
cin>>n;
int ans1, ans2;
for(int i = 1; i <= n; i++) { int temp; cin>>temp;

        if(temp > maxa)  
        {  
            ans1 = i;  
            maxa = temp;  
        }

        if(temp < mina)  
        {  
            ans2 = i;  
            mina = temp;  
        }  
    }  
    if(n == 1) cout<<"1 1"<<endl;  
    else cout<<ans2<<" "<<ans1<<endl;

}  

}

B

给定一个序列,每次去除任意一个元素,并且将其他剩余元素都减去这个元素的值,给定一个k,能否让最后剩下的那个数为k

思路:

推公式,模拟一下a1,a2 和 a1,a2,a3情况,并且以总和的角度来看,发现所有的答案都只与两个元素之间的差的绝对值有关

a1,a2,a3情况: 总和为a1+a2+a3

假如去除的是a2 那么总和就为(a1 - a2) + (a3 - a2),剩两个元素的时候求得就是他俩的差的绝对值了,那么就是|a1 - a2 - a3 + a2| = |a1 - a3|

去除的是其他同理,发现多个元素的时候都可以消成这种形式。那么答案就是在任意两个元素的差的绝对值之中,哈希表判断是否存在即可。

代码:

#include
using namespace std;
#define x first
#define y second
#define endl '\n'
#define int long long
#define debug(x) cout << "*" << x << endl; const int P = 13131; #define ll long long const int mod = 1E6 + 7; const int INF = 0x3f, sINF = 0x3f3f3f3f; typedef unsigned long long ULL; typedef pair PII;
typedef pair PLL;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e5 + 10;;
int T;
const int UN = 1e9 + 10;
int q[N];

signed main()
{
cin>>T;
while(T--)
{
map s;
int n, k;
cin>>n>>k;
for(int i = 0; i < n; i++) { cin>>q[i];
s[q[i]] = true; //出现过这个
}

    bool isk = false;  
    for(int i = 0; i < n; i++)  
        if(s\[q\[i\] - k\] || s\[q\[i\] + k\])  
        {  
            isk = true;  
            break;  
        }

    if(isk) puts("YES");  
    else puts("NO");  
}  

}

C

给定一个序列,可以选择任意k>=2 对里面所有元素模k 有没有可能让所有元素相等。

思路:仔细想想即可发现,只要从大到小模,一定可以把所有元素模为0或者1,那么问题仅存在于0,1之间。

1怎么也到不了0 ,所以一旦0,1都出现,就一定NO。如果没0,只有1,那所有元素必须化为1,但对于p %= p-1,如果存在另一个p-1的元素,那么一定会出现0

所以此时不能存在差值为1的元素对。

其他所有情况都输出YES,只要按照从大到小模

代码:

#include
using namespace std;
#define x first
#define y second
#define endl '\n'
#define int long long
#define debug(x) cout << "*" << x << endl; const int P = 13131; #define ll long long const int mod = 1E6 + 7; const int INF = 0x3f, sINF = 0x3f3f3f3f; typedef unsigned long long ULL; typedef pair PII;
typedef pair PLL;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 1e5 + 10;;
int T;
const int UN = 1e9 + 10;
int q[N];

signed main()
{
cin>>T;
while(T--)
{
int n;
cin>>n;
for(int i = 0; i < n; i++) cin>>q[i];
sort(q, q + n);
bool find0 = false, find1 = false;
int p = 0;
while(q[p] <= 1 && p < n)
{
if(q[p] == 0) find0 = true;
if(q[p] == 1) find1 = true;
p++;
}

    if(find0 && find1)  
    {  
        puts("NO");  
        continue;  
    }

    if(!find0 && find1)  
    {  
        bool flag = false;  
        for(int i = 0; i < n - 1; i++)  
            if(q\[i + 1\] - q\[i\] == 1)  
            {  
                flag = true;  
                break;  
            }  
        if(!flag) puts("YES");  
        else puts("NO");

        continue;  
    }

    puts("YES"); 

}  

}

D

给定一个数,如果这个数可以被k个能够被模k后互不相等的数相加而得到,那么这个数称为k-good数,对于这个n,输出任意一个k即可,没有则为-1

思路:(可以先打表找规律

条件转化一下,很容易就能得到条件是 (n - sum(0, 1, …, k - 1)) % k == 0;

然后观察奇数,发现2-good可以作用于任意奇数,所以奇数全部输出2

根据上述条件来判断偶数,(n - (k - 1) * k / 2 <求和公式>) % k == 0

如果k是n的因子,并且求和项为整数且小于n,那么一定能输出,观察(k - 1) * k / 2项,发现k要么是奇数,要么是2,这两种情况能让这项为整。

又因为枚举的是偶数,所以我们只需要找到2^p * 最大奇因子 = n即可

2^p * 最大奇因子 = n

先判断临界情况 前两者相等时,一定有n - 求和 = 0,此时n = 2^(2*p) 一定不能输出,此时输出-1,(意思是,n是2^a就输出-1就行)

其他情况,一定一个大于sqrt(n), 一个小于sqrt(n), 小于的数的(n - (k - 1) * k / 2 <求和公式>)一定为正,大于的一定为负****

那么输出两者的最小值就行。

代码:

#include
using namespace std;
#define x first
#define y second
#define endl '\n'
#define int long long
#define debug(x) cout << "*" << x << endl; const int P = 13131; #define ll long long const int mod = 1E6 + 7; const int INF = 0x3f, sINF = 0x3f3f3f3f; typedef unsigned long long ULL; typedef pair PII;
typedef pair PLL;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 1e5 + 10;;
int T;
const int UN = 1e9 + 10;
int q[N];

signed main()
{
cin>>T;
while(T--)
{
ll n;
cin>>n;
ll rem = n;
if(n % 2 == 1) cout<<"2"<<endl;
else {
ll k = 1;
while(n % 2 == 0)
{
n /= 2;
k *= 2;
}
if(n == 1) cout<<"-1"<<endl;
else
{ //此时剩下个奇数
k *= 2;
cout<<min(k, n)<<endl;

        }  
    }

}  

}