已经咕了三场了，看这场好像数学题比较多，特意来补补。。
这题范围爆longlong，需要更大的范围，例如__int128。
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6+5; inline __int128 read(char *S){ __int128 X = 0;int i=0; int flag=1; if(S[0]=='-'){ i++;flag=-1; } while(S[i]>='0'&&S[i]<='9') X=X*10+S[i]-'0',++i; return X*flag; } void print(__int128 x) { if(x < 0) { x = -x; putchar('-'); } if(x > 9) print(x/10); putchar(x + '0'); } int main(){ __int128 a,b; char A[110],B[110]; while(~scanf("%s%s",A,B)){ a = read(A); b = read(B); __int128 ans = a/b; if(a>0 && b<0 || a<0 && b>0) { if(a<0) a=-a; if(b<0) b=-b; if(a%b){ ans += -1; } } if(a<0 && b<0) { a=-a; b=-b; ans = a/b; } print(ans); printf("\n"); } return 0; }n个点,m条边的有向无环图，q次操作。
最初每个节点的颜色都是白色。
每次操作选择一个点，将白色变成黑色，或者将黑色变成白色。。
问多少个点对（u,v）u到v的路径上全是白色的。
拓扑排序一下，然后用bitset维护能到达这个点的祖先节点有哪些。。
bit[i][j]表示能从j节点到达i节点。与父亲节点或运算一下就可以了。
/* 这题不是问有多少个路径，那么就不能用累加型的拓扑排序了，只能用bitset？？ */ #include<bits/stdc++.h> using namespace std; typedef long long ll; int n,m,q; const int N=3e2+10; vector<int>G[N]; int col[N],du[N],d[N],tx[N]; int bfs() { bitset<310>bit[310]; queue<int>que; for(int i=1;i<=n;++i){ d[i]=du[i],tx[i]=0; bit[i][i]=1; if(d[i]==0)que.push(i); } while(que.size()) { int u=que.front();que.pop(); for(int v:G[u]) { if(col[u]==0&&col[v]==0) { bit[v]|=bit[u]; } d[v]--; if(d[v]==0) que.push(v); } } int ans=0; for(int i=1;i<=n;++i) { ans+=bit[i].count()-1; } return ans; } int main() { while(~scanf("%d%d%d",&n,&m,&q)) { for(int i=1;i<=n;++i) col[i]=0,G[i].clear(),du[i]=0; for(int i=1;i<=m;++i) { int u,v;scanf("%d%d",&u,&v); G[u].push_back(v); du[v]++; } while(q--) { int u; scanf("%d",&u); col[u]=1-col[u]; printf("%d\n",bfs()); } } }由于n=50001
可以想到n^2log(n)的做法，但是会超时，所以只能O(N^2)的做法
因为删除了一个数，那么当前数的LIS值肯定是在原LIS值或者原LIS-1，所以我们就不需要二分去查找当前值应该属于哪个位置了，加入当前数的原LIS值为b我们只需要判断v[b]是否小于a[i],如果不是那v[b-1]肯定小于a[i],然后就降低了一个log。
#include<bits/stdc++.h> using namespace std; const int N=5e3+10; int n,v[N],L[N],a[N],d[N]; typedef long long ll; void LIS() { int len=0; L[0]=0; for(int i=1;i<=n;++i) { if(a[i]>L[len]){ L[++len]=a[i]; d[i]=len; } else{ int id=lower_bound(L+1,L+1+len,a[i])-L; L[id]=a[i]; d[i]=id; } } } int main() { while(~scanf("%d",&n)) { for(int i=1;i<=n;++i) scanf("%d",&a[i]); LIS(); for(int i=1;i<=n;++i) { for(int i=1;i<=n;++i) v[i]=n+1; ll ans=0; for(int j=1;j<=n;++j) { if(i==j) continue; if(v[d[j]-1]<a[j]){ ans^=(d[j]*d[j]); v[d[j]]=min(v[d[j]],a[j]); } else{ ans^=((d[j]-1)*(d[j]-1)); v[d[j]-1]=min(v[d[j]-1],a[j]); } } printf("%lld ",ans); } puts(""); } }这种题，我不太会。。。。
由于A,B,C都不太大，那么只需要考虑-1000<x,y<1000时的答案就可以了。。暴力打表即可。
也有的人随机造1000个数，判断函数是否有小于零的。。。。
#include<bits/stdc++.h> using namespace std; int main(){ int a,b,c; while(cin>>a>>b>>c){ if(a < 0){ cout<<"No"<<endl; } else if(a == 0){ if(b == 0){ if(c>=0){ cout<<"Yes"<<endl; } else{ cout<<"No"<<endl; } } else{ cout<<"No"<<endl; } } else{ if(b*b - 4*a*c <= 0){ cout<<"Yes"<<endl; } else{ cout<<"No"<<endl; } } } return 0; }容斥原理，和2018类似，不过刚开始我居然写炸了，忘记减去重复计算的部分了。。
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll a,b,c,d; while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&d)) { ll t1=b-a+1; ll t2017=b/2017-(a-1)/2017; ll t2=d-c+1; ll t2018=d/2017-(c-1)/2017; ll ans=t1*t2018+t2017*t2-t2017*t2018; printf("%lld\n",ans); } }已经告诉你s3的O（1）计算方式了，那么枚举第四个数，前三个数用o（1）公式即可。o（1）公式就是一堆前缀和。。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; const int N=1e5+10; ll powmod(ll a,ll b) { ll res=1; for(;b;b>>=1){ if(b&1) res=res*a%mod; a=a*a%mod; } return res; } ll a1[N],a2[N],a3[N],a4[N],a[N]; int n; int main() { while(~scanf("%d",&n)) { a1[0]=a2[0]=a3[0]=a4[0]=0; for(int i=1;i<=n;++i){ scanf("%lld",&a[i]); a1[i]=(a1[i-1]+a[i])%mod; a2[i]=(a2[i-1]+a[i]*a[i]%mod)%mod; a3[i]=(a3[i-1]+a[i]*a[i]%mod*a[i]%mod)%mod; } if(n<4) { printf("0\n");continue; } ll ans=0; for(int i=4;i<=n;++i) { int m=i-1; ans=(ans+a[i]*(a1[m]*a1[m]%mod*a1[m]%mod-3*a2[m]%mod*a1[m]%mod+2*a3[m]%mod+3*mod)%mod*powmod(6,mod-2)%mod)%mod; } printf("%lld\n",ans); } }
