2015 Multi-University Training Contest
2015多校赛，历年来最屌的镇海代表队出征了，除了主力队，连人都凑不齐
由于蒟蒻水平太低，英语太烂，只好去蒟蒻队，每次都被主力队碾压，现在连高一都打不过啦
由于爆OJ的癖好，每次都在A题相同的队中排名倒数QAQ
总做题数：36
2015 Multi-University Training Contest 1
开场看T1，看了将近半小时不会，但已经有一堆人A了。。
然后看了会T7，虽然看不太懂英文，但感觉是一道最短路+网络流裸题。。
这时已经过去将近一个小时了，黈力告诉我T9就是虚树裸题，看了一下，发现果然是这样
正当我准备拿个板子去做T9时，YY大爷说T2是RMQ，不过有T组数据要T，我说你**吗，RMQ询问O(1)你不造吗，但他还是弃疗了
于是拉了个RMQ板秒了T2，但由于姿势不太对，CE了两发
然后把T9写完了，WA了两发，只好把数组一个一个清空，总算A了
然后LX翻译了T7，果然是最短路+网络流裸题，马上秒了
然后1001竺主力做了，但他RE了，我看来十多分钟，虽然没看懂他程序什么意思，但还是发现了错误。。
然后发现1006就是黈力那天的JOI原题，把他的程序借鉴抄了一下
然后一直在弄1012，但没想出来，后来发现T12是LZN树裸题。。
这场主力队RANK12，我们蒟蒻队RANK23。。。发现我除了拉板似乎什么都不会。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 1e9
#define N 111111
using namespace std;
typedef long long LL;
LL T,n,i,j,k,ans,head,tail,a[N],l2[N],er[20],f[N][20],g[N][20];
LL getmax(LL x,LL y){
LL k=l2[y-x+1];
return max(g[x][k],g[y-er[k]+1][k]);
}
LL getmin(LL x,LL y){
LL k=l2[y-x+1];
return min(f[x][k],f[y-er[k]+1][k]);
}
int main(){
scanf("%I64d",&T);
while(T--){
memset(f,0,sizeof(f));memset(g,0,sizeof(g));
scanf("%I64d%I64d",&n,&k);ans=0;
for(i=1;i<=n;i++)scanf("%I64d",&a[i]);
for(i=1;i<=n;i++)f[i][0]=g[i][0]=a[i];
er[0]=1;for(i=1;i<20;i++)er[i]=er[i-1]*2;
l2[0]=-1;
for(i=1;i<=n;i++)l2[i]=(i&(i-1))?l2[i-1]:l2[i-1]+1;
for(j=1;j<20;j++)
for(i=1;i+er[j]-1<=n;i++){
f[i][j]=min(f[i][j-1],f[i+er[j-1]][j-1]);
g[i][j]=max(g[i][j-1],g[i+er[j-1]][j-1]);
}
head=1;ans=1;
for(i=2;i<=n;i++){
while(head<=i&&getmax(head,i)-getmin(head,i)>=k)head++;
ans+=i-head+1;
}
printf("%I64d\n",ans);
}
}
#include<cstdio>
#include<cstring>
#define N 2222
#define M 222222
#define inf 1e16
using namespace std;
long long n,m,k,i,j,tot,tot2,max,flow,tmp,s,t,u,head,tail,p,last[M],value[M],next[M],first[N],first2[N],cur[N],dist[N],dis[N],pre[N],lj[N],numb[N],x[M],y[M],z[M],last2[M],cost[M],next2[M],q[M<<4];
bool v[N];
void insert2(long long x,long long y,long long z){
last2[++tot2]=y;cost[tot2]=z;next2[tot2]=first2[x];first2[x]=tot2;
last2[++tot2]=x;cost[tot2]=z;next2[tot2]=first2[y];first2[y]=tot2;
}
void insert(long long x,long long y,long long z){
last[tot]=y;value[tot]=z;next[tot]=first[x];first[x]=tot++;
last[tot]=x;value[tot]=0;next[tot]=first[y];first[y]=tot++;
}
long long ISAP(){
memset(pre,-1,sizeof(pre));memset(numb,0,sizeof(numb));memset(dist,0,sizeof(dist));
for(i=0;i<=n;i++)cur[i]=first[i];
u=s;numb[0]=n;max=0;
while(dist[s]<n){
if(u==t){
flow=inf;
for(i=s;i!=t;i=last[cur[i]])if(value[cur[i]]<flow)flow=value[cur[u=i]];
for(i=s;i!=t;i=last[cur[i]]){
value[cur[i]]-=flow;
value[cur[i]^1]+=flow;
}
max+=flow;
}
for(i=cur[u];i!=-1;i=next[i])if(value[i]&&dist[last[i]]+1==dist[u])break;
if(i!=-1){
cur[u]=i;
pre[last[i]]=u;
u=last[i];
}else{
if(0==--numb[dist[u]])break;
for(tmp=n,i=cur[u]=first[u];i!=-1;i=next[i])
if(value[i]&&dist[last[i]]<tmp)tmp=dist[last[i]];
++numb[dist[u]=tmp+1];
if(u!=s)u=pre[u];
}
}
return max;
}
int main(){
while(scanf("%lld%lld",&n,&m)!=EOF){
tot=2;tot2=0;
memset(first2,0,sizeof(first2));
memset(last,0,sizeof(last));
memset(value,0,sizeof(value));
memset(next,0,sizeof(next));
memset(last2,0,sizeof(last2));
memset(cost,0,sizeof(cost));
memset(next2,0,sizeof(next2));
memset(first,-1,sizeof(first));
memset(lj,0,sizeof(lj));
for(i=1;i<=m;i++){
scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
insert2(x[i],y[i],z[i]);
}
for(i=1;i<=n;i++)dis[i]=inf;
for(i=1;i<=n;i++)lj[i]=inf;
head=0;tail=1;s=1;t=n;dis[s]=0;q[1]=s;v[s]=1;lj[s]=0;
while(head<tail)
for(i=first2[p=q[++head]],v[p]=0;i;i=next2[i])
if(dis[p]+cost[i]<dis[j=last2[i]]||(dis[p]+cost[i]==dis[j]&&lj[p]+1<lj[j])){
dis[j]=dis[p]+cost[i];
lj[j]=lj[p]+1;
if(!v[j])v[q[++tail]=j]=1;
}
for(i=1;i<=m;i++){
if(dis[x[i]]+z[i]==dis[y[i]])insert(x[i],y[i],1);
if(dis[y[i]]+z[i]==dis[x[i]])insert(y[i],x[i],1);
}
s=1;t=n;u=s;n=t;
printf("%lld %lld\n",ISAP(),m-lj[n]);
}
}
#include<cstdio>
#include<iostream>
#include<set>
#include<cstring>
#define N 222222
#define inf 1e16
using namespace std;
set<long long> st;
long long T,p,n,m,k,i,x,y,z,u,l,r,f,tot,sz,now,head,cas,id[N],pos[N],high[N],fir[N],val[N<<1],la[N<<1],ne[N<<1],fa[N][18];
long long ans,tmp,deep[N];
bool mark[N];
void ins(long long x,long long y,long long z){la[++tot]=y;val[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void dfs(long long x,long long z){
id[x]=++sz;pos[sz]=x;
for(long long i=1;i<=17;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
for(long long i=fir[x];i;i=ne[i]){
long long y=la[i];
if(y!=z){
deep[y]=deep[x]+val[i];
high[y]=high[x]+1;
fa[y][0]=x;
dfs(y,x);
}
}
}
long long lca(long long x,long long y){
if(high[x]<high[y])swap(x,y);
long long t=high[x]-high[y];
for(long long i=0;i<=17;i++)if(t&(1<<i))x=fa[x][i];
for(long long i=17;i>=0;i--)if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}
if(x==y)return x;else return fa[x][0];
}
long long dis(long long x,long long y){return deep[x]+deep[y]-2*deep[lca(x,y)];}
void change(long long i,long long f){
long long l=*--st.lower_bound(id[i]),r=*st.upper_bound(id[i]);
if(r!=inf)ans+=f*dis(i,pos[r]);
if(l!=-inf)ans+=f*dis(i,pos[l]);
if(l!=-inf&&r!=inf)ans-=f*dis(pos[l],pos[r]);
if(st.size()!=2)tmp=dis(pos[*st.upper_bound(-inf)],pos[*--st.lower_bound(inf)]);else tmp=0;
now=1+((ans+tmp)>>1);
}
int main(){
scanf("%I64d",&T);
while(T--){
printf("Case #%lld:\n",++cas);
memset(mark,0,sizeof(mark));
memset(pos,0,sizeof(pos));
memset(fir,0,sizeof(fir));
memset(fa,0,sizeof(fa));
memset(deep,0,sizeof(deep));
memset(ne,0,sizeof(ne));
memset(val,0,sizeof(val));
memset(la,0,sizeof(la));
memset(id,0,sizeof(id));
st.clear();ans=0;tmp=0;
sz=0;tot=0;
scanf("%I64d%I64d",&n,&m);
for(i=1;i<n;i++)scanf("%I64d%I64d%I64d",&x,&y,&z),ins(x,y,z),ins(y,x,z);
dfs(1,0);st.insert(inf);st.insert(-inf);
while(m--){
scanf("%I64d%I64d",&p,&x);
f=0;
if(p==1){
if(!mark[x])st.insert(id[x]),f=1;
mark[x]=1;
}else{
if(mark[x])st.erase(id[x]),f=-1;
mark[x]=0;
}
if(f){
long long l=*--st.lower_bound(id[x]),r=*st.upper_bound(id[x]);
if(r!=inf)ans+=f*dis(x,pos[r]);
if(l!=-inf)ans+=f*dis(x,pos[l]);
if(l!=-inf&&r!=inf)ans-=f*dis(pos[l],pos[r]);
if(st.size()!=2)tmp=dis(pos[*st.upper_bound(-inf)],pos[*--st.lower_bound(inf)]);else tmp=0;}
printf("%I64d\n",(ans+tmp)/2);
}
}
}
2015 Multi-University Training Contest 2
看到主力队开场拿了1006的一血，问一下果然是暴力，于是把1006秒了
然后觉得1002还稍微简单点，就去弄，发现只要枚举删除点的四边判断答案就可以了，但还是爆了2发OJ
然后看了下1009，觉得就是道码农题，太烦了，于是看1004
发现可以先把大于K的果子去掉，然后剩下的贪心取就可以了,不过一开始没有考虑环状的情况，想了一会发现环状取的一定是一整段的区间，于是可以考虑判断每个果子作为两边的分界线
然后LX说他做T9，说>47的数已经弄好了，于是帮他弄<47的数，弄了好久总算弄完了，然后发现自己真是个SB，后面的数直接乘0就行了，+1-1+1-1什么劲啊、、第一发WA了，写了个CHECK，发现了一个小BUG，改一下就A了，ORZORZ
这场主力队RANK10，我们蒟蒻队RANK18
#include<cstdio>
#include<algorithm>
#include<cstring>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
int T,i,n,m,ans,h1[10],h2[10],u[10];
struct EG{int x,y;}eg[110];
bool cmp(EG a,EG b){return(a.x<b.x)||(a.x==b.x&&a.y<b.y);}
void dfs(int x){
if(x>m){ans++;return;}
if(h1[eg[x].x]&&h1[eg[x].y]){
h1[eg[x].x]--;h1[eg[x].y]--;
dfs(x+1);h1[eg[x].x]++;h1[eg[x].y]++;
}
if(h2[eg[x].x]&&h2[eg[x].y]){
h2[eg[x].x]--;h2[eg[x].y]--;
dfs(x+1);h2[eg[x].x]++;h2[eg[x].y]++;
}
}
int main(){
scanf("%d",&T);
while(T--){
memset(gs,0,sizeof(gs));ans=0;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d%d",&eg[i].x,&eg[i].y);
u[eg[i].x]++;u[eg[i].y]++;
if(eg[i].x>eg[i].y)swap(eg[i].x,eg[i].y);
}
for(i=1;i<=n;i++)if(u[i]&1)break;else h2[i]=h1[i]=u[i]>>1;
if(i<=n){puts("0");continue;}
sort(eg+1,eg+m+1,cmp);
dfs(1);printf("%d\n",ans);
}
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 1e9
#define N 222222
using namespace std;
typedef long long LL;
int T,n,m,x,y,now;
int main(){
while(scanf("%d%d%d%d",&n,&m,&x,&y)!=EOF){
now=1;
now=max(min(min(m-y+1,y),n-x),now);
now=max(min(min(n-x+1,x),m-y),now);
now=max(min(min(m-y+1,y),x-1),now);
now=max(min(min(n-x+1,x),y-1),now);
if((n&1)&&(m&1)&&(2*x==n+1)&&(2*y==m+1)&&(n==m)){
now=n>>1;
}else now=max(now,(min(n,m)+1)>>1);
printf("%d\n",now);
}
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 1e16
#define N 222222
using namespace std;
long long T,n,i,j,L,K,u,d,ans,tot,tmp,a[N],dl[N],dr[N],q[N];
struct EG{long long x,y;}eg[N];
bool cmp(EG a,EG b){return a.x<b.x;}
int main(){
scanf("%I64d",&T);
while(T--){
memset(dl,0,sizeof(dl));memset(dr,0,sizeof(dr));
memset(q,0,sizeof(q));
scanf("%I64d%I64d%I64d",&L,&n,&K);tmp=inf;ans=0;tot=0;
for(i=1;i<=n;i++){
scanf("%I64d%I64d",&eg[i].x,&eg[i].y);
if(eg[i].x==L||eg[i].x==0)eg[i].y=0;
}
for(i=1;i<=n;i++){
if(eg[i].y>=K){
u=eg[i].y/K;
eg[i].y%=K;
d=min(eg[i].x,L-eg[i].x);
ans+=u*d;
}
}
sort(eg+1,eg+n+1,cmp);
for(i=1;i<=n;i++)
for(j=eg[i].y;j;j--)q[++tot]=eg[i].x;
for(i=1;i<=tot;i++)dl[i]=dl[max(i-K,(long long)0)]+q[i]+min(L-q[i],q[i]);
for(i=tot;i;i--)dr[i]=dr[min(i+K,tot+1)]+L-q[i]+min(L-q[i],q[i]);
for(i=0;i<=tot;i++)tmp=min(tmp,dl[i]+dr[i+1]);
printf("%I64d\n",ans*2+tmp);
}
}
2015 Multi-University Training Contest 3
开场发现T11是傻逼题，但再次由于姿势不太对CE了两发，现在想想要是当时不那么倔强，现在也没那么遗憾
然后就去弄T2了，发现RMQ随便搞搞就可以了，然后就MLE了，发现空间必须要O(n)。。
于是写了发线段树，再次MLE，连4*n的空间都不让开。。。
然后发现高一的小盆友都会做。。于是觉得肯定不是线段树什么的、、然后发现可以维护一个前缀和啊。。
然后终于A了，不过还是落后于高一小盆友。。
然后就去做数据结构题T1了，一开始以为是维修数列弱化版，然后发现自己太天真了
然后发现写平衡树实在是太坑爹了，于是乖乖地写了个线段树，1A了爽~
然后T10想了很久没有结果，但已经有很多人A了，感觉自己没有希望了，交了个判LCA的WA了、
然后发现可以树上DP搞搞，总算A了不容易
然后看1009很多人A，就是求二维LIS，觉得树套树没希望就弃疗了
今天发现竟然是二维偏序，要用CDQ分治+树状数组，非常简单的模板题。。
T3、T4、T8都被强力队友A了，YY大爷一改往日睡觉的颓势，强势回归
这场主力队RANK13，我们蒟蒻队RANK51，正好掉出了第一版~
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define inf 1e9
#define N 222222
#define M 222222
#define MOD 1000000007
using namespace std;
typedef long long LL;
int T,n,m,k,x,y,i,tot,ans,size[N],a[N],last[M],ne[M],first[N];char ch;
void ins(int x,int y){last[++tot]=y;ne[tot]=first[x];first[x]=tot;}
void read(int &x){
for(ch=getchar();ch<'0';ch=getchar());
for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void dfs(int x,int la){
size[x]=1;
for(int i=first[x];i;i=ne[i]){
int y=last[i];
if(y!=la){
dfs(y,x);
size[x]+=size[y];
}
}
}
int main(){
while(scanf("%d%d",&n,&k)!=EOF){
memset(first,0,sizeof(first));tot=0;
memset(size,0,sizeof(size));
rep(i,1,n-1)read(x),read(y),ins(x,y);
dfs(1,0);
for(ans=0,i=1;i<=n;i++)if(size[i]-1==k)ans++;
printf("%d\n",ans);
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 1000005
using namespace std;
int T,x,y,i,j,k,n,p,ans,R,prime[N>>1],cnt[N],now[8],sum[N][8];
bool f[N];
int main(){
n=1000000;
for(i=2;i<=n;i++){
if(!f[i]){
prime[++p]=i;
cnt[i]=1;
}
for(j=1;j<=p&&i*prime[j]<=n;j++){
f[i*prime[j]]=1;
if(i%prime[j]==0){
cnt[i*prime[j]]=cnt[i];
break;
}else{
cnt[i*prime[j]]=cnt[i]+cnt[prime[j]];
}
}
}
for(i=2;i<=n;i++){
for(j=1;j<=7;j++)sum[i][j]=sum[i-1][j];
sum[i][cnt[i]]++;
}
scanf("%d",&T);
while(T--){
scanf("%d%d",&x,&y);
for(i=1;i<=7;i++)now[i]=sum[y][i]-sum[x-1][i];
if(now[7]>=2)puts("7");else{
if(now[6]>=2)puts("6");else{
if(now[5]>=2)puts("5");else{
if(now[4]>=2)puts("4");else{
if(now[3]+now[6]>=2)puts("3");else{
if(now[2]+now[4]+now[6]>=2)puts("2");else{
puts("1");
}
}
}
}
}
}
}
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 1e16
#define N 111111
using namespace std;
typedef long long LL;
LL T,n,m,x,y,i,p,a[N];char ch;
struct Tr{LL l,r,v[4];}t[N*4],ans;
void pushup(LL k){//0jj 1jo 2 oj 3 oo
for(LL i=0;i<4;i++)t[k].v[i]=max(t[k<<1].v[i],t[k<<1|1].v[i]);
t[k].v[0]=max(t[k].v[0],max(t[k<<1].v[0]+t[k<<1|1].v[2],t[k<<1].v[1]+t[k<<1|1].v[0]));
t[k].v[1]=max(t[k].v[1],max(t[k<<1].v[0]+t[k<<1|1].v[3],t[k<<1].v[1]+t[k<<1|1].v[1]));
t[k].v[2]=max(t[k].v[2],max(t[k<<1].v[2]+t[k<<1|1].v[2],t[k<<1].v[3]+t[k<<1|1].v[0]));
t[k].v[3]=max(t[k].v[3],max(t[k<<1].v[2]+t[k<<1|1].v[3],t[k<<1].v[3]+t[k<<1|1].v[1]));
}
Tr update(Tr a,Tr b){
Tr c;
for(LL i=0;i<4;i++)c.v[i]=max(a.v[i],b.v[i]);
c.v[0]=max(c.v[0],max(a.v[0]+b.v[2],a.v[1]+b.v[0]));
c.v[1]=max(c.v[1],max(a.v[0]+b.v[3],a.v[1]+b.v[1]));
c.v[2]=max(c.v[2],max(a.v[2]+b.v[2],a.v[3]+b.v[0]));
c.v[3]=max(c.v[3],max(a.v[2]+b.v[3],a.v[3]+b.v[1]));
return c;
}
void change(LL k,LL x,LL key){
LL l=t[k].l,r=t[k].r,mid=(l+r)>>1;
if(l==r){
if(x&1)t[k].v[0]=key;else t[k].v[3]=key;
return;
}
if(x<=mid)change(k<<1,x,key);else change(k<<1|1,x,key);
pushup(k);
}
Tr query(LL k,LL x,LL y){
LL l=t[k].l,r=t[k].r,mid=(l+r)>>1;
if(x<=l&&r<=y){
return t[k];
}
if(x>mid)return query(k<<1|1,x,y);
else if(y<=mid)return query(k<<1,x,y);
else return update(query(k<<1,x,mid),query(k<<1|1,mid+1,y));
}
void buildtree(LL k,LL l,LL r){
t[k].l=l;t[k].r=r;
if(l==r){
for(LL i=0;i<4;i++)t[k].v[i]=-inf;
if(l&1)t[k].v[0]=a[l];else t[k].v[3]=a[l];
return;
}
LL mid=(l+r)>>1;
buildtree(k<<1,l,mid);
buildtree(k<<1|1,mid+1,r);
pushup(k);
}
int main(){
scanf("%lld",&T);
while(T--){
scanf("%lld%lld",&n,&m);
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
buildtree(1,1,n);
while(m--){
scanf("%lld%lld%lld",&p,&x,&y);
if(!p){
ans=query(1,x,y);
printf("%lld\n",max(max(ans.v[0],ans.v[1]),max(ans.v[2],ans.v[3])));
}else change(1,x,y);
}
}
}
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define inf 1e9
#define N 555555
#define M 1111111
#define MOD 1000000007
using namespace std;
typedef long long LL;
int T,n,m,x,y,i,tot,tmp,now,ans,a[N],fa[N],last[M],ne[M],first[N],size[N],sz2[N];char ch;
void ins(int x,int y){last[++tot]=y;ne[tot]=first[x];first[x]=tot;}
void read(int &x){
for(ch=getchar();ch<'0';ch=getchar());
for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void dfs(int x){
size[x]=1;
for(int i=first[x];i;i=ne[i]){
int y=last[i];
if(y!=fa[x]){
fa[y]=x;
dfs(y);
if(a[x]<a[y])size[x]+=size[y];
}
}
}
void dfs2(int x,int w){
sz2[x]=size[x];
if(a[fa[x]]>a[x])sz2[x]+=w;
ans=max(ans,sz2[x]);
for(int i=first[x];i;i=ne[i]){
int y=last[i];
if(y!=fa[x]){
int tmp;
if(a[y]>a[x])tmp=size[y];else tmp=0;
dfs2(y,sz2[x]-tmp);
}
}
}
int main(){
while(scanf("%d",&n)!=EOF){
memset(first,0,sizeof(first));tot=0;ans=0;
memset(fa,0,sizeof(fa));
memset(size,0,sizeof(size));
memset(sz2,0,sizeof(sz2));
rep(i,1,n)read(a[i]);
rep(i,1,n-1)read(x),read(y),ins(x,y),ins(y,x);
dfs(1);dfs2(1,0);
printf("%d\n",ans);
}
}
2015 Multi-University Training Contest 4
开场就发现T1是大水题，就秒了
然后发现T2也是大水题，但RE了一发又没开LL WA了一发。。
然后看T5，写了发二分图WA了，后来发现的确是不对的，如果离线可以树形DP，但在线似乎没啥办法啊
然后T9想了一会觉得就是先能走0就走0然后判断，但感觉直接记忆化是存不下的
一开始想Bitset，但觉得就算bitset也肯定MLE了。。。。
然后发现可以逐步判断哪些格子是可以走的，而且对答案输出没有影响，因为答案是一样的。。
但还是由于一些小问题WA了3发。。。。
然后看T12分解置换A的人挺多，但我连样例都没搞懂怎么弄，又重新研究了下置换，还是没搞懂，于是弃疗了
然后T10由于英文太差并没有看懂，于是就去翻讨论版，整合了一下讨论的信息差不多懂了是什么题了
然后写了发模拟，虽然理论时间复杂度是可行的，但还是TLE了。。加了读入优化也无济于事
只好用SET优化了一下，总算A了。。。。
然后T8被LX大爷A了，LX大爷太强了，这题我看都没看懂。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define inf 1e9
#define N 222222
#define M 222222
#define MOD 1000000007
using namespace std;
typedef long long LL;
int T,n,m,x,y,i,ff,now,sum[N];char ch;
bool f[10];
void read(int &x){
for(ch=getchar();ch<'0';ch=getchar());
for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
int main(){
for(i=1;i<=100000;i++){
now=i;memset(f,0,sizeof(f));ff=0;
while(now>0){
if(f[now%10])ff=1;
f[now%10]=1;
now/=10;
}
if(!ff)sum[i]=sum[i-1]+1;else sum[i]=sum[i-1];
}
read(T);
while(T--){
read(x);read(y);
printf("%d\n",sum[y]-sum[x-1]);
}
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define inf 1e9
#define N 1111111
#define MOD 1000000007
using namespace std;
typedef long long LL;
int T,n,m,x,y,i,ans,h1,h2,q1[N],q2[N],a[N];char ch;
void read(int &x){
for(ch=getchar();ch<'0';ch=getchar());
for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
int main(){
read(T);
while(T--){
scanf("%d",&n);rep(i,1,n)read(a[i]);
if(n==1){puts("1");continue;}
if(n==2){puts("2");continue;}
q1[1]=1;q1[2]=2;h1=2;
q2[1]=1;q2[2]=2;h2=2;
ans=2;
rep(i,3,n){
if(a[i]-a[q1[h1]]==a[q1[h1]]-a[q1[h1-1]])q1[++h1]=i;else{
q1[1]=i-1;q1[2]=i;h1=2;
}
if((long long)a[i]*(long long)a[q2[h2-1]]==(long long)a[q2[h2]]*(long long)a[q2[h2]])q2[++h2]=i;else{
q2[1]=i-1;q2[2]=i;h2=2;
}
ans=max(h1,ans);ans=max(h2,ans);
}
printf("%d\n",ans);
}
}
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define inf 1e9
#define N 1111
#define MOD 1000000007
using namespace std;
typedef long long LL;
int T,n,m,x,y,i,j,w,tmp,now,a[N][N];char s[N],ch;
bool vis[N][N],wil[N][N];
void read(int &x){
for(ch=getchar();ch<'0';ch=getchar());
for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void dfs(int x,int y){
now=max(now,x+y);
vis[x][y]=1;
if(a[x][y]==1)return;
if(x>1&&a[x-1][y]==0&&!vis[x-1][y])dfs(x-1,y);
if(x<n&&a[x+1][y]==0&&!vis[x+1][y])dfs(x+1,y);
if(y>1&&a[x][y-1]==0&&!vis[x][y-1])dfs(x,y-1);
if(y<m&&a[x][y+1]==0&&!vis[x][y+1])dfs(x,y+1);
}
int main(){
read(T);
while(T--){
memset(vis,0,sizeof(vis));memset(wil,0,sizeof(wil));memset(a,0,sizeof(a));now=0;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%s",s+1);
for(j=1;j<=m;j++)
a[i][j]=s[j]-'0';
}
dfs(1,1);
if(a[1][1]==1)printf("1"),now=2;else if(now==n+m){puts("0");continue;}
for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(i+j==now&&vis[i][j])wil[i][j]=1;//,printf("%d %d\n",i,j);
for(w=now;w<=m+n-1;w++){
tmp=2;
for(i=1;i<=n;i++){
j=w-i;
if(j<=0||j>m)continue;
if(wil[i][j]){
if(i<n)tmp=min(tmp,a[i+1][j]);
if(j<m)tmp=min(tmp,a[i][j+1]);
}
}
for(i=1;i<=n;i++){
j=w-i;
if(j<=0||j>m)continue;
if(wil[i][j]){
if(j<m)if(a[i][j+1]==tmp)wil[i][j+1]=1;//,printf("%d %d\n",i,j+1);
if(i<n)if(a[i+1][j]==tmp)wil[i+1][j]=1;//,printf("%d %d\n",i+1,j);
}
}
printf("%d",tmp);
}
puts("");
}
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define inf 1e9
#define N 222
#define M 222
#define MOD 1000000007
using namespace std;
typedef long long LL;
int T,n,x,y,z,i,j,k,r,c,w,a[N][N],pos[N][N],lx[N],time[N],xx[5],yy[5];char ch;
struct EG{int x,y;}eg[N];
set<pair<pair<int,int>,int> >st,st2;
set<pair<pair<int,int>,int> >::iterator it;
pair<pair<int,int>,int>tmp;
void read(int &x){
for(ch=getchar();ch<'0';ch=getchar());
for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
int main(){
xx[0]=1;xx[1]=-1;yy[2]=1;yy[3]=-1;
while(scanf("%d%d%d%d",&r,&c,&n,&T)!=EOF){
memset(a,0,sizeof(a));
memset(pos,0,sizeof(pos));
memset(time,0,sizeof(time));
st.clear();
for(i=1;i<=n;i++){
read(eg[i].x);read(eg[i].y);read(z);
a[eg[i].x][eg[i].y]=z;
pos[eg[i].x][eg[i].y]=i;
}
memset(lx,1,sizeof(lx));
read(x);read(y);
for(i=0;i<=3;i++)st.insert(make_pair(make_pair(x,y),i));
for(w=1;w<=T;w++){
st2=st;st.clear();
for(it=st2.begin();it!=st2.end();it++){
tmp=*it;tmp.first.first+=xx[tmp.second];tmp.first.second+=yy[tmp.second];
if(tmp.first.first<1||tmp.first.first>r||tmp.first.second<1||tmp.first.second>c)continue;
if(pos[tmp.first.first][tmp.first.second]&&lx[pos[tmp.first.first][tmp.first.second]]){
if(++a[tmp.first.first][tmp.first.second]>4){
a[tmp.first.first][tmp.first.second]=0;
for(i=0;i<=3;i++)st.insert(make_pair(make_pair(tmp.first.first,tmp.first.second),i));
lx[pos[tmp.first.first][tmp.first.second]]=0;
time[pos[tmp.first.first][tmp.first.second]]=w;
}
}else st.insert(tmp);
}
}
for(i=1;i<=n;i++)if(lx[i])printf("1 %d\n",a[eg[i].x][eg[i].y]);else printf("0 %d\n",time[i]);
}
}
2015 Multi-University Training Contest 5
中午吃完饭到机房已经11:59了，只好赶紧上，但还是没恢复过来。。
开局看水题，先发现T7是水题，但写SET由于姿势不太对总是调不出，弄了将近20分钟，然后队友早就把三道水题全切了。。
然后看T4，想了一会觉得n^3DP还是挺简单的，但是n^2就死也想不出来啦
然后已经过了将近两个小时了，我还是0贡献，然后黄主力T6会做但是WA了，就听了下他的思路，感觉挺对的，看了下T6和他的代码
写了个CHECK，发现黈力程序的错误挺严重的。。然后黈力改好错误就A了。。我也蹭了他的程序“A”了。。
然后想T4也想不出，然后T10看不懂就去问了下YY大爷题意，把题目转化了一下
一开始想状压，但N=200明显不可能啊。。然后我跟YY大爷说了下我的想法，他提到了网络流，我瞬间领悟过来，这题网络流一下第一问不是秒出吗
虽然从来没写过字典序的网络流，但没办法别的题不会做了还是要试试看，于是写了发，尝试顺着流倒着流，发现倒着流再反边就对啦，然后一交竟然1A啦
然后看了下T1，觉得肯定是SAM之类的，想把字符单个算，但手算就错了，然后就觉得没有办法了
然后只有半小时了，就开始爆T3，一开始没随机化，后来又发现输错了，然后再爆也没有结果。然后发现卡下时间也许可以出解，但卡到第10个时时间已经不够了。。
最后就只做了1道题滚粗啦。。不过我们队排名还不错，排到了RANK18，主力队更是怒肏RANK6
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<bitset>
#define fon(i,n) for(int i=0;i<n;i++)
#define frn(i,n) for(int i=1;i<=n;i++)
#define drn(i,n) for(int i=n;i;i--)
#define don(i,n) for(int i=n-1;i>=0;i--)
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define mjj(i,x) for(int i=fir[x];i;i=ne[i])
#define X first
#define Y second
#define MAX(a,b) a=max(a,b)
#define MIN(a,b) a=min(a,b)
#define mp make_pair
#define rlr son[son[root][1]][0]
#define gi(a) scanf("%d",&a);
#define gi2(a,b) scanf("%d%d",&a,&b);
#define gi3(a,b,c) scanf("%d%d%d",&a,&b,&c);
#define gl(a) scanf("%I64d",&a);
#define gs(s) scanf("%s",s);
#define pi(a) printf("%d\n",a);
#define pi2(a,b) printf("%d %d\n",a,b);
#define pl(a) printf("%I64d\n",a);
#define spr(x) (x*x)
#define pie acos(-1)
#define CP(a,b) memcpy(a,b,sizeof(a))
#define CL(a) memset(a,0,sizeof(a))
#define N 707
#define M 99999
#define MOD 1000000007
#define inf 1e9
#define eps 1e-8
using namespace std;
typedef long long LL;typedef unsigned long long ULL;typedef double LF;typedef long double LD;
typedef pair<int,int>pii;typedef pair<int,LL>pil;typedef pair<LL,int>pli;typedef pair<LL,LL>pll;typedef pair<LF,LF>pff;
const int xx[]={1,-1,0,0},yy[]={0,0,1,-1};
map<pii,int>ma;
map<pii,int>::iterator it;
int T,n,m,x,y,i,j,tot,tot2,po,k,p;
bool vv[1111][222],fr[1111];
int la2[1111],ne2[1111],fir2[1111],to[1111];void ins(int x,int y){la2[++tot2]=y;ne2[tot2]=fir2[x];fir2[x]=tot2;ma[mp(x,y)]=tot2;}
void del(int x,int y){fr[ma[mp(x,y)]]=fr[ma[mp(x,y)]^1]=1;}
void ISAP(){memset(numb,0,sizeof(numb));memset(dist,0,sizeof(dist));memset(pre,0,sizeof(pre));for(i=1;i<=t;i++)cur[i]=fir[i];u=s;numb[0]=t;while(dist[s]<t){if(u==t){now=inf;for(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]&&dist[la[i]]+1==dist[u])break;if(i){cur[u]=i;pre[la[i]]=u;u=la[i];}else{if(0==--numb[dist[u]])break;for(i=cur[u]=fir[u],tmp=t;i;i=ne[i])if(dist[la[i]]<tmp&&va[i])tmp=dist[la[i]];++numb[dist[u]=tmp+1];if(u!=s)u=pre[u];}}}
void find(int x){
vv[po][x]=1;
for(int i=fir2[x];i;i=ne2[i])
if(!fr[i]){
int y=la2[i];
if(!vv[po][y]){
vv[po][y]=1;
find(y);
}
}
}
char ch;void read(int &x){for(ch=getchar();ch<'0';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
int main(){
scanf("%d",&T);
while(T--){
tot=tot2=1;
CL(fir);CL(fir2);CL(vv);CL(fr);CL(ne);CL(ne2);CL(la);CL(la2);
u=po=s=t=now=tmp=flow=0;
scanf("%d%d%d",&n,&m,&k);
for(int w=1;w<=m;w++){
scanf("%d",&p);
if(p==1){
po++;
scanf("%d",&x);find(x);
}else if(p==2){
scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}else{
scanf("%d",&p);
for(i=1;i<=p;i++)scanf("%d%d",&x,&y),del(x,y),del(y,x);
}
}
s=n+po+1;t=s+1;
for(i=1;i<=n;i++)ins(po+i,t,1);
for(int w=po;w;w--){
ins(s,w,k);to[w]=tot;
for(int o=1;o<=n;o++)if(vv[w][o])ins(w,po+o,1);
u=s;
ISAP();
}
printf("%d\n",flow);
for(i=1;i<=po;i++)
if(i==1)printf("%d",va[to[i]]);else printf(" %d",va[to[i]]);puts("");
}
}
然后1001其实挺简单的，后缀自动机直接上就行啦。。
#include<cstdio>
#include<cstring>
#define frn(i,n) for(int i=1;i<=n;i++)
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define drn(i,n) for(int i=n;i;i--)
#define CL(a) memset(a,0,sizeof(a))
#define N 200000
typedef unsigned long long LL;
int T,n,m,i,j;char s[N];LL ans,dp[27];bool vis[N];
struct SAM{
int S,p,q,np,nq,last,cnt,son[N][26],fa[N],step[N],to[N];
void init(){
S=last=cnt=1;
memset(to,-1,sizeof(to));
CL(son);CL(step);CL(fa);
step[0]=-1;
}
void add(int c){
p=last;last=np=++cnt;step[np]=step[p]+1;to[np]=c;
for(;p&&!son[p][c];p=fa[p])son[p][c]=np;
if(!p)fa[np]=S;else{
q=son[p][c];
if(step[p]+1==step[q])fa[np]=q;else{
nq=++cnt;step[nq]=step[p]+1;
memcpy(son[nq],son[q],sizeof son[q]);
fa[nq]=fa[q];fa[q]=fa[np]=nq;
for(;p&&son[p][c]==q;p=fa[p])son[p][c]=nq;
}
}
}
}A,B;
int main(){
scanf("%d",&T);
while(T--){
ans=0;A.init();B.init();CL(dp);CL(vis);
scanf("%s",s+1);n=strlen(s+1);
frn(i,n)A.add(s[i]-'a');
scanf("%s",s+1);m=strlen(s+1);
drn(i,m)B.add(s[i]-'a');
for(vis[B.S]=i=1;i<=B.cnt;i++)if(B.to[i]>=0&&!vis[i])
for(j=i;!vis[j];vis[j]=1,j=B.fa[j])if(B.to[B.fa[j]]==-1)B.to[B.fa[j]]=B.to[i];else break;
fr(i,2,B.cnt)dp[B.to[i]]+=(LL)(B.step[i]-B.step[B.fa[i]]);
frn(i,A.cnt){
LL num=(LL)(A.step[i]-A.step[A.fa[i]]);
ans+=num;
for(int j=0;j<26;j++)if(!A.son[i][j]){
ans+=num*dp[j];
}
}
printf("%I64u\n",ans);
}
}
然后1008是合并果子也是醉了，代码不到1K，比赛时我看没多少人做看都没看、
2015 Multi-University Training Contest 6
开场发现主力队马上肏了T11，于是发现T11是一道傻逼题，拉个板秒掉了
然后看了下别的题，一开始弄T7，感觉就是模板题，但似乎找不到求有向图割边的模板
然后觉得T6还是可以做的。。于是开始肏T6。。
一开始写了个nlgnlgΣai的算法，写了挺久，然后觉得太坑爹肯定T
于是开始写nlgΣai的算法，我调了好久总算调出来了，可是竟然T了。。
我想我这复杂度也已经最低了吧。。然后这时候主力队和高一都4题了。。我还在摞T6摞不出、
然后各种卡常数，卡了7发总算卡过去了
然后看T3做对的人挺多的，我觉得贪心挺对，但YY大爷一口否定。。
于是只好写了个网络流，写到一半发现肯定没希望的，就弃疗了、、
后来发现T3A的人实在太多了，然后就乱写了一个贪心，竟然A了
然后T8也被鏼出来了，然后看T9作对的人挺多的，开始弄T9
然后发现就是黈力昨天给我出的题，虽然当时我T了最大的数据，但这里的N比较小，应该能过吧
可是我写完SPFA后发现T了。。然后各种卡常数，改成Dijkstra也没用
调了好久，大约爆了30多发OJ，然后想了会，发现有的点比较多余，只需要2*N个点就够啦。。
结果爆了20多发还是T，我只好弃疗了、、
最后10分钟发现T9可以线段树+Dijkstra肏掉，可是时间不够来不及写了。。
这场被高一摞翻啦，排名掉到了88名，高一都RANK36啦。。主力队也拿了RANK18、
LL pow(LL a,LL b,LL p){LL sum=1;for(a%=p;b;a=a*a%p,b>>=1)if(b&1)sum=sum*a%p;return sum;}
int T,n,m,x,y,i,j,tot,a[N];
long long ans;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
ans=pow(2,n-1,MOD);
ans--;if(ans<0)ans+=MOD;
printf("%lld\n",ans);
}
}
int T,n,m,x,y,i,j,tot,top,fl,a[N],q[N];bool v[N];
int main(){
scanf("%d",&T);
while(T--){
CL(v);
scanf("%d%d",&n,&m);
tot=n*(n+1)/2;
if(tot%m!=0||n>(tot/m))puts("NO");else{
puts("YES");
for(i=1;i<=m;puts(""),i++){
fl=tot/m;top=0;
for(j=n;j;j--)if(!v[j]&&fl>=j)fl-=j,q[++top]=j,v[j]=1;
printf("%d ",top);
for(j=top;j;j--)printf("%d ",q[j]);
}
}
}
}
#include<cstdio>
#include<cstring>
#define N 100100
char ch;void read(long long &x){for(ch=getchar();ch<'0';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
long long ans,nv,a[N],f[N],now,er[36];
int T,n,t,i,j,la[N];bool flag;
int main(){
scanf("%d",&T);
er[0]=1;for(i=1;i<=34;i++)er[i]=er[i-1]*2;
while(T--){
memset(f,0,sizeof(f));
scanf("%d",&n);ans=0;
for(i=1;i<=n;i++){
read(a[i]),a[i]+=a[i-1];f[0]=i;
for(j=0;j<=34;j++){
while(a[i]-a[f[j]]>=er[j])f[j]++;
ans+=(f[j-1]-f[j])*((long long)i*2+(f[j]+1+f[j-1]))*(long long)j;
}
}
printf("%I64d\n",ans/2);
}
}
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 400102
#define inf 1e16
using namespace std;
int T,i,x,y,l,r,n,m,tot,w,to[N],X[N],Y[N];
long long Z[N],dis[N];struct Tr{long long mv,lazy;int l,r,from;bool sel;}t[N*4];
void pushup(int k){
t[k].lazy=inf;
if(t[k<<1].sel&&t[k<<1|1].sel){t[k].sel=1,t[k].mv=t[k].lazy=inf;return;}
if(t[k<<1].sel){t[k].mv=t[k<<1|1].mv;t[k].from=t[k<<1|1].from;return;}
if(t[k<<1|1].sel){t[k].mv=t[k<<1].mv;t[k].from=t[k<<1].from;return;}
if(t[k<<1].mv<t[k<<1|1].mv)t[k].from=t[k<<1].from,t[k].mv=t[k<<1].mv;
else t[k].from=t[k<<1|1].from,t[k].mv=t[k<<1|1].mv;
}
void pushdown(int k){
t[k<<1].mv=min(t[k<<1].mv,t[k].lazy);
t[k<<1|1].mv=min(t[k<<1|1].mv,t[k].lazy);
t[k<<1].lazy=min(t[k<<1].lazy,t[k].lazy);
t[k<<1|1].lazy=min(t[k<<1|1].lazy,t[k].lazy);
if(t[k].sel)t[k<<1].sel=t[k<<1|1].sel=1;
t[k].lazy=inf;
}
void build(int k,int l,int r){
t[k].l=l;t[k].r=r;t[k].lazy=inf;t[k].sel=0;t[k].mv=inf;
if(l==r){t[k].from=l;if(l==1)t[k].mv=0;to[l]=k;return;}
int mid=(l+r)>>1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
pushup(k);
}
void modify(int k,int x,int y,long long key){
if(t[k].sel)return;
int l=t[k].l,r=t[k].r;
pushdown(k);
if(x<=l&&r<=y){
if(key<t[k].mv)t[k].mv=key,t[k].from=x;
t[k].lazy=min(t[k].lazy,key);
return;
}
int mid=(l+r)>>1;
if(x>mid)modify(k<<1|1,x,y,key);
else if(y<=mid)modify(k<<1,x,y,key);
else modify(k<<1,x,mid,key),modify(k<<1|1,mid+1,y,key);
pushup(k);
}
void go(int k,int w){
pushdown(k);
int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
if(l==r){t[k].mv=t[k].lazy=inf;t[k].sel=1;return;}
if(w<=mid)go(k<<1,w);else go(k<<1|1,w);
pushup(k);
}
char ch;void read(int &x){for(ch=getchar();ch<'0';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
void Read(long long &x){for(ch=getchar();ch<'0';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
int main(){
read(T);
while(T--){
read(n);
build(1,1,n);
for(i=1;i<=n;i++)read(X[i]);
for(i=1;i<=n;i++)read(Y[i]);
for(i=1;i<=n;i++)Read(Z[i]);
for(i=1;i<=n;i++)dis[i]=inf;
for(int k=1;k<=n;k++){
i=t[1].from;
dis[i]=t[1].mv;
go(1,i);
l=max(min(i+X[i],n+1),i+1);r=min(i+Y[i],n);
if(l<=n&&l<=r)modify(1,l,r,dis[i]+Z[i]);
l=max(i-Y[i],1);r=min(max(i-X[i],0),i-1);
if(r>=1&&l<=r)modify(1,l,r,dis[i]+Z[i]);
}
for(i=1;i<=n;i++)if(dis[i]==inf)printf("-1 ");else printf("%lld ",dis[i]);puts("");
}
}
2015 Multi-University Training Contest 7
由于YY大爷在螺杆螺杆
，我11:57还在校门外溜达，发现了以后赶紧往机房跑，差不多十二点多几秒跑到了机房，赶紧开题看。。
然后看了会觉得没有什么题能做的，然后chorme又爆了就颓了一会儿。。
然后发现有人A了T5，就发现这是一道傻逼题，马上就艹掉了
然后似乎T7也有人做出来了，百度了一下格雷码，说是二进制转格雷码就是两位两位异或。。
然后想了一会就把DP想出来了，然后就秒了。。
不过这时主力队已经4题领板了、
然后看了一会觉得T11对的人挺多的，拿到翻译以后就开始摞，YY了很多不同情况，但最后还是连样例都没过，主力队都已经7题了。。
大约14:30的时候发现我们队已经A了，于是也就弃疗了
然后摞那道最长1.5回文串T3，我想我曾经做过最长双回文串，于是就翻了翻那道题的题解、
然后发现只要改动一个小小的地方就可以啦，于是改了一下试试看，试了几组数据就交了，竟然A啦
然后颓了一会开始摞T5，一开始发现这是一道二维树状数组裸题，于是写了个MAP+树状数组去作死，毫不意外MLE了
然后发现可以统计在该线段左边和右边端点的个数得到答案，但是一直TLE。。然后只有二十多分钟了、
最后才发现题目看错了一点，他改的时候需要的是修改操作的次数不是总次数，然后赶紧写但是又WA了。。
然后没有办法最后一分钟赶紧把主力队程序弄下来，就当我会做了、
这场主力队9题怒肏RANK3，仅仅是惜败于杜教领衔的学车代表队，我们队仅仅拿到了RANK68.。
int T,n,m,x,y,i,j,tot,now,ws,top,sum,ans1,ans2,pp,cas,a[N],b[N];
char s[N];
int main(){
while(scanf("%s%d",s+1,&n)!=EOF){
if(n==-1)return 0;
printf("Case #%d: ",++cas);
ws=strlen(s+1);sum=0;ans1=0;ans2=0;
for(i=1;i<=ws;i++)a[i]=s[i]-'0',sum+=a[i];
while(n--){
now=sum;top=0;
while(now){
b[++top]=now%10;
sum+=now%10;
now/=10;
}
for(i=1;i<=top;i++)a[++ws]=b[top-i+1];
}
for(i=1;i<=ws;i++)if(i&1)ans1+=a[i];else ans2+=a[i];
pp=ans1-ans2;
if(pp<0)pp=-pp;
if(pp%11==0)puts("Yes");else puts("No");
}
}
int T,n,m,x,y,i,j,tot,cas,a[N],dp[N][2];char s[N];
int main(){
scanf("%d",&T);
while(T--){
scanf("%s",s+1);n=strlen(s+1);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
dp[1][0]=0;dp[1][1]=a[1];
if(s[1]=='0')dp[1][1]=-inf;
if(s[1]=='1')dp[1][0]=-inf;
for(i=2;i<=n;i++){
if(s[i]=='?'){
dp[i][0]=max(dp[i-1][1]+a[i],dp[i-1][0]);
dp[i][1]=max(dp[i-1][0]+a[i],dp[i-1][1]);
}else if(s[i]=='0'){
dp[i][0]=max(dp[i-1][1]+a[i],dp[i-1][0]);
dp[i][1]=-inf;
}else{
dp[i][1]=max(dp[i-1][0]+a[i],dp[i-1][1]);
dp[i][0]=-inf;
}
}
printf("Case #%d: %d\n",++cas,max(dp[n][0],dp[n][1]));
}
}
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define mod 1000000007
#define inf 1000000000
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,ans,T,cas,ch[500005],p[500005],q[500005];
set<int> t;
void manacher(){
memset(p,0,sizeof(p));
int mx=0,id=0;
for(int i=1;i<=n;i++){
if(mx>=i)p[i]=min(mx-i,p[2*id-i]);else p[i]=0;
for(;ch[i+p[i]+1]==ch[i-p[i]];p[i]++);
if(p[i]+i>mx)id=i,mx=p[i]+i;
}
}
bool cmp(int a,int b){return (a-p[a])<(b-p[b]);}
int main(){
scanf("%d",&T);
while(T--){
ans=0;t.clear();
n=read();
for(int i=1;i<=n;i++)ch[i]=read();
ch[0]=1000000001;
manacher();
for(int i=1;i<=n;i++)q[i]=i;
sort(q+1,q+n+1,cmp);
int now=1;
for(int i=1;i<=n;i++){
while(now<=n&&q[now]-p[q[now]]<=i){
t.insert(q[now]);
now++;
}
set<int>::iterator tmp=t.upper_bound(i+p[i]);
if(tmp!=t.begin())ans=max(ans,(*--tmp-i)*3);
}
printf("Case #%d: %d\n",++cas,ans);
}
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#define CL(a) memset(a,0,sizeof(a))
#define M 411114
using namespace std;
int f,x,sum,cnt,pp,p[M],c1[M],c2[M],v[M],to[M],w,top,n,i,cas;
struct EG{int l,r;}eg[M];char ch;
void read(int &x){
for(f=0,ch=getchar();ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=1;
for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';if(f)x=-x;
}
void add(int c[],int x,int y){for(;x<=top*2+1;x+=x&-x)c[x]+=y;}
int query(int c[],int x){for(sum=0;x;x-=x&-x)sum+=c[x];return sum;}
int main(){
while(scanf("%d",&n)!=EOF){
printf("Case #%d:\n",++cas);top=0;pp=0;
CL(c1);CL(c2);CL(v);CL(eg);CL(p);cnt=0;
for(i=1;i<=n;i++){
read(p[i]);read(x);
if(!p[i]){
pp++;eg[pp].l=x;eg[pp].r=x+pp;
v[++top]=x;v[++top]=x+pp;
to[i]=pp;
}else to[i]=x;
}
sort(v+1,v+top+1);cnt=unique(v+1,v+top+1)-(v+1);
for(i=1;i<=pp;i++)eg[i].l=lower_bound(v+1,v+top+1,eg[i].l)-v,eg[i].r=lower_bound(v+1,v+top+1,eg[i].r)-v;
for(i=1;i<=n;i++){
w=to[i];
if(!p[i]){
printf("%d\n",query(c2,eg[w].r)-query(c1,eg[w].l-1));
add(c1,eg[w].l,1);add(c2,eg[w].r,1);
}else add(c1,eg[to[i]].l,-1),add(c2,eg[to[i]].r,-1);
}
}
}
2015 Multi-University Training Contest 8
开场发现T8是一道普及难度的模拟，就开始摞，摞来摞去摞了20分钟第一发交上去PE了，但发现我们队已经A了
颓了一会，然后T10把表打出来发现了明显的规律，想了一会觉得DP一下就好了，但由于一些特殊情况没有处理好WA了三发才A。。
然后看T7 A的人挺多的，就开始写暴力，但30分钟过编译后发现我们队又已经A了。。
然后就开始弄AC自动机题T5，弄了一个多小时1A了，但发现我们队还是已经A了、、
然后看来看去觉得都挺难的，就游走了一会。然后开始弄T6，弄了一会弄出来了
然后看T2挺多人A的，想了好久但也没有想出怎么做。。最后摞T3也没有摞出来
这场只有2贡献，排到了55名，主力队创造了第二名的最佳战绩
int T,n,m,a,b,c,x,y,i,j,tot,fz,sz,mz,aa,bb,cc,ga,gb,gc,fm,mm,sm;
char s[9];
int main(){
scanf("%d",&T);
while(T--){
scanf("%s",s);
a=(s[0]-'0')*10+(s[1]-'0');
b=(s[3]-'0')*10+(s[4]-'0');
c=(s[6]-'0')*10+(s[7]-'0');
if(a>=12)a-=12;
mz=c*60*12;fm=mm=sm=43200;
fz=(c+b*60)*12;
sz=c+b*60+a*3600;
aa=abs(sz-fz);
bb=abs(sz-mz);
cc=abs(fz-mz);
aa*=360;bb*=360;cc*=360;
if(aa>7776000)aa=2*7776000-aa;
if(bb>7776000)bb=2*7776000-bb;
if(cc>7776000)cc=2*7776000-cc;
ga=gcd(aa,43200);gb=gcd(bb,43200);gc=gcd(cc,43200);
aa/=ga;fm/=ga;bb/=gb;mm/=gb;cc/=gc;sm/=gc;
printf("%d",aa);if(fm!=1)printf("/%d",fm);printf(" ");
printf("%d",bb);if(mm!=1)printf("/%d",mm);printf(" ");
printf("%d",cc);if(sm!=1)printf("/%d",sm);puts(" ");
}
}
int T,n,m,now,pp,x,y,i,j,k,tot,A,B,ans,a[N],dp[10],g[10];
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&A,&B);
now=0;CL(dp);CL(g);
dp[0]=1;
for(i=1;i<=n;i++){
CL(g);
scanf("%d",&x);now=(now+x)%9;
for(j=0;j<9;j++)g[(j+x)%9]=(dp[j]+dp[(j+x)%9])%MOD;
for(j=0;j<9;j++)dp[j]=g[j];
}
ans=0;if(now==(A+B)%9)ans=dp[A%9];
if(now==A%9&&B!=9)ans++;if(now==B%9&&A!=9)ans++;
printf("%d\n",ans%MOD);
}
}
#include<cstdio>
#include<cstring>
#include<vector>
#define N 111111
#define M 11111
#define CL(a) memset(a,0,sizeof(a))
using namespace std;
int T,n,m,cnt,ans2[N],q[N],fail[N],st[N],to[N][26];
vector<int> a[N];char s[M];
struct data{
void insert(int id){
scanf("%s",s+1);
int L=strlen(s+1);
int now=1;
for(int i=1;i<=L;i++){
int x=s[i]-'a';
if(!to[now][x])to[now][x]=++cnt;
now=to[now][x];
}
st[now]++;
}
void buildfail(){
int head=1,tail=1;
for(int i=0;i<26;i++)
if(to[1][i]){
fail[to[1][i]]=1;
q[++tail]=to[1][i];
}
while(head<tail){
int x=q[++head];
for(int i=0;i<26;i++){
int v=to[x][i];
if(!v)continue;
int k=fail[x];
while(!to[k][i])k=fail[k];
fail[v]=to[k][i];
q[++tail]=v;
}
}
}
void get(int id,int x){for(int i=x;i;i=fail[i])ans2[id]+=st[i];}
void solve(int x){
int now=1;
for(int i=0;i<a[x].size();i++){
int t=a[x][i];
while(!to[now][t])now=fail[now];
now=to[now][t];get(x,now);
}
}
}trie;
int main(){
scanf("%d",&T);
while(T--){
CL(ans2);CL(to);CL(fail);CL(st);
fail[1]=0;for(int i=0;i<26;i++)to[0][i]=1;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)a[i].clear();
int L,x;cnt=1;
for(int i=1;i<=n;i++){
scanf("%s",s+1);int u=strlen(s+1);
for(int j=1;j<=u;j++)a[i].push_back(s[j]-'a');
}
for(int i=1;i<=m;i++)trie.insert(i);
trie.buildfail();
for(int i=1;i<=n;i++)trie.solve(i);
for(int i=1;i<=n;i++)printf("%d\n",ans2[i]);
}
}
int T,n,m,x,y,l,r,i,tot,dis[N],pre[N];
int la[M],ne[M],og[M],fir[N];void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;og[tot]=x;}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);tot=0;
CL(fir);CL(pre);
for(i=1;i<=m;i++)scanf("%d%d",&x,&y),ins(x,y);
for(i=fir[1];i;i=ne[i])pre[la[i]]=1;
l=2;r=n;tot=0;
while(l<=r){
if(pre[l]){
for(i=fir[l];i;i=ne[i])pre[la[i]]=l;
dis[l++]=++tot;
}else if(pre[r]){
for(i=fir[r];i;i=ne[i])pre[la[i]]=r;
dis[r--]=++tot;
}
}
for(i=1;i<=m;i++)if(dis[la[i]]-dis[og[i]]<=0)printf("%d\n",n);else printf("%d\n",dis[la[i]]-dis[og[i]]);
}
}
2015 Multi-University Training Contest 9
这场我中途有两个小时要去上课，于是就比较坑。。
开场先看了T7，虽然看上去挺简单但觉得挺难写的就先放到一边。。然后看T5挺水的，原来以为能水过的，没想到WA了、、
查了好久才发现原来d1=d2的时候要特判一下，不然就痿了、、
然后看T4也是挺简单的，赶在上课前交了几发，可是都WA了。。
上课回来差不多是三点多，就继续交，还是交不过。。觉得哪里都没错了，和主力队代码还对了一遍还是觉得都考虑到了、、最后没办法了交了主力队的、
然后开始弄T7，画了一会发现有些点不能挖，后来发现奇数点都不能挖，然后就觉得两列两列做是没有什么问题的
就写了发，然后WA了，然后调出了一些小错误，但还是WA。。
然后Marscat来帮助我，马上就又发现了一个小错误，最后终于A了。。
毫不意外地创造历史最低成绩，同时也是A4题中罚时最多的队伍
LL ans;
int T,n,m,x,y,i,j,tot,now,fg,d1,d2,q[N],t1[N],t2[N],a[N];
int main(){
while(scanf("%d%d%d",&n,&d1,&d2)!=EOF){
for(i=1;i<=n;i++)scanf("%d",&a[i]);
ans=0;
if(d1==d2){
now=1;
for(i=2;i<=n;i++)if(a[i]-a[i-1]!=d1)ans+=((LL)now*(LL)(now+1)/2),now=1;else now++;
ans+=((LL)now*(LL)(now+1)/2);
printf("%lld\n",ans);
continue;
}
fg=0;
for(i=1;i<=n-1;i++)if(a[i+1]-a[i]!=d2)q[++fg]=i;q[++fg]=n;
for(now=1,i=1;i<=n;i++){
while(i>q[now])now++;
t1[i]=q[now];
}
fg=0;
for(i=n;i>=2;i--)if(a[i]-a[i-1]!=d1)q[++fg]=i;q[++fg]=1;
for(now=1,i=n;i>=1;i--){
while(i<q[now])now++;
t2[i]=q[now];
}
for(i=1;i<=n;i++)ans+=((LL)(i-t2[i]+1)*(LL)(t1[i]-i+1));
printf("%I64d\n",ans);
}
}
LL po,ans;bool flag,jj,jk,v[N];
int T,n,m,x,i,j,pp,to[N],a[N][N],now[N];
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
po=1;pp=0;jj=0;
for(i=1;i<=n;i++)to[i]=i,po=po*i%MOD;
for(i=1;i<=m;i++){
scanf("%d",&a[i][1]);
if(a[i][1]==-1)pp++;else{
CL(v);jk=0;v[a[i][1]]=1;
for(j=2;j<=n;j++)scanf("%d",&a[i][j]),v[a[i][j]]=1;
for(j=1;j<=n;j++)if(!v[j])jk=1;
if(jk)jj=1;
}
}
if(jj){puts("0");continue;}
if(!pp){
for(i=m;i;i--){
for(j=1;j<=n;j++)now[a[i][j]]=to[i];
for(j=1;j<=n;j++)to[i]=now[i];
}
for(i=1;i<=n;i++)if(to[i]!=i)break;
if(i<=n){puts("0");continue;}
}
ans=1;
for(i=1;i<pp;i++)ans=ans*po%MOD;
printf("%I64d\n",ans);
}
}
int T,n,m,x,y,i,j,tot,nx,ny,sum,a[N][N];bool flag;
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
sum=0;flag=0;
for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&a[i][j]),sum+=a[i][j];
if(n%2==0&&m%2==0){
nx=1;ny=2;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if((i+j)%2==1){
if(a[i][j]<a[nx][ny])nx=i,ny=j;
}
printf("%d\n",sum-a[nx][ny]);
for(i=1;i<=m/2;i++){
if(ny==i*2||ny==i*2-1){
flag=1;
for(j=1;j<nx;j++){
if(j%2==1)printf("RD");
else printf("LD");
}
if(nx!=n)printf("D");
for(j=nx+1;j<n;j++){
if(j%2==1)printf("LD");
else printf("RD");
}
if(nx!=n)printf("R");
}else{
for(j=1;j<n;j++)if(flag)printf("U");else printf("D");
printf("R");
for(j=1;j<n;j++)if(flag)printf("D");else printf("U");
}
if(i!=m/2)printf("R");
}
}else{
printf("%d\n",sum);
if(n%2==1){
for(i=1;i<=n/2;i++){
for(j=1;j<m;j++)printf("R");
printf("D");
for(j=1;j<m;j++)printf("L");
printf("D");
}
for(i=1;i<m;i++)printf("R");
}else{
for(i=1;i<=m/2;i++){
for(j=1;j<n;j++)printf("D");
printf("R");
for(j=1;j<n;j++)printf("U");
printf("R");
}
for(i=1;i<n;i++)printf("D");
}
}
puts("");
}
}
2015 Multi-University Training Contest 10
最后一场多校了哈哈，这回估计又要滚出100名啦
开场就发现T7是一道裸题+原题，就去网上找，找了一个改好交上去，但怎么改也改不对，要不然WA要不然TLE，不过毛主力已经爆了20多发了，才爆了不到10发的我还是很自豪的
差不多爆了20多分钟，终于弃疗了。。然后看T5，马上就秒了
然后又继续摞T7，又摞了20多分钟，还是没摞出来，这时主力队已经6题领板了
然后就摞T11，想了一会还是想出来了，然后写出来A了
然后我就开始颓，颓了1个多小时
YY大爷走了进来，看了T9，说这不是傻逼题吗，然后他马上就秒了，跪跪跪！
然后继续弄想了很久没想出来的T2，受到了数国队的启发，去oeis网站输入了数列，马上就得到要求的是LCM{1,2,...,n}/n，马上就会了，但还是因为没取模爆了两发OJ
然后就弄T6，虽然看了好久没看懂，但猜一猜总是矩阵之类的，就写了一发乱搞的，乱改一会就过了样例，交一发竟然A啦
又颓了一会，最后半小时才开始摞T1，但是到最后由于太弱也没有摞出来。。这场竟然没有掉出100名，真是可喜可贺
int T,n,m,x,y,i,j,tot,a,b,w,dp[N];
int main(){
scanf("%d",&T);
while(T--){
CL(dp);
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++){
scanf("%d%d%d",&w,&a,&b);
for(j=m;j>=w;j--)dp[j]=max(dp[j],dp[j-w]+a+b);
for(j=w;j<=m;j++)dp[j]=max(dp[j],dp[j-w]+a);
}
printf("%d\n",dp[m]);
}
}
void dfs(int x,int fa){
for(int i=fir[x];i;i=ne[i]){
int y=la[i];
if(y!=fa){
sum[y]=sum[x]^va[i];
dfs(y,x);
}
}
}
int main(){
scanf("%d",&T);
while(T--){
CL(fir);tot=0;CL(cnt);CL(sum);
scanf("%d",&n);
for(i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),ins(x,y,z),ins(y,x,z);
dfs(1,0);
for(i=1;i<=n;i++)cnt[sum[i]]++;
scanf("%d",&Q);
while(Q--){
scanf("%d",&x);ans=0;
for(i=1;i<=n;i++)ans+=(LL)cnt[x^sum[i]];
if(!x)ans+=n;
printf("%I64d\n",ans/2);
}
}
}
LL T,p,i,j,n,w,prime[N];
bool f[N];LL ans,now,x,y;
void gprime(){
w=1000000;
for(i=2;i<=w;i++){
if(!f[i])prime[++p]=i;
for(j=1;j<=p&&i*prime[j]<=w;j++){
f[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
LL pow(LL a,LL b,LL p){LL sum=1;for(a%=p;b;a=a*a%p,b>>=1)if(b&1)sum=sum*a%p;return sum;}
void exgcd(LL a,LL b,LL &x,LL &y){if(!b){x=1;y=0;return;}exgcd(b,a%b,y,x);y-=x*(a/b);}
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
char ch;void read(int &x){for(ch=getchar();ch<'0';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
int main(){
scanf("%I64d",&T);
gprime();
while(T--){
scanf("%I64d",&n);n++;
ans=1ll;
for(i=1;i<=p;i++)if(prime[i]<=n)ans=ans*pow(prime[i],floor(log(n)/log(prime[i])),MOD)%MOD;
else break;
exgcd(n,MOD,x,y);if(x<0)x+=MOD;
printf("%I64d\n",ans*x%MOD);
}
}
struct JZ{int x,y,m[N][N];}ans,now;JZ cheng(JZ a,JZ b){JZ c;memset(c.m,0,sizeof c.m);c.x=a.x;c.y=b.y;for(int i=1;i<=a.x;i++)for(int j=1;j<=b.y;j++)for(int k=1;k<=a.y;k++)c.m[i][j]=(c.m[i][j]+(a.m[i][k]%MOD)*(b.m[k][j]%MOD))%MOD;return c;}
int T,n,m,x,y,i,j,k,sum;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);m--;
memset(now.m,0,sizeof now.m);
memset(ans.m,0,sizeof ans.m);
for(i=1;i<=n;i++){
scanf("%d",&k);
for(j=1;j<=k;j++)scanf("%d",&x),now.m[i][x]=1;
}
n++;for(i=1;i<=n;i++)now.m[i][n]=1;
for(i=1;i<=n;i++)ans.m[i][i]=1;
ans.x=ans.y=now.x=now.y=n;
for(;m;m>>=1){
if(m&1)ans=cheng(ans,now);
now=cheng(now,now);
}
sum=0;
for(i=1;i<=n;i++)for(j=1;j<=n;j++)sum=(sum+ans.m[i][j])%MOD;
printf("%d\n",sum);
}
}
2015年8月05日 10:05
为什么你一定要打肏而不是艹呢，多不文雅
2015年8月13日 16:49
"我12:57还在校门外溜达，发现了以后赶紧往机房跑，差不多十二点多几秒跑到了机房"
膜能逆着时间走的李泊宁大爷
2022年8月08日 19:23
Netflix has become one of the world’s largest streaming services. It is an absolute beast when it comes to providing some of the best streaming TV series and movies online. The reason it has become such a huge trend and hype is due to growth in the modern gadgets and better Internet all across the world. How to Cancel Netflix But at the same time people have made a change in the
2022年10月03日 16:59
Rajasthan Board Model Paper 2023 Pdf Download for School Education Ajmer & Jaipur Board Sample Model Question Paper for Class 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 & 12 Standard Theory, Objective (MCQ) and Bit Questions for Hindi Medium, English Medium, Urdu Medium and others. New Exam Scheme orRajasthan Board Model Paper Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.
2023年3月11日 16:37
敬啟者：個人小網站希望大家多多支持 感謝您對我們熱心的支持 f88tw｜華歌爾｜I appreciate your kind assistance.
https://mypaper.pchome.com.tw/f88tw
f88tw|修墳|修墓|新竹|桃園|苗栗|撿骨|拾骨|發票
https://mypaper.pchome.com.tw/f88tw/post/1370781143
https://mypaper.m.pchome.com.tw/f88tw/post/1370781143