给定
n
n
n 的二进制表示和三进制表示。 但这两个表示中，都有一位数字是错误的。 求原来的
n
n
n
n
≤
1
0
9
n\le 10^9
n≤109
思路
分别枚举两个表示中，哪一位出错，以及修改后改成什么。 然后判断修改后数字是否相同即可。可以
O
(
1
)
O(1)
O(1) 去判。
代码
时间复杂度：
O
(
log
2
n
×
log
3
2
n
)
，
就
1.1
e
4
O(\log_2n\times \log_3^2n)，就1.1e4
O(log2n×log32n)，就1.1e4次运算。
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x << " ] , ";show(args...);}
const int MAX = 60;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-5;
int b2[MAX],b3[MAX];
int main()
{
b2[0] = 1;b3[0] = 1;
string ta,tb;
int la,lb;
cin >> ta >> tb;
la = ta.size();lb=tb.size();
int n1 = 0,n2 = 0;
int st = 0;
for(int i = la-1;i>=0;--i){
n1 = n1 + b2[st] * (ta[i] - '0');
st++;
b2[st] = b2[st-1] * 2;
}
st = 0;
for(int i = lb-1;i>=0;--i){
n2 = n2 + b3[st] * (tb[i] - '0');
st++;
b3[st] = b3[st-1] * 3;
}
// show(n1,n2);
int nn1=0,nn2=0;
for(int i = la-1;i>=0;--i){
nn1=n1;
if(ta[i] == '1'){
nn1 -= b2[la-1-i];
}else{
nn1 += b2[la-1-i];
}
for(int j = lb-1;j>=0;--j){
for(int k = 0;k <= 2;++k){
if(k != (tb[j]-'0')){
nn2 = n2-(tb[j]-'0')*b3[lb-1-j] + k*b3[lb-1-j];
if(nn1 == nn2){
cout << nn1;
return 0;
}
}
}
}
}
return 0;
}
B
题意
给你一个长度为
n
n
n 的序列
H
H
H 给你一个
X
X
X 问你其中有多少个连续区间，满足这个区间中所有数字排序后的中位数
≥
X
\ge X
≥X
1
≤
N
≤
1
0
5
1\le N\le 10^5
1≤N≤105
1
≤
H
i
≤
1
0
9
1\le H_i\le 10^9
1≤Hi≤109
1
≤
X
≤
1
0
9
1\le X\le 10^9
1≤X≤109
思路
首先容易得到，若
H
i
≥
X
H_i\ge X
Hi≥X,我们令
A
i
=
1
A_i=1
Ai=1 否则，我们令
A
i
=
−
1
A_i=-1
Ai=−1 考虑区间右端点为
i
i
i，满足区间和
=
x
=x
=x 的区间个数为
s
h
u
[
i
]
[
x
]
shu[i][x]
shu[i][x] 我们答案容易得到为
∑
s
h
u
[
i
]
[
j
≥
0
]
\sum shu[i][j\ge0]
∑shu[i][j≥0]
我们考虑转移。如果当前
A
i
=
1
A_i=1
Ai=1 时：
s
h
u
[
i
−
1
]
[
x
]
shu[i-1][x]
shu[i−1][x] 转移到
s
h
u
[
i
]
[
x
+
1
]
shu[i][x+1]
shu[i][x+1] 然后
s
h
u
[
i
]
[
1
]
shu[i][1]
shu[i][1] 额外增加1，因为多了一个长度为1的区间
[
i
,
i
]
[i,i]
[i,i]
如果当前
A
i
=
−
1
A_i=-1
Ai=−1 时：
s
h
u
[
i
−
1
]
[
x
]
shu[i-1][x]
shu[i−1][x] 转移到
s
h
u
[
i
]
[
x
−
1
]
shu[i][x-1]
shu[i][x−1] 然后
s
h
u
[
i
]
[
−
1
]
shu[i][-1]
shu[i][−1] 额外增加1。
每次都把
s
h
u
[
]
[
]
shu[][]
shu[][] 向左/右 移动肯定不好做，但是我们可以移动假想原点
o
r
i
ori
ori，原点移动就相当于
s
h
u
[
]
[
]
shu[][]
shu[][] 数组移动了。
其他的就是每次单点更新
+
1
/
−
1
+1/-1
+1/−1 ，还有求区间和
s
h
u
[
i
]
[
j
≥
0
]
shu[i][j\ge0]
shu[i][j≥0]，用一个线段树即可。 注意一下数组下标不能为负数，集体向右移动一段即可。
代码
时间复杂度：
O
(
N
log
N
)
O(N\log N)
O(NlogN)
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x << " ] , ";show(args...);}
const int MAX = 1e5+50;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-5;
#define ls (p<<1)
#define rs (p<<1|1)
#define md ((l+r)>>1)
const int YOU = 2e5+2;
int aa[MAX];
int tree[YOU*4];
void push_up(int p){
tree[p] = tree[ls] + tree[rs];
}
void build(int p,int l,int r){
if(l == r){
tree[p] = 0;
return;
}
build(p,l,md);
build(p,md+1,r);
push_up(p);
}
void update(int p,int l,int r,int u,ll k){
if(l == r){
tree[p] += k;
return;
}
if(md >= u)update(ls,l,md,u,k);
else update(rs,md+1,r,u,k);
push_up(p);
}
ll query(int p,int l,int r,int qx,int qy){
if(qx <= l && qy >= r){
return tree[p];
}
ll res = 0;
if(qx <= md)res += query(ls,l,md,qx,qy);
if(qy > md)res += query(rs,md+1,r,qx,qy);
return res;
}
int main()
{
int n,x;
scanf("%d%d",&n,&x);
for(int i = 1;i <= n;++i){
int t;scanf("%d",&t);
if(t >= x)aa[i] = 1;
else aa[i] = -1;
}
build(1,1,YOU);
int ori = 1e5+1;
ll ans = 0;
for(int i = 1;i <= n;++i){
if(aa[i] == 1){
ori--;
update(1,1,YOU,ori+1,1);
ans += query(1,1,YOU,ori,YOU);
}else{
ori++;
update(1,1,YOU,ori-1,1);
ans += query(1,1,YOU,ori,YOU);
}
//show(ans);
}
printf("%lld",ans);
return 0;
}
/**
4 6
0 0 0 0
*/
C
暴力
D
题意
n
n
n 个点，每个点有一个坐标
x
i
x_i
xi 和种类
y
i
y_i
yi 求最短的区间长度，其中覆盖了所有种类的点。
1
≤
n
≤
5
e
4
1\le n\le 5e4
1≤n≤5e4
思路
尺取即可。 注意一下跳出条件。
代码
时间复杂度：
O
(
n
)
O(n)
O(n)
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x << " ] , ";show(args...);}
const int MAX = 5e4+50;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-5;
struct node{
int p;
int id;
bool operator <(const node &ND)const{
return p < ND.p;
}
}aa[MAX];
map<int,int>M;
int main()
{
int n,cnt = 0;
scanf("%d",&n);
for(int i = 1;i <= n;++i){
scanf("%d%d",&aa[i].p,&aa[i].id);
M[aa[i].id]++;
if(M[aa[i].id] == 1)cnt++;
}
sort(aa+1,aa+1+n);
// for(int i = 1;i <= n;++i){
// printf("%d %d\n",aa[i].p,aa[i].id);
// }
M.clear();
int L = 1,R = 0;
int ans = INF;
int now = 0;
while(1){
while(R < n && now < cnt){
R++;
M[aa[R].id]++;
if(M[aa[R].id] == 1)now++;
}
if(R == n){
if(now == cnt)ans = min(ans,aa[R].p - aa[L].p);
else break;
}
while(L <= R && now == cnt){
//show(L,R);
ans = min(ans,aa[R].p - aa[L].p);
M[aa[L].id]--;
if(M[aa[L].id] == 0)now--;
L++;
}
}
printf("%d",ans);
return 0;
}
/**
5
1 1
2 1
3 1
4 1
5 2
*/
E
题意
n
×
m
n\times m
n×m 的图，要么为
X
X
X 要么为
.
.
. 其中有两个
X
X
X 的连通块 问你最少把多少个点变成
X
X
X ，使得变成一个
X
X
X 的连通块
n
,
m
≤
50
n,m\le 50
n,m≤50
思路
B
F
S
BFS
BFS 让两坨
X
X
X 相遇即可。
F
随便数时间就行了。 我暴力数的，其实可以
O
(
1
)
O(1)
O(1) 判…
int main()
{
int d,h,m;
scanf("%d%d%d",&d,&h,&m);
if(d == 11 && h == 11 && m < 11){
puts("-1");
}else if(d == 11 && h < 11){
puts("-1");
}else{
int ans = 0;
int dd,hh,mm;
for(dd = 11;dd <= d;++dd){
if(dd == 11)hh = 11;
else hh = 0;
for(;hh <= 23;++hh){
if(dd == 11 && hh == 11)mm = 11;
else mm = 0;
for(;mm <= 59;++mm){
ans++;
if(dd == d && hh == h && mm == m){
printf("%d",ans-1);
return 0;
}
}
}
}
}
return 0;
}
H
n
×
m
n\times m
n×m 的图，要么为
X
X
X 要么为
.
.
. 其中有三个
X
X
X 的连通块 问你最少把多少个点变成
X
X
X ，使得变成一个
X
X
X 的连通块
有
N
N
N 个方块，每个有边长
A
i
A_i
Ai，给你一个
M
M
M 你需要选出一些方块，让他们的边长变成
A
i
′
A_i^\prime
Ai′，花费为
(
A
i
−
A
i
′
)
2
(A_i-A_i^\prime)^2
(Ai−Ai′)2 问最后所有方块的面积变成
M
M
M 的最小花费
1
≤
N
≤
10
1\le N\le 10
1≤N≤10
1
≤
M
≤
1
0
4
1\le M\le 10^4
1≤M≤104
1
≤
A
i
≤
100
1\le A_i\le 100
1≤Ai≤100
思路
首先，爆搜
O
(
1
0
x
)
O(10^x)
O(10x) 这里
x
x
x 很大，肯定不行 （会 T 四个点） 考虑一般的状态保存，
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 表示目前搞定了前
i
i
i 个方块，得到的面积为
j
j
j 的最小花费。 状态数已经
O
(
N
M
)
O(NM)
O(NM)了，但是转移的时间复杂度不会很大 因为我们枚举的是边长，边长不会
>
M
>\sqrt M
>M
所以就不会有什么问题
代码
时间复杂度：
O
(
N
M
M
)
O(NM\sqrt M)
O(NMM
)
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x << " ] , ";show(args...);}
const int MAX = 30;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-5;
int aa[MAX];
int n,m;
ll dp[11][10050];
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;++i)scanf("%d",&aa[i]);
for(int i = 0;i <= n;++i)
for(int j = 0;j <= m;++j)
dp[i][j] = LINF;
dp[0][0] = 0;
for(int i = 1;i <= n;++i){
for(int j = 1;j <= m;++j){
for(ll k = 1;k*k <= m && j-k*k>=0;++k){
dp[i][j] = min(dp[i][j],dp[i-1][j-k*k] + (aa[i] - k) * (aa[i] - k));
}
}
}
if(dp[n][m] >= LINF){
puts("-1");
return 0;
}
printf("%lld",dp[n][m]);
return 0;
}
/**
1 2
1
*/