目录
A – π
题意
思路
正解代码
B – Deconstruct Chocolate
题意
思路
正解代码
C – Comfortable Distance
题意
思路
正解代码
D – Make Target 2
题意
思路
正解代码
E – A += v
题意
思路
正解代码
A – π
B – Deconstruct Chocolate
C – Comfortable Distance
D – Make Target 2
E – A += v
A – π
题意
题目的意思是给出直径 D ，要求我们算出圆的面积。
思路
这道题的主要难点在于精度的控制，题目说我们的误差要控制在 10 的 -6 次方，但由于面积是 D^2/4*pi ，我们最好输出精确到小数点后 10 位的值以避免精度上的问题。
正解代码
#include<bits/stdc++.h>
using namespace std;
int main(){
double d;
cin>>d;
cout<<setprecision(10)<<fixed<<d*d/4*3.141592653589793;
}
B – Deconstruct Chocolate
题意
题目的意思大致是：我们有一个长度为 H ，宽度为 W 的巧克力，我们有两种操作：
1.吃掉前 R 行
2.吃掉前 C 列
问所有操作做完后吃掉了多少巧克力
思路
正常地遍历操作，更新现在的行数和列数就可以了。
正解代码
#include<bits/stdc++.h>
using namespace std;
const int H = 105;
int h,w,q;
int main(){
cin>>h>>w>>q;
while(q–){
int op,x;
cin>>op>>x;
if(op == 1){
cout<<x*w<<'\\n';
h -= x;
}
else{
cout<<x*h<<'\\n';
w -= x;
}
}
}
C – Comfortable Distance
题意
题目的意思大致是：给出一个长为 N 的字符串，我们需要找出符合以下条件的数对的个数：
思路
首先我们会想到去枚举 i 和 j ，但是 N 很大，所以这个想法必然是不可行的。所以我们得另辟蹊径。
这时，我们注意到，这个字符串仅仅由小写英文字母组成，于是我们可以先把所有字母的位置分别提取出来，储存在不同的容器当中。
然后，对于一个字母，我们发现，由于它们的位置都是单调递增的，所以我们可以维护一个滑动窗口来统计数量。
这样，我们就完美地在 O(n) 的时间内解决了这道题。
正解代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5+5;
int n,L,R;
string s;
vector<int>pos[30];
signed main(){
cin>>n>>L>>R;
cin>>s;
for(int i=0;i<n;i++) pos[s[i]-'a'].push_back(i);
int ans = 0;
for(int i=0;i<26;i++){
if(pos[i].size() == 0) continue;
int now = 0, l = 0, r = 0;
while(now < pos[i].size() && l < pos[i].size()){
while(l < pos[i].size() && pos[i][l] – pos[i][now] < L) l++;
if(l >= pos[i].size()) break;
while(r < pos[i].size() && pos[i][r] – pos[i][now] <= R) r++;
ans += r-l;
now ++;
}
}
cout<<ans<<'\\n';
return 0;
}
D – Make Target 2
题意
题目的意思大致是：在一个 x-y 坐标系中，max(|x|, |y|) 是偶数的点是黑色，是奇数的点是白色。给出 L, R, D, U，要求我们求出这个范围内黑色的点的个数。
思路
由于给出的数字较大，通过枚举点来完成这道题是十分不现实的。所以，我们可以从另一个角度进行考虑。
我们可以考虑每一个 x = ? 的直线对结果的贡献。
然后，对于每一条这样的直线，它的贡献的求解可以分为两个情况，直线与 x 轴相交和直线不与 x 轴相交。对于前者，D 和 U 对结果都是正贡献，而对于后者我们可以只讨论直线在 x 轴上方的情况，因为整个求解是对称的，D 对结果是负贡献而 U 对结果是正贡献。
在这一基础上，我们又可以把直线分成两种，一种是 x 为偶数，另一种是 x 为奇数。前者会有靠近 x 轴的连续的黑点，后者则是连续的白点。我们需要分类讨论。
这里的讨论比较复杂，详情见正解代码。
正解代码
#include<bits/stdc++.h>
typedef unsigned long long ull;
using namespace std;
int L,R,D,U;
signed main(){
cin>>L>>R>>D>>U;
if(D < 0 && U < 0) D = -D, U = -U, swap(D,U);
ull ans = 0;
for(int i = L;i <= R;i++){
int now = abs(i);
ull res = 0;
if(now % 2 == 0){
if(D < 0 && U >= 0){
res += min(now,U) + 1;
res += min(now,-D);
if(U > now) res += (U – now)/2;
if(-D > now) res += (-D – now)/2;
}
else{
res += min(now,U) + 1;
res -= min(now,D-1) + 1;
if(U > now) res += (U – now)/2;
if(D > now + 1) res -= (D – 1 – now)/2;
}
}
else{
if(D < 0 && U >= 0){
if(U > now) res += (U – now + 1)/2;
if(-D > now) res += (-D – now + 1)/2;
}
else{
if(U > now) res += (U – now + 1)/2;
if(D > now + 1) res -= (D – now)/2;
}
}
//cout<<i<<' '<<res<<'\\n';
ans += res;
}
cout<<ans;
return 0;
}
E – A += v
题意
题目的意思大致是：我们现在有 1~m 的整数，给出一个长度为 n 的数列，我们需要进行以下的操作 10^100 次。
1.找到数列中出现次数最少的 1~m 的整数（0次也算）。
2.将其加入末尾。
给出 q 次询问，每次我们需要输出该位置的元素。
思路
我们先设原数列长度为 N1 ，经过大量操作后所有数的出现次数相等后的数列长度为 N2。我们可以将询问分成 3 种类型：1.长度小于等于 N1 2.长度在 N1 和 N2 之间 3.长度大于 N2
为什么这么分呢？因为第一种类型可以直接查询，第三种类型已经进入一个有规律的循环，即从小到大一直重复加入数列末尾。所以我们的重心就放在第二种类型的求解。
我们可以先把问题问的位置排序，从小到大解决。再把原数列出现的数字按出现次数进行分类。
我们可以发现，出现次数相同的数字会在同一轮从小到大加入，而所有出现次数较小的数字都会一同参加次数较大的轮次。所以，我们可以枚举加入的轮次进行处理。
这里我们需要引入 ordered_set ，它在 set 的基础上，具备了能够快速得到第 k 大数字的能力。
正解代码
#include<bits/stdc++.h>
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pil pair<int,long long>
#define pli pair<long long, int>
using namespace std;
typedef long long ll;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
const int N = 5e5+5;
int n, m;
int a[N];
int q;
int ans[N];
int cnt[N];
vector<int> num[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i = 1;i <= n;i++) {
cin>>a[i];
cnt[a[i]] ++;
}
for(int i = 1;i <= m;i++) {
num[cnt[i]].push_back(i);
}
cin>>q;
vector<pli> que;
for(int i = 0; i < q;i++) {
ll x;
cin>>x;
que.push_back({x, i});
}
sort(que.begin(), que.end());
int now = 0; //目前处理到哪个问题
while(now < q && que[now].first <= n) {
ans[que[now].second] = a[que[now].first];
now ++;
}
oset S;
ll len = n; //目前的序列长度
ll st = n; //当前块的起点
for(int i = 0;i <= n;i++){
for(int j:num[i]) S.insert(j);
len += S.size();
while(now < q && que[now].first <= len){
ans[que[now].second] = *S.find_by_order(que[now].first – st – 1);
//auto it = S.find_by_order(que[now].first – st – 1);
//if(it == S.end()) cout<<que[now].first<<' '<<len<<' '<<st<<' '<<S.size()<<"XX\\n";
now ++;
}
st = len;
}
while(now < q){
ll res = (que[now].first – st)%m;
if(res == 0) res = m;
ans[que[now].second] = res;
now ++;
}
for(int i = 0;i < q;i++) {
cout<<ans[i]<<"\\n";
}
return 0;
}
以上就是这篇文章的全部内容了。
