KYOCERA Programming Contest 2021(AtCoder Beginner Contest 200)D - Happy Birthday! 2

news/2024/12/22 15:15:20/

传送门

我们可以看出,B©序列的所有情况一共有2^n - 1种(就是每个数取或者不取),直接枚举肯定是不行。

再继续观察题目给出的条件,求和后要对200取模,也就是说取模后的结果有200种情况。我们所有序列的情况一共2^n - 1种,取极限情况,当前200种情况所得的结果都不相同时,第201种情况必定出现重复,因此只要情况总数超过200时必定有解。我们可以取n = 8(2 ^ 8-1 > 201)然后找到两种相同的情况即可。当n < 8 时,我们也可以采用同样的方法枚举。

不知道为什么开200的时候会越界,开300的时候就不会了。。。。。

#include<bits/stdc++.h>
using namespace std;typedef long long LL;         
typedef pair<int, int> P;const int maxn = 200 + 10;        
const int M_MAX = 10;
const int mod = 1e9 + 7;
const LL INF = 0x3f3f3f3f;    
const double eps = 1e-6;      int n;
int arr[maxn];
vector<int> ans[300];void out(vector<int> &t) {cout << t.size();for(auto i : t) {cout << " " << i;}cout << endl;
}void solve() {cin >> n;for(int i = 0; i < n; i++) cin >> arr[i];int cnt = min(n, 8);for(int i = 0; i < 1 << cnt; i++) {LL sum = 0;vector<int> s;for(int j = 0; j < cnt; j++) {if(1 << j & i) {s.emplace_back(j + 1);sum += arr[j];}}sum %= 200;if(!ans[sum].empty()) {cout << "YES\n";out(ans[sum]);out(s);return ;}else {ans[sum] = s;}}cout << "NO\n";
}int main() {ios::sync_with_stdio(false);//srand(time(NULL));    //更新种子solve();return 0;
}  

http://www.ppmy.cn/news/913626.html

相关文章

KYOCERA Programming Contest 2023(AtCoder Beginner Contest 305)(A、B、C、D、E、F)[施工中]

文章目录 A - Water Station(模拟)B - ABCDEFG&#xff08;模拟&#xff09;C - Snuke the Cookie Picker(模拟、暴力)D - Sleep Log&#xff08;二分&#xff0c;前缀&#xff09;E - Art Gallery on Graph&#xff08;dijkstra变种&#xff0c;BFS优先队列&#xff09;F - Du…

京瓷Kyocera Mita LS-C8026N 一体机驱动

京瓷Kyocera Mita LS-C8026N 一体机驱动是官方提供的一款一体机(打印、扫描)驱动&#xff0c;本站收集提供高速下载&#xff0c;用于解决一体机与电脑连接不了&#xff0c;无法正常使用的问题&#xff0c;本动适用于&#xff1a;Windows XP / Windows 7 / Windows 8 / Windows …

Kyocera6.2寸工业液晶屏TCG062HVLQAVNN-GN20

京瓷 (Kyocera) 推出的TCG062HVLQAVNN-GN20是一款采用a-Si TFT-LCD技术的6.2英寸液晶模组产品&#xff0c;它装配有WLED背光&#xff0c;含LED驱动器背光驱动&#xff0c;无触摸。 总结它的典型特征为: 白光LED背光&#xff0c;含LED驱动器&#xff0c;超宽屏&#xff0c;180度…

KYOCERA Programming Contest 2021(AtCoder Beginner Contest 200) E - Patisserie ABC 2

KYOCERA Programming Contest 2021&#xff08;AtCoder Beginner Contest 200&#xff09; E - Patisserie ABC 2 题意 将 n 3 n^3 n3个三元组 ( i , j , k ) , 1 ≤ i , j , k ≤ n (i,j,k),1\le i,j,k\le n (i,j,k),1≤i,j,k≤n进行排序&#xff0c;问第 k k k个三元组是什么…

KYOCERA Programming Contest 2021 (AtCoder Beginner Contest 200) A~E 题解

ABC200/KYOCERA2021 A~E [A - Century](https://atcoder.jp/contests/abc200/tasks/abc200_a)题目大意输入格式输出格式样例分析代码 [B - 200th ABC-200](https://atcoder.jp/contests/abc200/tasks/abc200_b)题目大意输入格式输出格式样例分析代码 [C - Ringos Favorite Numb…

KYOCERA Programming Contest 2021(AtCoder Beginner Contest 200)题解

文章目录 A - CenturyB - 200th ABC-200C - Ringos Favorite Numbers 2D - Happy Birthday! 2E - Patisserie ABC 2F - Minflip Summation KYOCERA Programming Contest 2021&#xff08;AtCoder Beginner Contest 200&#xff09; A - Century 简单的除以 200 200 200向上取…

KYOCERA Programming Contest 2022(AtCoder Beginner Contest 271)G.Access Counter(概率+矩阵快速幂优化dp)

题目 Takahashi布置了一个网页&#xff0c; 给定一个长为24的仅由A和T构成的字符串&#xff0c;表示每天整点能登进这个网页的概率 第i个字母如果是T&#xff0c;表示第i个整点的时候Takahashi有X(1<X<99)%的概率能登进去一次&#xff0c; 如果是A&#xff0c;表示第…

KYOCERA Programming Contest 2021(AtCoder Beginner Contest 200)E

首先考虑n^2的做法那就是 for(int i 1; i < 3; i){ for(int j 1; j < 3 * n; j){ for(int k 1; k < n; k){ dp[i][j k] dp[i - 1][j];我们从中可以看出 当 j 1的时候他对所有 j 1 ~ j n 那么 j 2 就对 j 2 ~ j n 1是有贡献的 所以我们只需求一个前缀和 即…