A. Perpendicular Segments
两条线取边长为 $min(x,y)$ 的正方形的对角线即可
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
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;
void solve(){
int x,y,k;
cin>>x>>y>>k;
x=min(x,y);
printf("0 0 %d %d\n",x,x);
printf("%d 0 0 %d\n",x,x);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
B. Black Cells
易发现，个数为偶数时，答案即为相邻两个差的最大值
个数为奇数时，需要借用一个格子，可以在每个奇数位后插入一个，计算当前数组中的相邻差的最大值
因为数据范围很小，可以直接进行 $O(n^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
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
55
56
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
#define int long long
typedef long long ll;
const int N=1e5+7, mod=1e9+7;
int n;
set<ll>s;
ll a[N];
void solve(){
s.clear();
bool flag=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
s.insert(a[i]);
}
if(n==1){
cout<<1<<endl;
return;
}
ll ans=-1;
for(int i=1;i<n;i+=2){
ans=max(ans,a[i+1]-a[i]);
}
if(n%2==0){
cout<<ans<<endl;
return;
}
for(int i=1;i<=n;i+=2){
if(a[i+1]==a[i]+1)continue;
s.insert(a[i]+1);
ll tmp=-1;
for(auto it=s.begin(); it!=s.end()&&next(it)!=s.end(); ++it,++it){
// cout<<*next(it)<<" "<<*it<<endl;
tmp = max(tmp, *next(it) - *it);
}
ans = min(ans, tmp);
s.erase(a[i]+1);
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
可以把为 1 的位置全部塞入一个栈中
反过来查找，遇到 0 的话，就看当前栈顶的元素是否比他大，如果比他大，说明栈顶这个元素可以 free
直到没有 0 开始对栈内元素考虑，如果栈内元素的个数大于 2 那么就可以用栈底元素来使栈顶元素 free
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
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;
int n;
string s;
void solve(){
cin>>n>>s;
deque<int>q;
ll ans=0;
s=" "+s;
for(int i=n;i>0;i--){
if(s[i]=='1')q.push_back(i);
}
for(int i=n;i>0;i--){
if(s[i]=='0'){
if(!q.empty()&&i<q.front())q.pop_front();
ans+=i;
}
}
while(!q.empty()){
ans+=q.back();
q.pop_back();
if(!q.empty())q.pop_front();
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
D. Sums of Segments
设
- $s[i]$ 为 $a[i]$ 的前缀和，
- $u[i]$ 为 $s[i]$ 的前缀和，
- $t[i]$ 为分块后的第 $i$ 块的和，
- $ts[i]$ 为分块后的前缀和
易得出 $b$ 中第 $k$ 块的个数为 $n-k+1$
所以前 $k$ 块的总数为 $nk-k(k-1)/2$
总数为单调递增，我们就可以利用二分找到 $l,r$ 对应的块数，假设分别为 $x,y$
此时 $ans=ts[y]-ts[x]$，但是会有些多加的片段
此时就需要找到 $l,r$ 在所属块中的第几个
可以假设 $l$ 对应的是 $s(x,z)$，这一块上最后的元素是 $s(x,n)$，所以 $n-z=xn-\frac{x(x-1)}2-l$，通过此式找到 $z$ 的值，只需要减掉 $s(x,1)$ 到 $s(x,z-1)$ 的值即可
同理可以找到 $r$ 多加的片段
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
55
56
57
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=3e5+7, mod=1e9+7;
int n,q,l,r;
ll a[N],s[N],u[N],t[N],ts[N];
ll x,y,z,v;
ll bs(int x){
ll l=1,r=n,ans=1;
while(l<=r){
ll mid=(l+r)>>1;
if((n*mid-mid*(mid-1)/2)<x)l=mid+1;
else r=mid-1,ans=mid;
}
return ans;
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
u[i]=u[i-1]+s[i];
}
for(int i=n;i>0;i--){
t[i]=t[i+1]+(n-i+1)*a[i];
}
for(int i=1;i<=n;i++){
ts[i]=ts[i-1]+t[i];
}
cin>>q;
while(q--){
cin>>l>>r;
x=bs(l),y=bs(r);
ll ans=ts[y]-ts[x-1];
z=n-(x*n-x*(x-1)/2-l);
v=n-(y*n-y*(y-1)/2-r);
ans-=u[z-1]-u[x-1]-(z-x)*s[x-1];
ans-=u[n]-u[v]-s[y-1]*(n-v);
cout<<ans<<endl;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
|