A. Perpendicular Segments
分析
题目中的要求\(34\)，说明需要较短的线段尽量长，那么两个线段应该一样长
而又要求线段垂直， 那么两线段可以放在一个正方形内做对角线
那么此时\(x\)和\(y\)对称(代数一样上), 取两个的较小值做一个正方形，答案即为对角线
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
const int N=1e6+10;
const int mod=998244353;
const int INF = 0x3f3f3f3f;
const ll INFll = 0x3f3f3f3f3f3f3f3f;
#define endl "\n"
//vector<vector<int>>adj(N);
void solve()
{
int x, y, k;
cin >> x >> y >> k;
if(x > y) swap(x, y);
cout << "0 0 " << x << " " << x << endl;
cout << "0 " << x << " " << x << " 0" << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cout << setprecision(11) << fixed;
int t;t=1;
cin>>t;
for(int i=1;i<=t;i++){
//printf("Case %d: ",i);
solve();
}
}
B. Black Cells
赛时脑瘫了，看到\(1e18\)不敢二分，硬写了个\(o(n)\), 成功\(wa2\)
分析
直接二分\(k\)的大小
分析\(check\)
如果\(n\)是偶数，最好的情况就是每次选相邻的两个，这种情况甚至不需要二分，直接算出来
否则可以选一个不染，当发现此时\(k\)不够染相邻\(2\)个时，舍掉左边那个，继续染剩下的
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
const int N=1e6+10;
const int mod=998244353;
const int INF = 0x3f3f3f3f;
const ll INFll = 0x3f3f3f3f3f3f3f3f;
#define endl "\n"
//vector<vector<int>>adj(N);
int a[N];
int b[N],c[N];
int n;
bool check(int mid) {
for(int i = 1; i + 1 <= n; i += 2) {
if(a[i + 1] - a[i] > mid) {
if(n % 2 == 0) return false;
if(i % 2 == 0) return false;
i --;
}
}
return true;
}
void solve()
{
cin >> n;
for(int i = 1; i <= n; i ++) {
cin >> a[i];
}
int l = 1, r = 1e18;
while(l < r) {
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cout << setprecision(11) << fixed;
int t;t=1;
cin>>t;
for(int i=1;i<=t;i++){
//printf("Case %d: ",i);
solve();
}
}
C. Action Figures
分析
首先，在某天买东西时，一定会试图免费第\(i\)个物品，因为这是可买中，最贵的
所以,当\(s[i] == 0\) 时， \(i\)物品的钱一定要出。
所以我们考虑那些物品可以被免费
逆袭枚举每一天，同时，用一个队列来存需要免费的物品
- 如果\(s[i] == 1\), 丢到队列里面
- 如果\(s[i] == 0\), 记录价值，同时取出队首(最贵的)
当枚举后，队列可能不空，需要支付里面较小的一半的钱，同时也可以免费较大的
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
const int N=1e6+10;
const int mod=998244353;
const int INF = 0x3f3f3f3f;
const ll INFll = 0x3f3f3f3f3f3f3f3f;
#define endl "\n"
//vector<vector<int>>adj(N);
void solve()
{
int n; cin >> n;
string s; cin >> s;
s = " " + s;
int cnt = 0;
queue<int> q;
int ans = 0;
vector<int>a(n + 1);
for(int i = n; i >= 1; i --) {
if(s[i] == '1') q.push(i);
else {
ans += i;
if(q.size())q.pop();
}
}
int t = (q.size() + 1)/2; // 这里没明白可以改为双端队列，一个一个慢慢算
while(q.size()) {
if(q.size() <= t) ans += q.front();
q.pop();
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cout << setprecision(11) << fixed;
int t;t=1;
cin>>t;
for(int i=1;i<=t;i++){
//printf("Case %d: ",i);
solve();
}
}
D. Sums of Segments
写的最屎的一题，正在试图看懂赛时代码