锐客网

  1. 首页 > it技术 > >

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

RatedPrizes!)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 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"<


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"<



CodeTON|CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!) A ~ D
文章图片

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

    推荐阅读


      上一篇：C|C语言程序设计第二版学习笔记

      下一篇：在 Android TV 上构建优秀的播放体验｜中文字幕视频