铁路建设网站多少,成都青羊区建设局网站,seo搜索引擎营销工具,建筑装饰公司做网站的作用KJY0047 - J1阶段测试题解
题目1#xff1a;SYAP0001. 闯关
解题思路#xff1a;
暴力思路#xff1a;每次碰到奇数都使用一次 f o r for for 循环将后续的数值 1 1 1, 时间复杂度 O ( n 2 ) O(n^2) O(n2) 优化思路#xff1a;可以用一个计数器 c n t cnt cnt 来存…KJY0047 - J1阶段测试题解
题目1SYAP0001. 闯关
解题思路
暴力思路每次碰到奇数都使用一次 f o r for for 循环将后续的数值 1 1 1, 时间复杂度 O ( n 2 ) O(n^2) O(n2) 优化思路可以用一个计数器 c n t cnt cnt 来存储后续数值需要增加多大如果碰到奇数则让计数器 1 1 1每次新读入一个数 x x x都让 x c n t x cnt xcnt 得到的值才是当前关卡真正的恐怖值不要忘记要开 l o n g l o n g longlong longlong。
代码实现
#includebits/stdc.h
using namespace std;
#define int long long
signed main(){int cnt 0; // 计数器int ans 0; // 恐怖值总和int n, m;cin n m;for(int i 1; i n; i ){int x;cin x;x cnt; // 真正的关卡恐怖值if(x % 2){ans x;cnt ;} else{ans x;}if(ans m){ // 闯关失败cout No endl;cout i endl;return 0; } }cout Yes endl;cout ans endl;return 0;
}题目2SYAP0023. 分割
解题思路
本题考的知识点是 map 的使用由于我们每个字段中的数值都要求唯一那么我们从左到右贪心的遍历数组如果当前的 x x x 在之前出现过则需要重新分段否则我们就尽可能让没出现的过的数放在当前段中。
代码实现
#includebits/stdc.h
using namespace std;
int main(){int n;cin n;mapint, int mp; // 用来存储当前段中数值出现次数int sum 0;for(int i 1; i n; i ){int x;cin x;if(mp[x] 1){ // 如果出现过则需要重新分段mp.clear(); // 清空 mapsum ; // 分段次数增加}mp[x] ;}cout sum endl;return 0;
}题目3P1247. brz的雪糕
解题思路
本道题是 前缀和 专题中做过的题为了测试同学们是否做过的题目真正的掌握了。我们可以刚开始预处理一个前缀和数组 s s s 如果 a [ i ] a [ i − 1 ] a[i] a[i - 1] a[i]a[i−1] 则 s [ i ] s [ i − 1 ] s[i] s[i - 1] s[i]s[i−1], 否则如果 a [ i ] ! a [ i − 1 ] a[i] ! a[i - 1] a[i]!a[i−1] 则 s [ i ] s [ i − 1 ] 1 s[i] s[i - 1] 1 s[i]s[i−1]1那么每次询问我们可以直接返回 s [ r ] − s [ l ] 1 s[r] - s[l] 1 s[r]−s[l]1 即可。
代码实现
#includebits/stdc.h
using namespace std;
const int N 1e5 10;
int a[N];
int s[N];
int main(){int n, k, q;cin n k q;for(int i 1; i n; i ){cin a[i]; s[i] s[i - 1] (a[i] ! a[i - 1]);}while(q --){int l, r;cin l r;if(s[r] - s[l] 1 k) cout Yes endl;else cout No endl; } return 0;
}题目4SYAP0030. 销毁easy
解题思路
因为我们要求 最多能剩下 多少 互不相同 的卡牌所以我们可以先统计出有多少张卡牌是没意义的易知 所有卡牌的总数 − 有多少种不同的卡牌 所有卡牌的总数 - 有多少种不同的卡牌 所有卡牌的总数−有多少种不同的卡牌 得到的值即为没有意义的卡牌数量。例如只有 3 种卡牌 2 3 5他们的数量分别是 1 6 8那么没有意义的卡牌数量即为 (1 - 1) (6 - 1) (8 - 1) 12 , 这 12 张卡牌是可以随意销毁的因为它 不会影响我们的最终答案 。又由于我们每次只会销毁 2 张卡牌所以如果我们 无意义的卡牌数量是奇数则意味这有意义的卡牌要损失 1 张否则有意义的卡牌无需损失
代码实现
#includebits/stdc.h
using namespace std;
const int N 1e6 10;
int sum[N];
int main(){int n;cin n;for(int i 1; i n; i ){int x;cin x;sum[x] ; // 统计卡牌数量} int ans 0; // 无意义的卡牌数量int res 0; // 统计卡牌的种类for(int i 1; i 1e6; i ){if(sum[i]){ans sum[i] - 1;res ;}}ans % 2;cout res - ans endl; // 如果是奇数则会 -1return 0;
}题目5SYAP0031. 销毁hard
解题思路 思路和上题差不多只不过需要存储最后保留的字典序最小的方案使用一个 v e c t o r vector vector 存储即可
代码实现
#includebits/stdc.h
using namespace std;
#define int long long
const int N 1e6 10;
int sum[N];
signed main(){int n, k;cin n k;vectorint v;for(int i 1; i n; i ){int x;cin x;sum[x] ;} int ans 0;for(int i 1; i 1e6; i ){if(sum[i]){ans sum[i] - 1;v.push_back(i); // 有多少种不同的数值放 vector 中}}ans % k;if(ans) ans k - ans; // 需要销毁多少有意义的卡牌if(ans v.size()){ // 如果销毁数量 不同数值个数则无解cout -1 endl;return 0;}sort(v.begin(), v.end()); // 排序按字典序从小到大cout v.size() - ans endl;for(int i 0; i v.size() - ans; i ){cout v[i] ;}cout endl;
}
