这次是校内OJ(HHHOJ)线上比赛,网址:http://211.140.156.254:2333/contest/51
(我去刚刚快写完了手贱关掉了)
这次总体难度也不高,T1&&T2都是TG难度的题(可能还更低),T3要用到主席树(这个以后再说)大力切,但60分的暴力还是很好水的。
所以 100+100+60=260分是可以拿的(然而我只拿了160,T2爆0了)
先%一下dalao:
yu'ao dalao 260又是RANK 1
陈潇然 dalao 199 小学生虐场
CJJ dalao 15 光荣炸裂,死而无憾地垫底(%%%)
然后开始讲题
T1 比赛的时候被我用玄学二分给艹过去了,到现在都不懂标算
%一下CJJ dalao的均值不等式
主要讲一下二分。由于n在1e5的范围内,1e4包括5位小数总共是1e9,1e5*log2(1e9)好像可以,没有犹豫地上二分
这里不推荐*10000再转化成整数来做,可能会有爆精度的危险。因此根据范围设立一个阙值来调l,r即可
对于mid要根据情况实际调整,每个水杯要用的水量可以直接通过一元一次方程来算。
最后有一个小技巧:通过sscanf和sprintf来将一个数四舍五入到某一位
具体看代码
CODE
#include<cstdio> #include<cstring> using namespace std; typedef double DB; const DB E=0.00001; const int N=100005; int n,i; DB T,C,t[N],c[N],MIN,MAX,l,r,mid,ans; bool flag=0; inline void search(DB x) { DB res=0; for (i=1;i<=n;++i) { if (t[i]>x&&T>=x) { l=mid; return; } if (t[i]<x&&T<=x) { r=mid; return; } res+=c[i]*(t[i]-x)/(x-T); } if (res<=C) l=mid; else { if (T<x) l=mid; else r=mid; } } inline bool check(DB x) { DB res=0; for (i=1;i<=n;++i) { if (t[i]>x&&T>=x) return 0; if (t[i]<x&&T<=x) return 0; if (t[i]-x==0) continue; res+=c[i]*(t[i]-x)/(x-T); } return res<=C; } int main() { //freopen("A.in","r",stdin); freopen("A.out","w",stdout); scanf("%d",&n); scanf("%lf%lf",&T,&C); MIN=MAX=T; for (i=1;i<=n;++i) { scanf("%lf%lf",&t[i],&c[i]); MIN=t[i]<MIN?t[i]:MIN; MAX=t[i]>MAX?t[i]:MAX; } l=MIN,r=MAX; while (r-l>E) { mid=(double)(l+r)/2; search(mid); } char temp[100]; sprintf(temp,"%.4lf",l); sscanf(temp,"%lf",&ans); if (check(ans)) printf("Possible %.4lf",ans); else printf("Impossible"); return 0; }
T2 一道大力枚举,然后我一直在想欧拉筛和排列组合云云。
令 a<=b<=c,枚举a,b,就可以确定出c的范围
然后就可以直接更新答案了(不同的排列算作不同的答案)
其实读懂题意最重要
CODE
#include<cstdio> using namespace std; const int MOD=1000000007; int i,j,k,n; long long ans; int main() { scanf("%d",&n); for (i=1;i*i*i<=n;++i) for (j=i;i*j*j<=n;++j) { k=n/i/j; if (k<j) break; if (i^j) ans=(ans+(k-j)*6+3)%MOD; else ans=(ans+(k-j)*3+1)%MOD; } printf("%d",(int)ans); return 0; }
复杂度 O(3√(n2))
T3 关于异或的题目也做过不少,不过这个无能为力(要主席树强制维护在线)
以下是吴嘉龙巨佬的Sol
Solution-Manchery
考虑sr xor si−1≤sr+1 xor si−1sr xor si−1≤sr+1 xor si−1
相当于对si−1si−1第k位有一个限制 k是srsr和sr+1sr+1的LCP后一位
然后就能很快算出每个点向右的答案
强制在线用主席树维护
ps.其实跟上文本质一样,akak的最大非 00 位就是 sk−1sk−1和sksk的LCP
好,我们来看60分的暴力,就是枚举左端点(l~r),同时不断向右^是否可行,不行就break
CODE
#include<cstdio> #include<iostream> using namespace std; const int N=2005; int n,t,last,a[N],q,x,y,ans,res,i,j; inline void read(int &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } inline void write(int x) { if (x/10) write(x/10); putchar(x%10+'0'); } int main() { //freopen("C.in","r",stdin); freopen("C.out","w",stdout); read(n); read(t); for (i=1;i<=n;++i) read(a[i]); read(q); while (q--) { ans=0; read(x); read(y); x=(x+last*t)%n+1; y=(y+last*t)%n+1; if (x>y) swap(x,y); for (i=x;i<=y;++i) { res=0; for (j=i;j<=y;++j) if ((res^a[j])>=res) res^=a[j],ans++; else break; } write(last=ans); putchar(' '); } return 0; }