1263-C Everyone is a Winner! （整除分块）

骑猪看日落 2021-07-17 02:45 382阅读 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