Preface
一套烂题。
T1 一眼搬的 CF(赛后十秒就找到原题了),只搬 idea 就算了,根本不设置部分分,大样例给的更是一坨(数据范围给的 \(10^{15}\),1
2
10
72
121
算什么大样例?),甚至最后的题解都是直接复制的洛谷。
T2 稍好,除了实数运算稍微恶心一点,其它都没什么。
T3 又是一大坨,不给 SPJ 都无所谓(虽然我严重怀疑它的 SPJ 有问题),但是题解上说测试点 \(1,2\)“随便暴力”是什么鬼?暴力的时间复杂度只与 \(m\) 有关,\(n \le 5\) 的数据更是不伦不类,虽然这两个点的 \(m\) 确实都很小,但是题面上压根没提。这道题的第 \(5\) 个测试点更是部分分 std 都过不去(一共就三行代码能怎么错?);第 \(2,4\) 个点也莫名其妙地能够把纯暴力卡 WA,这套数据大概率不是 SPJ 写错了,就是数据生成器有问题。
T4 也爽,题面直接是错的。原题面是这样的:
一到题解上,欸,它就变成这样啦:
而后面的一条数据范围是解题所必须的,连这都能牛头不对马嘴,我也无话可说。
吐槽完毕,进入正题。
基于1的算术(add
)
这是 Codeforces 上的原题(440C)。虽说大样例依托答辩,但是我用数学方法写了一遍以后也太自信了一点,在不确定算法正确性的前提下随便测了几组 Hack 没发现错误以后就直接换题了。
以后遇到这样不确定正确性的算法,一定要打暴力对拍一下,尤其是在 T1 挂的分是承受不起的。
一定要打暴力和对拍,这花不了你多长时间。——洛谷某用户
比如这次直接挂 \(50\) 分,\(225 \rightarrow 175\),爽飞。
赛后补题参照这篇题解,后面可能我自己也会写一篇题解。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
LL n;
LL zero[20],one[20];
void Prework()
{
zero[1]=one[1]=1;
for(int i=2;i<=16;i++)
{
zero[i]=zero[i-1]*10;
one[i]=one[i-1]*10+1;
}
return;
}
int ans=0x3f3f3f3f;
void DFS(LL x,int pos,int now)
{
if(now>ans) return;
if(x==0){ans=min(ans,now);return;}
if(x<0) x=-x;
if(x/zero[pos]==0){DFS(x,pos-1,now);return;}
LL r1=x; int add1=0;
while(r1>=zero[pos])
{
r1-=one[pos];
add1+=pos;
}
DFS(r1,pos-1,now+add1);
LL r2=one[pos+1]-x; int add2=pos+1;
while(r2>=zero[pos])
{
r2-=one[pos];
add2+=pos;
}
DFS(r2,pos-1,now+add2);
return;
}
int main()
{
freopen("add.in","r",stdin);
freopen("add.out","w",stdout);
scanf("%lld",&n);
Prework();
DFS(n,15,0);
printf("%d\n",ans);
return 0;
}
逃离(car
)
目测绿的样子(而且不是上位绿),算是结论题。
做题时思维没能打开,只想到某辆车离开与前一辆车有关,而没想到一路推过去,前一辆车又与更前面的车相关,进而某一辆车是否能离开与前面所有车都有关。
但是有了这个结论还不够,还要想到把这个结论反过来:当前车会影响后面所有车,只有当到达某个位置的时候才不会影响后面车的离开。
最后优先队列处理最大值什么的就都很好想了。
const int N=3e5+5,M=3e5+5;
int n,t,m,k;
struct Rain{
long long l,r,v;
}car[N];
#define PDI pair<double,int>
priority_queue<PDI> pq;
long long sum[N];
bool cmp(Rain x,Rain y){return x.l<y.l;}
int main()
{
freopen("car.in","r",stdin);
freopen("car.out","w",stdout);
read(n),read(t),read(m),read(k);
bool is_d23=true;
for(int i=1;i<=n;i++)
{
read(car[i].l),read(car[i].r),read(car[i].v);
if(car[i].v!=car[1].v) is_d23=false;
}
sort(car+1,car+n+1,cmp);
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+car[i].r-car[i].l;
double need_ti=1.0*(sum[i-1]+t-car[i].l)/car[i].v;
pq.push({need_ti,i});
}
for(int i=1;i<=m;i++)
{
PDI x=pq.top(); pq.pop();
int p=x.second;
car[p].v+=k;
double need_ti=1.0*(sum[p-1]+t-car[p].l)/car[p].v;
pq.push({need_ti,p});
}
printf("%.3lf\n",pq.top().first);
return 0;
}
南斯拉夫(yugo
)
恶心,等先把 SPJ 错误的问题解决了再说吧。
数数(count
)
好家伙,数据范围都标错了,如果数据范围是对的的话其实还蛮简单的(可惜它没对),难度绿左右,主要就是考了一点数学能力。
这种题的经典套路就是要将式子左右两边转化成各只有一个变量,本题中最重要的两步就是设 \(x=a_i+1\) 和左右两边同时乘以 \((x+y)\),而后面的那一步因为数据范围错误导致无法保证 \(x+y \neq p\) 而无法进行。
另外三次方差因式分解公式也需要牢记:\(x^3 \pm y^3 = (x \pm y)(x^2 \mp xy +y^2)\)。
官方题解:
const int N=5e5+5;
int n,p;
__int128 a[N];
map<__int128,int> mpx,mpy;
#define cube(x) ((x)*(x)*(x)%p)
#define sqr(x) ((x)*(x)%p)
#define mod(x) (((x)%p+p)%p)
int main()
{
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
read(n),read(p);
long long ans=0;
for(int i=1;i<=n;i++)
{
read(a[i]);
__int128 x=mod(cube(a[i]+1)-sqr(a[i]+1));
__int128 y=mod(-cube(a[i])-sqr(a[i]));
ans+=mpy[x]; mpy[y]++;
ans+=mpx[y]; mpx[x]++;
}
write(ans,'\n');
return 0;
}
标签:2024.11,return,int,题解,pos,long,12,模拟,define
From: https://www.cnblogs.com/jerrycyx/p/18542170