1263-C Everyone is a Winner! (整除分块) 骑猪看日落 2021-07-17 02:45 341阅读 0赞 [题目][Link 1] 老实说一开始并不知道这题是整除分块,就打表找规律做出来的。想着当一个数15 先除以15/1 = 15 15 /2=7 15/3=5 15/4=3 15/5=3 15/6=2 15/7=2 15/8=2…可以知道除到前面一定只有一个值,到了后面出现出现重复的后从3开始2 1 都会存在且重复。所以把从重复的数比其小的取完,再把前面分散的大的也取完就可以,因为有剪枝不会T掉。 最开始的代码: #include<iostream> #include<string> #include<map> #include<algorithm> #include<stack>; #include<memory.h> #include<cmath> #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const int Max = 1e6 + 5; int lst[Max]; int b[111]; int main() { int t;cin >> t; while (t--) { stack<int> sta; memset(lst, 0, sizeof(lst)); lst[0] = 0; int n;cin >> n; int sum = 1, k=0, f=0; for (int i = 1;i <= n;i++) { sta.push(n / i);//k = i;f = n / i; if (n / i == n / (i + 1)) { k = i;f = n / i; sta.pop(); break; } } sum = k + f; for (int i = 0;i <= f;i++)lst[i] = i; while (sta.size() >= 1) { lst[++f] = sta.top(); sta.pop(); } if (n == 1) { cout << 2<<endl << "0 1" << endl; } else if (n == 2)cout <<3<<endl <<"0 1 2" << endl; else { cout << sum << endl; for (int i = 0;i <= f;i++) { cout << lst[i] << " "; } cout << endl; } } } 整除分块 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]Code #include<iostream> using namespace std; typedef long long ll; const int Max = 1e6 + 5; int lst[Max]; int main() { int t;cin >> t; while (t--) { int n;cin >> n;int d = 0; for (int l = 1, r;l <= n;l = r + 1) { int k = n / l;lst[++d] = k; r = n / k; } lst[++d] = 0;cout << d << endl; for (int i = d;i >= 1;i--)cout << lst[i] << " "; cout << endl; } } [Link 1]: https://codeforces.ml/contest/1263/problem/C [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]: /images/20210716/4511efe8f29749b192f02a22c53da16d.png
还没有评论,来说两句吧...