round 672 div2
A : 思维
根据题意,显然n=2时只要是逆序的就no,考虑一般情况,最坏时候即整个为逆序排列,此时所需次数为$\frac{n*(n-1)}{2}$,显然得出结论,当仅最坏不可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include<iostream>
#define fuck() int t;cin>>t;while(t--)
using namespace std;
int main()
{
string y="YES",N="NO";
fuck(){
int n;cin>>n;
if(n==2){
int a,b;cin>>a>>b;
if(a>b)cout<<N<<endl;
else cout<<y<<endl;
}else{
int a,b;int cnt=0;
cin>>b;
for(int i=2;i<=n;++i){
a=b;cin>>b;
if(a>b)cnt++;
}
if(cnt==n-1)cout<<N<<endl;
else cout<<y<<endl;
}
}
return 0;
}
|
B : 思维
不难发现,两个数的按位与大于按位异或,当仅两数的二进制最高位位数相等
我第一次用了log,wa#3,可能是有误差,直接位运算找最高位即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include<iostream>
#define fuck() int t;cin>>t;while(t--)
using namespace std;
typedef long long ll;
int cn(int tmp){
int cnt=0;
while(tmp){
tmp>>=1;
cnt++;
}
return cnt;
}
int main()
{
fuck(){
ll n;cin>>n;
map<int,ll> dic;int tmp;
for(int i=1;i<=n;++i){
cin>>tmp;
if(tmp==0)continue;
dic[cn(tmp)]+=1;
}
ll cnt=0;
for(auto i:dic){
if(i.second>=2){
cnt+=(((ll)i.second-1)*i.second)/2;
}
}
cout<<cnt<<endl;
}
return 0;
}
|
C1 : DP
由题意,设置dp[maxn][2],dp[i][0]为减去这一个数的最大可能情况
过程中维护ma0和ma1,转移方程为$dp[i][0]=ma1-in[i],dp[i][1]=ma0+in[i]$
每次转移完成更新ma1,ma0,最后结果为$max(ma1,ma0)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include<iostream>
#define fuck() int t;cin>>t;while(t--)
using namespace std;
typedef long long ll;
const int maxn=3e5+3;
int in[maxn];
ll dp[maxn][2];
int main()
{
fuck(){
int n,q;cin>>n>>q;
for(int i=1;i<=n;++i){
cin>>in[i];
}
dp[0][0]=0;dp[0][1]=0;
ll ma1=0,ma0=0;
for(int i=1;i<=n;++i){
dp[i][1]=ma0+in[i];
dp[i][0]=ma1-in[i];
ma0=max(ma0,dp[i][0]);
ma1=max(ma1,dp[i][1]);
}
cout<<max(ma1,ma0)<<endl;
}
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
long long d[maxn];
int in[maxn];
int main()
{
int n,q;
int t;cin>>t;while(t--){
cin>>n>>q;
long long ans=0;
for(int i=1;i<=n;++i){
cin>>in[i];
}
in[0]=0;
for(int i=1;i<=n;++i){
d[i]=in[i]-in[i-1];
}
for(int i=1;i<=n;++i){
if(d[i]>0){
ans+=d[i];
}
}
cout<<ans<<endl;
}
return 0;
}
|
C2 : 贪心,思维
hard版本就是可以交换数,再来看整个过程
显然还有办法,就是波峰波谷,只取这些数即可,可以直接模拟求,也可以计算差分数组中正数的和.
转换之后,每次转换至多改变4个差分值,十分简单
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int in[maxn];
int main()
{
int t;cin>>t;while(t--){
memset(in,0,sizeof in);
int n,q;cin>>n>>q;
for(int i=1;i<=n;++i){
cin>>in[i];
}
long long ans=0;
for(int i=1;i<=n;++i){
if(in[i]-in[i-1]>0)ans+=in[i]-in[i-1];
}
cout<<ans<<endl;
int l,r;
while(q--){
cin>>l>>r;
if(l==r){
cout<<ans<<endl;
}else if(l+1==r){
long long tmp=max(in[l]-in[l-1],0)+max(in[r]-in[l],0)+max(in[r+1]-in[r],0);
swap(in[l],in[r]);
ans+=max(in[l]-in[l-1],0)+max(in[r]-in[l],0)+max(in[r+1]-in[r],0)-tmp;
cout<<ans<<endl;
}else {
long long tmp=max(in[l]-in[l-1],0)+max(in[l+1]-in[l],0)+max(in[r+1]-in[r],0)+max(in[r]-in[r-1],0);
swap(in[l],in[r]);
ans+=max(in[l]-in[l-1],0)+max(in[l+1]-in[l],0)+max(in[r+1]-in[r],0)+max(in[r]-in[r-1],0)-tmp;
cout<<ans<<endl;
}
}
}
return 0;
}
|
D : 离散化
对时刻离散化后,遍历时刻,仅计算,当前时刻刚刚亮的灯和之前就亮的灯的排列,因为题意中,不同时刻也不能开同几盏灯.
注意这ans可能是负的….(妈的我也不知道为什么)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e6+10;
const int mod=998244353;
int inv[N], fac[N];
void init(){
fac[0] = 1; inv[0] = inv[1] = 1;
for(int i = 1; i <= 1000000; i++)fac[i] = 1ll * fac[i - 1] * i % mod;
for(int i = 2; i <= 1000000; i++)inv[i] = (1ll * mod - mod / i)* inv[mod % i] % mod;
for(int i = 2; i <= 1000000; i++)inv[i] = 1ll * inv[i] * inv[i - 1] % mod;
}
int C(int n, int m){
if(m > n || m < 0)return 0;
return 1ll * fac[n] * inv[m] % mod* inv[n - m] % mod;
}
const int maxn=3e6+10;
int l[maxn],r[maxn];
int a[maxn*2];
int tot,cnt;
int d[maxn];
int wos[maxn];
int fts[maxn];
int main()
{
int n,k;cin>>n>>k;int x,y;
for(int i=1;i<=n;++i){
cin>>x>>y;
l[i]=x;r[i]=y;
a[++tot]=x;a[++tot]=y;
}
sort(a+1,a+1+tot);
for(int i=1;i<=tot;++i){
if(a[i]!=a[i+1]){
a[++cnt]=a[i];
}
}
for(int i=1;i<=n;++i){
int lll=lower_bound(a+1,a+1+cnt,l[i])-a;
int rrr=lower_bound(a+1,a+1+cnt,r[i])-a;
d[lll]+=1;d[rrr+1]-=1;
fts[lll]+=1;
}
for(int i=1;i<=cnt;++i){
wos[i]=d[i]+wos[i-1];
}
init();
long long ans=0;
for(int i=1;i<=cnt;++i){
ans=(ans+C(wos[i],k)-C(wos[i]-fts[i],k))%mod;
}
cout<<(ans+mod)%mod<<endl;
return 0;
}
|