A
题意
给出长度为n的数组，问是否可以经过不超过次交换相邻两值排序使该数组递增。
题解
我们知道冒泡排序的最坏情况复杂度即为，故只有在最坏情况下，即整个数组为严格递减序列时才能达到
次交换，所以只需要判断数组是否严格递减即可。
code
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n+1];
for(int i = 0;i < n;++i){
cin>>a[i];
}
int ok = 0;
for(int i = 1;i < n;++i){
if(a[i] >= a[i-1]){
ok = 1;
break;
}
}
if(ok) puts("YES");
else puts("NO");
}
return 0;
} B
题意
给出长度为n的数组，找到满足的数对数量。
题解
对于任意两个数，对两数中最大数的二进制最高位进行分析，当两数二进制最高位均为1时，则两数与操作后的值必然大于两数异或值，当两数二进制最高位不同时，则两数异或值必然大于两数与值。
举例： 5 101 2 010 5&2 = 000 5Xor2 = 111 5 101 4 100 5&4 = 100 5Xor4 = 001
可以看出，当两数对应二进制数的位数相同时，两数满足条件，否则不满足。
直接暴力枚举每段区间中数组中的个数即可（也可用二分优化），对每个区间内数的个数取组合数C(cnt,2)加和。
code
#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define e exp(1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(int i=(l);i<(r);i++)
using namespace std;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;
int main()
{
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<ll> a(n);
for(int i = 0;i < n;++i) scanf("%lld",&a[i]);
sort(a.begin(),a.end());
ll res = 0;
for(int i = 0;i < 32;++i){
int cnt = lower_bound(a.begin(),a.end(),(1ll<<(i+1))) - lower_bound(a.begin(),a.end(),(1ll<<(i)));
res += 1ll * cnt *(cnt-1) / 2;
}
printf("%lld\n",res);
}
return 0;
} C1
题意
定义一个序列的权值为将奇数位值相加，减掉所有偶数位值
给出长度为n的序列，求一个权值最大的子序列。
题解
dp
dp[i][0]代表选第i个数作为第奇数个,dp[i][1]代表选第i个数作为第偶数个。
转移方程
code
#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define e exp(1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(int i=(l);i<(r);i++)
using namespace std;
const int maxn = 3e5 + 10;
const int mod = 1e9 + 7;
ll dp[maxn][2];
int main()
{
int t;
cin>>t;
while(t--){
int n,q;
cin>>n>>q;
vector<ll> a(n);
for(int i = 0;i < n;++i){
scanf("%lld",&a[i]);
}
dp[0][0] = a[0];
dp[0][1] = 0;
for(int i = 1;i < n;++i){
dp[i][0] = max(dp[i-1][0],dp[i-1][1] + a[i]);
dp[i][1] = max(dp[i-1][1],dp[i-1][0] - a[i]);
}
printf("%lld\n",max(dp[n-1][0],dp[n-1][1]));
}
return 0;
} C2
题意
在C1的基础上，对于每个序列存在q次交换，要求回答每次交换后的序列的最大子序列权值
题解
线段树贪心，
记录每个线段的左右端点值和当前段子序列的最大权值，合并时，由于子序列最大权值必定为奇数个，所以要减去两线段中间较小的值（即左儿子右端点和右儿子左端点中较小的值），以保证父序列权值值最大。
两种情况，若该值为已选中的值，则取消选中，否则，将其放到偶数位，用总权值减掉该值。但在更新时代码表示相同。
code
#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define e exp(1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(int i=(l);i<(r);i++)
using namespace std;
const int maxn = 3e5 + 10;
const int mod = 1e9 + 7;
struct node{
ll res,l,r;
};
ll a[maxn];
struct SegmentTree{
node tree[maxn << 2];
#define lson rt<<1,L,M
#define rson rt<<1|1,M+1,R
void pushup(int rt)
{
tree[rt].res = tree[rt<<1].res + tree[rt<<1|1].res;
tree[rt].l = tree[rt<<1].l;
tree[rt].r = tree[rt<<1|1].r;
if(tree[rt<<1].r < tree[rt<<1|1].l) tree[rt].res -= tree[rt<<1].r;
else tree[rt].res -= tree[rt<<1|1].l;
// printf("-%d %d %d\n",tree[rt].res,tree[rt].l,tree[rt].r);
}
void build(int rt,int L,int R){
if(L == R){
tree[rt].l = tree[rt].res = tree[rt].r = a[L];
return ;
}
int M = L + R >> 1;
build(lson);
build(rson);
pushup(rt);
}
void update(int rt, int L,int R,int k)
{
if(L == R){
tree[rt].l = tree[rt].r = tree[rt].res = a[k];
return ;
}
int M = L + R >> 1;
if(k <= M)update(lson,k);
else update(rson,k);
pushup(rt);
}
}T;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("myout","w",stdout);
#endif
int t;
cin>>t;
while(t--){
int n,q;
scanf("%d%d",&n,&q);
for(int i = 0;i < n;++i){
scanf("%lld",&a[i+1]);
}
T.build(1,1,n);
printf("%lld\n",T.tree[1].res);
for(int i = 0;i < q;++i){
int l,r;
scanf("%d%d",&l,&r);
swap(a[l],a[r]);
T.update(1,1,n,l);
T.update(1,1,n,r);
printf("%lld\n",T.tree[1].res);
}
}
return 0;
} D
题意
给出n盏灯的允许打开时间，问一共打开k盏灯的集合有多少个。
题解
先按开灯时间l排序，再以关灯时间r作为排序条件建小根堆。
每次达到第i个的开灯时间，将第i盏灯加入堆，将已经关闭的灯弹出堆。
每次加入堆后判断是否满足k盏，为了不重复，刚刚加入的第i盏必须选择，在堆中其他的灯选择k-1个。
由于C(cnt-1,k-1)复杂度过高， 所以使用线性逆元预处理组合数即可。
code
#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<ll,ll>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define e exp(1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(ll i=(l);i<(r);i++)
using namespace std;
const ll maxn = 1e6 + 10;
const ll mod = 998244353;
pii p[maxn];
ll inv[maxn];
ll fac[maxn];
bool cmp(pii a ,pii b){
return a.second < b.second;
}
ll qpow(ll a,ll b)
{
ll res = 1;
while(b){
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
void init()
{
fac[0] = 1;
for(int i = 1;i <= maxn-1;++i){
fac[i] = fac[i-1] * i % mod;
}
inv[maxn-1] = qpow(fac[maxn-1],mod-2);
for(int i = maxn - 2;i >= 0;--i){
inv[i] = inv[i+1] * (i + 1) % mod;
}
}
ll C(ll n, ll m)
{
if(n < m) return 0;
return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main()
{
init();
ll n,k;
cin>>n>>k;
for(ll i = 0;i < n;++i){
scanf("%lld%lld",&p[i].second,&p[i].first);
}
sort(p,p+n,cmp);
ll res = 0;
priority_queue<pii,vector<pii>,greater<> > pq;
for(ll i = 0;i < n;++i){
ll now = p[i].second;
if(pq.size()){
pii hd = pq.top();
while(hd.first < now){
pq.pop();
if(pq.size())hd = pq.top();
else break;
}
}
pq.push(p[i]);
if(pq.size() >= k){
res = (res + (C(pq.size()-1,k-1)))%mod;
}
}
printf("%lld\n",res);
// system("pause");
return 0;
} 
京公网安备 11010502036488号