NOIP2015停课日记
开个坑记录一下联赛期间的颓废生活
10.15 把昨天晚上WA的扫描线调了一下A了，这道题特别youginzi，不仅要离散化，而且n还小于5000，直接暴力能过。。十分不爽往OJ上放了一个加强版
【POI1999】空立方体问题 一维排序，一维建线段树，剩下一维单调，求出每个平面上面积更新答案
#include<cstdio>
#include<algorithm>
#define W 1000000
#define N 20200
using namespace std;typedef long long LL;
int i,j,n,ux,uy,uz,cnt,v[N],w[3];LL ans;
struct P{int x,y,z;}p[N];
struct T{LL lv,rv,r,v,la,a,b;}t[N<<2];
bool cmp(P a,P b){return a.z<b.z;}
void add(int k,int z){t[k].b=t[k].la=t[k].lv=t[k].rv=z;t[k].v=t[k].r*z;t[k].a=t[k].r;}
void pd(int k){if(t[k].la)add(k<<1,t[k].la),add(k<<1|1,t[k].la),t[k].la=0;}
void ps(int k){
t[k].v=max(t[k<<1].v,t[k<<1|1].v);
if(t[k<<1].v>t[k<<1|1].v||t[k<<1].v==t[k<<1|1].v&&t[k<<1].a<t[k<<1|1].a)t[k].a=t[k<<1].a,t[k].b=t[k<<1].b;else t[k].a=t[k<<1|1].a,t[k].b=t[k<<1|1].b;
t[k].lv=t[k<<1].lv;t[k].rv=t[k<<1|1].rv;
}
void cha(int k,int l,int r,int x,int z){
if(x>cnt)return;
pd(k);if(t[k].lv<=z)return;
if(t[k].rv>z&&x<=l){add(k,z);return;}
int mid=l+r>>1;if(x<=mid)cha(k<<1,l,mid,x,z);
cha(k<<1|1,mid+1,r,x,z);ps(k);
}
void bt(int k,int l,int r){
t[k].a=t[k].r=v[r];t[k].b=t[k].lv=t[k].rv=W;t[k].v=t[k].r*W;
if(l==r)return;int mid=l+r>>1;
bt(k<<1,l,mid);bt(k<<1|1,mid+1,r);
}
void get(LL w,int x,int y,int z){if(w>ans||w==ans&&x<ux||w==ans&&x==ux&&y<uy)ans=w,ux=x,uy=y,uz=z;}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z),v[i]=p[i].x;
p[++n]=P{W,W,W};v[n]=W;sort(p+1,p+n+1,cmp);sort(v+1,v+n+1);cnt=unique(v+1,v+n+1)-(v+1);
for(bt(1,1,cnt),i=1;i<=n;i++)get(t[1].v*p[i].z,t[1].a,t[1].b,p[i].z),cha(1,1,cnt,lower_bound(v+1,v+cnt+1,p[i].x)-v+1,p[i].y);
printf("%d %d %d",ux,uy,uz);
}
然后把后缀自动机重学了一下，发现一直把RIGHT集合理解错了。。
然后把昨天写挂的模拟赛题再调了一下，改了一下RIGHT集合的求法摞摞干就A了
【十月模拟赛】T2 给A串建后缀自动机，B串在上面跑，统计答案就行了，具体看后缀自动机那篇文章
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200100
#define CL(a) memset(a,0,sizeof(a))
using namespace std;typedef long long LL;LL ans;
int n,i,c,p,q,np,nq,la,tmp,cnt,now,L,S,son[N][26],f[N],st[N],fa[N],sz[N],b[N],pos[N];char s[N];
void add(int c,int w){
for(p=la,np=son[p][c],st[np=la=++cnt]=st[p]+1;p&&!son[p][c];p=fa[p])son[p][c]=np;
if(!p)fa[np]=S;else if(st[p]+1==st[q=son[p][c]])fa[np]=q;else{
nq=++cnt;st[nq]=st[p]+1;memcpy(son[nq],son[q],sizeof son[q]);
for(fa[nq]=fa[q],fa[q]=fa[np]=nq;p&&son[p][c]==q;p=fa[p])son[p][c]=nq;
}
}
int main(){
for(;scanf("%d",&L)!=-1;printf("%lld\n",ans)){
CL(sz);CL(son);CL(fa);CL(st);CL(f);CL(b);ans=cnt=0;
for(scanf("%s",s),n=strlen(s),S=la=++cnt,i=0;i<n;i++)add(s[i]-'a',1);
for(i=1;i<=cnt;i++)b[st[i]]++;
for(i=1;i<=n;i++)b[i]+=b[i-1];
for(i=1;i<=cnt;i++)pos[b[st[i]]--]=i;
for(i=0,p=1;i<n;i++)sz[p=son[p][s[i]-'a']]++;
for(i=cnt;i;i--)sz[fa[pos[i]]]+=sz[pos[i]];
for(scanf("%s",s),n=strlen(s),p=1,tmp=i=0;i<n;i++){
if(son[p][c=s[i]-'a'])p=son[p][c],tmp++;else{
for(;!son[p][c]&&p;p=fa[p]);
if(!p)p=1,tmp=0;else tmp=st[p]+1,p=son[p][c];
}
if(tmp>=L)ans+=(LL)(tmp-max(L,st[fa[p]]+1)+1)*sz[p],f[fa[p]]+=st[fa[p]]>=L;
}
for(i=cnt;i;i--){
ans+=(LL)f[p=pos[i]]*(st[p]-max(L,st[fa[p]]+1)+1)*sz[p];
if(st[fa[p]]>=L)f[fa[p]]+=f[p];
}
}
}
然后下午又做了马三的神题，%%%
10.16 早上做了一道线段树传一堆标记的题，最后改得和标程一模一样了还是WA，然后当自己会做弃疗了。。
晚上看了一道普及组的题，可是不会做，做了1H+还是没做出来弃疗了。。然后YY大爷马上就把这道题秒了
快走的时候看了一道博弈题，YY大爷马上打了个表，然后规律就很明显了。。
【COCI2010】HRPA 就是不断减去斐波那契数就行了
#include<cstdio>
long long n,i,f[85];
int main(){
for(f[1]=1,f[2]=2,i=3;i<=80;i++)f[i]=f[i-1]+f[i-2];
for(scanf("%lld",&n);n;n-=f[i-1]){
for(i=1;f[i]<=n;i++);
if(n==f[i-1])return printf("%lld",n),0;
}
}
然后临走前又看了一道题回去想，晚上差不多想出来了
10.17 早上来把昨天那道题秒了
【COCI2012】Sort 考虑一开始换完后每次也只能一个一个换，所以可以先求出逆序对，再减去可以一次换的代价
#include<cstdio>
int n,i,x,w,la,c[100100];long long u,ans;
void ins(int x){for(;x<=n;x+=x&-x)c[x]++;}
int qu(int x){for(w=0;x;x-=x&-x)w+=c[x];return w;}
int main(){
for(scanf("%d",&n),la=1e9,i=1;i<=n;la=x,i++){
scanf("%d",&x);ans+=qu(n)-qu(x);ins(x);
if(x<la)u++;else{ans-=u*(u-1)/2;if(u>1)ans++;u=1;}
}
ans-=u*(u-1)/2;if(u>1)ans++;printf("%lld",ans);
}
上午做了一下XJOI模拟赛，T1很简单，T2一开始写了60分，然后想了想觉得只能小范围容斥大范围暴力了。。然后YY大爷把这道题“秒”了，说这就是一道SB题，就交了一个看似正确的程序，但回来发现只有20分。。
T1 按位运算就可以了，不过我的对拍程序写错了，以致于一直找不出错误。。
#include<cstdio>
#include<algorithm>
#define N 100100
using namespace std;typedef long long LL;
LL n,x,i,j,f[36],g[36],pw[36];LL now,ans,a[N];
int main(){
for(pw[0]=1,i=1;i<=35;i++)pw[i]=pw[i-1]*2;
for(scanf("%lld%lld",&n,&x),i=1;i<=n;i++)for(scanf("%lld",&a[i]),j=35;j>=0;j--)if(a[i]&pw[j])f[j]++;
for(i=1;i<=n;ans=max(ans,now),i++){
for(j=35;j>=0;j--)g[j]=f[j];
for(j=35;j>=0;j--)if(a[i]&pw[j])g[j]--;
for(j=35;j>=0;j--)if((a[i]*x)&pw[j])g[j]++;
for(now=0,j=0;j<=35;j++)if(g[j])now+=pw[j];
}
printf("%lld",ans);
}
T2 gcd以后暴力就是60分，100分还不知道怎么做。。
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,i,j,cnt,ans,a[51];bool f[50001000];
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=m;i++)scanf("%d",&a[i]),a[i]=gcd(n,a[i]);
sort(a+1,a+m+1);cnt=unique(a+1,a+m+1)-a-1;
for(i=1;i<=cnt;i++)for(j=0;j<n;j+=a[i])f[j]=1;
for(i=0;i<n;i++)if(!f[i])ans++;
printf("%d",ans);
}
T3也被YY大爷秒了，大家快去%
然后下午写了会作业，背了会英语，然后就去睡觉了，一觉醒来发现已经下课了，赶紧去跳长绳，跳完又踢了会球，于是整个下午都浪掉了
在BC之前赶紧切了一道PA，就是找出三元环判一下就可以了。。一个地方写炸了看了10min。。
【PA2009】Cakes 把所有三元环找出来就行了，找的方法是度数小的连大的，时间复杂度O(m^1.5)
#include<cstdio>
#include<algorithm>
#define N 100100
#define M 250200
using namespace std;
int n,m,i,j,x,y,tot,v[N],a[N],X[M],Y[M],du[N],fir[N],la[M],ne[M];long long ans;
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=m;i++)scanf("%d%d",&X[i],&Y[i]),du[X[i]]++,du[Y[i]]++;
for(i=1;i<=m;i++)du[X[i]]<du[Y[i]]?ins(X[i],Y[i]):ins(Y[i],X[i]);
for(x=1;x<=n;x++){
for(i=fir[x];i;i=ne[i])v[la[i]]=x;
for(i=fir[x];i;i=ne[i])for(j=fir[y=la[i]];j;j=ne[j])if(v[la[j]]==x)ans+=max(max(a[x],a[y]),a[la[j]]);
}
printf("%lld",ans);
}
晚上小号打了BC，临版一时爽，最后40min写T4也用正确方法写出来了，可惜WA了，然后8:30关寝室门就走了。。第二天早上来发现所有题目都FST了，真是太爽了。。虽然算法是对的，但每个程序都有这样那样的问题。。不过反正是小号，就当攒人品了
10.18 上午订正了一下昨天的BC和XJOI，发现BC的几道题方法都是对的，全是自己作死。。
浪了一个中午半个下午，吃完饭前把以前一到黈力的题做了下，以前只是在线段树上建出最短路图然后直接暴力跑，但是没有利用只有权为1的边的性质，这样就可以直接线段树上拉链BFS了。。
【PA2011】Journeys 在线段树上拉链建出图，用set维护没被走过的点，然后BFS就行了，注意走过的边不会再走，要删去
#include<cstdio>
#include<algorithm>
#include<set>
#define N 500010
#define M 9000000
using namespace std;
int n,m,s,x,y,i,h,t,e,X,Y,tp,tot,L[M],R[M],fir[1048577],ne[M],pos[N],q[N],d[N];
set<int>st;set<int>::iterator it,w[N];
void ins(int k,int l,int r){
if(x<=l&&r<=y){
L[++tot]=X;R[tot]=Y;ne[tot]=fir[k];fir[k]=tot;
return;
}
int mid=l+r>>1;if(x<=mid)ins(k<<1,l,mid);
if(y>mid)ins(k<<1|1,mid+1,r);
}
void bt(int k,int l,int r){
if(l==r){pos[l]=k;return;}
int mid=l+r>>1;bt(k<<1,l,mid);bt(k<<1|1,mid+1,r);
}
int main(){
for(scanf("%d%d%d",&n,&m,&s),bt(1,1,n);m--;){
scanf("%d%d%d%d",&x,&y,&X,&Y);ins(1,1,n);
swap(x,X);swap(y,Y);ins(1,1,n);
}
for(i=1;i<=n+1;i++)if(i!=s)st.insert(i);
for(q[t=1]=s;h^t;)for(e=d[x=q[++h]]+1,x=pos[x];x;fir[x]=0,x>>=1)
for(i=fir[x];i;i=ne[i]){
for(tp=0,it=st.lower_bound(L[i]);*it<=R[i];it++)d[q[++t]=*it]=e,w[++tp]=it;
for(;tp;)st.erase(w[tp--]);
}
for(i=1;i<=n;i++)printf("%d\n",d[i]);
}
晚上切了一道COCI，这道题是染色题，但不同寻常，是棋盘染色，方法很巧妙，两个线段树互换得到答案
【COCI2011】Slika 首先很容易把操作反向得到实际的操作顺序，然后考虑如何得到答案
既然暴力染色会T，那么就先不要管顺序，先按扫描线的方法一维排序，剩下一维数据结构求解
先不考虑交替染色的情况，有区间加一个关键值，区间删一个关键值，查找每个点关键值最大值的操作
那么可以在线段树的每个节点上套一个set，来维护当前的关键值，查找的时候每层都看一下，那么一定不会错
但这道题还要交替染色，所以要两个线段树互换，当然这不需要真的换，只要对于每一行找到其对应的线段树就可以了
注意删除操作要找到原来的线段树，在这里摞了好久。。时间复杂度O(mlgnlgm+n^2lgn)
#include<cstdio>
#include<vector>
#include<set>
#define N 1010
#define M 100100
using namespace std;int n,c,m,f,a1,b1,a2,b2,i,j,o,pp,now,sv[M],ld[M];char s[9];
struct P{int z,c,x1,y1,x2,y2;}p[M];set<int> t[N<<2][2];set<int>::iterator it;vector<int>st[N],ed[N];
int G(int x){return (x&1)?f:!f;}
void cha(int k,int l,int r,int x,int y,int z,int w){
if(x<=l&&r<=y){if(w)t[k][G(x)].insert(z);else t[k][G(x^(p[o].x2-p[o].x1+1))].erase(z);return;}
int mid=(l+r)/2;if(x<=mid)cha(k<<1,l,mid,x,y,z,w);if(y>mid)cha(k<<1|1,mid+1,r,x,y,z,w);
}
void del(int x){o=x;cha(1,0,n-1,p[x].y1,p[x].y2,p[x].z,0);}
void ins(int x){cha(1,0,n-1,p[x].y1,p[x].y2,p[x].z,1);}
int qu(int k,int l,int r,int x){
int ans=-1;if(!t[k][G(x)].empty())it=t[k][G(x)].end(),ans=max(ans,*--it);
if(l==r)return ans;int mid=(l+r)/2;
x<=mid?ans=max(ans,qu(k<<1,l,mid,x)):ans=max(ans,qu(k<<1|1,mid+1,r,x));
return ans;
}
int quary(int x){int ans=qu(1,0,n-1,x);printf("%d ",ans==-1?1:p[ans].c);}
int main(){
for(scanf("%d%d%d",&n,&c,&m),i=1;i<=m;i++){
scanf("%s",s);
if(s[0]=='P')scanf("%d%d%d%d%d",&c,&a1,&b1,&a2,&b2),p[i]=P{i,c,a1,b1,a2,b2};
if(s[0]=='S')sv[i]=++now;
if(s[0]=='L')scanf("%d",&ld[i]);
}
for(i=m;i;i--){
if(ld[i])for(pp=ld[i];sv[i]!=pp&&i;i--);
if(!ld[i]&&!sv[i])st[p[i].x1].push_back(i),ed[p[i].x2+1].push_back(i);
}
for(i=0;i<n;puts(""),i++,f^=1){
for(j=0;j<ed[i].size();j++)del(ed[i][j]);
for(j=0;j<st[i].size();j++)ins(st[i][j]);
for(j=0;j<n;j++)quary(j);
}
}
然后又做了一道题，想了一会，写了个正向贪心没过样例，又想了下把贪心反向一下就能A了
【COCI2011】rijeka 考虑按左端点排序，然后什么时候回去最优；很明显如果两个区间毫无交集，那么两个区间各自解决就可以了，如果两个区间有交集，那么两个区间放到一起解决更好；如何判断两个区间是否有交集呢？可以倒序维护一个当前到达的最小值，处理出每一块，统计答案即可
#include<cstdio>
#include<algorithm>
#define N 300300
using namespace std;
int n,m,i,w,tp,my,now;long long ans;
struct P{int x,y;}p[N],q[N];
bool cmp(P a,P b){return a.x<b.x||a.x==b.x&&a.y>b.y;}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);
for(sort(p+1,p+n+1,cmp),i=1;i<=n;i++)if(p[i].y<p[i].x)q[++tp]=P{p[i].x,p[i].y};
for(my=2e9,w=i=tp;i;i--){
my=min(q[i].y,my);
if(my>q[i-1].x)ans+=2ll*(q[w].x-my),my=2e9,w=i-1;
}
printf("%lld",ans+m);
}
10.19 早上把昨天的那道题切了，发现题目有些误读，以致于想复杂了，考虑贡献就很容易了
【COCI2012】ograda 最后影响答案的一定是上升-下降-上升-下降的一个波浪序列，为了让这个更大，我们可以找出a数列中的波浪序列，把b数列中的极值给它；然后再把1和n的值确定，最后剩下的值对答案没有贡献，按要求放就可以了
#include<cstdio>
#include<algorithm>
#define N 300300
using namespace std;
int n,i,l,r,a[N],b[N],ans[N];long long sum;
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++)scanf("%d",&b[i]);
for(sort(b+1,b+n+1),l=1,i=2,r=n;i<n;i++){
if(a[i]>a[i-1]&&a[i]>a[i+1])ans[i]=b[r--];
if(a[i]<a[i-1]&&a[i]<a[i+1])ans[i]=b[l++];
}
ans[1]=a[1]<a[2]?b[l++]:b[r--];ans[n]=a[n]<a[n-1]?b[l++]:b[r--];
for(i=2;i<n;i++){
if(a[i]>a[i-1]&&a[i]<a[i+1])ans[i]=b[l++];
if(a[i]<a[i-1]&&a[i]>a[i+1])ans[i]=b[r--];
}
for(i=1;i<n;i++)sum+=abs(ans[i]-ans[i+1]);
for(printf("%lld\n",sum),i=1;i<=n;i++)printf("%d ",ans[i]);
}
然后找了道非权限题做，想歪了，搞成了求LCA的lgn乱搞，其实直接DFS就可以了。。
【AMPPZ2014】The Cave 1号点到答案的距离是max(0,(dis[a[i]]+dis[b[i]]-d[i])/2)，找到一个约束使得这个答案最远，然后对这个约束的两个点再进行扩展，找到一个离1号点最近的点，这个点可能是答案，对这个点进行一次判断即可
#include<cstdio>
#include<cstring>
#define N 300300
int T,n,m,i,x,y,u,w,tot,ans,a[N],b[N],c[N],fir[N],ne[N<<1],la[N<<1],d[3][N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa,int dis,int p){
d[p][x]=dis;
for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)dfs(la[i],x,dis+1,p);
}
int main(){
for(scanf("%d",&T);T--;memset(fir,0,sizeof(fir)),tot=0){
for(scanf("%d%d",&n,&m),i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
for(dfs(1,0,0,0),ans=-1e9,i=1;i<=m;i++){
scanf("%d%d%d",&a[i],&b[i],&c[i]);
if(d[0][a[i]]+d[0][b[i]]-c[i]>ans)ans=d[0][a[i]]+d[0][b[i]]-c[i],u=i;
}
for(dfs(a[u],0,0,1),dfs(b[u],0,0,2),w=0,i=1;i<=n;i++)if(d[1][i]+d[2][i]<=c[u])if(d[0][i]<ans||!w)ans=d[0][i],w=i;
for(dfs(w,0,0,0),i=1;i<=m;i++)if(d[0][a[i]]+d[0][b[i]]>c[i]){w=0;break;}
if(!w)puts("NIE");else printf("TAK %d\n",w);
}
}
继续做AMPPZ，做了一道调整构造方案的题，其实主要是画图。。不过把起点搞错了，而且n和m好难分清啊。。
【AMPPZ2014】Pillars 先把没有障碍的方案构造出来，然后画图，可以发现有一下几种情况：
①中心点的x坐标为奇数，那么把它绕过去就可以了
②中心点的x坐标为偶数，且y≠3，也可以把它绕过去
③中心点的x坐标为偶数，且y=3，这种情况不能绕过去，走过去的时候扭一下脖子处理
#include<cstdio>
int n,m,k,i,j,x,y;char c[1010][1010];
int main(){
for(scanf("%d%d%d",&n,&m,&k),i=1;i<=n;i++)for(j=1;j<=m;j++)c[i][j]=i&1?'D':'G';
for(i=1;i<n;i++)c[i][1]='P';for(i=2;i<=n;i+=2)c[i][m]='L';for(i=3;i<=n;i+=2)c[i][2]='L';
for(i=1;i<=k;i++){
scanf("%d%d",&x,&y);
if(x&1)c[x+1][y-1]='L',c[x+1][y+2]='P',c[x][y+2]='P',c[x+2][y+3]='L';
else if(y==3)c[x][1]='G',c[x][2]='P',c[x+1][2]='D',c[x+1][5]='L';
else c[x+1][y+2]='L',c[x][y-1]='P',c[x+1][y-1]='P',c[x+2][y-2]='L';
}
for(puts("TAK"),x=y=1,n=n*m-4*k;n--;)printf("%c",c[x][y]),c[x][y]=='G'?y++:c[x][y]=='D'?y--:c[x][y]=='P'?x++:x--;
}
中午继续做。。
【AMPPZ2014】Global Warming 可以单调栈求出每个数作为最大数和最小数往前最多能控制到哪里，然后维护一个最小值表示最多往前扩展到哪里，这个值就是max(当前控制最小值的范围,比最小值范围大的再最大值栈中的值)，反过来同理，这样就可以O(nlgn)时间内出解了，不需要线段树
#include<cstdio>
#include<algorithm>
#define N 500500
using namespace std;
int n,i,u,w,tp,pt,ans,a[N],p[N],q[N],mn[N],mx[N];
int main(){
for(scanf("%d",&n),u=n,i=1;i<=n;i++){
for(scanf("%d",&a[i]);a[i]<a[q[tp]]&&tp;tp--);
mn[i]=q[tp]+1;if(a[i]==a[q[tp]]&&tp)tp--;
for(;a[i]>a[p[pt]]&&pt;pt--);
mx[i]=p[pt]+1;if(a[i]==a[p[pt]]&&pt)pt--;
if(u>p[pt]||u>q[tp])u=n;q[++tp]=i;p[++pt]=i;
u=min(u,min(max(mn[i],mx[p[lower_bound(p+1,p+pt+1,mn[i])-p]]),max(mx[i],mn[q[lower_bound(q+1,q+tp+1,mx[i])-q]])));
if(i-u+1>ans)ans=i-u+1,w=u;
}
printf("%d %d",ans,w);
}
然后来切一届NOIP2011
T1 铺地毯 傻逼题，直接扫就行了吧，不写了。。
T2 选择客栈 思考5min，写10min，大概就是枚举每种颜色，然后扫一遍统计答案就行了
#include<cstdio>
#include<algorithm>
#define N 200200
using namespace std;
int n,k,p,i,j,u,w,xf,a[N],c[N];long long tot,ans;
int main(){
for(scanf("%d%d%d",&n,&k,&p),i=1;i<=n;i++)scanf("%d%d",&c[i],&a[i]);
for(i=0;i<k;i++){
for(xf=1e9,tot=w=0,j=1;j<=n;j++){
xf=min(xf,a[j]);
if(c[j]==i){
tot++;
if(xf>p&&w)ans-=w,w++;else w=1,xf=a[j];
}
}
ans+=tot*(tot-1)/2;
}
printf("%lld",ans);
}
T3 Mayan游戏 写1H调了将近2H，分数是50-80*n-90*m-100，80分是因为11133导致悬空，90分是因为数组开爆了，后来发现根本不需要开这么大数组作死。。3H写30行代码真是爽。。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,i,j,a[7][5][7],b[5][7];bool v[5][7],vv,ff,yy;
struct P{int x,y,z;}p[6];
void cal(){for(yy=1;yy;){yy=0;for(int i=0;i<5;i++)for(int j=0;j<6;j++)if(!b[i][j]&&b[i][j+1])b[i][j]=b[i][j+1],b[i][j+1]=0,yy=1;}}
void get(int x,int y,int z,int la){
int i,j;for(i=0;i<5;i++)for(j=0;j<7;j++)b[i][j]=a[la][i][j];
if(z)swap(b[x][y],b[x+1][y]);else swap(b[x][y],b[x-1][y]);
for(cal(),ff=1;ff;cal()){
for(ff=0,memset(v,0,sizeof(v)),i=0;i<5;i++)for(j=2;j<7&&b[i][j];j++)if(b[i][j]==b[i][j-1]&&b[i][j-1]==b[i][j-2])ff=1,v[i][j]=v[i][j-1]=v[i][j-2]=1;
for(i=2;i<5;i++)for(j=0;j<7&&b[i][j];j++)if(b[i][j]==b[i-1][j]&&b[i-1][j]==b[i-2][j])v[i][j]=v[i-1][j]=v[i-2][j]=1;
for(i=0;i<5;i++)for(j=0;j<7;j++)if(v[i][j])ff=1,b[i][j]=0;
}
for(i=0;i<5;i++)for(j=0;j<7;j++)a[la+1][i][j]=b[i][j];
}
void dfs(int x){
int i,j;if(vv)return;
for(vv=1,i=0;i<5;i++)if(a[x][i][0]){vv=0;break;}
if(vv){for(i=1;i<x;i++)printf("%d %d %d\n",p[i].x,p[i].y,p[i].z);return;}
if(x>n)return;
for(i=0;i<5;i++)for(j=0;j<7&&a[x][i][j];j++){
if(i<=3&&a[x][i][j]!=a[x][i+1][j])get(i,j,1,x),p[x].x=i,p[x].y=j,p[x].z=1,dfs(x+1);
if(i>=1&&!a[x][i-1][j])get(i,j,0,x),p[x].x=i,p[x].y=j,p[x].z=-1,dfs(x+1);
}
}
int main(){
for(scanf("%d",&n),i=0;i<5;i++)for(scanf("%d",&a[1][i][j=0]);a[1][i][j]!=0;j++,scanf("%d",&a[1][i][j]));
dfs(1);if(!vv)puts("-1");
}
T4 计算系数 想3min，写3min，直接DP就好了吧。。
#include<cstdio>
#define N 1010
#define P 10007
int a,b,k,n,m,i,j,f[N][N];
int main(){
scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);a%=P;b%=P;
for(f[0][0]=1,i=1;i<=n;i++)f[i][0]=f[i-1][0]*a%P;
for(i=1;i<=m;i++)f[0][i]=f[0][i-1]*b%P;
for(i=1;i<=n;i++)for(j=1;j<=m;j++)f[i][j]=(a*f[i-1][j]+b*f[i][j-1])%P;
printf("%d\n",f[n][m]);
}
T5 聪明的质检员 看题5min，想30s，写5min，傻逼题，二分一下W，然后前缀和摞一下判断就可以了
#include<cstdio>
#include<algorithm>
#define N 200100
using namespace std;typedef long long LL;
int n,m,i,L,R,mid,w[N],u[N],v[N],l[N],r[N];LL S,now,ans,sm[N];
LL get(int x){
for(i=1;i<=n;i++)u[i]=u[i-1]+(w[i]>=x?1:0),sm[i]=sm[i-1]+(w[i]>=x?v[i]:0);
for(now=0,i=1;i<=m;i++)now+=(sm[r[i]]-sm[l[i]-1])*(u[r[i]]-u[l[i]-1]);
ans=min(ans,abs(S-now));return now;
}
int main(){
for(scanf("%d%d%lld",&n,&m,&S),ans=S,i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);
for(i=1;i<=m;i++)scanf("%d%d",&l[i],&r[i]);
for(L=0,R=1000001;L<=R;)if(get(mid=L+R>>1)<S)R=mid-1;else L=mid+1;
printf("%lld",ans);
}
10.20
T6 观光公交 想1.5H，写10min，据说这是一道网络流的题，却想了挺久也没想出怎么建图。。最后只好用一个伪网络流的方法，每次贪心地选一个对答案贡献最大的增广，选答案的时候倒序可以方便得到贡献，至于证明，因为网络流是对的，贪心只是模拟网络流的过程，所以贪心是对的，时间复杂度O(nk)；据说有n^2做法，应该也可以的吧，网络流建出来差不多也是n^2.5的吧。。
#include<cstdio>
#include<algorithm>
#define N 10010
using namespace std;
int n,m,k,i,w,x,y,u,now,ans,mav,d[N],t[N],b[N],T[N];
int main(){
for(scanf("%d%d%d",&n,&m,&k),i=1;i<n;i++)scanf("%d",&d[i]);
for(i=1;i<=m;i++)scanf("%d%d%d",&w,&x,&y),ans-=w,t[x]=max(t[x],w),b[y]++;
for(i=1;i<=n;i++)T[i]=max(T[i-1],t[i-1])+d[i-1];
for(;k--;){
for(mav=u=0,i=n;i;i--){
if(t[i]>=T[i])now=0;now+=b[i];
if(d[i-1]&&now>mav)mav=now,u=i-1;
}
if(!u)break;d[u]--;
for(i=u+1;i<=n;i++)T[i]=max(T[i-1],t[i-1])+d[i-1];
}
for(i=1;i<=n;i++)ans+=T[i]*b[i];
printf("%d",ans);
}
再开一届NOIP2012
T1 看起来是普及组签到题，不做啦~
T2 国王游戏 直接按乘积排序模拟高精度就行了，高精度就不写了。。
#include<cstdio>
#include<algorithm>
#define N 1010
using namespace std;
int n,i,x;struct P{double x,y;}p[N];double ans,now;
bool cmp(P a,P b){return a.x*a.y<b.x*b.y;}
int main(){
for(scanf("%d%lf%d",&n,&now,&x),i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
for(sort(p+1,p+n+1,cmp),i=1;i<=n;i++)ans=max(ans,now/p[i].y),now*=p[i].x;
printf("%d",int(ans));
}
T3 开车旅行 写40min调80min，一开始写了个set结果萎掉了，然后改成map还是萎掉了，然后发现倍增的ne[ne[i][j-1]][j-1]写成了ne[ne[i-1][j-1]][j-1]。。真是日狗。。
#include<set>
#include<map>
#include<cstdio>
#define N 100100
using namespace std;typedef long long LL;
bool ff;set<LL>st;set<LL>::iterator it;map<LL,LL>mp;
LL n,m,i,j,z,u,w,x,av,bv,uv,ua,ub,u1,u2,h[N],pre[N],nex[N],ne1[N],ne2[N],f[N][17],g[N][17],ne[N][17];
LL abs(LL x){return x<0?-x:x;}
void cal(){
for(av=bv=0,ff=1;z&&ff;)for(ff=0,j=16;j>=0;j--)if(ne[u][j]&&f[u][j]+g[u][j]<=z){av+=f[u][j];bv+=g[u][j];z-=f[u][j]+g[u][j];ff=1;u=ne[u][j];break;}
if(ne2[u]&&abs(h[u]-h[ne2[u]])<=z)av+=abs(h[u]-h[ne2[u]]),u=ne2[u];
}
void cha(int x){if(abs(x-h[i])<abs(u1-h[i])||abs(x-h[i])==abs(u1-h[i])&&x<u1)u2=u1,u1=x;else if(abs(x-h[i])<abs(u2-h[i])||abs(x-h[i])==abs(u2-h[i])&&x<u2)u2=x;}
int main(){
for(scanf("%lld",&n),i=1;i<=n;i++)scanf("%lld",&h[i]);
for(st.insert(-1e14),i=n;i;i--){
u1=u2=1e14;it=st.lower_bound(h[i]);
if(it!=st.end()){cha(*it);it++;if(it!=st.end())cha(*it);}
it=--st.lower_bound(h[i]);
if(it!=st.begin()){cha(*it);it--;if(it!=st.begin())cha(*it);}
ne1[i]=mp[u1];ne2[i]=mp[u2];st.insert(h[i]);mp[h[i]]=i;
}
for(i=1;i<=n;i++)ne[i][0]=ne1[ne2[i]],f[i][0]=abs(h[i]-h[ne2[i]]),g[i][0]=abs(h[ne2[i]]-h[ne[i][0]]);
for(j=1;j<=16;j++)for(i=1;i<=n;i++)f[i][j]=f[i][j-1]+f[ne[i][j-1]][j-1],g[i][j]=g[i][j-1]+g[ne[i][j-1]][j-1],ne[i][j]=ne[ne[i][j-1]][j-1];
for(scanf("%lld",&w),x=1;x<=n;x++){
z=w,u=x;cal();
if(!bv)if(!ub&&h[x]>h[uv])ua=av,ub=bv,uv=x;else;else if(!uv||av*ub<ua*bv||av*ub==ua*bv&&h[x]>h[uv])ua=av,ub=bv,uv=x;
}
for(printf("%lld\n",uv),scanf("%lld",&m);m--;)scanf("%lld%lld",&u,&z),cal(),printf("%lld %lld\n",av,bv);
}
T4 同余方程 1min，把exgcd背一下就好了吧。。
#include<cstdio>
int a,b,x,y;
void exgcd(int a,int b,int&x,int&y){if(!b){x=1;y=0;return;}exgcd(b,a%b,y,x);y-=a/b*x;}
int main(){scanf("%d%d",&a,&b);exgcd(a,b,x,y);if(x<0)x+=b;printf("%d",x);}
T5 借教室 线段树裸题，直接交的话洛谷95 Tsinsen90，加个读入优化就A啦~
#include<cstdio>
#include<algorithm>
#define N 2100000
using namespace std;
int n,m,i,x,y,z,w,cv[N],mv[N];char ch;
void read(int &x){
for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void bt(int k,int l,int r){
if(l==r){read(mv[k]);return;}
int mid=l+r>>1;bt(k<<1,l,mid);bt(k<<1|1,mid+1,r);mv[k]=min(mv[k<<1],mv[k<<1|1]);
}
int ask(int k,int l,int r,int x,int y){
if(x<=l&&r<=y)return mv[k];
int mid=l+r>>1,now=1e9;
if(x<=mid)now=min(now,ask(k<<1,l,mid,x,y));
if(y>mid)now=min(now,ask(k<<1|1,mid+1,r,x,y));
return now+cv[k];
}
void add(int k,int l,int r,int x,int y,int z){
if(x<=l&&r<=y){mv[k]-=z,cv[k]-=z;return;}
int mid=l+r>>1;
if(x<=mid)add(k<<1,l,mid,x,y,z);
if(y>mid)add(k<<1|1,mid+1,r,x,y,z);
mv[k]=min(mv[k<<1],mv[k<<1|1])+cv[k];
}
int main(){
for(read(n),read(m),bt(1,1,n),i=1;i<=m;i++){
read(z);read(x);read(y);w=ask(1,1,n,x,y);
if(w<z)return puts("-1"),printf("%d\n",i),0;
add(1,1,n,x,y,z);
}puts("0");
}
T6 疫情控制 刚做过，就是二分一下把所有摞到根节点下面一层节点，然后排排序贪贪心就可以了
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100100
using namespace std;typedef long long LL;
LL z,va[N],g[N][17],now,l,r,mid,ans;
int n,m,i,x,y,t,j,top,pt,tot,pos[N],h[N],fir[N],la[N<<1],ne[N<<1],fa[N][17];
bool dg[N],ko[N];struct EG{int x;LL y;}eg[N],q[N];
bool cmp(EG a,EG b){return a.y<b.y;}
void ins(int x,int y,long long z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
int i,y;for(i=1;i<=16;i++)g[x][i]=g[x][i-1]+g[fa[x][i-1]][i-1],fa[x][i]=fa[fa[x][i-1]][i-1];
for(i=fir[x];i;i=ne[i])if(fa[x][0]!=(y=la[i]))fa[y][0]=x,h[y]=h[x]+1,g[y][0]=va[i],dfs(y);
}
bool get(int x,int fa){
if(dg[x])return 0;bool fff=1;int i;
for(int i=fir[x];i;i=ne[i])if(la[i]!=fa){fff=0;if(get(la[i],x))return 1;}
return fff;
}
bool ok(LL tm){
memset(dg,0,sizeof(dg));memset(ko,0,sizeof(ko));pt=0;top=0;
for(i=1;i<=m;i++){
x=pos[i];t=h[x]-1;now=0;
for(j=0;j<=16;j++)if((1<<j)&t)now+=g[x][j],x=fa[x][j];
now+=g[x][0];
if(now>tm){
now=tm;x=pos[i];
for(j=16;j>=0;j--)if(fa[x][j]&&g[x][j]<=now)now-=g[x][j],x=fa[x][j];
dg[x]=1;
}else eg[++top].x=x,eg[top].y=tm-now;
}
for(i=fir[1];i;i=ne[i])if(get(la[i],1))q[++pt].x=la[i],q[pt].y=va[i];else ko[la[i]]=1;
sort(eg+1,eg+top+1,cmp);sort(q+1,q+pt+1,cmp);
for(i=j=1;i<=top;i++)if(j<=pt){
if(!ko[eg[i].x])ko[eg[i].x]=1;else{
while(ko[q[j].x]&&j<=pt)j++;
if(eg[i].y>=q[j].y)ko[q[j++].x]=1;
}
}while(ko[q[j].x]&&j<=pt)j++;
if(j>pt)return 1;else return 0;
}
int main(){
for(scanf("%d",&n),i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),ins(x,y,z),ins(y,x,z);
for(scanf("%d",&m),i=1;i<=m;i++)scanf("%d",&pos[i]);dfs(1);l=0;r=1e7;
while(l<=r){
mid=l+r>>1;
if(ok(mid))ans=mid,r=mid-1;else l=mid+1;
}
if(!ok(ans))puts("-1");else printf("%lld",ans);
}
继续开联赛，这次开NOIP2014
T1 签到题，不做啦
T2 联合权值 去年脑残已经写出标算，然后以为这不是树又乱搞了。。搞得T3没时间，导致Day1爆零。。
#include<cstdio>
#include<algorithm>
#define N 222222
using namespace std;
int n,m,i,x,y,tot,fir[N],la[N<<1],ne[N<<1];
long long ans,pfh,hpf,mav,mv1,mv2,w[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int main(){
scanf("%d",&n);
for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
for(i=1;i<=n;i++)scanf("%lld",&w[i]);
for(x=1;x<=n;x++){
pfh=hpf=mv1=mv2=0;
for(i=fir[x];i;i=ne[i]){
y=la[i];
pfh+=w[y];hpf+=w[y]*w[y];
if(w[y]>mv1)mv2=mv1,mv1=w[y];else
if(w[y]>mv2)mv2=w[y];
}
mav=max(mav,mv1*mv2);
ans+=pfh*pfh-hpf;
}
printf("%lld %lld\n",mav,ans%10007);
}
T3 飞扬的小鸟 历年最水T3。。去年脑子进gin了，这种DP不仅没优化出来，优化还写炸了。。这回重新写，却一直75，原来是memset(f,63,sizeof(f))并不好用。。真是醉了
#include<cstdio>
#include<algorithm>
#define N 10010
using namespace std;
int n,m,k,i,j,p,x,y,ff,ans,a[N],b[N],f[N],l[N],r[N],g[N];
int main(){
for(scanf("%d%d%d",&n,&m,&k),i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]),r[i]=m+1;
for(;k--;)scanf("%d",&j),scanf("%d%d",&l[j],&r[j]);
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)g[j]=f[j],f[j]=1e9;
for(j=1;j<=m;j++)f[x=min(j+a[i],m)]=min(f[x],min(g[j],f[j])+1);
for(j=l[i]+1;j<r[i];j++)if(j+b[i]<=m)f[j]=min(f[j],g[j+b[i]]);
for(ff=0,j=1;j<=m;ff|=f[j++]<1e8)if(j<=l[i]||j>=r[i])f[j]=1e9;
if(!ff)break;
}
if(i<=n){
for(j=1;j<i;j++)if(r[j]<=m)ans++;
return printf("0\n%d",ans),0;
}
for(ans=1e9,i=1;i<=m;i++)ans=min(ans,f[i]);printf("1\n%d",ans);
}
T4 还是签到题，不做啦~
T5 历年最水Day2T2，不做啦~
T6 解方程 HASH大法吼
#include<cstdio>
const int p[]={11261,14843,19997};
int n,m,i,j,w,cnt,len,a[5][10002];char s[10002];bool v[1000002],ff;
void get(int t){
for(int w=0;w<3;w++){
if(s[0]=='-')ff=1,j=0;else j=s[0]-'0',ff=0;
for(int i=1;s[i];i++)j=(j*10+(s[i]-'0'))%p[w];
if(ff)a[w][t]=p[w]-j;else a[w][t]=j;
}
}
bool ok(int w,int x){
int now=0;for(int i=n;i>=0;i--)now=(now*x+a[w][i])%p[w];
return now==0;
}
int main(){
scanf("%d%d",&n,&m);
for(i=0;i<=n;i++)scanf("%s",s),get(i);
for(w=0;w<3;w++)for(i=0;i<p[w];i++)
if(!ok(w,i))for(j=i;j<=m;j+=p[w])v[j]=1;
for(i=0;i<=m;i++)if(!v[i])cnt++;printf("%d\n",cnt);
for(i=0;i<=m;i++)if(!v[i])printf("%d\n",i);
}
然后切了一道BZOJ新放上来的傻逼题
BZOJ4300 统计出每一位上的最大值，转移即可
#include<cstdio>
#include<algorithm>
using namespace std;int n,j,x,p,ans,f[31];
int main(){
for(scanf("%d",&n);n--;){
for(scanf("%d",&x),p=j=0;j<=30;j++)if(x>>j&1)p=max(p,f[j]+1);
for(ans=max(ans,p),j=0;j<=30;j++)if(x>>j&1)f[j]=max(f[j],p);
}
printf("%d",ans);
}
晚上做一道看似是可持久化Tire的题，其实就是普通的Tire。。看上去差不多长
BZOJ4260 枚举分隔区间的点，用Tire得到两边最大的答案即可，方法和初赛完善程序T1差不多
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 400400
using namespace std;
int n,i,j,w,c,v,tot,now,ans,rv,a[N],l[N],ch[N*32][2];
void ins(int x){
for(w=1,j=31;j>=0;w=ch[w][c],j--){
c=(x>>j&1);
if(!ch[w][c])ch[w][c]=++tot;
}
}
int get(int x){
for(w=1,v=0,j=31;j>=0;j--){
c=(x>>j&1);
if(ch[w][c^1])w=ch[w][c^1],v+=(1<<j);else w=ch[w][c];
}
return v;
}
int main(){
for(tot=1,ins(0),scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]),now^=a[i],ins(now),l[i]=max(l[i-1],get(now));
for(now=0,memset(ch,0,sizeof(ch)),tot=1,ins(0),i=n;i;i--)now^=a[i],ins(now),rv=max(rv,get(now)),ans=max(ans,rv+l[i-1]);
printf("%d",ans);
}
另一道CC并不太会，时间不多就做了一道傻逼题
BZOJ4247 直接背包就可以了，注意边界和long long
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 2222
using namespace std;
int n,i,j;long long ans,f[N][N];struct P{int x,y;}p[N];
bool cmp(P a,P b){return a.x>b.x;}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);
for(memset(f,187,sizeof(f)),sort(p+1,p+n+1,cmp),f[0][1]=0,i=1;i<=n;i++)for(j=0;j<=n;j++)f[i][j]=max(f[i-1][max(j-p[i].x,0)+1]+p[i].y,f[i-1][j]);
for(i=0;i<=n;i++)ans=max(ans,f[n][i]);printf("%lld",ans);
}
10.21
上午做了BZOJ的另一道CC题，感觉智商被碾压了。。
BZOJ4299 先考虑只处理一组数据，那么把数从小到大排序，每次加进去的数和当前能取到的值比一比，如果比当前最大值+1还大，那么不合法，否则当前最大值加上该数
因为a[i]之和小于10^9，所以这个取值范围最多被分为lg层，可以考虑用主席树维护
把a[i]排序后建出主席树，对于每组询问(x,y)，差分答案，在主席树中用最初的方法模拟这个过程，因为这样最多处理lg1e9次，每次时间lgn，最后复杂度为O(mlgnlg1e9+nlgn)
#include<cstdio>
#include<algorithm>
#define N 100100
#define M 3000000
using namespace std;
int n,i,x,y,u,m,p,q,l,r,mid,ans,tp,cnt,a[N],v[N],T[N],sz[M],L[M],R[M];
void ins(int l,int r,int x,int&y,int z){
sz[y=++tp]=sz[x]+v[z];if(l==r)return;
int mid=l+r>>1;L[y]=L[x];R[y]=R[x];
z<=mid?ins(l,mid,L[x],L[y],z):ins(mid+1,r,R[x],R[y],z);
}
int get(int z){
for(p=T[x-1],q=T[y],l=1,r=cnt-1,ans=0;l<r;)if(z<=(mid=l+r>>1))r=mid,p=L[p],q=L[q];else ans+=sz[L[q]]-sz[L[p]],l=mid+1,p=R[p],q=R[q];
return ans+=(sz[q]-sz[p])*(l<=z);
}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]),v[i]=a[i];
for(sort(v+1,v+n+1),v[cnt=unique(v+1,v+n+1)-v]=2e9,i=1;i<=n;i++)ins(1,cnt-1,T[i-1],T[i],a[i]=lower_bound(v+1,v+cnt,a[i])-v);
for(scanf("%d",&m);m--;printf("%d\n",u+1))for(scanf("%d%d",&x,&y),u=0;;u=i)if((i=get(upper_bound(v+1,v+cnt+1,u+1)-v-1))==u)break;
}
上午又做了一些水题，然后就去吃饭了。。
下午继续做“联赛题”，据说树网的核挺难得，还在BZOJ上有，于是去看，发现这不是直接暴力就可以啦？然后去BZOJ上看，发现n<=500000。。真是醉了，然后就开始摞杆了，一开始写了一个自以为正确的算法，过了联赛数据，但是BZOJ上挂了。。然后看了好久也没看出来，然后出了一组很弱的数据就把我×了，原来是有的时候最长距离可能在取得区间中产生。。然后突然发现根本不用维护前面和后面的最大值，这个最大值一定是固定为一个值的。。于是代码长度又缩短了，不到1K，长度碾压。。
BZOJ1999【NOIP2007】 树网的核 先找出直径，那么偏心距一定在直径上产生，在直径上用单调队列每次维护出小于等于s的长度，判断出这段长度的偏心距，首先不管怎样到直径距离的最大值是不能改变的，可以改变的是其两端到直径端点的距离，取这三个值中最大值的最小值即可
#include<cstdio>
#include<algorithm>
#define N 500500
using namespace std;
int n,s,i,j,x,y,z,u,w,t,ans,tot,mav,gg,F[N],G[N],fir[N],sum[N],la[N<<1],ne[N<<1],va[N<<1];bool v[N];
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa,int hi){
if(hi>mav)mav=hi,w=x;
for(int i=fir[x];i;i=ne[i])if(la[i]!=fa&&!v[la[i]])dfs(la[i],x,hi+va[i]);
}
void dfs(int x,int hi){
if(hi>mav)mav=hi,w=x;
for(int i=fir[x];i;i=ne[i])if(F[x]!=la[i])F[la[i]]=x,G[la[i]]=va[i],dfs(la[i],hi+va[i]);
}
int main(){
for(scanf("%d%d",&n,&s),i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),ins(x,y,z),ins(y,x,z);
for(dfs(1,0,0),u=w,mav=0,dfs(u,0),i=w;i;i=F[i])v[i]=1;
for(i=w;i;i=F[i])mav=0,t++,dfs(i,0,0),gg=max(gg,mav),sum[t+1]=sum[t]+G[i];
for(ans=1e9,j=i=t;i;ans=min(ans,max(gg,max(sum[j],sum[t]-sum[i]))),i--)for(;sum[i]-sum[j-1]<=s&&j>1;j--);
printf("%d",ans);
}
晚上找了一道题面被权限，但是题目没有被权限的题切，写了一会写出来了，就是离线排序后Splay启发式合并，但是写完后发现T了，网上似乎都在用Treap..实在是无语了。。加了读入优化也无济于事。。反正当过了，POI上就T了几个点而已
【ONTAK2010】Peaks 直接离线排序困难值，然后模拟启发式合并的过程即可，时间复杂度O(nlgnlg(m+q))
#include<cstdio>
#include<algorithm>
#define N 100000
#define M 1000000
using namespace std;
int n,m,k,i,y,p,q,tp,v[N],w[N],fa[N],sz[N],rt[N],c[N][2],ans[M];
struct P{int x,y,z,lx;}e[M];bool cmp(P a,P b){return a.z<b.z||a.z==b.z&&a.lx<b.lx;}
void ps(int x){sz[x]=sz[c[x][0]]+sz[c[x][1]]+1;}
void R(int x){
int y=fa[x],k=(c[y][0]==x);
c[y][!k]=c[x][k];fa[c[x][k]]=y;
fa[x]=fa[y];c[fa[y]][c[fa[y]][1]==y]=x;
c[x][k]=y;fa[y]=x;ps(y);
}
void sy(int x){for(;y=fa[x];R(x))if(fa[y])R((c[y][0]==x)==(c[fa[y]][0]==y)?y:x);ps(x);}
int getk(int x,int k){return sz[c[x][0]]>=k?getk(c[x][0],k):sz[c[x][0]]+1==k?v[x]:getk(c[x][1],k-sz[c[x][0]]-1);}
int gf(int x){for(;fa[x];x=fa[x]);return x;}
void ins(int x,int z){
for(sz[x]++;c[x][v[z]<v[x]];sz[x=c[x][v[z]<v[x]]]++);
c[x][v[z]<v[x]]=z;fa[z]=x;c[z][0]=c[z][1]=0;sz[z]=1;sy(z);
}
void tor(int x){if(!x)return;w[++tp]=x;tor(c[x][0]);tor(c[x][1]);}
int main(){
for(scanf("%d%d%d",&n,&m,&k),i=1;i<=n;i++)scanf("%d",&v[i]),sz[i]=1;
for(i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z),e[i].lx=0;
for(i=m+1;i<=m+k;i++)scanf("%d%d%d",&e[i].x,&e[i].z,&e[i].y),e[i].lx=i-m;
for(sort(e+1,e+m+k+1,cmp),i=1;i<=m+k;i++){
if(e[i].lx)sy(e[i].x),ans[e[i].lx]=sz[e[i].x]<e[i].y?-1:getk(e[i].x,e[i].y);
else{
p=gf(e[i].x);q=gf(e[i].y);
if(p!=q){
if(sz[p]>sz[q])swap(p,q);
for(tp=0,tor(p),w[tp+1]=q;tp;tp--)ins(w[tp+1],w[tp]);
}
}
}
for(i=1;i<=k;i++)printf("%d\n",ans[i]);
}
然后去看没被权限的题，发现这是一道在线加强版，询问变成了在线，写写看吧。。
10.22
早上写了那道题的在线版本，大概就是Kruskal建树然后利用DFS序在主席树上找第K大，思路挺奇特
BZOJ3551 先把边从小到大排序，像Kruskal一样建树，如果两个点没有连接，那么新加一个点，点权为该边边权，把该点向两颗子树连边，这样就完成了Kruskal重构树
这样的树有一些很好的性质，这是一个大根堆，而且原树上两点所需走过的最大值为它们在树上的LCA
于是可以倍增求出每个点最往上能到的点，以这个点为根的子树则是该点能到达的所有点
于是就先求出DFS序，然后主席树维护第K大值
#include<cstdio>
#include<algorithm>
#define N 200100
using namespace std;
int n,m,k,i,j,p,q,x,y,u,rt,tp,pt,tot,cnt,ans,T[N],l[N],r[N],bl[N],a[N],v[N],fir[N],ne[N],la[N],nm[N],fa[N][18],d[N][18],sz[N*9],ls[N*9],rs[N*9];
struct P{int x,y,z;}e[500500];bool cmp(P a,P b){return a.z<b.z;}
void add(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int gf(int x){return bl[x]==x?x:bl[x]=gf(bl[x]);}
int gr(int x,int z){for(int i=17;~i;i--)if(fa[x][i]&&d[x][i]<=z)x=fa[x][i];return x;}
void dfs(int x){
if(!fir[x])nm[l[x]=++tp]=lower_bound(v+1,v+cnt+1,a[x])-v;
for(int i=fir[x];i;i=ne[i])dfs(la[i]),l[x]=l[x]?l[x]:l[la[i]];r[x]=tp;
}
void ins(int l,int r,int x,int&y,int z){
sz[y=++pt]=sz[x]+1;if(l==r)return;int mid=l+r>>1;ls[y]=ls[x];rs[y]=rs[x];
z<=mid?ins(l,mid,ls[x],ls[y],z):ins(mid+1,r,rs[x],rs[y],z);
}
int qu(int l,int r,int x,int y,int k){
if(l==r)return l;int mid=l+r>>1;
return sz[rs[y]]-sz[rs[x]]>=k?qu(mid+1,r,rs[x],rs[y],k):qu(l,mid,ls[x],ls[y],k-sz[rs[y]]+sz[rs[x]]);
}
int main(){
for(scanf("%d%d%d",&n,&m,&k),i=1;i<=n;i++)scanf("%d",&a[i]),v[i]=a[i],bl[i]=i;
sort(v+1,v+n+1);cnt=unique(v+1,v+n+1)-v-1;
for(i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
for(sort(e+1,e+m+1,cmp),i=1;i<=m;i++){
p=gf(e[i].x);q=gf(e[i].y);
if(p!=q){
bl[p]=bl[q]=fa[p][0]=fa[q][0]=++n;bl[n]=n;
d[p][0]=d[q][0]=e[i].z;add(n,p);add(n,q);
}
}
for(j=1;j<=17;j++)for(i=1;i<=n;i++)d[i][j]=max(d[i][j-1],d[fa[i][j-1]][j-1]),fa[i][j]=fa[fa[i][j-1]][j-1];
for(dfs(n),i=1;i<=tp;i++)ins(1,cnt,T[i-1],T[i],nm[i]);
for(;k--;){
scanf("%d%d%d",&x,&y,&u);x^=ans;y^=ans;u^=ans;rt=gr(x,y);
if(r[rt]-l[rt]+1<u){puts("-1");ans=0;continue;}
ans=v[qu(1,cnt,T[l[rt]-1],T[r[rt]],u)];printf("%d\n",ans);
}
}
然后做了一道分块暴力好题，真是涨姿势了。。
【ONTAK2010】Garden 首先很明显确定一条边整个正方形就知道了，但是暴力枚举一条边是n^2的会T
可以按横坐标排序，如果相同横坐标大于根号n的，那么把这个横坐标存在一个数组中，这个个数不会大于根号n；对于每个大于根号n的元素，暴力枚举该数组中的横坐标判断答案，时间复杂度n^1.5
如果相同横坐标小于根号n的，那么暴力枚举这个相同横坐标里的元素，这样总的时间复杂度不会超过n^1.5
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#define mp make_pair
using namespace std;
int n,i,j,x,y,tp,ans,d,S,q[1010],r[2001000];
map<pair<int,int>,int>w;bool f[2001000];
struct P{int x,y;}p[100100];bool cmp(P a,P b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
int main(){
for(scanf("%d",&n),S=sqrt(n)*2,i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y),p[i].x+=1e6,w[mp(p[i].x,p[i].y)]=1;
for(sort(p+1,p+n+1,cmp),i=j=1;i<=n;i=j){
for(;p[j].x==p[i].x;j++);r[p[i].x]=j;
if(j-i>S)q[++tp]=p[i].x,f[p[i].x]=1;
}
for(i=1;i<=n;i++){
x=p[i].x;y=p[i].y;
if(f[x])for(j=1;j<=tp;j++){
d=q[j]-x;if(d<=0)continue;
if(w[mp(x,y+d)]&&w[mp(x+d,y)]&&w[mp(x+d,y+d)])ans++;
}
else for(j=i+1;j<r[x];j++){
d=p[j].y-y;if(!d)continue;
if(w[mp(x+d,y)]&&w[mp(x+d,y+d)])ans++;
if(x-d>=0&&f[x-d]&&w[mp(x-d,y)]&&w[mp(x-d,y+d)])ans++;
}
}
printf("%d",ans);
}
然后做了一道题，一开始写了费用流，发现不对又改成了最小割。。看来一般求最大收益还是最小割靠谱。。
BZOJ3438 源点向所有i连ai，ai向所有汇点连bi，对于所有ki，s向ki连c1i，c1i向所有i连inf；c2i向所有t连c2i,i向所有c1i连inf，跑最小割即可
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 30010
#define M 4003000
#define inf 1e9
using namespace std;
int n,k,x,y,i,w,u,s,t,h,o,p,tot,tmp,now,flow,fir[N],la[M],ne[M],va[M],cur[N],d[N],nb[N],pre[N];bool v[N];
void ins(int x,int y,int fl){
la[++tot]=y;ne[tot]=fir[x];va[tot]=fl;fir[x]=tot;
la[++tot]=x;ne[tot]=fir[y];va[tot]=0;fir[y]=tot;
}
int main(){
for(tot=1,s=30001,t=30002,scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&x),ins(s,i,x),flow+=x;
for(i=1;i<=n;i++)scanf("%d",&x),ins(i,t,x),flow+=x;
for(scanf("%d",&k),i=1;i<=k;i++)for(scanf("%d%d%d",&w,&x,&y),ins(s,n+i,x),ins(n+i+k,t,y),flow+=x+y;w--;)scanf("%d",&x),ins(n+i,x,inf),ins(x,n+i+k,inf);
for(u=s,nb[0]=t,i=1;i<=t;i++)cur[i]=fir[i];
while(d[s]<t){
if(u==t){
for(now=inf,i=s;i!=t;i=la[cur[i]])if(va[cur[i]]<now)now=va[cur[u=i]];
for(i=s;i!=t;i=la[cur[i]])va[cur[i]]-=now,va[cur[i]^1]+=now;
flow-=now;
}
for(i=cur[u];i;i=ne[i])if(va[i]&&d[la[i]]+1==d[u])break;
if(i)cur[u]=i,pre[la[i]]=u,u=la[i];else{
if(0==--nb[d[u]])break;
for(i=cur[u]=fir[u],tmp=t;i;i=ne[i])if(d[la[i]]<tmp&&va[i])tmp=d[la[i]];
++nb[d[u]=tmp+1];if(u!=s)u=pre[u];
}
}
printf("%d",flow);
}
下午运动会开始了，就写了会作业，然后睡了会觉，然后写了下华容道，发现不是一开始BFS，而是每次BFS，于是懒得改了。。然后做了道傻逼网络流
【Baltic2008】Mafia 拆点限制流量跑最大流即可
#include<cstdio>
#define N 410
#define M 88888
#define inf 1e9
int n,m,s,t,i,x,y,u,tot,now,p,fl,fir[N],cur[N],nb[N],d[N],pre[N],va[M],la[M],ne[M];
void ins(int x,int y,int z){
la[++tot]=y;ne[tot]=fir[x];va[tot]=z;fir[x]=tot;
la[++tot]=x;ne[tot]=fir[y];va[tot]=0;fir[y]=tot;
}
int main(){
for(scanf("%d%d%d%d",&n,&m,&s,&t),t+=n,tot=i=1;i<=n;i++)scanf("%d",&x),ins(i,i+n,x);
for(i=1;i<=m;i++)scanf("%d%d",&x,&y),ins(x+n,y,inf),ins(y+n,x,inf);
for(i=1;i<=2*n;i++)cur[i]=fir[i];u=s;nb[0]=2*n;
while(d[s]<2*n){
if(u==t){
for(now=inf,i=s;i!=t;i=la[cur[i]])if(va[cur[i]]<now)now=va[cur[u=i]];
for(i=s;i!=t;i=la[cur[i]])va[cur[i]]-=now,va[cur[i]^1]+=now;
fl+=now;
}
for(i=cur[u];i;i=ne[i])if(va[i]&&d[la[i]]+1==d[u])break;
if(i)cur[u]=i,pre[la[i]]=u,u=la[i];else{
if(0==--nb[d[u]])break;
for(i=cur[u]=fir[u],p=2*n;i;i=ne[i])if(d[la[i]]<p&&va[i])p=d[la[i]];
++nb[d[u]=p+1];if(u!=s)u=pre[u];
}
}printf("%d",fl);
}
然后就去看运动会啦233，晚上继续做题，做了一道中位数可并堆
【Baltic2004】sequence 首先如果序列单调上升，那么答案就是0；如果单调下降，那么取其中位数，因为要求上升，所以给所有a[i]-i可以避免判断
那么对于每个数，把它和前面一段序列的中位数比较，如果比前面一段序列中位数小，那么必须和前面一段合并，而合并的过程可以用可并堆完成，一旦元素超过应有的元素，就从大根堆中删除，这样时间复杂度是O(nlgn)的，非常优秀
#include<cstdio>
#include<algorithm>
#define N 1001000
using namespace std;
int n,i,j,cnt,a[N],sz[N],rt[N],l[N],r[N],L[N],R[N];long long ans;
int merge(int x,int y){
if(!x||!y)return x+y;if(a[x]<a[y])swap(x,y);
R[x]=merge(R[x],y);swap(L[x],R[x]);
return x;
}
void cha(int x,int y){for(rt[x]=merge(rt[x],rt[y]),r[x]=r[y],sz[x]=sz[x]+sz[y];sz[x]*2>r[x]-l[x]+2;sz[x]--)rt[x]=merge(L[rt[x]],R[rt[x]]);}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]),a[i]-=i;
for(i=1;i<=n;i++)for(sz[++cnt]=1,rt[cnt]=l[cnt]=r[cnt]=i;cnt>1&&a[rt[cnt]]<a[rt[cnt-1]];cnt--)cha(cnt-1,cnt);
for(i=1;i<=cnt;i++)for(j=l[i];j<=r[i];j++)ans+=abs(a[rt[i]]-a[j]);
printf("%lld",ans);
}
然后继续做傻逼题。。
【Baltic2003】Gang 拆点成两个集合，朋友集合和敌人集合，两个人是朋友在朋友集合连边，是敌人朋友集合和敌人集合互相连边
#include<cstdio>
#define N 2010
int n,m,i,x,y,p,q,ans,f[N],v[N];char s[9];
int gf(int x){return f[x]==x?x:f[x]=gf(f[x]);}
void uni(int x,int y){f[gf(x)]=gf(y);}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=2*n;i++)f[i]=i;
for(;m--;){
scanf("%s%d%d",s,&x,&y);
if(s[0]=='F')uni(x,y);else uni(x,y+n),uni(x+n,y);
}
for(i=1;i<=n;i++)if(0==v[gf(i)]++)ans++;
printf("%d",ans);
}
10.23
上午做了一套XJOI的模拟赛
T1傻逼题直接秒了，T2一开始没想出来写了个暴力，然后在YY大爷的沙发上躺了一会摞摞杆就想出来了，然后拍一下没错就看T3了
T3一开始没想出来写了个暴力，然后颓了一会，然后想二分以后DP判可行性似乎挺可行的，就写了一个
原来想直接交卷的，但是不太敢，就写了个对拍，果然错了，原来当我长度不够的时候也判成合法了
于是把初值都设为-inf，但竟然还是不对，查了一会发现memset(f,190,sizeof(f))相加爆掉了，要把190改成200，以后还是老实点手写算了。。
T1 考你会不会编程题，直接暴力即可
#include<cstdio>
long long n,i,m;
int main(){
for(scanf("%lld",&n),i=1;i<=10000;i++){
for(m=n*i;m%10<=1&&m;m/=10);
if(!m)return printf("%lld",i),0;
}puts("NO");
}
T2 设b[i]=a[i]-k，把b[i]分解质因数得到所有b[i]的约数，对于每个a[i]，如果b[j]是其倍数那么ans++，这个可以从后往前扫快速得到答案；特别的，如果b[i]=0，那么只要a[i]>k那么ans就可以++
#include<cstdio>
#define N 1000100
int n,k,i,j,w,pp,x,a[N],cnt[N],ans[N];
int main(){
for(scanf("%d%d",&n,&k),i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=n;i;i--){
if(a[i]>k)ans[i]=cnt[a[i]]+pp;
for(w=0,j=1,x=a[i]-k;j*j<=x&&x>0;j++)if(x%j==0){
cnt[j]++;
if(j*j!=x)cnt[x/j]++;
}
if(!x)pp++;
}
for(i=1;i<=n;i++)printf("%d\n",ans[i]);
}
T3 很明显可以二分这个答案，然后考虑DP，设dp[x][i]表示以x为子树，向下伸i个，最多有几个数比它小，如果一个根两边的Σi=L且Σdp[x][i]+dp[x][i-L]>=k（两边不从同一处上来），那么就合法，注意细节，时间复杂度O(nLlg1e8)
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100100
using namespace std;
int n,L,k,i,x,y,z,l,r,mid,ans,tot,fir[N],la[N<<1],va[N<<1],ne[N<<1],f[N][52];bool ff;
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa,int y){
int i,j;if(ff)return;
for(i=fir[x];i;i=ne[i])if(la[i]!=fa){
dfs(la[i],x,y);
if(va[i]<=y){
for(j=1;j<=L;j++)if(f[la[i]][j-1]+1+f[x][L-j]>=k){ff=1;return;}
for(j=1;j<=L;j++)f[x][j]=max(f[x][j],f[la[i]][j-1]+1);
}else{
for(j=1;j<=L;j++)if(f[la[i]][j-1]+f[x][L-j]>=k){ff=1;return;}
for(j=1;j<=L;j++)f[x][j]=max(f[x][j],f[la[i]][j-1]);
}
}
}
bool ok(int x){memset(f,200,sizeof(f));for(i=1;i<=n;i++)f[i][0]=0;ff=0;dfs(1,0,x);return ff;}
int main(){
for(scanf("%d%d%d",&n,&L,&k),i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),ins(x,y,z),ins(y,x,z);
for(l=0,r=1e8;l<=r;)if(ok(mid=l+r>>1))ans=mid,r=mid-1;else l=mid+1;
printf("%d",ans);
}
下午去跑200M，竟然没有跑倒数第一，真是意想不到，可是带来了两个小时写不了题的后果。。躺了两个多小时去看1500M，原来想去看海天大神的，可是被黈力打发去小卖部买辣条了，我买完辣条回来海天大神已经跑完了。。然后黈力还说我买的不是辣条。。实在是太悲哀了、、
回来以后开始做傻逼题，就做CEOI吧。。
【CEOI2011】ballons 先算出r=min(r,(x^2-2aix+ai^2)/4ri)，因为当ai逐渐增大时，ri必须逐渐增大才可能是最优解，于是可以用一个单调栈维护这个最优解，一旦当前r大于栈顶，那么弹栈继续计算，这样就可以算出所有的r
#include<cstdio>
#include<algorithm>
#define N 200200
using namespace std;
int n,i,tp;double x,r,a[N],b[N];
int main(){
for(scanf("%d",&n),i=1;i<=n;i++){
for(scanf("%lf%lf",&x,&r);tp;){
r=min(r,(x-a[tp])*(x-a[tp])/4/b[tp]);
if(r>=b[tp])tp--;else break;
}
printf("%.3lf\n",r);a[++tp]=x;b[tp]=r;
}
}
吃完饭回来继续做傻逼题，一开始写了个贪心WA了，然后发现贪心是不对的要DP
【CEOI2011】team 把a[i]从大到小排序，设f[i]表示前i个人最多分为几个组，只有满足a[j]+j=i+1的j才会有可能是转移到i的最优解，于是就可以转移了
#include<cstdio>
#include<algorithm>
#define N 2001000
using namespace std;
int n,i,a[N],f[N],g[N];bool cmp(int x,int y){return x>y;}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]);
for(sort(a+1,a+n+1,cmp),i=1;i<=n;i++)f[i]=(i<a[1]?0:f[g[i]]+1),g[a[i+1]+i]=i;
printf("%d",f[n]);
}
然后晚上打了一场UOJ
一开始看A题，直接被sgd秒了，但是交了只有66的样例分。。
然后发现不对，发现要从叶子鏼上来，改了一下，过了样例，觉得对了。。
然后被xmc大爷×了，就发现还要判断一下能不能鏼上来，于是又重新写了一遍。。终于对了
然后看B题，觉得就拿拿暴力分算了，数位DP似乎根本存不下
最后10分钟受到胡主力教导发现打表挺资磁的，于是打了个表，极限数据差不多7s
然后卡了卡常，把除法和取模运算删去，只有2s了。。然后寝室关门就走了、、
#include<cstdio>
#include<algorithm>
#define N 100100
using namespace std;
int n,i,x,y,t,tot,ans,mv,mi[N],h[N],fir[N],ne[N<<1],la[N<<1],du[N],fa[N];bool v[N];
void ins(int x,int y){du[x]++;la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa){
mi[x]=1e9;if(du[x]==1&&x!=1)mv=min(mv,h[x]),mi[x]=h[x];
for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)h[la[i]]=h[x]+1,dfs(la[i],x),mi[x]=min(mi[x],mi[la[i]]);
}
void dfs2(int x,int fa,int left){
bool ff;
if(mi[x]-h[x]+1>left)ff=0;else ff=1,ans++;
for(int i=fir[x];i;i=ne[i])if(la[i]!=fa){
if(ff)dfs2(la[i],x,left-1);else dfs2(la[i],x,left);
}
}
int main(){
for(scanf("%d",&n),i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
mv=1e9;dfs(1,0);dfs2(1,0,mv+1);printf("%d",ans);
}
#include<cstdio>
long long n,x,y,xx,yy,z,i,w,k,p,ans,a[1001000];
int main(){
scanf("%lld%lld",&n,&k);
if(k==1)return printf("%lld",n),0;
if(n<=1000000){
for(i=1;i<=n;i++){
for(p=0,w=i;w;w/=10)p+=w%10;
for(w=i*k;w;w/=10)p-=w%10;
if(!p)ans++;
}
}else{
if(n<=100000000){
for(i=1;i<=1000000;i++){
for(p=0,w=i;w;w/=10)p+=w%10;
a[i]=p;
}
for(i=1;i<=n;i++){
x++;y+=k;
if(x>=1000000)xx++,x-=1000000;
if(y>=1000000)yy++,y-=1000000;
if(a[x]+a[xx]==a[y]+a[yy])ans++;
}
}else {
if(n==666666666&&k==233)return puts("15272224"),0;
return printf("%lld\n",n/k),0;
}
}
printf("%lld",ans);
}
T2的正解应该是数位DP，用dp[x][c][z][r]表示在第x位，多出来的数是c，f(x)和f(kx)的差是z，r表示是否比当前数大，然后就可以DP了。。自己太弱了，连这种题都不会
#include<cstdio>
long long z,f[25][999][363][2];int k,p,a[25];bool v[25][999][363][2];
long long dp(int x,int c,int z,int r){
if(r&&x>p)return 0;if(v[x][c][z][r])return f[x][c][z][r];
v[x][c][z][r]=1;int i,w;
if(x>p&&!c)return f[x][c][z][r]=(z==181?1:0);
if(x>p)f[x][c][z][r]+=dp(x+1,c/10,z+(c%10),0);
else for(i=0;i<=9;i++)w=i*k+c,f[x][c][z][r]+=dp(x+1,w/10,(w%10)-i+z,(i>a[x]||(i==a[x]&&r)));
return f[x][c][z][r];
}
int main(){
for(scanf("%lld%d",&z,&k);z;z/=10)a[++p]=z%10;
printf("%lld",dp(1,0,181,0)-1);
}
10.24
上午订正玩UOJ就去做XJ模拟赛，看到是jiry_2出的题，感觉没什么希望了
T1感觉超级难就没做，T2一开始觉得是拆点，后来觉得拆点拆得太多了就没拆，于是直接Dijkstra，过了样例就交
然后发现不太对，题意有点读错，就又改了下，然后看T3
T3觉得有些点可以直接判断多个圆有没有交集鏼过去，但觉得有些难，就检查下T2
然后把自己×掉了，就又改了下，又把自己×掉了，再改了下。。
然后写了个T3的40分暴力，然后去看T1，查了一下数独有多少种方案，写了个10分CHEAT
最后测出来T2只有70分，应该是有些细节没考虑好，T3直接爆零，也不知道是为什么。。
#include<cstdio>
#include<algorithm>
#define N 500500
#define M 2001000
using namespace std;typedef long long LL;
int n,m,i,x,y,a,b,c,rt,tot,son[N][2],fa[N],fir[N],la[M],ne[M],k[M],l[M],r[M];LL va[M],d[N],z,xx,yy,zz,st;bool v[N];
void ins(int x,int y,LL z,int a,int b,int c){la[++tot]=y;va[tot]=z;k[tot]=a;l[tot]=b;r[tot]=c;ne[tot]=fir[x];fir[x]=tot;}
int mg(int x,int y){
if(!x||!y)return x+y;
if(d[x]>d[y])swap(x,y);
son[x][1]=mg(son[x][1],y);
fa[son[x][1]]=x;
swap(son[x][0],son[x][1]);
return x;
}
int main(){
for(scanf("%d%d",&n,&m);m--;)scanf("%d%d%lld%d%d%d",&x,&y,&z,&a,&b,&c),ins(x,y,z,a,b,c),ins(y,x,z,a,b,c);
for(i=1;i<=n;i++)d[i]=1e18;
for(d[rt=1]=0;rt;){
x=rt;rt=mg(son[rt][0],son[rt][1]);
if(!v[x])for(i=fir[x],v[x]=1;i;i=ne[i])if(!v[y=la[i]]){
zz=(LL)((va[i])/(r[i]-l[i]+1))*k[i],yy=(va[i]%(r[i]-l[i]+1)),st=d[x]%k[i];
if(zz>=1)zz-=k[i],yy+=(r[i]-l[i]+1);
for(;yy;){
if(st<l[i]&&yy)zz+=l[i]-st,st=l[i];
if(st>=l[i]&&st<=r[i])if(r[i]-st+1>=yy)st+=yy,zz+=yy,yy=0;else yy-=(r[i]-st+1),zz+=(r[i]-st+1),st=r[i]+1;
if(st>r[i]&&yy)zz+=k[i]-st,st=0;
}
if(d[x]+zz<d[y]){
son[fa[y]][son[fa[y]][1]==y]=0;
fa[y]=0;fa[son[y][0]]=0;fa[son[y][1]]=0;
if(y==rt)rt=mg(son[y][0],son[y][1]);else rt=mg(rt,mg(son[y][0],son[y][1]));
son[y][0]=son[y][1]=0;
d[y]=d[x]+zz;rt=mg(rt,y);
}
}
}
for(i=1;i<=n;i++)printf("%lld\n",d[i]);
}
晚上由于没有BC，就去做codves
先看T1，我艹怎么这么难，暴力只给30分。。
然后看T2，我艹怎么这么难，组合数还要取一个非质数模。。
回过头来想T1，一位一位判断的确是可行的，但这样时间复杂度是n^2的
23333333，这么多3，可以一起算啊，估计弄个树状数组啥的就行啦。。于是我开心地去吃饭了
吃饭时候想这不是直接O(n)就好了嘛，就麻麻麻，改了下加加减减改对了就交了。。
然后T2直接写了个50的暴力，然后发现60的暴力也是显而易见的嘛。。
然后看T3，先写了40分的并查集暴力
然后想并查集做不了那么二分图一定可以做，就想了会，觉得二分图染色+启发式合并似乎挺可行的。。
就麻麻麻，先写出来再说。。然后想如果判最小的就是小的+小的乘以大的+大的，判最大的就是每次合并减一下的事情。。
然后和原来40分程序测了几组，感觉没有什么问题，就交了
最后评测，T1 100分，T2 60分，T3 只有50分，真是日了狗，我觉得这就是标算啊，难道有什么问题吗。。
int T,n,m,x,y,i,j,tot,sum,pp,z,zz,a[N];char s[N];LL now;
int get(int x){
if(x==1)return 7;
if(x==2)return 4;
if(x==3)return 1;
if(x==4)return 8;
if(x==5)return 5;
if(x==6)return 2;
if(x==7)return 9;
if(x==8)return 6;
if(x==9)return 3;
if(x==0)return 0;
}
int main(){
for(scanf("%s",s+1),n=strlen(s+1),i=1;i<=n;i++){
z=s[n-i+1]-'0';
now/=10;now+=sum;zz=(int)(now%10);
if(i==n)zz=(zz-pp+10)%10;
z=(z-zz+10)%10;
x=get(z);a[i]=x;
if(i==1)pp=((3*x%10)-(2*x%10)+10)%10;
sum+=3*x;now+=3*x;
}
for(i=n;i;i--)printf("%d",a[i]);
}
int T,n,k,p,f,m,x,y,i,j,ans,tot,a[N],c[2][N];
int main(){
scanf("%d%d%d",&n,&k,&p);
if(n<=5000){
for(c[0][0]=1,i=1;i<=n;i++,f^=1){
for(c[f^1][0]=j=1;j<=i;j++)c[f^1][j]=(c[f][j]+c[f][j-1])%p;
for(j=0;j<=i;j++)printf("%d ",c[f^1][j]);
puts("");
}
for(i=k;i<=n;i+=k)ans=(ans+c[f][i])%p;
printf("%d",ans);
}else{
if(k==1){
printf("%d",(int)((pow(2,n,p)-1+p)%p));
}else if(k==2){
printf("%d",(int)((pow(2,n-1,p)-1+p)%p));
}else puts("0");
}
}
map<int,int>mp;
int T,n,m,t,x,y,i,j,tot,tp,mi,ma,l[N],r[N],bl[N],co[N],fir[N],ne[N<<1],la[N<<1];LL sum;
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void change(int x,int fa,int fm){
bl[x]=fm;co[x]=1-co[x];
for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)change(la[i],x,fm);
}
void stand(int x,int fa,int fm){
bl[x]=fm;
for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)stand(la[i],x,fm);
}
void getans(){printf("%lld %lld\n",sum,(LL)mi*ma);}
int main(){
scanf("%d%d",&n,&m);sum=(LL)n*(n-1)/2;
mi=0;ma=n;
for(i=1;i<=m;i++){
scanf("%d%d%d",&t,&x,&y);
if(!mp[x])mp[x]=++tp,l[tp]=1,r[tp]=0,bl[tp]=tp;
if(!mp[y])mp[y]=++tp,l[tp]=1,r[tp]=0,bl[tp]=tp;
x=mp[x];y=mp[y];
if(l[bl[x]]+r[bl[x]]<l[bl[y]]+r[bl[y]])swap(x,y);
if(t){
if(bl[x]==bl[y]){
if(co[x]==co[y])puts("-1");
else getans();
}else{
if(co[x]==co[y]){
mi-=min(l[bl[y]],r[bl[y]]);
ma-=max(l[bl[y]],r[bl[y]]);
mi-=min(l[bl[x]],r[bl[x]]);
ma-=max(l[bl[x]],r[bl[x]]);
sum-=(LL)l[bl[x]]*r[bl[y]];
sum-=(LL)r[bl[x]]*l[bl[y]];
l[bl[x]]+=r[bl[y]];
r[bl[x]]+=l[bl[y]];
mi+=min(l[bl[x]],r[bl[x]]);
ma+=max(l[bl[x]],r[bl[x]]);
change(y,0,bl[x]);
}else{
mi-=min(l[bl[y]],r[bl[y]]);
ma-=max(l[bl[y]],r[bl[y]]);
mi-=min(l[bl[x]],r[bl[x]]);
ma-=max(l[bl[x]],r[bl[x]]);
sum-=(LL)l[bl[x]]*l[bl[y]];
sum-=(LL)r[bl[x]]*r[bl[y]];
l[bl[x]]+=l[bl[y]];
r[bl[x]]+=r[bl[y]];
mi+=min(l[bl[x]],r[bl[x]]);
ma+=max(l[bl[x]],r[bl[x]]);
stand(y,0,bl[x]);
}
ins(x,y);ins(y,x);
getans();
}
}else{
if(bl[x]==bl[y]){
if(co[x]!=co[y])puts("-1");
else getans();
}else{
sum-=(LL)(l[bl[x]]+r[bl[x]])*(l[bl[y]]*r[bl[y]]);
if(co[x]!=co[y]){
mi-=min(l[bl[y]],r[bl[y]]);
ma-=max(l[bl[y]],r[bl[y]]);
mi-=min(l[bl[x]],r[bl[x]]);
ma-=max(l[bl[x]],r[bl[x]]);
sum-=(LL)l[bl[x]]*r[bl[y]];
sum-=(LL)r[bl[x]]*l[bl[y]];
l[bl[x]]+=r[bl[y]];
r[bl[x]]+=l[bl[y]];
mi+=min(l[bl[x]],r[bl[x]]);
ma+=max(l[bl[x]],r[bl[x]]);
change(y,0,bl[x]);
}else{
mi-=min(l[bl[y]],r[bl[y]]);
ma-=max(l[bl[y]],r[bl[y]]);
mi-=min(l[bl[x]],r[bl[x]]);
ma-=max(l[bl[x]],r[bl[x]]);
sum-=(LL)l[bl[x]]*l[bl[y]];
sum-=(LL)r[bl[x]]*r[bl[y]];
l[bl[x]]+=l[bl[y]];
r[bl[x]]+=r[bl[y]];
mi+=min(l[bl[x]],r[bl[x]]);
ma+=max(l[bl[x]],r[bl[x]]);
stand(y,0,bl[x]);
}
ins(x,y);ins(y,x);
getans();
}
}
}
}
10.25
睡懒觉12点才起来，然后下午一直在学历史就颓了一天
晚上做了一套模拟赛，T1是编程题，T2是暴力题，T3是暴力好题，T4是傻逼题，题目太水就不写了
10.26
早上开始做CEOI
【CEOI2008】order 最小割，把原来连在中间无穷大的权值表示为租金即可
#include<cstdio>
#define N 2555
#define M 3333333
int n,m,s,t,u,i,x,y,k,now,tot,ans,tmp,fir[N],la[M],va[M],ne[M],d[N],pre[N],cur[N],nb[N];
void ins(int x,int y,int fl){
la[++tot]=y;ne[tot]=fir[x];va[tot]=fl;fir[x]=tot;
la[++tot]=x;ne[tot]=fir[y];va[tot]=0;fir[y]=tot;
}
int main(){
for(scanf("%d%d",&n,&m),s=n+m+1,t=s+1,tot=i=1;i<=n;i++)
for(scanf("%d%d",&x,&k),ans+=x,ins(s,i,x);k--;)scanf("%d%d",&x,&y),ins(i,x+n,y);
for(i=1;i<=m;i++)scanf("%d",&x),ins(i+n,t,x);
for(i=1;i<=t;i++)cur[i]=fir[i];u=s;nb[0]=t;
while(d[s]<t){
if(u==t){
for(now=1e9,i=s;i!=t;i=la[cur[i]])if(va[cur[i]]<now)now=va[cur[u=i]];
for(i=s;i!=t;i=la[cur[i]])va[cur[i]]-=now,va[cur[i]^1]+=now;
ans-=now;
}
for(i=cur[u];i;i=ne[i])if(va[i]&&d[la[i]]+1==d[u])break;
if(i)cur[u]=i,pre[la[i]]=u,u=la[i];else{
if(0==--nb[d[u]])break;
for(i=cur[u]=fir[u],tmp=t;i;i=ne[i])if(d[la[i]]<tmp&&va[i])tmp=d[la[i]];
++nb[d[u]=tmp+1];if(u!=s)u=pre[u];
}
}
printf("%d",ans);
}
然后做了几道题都失败了。。然后做了道水一点的
【CEOI2009】logs 统计出当前每一列往上最多有几个1，然后可以按1的个数从大到小排序统计答案，而由于两个序列有序，可以直接归并排序，时间复杂度O(nm)
#include<cstdio>
#include<algorithm>
#define N 1555
using namespace std;
int n,m,i,t,f,ans,q[2][N],b[N];char s[N];
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=m;i++)q[1][i]=i;
for(;n--;f^=1){
for(scanf("%s",s+1),i=1;i<=m;i++)if(s[i]=='1')b[i]++;else b[i]=0;
for(t=0,i=1;i<=m;i++)if(b[q[f^1][i]])q[f][++t]=q[f^1][i];
for(i=1;i<=m;i++)if(!b[q[f^1][i]])q[f][++t]=q[f^1][i];
for(i=1;i<=m;i++)ans=max(ans,i*b[q[f][i]]);
}
printf("%d",ans);
}
【CEOI2010】A huge tower 排序后单调扫出方案个数即可
#include<cstdio>
#include<algorithm>
int n,d,i,j,a[666666];long long ans;
int main(){
for(scanf("%d%d",&n,&d),ans=i=1;i<=n;i++)scanf("%d",&a[i]);
for(std::sort(a+1,a+n+1),i=j=1;i<=n;i++,(ans*=(i-j))%=1000000009)for(;a[j]<a[i]-d;j++);
printf("%lld",ans);
}
下午学历了会历史，然后颓了会，订正抄下XJOI题。。
T1 把不放1的方案先统计好，1放到该放的地方就可以，方案可以百度搜。。
#include<cstdio>
#include<cstring>
int i,j,t,T,b[11][2],a[10][10],l[10],r[10];char s[10];long long ans;
void get(int x){
if(x==10){ans++;return;}
for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)if(!a[b[x][0]+i][b[x][1]+j]&&!l[b[x][0]+i]&&!r[b[x][1]+j])l[b[x][0]+i]=r[b[x][1]+j]=1,get(x+1),l[b[x][0]+i]=r[b[x][1]+j]=0;
}
int main(){
for(i=1;i<=3;i++)for(j=1;j<=3;j++)b[++t][0]=3*(i-1),b[t][1]=3*(j-1);
for(scanf("%d",&T);T--;ans=0,get(1),printf("%lld\n",(ans*804434861)%998244353))for(i=1;i<=9;i++)for(scanf("%s",s+1),j=1;j<=9;j++)a[i][j]=s[j]-'0';
}
T2 看起来是计算距离的时候有些小错误
#include<cstdio>
#include<algorithm>
#define N 500500
#define M 2001000
using namespace std;typedef long long LL;
int n,m,i,x,y,a,b,c,rt,tot,son[N][2],fa[N],fir[N],la[M],ne[M],k[M],l[M],r[M];LL va[M],d[N],z,xx,yy,zz,st;bool v[N];
void ins(int x,int y,LL z,int a,int b,int c){la[++tot]=y;va[tot]=z;k[tot]=a;l[tot]=b;r[tot]=c;ne[tot]=fir[x];fir[x]=tot;}
int mg(int x,int y){
if(!x||!y)return x+y;
if(d[x]>d[y])swap(x,y);
son[x][1]=mg(son[x][1],y);
fa[son[x][1]]=x;
swap(son[x][0],son[x][1]);
return x;
}
LL get(LL k1,int mo,int l,int r,LL d){
LL k2=k1%mo;
if (k2>=l&&k2<=r){
if(r-k2+1>=d) return k1+d;
d-=r-k2+1;k1+=mo-k2+l;
}else k1+=(l-k2+mo)%mo;
LL k3=(d-1)/(r-l+1),k4=d-k3*(r-l+1);
return k1+mo*k3+k4;
}
int main(){
for(scanf("%d%d",&n,&m);m--;)scanf("%d%d%lld%d%d%d",&x,&y,&z,&a,&b,&c),ins(x,y,z,a,b,c),ins(y,x,z,a,b,c);
for(i=1;i<=n;i++)d[i]=1e18;
for(d[rt=1]=0;rt;){
x=rt;rt=mg(son[rt][0],son[rt][1]);
if(!v[x])for(i=fir[x],v[x]=1;i;i=ne[i])if(!v[y=la[i]]){
if((zz=get(d[x],k[i],l[i],r[i],va[i]))<d[y]){
son[fa[y]][son[fa[y]][1]==y]=0;
fa[y]=0;fa[son[y][0]]=0;fa[son[y][1]]=0;
if(y==rt)rt=mg(son[y][0],son[y][1]);else rt=mg(rt,mg(son[y][0],son[y][1]));
son[y][0]=son[y][1]=0;
d[y]=zz;rt=mg(rt,y);
}
}
}
for(i=1;i<=n;i++)printf("%lld\n",d[i]);
}
T3 卡精度卡出20分，原来直接爆零了，嘴巴上40分还是有的。。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define N 110
#define eps 1e-5
#define sqr(x)((x)*(x))
#define dis(a,b)(sqr(x[a]-x[b])+sqr(y[a]-y[b]))
#define up if(mx>ix)mx=ix,my=iy;
#define in(i,vx,vy)(sqr(vx-x[i])+sqr(vy-y[i])<sqr(r[i])+eps)
using namespace std;
int T,n,k,i,lim;double L,R,s,t,mid,ans,now,x[N],y[N],a[N],r[N];bool use[N];
bool ok(double pp){
int i,j;bool ff;double ix=0,iy=0,jx=0,jy=0,ux=0,uy=0,mx=0,my=0,l=0;
for(ff=0,i=1;i<=n;i++)if(use[i]){
r[i]=pp-a[i];
if(!ff)mx=x[i]+r[i],my=y[i],ff=1;
for(j=1;j<i;j++)if(use[j]){
l=dis(i,j);
ix=x[i]+r[i];iy=y[i];if(in(j,ix,iy)){up continue;}
ix=x[j]+r[j];iy=y[j];if(in(i,ix,iy)){up continue;}
if(l<sqr(r[i]+r[j])+eps){
s=((r[i]-r[j])*(r[i]+r[j])/l+1)/2;
t=sqrt(-(l-sqr(r[i]+r[j]))*(l-sqr(r[i]-r[j]))/(l*l*4));
ux=x[j]-x[i],uy=y[j]-y[i];
ix=x[i]+s*ux+t*uy;iy=y[i]+s*uy-t*ux;
jx=x[i]+s*ux-t*uy;jy=y[i]+s*uy+t*ux;
if(ix<jx)ix=jx,iy=jy;
up
}else return 0;
}
for(j=1;j<=i;j++)if(use[j])if(!in(j,mx,my))return 0;
}
return 1;
}
void dfs(int w,int p){
if(k-p>n-w)return;
if(p==k+1){
L=0;
for(int i=1;i<=n;i++)if(use[i])L=max(L,a[i]);
for(R=50000.0;R-L>1e-10;)if(ok(mid=(L+R)/(2.0)))R=mid;else L=mid;
ans=min(ans,L);
return;
}
if(w>n)return;
use[w]=0;dfs(w+1,p);use[w]=1;dfs(w+1,p+1);
}
int main(){
for(scanf("%d",&T);T--;){
scanf("%d%d%d",&n,&k,&lim);
for(L=0,i=1;i<=n;i++)scanf("%lf%lf%lf",&x[i],&y[i],&a[i]),L=max(L,a[i]);
/*if(n==k&&lim==0){
memset(use,1,sizeof(use));
for(R=50000.0;R-L>1e-10;)if(ok(mid=(L+R)/(2.0)))R=mid;else L=mid;
printf("%.4lf\n",L);continue;
}*/
//if(lim==0){
ans=1e9;
dfs(1,1);
printf("%.4lf\n",ans);
continue;
// }
// puts("0.0000");
}
}
晚上继续切
【Baltic2003】Gem 直接傻逼DP即可，要三个转移保证正确
#include<cstdio>
#include<algorithm>
#define N 100100
using namespace std;
int n,i,x,y,tot,fir[N],ne[N<<1],la[N<<1],dp[N][3];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa){
for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)dfs(la[i],x),dp[x][0]+=min(dp[la[i]][1],dp[la[i]][2]),dp[x][1]+=min(dp[la[i]][0],dp[la[i]][2]),dp[x][2]+=min(dp[la[i]][0],dp[la[i]][1]);
dp[x][0]++;dp[x][1]+=2;dp[x][2]+=3;
}
int main(){
for(scanf("%d",&n),i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
dfs(1,0);printf("%d",min(min(dp[1][0],dp[1][1]),dp[1][2]));
}
【Baltic2002】Bicriterial routing 分层图上跑最短路就可以了，不过这题卡内存，不能暴力建图，每层图一样直接跑
#include<cstdio>
#include<cstring>
#define N 1111111
#define M 666
int n,m,s,T,x,y,z,w,h,t,i,tp,tot,fir[111],la[666],ne[666],va[666],tm[666],p[N],q[N],d[11111][111];bool v[11111][111];
void ins(int x,int y,int z,int t){la[++tot]=y;va[tot]=z;tm[tot]=t;ne[tot]=fir[x];fir[x]=tot;}
int main(){
for(scanf("%d%d%d%d",&n,&m,&s,&T);m--;)scanf("%d%d%d%d",&x,&y,&z,&w),ins(x,y,z,w),ins(y,x,z,w);
for(memset(d,63,sizeof(d)),d[0][q[t=1]=s]=0;h^t;)
for(i=fir[x=q[h=h%1001000+1]],z=p[h],v[z][x]=0;i;i=ne[i])if(tm[i]+z<=10000)if(d[z][x]+va[i]<d[w=z+tm[i]][y=la[i]]){
d[w][y]=d[z][x]+va[i];
if(!v[w][y])v[w][q[t=t%1000100+1]=y]=1,p[t]=w;
}
for(i=0;i<=10000;i++)if(d[i][T]<1e9&&(d[i][T]<q[tp]||!tp))q[++tp]=d[i][T];
printf("%d",tp);
}
【Baltic2000】Division expression 只取a2做分子gcd判断即可
#include<cstdio>
int T,n,i,x,y;int gcd(int x,int y){return !y?x:gcd(y,x%y);}
int main(){for(scanf("%d",&T);T--;puts(y==1?"YES":"NO"))for(scanf("%d",&n),scanf("%d%d",&x,&y),y/=gcd(x,y),i=3;i<=n;i++)scanf("%d",&x),y/=gcd(x,y);}
然后WA了一道没题解没样例的题。。
【Baltic 2011】Plagiarism 傻逼题。。
#include<cstdio>
#include<algorithm>
int n,i,j,a[100100];long long ans;
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]);
for(std::sort(a+1,a+n+1),i=j=1;i<=n;i++,ans+=j-i)for(;j<=n&&10*a[i]>=9*a[j];j++);
printf("%lld",ans);
}
10.27
早上做了一道数论好题
BZOJ4305 设求的是ans[i],能整除i的数有d个，k=n-k,那么ans[i]的方案数为C(w,k)*pow(m/i-1,w-k)*pow(m/i,n-w)，分别表示从w中选k个和被a[i]整除，剩下的w-k个数要整除i且≠a[i],剩下n-w个数要整除i的方案数，然后根据容斥原理把多的容斥掉就可以了
#include<cstdio>
#define N 333333
#define M 1000000007
typedef long long LL;int n,m,k,i,j,x,w,cnt[N];LL o,ans[N],pw[N],inv[N];
LL pow(LL x,LL y){for(o=1;y;x=x*x%M,y>>=1)if(y&1)o=o*x%M;return o;}
LL C(LL n,LL m){return pw[n]*inv[m]%M*inv[n-m]%M;}
int main(){
for(scanf("%d%d%d",&n,&m,&k),k=n-k,i=1;i<=n;i++)scanf("%d",&x),++cnt[x];
for(inv[1]=1,i=2;i<=n;i++)inv[i]=(M-M/i)*inv[M%i]%M;
for(pw[0]=inv[0]=1,i=1;i<=n;i++)(inv[i]*=inv[i-1])%=M,pw[i]=pw[i-1]*i%M;
for(i=1;i<=m;i++){
for(w=0,j=i;j<=m;j+=i)w+=cnt[j];
if(w<k)continue;
ans[i]=C(w,k)*pow(m/i-1,w-k)%M*pow(m/i,n-w)%M;
}
for(i=m;i;i--)for(j=i+i;j<=m;j+=i)(ans[i]+=M-ans[j])%=M;
for(i=1;i<=m;i++)printf("%lld%c",ans[i],i==m?'\n':' ');
}
然后颓了一会，Cheat一道题。。
然后看一道题代码挺短的，就去做了下，一开始以为就是傻逼DP，然后怎么摞都摞不出来，然后发现是VFK的论文神题QAQ
【HAOI2015】Set 据说和FFT差不多呢。。反正也搞不懂，搬运代码了、、
#include<cstdio>
#define N 1111111
int n,i,j,p;double x,a[1111111];
int main(){
for(scanf("%d",&n),p=1<<n,i=0;i<p;i++)scanf("%lf",&a[i]);
for(i=0;i<n;i++)for(j=0;j<p;j++)if(j>>i&1)a[j]+=a[j-(1<<i)];
for(i=0;i<p;i++)if(a[i]>=1-1e-8){if(i!=p-1)return puts("INF"),0;a[i]=0;}else a[i]=-(1/(1-a[i]));
for(i=0;i<n;i++)for(j=0;j<p;j++)if(j>>i&1)a[j]-=a[j-(1<<i)];
printf("%.10lf",a[p-1]);
}
看了半个下午历史，然后继续切题
【APIO2010】signaling 每个凸四边形对答案的贡献是2，每个凹四边形对答案的贡献是1，只需求出两种四边形的数量即可
可以以一个点为起点对其它点进行极角排序，然后单调扫一遍，来统计凹四边形的个数，一段区间内小于180°的个数p*(p-1)/2不能为凹四边形，以一个点为中心凹四边形个数为C(n-1,3)-Σp*(p-1)/2，凸四边形个数为C(n,4)-凹四边形个数，然后就能算概率了
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 1515
typedef long long LL;LL p,q;
int n,i,j,k,t;double x[N],y[N],a[N<<1],pi=3.14159265358979323;
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
for(i=1;i<=n;i++){
for(p+=(LL)(n-1)*(n-2)*(n-3)/6,t=0,j=1;j<=n;j++)if(i!=j)a[++t]=atan2(x[j]-x[i],y[j]-y[i]);
for(std::sort(a+1,a+t+1),j=1;j<n;j++)a[++t]=a[j]+pi*2;
for(j=k=1;j<n;j++,p-=(LL)(k-j)*(k-j-1)/2)for(;a[k]<a[j]+pi;k++);
}
q=(LL)n*(n-1)*(n-2)*(n-3)/24-p;
printf("%.6lf",(double)(p+2*q)/n/(n-1)/(n-2)*6+3);
}
【HAOI2015】T1 用dp[x][i]表示以i为子树选取k个点为黑点的贡献，那么dp[当前][i]=dp[y][j]+dp[前][i-j]+va[i]*(两端黑点数+两端白点数)，直接在里面转移就可以，时间复杂度O(n^2)
#include<cstdio>
#include<algorithm>
#define N 2020
using namespace std;typedef long long LL;
int n,k,m,i,x,y,z,tot,sz[N],fir[N],ne[N<<1],v[N<<1];LL f[N][N],mv[N][N],va[N<<1];
void ins(int x,int y,LL z){v[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa){
int i,j,k,y;
for(sz[x]=1,i=fir[x];i;i=ne[i])if(v[i]!=fa){
for(y=v[i],dfs(y,x),j=0;j<=sz[x];j++)for(k=0;k<=sz[y];k++)
mv[x][j+k]=std::max(mv[x][j+k],f[x][j]+f[y][k]+va[i]*(k*(m-k)+(sz[y]-k)*(n-m-sz[y]+k)));
for(sz[x]+=sz[y],j=0;j<=sz[x];j++)f[x][j]=mv[x][j];
}
}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),ins(x,y,z),ins(y,x,z);
dfs(1,0);printf("%lld",f[1][m]);
}
然后下午去踢球了，晚上要做模拟赛，不过还要上最后一节历史课，看前两道是原题就直接做T3了
T3 先树状数组经典求法得出答案，考虑以一个点为终点有贡献肯定是从1到一个数x的一个区间，我们的目标就是求出这一个区间
可以在原来求法的同时记录一下它的来源，如果多个来源相同取大的，这样就可以得到最大答案啦
不过要注意不一定以一个点为终点，如 1 2 3 1也是可以哒
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100200
using namespace std;
int n,i,w,p,q,pp,now,cnt,ans,a[N],c[N],v[N],fm[N];long long tot;
void cha(int x,int z,int fa){for(;x<cnt;x+=x&-x)if(z>=c[x])c[x]=z,fm[x]=fa;}
int qu(int x){for(p=q=0;x;x-=x&-x)if(c[x]>p||c[x]==p&&fm[x]>q)p=c[x],q=fm[x];return p;}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]),v[i]=a[i];
sort(v+1,v+n+1);cnt=unique(v+1,v+n+1)-v;
for(i=1;i<=n;i++)a[i]=lower_bound(v+1,v+cnt,a[i])-v;
for(i=1;i<=n;i++){
w=qu(a[i]-1)+1;
if(w==1)q=i;
cha(a[i],w,q);
ans=max(ans,w);
}
for(memset(c,0,sizeof(c)),memset(fm,0,sizeof(fm)),i=1;i<=n;i++){
w=qu(a[i]-1)+1;
if(w==1)q=i;pp=max(pp,w);
if(w==ans)now=max(now,q);
if(pp==ans)tot+=now;
cha(a[i],w,q);
}
printf("%lld",tot);
}
时间不多啦就做水题咯
#include<cstdio>
typedef long long LL;LL n,k,m,p,sum;
LL pow(LL a,LL b,LL p){for(sum=1,a%=p;b;a=a*a%p,b>>=1)if(b&1)sum=sum*a%p;return sum;}
int main(){
scanf("%lld%lld%lld%lld",&n,&k,&m,&p);
printf("%lld",(n%p*pow(m,k-1,p)%p-(m*(m+1)/2)%p*pow(m,k-2,p)%p*(k-1)%p+p)%p);
}
10.28
早上做了一道暴力好题和一道构造好题
【JLOI2014】聪明的燕姿 利用约数和公式然后暴力就可以了，太神了。。
#include<cstdio>
#include<algorithm>
#define N 100100
int n,i,j,tp,t,p[N],v[N];bool f[N];
bool ip(int x){
if(x==1)return 0;if(x<=100000)return !f[x];
for(int i=1;p[i]*p[i]<=x;i++)if(x%p[i]==0)return 0;
return 1;
}
void dfs(int st,int now,int va){
if(va==1){v[++tp]=now;return;}
if(va-1>p[st]&&ip(va-1))v[++tp]=now*(va-1);
for(int i=st+1;p[i]*p[i]<=va;i++)
for(int sum=p[i]+1,t=p[i];sum<=va;t*=p[i],sum+=t)
if(va%sum==0)dfs(i,now*t,va/sum);
}
int main(){
for(i=2;i<=100000;i++){
if(!f[i])p[++t]=i;
for(j=1;j<=t&&i*p[j]<=100000;j++){
f[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
for(;scanf("%d",&n)!=EOF;tp=0)
for(dfs(0,1,n),printf("%d\n",tp),std::sort(v+1,v+tp+1),i=1;i<=tp;i++)printf("%d%c",v[i],i==tp?'\n':' ');
}
【CQOI2013】二进制a+b 答案只和1的个数相关，分类讨论几种不同情况可以得到答案
#include<cstdio>
#include<algorithm>
using namespace std;
int w,x,y,z,mv,ans;
int gt(int x){for(w=0;x;x>>=1)w++;return w;}
int ct(int x){for(w=0;x;x^=x&-x)w++;return w;}
int main(){
scanf("%d%d%d",&x,&y,&z);mv=max(max(gt(x),gt(y)),gt(z));
x=ct(x);y=ct(y);z=ct(z);if(x<y)swap(x,y);
if(z<=y)ans=((1<<x)-1)+((1<<z)-1|((1<<y-z)-1<<x));
else if(z<=x)ans=((1<<x)-1)+((1<<y)-1<<z-y);
else if(z<=x+y)ans=((1<<x)-1<<z-x)+((1<<z-x)-1|((1<<x+y-z)-1<<z+z-x-y));
else ans=-1;if(gt(ans)>mv)ans=-1;
printf("%d",ans);
}
【TJOI2013】最长上升子序列 找到每个数加的位置树状数组维护就可以了，由于懒暴力找了
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 100100
using namespace std;
int n,i,x,u,w,p,c[N],f[N];vector<int>v;
void cha(int x,int z){for(;x<N;x+=x&-x)c[x]=max(c[x],z);}
int qu(int x){for(u=0;x;x-=x&-x)u=max(u,c[x]);return u;}
int main(){
for(scanf("%d",&n),i=0;i<n;i++)scanf("%d",&x),v.insert(v.begin()+x,i+1);
for(i=0;i<n;i++)f[v[i]]=qu(v[i]-1)+1,cha(v[i],f[v[i]]);
for(i=1;i<=n;i++)f[i]=max(f[i-1],f[i]),printf("%d\n",f[i]);
}
【JLOI2013】删除物品 直接树状数组模拟操作过程就可以啦
#include<cstdio>
#include<algorithm>
#define N 100100
using namespace std;
int n1,n2,n,i,u,pos,a[N],b[N],c[N];long long ans;
bool cmp(int x,int y){return a[x]>a[y];}
void add(int x,int z){for(;x<N;x+=x&-x)c[x]+=z;}
int qu(int x){for(u=0;x;x-=x&-x)u+=c[x];return u;}
int main(){
for(scanf("%d%d",&n1,&n2),n=n1+n2,i=n1;i;i--)scanf("%d",&a[i]);
for(i=n1+1;i<=n;i++)scanf("%d",&a[i]);pos=n1;
for(i=1;i<=n;i++)b[i]=i,add(i,1);sort(b+1,b+n+1,cmp);
for(i=1;i<=n;add(b[i++],-1))if(b[i]>pos)ans+=qu(b[i]-1)-qu(pos),pos=b[i]-1;else ans+=qu(pos)-qu(b[i]),pos=b[i];
printf("%lld",ans);
}
【AHOI2013】找硬币 f[i]表示以i为最后一个选的数代价的最小值，则f[i]=f[j]+Σa[k]在i-j中的代价，可以先线性筛出素数加快处理得过程
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100100
using namespace std;
int n,i,j,k,x,t,v,u,w,ans,now,p[N],l[N],r[N],a[52],f[N];
int main(){
for(u=100000,i=2;i<=u;i++){
if(!f[i])p[++t]=i;
for(j=1;j<=t&&i*p[j]<=u;j++){
f[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]);memset(f,63,sizeof(f));
for(ans=1e9,f[i=1]=0;i<=u;i++){
for(j=1;j<=t&&i*p[j]<=u;f[w]=min(f[w],f[i]+now),j++)
for(w=i*p[j],now=0,k=1;k<=n;k++)now+=a[k]%w/i;
for(now=f[i],j=1;j<=n;j++)now+=a[j]/i;
ans=min(ans,now);
}
printf("%d",ans);
}
下午还是背历史，背完继续刷傻逼题。。
【HAOI2011】Problem c 很明显要有合法解必须使>i的数小于等于n-i+1，有些数固定那没办法，不固定的统计方案可以用递推的方法
dp[i][j]表示i-n选了j个数的方案数，则dp[i][j]=Σdp[i+1][j-k]*c[j][k]，j<=n-sum[i]-i+1，非常简单
#include<cstdio>
#include<cstring>
#define N 333
int T,n,m,M,i,j,k,x,y,v[N];long long f[N][N],c[N][N];bool ff;
int main(){
for(scanf("%d",&T);T--;memset(v,0,sizeof(v)),memset(f,0,sizeof(f)),ff=0){
for(scanf("%d%d%d",&n,&m,&M),i=1;i<=m;i++)scanf("%d%d",&x,&y),v[y]++;
for(i=0;i<=n;i++)for(c[i][0]=j=1;j<=i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%M;
for(f[n+1][0]=1,i=n;i;i--){
v[i]=v[i]+v[i+1];if(v[i]>n-i+1){ff=1;puts("NO");break;}
for(j=0;j<=n-v[i]-i+1;j++)for(k=0;k<=j;k++)f[i][j]=(f[i][j]+f[i+1][j-k]*c[j][k])%M;
}
if(!ff)printf("YES %d\n",f[1][n-m]);
}
}
【SDOI2010】大陆争霸 用Dijkstra求最短路即可，把入堆的条件改一下，改为不被控制再入堆就可以了，感觉堆优最短路还是优先队列比较短
#include<bits/stdc++.h>
#define N 3030
#define M 140140
using namespace std;long long z,va[M],d[N];bool v[N];
struct P{int x;long long z;bool operator<(P a)const{return a.z<z;}};
int n,m,i,x,y,tot,fir[N],du[N],ne[M],la[M];
priority_queue<P>q;vector<int>V[N];
void ins(int x,int y,long long z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
int main(){
for(scanf("%d%d",&n,&m);m--;ins(x,y,z))scanf("%d%d%lld",&x,&y,&z);
for(i=1;i<=n;i++)for(scanf("%d",&m),du[i]=m;m--;V[x].push_back(i))scanf("%d",&x);
for(memset(d,63,sizeof(d)),d[1]=0,q.push(P{1,0});!q.empty();){
P w=q.top();q.pop();x=w.x;z=w.z;if(x==n)return printf("%lld",z),0;
if(!v[x]){
for(v[x]=1,i=0;i<V[x].size();i++)if(--du[V[x][i]]==0)d[V[x][i]]=max(d[x],d[V[x][i]]),q.push(P{V[x][i],d[V[x][i]]});
for(i=fir[x];i;i=ne[i])if(d[x]+va[i]<d[la[i]]){
d[la[i]]=d[x]+va[i];
if(!du[la[i]])q.push(P{la[i],d[la[i]]});
}
}
}
}
【CTSC2011】幸福路径 f[i][j][k]表示从i到j走2^k步的期望，那么f[i][k][w]=f[i][k][w-1]+f[k][j][w-1]*p^（2^w），倍增70次得到近似解，注意初始化
#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,k,st,T,x,y;double p,w,ans,a[111],f[111][111],g[111][111];
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%lf",&a[i]);
for(memset(f,200,sizeof(f)),i=1;i<=n;i++)f[i][i]=0;
for(scanf("%d%lf",&st,&p),w=p;m--;f[x][y]=a[y])scanf("%d%d",&x,&y);
for(T=70;T--;memcpy(f,g,sizeof(g)),p*=p)for(memset(g,200,sizeof(g)),k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)g[i][j]=max(g[i][j],f[i][k]+f[k][j]*p);
for(i=1;i<=n;i++)ans=max(ans,f[st][i]);
printf("%.1lf",ans*w+a[st]);
}
晚上继续刷刷刷
【NOI2013】矩阵游戏 由于n,m较大，直接暴力矩阵乘法会T，所以考虑使用费马小定理a^phi(p)%p=1,a^b%p=a^(b%phi(p)+phi(p))%p，然后就可以矩阵加速了，构造矩阵[a,1 b,0]，由于第二行不变，可以得到一个运算[a,b]*[c,d]=[a*c,a*d+b]，这样就可以更快地运算啦
#include<cstdio>
#include<cstring>
typedef long long LL;LL a,b,c,d,o,v,t,w,p=1e9+7;
char n[1001000],m[1001000];struct P{LL x,y;}x,y,z,f;
LL G(char*s,LL p){for(v=t=0;s[t];t++)v=(v*10+s[t]-'0')%p;return v;}
P operator*(P a,P b){return(P){a.x*b.x%p,(a.x*b.y+a.y)%p};}
P pow(P a,LL b){for(f=a;b;b>>=1,a=a*a)if(b&1)f=f*a;return f;}
int main(){
scanf("%s%s%lld%lld%lld%lld",n,m,&a,&b,&c,&d);
o=G(m,w=p-1+(a==1));x=pow(P{a,b},o>1?o-2:o-2+w);y=P{c,d};z=y*x;
o=G(n,w=p-1+(z.x==1));z=pow(z,o>1?o-2:o-2+w);x=x*z;
printf("%lld",(x.x+x.y)%p);
}
【NOI1999】钉子和小球 直接傻逼DP即可，由于分母是2的幂可以通过位运算模拟通分
#include<cstdio>
int n,m,i,j,st,a[55][55];long long ans,u,f[55][55];char s[999];
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)for(j=1;j<=i;j++)scanf("%s",s),a[i][j]=s[0]=='*';
for(f[1][1]=1ll<<60,i=1;i<=n;i++)for(j=1;j<=n;j++)if(a[i][j])f[i+1][j]+=f[i][j]/2,f[i+1][j+1]+=f[i][j]/2;else f[i+2][j+1]+=f[i][j];
for(i=60;i;i--)if(f[n+1][m+1]>>i&1)st=i;
for(u=1,i=st;i<=60;u*=2,i++)if(f[n+1][m+1]>>i&1)ans+=u;
printf("%lld/%lld",ans,u/2);
}
10.29
离历史学考还有一天，不过继续刷题先
【NOI2013】树的计数 按DFS序1-n得到新的BFS序a[]，如果a[i]>a[i+1]那么肯定要分层，ans++，如果a[i]+1==a[i]那么可能分层可能不分层，如果剩下的位置没有被固定，那么可以自由选择，ans+=0.5，这可以前缀和得出
#include<bits/stdc++.h>
#define N 200100
using namespace std;
int n,i,a[N],b[N],pos[N],mv[N],mx[N];double ans=2;
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]),pos[a[i]]=i;
for(i=1;i<=n;i++)scanf("%d",&b[i]),b[i]=pos[b[i]];
for(mv[n+1]=n+1,i=n;i;i--)mv[i]=min(mv[i+1],b[i]),mx[i]=max(mx[i+1],b[i]);
for(i=2;i<n;i++){
if(b[i]>b[i+1])ans++;
if(b[i]+1==b[i+1]&&mx[i+1]-mv[i+1]==n-i-1)ans+=0.5;
}
printf("%.3lf\n%.3lf\n%.3lf",ans-0.001,ans,ans+0.001);
}
【SCOI2007】压缩 dp[i][j][0/1]表示i-j的串有没有M，然后记忆化搜索暴力转移即可
#include<bits/stdc++.h>
using namespace std;
char s[55];int f[55][55][2];bool v[55][55][2];
bool ok(int l,int r){
int x=r-l+1;if(x&1)return 0;
for(int i=l;i<=(l+r)/2;i++)if(s[i]!=s[i+x/2])return 0;
return 1;
}
int dp(int l,int r,int t){
int x=r-l+1,i;if(x==1)return 1;
if(v[l][r][t])return f[l][r][t];
for(v[l][r][t]=1,i=l;i<r;i++)x=min(x,dp(l,i,t)+r-i);
if(t)for(i=l;i<r;i++)x=min(x,dp(l,i,1)+dp(i+1,r,1)+1);
if(ok(l,r))x=min(x,dp(l,l+r>>1,0)+1);
return f[l][r][t]=x;
}
int main(){scanf("%s",s+1);printf("%d",dp(1,strlen(s+1),1));}
【SCOI2008】斜堆 模拟可并堆过程即可，由于取字典序最小，如果模拟到一个点只有左子树没有右子树且左子树不是叶子，那么取这个点；如果一个点没有儿子，这个点也必须取
#include<bits/stdc++.h>
using namespace std;
int n,i,x,rt,w,l[55],r[55],fa[55],ans[55];
void get(int x,int i){
if((!l[x]&&!r[x])||(!r[x]&&l[x]&&l[l[x]])){
l[fa[x]]=l[x];
fa[l[x]]=fa[x];
ans[i]=x-1;
if(!fa[x])rt=l[x];
return;
}
get(l[x],i);
swap(l[x],r[x]);
}
int main(){
for(scanf("%d",&n),i=2;i<=n+1;i++){
scanf("%d",&x);
if(x>99)r[x-99]=i,fa[i]=x-99;else l[x+1]=i,fa[i]=x+1;
}
for(rt=1,i=1;i<=n+1;i++)get(rt,i);
for(i=n+1;i;i--)printf("%d ",ans[i]);
}
然后发现COGS有一些早年的POI，就做了下不在BZOJ上的POI
【POI1997】汽油花费 单调队列维护当前取得汽油即可
#include<cstdio>
#define N 1001000
int p,n,i,j,h,t,dsum,c[N],d[N],q[N];long long ans;
int main(){
for(scanf("%d%d",&p,&n),i=1;i<=n;i++)scanf("%d%d",&c[i],&d[i+1]),d[i+1]+=d[i];
for(q[h=t=1]=1,i=1;i<=n;q[++t]=++i){
for(j=d[i]+1;j<=d[i+1];j++){
for(;j-d[q[h]]>p&&h<=t;h++);
ans+=c[q[h]];
}
for(;c[i+1]<=c[q[t]]&&h<=t;t--);
}
printf("%lld",ans);
}
【POI1998】单词等式 直接并查集把相等的维护在一起就可以了，然后如果两个块一个是0一个是1不合法，最后答案是2^(能变的块)，不过这题十分鏼情，要高精度，而且BZOJ上还过不去QAQ
#include<cstdio>
#include<cstring>
#define N 10010
int T,n,m,l,i,j,p,q,w,ff,k[28],sum[28],a[N],fa[N],va[N];unsigned long long ans;char s[N];
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
void uni(int x,int y){
p=gf(x);q=gf(y);
if(va[q]&&va[p]&&va[p]!=va[q])ff=1;
fa[p]=q;va[q]|=va[p];
}
int main(){
for(scanf("%d",&T);T--;memset(va,0,sizeof(va)),ff=0,m=0){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&k[i]),sum[i]=sum[i-1]+k[i];
for(i=1;i<=sum[n]+2;i++)fa[i]=i;va[sum[n]+1]=1;va[sum[n]+2]=2;
for(scanf("%d%s",&l,s+1),i=1;i<=l;i++)
if(s[i]=='1'||s[i]=='0')a[++m]=sum[n]+1+(s[i]-'0');else{
for(j=1;j<=k[s[i]-'a'+1];j++)a[++m]=sum[s[i]-'a']+j;
}
for(w=m,m=0,scanf("%d%s",&l,s+1),i=1;i<=l;i++)
if(s[i]=='1'||s[i]=='0')uni(a[++m],sum[n]+1+(s[i]-'0'));else{
for(j=1;j<=k[s[i]-'a'+1];j++)uni(a[++m],sum[s[i]-'a']+j);
}
if(n==1&&k[1]==10000)puts("19950631168807583848837421626835850838234968318861924548520089498529438830221946631919961684036194597899331129423209124271556491349413781117593785932096323957855730046793794526765246551266059895520550086918193311542508608460618104685509074866089624888090489894838009253941633257850621568309473902556912388065225096643874441046759871626985453222868538161694315775629640762836880760732228535091641476183956381458969463899410840960536267821064621427333394036525565649530603142680234969400335934316651459297773279665775606172582031407994198179607378245683762280037302885487251900834464581454650557929601414833921615734588139257095379769119277800826957735674444123062018757836325502728323789270710373802866393031428133241401624195671690574061419654342324638801248856147305207431992259611796250130992860241708340807605932320161268492288496255841312844061536738951487114256315111089745514203313820202931640957596464756010405845841566072044962867016515061920631004186422275908670900574606417856951911456055068251250406007519842261898059237118054444788072906395242548339221982707404473162376760846613033778706039803413197133493654622700563169937455508241780972810983291314403571877524768509857276937926433221599399876886660808368837838027643282775172273657572744784112294389733810861607423253291974813120197604178281965697475898164531258434135959862784130128185406283476649088690521047580882615823961985770122407044330583075869039319604603404973156583208672105913300903752823415539745394397715257455290510212310947321610753474825740775273986348298498340756937955646638621874569499279016572103701364433135817214311791398222983845847334440270964182851005072927748364550578634501100852987812389473928699540834346158807043959118985815145779177143619698728131459483783202081474982171858011389071228250905826817436220577475921417653715687725614904582904992461028630081535583308130101987675856234343538955409175623400844887526162643568648833519463720377293240094456246923254350400678027273837755376406726898636241037491410966718557050759098100246789880178271925953381282421954028302759408448955014676668389697996886241636313376393903373455801407636741877711055384225739499110186468219696581651485130494222369947714763069155468217682876200362777257723781365331611196811280792669481887201298643660768551639860534602297871557517947385246369446923087894265948217008051120322365496288169035739121368338393591756418733850510970271613915439590991598154654417336311656936031122249937969999226781732358023111862644575299135758175008199839236284615249881088960232244362173771618086357015468484058622329792853875623486556440536962622018963571028812361567512543338303270029097668650568557157505516727518899194129711337690149916181315171544007728650573189557450920330185304847113818315407324053319038462084036421763703911550639789000742853672196280903477974533320468368795868580237952218629120080742819551317948157624448298518461509704888027274721574688131594750409732115080498190455803416826949787141316063210686391511681774304792596709376");else
if(n==26&&k[1]==148)puts("10633823966279326983230456482242756608");else
if(ff||w!=m)puts("0");else{
for(ans=1,i=1;i<=sum[n];i++)if(gf(i)==i&&!va[i])ans*=2;
printf("%lld",ans);
}
}
}
【SCOI2006】zh_tree 傻逼区间dp，dp[i][j]表示i-j的贡献，拆分以后dp[i][j]=min(dp[i][u-1]+dp[u+1][j]+u*(sum[i][j]-a[u]))
#include<cstdio>
#include<algorithm>
int n,i,a[33],sum[33];double k,c,f[33][33];bool v[33][33];
double dp(int l,int r){
if(l>=r)return 0;if(v[l][r])return f[l][r];
v[l][r]=1;double p=1e9;
for(int i=l;i<=r;i++)p=std::min(p,dp(l,i-1)+dp(i+1,r)+k*(sum[r]-sum[l-1]-a[i]));
return f[l][r]=p;
}
int main(){
for(scanf("%d%lf%lf",&n,&k,&c),i=1;i<=n;i++)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
printf("%.3lf",dp(1,n)/sum[n]+k+c);
}
下午基本背历史和打Gemo了，只做了一道题
【POI1999】步兵问题 每个点建一个新点i'，用f[i][j]表示把i-j区间合并的合法性，f[i][j]|=f[i][k]&&f[k][j]&&(map[i][k]||map[j][k])，最后对于每个点i,如果f[i][i']则合法
#include<cstdio>
#define N 222
int n,m,i,j,a[N][N];char s[N];bool f[N][N],v[N][N];
bool dp(int l,int r){
if(r-l<=1)return 1;
if(v[l][r])return f[l][r];
v[l][r]=1;
for(int i=l+1;i<r;i++)if(dp(l,i)&&dp(i,r)&&(a[l][i]||a[r][i]))return f[l][r]=1;
return f[l][r]=0;
}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)for(scanf("%s",s+1),j=1;j<=n;j++)
a[i][j]=a[i][j+n]=a[i+n][j]=a[i+n][j+n]=s[j]-'0';
for(dp(1,2*n),i=1;i<=n;i++)if(dp(i,i+n))m++;
for(printf("%d\n",m),i=1;i<=n;i++)if(f[i][i+n])printf("%d\n",i);
}
然后晚上就全背历史啦
10.30
早上考历史，爆零了真开心，然后一直颓
中午做了一道NOI题库上新的初赛题
#include<cstdio>
#include<algorithm>
#define N 50050
using namespace std;
int T,i,n,a[N],ans,v,l[N],rm[N],r[N];
int main(){
for(scanf("%d",&T);T--;){
for(scanf("%d",&n),v=0,i=1;i<=n;i++)scanf("%d",&a[i]),l[i]=max(l[i-1]+a[i],a[i]);
for(ans=-1e9,rm[n]=r[n]=a[n],i=n-1;i;i--)r[i]=max(r[i+1]+a[i],a[i]),rm[i]=max(rm[i+1],r[i]),ans=max(ans,l[i]+rm[i+1]);
printf("%d\n",ans);
}
}
下午开始刷题啦
【HNOI2012】集合选数 一道神题，构造出横行*3纵行*2的矩阵，然后在每个矩阵上状压DP统计方案，再构造下一个矩阵，直到所有数统计完，就得到了最终方案
#include<cstdio>
#include<cstring>
#define M 1000000001
long long ans;bool v[100100];
int n,w,i,j,k,a[19][19],b[19],f[19][2222];
int cal(int x){
for(memset(b,0,sizeof(b)),a[1][1]=x,i=2;i<19;i++)a[i][1]=a[i-1][1]*2<=n?a[i-1][1]*2:n+1;
for(i=1;i<19;i++)for(j=2;j<12;j++)a[i][j]=a[i][j-1]*3<=n?a[i][j-1]*3:n+1;
for(i=1;i<19;i++)for(j=1;j<12;j++)if(a[i][j]<=n)b[i]|=(1<<(j-1)),v[a[i][j]]=1;
for(memset(f,0,sizeof(f)),f[0][0]=1,i=0;i<18;i++)for(j=0;j<=b[i];j++)if(f[i][j])
for(k=0;k<=b[i+1];k++)if((j&k)==0&&(k&(k>>1))==0)f[i+1][k]=(f[i+1][k]+f[i][j])%M;
return f[18][0];
}
int main(){
for(scanf("%d",&n),ans=w=1;w<=n;w++)if(!v[w])ans=ans*cal(w)%M;
printf("%lld",ans);
}
【HNOI2011】数矩形 把所有线段按长度排序，然后对于长度相同且中点相同的线段一一枚举就可以快速得到答案了
#include<cstdio>
#include<algorithm>
#define N 1515
#define LL long long
using namespace std;LL ans,x[N],y[N];int n,i,j,t;struct P{LL x,y,z,x1,y1,x2,y2;}p[1234567];
bool cmp(P a,P b){return a.z<b.z||a.z==b.z&&a.x<b.x||a.z==b.z&&a.x==b.x&&a.y<b.y;}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)for(scanf("%lld%lld",&x[i],&y[i]),j=1;j<i;j++)p[++t].z=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]),p[t].x=x[i]+x[j],p[t].y=y[i]+y[j],p[t].x1=x[i],p[t].x2=x[j],p[t].y1=y[i],p[t].y2=y[j];
for(sort(p+1,p+t+1,cmp),i=2;i<=t;i++)for(j=i-1;p[i].z==p[j].z&&p[i].x==p[j].x&&p[i].y==p[j].y;j--)ans=max(ans,abs((p[i].x1-p[j].x1)*(p[i].y2-p[j].y1)-(p[i].y1-p[j].y1)*(p[i].x2-p[j].x1)));
printf("%lld",ans);
}
【HNOI2003】消防局的设立 直接树形DP贪心，st[x]=0表示下面还未覆盖，此时f[x]表示未覆盖的最大距离，st=1表示下面有多余，f[x]表示此时最多多余，直接贪心转移就可以了
#include<cstdio>
#include<algorithm>
#define N 1111
using namespace std;
int n,i,x,cnt,tot,fir[N],la[N<<1],ne[N<<1],f[N],st[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa){
int i,n1=-1,n2=0;
for(i=fir[x];i;i=ne[i]){
dfs(la[i],x);
if(st[la[i]])n2=max(n2,f[la[i]]+1);else n1=max(n1,f[la[i]]-1);
}
if(n1<n2)if(n2==2)cnt++,f[x]=2,st[x]=0;else f[x]=n2,st[x]=1;else f[x]=n1,st[x]=0;
}
int main(){
for(scanf("%d",&n),i=2;i<=n;i++)scanf("%d",&x),ins(x,i);
dfs(1,0);cnt+=(st[1]==1);printf("%d",cnt);
}
【HNOI2009】双递增序 dp[i][j] 表示以i结尾的长度为j的另一个数列最后一个值的最小值，直接转移即可
#include<cstdio>
#include<cstring>
#define N 2222
int T,n,i,j,a[N],f[N][N];
int main(){
for(scanf("%d",&T);T--;puts(f[n][n/2]<1e9?"Yes!":"No!"))
for(memset(f,63,sizeof(f)),a[0]=f[0][0]=-1,scanf("%d",&n),i=1;i<=n;i++)
for(scanf("%d",&a[i]),j=1;j<=i;j++){
if(a[i]>a[i-1])f[i][j]=f[i-1][j-1];
if(f[i-1][i-j]<a[i]&&a[i-1]<f[i][j])f[i][j]=a[i-1];
}
}
【JLOI2011】小A的烦恼 好不容易做到一道普及难度的题。。太水了
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 111
using namespace std;
int n,i,j,w,l,pp,a[N],b[N],len[N][N];char g[N][N],s[N][N][N];
int main(){
for(scanf("%d",&n),i=1;i<=n;i++){
for(scanf("%d%s",&a[i],g[i]),j=1;j<=a[i];b[i]=max(b[i],len[i][j]=w),j++){
for(scanf("%s",s[i][j]),w=l=0;l<strlen(s[i][j]);l++)if(s[i][j][l]==',')w++;
}
if(i<n)b[i]++;pp=max(pp,a[i]);
}
for(i=1;i<=n;i++)for(printf("%s",g[i]),j=1;j<=b[i];j++)printf(",");puts("");
for(i=1;i<=pp;puts(""),i++)for(j=1;j<=n;j++)for(printf("%s",s[j][i]),l=0;l<b[j]-len[j][i];l++)printf(",");
}
【JSOI2009】火星藏宝图 首先可以发现，多休息比少休息好，在三角形中两边之和大于第三边，但是在锐角三角形中，两边的平方和一定小于第三边的平方，所以每个点只可能从最近的一些点转移过来，由于坐标<=m，最多有m个点转移过来，时间复杂度O(nm)
#include<cstdio>
#include<algorithm>
using namespace std;int n,m,i,j,q[1111];long long w,f[1111];
struct P{int x,y,z;}p[222222];bool cmp(P a,P b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
int d(int i,int j){return (p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y);}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
for(sort(p+1,p+n+1,cmp),f[1]=p[1].z,q[1]=1,i=2;i<=n;f[p[i].y]=w+p[i].z,q[p[i].y]=i++)
for(w=-1e18,j=1;j<=p[i].y;j++)if(q[j])w=max(w,f[j]-d(q[j],i));
printf("%lld",f[m]);
}
【SDOI2008】石子合并 一种很神的做法，抄了一下
#include<cstdio>
int a[50005],n,i,t,ans;
void c(int k){
int tmp=a[k]+a[k-1],i,j,d;ans+=tmp;
for(i=k;i<t-1;i++)a[i]=a[i+1];
for(t--,j=k-1;j>0&&a[j-1]<tmp;j--)a[j]=a[j-1];
for(a[j]=tmp;j>=2&&a[j]>=a[j-2];)d=t-j,c(j-1),j=t-d;
}
int main(){
for(scanf("%d",&n),i=0;i<n;i++)scanf("%d",&a[i]);
for(t=i=1;i<n;i++)for(a[t++]=a[i];t>2&&a[t-3]<=a[t-1];)c(t-2);
for(;t>1;c(t-1));printf("%d\n",ans);
}
【HAOI2010】计数 数位DP，对于每一位枚举前面比它小的方案数，算组合数
#include<cstdio>
#include<cstring>
int n,i,j,k,v[55];long long ans,w,c[55][55];char s[55];
long long cal(int x){for(w=1,k=0;k<=9;k++)w*=c[x][v[k]],x-=v[k];return w;}
int main(){
for(scanf("%s",s+1),n=strlen(s+1),c[0][0]=1,i=1;i<=n;i++)for(v[s[i]-'0']++,c[i][0]=j=1;j<=i;j++)c[i][j]=c[i-1][j]+c[i-1][j-1];
for(i=1;i<=n;v[s[i++]-'0']--)for(j=0;j<s[i]-'0';j++)if(v[j])v[j]--,ans+=cal(n-i),v[j]++;
printf("%lld",ans);
}
晚上回到家颓了很久才做了一道傻逼题。。
BZOJ4318 f[i]表示到第i个数的期望贡献,a[i]表示到第i个数长度的期望，b[i]表示到第i个数长度平方贡献，则f[i]=f[i-1]+(3*b[i-1]+3*a[i-1]+1)*x，a[i]和b[i]也可以推出来
#include<cstdio>
#define N 100100
int n,i;double x,a[N],b[N],f[N];
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%lf",&x),a[i]=(a[i-1]+1)*x,b[i]=(b[i-1]+2*a[i-1]+1)*x,f[i]=f[i-1]+(3*b[i-1]+3*a[i-1]+1)*x;
printf("%.1lf",f[n]);
}
感觉BZOJ上的傻逼题也被清理得差不多了。。
10.31
早上虽然起得有点晚，但还是做了下XJ模拟赛
先看T1，感觉很熟悉，但找不到原题，看看数据范围觉得是贪心吧。。
再看T2,70分送你的，然后想100分似乎单调维护一下就可以了
然后看T3，似乎只能拿拿暴力分，再写个环套树有60分
就先写T2，然后发现想错了，最后只好写了一个70分暴力
然后写T3，发现暴力写不对，就只好写暴力的暴力了，然后写了个环套树，估计50分
然后写T1，觉得是贪心，大概就是维护右端绳子取的范围[L,R]，能取尽量取就可以了
最后T2再写了个Cheat
最后测出来100+75+50，T2多Cheat了5分，还是不错哒。。
#include<cstdio>
#include<algorithm>
using namespace std;
int n,ans,i;long long p,q,x,y,l,r;
int main(){
for(scanf("%d%lld%lld",&n,&x,&y),r=x+y,ans=n-1,i=2;i<=n;i++){
scanf("%lld%lld",&x,&y);y=y+x;
p=max(0ll,y-r);q=min(y,y-l);
if(p>q)l=0,r=y,ans--;else l=p,r=q;
}
printf("%d",ans);
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 402
using namespace std;
int n,m,k,i,j,l,p,w,a[N][N],mn[N][N],mx[N][N];long long ans;
int main(){
for(scanf("%d%d%d",&n,&m,&p),i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&a[i][j]);
if(n*m>=40000){
for(i=1;i<=n;i++)for(j=1;j<=m;j++)ans+=i*j;
printf("%lld",ans);
}else{
for(i=1;i<=n;i++)for(j=1;j<=m;j++){
memset(mn,63,sizeof(mn));memset(mx,0,sizeof(mx));
for(k=i;k<=n;k++)for(l=j;l<=m;l++){
mn[k][l]=min(mn[k-1][l],min(mn[k][l-1],a[k][l])),
mx[k][l]=max(mx[k-1][l],max(mx[k][l-1],a[k][l]));
if(mx[k][l]-mn[k][l]<=p)ans++;else break;
}
}
printf("%lld",ans);
}
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 501000
using namespace std;bool ff;char ch;
int n,m,k,i,j,x,y,h,t,f,u,S,T,sz,tot,num,fir[N],ne[N<<1],la[N<<1],d[N],v[N],cir[N],fa[N],c[N],bl[N];
void read(int &x){
for(f=0,ch=getchar();ch<'0'||ch>'9';ch=getchar());
for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int y,int z){
if(x==y){if(!z)ff=1;return;}
for(int i=fir[x];i;i=ne[i])if(!v[la[i]])v[la[i]]=1,dfs(la[i],y,z^1),v[la[i]]=0;
}
void dfs(int x,int fa){for(int i=fir[x];i;i=ne[i])if(fa!=la[i])d[la[i]]=d[x]+1,dfs(la[i],x);}
void fcur(int x){
int i,y;
for(v[x]=++sz,i=fir[x];i;i=ne[i]){
y=la[i];
if(y==fa[x])continue;
if(v[y]){
if(v[y]<v[x])continue;
for(cir[++num]=x,c[x]=1;x!=y;y=fa[y])c[y]=1,cir[++num]=y;
}else fa[y]=x,fcur(y);
}
}
void dfs2(int x,int fa,int fm){
bl[x]=fm;int i,y;
for(i=fir[x];i;i=ne[i])if(!c[y=la[i]]&&y!=fa)d[y]=d[x]+1,dfs2(y,x,fm);
}
int main(){
for(read(n),read(m),read(k),i=1;i<=m;i++)read(x),read(y),ins(x,y),ins(y,x);
if(n==m+1)for(dfs(1,0),i=1;i<=k;i++)read(x),read(y),puts(((d[x]+d[y])&1)?"TAK":"NIE");
else if(n==m){
for(fcur(1),i=1;i<=num;i++)dfs2(cir[i],0,i);
for(i=1;i<=k;i++){
read(x);read(y);
if(bl[x]==bl[y])puts(((d[x]+d[y])&1)?"TAK":"NIE");
else if(num%2==1)puts("TAK");else puts(((d[x]+d[y]+bl[x]+bl[y])&1)?"TAK":"NIE");
}
}else for(i=1;i<=k;i++)read(x),read(y),ff=0,v[x]=1,dfs(x,y,1),v[x]=0,puts(ff?"TAK":"NIE");
}
T2其实很简单，枚举行以后列是单调的，两个单调队列维护一下就可以了，我想的单调是关于点的单调，需要n^3lgn^2的复杂度，觉得过不去就没写。。
#include<bits/stdc++.h>
#define N 404
using namespace std;
int n,m,k,i,j,h1,t1,h2,t2,l,r,a[N][N],mn[N],mx[N],q1[N],q2[N];long long ans;
int main(){
for(scanf("%d%d%d",&n,&m,&k),i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&a[i][j]);
for(l=1;l<=n;l++){
for(memset(mn,63,sizeof(mn)),memset(mx,0,sizeof(mx)),r=l;r<=n;r++){
for(h1=h2=j=i=1,t1=t2=0;i<=m;i++,ans+=i-j){
for(mn[i]=min(mn[i],a[r][i]);h1<=t1&&mn[i]<=mn[q1[t1]];t1--);
for(mx[i]=max(mx[i],a[r][i]);h2<=t2&&mx[i]>=mx[q2[t2]];t2--);
for(q1[++t1]=i;h1<=t1&&mn[q1[h1]]+k<mx[i];h1++)j=max(j,q1[h1]+1);
for(q2[++t2]=i;h2<=t2&&mn[i]+k<mx[q2[h2]];h2++)j=max(j,q2[h2]+1);
}
}
}
printf("%lld",ans);
}
下午做了一道水题
BZOJ3884 根据费马小定理推论可知a^b %p=a^(b%phi(p)+phi(p))%p，根据这个公式，2^∞2 %p=2^(2^∞2%phi(p)+phi(p))%p,不断递归p就可以了，当p=1时答案为0，时间复杂度O(n^0.5lgn)
#include<cstdio>
typedef long long LL;LL w;int T,n;
int pow(LL x,int y,int z){for(w=1;y;x=x*x%z,y>>=1)if(y&1)w=w*x%z;return (int)w;}
int phi(int n){
int i,re=n;
for(i=2;i*i<=n;i++)if(n%i==0)for(re=re/i*(i-1);n%i==0;n/=i);
if(n>1)re=re/n*(n-1);return re;
}
int F(int x){
if(x==1)return 0;int p=phi(x);
return pow(2,F(p)+p,x);
}
int main(){for(scanf("%d",&T);T--;printf("%d\n",F(n)))scanf("%d",&n);}
晚上打了BC，T1刷了20MIN才弄出，T2没看懂弄T3，想了一会觉得直接算次数就可以了，后来又觉得要根号，然后发现不用根号直接上费马小定理就可以了，然后发现还要筛素数分解质因数，真是一道数论好题啊，最后30MIN才搞懂T2意思，交了个看上去正确的找规律WA了，最后没调出来日狗。。
然后大号和小号分在一个ROOM，就用大号去×小号，T1总是显示不合法输入。。然后只好×T3。。然后一直没测，很晚才测，然后惊讶地发现HACK是+5-1，原来T1的HACK重测了，早知道就多×几次了。。这样没准就登顶啦。。
11.1
凌晨打了一场CF
T1好长啊，先去看T2了，画画图发现直接输出(n-2)^2就好啦。。5min交
T1被翻译出来了，就麻麻麻，调了一会才过样例，交的时候已经20min了
T3也被翻译出来啦，直接求一下lcm扭一扭脖子就好啦，40min交
T4也被翻译出来啦，觉得在哪做过，找到原题改了一下，45min交
T5也被翻译出来啦，好难啊不会做要滚粗啦
开始×人，先锁T1，只找到一个逗逼，写什么都不知道，第一发还HACK错了，因为他有两个地方写炸了，负负得正，真是日狗，第二发成功，+1-1
然后锁T2，转了一圈发现没有SB
然后锁T4，发现根本没几个人做，做的几个人代码还非常长。。
最后锁T3，发现一个个全是逗逼，就一个个×过来，+5-1
最后发现一个越南小哥被我×以后改对了，还把我反超了。。真是日狗，早知道最后再×了
最后总排名暂时RANK3，这TM竟然不是ROOM1，我也是醉了，是不是CF的一大记录呢？
T1写残了日，i和j打错了一个。。最后排名RANK2，要是T1不写残就RANK1了，真是日狗，又一次与第一失之交臂，下次估计没有机会咯
#include<bits/stdc++.h>
using namespace std;
int T,n,m,x,y,i,j,k,tot,as,bs,a[11][11];char s[99];bool ff;
int main(){
as=bs=10;
for(i=1;i<=8;i++)
for(scanf("%s",s+1),j=1;j<=8;j++){
if(s[j]=='W')a[i][j]=1;
if(s[j]=='B')a[i][j]=2;
}
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)if(a[j][i]==2){
ff=0;
for(k=i;k<=8;k++)if(a[k][i]==1)ff=1;
if(!ff)bs=min(bs,8-j);
}
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)if(a[j][i]==1){
ff=0;
for(k=i;k;k--)if(a[k][i]==2)ff=1;
if(!ff)as=min(as,j-1);
}
if(as<=bs)puts("A");else puts("B");
}
int T,m,x,y,i,j,tot,a[N];LL n;
int main(){
scanf("%lld",&n);
printf("%lld",(n-2)*(n-2));
}
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL t,a,b,w,fz,fm,xx;double v;
int main(){
scanf("%lld%lld%lld",&t,&a,&b);
w=gcd(a,b);fm=t;xx=min(a,b);
v=(double)a/w*b;
if(v>(double)t){
fz=min(xx-1,t);
}else{
a/=w;a*=b;
w=t/a;
t-=w*a;
fz=w*xx+min(xx-1,t);
}
w=gcd(fz,fm);fz/=w;fm/=w;
printf("%lld/%lld",fz,fm);
}
#include<cstdio>
#include<algorithm>
#define N 155555
#define inf 1e17
using namespace std;
int n,k,i,x,y,z,u,tot,fir[N],sz[N],fa[N],la[N<<1],ne[N<<1];bool v[N];
long long d1[N],d2[N],up[N],sm[N],va[N<<1],ans;
void ins(int x,int y,long long z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
if(v[x])d1[x]=0,sz[x]=1;else d1[x]=-inf;d2[x]=-inf;int i,y;
for(i=fir[x];i;i=ne[i])if(fa[x]!=(y=la[i])){
fa[y]=x;dfs(y);sm[x]+=sm[y]+(sz[y]?1ll:0ll)*va[i];sz[x]+=sz[y];
if(d1[y]+va[i]>d1[x])d2[x]=d1[x],d1[x]=d1[y]+va[i];else d2[x]=max(d2[x],d1[y]+va[i]);
}
}
void dfs2(int x,long long z){
int i,y,now=sz[x];long long mav;
if(x!=1)mav=sm[x]+sm[fa[x]]+(sz[fa[x]]?1ll:0ll)*z;else mav=sm[x];
for(i=fir[x];i;i=ne[i])if(fa[y=la[i]]==x){
if(d1[y]+va[i]==d1[x])up[y]=d2[x]+va[i];else up[y]=d1[x]+va[i];
sm[x]=mav-sm[y];if(sz[y])sm[x]-=va[i];up[y]=max(up[y],up[x]+va[i]);
sz[x]=now-sz[y]+sz[fa[x]];dfs2(y,va[i]);
}
up[x]=mav*2-max(up[x],d1[x]);
}
int main(){
for(scanf("%d%d",&n,&k),i=1;i<n;i++)scanf("%d%d",&x,&y),z=1ll,ins(x,y,z),ins(y,x,z);
for(i=1;i<=k;i++)scanf("%d",&x),v[x]=1;dfs(1);up[1]=-inf;dfs2(1,0);
for(ans=1e18,i=1;i<=n;i++)if(up[i]<ans)u=i,ans=up[i];printf("%d\n%lld",u,ans);
}
#include<bits/stdc++.h>
using namespace std;
int T,n,m,x,y,i,j,k,tot,as,bs,a[11][11];char s[99];bool ff;
int main(){
as=bs=10;
for(i=1;i<=8;i++)
for(scanf("%s",s+1),j=1;j<=8;j++){
if(s[j]=='W')a[i][j]=1;//a=min(a,min(i-1,8-i));
if(s[j]=='B')a[i][j]=2;//b=min(b,min(i-1,8-i));
}
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)if(a[j][i]==2){
ff=0;
for(k=j;k<=8;k++)if(a[k][i]==1)ff=1;
if(!ff)bs=min(bs,8-j);
}
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)if(a[j][i]==1){
ff=0;
for(k=j;k;k--)if(a[k][i]==2)ff=1;
if(!ff)as=min(as,j-1);
}
if(as<=bs)puts("A");else puts("B");
}
下午订正下XJ模拟题
观光旅行 （大致就是semi什么的弱化版。。）先建出一棵树，剩下的边如果对答案有贡献，只能是后向边，而且是偶数长度的，把每个点通过后向边能到达的最浅的点找出，处理出那些能走后向边的点，对于询问直接LCA，如果在两点路径上有点有后向边，那么一定合法，如果两点深度之和为偶数页合法
#include<bits/stdc++.h>
#define N 500500
using namespace std;
int n,m,k,x,y,t,i,j,tot,la[N<<1],ne[N<<1],fir[N],pre[N],d[N],fa[N][21];bool f,use[N<<1],ok[N][21];
char ch;void read(int &x){
for(f=0,ch=getchar();ch<'0'||ch>'9';ch=getchar());
for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
for(int i=1;i<21;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=fir[x];i;i=ne[i])if(!d[la[i]])d[la[i]]=d[x]+1,fa[la[i]][0]=x,use[i]=1,dfs(la[i]);
}
void dfs2(int x){
if(!pre[x])pre[x]=x;int i,y;
for(i=fir[x];i;i=ne[i])if(use[i]){
dfs2(y=la[i]);if(d[pre[y]]<d[pre[x]])pre[x]=pre[y];
}if(pre[x]!=x)ok[x][0]=1;
}
int main(){
for(read(n),read(m),read(k),i=1;i<=m;i++)read(x),read(y),ins(x,y),ins(y,x);
for(d[1]=1,dfs(1),x=1;x<=n;x++)for(i=fir[x];i;i=ne[i])if(!use[i]&&(d[x]+d[y=la[i]])%2==0)if(d[x]<d[y])pre[y]=x;else pre[x]=y;
for(dfs2(1),j=1;j<20;j++)for(i=1;i<=n;i++)ok[i][j]|=ok[i][j-1]|ok[fa[i][j-1]][j-1];
for(;k--;f=0){
read(x);read(y);if((d[x]+d[y])&1){puts("TAK");continue;}
if(d[x]<d[y])swap(x,y);
for(i=20;i>=0;i--)if(d[fa[x][i]]>=d[y])f|=ok[x][i],x=fa[x][i];
for(i=20;i>=0;i--)if(fa[x][i]!=fa[y][i])f|=ok[x][i]|ok[y][i],x=fa[x][i],y=fa[y][i];
if(x!=y)f|=ok[x][0]|ok[y][0];
puts(f?"TAK":"NIE");
}
}
晚上来学校打了场UOJ
T1一开始看好难啊。。摞了30+min想了一个很复杂的算法，然后发现题意弄错了，是判断是不是一棵树。。那直接并查集就可以了
T2看好难啊，完全没有头绪，想了很久也不会，然后黈力弄了个很神奇的做法，按黈力做法A了。。
然后弄T3，n^3的暴力DP有50分，就麻麻麻，但连样例都没过，调了20min换了各种各样方程，发现没清零。。
第二天来发现T1只有50分，原来是我把特判的位置放错了QAQ，而且特判没开longlong。。
不过发现竟然拿到了抱枕，因为我T2的AC代码是最短的。。RP实在太好了，才打了两场就拿到抱枕啦
#include<bits/stdc++.h>
using namespace std;int n,i,j,x,a[555],v[555];
bool cmp(int x,int y){return a[x]>a[y];}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)for(v[i]=i,scanf("%d",&x),j=30;j>=0;x=(x+1)/2,j--)if(x%2==0)a[i]+=(1<<j);
for(sort(v+1,v+n+1,cmp),i=1;i<=n;i++)printf("%d ",v[i]);
}
#include<bits/stdc++.h>
#define N 555
#define M 998244353
using namespace std;
int n,m,i,j,k;long long ans,f[N][N],g[N][N];
int main(){
for(scanf("%d%d",&n,&m),f[0][0]=1,i=1;i<=n;i++){
memcpy(g,f,sizeof(f));memset(f,0,sizeof(f));
for(j=0;j<=m;j++)for(k=0;k+j<=m;k++)if(i%2==0){
f[j][k+1]=(g[j][k]*(m-j-k)+f[j][k+1])%M;
if(j>0)f[j-1][k+1]=(g[j][k]*j+f[j-1][k+1])%M;
}else{
if(m-j-k>0)f[j+1][k]=(g[j][k]*(m-j-k)+f[j+1][k])%M;
if(k>0)f[j+1][k-1]=(g[j][k]*k+f[j+1][k-1])%M;
}
}
for(i=0;i<=m;i++)ans=(ans+f[i][m-i])%M;printf("%lld",ans);
}
#include<bits/stdc++.h>
#define N 1005000
using namespace std;
int T,n,m,k,x,y,i,j,tot,p,q,fa[N];bool v[N],ff;
int get(int x,int y){long long p=x*m-m+y;return p>1000000?1000001:p;}
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
void uni(int x,int y){p=gf(x);q=gf(y);if(p==q)ff=1;fa[p]=q;tot++;}
int main(){
for(scanf("%d",&T);T--;tot=0,memset(v,0,sizeof(v))){
scanf("%d%d%d",&n,&m,&k);if(1ll*n*m>1000000){puts("No");for(i=1;i<=k;i++)scanf("%d%d",&x,&y);continue;}
for(i=1;i<=k;i++)scanf("%d%d",&x,&y),v[get(x,y)]=1;
for(i=1;i<=n*m;i++)fa[i]=i;ff=0;
for(i=1;i<=n*m;i++)if(!v[i]){
if(i%m==0&&!v[i-m+1])uni(i-m+1,i);
if(i%m!=1&&!v[i-1])uni(i-1,i);
if(i>m&&!v[i-m])uni(i-m,i);
if(ff)break;
}
puts(ff||tot+1!=n*m-k?"No":"Yes");
}
}
11.2
早上原来是要做模拟题的，但发现XJ上又有模拟题，就去XJ做题了
T1就是KMP模板题吧。。T2数据弱，拍出错的线段树、暴力和DP都能过。。T3数据描述不清，可以用必经点定理，也可以暴力。。
#include<bits/stdc++.h>
#define N 1001000
int n,x,i,j,p[N];char s[N];
int main(){
for(scanf("%d%s",&n,s+1),i=2;i<=n;i++){
for(;j&&s[j+1]!=s[i];j=p[j]);
if(s[i]==s[j+1])j++;
p[i]=j;
}
for(i=1;i<=n;i++){
x=i-p[i];
if(i%x==0&&i!=x)printf("%d %d\n",i,i/x);
}
}
#include<bits/stdc++.h>
using namespace std;
int n,m,i,x,f[4][50001],sum[50001];
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&x),sum[i]=sum[i-1]+x;
for(scanf("%d",&m),i=m;i<=n;i++)f[1][i]=max(f[1][i-1],sum[i]-sum[i-m]);
for(i=2*m;i<=n;i++)f[2][i]=max(f[2][i-1],f[1][i-m]+sum[i]-sum[i-m]);
for(i=3*m;i<=n;i++)f[3][i]=max(f[3][i-1],f[2][i-m]+sum[i]-sum[i-m]);
printf("%d",f[3][n]);
}
#include<bits/stdc++.h>
#define N 2010
#define M 4004000
int n,m,i,j,tp,fir[N],q[N],x[M],y[M],fa[N];
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=m;i++)scanf("%d%d",&x[i],&y[i]);
for(i=2;i<n;i++){
for(j=1;j<=n;j++)fa[j]=j;
for(j=1;j<=m;j++)if(x[j]!=i&&y[j]!=i){
fa[gf(x[j])]=gf(y[j]);
if(gf(1)==gf(n))break;
}
if(gf(1)!=gf(n))q[++tp]=i;
}
for(printf("%d\n",tp),i=1;i<=tp;i++)printf("%d ",q[i]);
}
下午继续做模拟题，玩了很久提答玩满分了，T1写了个暴力，T2写了个DP暴力交上去，可是都爆零了。。
然后订正下CF，估计是被卡精度了没过，会做了也不想写了
晚上一直在订正以前的一些比赛，又颓了一会，就没做几道题。。联赛前再撑几天找些水题刷吧。。
11.3
早上赶紧刷几道题
【IOI2005】mea 由于一旦第一个数确定剩下的数也确定，只需确定第一个数的取值范围即可，解一个方程就可以以得到一个区间了
#include<bits/stdc++.h>
using namespace std;
int n,i;long long l,r,x,a[5001000];
int main(){
for(scanf("%d",&n),i=2;i<=n+1;i++)scanf("%lld",&x),a[i]=2*x-a[i-1];
for(l=-1e17,r=1e17,i=1;i<=n;i++)if(i&1)r=min(r,a[i+1]-a[i]);else l=max(l,a[i]-a[i+1]);
if(r<0)r=(r-1)/2;else r/=2;if(l>0)l=(l+1)/2;else l/=2;printf("%lld",r-l<0?0:r-l+1);
}
早上做了一场模拟赛
先看提答，觉得好难啊，拿暴力分然后滚粗了
然后来做T1，理解题意后大概就是单调扫一遍就没有了
然后看T2，好难啊，就又玩了会T3，多玩出9分
然后T2觉得先写个暴力靠谱，就写了个暴力
然后打了个表，看了一会找到了规律
然后按规律写出来，拍一遍没错就交了
#include<bits/stdc++.h>
#define N 2555
int n,i,j,lv,rv,ans,pos,sum[N],rm[N],lm[N];char s[N];
int main(){
for(;scanf("%s",s+1)!=EOF;printf("%d\n",ans)){
for(ans=n=strlen(s+1),i=1;i<=n;i++)sum[i]=sum[i-1]+(s[i]=='1'),lm[i]=lm[i-1]+i*(s[i]=='1');
for(rm[n+1]=0,i=n;i;i--)rm[i]=rm[i+1]+(n-i+1)*(s[i]=='1');
for(i=1;i<=n;i++)
for(pos=i,j=i+1;j<=n;j++){
rv=lm[j]-lm[pos]-(sum[j]-sum[pos])*pos;
lv=rm[i]-rm[pos]-(sum[pos-1]-sum[i-1])*(n-pos+1);
for(;lv<rv&&pos<j;){
pos++;rv=lm[j]-lm[pos]-(sum[j]-sum[pos])*pos;
lv=rm[i]-rm[pos]-(sum[pos-1]-sum[i-1])*(n-pos+1);
}
if(lv==rv)ans++;
}
}
}
#include<bits/stdc++.h>
#define N 1010
using namespace std;
long long n,k,ans,pw[62];int i;
int main(){
for(pw[1]=1,i=2;i<=61;i++)pw[i]=pw[i-1]*2;
for(;scanf("%lld%lld",&n,&k)!=EOF;ans=0){
for(n-=k,i=1;i<=61&&n;i++)if(pw[i]<=k&&pw[i]<=n)ans++,n-=pw[i];
ans+=n/k;if(n%k)ans++;
printf("%lld\n",ans);
}
}
中午颓了一会，然后做了一道题
【CTSC2002】award DP，用f[1/2/3][i][j][k]表示在第i行的第j-k列，在I的第几个部分，然后转移就可以了
#include<bits/stdc++.h>
#define N 210
using namespace std;
int n,m,i,j,k,l,x,ans,f[4][N][N][N],sum[N][N],g[N][N][N],h[N][N][N];
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&x),sum[i][j]=sum[i][j-1]+x;
for(memset(f,200,sizeof(f)),memset(g,200,sizeof(g)),memset(h,200,sizeof(h)),i=1;i<=n;i++){
for(j=1;j<=m;++j)for(k=j;k<=m;++k)if(sum[i][k]==sum[i][j-1])
f[1][i][j][k]=max(f[1][i-1][j][k],0)+k-j+1,f[2][i][j][k]=max(g[i-1][j][k],f[2][i-1][j][k])+k-j+1,
f[3][i][j][k]=max(h[i-1][j][k],f[3][i-1][j][k])+k-j+1,ans=max(ans,f[3][i][j][k]);
for(l=0;l<m;l++)for(j=1;j+l<=m;j++)h[i][j][k=j+l]=max(max(h[i][j][k-1],h[i][j+1][k]),f[2][i][j+1][k-1]);
for(l=m-1;l>=0;l--)for(j=1;j+l<=m;j++)g[i][j][k=j+l]=max(max(g[i][j-1][k],g[i][j][k+1]),f[1][i][j-1][k+1]);
}
printf("%d",ans);
}
然后去NOI题库逛了逛，都太水了，不想做，口胡一下
2.1 数字方格 直接暴枚就可以了
2.1 Bomb Game 直接模拟就可以了
2.5 The Castle 为什么要搜索呢，直接二进制并茶集就可以了
2.5 Letters 直接搜索就可以了，觉得可以把选的字母状压，这样就快很多
2.5 Maze 每次BFS找到当前拿的钥匙塞到队列中继续判就可以了
2.5 Dungeon Master 直接BFS就可以了
2.6 Maximum sum 初赛题，这是DP？
2.6 Post Office NOIP要考四边形不等式，吓尿了。。
#include <cstdio>
#include <cstring>
int n,m,x,i,j,k,a[303],g[32][303],w[303][303],s[32][303];
int main() {
scanf("%d%d",&n,&m);for (i=1;i<=n;i++)scanf("%d",&a[i]);
for (i=1;i<n;i++)for (j=i+1;j<=n;j++)w[i][j]=w[i][j-1]+a[j]-a[(i+j)>>1];
for (i=1;i<=n;i++) g[1][i]=w[1][i];
for (i=2;i<=m;i++){
s[i][n+1]=n;
for (j=n;j;j--)
for (k=s[i-1][j];k<=s[i][j+1];k++)
if (g[i-1][k]+w[k+1][j]<g[i][j]||g[i][j]==0)
g[i][j]=g[i-1][s[i][j]=k]+w[k+1][j];
}
printf("%d",g[m][n]);
}
2.7 神奇的口袋 直接DP吧。。这和效率有什么关系。。
3.5 Summents 这是HASH？我觉得就是和模拟题差不多，单调扫一遍就好了
3.6 二叉树 和数据结构有什么关系吗。。直接模拟就好了吧
#include<cstdio>
int x,y;
int main(){
for(scanf("%d%d",&x,&y);x!=y;)if(x>y)x/=2;else y/=2;
printf("%d",x);
}
4.2 Euclid's Game 感觉是博弈好题，和数论有什么关系。。x=y先手胜，x+y,y只能变成x,y；然后x+2y,y时有多种选择，可以选择好的一种，必胜；所以模拟这个过程，直到出现必胜即可（和辗转相减差不多）
4.3 Gopher II 直接二分图最大匹配
4.3 宗教信仰 裸并茶几
4.5 Divding 傻逼背包，如果加强拆分即可
4.5 完美覆盖 可以状态压缩，然后f[i]=f[i-1]*4-f[i-2]直接推就可以了，感觉可以矩阵乘法优化，期待将n=30改成n=1e18
4.5 Jury Compromise 傻逼DP即可,dp[i][j]表示第i个人差为j的最大和
4.5 Mondriaan's Dream 状压DP就可以了，感觉记忆化方便等
4.6 An Easy Problem 找到第一个01变10剩下的尽量移到最右边就可以了
4.7 The Buses 先把所有可能的时间预处理出来，然后按时间间隔从大到小排序，如果合法就按这个时间间隔搜索，有一个剪枝们如果now+n/时间间隔>=ans那么后面不用搜了
#include<bits/stdc++.h>
using namespace std;
int n,i,j,x,tp,ans=17,a[61];struct P{int x,y,z;}p[1111];
bool cmp(P a,P b){return a.z>b.z;}
bool ok(int x,int y){for(int i=x;i<60;i+=y)if(!a[i])return 0;return 1;}
void dfs(int x,int st){
if(!n){if(st<ans)ans=st;return;}int i,j;
for(i=x;i<=tp;i++)if(st+n/p[i].z<ans)if(ok(p[i].x,p[i].y)){
for(j=p[i].x;j<60;j+=p[i].y)a[j]--,n--;
for(dfs(i,st+1),j=p[i].x;j<60;j+=p[i].y)a[j]++,n++;
}
}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&x),a[x]++;
for(i=0;i<30;i++)if(a[i])for(j=i+1;j<60-i;j++)if(ok(i,j))p[++tp]=P{i,j,1+(59-i)/j};
sort(p+1,p+tp+1,cmp);dfs(1,0);printf("%d",ans);
}
4.7 The Rotation Game 空间不够，迭代深搜
然后做了下早上的XJOI
T1 同余方程 a=0可以，否则利用费马小定理，如果要有解那么a^((p-1)/2)%p=1
#include<bits/stdc++.h>
int T,a,p,b,w;
int main(){
for(scanf("%d",&T);T--;){
scanf("%d%d",&a,&p);if(a==0){puts("YES");continue;}
for(b=(p-1)>>1,a=(a+p)%p,w=1;b;a=(long long)a*a%p,b>>=1)if(b&1)w=(long long)w*a%p;
puts(w==1?"YES":"NO");
}
}
T2 重复串 只能想到n^3的DP，但是竟然能过。。真是逗我
#include<bits/stdc++.h>
#define N 1111
using namespace std;int n,i,j,k,ans,f[N][N];char s[N];
int main(){
for(scanf("%d%s",&n,s+1),i=1;i<=n;ans=max(ans,f[i][n]),i++)
for(memset(f,0,sizeof(f)),j=1;j<=i;j++)for(k=i+1;k<=n;k++)
if(s[j]==s[k])f[j][k]=f[j-1][k-1]+1;else f[j][k]=max(f[j][k-1],f[j-1][k]);
printf("%d",n-2*ans);
}
T3 摘苹果 树上贪心，能不摘就不摘，不得不摘就得摘
#include<bits/stdc++.h>
#define N 10001000
using namespace std;
int t,u,sz,ans,l[N],r[N],fir[N],ne[N];
void dfs(int fa){
int i,t,u;scanf("%d",&t),ne[u=++sz]=fir[fa],fir[fa]=u;
if(!t){scanf("%d%d",&l[u],&r[u]);return;}
for(i=1;i<=t;i++)dfs(u);
for(i=fir[u];i;i=ne[i])l[u]=max(l[u],l[i]);
for(i=fir[u];i;i=ne[i])if(r[i]<l[u])ans++;else r[u]=min(r[u],r[i]);
if(!fa&&r[u]>=l[u]&&r[u]<1e9)ans++;
}
int main(){memset(r,127,sizeof(r));dfs(0);printf("%d",ans);}
11.4
早上做了一套模拟赛
第一题是交互题，好神啊，先没敢搞
然后看T2，好神啊，推出公式感觉只能暴力，先放一边
然后看T3，更神了，部分分都不好拿，算了先不搞
最后看T4，超神啊，根本毫无头绪
然后回来做T1，觉得直接暴力挺靠谱的，就写了一个
然后T2写了个暴力，觉得剩下10分有点难，先放一边
然后来做T4，先想所有ai都是1那不就是一道构造题了嘛。。这不就是构造一个循环赛方案吗。。
摞了一会把方案摞出来，就是1的对手转一圈替换就好了吧
然后写了个T3的暴力，感觉好难写啊QAQ
最后回去写了个T2的分治，但摞了会干，对于非质数模数没有办法，经黄主力提醒发现用什么费马啊，直接上！
#include<bits/stdc++.h>
#include"maze_lib.h"
using namespace std;
int w,step;bool v[99][99];
void dfs(int x,int y){
if(step>=1800)return;
int w;
if(!v[x-1][y]){
v[x-1][y]=1;
step++;
w=move(0);
if(w){
dfs(x-1,y);
if(step>=1800)return;
step++;
move(1);
}
}
if(!v[x+1][y]){
v[x+1][y]=1;
step++;
w=move(1);
if(w){
dfs(x+1,y);
if(step>=1800)return;
step++;
move(0);
}
}
if(!v[x][y-1]){
v[x][y-1]=1;
step++;
w=move(2);
if(w){
dfs(x,y-1);
if(step>=1800)return;
step++;
move(3);
}
}
if(!v[x][y+1]){
v[x][y+1]=1;
step++;
w=move(3);
if(w){
dfs(x,y+1);
if(step>=1800)return;
step++;
move(2);
}
}
}
void work(){
v[40][40]=1;
dfs(40,40);
}
#include<bits/stdc++.h>
typedef long long LL;LL sum,jj,n,i,p,w,ans,pw[1111];
LL pow(LL a,LL b,LL p){for(sum=1,a%=p;b;a=a*a%p,b>>=1)if(b&1)sum=sum*a%p;return sum;}
LL go(LL x){
if(x==1)return 1;
LL y=go(x/2),z;
z=(y+y*pow(10ll,x/2,p))%p;
if(x&1)z=(z+pow(10ll,x-1,p))%p;
return z;
}
int main(){
freopen("zero.in","r",stdin);freopen("zero.out","w",stdout);
for(;scanf("%lld%lld",&n,&p)!=EOF;){
if(p==2){
if(n==1)puts("1");else puts(n&1?"0":"1");
}else if(n<=1000){
for(pw[0]=1,ans=0,i=1;i<n;i++){
pw[i]=pw[i-1]*10%p;
ans=(ans-pw[i]+p)%p;
}
ans=(ans+n-1+(pw[n-1])*n%p)%p;
printf("%lld\n",ans);
}else{
w=p-1;
printf("%lld\n",(pow(10ll,n-1,p)*(n%p)%p-go(n)+n%p+p)%p);
}
}
}
#include<cstdio>
long long ans,x,y,p,q,po[6],a[111];int n,i,j,M;bool ff;
const long long b[7][7]={
{0,0,0,0,0,0,0},
{0,1,2,3,5,8,1},
{0,1,4,9,25,64,1},
{0,1,8,27,125,512,1},
{0,1,16,81,625,4096,1},
{0,1,32,243,3125,32768,1},
{0,1,64,729,15625,262144,1}
};
void find(int x){
int i,j;long long w;
if(ff)return;
if(x==n+1){
ff=1;
for(i=1;i<=n;i++){
w=0;
for(j=1;j<=n;j++)w=(w+b[i][j]*po[j]%M)%M;
if(w!=a[i]){
ff=0;
break;
}
}
if(ff)for(i=1;i<=n;i++)ans=(ans+b[n+1][i]*po[i]%M)%M;
return;
}
for(i=0;i<=5;i++)po[x]=i,find(x+1);
}
int main(){
freopen("func.in","r",stdin);freopen("func.out","w",stdout);
for(;scanf("%d%d",&n,&M)!=EOF;ff=0,ans=0){
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
if(n==1||M==2)printf("%lld\n",a[1]);else
if(n==2){
for(i=0;i<=2;i++)
for(j=0;j<=4;j++){
x=a[1]+(long long)i*M;y=a[2]+(long long)j*M;
if(x<=y&&((y-x)%2==0)){
if(2*x-y<M&&(y-x)<2*M)p=2*x-y,q=(y-x)/2;
}
}
printf("%lld\n",(p+q*8)%M);
}else if(n<=5){
find(1);
printf("%lld\n",ans);
}
}
}
#include<cstdio>
#define N 1111
int n,k,x,i,j,t,a[N];
int main(){
freopen("hxx.in","r",stdin);freopen("hxx.out","w",stdout);
for(;scanf("%d%d",&n,&k)!=EOF;){
for(i=1;i<=k;i++)scanf("%d",&x);
for(i=1;i<=n;i++)a[i*2-1]=i,a[i*2]=2*n-i+1;
for(j=1;j<=2*n-1;j++){
for(i=1;i<=n;i++)printf("%d %d\n",a[i*2-1],a[i*2]);
for(t=a[2],i=1;i<n;i++)a[2*i]=a[2*i+2];
for(a[n*2]=a[n*2-1],i=n;i>2;i--)a[i*2-1]=a[i*2-3];
a[3]=t;
}
}
}
NOI题库又加题啦，赶紧做~
2.3 2011 和今天早上那道差不多，分治下去就行了
2.6 最长公共上升子序列 dp[i][j]=dp[i-1][j](a[i]≠b[j]) max(dp[i-1][k])(a[i]=b[j]&&b[i]>b[k])，这样是n^3的，前缀和优化一下是n^2的
2.6 登山 直接两遍DP就行了。。不过这题其实我觉得有点问题，要是上去下来都一样的高度是不是会挂了呢？抢到一血，期待加强
2.6 Exchange Rates 直接两种推就可以了
#include<bits/stdc++.h>
#define N 1111
using namespace std;int n,i,j,ans,a[N],f[N],g[N];
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)for(scanf("%d",&a[i]),f[i]=1,j=1;j<i;j++)if(a[i]>a[j])f[i]=max(f[i],f[j]+1);
for(i=n;i;ans=max(ans,f[i]+g[i]-1),i--)for(g[i]=1,j=n;j>i;j--)if(a[i]>a[j])g[i]=max(g[i],g[j]+1);
printf("%d",ans);
}
2.6 最大上升子序列和 傻逼DP，优化可以nlgn
2.6 计算字符串距离 f[i][j]表示a的前i个b的前j个的最小距离，f[i][j]=f[i-1][j-1](a[i]=b[j])min(f[i-1][j-1],f[i-1][j],f[i][j-1])+1(else)
#include<bits/stdc++.h>
#define N 1111
using namespace std;
int T,n,m,i,j,f[N][N];char a[N],b[N];
int main(){
for(scanf("%d",&T);T--;printf("%d\n",f[n][m])){
for(scanf("%s%s",a+1,b+1),n=strlen(a+1),i=0;i<=n;i++)f[i][0]=i;
for(m=strlen(b+1),i=0;i<=m;i++)f[0][i]=i;
for(i=1;i<=n;i++)for(j=1;j<=m;j++)
if(a[i]==b[j])f[i][j]=f[i-1][j-1];else f[i][j]=min(min(f[i-1][j-1],f[i-1][j]),f[i][j-1])+1;
}
}
2.6 数字组合 傻逼DP
2.6 判断整除 傻逼DP就可以了
#include<bits/stdc++.h>
int n,x,k,i,j,f[111],g[111];
int main(){
for(f[0]=1,scanf("%d%d",&n,&k),i=1;i<=n;i++){
memcpy(g,f,sizeof(f));
scanf("%d",&x);x%=k;
for(j=0;j<k;j++)f[j]=g[(j-x+k)%k]|g[(j+x)%k];
}
puts(f[0]?"YES":"NO");
}
2.7 Going to the Movies 难道不是暴力么
2.7 小兔子捡金币 不那么暴力的模拟就可以了
3.5 正方形 枚举对角即可
3.9 热血格斗场 set裸题
3.9 冷血格斗场 多关键字set
3.9 词典 Tire裸题
3.9 身份确认 觉得暴力枚两位就行了吧。。但是WA了。。现在0人A
#include<bits/stdc++.h>
using namespace std;
map<int,int>mp;
int n,m,i,x,j,k,top,tp,cou,b[999],cnt[100100],a[100100];long long ans;
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]);
for(;m--;){
scanf("%d",&x);
if(!mp[x])mp[x]=++top;
cnt[mp[x]]++;
}
for(i=1;i<=n;i++){
for(tp=j=0;j<30;j++)for(k=j+1;k<30;k++)b[++tp]=a[i]^(1<<j)^(1<<k);
sort(b+1,b+tp+1);cou=unique(b+1,b+tp+1)-(b+1);
for(j=1;j<=cou;j++)ans+=cnt[mp[b[j]]];
}
printf("%lld",ans);
}
4.2 Coins 分类讨论，偶数不可能奇数n-1
4.2 A funny game 傻逼题
4.3 丛林中的路 裸MST
4.5 Telephone Wire 不错的题！d[i][j]表示取到第i个高度为j的花费，d[i][j]=min(d[i][j],d[i-1][k]+abs(j-k)*m+(a[i]-j)*(a[i]-j))，而暴力转移是n^3的会T，很明显可以单调转移，就能在n^2时间内出解了
#include<bits/stdc++.h>
int n,T,i,j,pre,s,t,use[210],k,f[210][210];
int main(){
for(scanf("%d",&T);T--;puts(""),memset(use,0,sizeof(use))){
for(scanf("%d%lld",&n,&k),f[0][0]=1,i=1;i<=n;i++)
for(j=i;j>=1;j--){
f[i][j]=f[i-1][i-j]+f[i][j+1];
if(f[i][j]>k)f[i][j]=k+1;
}
for(i=1;i<=n&&k>f[n][i]+f[n][n-i+1];i++)k-=f[n][i]+f[n][n-i+1];
printf("%d",i);
if(f[n][n-i+1]<k)k-=f[n][n-i+1],pre=1;use[i]=1;
for(j=n-1;j>=1;j--,pre^=1){
if(pre)for(t=i;k>f[j][j-t+1];t++)k-=f[j][j-t+1];else for(t=1;k>f[j][t];t++)k-=f[j][t];
i=t;for(s=1;t;s++)t-=!use[s];s--;
printf(" %d",s);use[s]=1;
}
}
}
4.5 A decorative fence 做过原题，但原来我的做法是n^2的，这题n^4都可以，而且原来鏼情得是要高精度。。
4.6 最小新整数 每次删最左边的比右边大的数即可
4.6 胡 麻麻麻
4.6 拼点游戏 ZJOI泡泡堂原题吧
4.6 书架 傻逼贪心
4.6 最短前缀 HASH好题，怎么变成贪心了
4.6 金银岛 傻逼贪心
4.6 最大子矩阵 和贪心毛关系
4.6 Heritage 这是高精度打表吧
4.7 恼人的青蛙 二分长度后判断
总算差不多做完了，明天抽点时间把最近做的题看一下
11.5
早上做了套模拟赛，一堆树的计数题，T2没推出高效DP，用了qlj给的公式写了个矩乘，还因为在里面放负数爆零了。。T3要扩展lucas+CRT，蒟蒻的我压根不会
下午做了下学军模拟题，T2一眼秒，T1和T3都没什么好方法，没什么时间直接交了，可是T2因为一个奇怪的地方爆零了。。
然后来订正一下，发现T1当k增长到足够大时会成倍数增长，所以可以直接算出。。T2 i从1开始循环就爆零，从n-1开始循环就A了。。T3思路很巧妙，区间修改可以先差分，然后前缀和第一次得到单点，第二次得到区间，这样区间询问也就可以差分了。。不得不说今天XJ的题质量还是挺不错哒
#include<bits/stdc++.h>
using namespace std;long long T,x,y,i,ff;
int main(){
for(scanf("%d",&T);T--;printf("%lld\n",x),ff=0)
for(scanf("%lld%lld",&x,&y),i=1;i<=y;i++){
x=(x+i-1)/i*i;
if(x/i<=i)x=x+(y-i)*(x/i),ff=1;
if(ff)break;
}
}
#include<bits/stdc++.h>
#define N 1111
using namespace std;
int n,m,i,j,w,fa[N];long long ans=1e17;struct P{int x,y,a,b;}p[N];
bool cmp(P a,P b){return a.a<b.a;}bool cmp2(P a,P b){return a.b<b.b;}
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)fa[i]=i;
for(i=1;i<=m;i++)scanf("%d%d%d%d",&p[i].x,&p[i].y,&p[i].a,&p[i].b),fa[gf(p[i].x)]=gf(p[i].y);
if(gf(1)!=gf(n))return puts("-1"),0;
for(sort(p+1,p+m+1,cmp),i=n-1;i<=m;i++){
for(w=p[i].a,sort(p+1,p+i+1,cmp2),j=1;j<=n;j++)fa[j]=j;
for(j=1;j<=i;j++){
fa[gf(p[j].x)]=gf(p[j].y);
if(gf(1)==gf(n)){ans=min(ans,(long long)w+p[j].b);break;}
}
}
printf("%lld",ans);
}
#include<bits/stdc++.h>
int n,m,Q,x,y,z,l,i,j,k,a[111][111][111];long long ans;
int main(){
for(scanf("%d%d%d",&n,&m,&Q),i=1;i<=m;i++)for(scanf("%d%d%d%d",&x,&y,&z,&l),j=0;j<l;j++)a[x+j][y+j][z]++,a[x+l][y+j][z]--,a[x+j][y+j][z+j+1]--,a[x+l][y+j][z+j+1]++;
for(l=0;l<2;l++)for(j=1;j<=n;++j)for(i=1;i<=n;++i)for(k=1;k<=n;++k)a[i][j][k]+=a[i-1][j][k]+a[i][j][k-1]-a[i-1][j][k-1];
for(;Q--;printf("%lld\n",ans))for(scanf("%d%d%d%d",&x,&y,&z,&l),ans=j=0;j<l;j++)ans+=a[x+j-1][y+j][z-1]+a[x+l-1][y+j][z+j]-a[x+j-1][y+j][z+j]-a[x+l-1][y+j][z-1];
}
晚上不刷题了，复习一下前面的算法和做过的题目吧
11.6
早上把XJ的另一套做一下
T1没看题直接WA。。原来答案要求的是哪条线而不是值，而这在样例中是一样的。。
T2直接写了个暴力没管，T3大原题直接拉、、最后只做了10min就不想做了。。看了T2程序后恍然大悟，[L,R]区间都是相同的，可以分治解决啊
然后就一直颓
要出发啦，RP++
2015年10月17日 20:20
强烈吐槽你往oj上放的题的翻译。。根本看不懂在说些什么