个人赛 FGH补题（二分+取模+set）

DIJ大水题略过，C另外开一篇

G 潘神的魔鬼训练（二分）

暴力n^3肯定TLE，由三角形给出两边长度a,b，第三边长度限制为/a-b/~a+b，二分查找即可

记得排序。。

#include <bits/stdc++.h> using namespace std; int a[1005],b[1005],c[1005]; int main() { int N,M,L; cin>>N>>M>>L; for(int i=0;i<N;i++)scanf("%d",&a[i]); for(int i=0;i<M;i++)scanf("%d",&b[i]); for(int i=0;i<L;i++)scanf("%d",&c[i]); sort(c,c+L);//二分一定要记得排序 int sum=0; for(int i=0;i<N;i++){ for(int j=0;j<M;j++){ cout<<i<<" "<<j<<" "<<lower_bound(c,c+L,a[i]+b[j]) -c<<endl; // cout<<(upper_bound(c,c+L,abs(b[j]-a[i]))-c) <<endl; sum+=lower_bound(c,c+L,a[i]+b[j]) -upper_bound(c,c+L,abs(b[j]-a[i])) ; } } cout<<sum<<endl; }

 

H 奇奇的splay（STL）

splay也可以但是这里没有翻转操作，set可以水过

这里set遍历有点生疏了

#include <bits/stdc++.h> using namespace std; set<int>mp; char str[20]; int a[200005]; int n,m,x,y,D,P,T; int main() { scanf("%d",&n); int k=n; for(int i=0;i<n;i++) scanf("%d",&a[i]),mp.insert(a[i]); scanf("%d",&m); while(m--) { scanf("%s",str); if(strcmp(str,"INSERT")==0) { scanf("%d",&P); mp.insert(P); } else if(strcmp(str,"DELETE")==0) { scanf("%d",&x); mp.erase(x); } else { if(!mp.empty()) printf("%d %d\n",*mp.begin(),*(--mp.end()));//最后一个元素 else printf("EMPTY\n"); } } return 0; }

F 后退，迪鸿哥要装X了

由于avg会变，所以把平方和式子拆开计算

①加减、乘后每一步都要取模，以后取模最好分开分步骤写

②取模后运算很可能出现负数，所以sx开什么unsigned long long！

#include <bits/stdc++.h> using namespace std; typedef long long ll;//别用unsigned long long！ 取模后可能为负 ll DH[1000010]; ll t[1000010]; ll fa[1000010]; ll JZ; ll n; int DHG(int i){ int sum = 0; for(int j=1; j < i; j++){ sum += DH[j]; } int avg = sum / (i - 1); //注意，此处为向下取整 DH[i] = 0; for(int j=1; j < i; j++){ DH[i] += (DH[j] - avg) * (DH[j] - avg); } DH[i] = DH[i] % JZ; //JZ又是另一个神秘数字了，你只需要知道%JZ就行了。 } void init(){ for(ll j=2; j < n+10; j++){ ll avg = t[j-1] /(j - 1); //注意int avg%=JZ; DH[j] = ((fa[j-1]-2*t[j-1]%JZ*avg%JZ)%JZ+(j-1)*avg%JZ*avg%JZ)%JZ+JZ;//拆项 DH[j] = DH[j] % JZ; //cout<<DH[j]<<endl; fa[j]=(fa[j-1]+DH[j]*DH[j]%JZ)%JZ+JZ; fa[j]%=JZ; t[j]= t[j-1]+DH[j]; // t[j]%=JZ;和不用% } } int main() { int T; cin>>T; while(T--){ scanf("%lld%lld%lld",&DH[1],&JZ,&n);//cin>>DH[1]>>JZ>>n; t[1]=DH[1]; fa[1]=t[1]*t[1]%JZ; init(); printf("%lld\n",(DH[n]+JZ)%JZ); } }