前言：昨晚cf卡的不行，镜像的页面也打不开，卡爆了，硬着头皮打了一个小时，给卡红温了。 据说比上次的div3还难（我也看不出来），一小时后，官方说明本次unrated,直接睡觉去了，只A了ABD，cwa了三发没做出来。
今天也是补到F题了，把题解写一写---2024.9.4
A.Minimize!
赛后发现直接算就行了，c可以抵消掉，直接输出b-a，当时还傻傻地遍历。。。
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
void solve()
{
int a,b;
cin>>a>>b;
int op = INT_MAX;
for(int i=a;i<=b;i++){
op = min(op,i-a+b-i);
}
cout<<op<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t ;
cin>>t;
while (t--)
{
solve();
}
}
B. osu!mania
直接存入矩阵点，然后从大到小遍历输出#第一次出现地位置
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
void solve()
{
int n;
cin>>n;
char a[n+1][5];
for(int i=1;i<=n;i++){
for(int j=1;j<=4;j++){
cin>>a[i][j];
}
}
for(int i=n;i>=1;i--){
for(int j=1;j<=4;j++){
if(a[i][j]=='#'){
cout<<j<<" ";
break;
}
}
}
cout<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t ;
cin>>t;
while (t--)
{
solve();
}
}
C. The Legend of Freya the Frog
关键在于出发顺序，这里被坑了好几发罚时，可以提前计算出向x和向y所走的步数。
如果x所需的步数大，在x走完之前，y肯定已经达到，x走完最后一步，y就不用走了，所以是2*x-1；
如果是y较大或者相等，则必须走完x再走y,所有结果为2*y
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
void solve()
{
LL x,y,k;
cin>>x>>y>>k;
if(x==0 && y==0){
cout<<0<<endl;
return;
}
LL xx = x/k+(x%k!=0);
LL yy = y/k+(y%k!=0);
if(xx>yy){
cout<<LL(xx*2)-1<<endl;
}
else{
cout<<LL(yy*2)<<endl;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t ;
cin>>t;
while (t--)
{
solve();
}
}
D. Satyam and Counting
题目乍一看很复杂，n个点取三个凑成三角形，其实限定y的高度不是0或者1，样例也给出了提示。
一共两种情况：
一个点，如果其对面的两个相邻的点存在，则是一个三角形。
另外就是上下点都存在，则其他点必然凑成三角形。
考虑遍历求解即可，注意边界，这里卡时间复杂度。（赛后边界给我重测wa了！！！）
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
void solve()
{
int n;
cin>>n;
vector<vector<int> > a(n+1,vector<int>(2,0));
int l =0,r= 0;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
a[x][y]=1;
if(y==0) r++;else l++;
}
LL ans = 0;
for(int i=0;i<=n;i++){
if(a[i][0]==1 && a[i][1]==1){
ans = ans + r+l -2;
}
if(a[i][0]==1 && i>0 && i<n){
if(a[i-1][1]==1 && a[i+1][1]==1) ans++;
}
if(a[i][1]==1 && i>0 && i<n){
if(a[i-1][0]==1 && a[i+1][0]==1) ans++;
}
}
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t ;
cin>>t;
while (t--)
{
solve();
}
}
E. Klee's SUPER DUPER LARGE Array!!!
给出一个数，表示成一个数组，以给出的数开头，ai+1与ai相隔1，在数组中选定一个i值，取i前数字的和和i后的合做差的绝对值，求绝对值的最小值，（即最接近0）
取的i值从右往左，逐渐递增，最终一定会有大于0和小于0的边界点，考虑二分求解
最后求出的l值不一定是最小，根据check函数模拟一下，可得l-1也有可能，计算取一个min值即可
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
void solve()
{
LL n,k;
cin>>n>>k;
LL l = k , r = k+n-1;
function<LL(LL)> check = [&](LL x) -> LL{
LL res = 0;
LL nn = x-k+1;
LL pre = nn*(k)+(nn*(nn-1))/2;
LL sub = (n-nn)*(k+nn)+(n-nn)*(n-nn-1)/2;
// cout<<pre<<" "<<sub<<" ";
res = pre - sub;
return res;
};
while(l<r){
LL mid = (l+r)/2;
if(check(mid)>=0) r =mid;
else l =mid + 1;
}
if(abs(check(l-1))<=abs(check(l))){
l = l-1;
}
cout<<abs(check(l))<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t ;
cin>>t;
while (t--)
{
solve();
}
}
F. Firefly's Queries
这题花了不少时间，但其实思路很简单，还是练少了，注意用64位使用unsigned long long
以每n次进入一个循环，而每个前n项的总和是不变的，变的是多出来的一部分在原数组中的起始值，起始值到n可能会不够减去，考虑用后缀和前缀一起维护，分类讨论即可
#include <bits/stdc++.h>
using namespace std;
using LL = unsigned long long;
void solve()
{
int n,q;
cin>>n>>q;
vector<LL> a(n+1,0),pre(n+1,0),sub(n+1,0);
LL sum = 0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
pre[i] = pre[i-1] +a[i];
}
sub[n] = a[n];
for(int i=n - 1;i>=1;i--){
sub[i] = sub[i+1] + a[i];
}
while(q--){
LL l,r;
cin>>l>>r;
l--;
LL num1 = (r/n)*sum;
LL num2 = (l/n)*sum;
LL i = r/n + 1;
LL j = l/n + 1;
l%=n; r%=n;
// cout<<num1<<" ";
if(n-i+1<r){
num1 += sub[i] + pre[r-n+i-1];
}
else{
num1+= pre[i+r-1] - pre[i-1];
// cout<<pre[i+r-1]<<" "<<pre[i-1]<<" ";
}
if(n-j+1<l){
num2 += sub[j] + pre[l-n+j-1];
}
else{
num2+= pre[j+l-1] - pre[j-1];
// cout<<pre[i+r-1]<<" "<<pre[i-1]<<" ";
}
cout<<LL(num1-num2)<<endl;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t ;
cin>>t;
while (t--)
{
solve();
}
}
京公网安备 11010502036488号