Oi

一个叫做整体二分的东西。 单个国家可以二分。 为了节约时间，可以把情况相同的一同二分。 可以用树状数组做必要的统计。 时间复杂度不明。 code: #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; int n,m; vector<int> has[300005]; int p[300005]; typedef long long LL; LL c[300005]; int k,T; int l[300005],r[300005], a[300005]; int ans[300005]; int id[300005]; bool mark[300005]; int tmp[300005]; #define lowbit(x) ((x)&-(x)) void add(int x,int k){ while(x<=m){ c[x]+=k; x+=lowbit(x); } } LL ask(int x){ LL ret=0; while(x>0){ ret+=c[x]; x-=lowbit(x); } return ret; } void Add(int x,int f){ if(l[x]<=r[x]){ add(l[x],f*a[x]); add(r[x]+1,-f*a[x]); }else{ add(l[x],f*a[x]); add(1,f*a[x]); add(r[x]+1,-f*a[x]); } } void solve(int l,int r,int L,int R){ if(L>R) return; if(l==r){ for(int i=L;i<=R;i++){ ans[id[i]]=l; } }else{ int mid=(l+r)>>1; while(T<mid) T++,Add(T,1); while(T>mid) Add(T,-1),T--; for(int i=L;i<=R;i++){ LL tmp=0; for(int j=0;j<has[id[i]].size();j++){ tmp+=ask(has[id[i]][j]); if(tmp>=p[id[i]]) { mark[id[i]]=1;break; } } } int cc=0,tot=0; for(int i=L;i<=R;i++){ if(mark[id[i]]){ id[L+cc]=id[i]; cc++; }else{ tmp[tot++]=id[i]; } } for(int i=L;i<L+cc;i++) mark[id[i]]=0; for(int i=0;i<tot;i++) id[L+cc+i]=tmp[i]; solve(l,mid,L,L+cc-1),solve(mid+1,r,L+cc,R); } } int main(){ scanf("%d%d",&n,&m); for(int i=1,x;i<=m;i++) scanf("%d",&x),has[x].push_back(i); for(int i=1;i<=n;i++) scanf("%d",&p[i]); scanf("%d",&k); for(int i=1;i<=k;i++){ scanf("%d%d%d",&l[i],&r[i],&a[i]); } k++; l[k]=1,r[k]=m,a[k]=0x3fffffff; for(int i=1;i<=n;i++) id[i]=i; solve(1,k,1,n); for(int i=1;i<=n;i++){ if(ans[i]==k) puts("NIE"); else printf("%d\n",ans[i]); } return 0; }

不知道OI是啥或者信息学竞赛是啥的可以按Ctrl+W。 很早开始写的。。准备出分之后再发布。 谨以此文纪念我信息学竞赛的第一次正式考试。 考前一些天写的: 11.5 下午想转发一下去年的RP++的说说。发现去年没有发(或被删？)。。 ...

题解： 简单的说就是给定平面上n个点，求这n个点组成三角形的最小面积。 如果分别枚举三个点的话是$O(n^3)$的，时间无法承受。 如果枚举了两个点a,b。设它们间的距离是L。如果以点a,b所在直线为y轴的话，与其他点所组成的三角形的面积$S=L*|x|/2$，x是其他点在这个坐标系中的横坐标。可以看出面积最小的就是离这个坐标系y轴最近的一个点。如果我们能够快速的得知最近的点的话，就可以将复杂度降低到$O(n^2)$。 ...

题解： 参考小胖的奇偶那道题。 那道题用的并查集维护。 如果知道 i..j 之间奇偶性的话，实际上知道的是 sum[j]-sum[i-1]的奇偶性（sum为前缀和）。 ...

题解: 鉴于F[44]> 1e9。于是可以把两两乘积算出来，枚举即可。 code: #include<cstdio> #include<cstring> #include<algorithm> #include<set> //by zrt //problem: using namespace std; int f[46]; set<int> s; int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif f[0]=0;f[1]=1; for(int i=2;i<=45;i++){ f[i]=f[i-1]+f[i-2]; } int MAX=1e9; for(int i=0;i<=45;i++) s.insert(f[i]); for(int i=3;i<=45;i++){ for(int j=i;j<=45;j++){ if(f[i]*1LL*f[j]<=MAX){ s.insert(f[i]*f[j]); } } } int t,x; scanf("%d",&t); while(t--){ scanf("%d",&x); if(s.count(x)){ puts("TAK"); }else{ puts("NIE"); } } return 0; }

题解： 若d[x]<a[x]，杀这个怪是有收益的，可以按d值从小到大杀。 若d[x]>a[x]，考虑反过来的过程，如果都杀完后血量是S，那么从后向前就是 S-a[i]+d[i]，相当于第一种情况，需要按a值从大到小杀。 ...

题解： 定义F[i]为前 i-1 只奶牛工作效率的最大值。 sum[i]是Ei的前缀和。 有F[i]=max{F[j]+sum[i-1]-sum[j]} (i-j<k) 可以用单调队列维护 F[j]-sum[j] 。 ...

题解： 不能盖住好地，那么宽为1的木板只能放在行、列连通块里。 所以行、列连通块对应左、右部中的点，泥地对应边。 求二分图最小覆盖就是答案。 二分图最小点覆盖==最大匹配 ...

题解： 题意是问你一个混合图是否存在负环。 spfa即可，开始时将所有点入队，求最短路，当最短路长度超过n时，说明有负环。 code: #include<cstdio> #include<cstring> #include<algorithm> #include<queue> //by zrt //problem: using namespace std; int n,m,w; int H[505],X[6000],P[6000],E[6000]; int d[505],l[505]; int tot; inline void add(int x,int y,int z){ P[++tot]=y;X[tot]=H[x];H[x]=tot;E[tot]=z; } int tt; queue<int> q; int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); #endif scanf("%d",&tt); while(tt--){ memset(H,0,sizeof H); tot=0; scanf("%d%d%d",&n,&m,&w); for(int i=1,x,y,z;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } for(int i=1,x,y,z;i<=w;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,-z); } memset(d,0,sizeof d); memset(l,0,sizeof l); while(!q.empty()) q.pop(); for(int i=1;i<=n;i++) q.push(i); bool have=0; while(!q.empty()){ int x=q.front();q.pop(); // printf("%d %d %d\n",x,d[x],l[x]); for(int i=H[x];i;i=X[i]){ if(d[P[i]]>d[x]+E[i]){ d[P[i]]=d[x]+E[i]; q.push(P[i]); l[P[i]]=l[x]+1; if(l[P[i]]>n) { have=1;goto ed; } } } } ed:; if(have) puts("YES"); else puts("NO"); } return 0; }

题目链接 昨天mhr神犇，讲分治时的CDQ分治的入门题。 题意: 你有一个wxw正方形的田地。 初始时没有蝗虫。 给你两个操作： 1 x y z： (x,y)这个位置多了z只蝗虫。 ...