CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!) A ~ D

A.

給定一個序列，對于任意1<=k<=n 都滿足|ai?ak|+|ak?aj|=|ai?aj|,

找滿足條件的i和j并輸出

思路：

觀察樣例，發現輸出的是最大值和最小值，那么猜答案是最大值和最小值，進行證明

若答案不是最大值和最小值，則一定存在一個k使得|ak-ap|大于|aj-ai| 一定不滿足|ai?ak|+|ak?aj|=|ai?aj| 與命題矛盾

所以記錄最大值和最小值 輸出即可，

代碼：

#include <bits/stdc++.h>
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<int, int> PII;
typedef pair<long long, long long> 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 <bits/stdc++.h>
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<int, int> PII;
typedef pair<long long, long long> 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<int, bool> 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 <bits/stdc++.h>
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<int, int> PII;
typedef pair<long long, long long> 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 <bits/stdc++.h>
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<int, int> PII;
typedef pair<long long, long long> 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;
                
            }
        }
        
    }
}

標籤：C++

上一篇：P1030

下一篇：字串