A
找到一个数和数组中任何一个数都不互为倍数，注意到数组中数字不超过1e9，但我们找的这个数可以1e18，那显然找一个比1e9打的质数就行了。但是注意任何数都是1的倍数，所以出现1就无解
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int cnt=0;
for(int i=0;i<n;i++){
int x;
cin>>x;
if(x==1)cnt++;
}
if(cnt)cout<<-1<<'\n';
else cout<<(int)(1e9+7)<<'\n';
}
}
B
给一棵树，找到一条简单路径通过所有点。显然只有是一条链才能做到，可以用每个点的边数判断，只有两个点度为1的时候就是一条链
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>cnt(n+1);
vector<vector<int>>g(n+1);
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
cnt[u]++;
cnt[v]++;
g[u].push_back(v);
g[v].push_back(u);
}
int t=0;
vector<int>ans;
for(int i=1;i<=n;i++){
if(cnt[i]==1){
t++;
ans.push_back(i);
}
}
if(t==2){
for(int x:ans)cout<<x<<' ';
}
else{
cout<<-1;
}
}
D
判断一个数组是否只有两种元素，且出现次数相等，map统计即可
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
map<int,int>mp;
for(int i=0;i<n;i++){
int x;
cin>>x;
mp[x]++;
}
if(n%2==0&&mp.size()==2&&mp.begin()->second==n/2){
cout<<"Yes\n";
}
else{
cout<<"No\n";
}
}
}
E
中位数贪心结论
给你一个数组，要把它变成D里定义的双生数组，也就是只有两种元素，出现次数相等。每次操作可以选一个数加一/减一，问最少操作次数
首先应该分成两部分，先排序，前半段集中到一个点，后半段集中到另一个数。感性上证明可以考虑交换论证，如果把后半部分的一个元素给前半部分，答案不会变得更优。
然后对于前半部分和后半部分，应该分别集中到他们的中位数，这是个经典贪心结论。需要特判的是前半部分和后半部分中位数一样的情况，我们要变成两种数字，肯定不能全变成一样的。因此要把其中一个变化1.可以把前半部分的-1或后半部分+1，取最小值
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int>a(n);
for(int i=0;i<n;i++)cin>>a[i];
sort(a.begin(),a.end());
int m1,m2;
if(n%4==0){
m1=(a[n/4-1]+a[n/4])/2;
m2=(a[n/4*3-1]+a[n/4*3])/2;
}
else{
m1=a[n/4];
m2=a[n-1-n/4];
}
auto cal=[&](int m1,int m2)->long long{
long long ans=0;
for(int i=0;i<n/2;i++){
ans+=abs(a[i]-m1);
}
for(int i=n/2;i<n;i++){
ans+=abs(a[i]-m2);
}
return ans;
};
//cout<<m1<<' '<<m2<<' ';
if(m1!=m2){
cout<<cal(m1,m2)<<'\n';
}
else{
cout<<min(cal(m1-1,m1),cal(m1,m1+1))<<'\n';
}
}
}
F
双指针+前缀和
要找到所有是双生数组的子数组个数。这里可以分两部分思考。首先是只含两种元素，这可以用滑窗+map解决，map统计当前区间内元素种类数。
然后对于每个找到的只含两种元素的区间，我们要判断两种元素个数相同的区间个数，这也是个经典问题，可以把一种元素看成+1，另一种看成-1，然后就转化为了找元素和为0的子数组个数，这可以map前缀和实现。
需要注意的是，对于每两种元素，我们要找到包含只这两种元素的最大区间，比如数组，区间
都是只含两种元素的，如果对这两个区间都跑前缀和，其实是有重复计算的，可能超时，所以我们应该取
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int>a(n);
for(int i=0;i<n;i++){
cin>>a[i];
}
unordered_map<int,int>mp;
vector<vector<int>>seg;
for(int l=0,r=0;r<n;r++){
mp[a[r]]++;
if(mp.size()==3){
seg.push_back({l,r-1});
}
while(l<=r&&mp.size()>2){
mp[a[l]]--;
if(mp[a[l]]==0){
mp.erase(a[l]);
}
l++;
}
if(r==n-1&&mp.size()==2){
seg.push_back({l,r});
}
}
long long ans=0;
for(auto &v:seg){
int l=v[0],r=v[1];
//cout<<l<<' '<<r<<' ';
set<int>s;
for(int i=l;i<=r;i++){
s.insert(a[i]);
}
unordered_map<int,int>cnt;
cnt[0]++;
int pre=0;
for(int i=l;i<=r;i++){
if(a[i]==*s.begin()){
pre++;
}
else{
pre--;
}
if(cnt.count(pre)){
ans+=cnt[pre];
}
cnt[pre]++;
}
}
cout<<ans<<'\n';
}
}
G
每次操作对一个元素+1，对另一个元素-1，问能不能把这个序列变成一个排列？
首先这个操作不改变数组元素和，因此可以先根据数组元素和判断它是不是和长为n的排列元素和一样，不一样肯定无解
其次，只要求变成排列，没要求变成哪个排列，每个数都可以变成最终排列中任意一个数，这就又是一个经典贪心：可以先排序，然后第i个元素变成i，总操作次数最少，这相当于每个元素都就近，变成它最近的那个数
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>a(n);
long long sum=0;
for(int i=0;i<n;i++){
cin>>a[i];
sum+=a[i];
}
if(sum!=1ll*(1+n)*n/2){
cout<<-1;
return 0;
}
sort(a.begin(),a.end());
long long ans=0;
for(int i=0;i<n;i++){
ans+=abs(a[i]-(i+1));
}
cout<<ans/2;
}
H
贪心构造
构造一个排列，要满足第i个数在范围内。需要转变一下思路，正着思考每个位置应该放几，会很复杂。不妨反过来思考，每个数i，应该放到哪个位置
显然一个数i可以放到所有包含i的区间内，那应该放哪个呢？贪心的思路是，应该放到最小的区间里，因为这个区间限制最严，如果我们从小到大放i,现在不放，后面i越来越大，肯定是越来越难放，最后可能这个区间就不放了，但是我们n个数放到n个区间，是一一对应的，如果有一个区间放不了，就无解了。所以应该现在就放到能放的区间里,r最小的那个里。
那么我们可以从小到大放i，把所有的区间都拿出来当成备选的，然后对于
排序，找
最小的区间放i。这需要一个支持动态插入和排序的数据结构，可以是set，也可以优先队列。如果任意时刻,所有r都比i小，或者set/优先队列空了，说明这个i没有能放的区间，也是无解
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<vector<int>>seg;
for(int i=0;i<n;i++){
int l,r;
cin>>l>>r;
seg.push_back({l,r,i});
}
set<vector<int>>s;
sort(seg.begin(),seg.end());
vector<int>ans(n);
for(int i=1,j=0;i<=n;i++){
while(j<n&&seg[j][0]<=i){
s.insert({seg[j][1],seg[j][2]});
j++;
}
if(s.empty()||(*s.begin())[0]<i){
//cout<<i<<' ';
cout<<-1;
return 0;
}
auto v=*s.begin();
ans[v[1]]=i;
s.erase(s.begin());
}
for(int x:ans)cout<<x<<' ';
}
J
数论，枚举gcd
这种多个条件，其中一个条件是gcd的，都可以考虑枚举gcd，因为gcd一般都不多。
对于本题，要找所有异或等于gcd的数对，一个数的gcd一定是他的因子，所以我们可以枚举一个数的因子，然后又有ai^aj=gcd，ai是我们当前的数，gcd我们又枚举出来了，那可以算出aj=ai^gcd，到这一步这个aj只是候选，我们再去检查ai^aj=gcd(ai,aj)是否真的成立就行了，如果真的成立就把aj的出现次数加入答案
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
map<int,int>mp;
long long ans=0;
for(int i=0;i<n;i++){
int x;
cin>>x;
for(int j=1;j*j<=x;j++){
if(x%j==0){
int y=x^j;
if(__gcd(x,y)==j){
if(mp.count(y)){
ans+=mp[y];
}
}
if(x/j!=j){
int y=x^(x/j);
if(__gcd(x,y)==x/j){
if(mp.count(y)){
ans+=mp[y];
}
}
}
}
}
mp[x]++;
}
cout<<ans;
}
K
求有多少个长度大于1的子数组，所有元素的异或和等于所有元素的gcd。
这里有一个重要的思想：，对于gcd，按位与，按位或这种随着元素增加单调变化的，且每次变化至少除2/乘二的运算，所有以
为端点的子数组中，不同的gcd/按位与/按位或值只有
种
也就是所有以i为左端点的子数组中,只有个
，这些
内部，
的gcd都相同。于是我们可以对每个i求出所有l，然后对于这些l形成的区间，分别计算有多少区间满足异或和等于gcd
首先计算所有，可以用st表+二分，st表可以
查询一个区间的gcd，假设当前区间的开始是
，gcd为
，我们可以二分找到满足
的最大的
是多少，然后
就组成了一个gcd相同的区间
对于每个区间，假设，我们实际上是要求有多少个
满足
求一个区间内某个值的出现次数，最简单的方式是，对于每个值维护一个下标数组，然后对这个下标数组进行二分，找到第一个大于等于的下标的位置，以及最后一个小于等于
的下标的位置，他们的中间就是
区间中这个值出现的所有下标
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define ll long long
#define LL ll
#define int ll
#define db double
#define ld long double
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define rep1(i,x,y) for(int i=(x);i>=(y);i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define ls u<<1
#define rs u<<1|1
const int N=5e5+10,M=5e5+10;
const int M1=1e9+7,M2=998244353,P=100000000000031,base=77;
int n,m,k;
class SparseTable {
public:
SparseTable(const std::vector<int>& data) {
n = data.size();
log.resize(n + 1);
for (int i = 2; i <= n; ++i) {
log[i] = log[i / 2] + 1;
}
int k = log[n];
st.assign(n, std::vector<int>(k + 1, 0));
for (int i = 0; i < n; ++i) {
st[i][0] = data[i];
}
for (int j = 1; j <= k; ++j) {
for (int i = 0; i + (1 << j) <= n; ++i) {
st[i][j] = gcd(st[i][j - 1] , st[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int left, int right) {
int j = log[right - left + 1];
return gcd(st[left][j] , st[right - (1 << j) + 1][j]);
}
private:
int n; // 数据的大小
std::vector<std::vector<int>> st; // 稀疏表
std::vector<int> log; // 记录对数值
};
void solve(){
cin>>n;
vector<int>a(n+1),pre(n+1);
map<int,vector<int>>mp;
rep(i,1,n)cin>>a[i];
rep(i,1,n){
pre[i]=pre[i-1]^a[i];
mp[pre[i]].push_back(i);
}
rep(i,1,n)mp[i].push_back(1e9);
SparseTable st(a);
vector<vector<vector<int>>>seg(n+1);
rep(i,1,n-1){
int l=i+1;
auto find=[&](int x)->int{
int l=x,r=n;
while(l<=r){
int m=l+r>>1;
if(st.query(i,m)==st.query(i,x))l=m+1;
else r=m-1;
}
return r;
};
while(1){
if(l>n)break;
int r=find(l);
seg[i].push_back({l,r});
l=r+1;
}
}
int ans=0;
rep(i,1,n){
for(auto &v:seg[i]){
int l=v[0],r=v[1];
int g=st.query(i,l);
int val=pre[i-1]^g;
vector<int>&pos=mp[val];
auto p1=lower_bound(pos.begin(),pos.end(),l);
auto p2=upper_bound(pos.begin(),pos.end(),r);
//cout<<i<<' '<<l<<' '<<r<<' '<<g<<' '<<val<<' '<<p2-p1<<'\n';
ans+=p2-p1;
}
}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int test=1;
cin>>test;
while(test--){
solve();
}
}
M
贪心
选一个非空区间乘2，问操作完数组的极差。策略不复杂，关键是证明。策略就是先把最小值乘2，然后把次小值乘2，以此类推，每扩大一次区间，就计算一次极差。由于最小值和次小值不一定挨着，我们又只能操作一个区间，只能把能包含当前所有要操作的的值的最小区间乘二，也就是会把一些无关的元素也乘2
这样为啥是对的呢？可以这样想，如果我不把最小值乘2，而是把别的值乘2，最小值还是最小值，然后最大值肯定不减，极差肯定不减，相当于白操作了，所以一定要操作最小值，然后操作完最小值了，如果不操作次小值，也是同理，不管你对其他元素怎么操作，次小值会一直是最小值然后极差不会变小。
所以我们的操作必须包含，最小值，次小值……然后我们还操作了无关元素，最小值和最大值都可能变化，所以需要动态维护最值，这可以set实现
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>a(n);
vector<vector<int>>b(n);
multiset<int>s;
int mx=0,mn=1e9;
for(int i=0;i<n;i++){
cin>>a[i];
mn=min(mn,a[i]);
mx=max(mx,a[i]);
b[i]={a[i],i};
s.insert(a[i]);
}
sort(b.begin(),b.end());
s.erase(s.find(b[0][0]));
s.insert(b[0][0]*2);
int ans=*s.rbegin()-*s.begin();
int l=b[0][1],r=b[0][1];
for(int i=1;i<n;i++){
while(l>b[i][1]){
l--;
s.erase(s.find(a[l]));
s.insert(a[l]*2);
}
while(r<b[i][1]){
r++;
s.erase(s.find(a[r]));
s.insert(2*a[r]);
}
ans=min(ans,*s.rbegin()-*s.begin());
}
cout<<ans;
}
京公网安备 11010502036488号