A:一组长度为n 的排列,问交换多少次,能让前m个数变成[1,m]中的数
输出前 m 个数中有多少个比 m 大的就可以了
//-------------------------代码---------------------------- //#define int ll const int N = 1e5+10; int n,m; void solve() { cin>>n>>m; int ans = 0; set<int> q; fo(i,1,n) { int x;cin>>x; if(i <= m) { if(x > m) { ans ++ ; } } } cout<<ans<<endl; } void main_init() {} signed main(){ AC();clapping();TLE; cout<<fixed<<setprecision(12); main_init(); // while(cin>>n,n) // while(cin>>n>>m,n,m) int t;cin>>t;while(t -- ) solve(); // {solve(); } return 0; } /*样例区 */ //------------------------------------------------------------
B:一组长度为n的数,让所有数的位置和值的lcm之和最大
位置大的和值大的lcm如果不是本身一般就是最大的。
知识:x和x+1互质。所以只要 将n 个数两两互换就可以了
需要注意,如果有奇数个数,第一个数只能是1,偶数个数,第一个数只能是2
//-------------------------代码---------------------------- //#define int ll const int N = 1e5+10; int n,m; int a[N]; void solve() { cin>>n; for(int i = n;i>=1;i-=2) { a[i] = i - 1;a[i-1] = i; } if(n % 2 == 1) a[1] = 1; else a[1] = 2; fo(i,1,n) cout<<a[i]<<' ';cout<<endl; } void main_init() {} signed main(){ AC();clapping();TLE; cout<<fixed<<setprecision(12); main_init(); int t;cin>>t;while(t -- ) solve(); return 0; } /*样例区 */ //------------------------------------------------------------
C:n个数,问删除多少种数,可以使序列递增
从前往后遍历,如果当前数出现两次以上,并且不相邻,就要删掉所有数的种数
如果当前数比后面的数大,也要删掉所有数的种数
取一个删去种数的最大值就好了
前k 个数有多少种数怎么算?将所有数放到set里会自动去重,算set的大小就可以了
//-------------------------代码---------------------------- //#define int ll const int N = 1e5+10; int n,m; int a[N]; void solve() { cin>>n; int mx = 0; map<int,int> mp; set<int> q; fo(i,1,n) { cin>>a[i]; mp[a[i]] ++ ; if(i >= 2 && mp[a[i]] >= 2 && a[i-1] != a[i]) mx = max(int(q.size()),mx); if(i >= 2 && a[i] < a[i-1]) mx = max((int)q.size(),mx); q.insert(a[i]); } cout<<mx<<endl; } void main_init() {} signed main(){ AC();clapping();TLE; cout<<fixed<<setprecision(12); main_init(); // while(cin>>n,n) // while(cin>>n>>m,n,m) int t;cin>>t;while(t -- ) solve(); // {solve(); } return 0; } /*样例区 */ //------------------------------------------------------------
E1:(easy版) lcm的性质:必定是最大的数的倍数,数据范围一眼做法
题意:多组询问。lcm(i,j,k) >= i + j + k,问l 到 r 之间有多少满足条件的。l ,r <= 2e5。t <= 10
有一个性质:l 和 r 都是 1e5级别的,搜索三元组爆搜 要 n ^3,稍微优化:n^2 很难到 nlogn或者 n根号n。这里一眼可以确定要筛出某些数,在筛出来的数里搜了。
[l,r] 区间内三元组的数目是 组合数Cn3,就等于 len * (len - 1) * (len - 2) / 6
对于lcm(i,j,k) >= i + j + k,并不好直接判断,将大于等于号改成小于号:lcm(i,j,k) < i + j + k 。然后从最共的三元组数量找出满足条件的三元组数量即可
假设i,j,k中最大的数是 k ,那 lcm = 2 * k 或者 k 才满足条件 :比i + j + k 小。如果是 3k 的话 肯定要比 i + j + k 大
如果 lcm == k 。那肯定满足条件,三元组总数 - 1
如果 lcm == 2 * k 。那肯定是 k % i != 0 && k % j != 0。如果 满足 2 * k < i + j + k 也满足条件,三元组总数 - 1
只要枚举 所有 的2 * k ,并且找出它的因子 i ,j ,剪枝即可
ps:
1.lcm == 2 * k,如果 第二大的数 比 最大的数 的一半还小,那肯定不满足条件,可以减少对第一个数的搜索
2.找出每个数的因子是 o(n根号n)
//-------------------------代码---------------------------- //#define int ll const int N = 4e5+10; int n,m; V<int> g[N]; void solve() { // cin>>n>>m; int l,r;cin>>l>>r; int len = r - l + 1;; ll res = 1ll * len * (len - 1) * (len - 2) / 6; for(int i = l + 2;i<=r;i++) { V<int> v; for(auto x:g[2*i]) { if(x < l) continue; if(i % x && x * 2 <= i) continue;//如果不是 i 的因子,说明它是 2 * i 的因子 ,要满足 lcm(i,j,k) < i + j + k 那它的大小至少要是 i 的一半, if(x >= i) break; for(auto y : g[2*i]) { if(y < l) continue; if(y >= x) break; if(i % x || i % y ) res -= 2 * i < x + y + i;//如果lcm = 2 * k,就要判断 else res -- ; //lcm = k,直接减 } } } } void main_init() { fo(i,1,200000) { for(int j = i;j<=400000;j+=i) { g[j].pb(i); } } } signed main(){ AC();clapping();TLE; cout<<fixed<<setprecision(12); main_init(); // while(cin>>n,n) // while(cin>>n>>m,n,m) int t;cin>>t;while(t -- ) solve(); // {solve(); } return 0; } /*样例区 */ //------------------------------------------------------------
E2:hard版(t <= 1e5)树状数组+离线算法
我们把所有的循环 l 和 r 以及它是第几个询问,装进结构体
枚举[1,i] 以 r 为关键词,所有的 l 都是已经被计算过的
当枚举到当前询问的 r 的时候,l 就是一个特征值,不同的l 答案不一样
所以我们把所有的 i j k 的权值放入到最小的数 i 里,
ans[id] -= sum - query( l - 1)
//-------------------------代码---------------------------- #define int ll const int N = 4e5+10; int n,m; V<int> v[N]; V<pii> q[N]; int tr[N]; void add(int x,int v) { for(int i = x;i<N;i+=lowbit(i)) tr[i] += v; } int ans[N]; ll qq(int x) { ll res = 0;for(int i = x;i;i-=lowbit(i)) res += tr[i];return res; } void solve() { // cin>>n>>m; int t;cin>>t;fo(i,1,t) { int l,r;cin>>l>>r; q[r].pb({l,i});int len = r - l + 1; ans[i] = len * (len - 1) * (len - 2) / 6 ; } int sum = 0; for(int i = 1;i<=200000;i++) { for(auto x:v[i * 2]) { if(x >= i) break; if((i % x) && x * 2 <= i) continue; for(int y:v[i * 2]) { if(y >= x) break; if(i % x || i % y) { if(x + y + i > 2 * i) { sum ++ ; add(y,1); } } else { sum ++ ;add(y,1); } } } for(auto it : q[i]) { int l = it.first,id = it.second; ans[id] -= sum - qq(l-1); } } fo(i,1,t) { cout<<ans[i]<<'\n'; } } void main_init() { for(int i = 1;i<=2e5;i++) { for(int j = i * 2;j<=4e5;j+= i) { v[j].pb(i); } } } signed main(){ AC();clapping();TLE; cout<<fixed<<setprecision(12); main_init(); // while(cin>>n,n) // while(cin>>n>>m,n,m) // int t;cin>>t;while(t -- ) solve(); // {solve(); } return 0; } /*样例区 */ //------------------------------------------------------------
标签:lcm,int,Codeforces,len,cin,while,solve,Div,813 From: https://www.cnblogs.com/er007/p/16629714.html