3166: [Heoi2013]Alo
这题大意是给你一个序列，求一个最优区间[l,r],使其中的次大值xor上区间中任意另一个数，使xor和最大（对不起，我又语死了）
这题其实暴力能a= =
但是写暴力太没节操了（- -b）
网上似乎没有除暴力以外的题解= =我来写一篇吧= =
我的大致想法就是用线段树维护i前面第二个比他大的值f[i]（这里可以用权值线段树），然后用函数式trie找(f[i]+1,i)上与a[i]的最大xor。。
貌似很基础的样子= =也很暴力= =
有更优解请告诉我= =
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3000010;
struct re{
int l,r,lc,rc,ms,mf;
} t[N];
int root[N],col[N],a[N],b[N],c[N],d[N];
int tr[N][2];
int n,sum=0,num=0,tot=0,ans=0;
inline void inse(int pp,int i,int x){
root[i]=++sum;
int pos=root[i];
col[pos]=i;
for (int j=30;j>=0;j--){
int y=(x>>j)&1;
tr[pos][y^1]=tr[pp][y^1];
tr[pos][y]=++sum;
col[sum]=i;
pos=tr[pos][y];
pp=tr[pp][y];
}
}
inline int ques(int l,int r,int x){
int pos=root[r];
int ans=0;
for (int j=30;j>=0;j--){
int z=(x>>j)&1;
if (col[tr[pos][z^1]]>=l){
ans+=1<<j;
pos=tr[pos][z^1];
}else pos=tr[pos][z];
}
return ans;
}
inline int buildtree(int l,int r){
int x=++num;
t[x].l=l;
t[x].r=r;
t[x].mf=t[x].ms=0;
if (l==r){
t[x].lc=t[x].rc=0;
return x;
}
int mm=(l+r)/2;
t[x].lc=buildtree(l,mm);
t[x].rc=buildtree(mm+1,r);
return x;
}
inline void renew(int c,int x){
if (t[x].mf<c){
t[x].ms=t[x].mf;
t[x].mf=c;
return;
}
if (t[x].mf==c) return;
if (t[x].ms<c) t[x].ms=c;
}
inline void down(int x){
int l=t[x].lc,r=t[x].rc;
renew(t[x].ms,l);
renew(t[x].mf,l);
renew(t[x].ms,r);
renew(t[x].mf,r);
}
inline int query(int x,int pos){
if (t[x].l==t[x].r) return t[x].ms;
down(x);
int mm=(t[x].l+t[x].r)/2;
if (pos<=mm) return query(t[x].lc,pos);
return query(t[x].rc,pos);
}
inline void add(int x,int l,int r,int c){
if (t[x].l==0) return;
if (l<=t[x].l&&t[x].r<=r){
t[x].ms=t[x].mf;
t[x].mf=c;
return;
}
down(x);
int mm=(t[x].l+t[x].r)/2;
if (l<=mm) add(t[x].lc,l,r,c);
if (mm<r) add(t[x].rc,l,r,c);
}
inline void calc(){
memset(col,0,sizeof(col));
memset(tr,0,sizeof(tr));
sum=0; tot=0;
inse(0,0,0);
for (int i=1;i<=n;i++){
b[++tot]=a[i];
inse(root[i-1],i,a[i]);
}
std::sort(b+1,b+n+1);
for (int i=1;i<=n;i++){
c[i]=lower_bound(b+1,b+n+1,a[i])-b;
}
num=0;
int ro=buildtree(1,n);
for (int i=1;i<=n;i++){
int x;
x=query(ro,c[i]);
x++;
ans=max(ans,ques(x,i,a[i]));
if (c[i]>1) add(ro,1,c[i]-1,i);
}
}
inline void read(int &T){
int ch=getchar();
while (ch<'0'||ch>'9'){
ch=getchar();
}
T=0;
while (ch>='0'&&ch<='9'){
T=T*10+ch-'0';
ch=getchar();
}
}
int main(){
scanf("%d",&n);
num=0;
for (int i=1;i<=n;i++){
scanf("%d",&d[i]);
a[i]=d[i];
}
calc();
for (int i=1;i<=n;i++) a[i]=d[n-i+1];
calc();
printf("%d\n",ans);
}
poi2012 Tour de Byteotia
一眼题，不解释。。
#include<cstdio>
int n,m,k,ans=0;
int fa[1000001];
struct re{
int u,v;
} a[2000001];
re b[2000001];
int getfa(int x){return fa[x]==x? x:fa[x]=getfa(fa[x]);}
int main(){
//freopen("tou1a.in","r",stdin);
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=n;i++) fa[i]=i;
for (int i=1;i<=m;i++){
scanf("%d%d",&a[i].u,&a[i].v);
if (a[i].u<=k||a[i].v<=k) continue;
int fx=getfa(a[i].u);
int fy=getfa(a[i].v);
if (fx!=fy){
fa[fx]=fy;
}
}
for (int i=1;i<=m;i++){
if (a[i].u>k&&a[i].v>k) continue;
int fx=getfa(a[i].u);
int fy=getfa(a[i].v);
if (fx==fy){
ans++;
b[ans].u=a[i].u;
b[ans].v=a[i].v;
}
else fa[fx]=fy;
}
printf("%d\n",ans);
for (int i=1;i<=ans;i++) printf("%d %d\n",b[i].u,b[i].v);
}
poi2012 well
二分答案+单调队列。。main过了，bzoj无限tle。。。
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int q[1000011];
int n,maxi=0;
int ansx,ansk;
ll m;
int a[1000011];
ll sum[1000011];
ll c[1000011],f[1000011],fr[1000011],fl[1000011],g[1000011];
inline ll min(ll a,ll b){return a<b? a:b;}
inline bool check(int xx){
ll x=xx;
int h=0,t=1;
c[1]=a[1];
q[t]=1;
f[1]=0;
sum[1]=a[1];
for (int i=2;i<=n;i++){
sum[i]=sum[i-1]+a[i];
c[i]=min(c[i-1]+x,a[i]);
while (h<t&&c[q[t]]+x*q[t]>=c[i]+x*i) t--;
int j=q[t];
//printf("i=%d j=%d\n",i,j);
if (h==t){ f[i]=sum[i]-(c[i]+c[i]+(i-1)*x)*i/2;}
else { f[i]=sum[i]-sum[j]-(c[i]+c[i]+(i-j-1)*x)*(i-j)/2+f[j];}
q[++t]=i;
}
//for (int i=1;i<=n;i++) printf("f[%d]=%I64d ",i,f[i]);
//printf("\n");
//for (int i=1;i<=n;i++) printf("c[%d]=%I64d\n",i,c[i]);
h=0; t=1; q[1]=1; fl[1]=a[1];
for (int i=2;i<=n;i++){
while (h+1<t&&c[q[h+2]]+q[h+2]*x<=i*x) h++;
int j=q[h+1];
if (c[q[h+1]]+q[h+1]*x>i*x){fl[i]=sum[i]-(i-1)*x*i/2;}
else {fl[i]=sum[i]-sum[j]-(i-j-1)*x*(i-j)/2+f[j];}
while (h<t&&c[q[t]]+q[t]*x>=c[i]+i*x) t--;
q[++t]=i;
}
//for (int i=1;i<=n;i++) printf("fl[%d]=%I64d ",i,fl[i]);
//printf("\n");
h=0; t=1; c[n]=a[n]; q[t]=n; g[n]=0;
sum[n]=a[n];
for (int i=n-1;i>=1;i--){
sum[i]=sum[i+1]+a[i];
c[i]=min(c[i+1]+x,a[i]);
while (h<t&&c[q[t]]-x*q[t]>=c[i]-x*i) t--;
int j=q[t];
if (h==t){ g[i]=sum[i]-(c[i]+c[i]+(n-i)*x)*(n-i+1)/2;}
else { g[i]=sum[i]-sum[j]-(c[i]+c[i]+(j-i-1)*x)*(j-i)/2+g[j];}
q[++t]=i;
}
//for (int i=1;i<=n;i++) printf("g[%d]=%I64d ",i,g[i]);
//printf("\n");
h=0; t=1; q[1]=n; fr[n]=a[n];
ll ans=fr[n]+fl[n]-a[n];
for (int i=n-1;i>=1;i--){
while (h+1<t&&c[q[h+2]]-q[h+2]*x<=-i*x) h++;
int j=q[h+1];
if (c[q[h+1]]-q[h+1]*x>-i*x){fr[i]=sum[i]-(n-i)*x*(n-i+1)/2;}
else {fr[i]=sum[i]-sum[j]-(j-i-1)*x*(j-i)/2+g[j];}
while (h<t&&c[q[t]]-q[t]*x>=c[i]-i*x) t--;
q[++t]=i;
ans=min(ans,fl[i]+fr[i]-a[i]);
}
//printf("ans=%I64d\n",ans);
if (ans>m) return false;
if (x<ansx){
ansx=x;
for (int i=1;i<=n;i++){
if (fr[i]+fl[i]-a[i]<=m){
ansk=i;
break;
}
}
}
return true;
}
inline void half(int l,int r){
while (l!=r){
int mm=(l+r)/2;
//printf("%I64d\n",mm);
if (check(mm)) r=mm;
else l=mm+1;
}
}
int main(){
//freopen("stu.in","r",stdin);
//freopen("stu.out","w",stdout);
scanf("%d%lld",&n,&m);
ansx=1000000000; ansk=1000000000;
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
maxi=max(maxi,a[i]);
}
//printf("%d\n",maxi);
if (maxi>20000000) maxi=20000000;
half(0,maxi+1);
if (ansx==1000000000) half(20000001,100000000);
printf("%d %d\n",ansk,ansx);
//printf("%d\n",check(1076));
}
poi2012 rendezvous
基圈上的外向树求lca。。。先预处理所有的环长，以及外向树内的lca，对每个询问，在一棵树上就直接求，在一个环上就先到根，再判断从哪个方向走，如果不在一个环上输出-1 -1。。。
另：lca不知哪写错了，求大神查错。。。
#include<cstdio>
#include<cmath>
#include<cstring>
int can[500001];
int ansx=0,ansy=0,n,p=0,ss=0,m,sum=0;
int d[500001],pos[500001],fa[500001];
int f[500001][20],root[500001];
int dis[500001],kind[500001],head[500001],next[1000001];
struct re{
int u,v;
} a[1000001];
inline int max(int a,int b){return a>b? a:b;}
inline int min(int a,int b){return a<b? a:b;}
void getlca(int x,int y){
ansx=0; ansy=0;
if (x==y) return;
//printf("fu\n");
if (dis[x]>dis[y]){
int xx=dis[x]-dis[y];
ansx=xx;
int k=int(log2(n));
while (k>=0){
if (xx>=(1<<k)){
x=f[x][k];
xx-=(1<<k);
}
k--;
}
}else{
int xx=dis[y]-dis[x];
ansy=xx;
//printf("%d\n",xx);
int k=int(log2(n));
while (k>=0){
if (xx>=(1<<k)){
y=f[y][k];
xx-=1<<k;
}
k--;
}
}
//printf("f2\n");
if (x==y) return;
//printf("ansx=%d ansy=%d\n",ansx,ansy);
//printf("x\n");
int k=int(log2(n));
while (k>=0){
//printf("%d %d %d %d %d\n",k,ansx,ansy,f[x][k],f[y][k]);
if (f[x][k]!=f[y][k]&&f[x][k]!=0&&f[y][k]!=0){
ansx+=1<<k; ansy+=1<<k;
x=f[x][k]; y=f[y][k];
}
k--;
}
ansx++; ansy++;
}
void get(int x,int y){
if (root[x]==root[y]){
//printf("e\n");
getlca(x,y);
return;
}
if (kind[root[x]]!=kind[root[y]]) return;
ansx=dis[x]; ansy=dis[y];
x=root[x]; y=root[y];
int t=kind[x];
int len=d[t];
int lx=pos[y]-pos[x];
if (lx<0) lx+=len;
int rx=pos[x]-pos[y];
if (rx<0) rx+=len;
//printf("len=%d px=%d py=%d\n",len,pos[x],pos[y]);
//printf("ax=%d ay=%d tx=%d ty=%d\n",ansx,ansy,lx,rx);
if (max(lx+ansx,ansy)<max(ansx,rx+ansy)){
//printf("a1\n");
ansx+=lx;
return;
}
if (max(lx+ansx,ansy)>max(ansx,rx+ansy)){
//printf("a2\n");
ansy+=rx;
return;
}
//printf("f1 %d %d\n",ansx,rx+ansy);
//printf("f2 %d %d\n",ansx+lx,ansy);
if (min(lx+ansx,ansy)<min(ansx,rx+ansy)){
//printf("b1\n");
ansx+=lx;
return;
}
if (min(lx+ansx,ansy)>min(ansx,rx+ansy)){
//printf("b2\n");
ansy+=rx;
return;
}
//printf("s\n");
ansx+=lx;
}
void done(int i){
root[i]=i;
kind[i]=++ss;
d[ss]++;
pos[i]=++p;
int j=fa[i];
while (j!=i){
//printf("j=%d %d\n",j,i);
root[j]=j;
kind[j]=ss;
d[ss]++;
pos[j]=++p;
j=fa[j];
}
}
void dfs(int i,int x){
can[i]=x;
int k=fa[i];
if (can[k]==x){
done(k);
return;
}
if (can[k]) return;
can[k]=x;
dfs(k,x);
}
void dfs2(int i){
can[i]=1;
//printf("ii=%d\n",i);
int x=int(log2(n));
f[i][0]=fa[i];
for (int j=1;j<=x;j++){
f[i][j]=f[f[i][j-1]][j-1];
}
for (int j=head[i];j;j=next[j]){
int k=a[j].v;
if (root[k]||can[k]) continue;
root[k]=root[i];
dis[k]=dis[i]+1;
dfs2(k);
}
}
void build(int u,int v){
a[++sum].u=u;
a[sum].v=v;
next[sum]=head[u];
head[u]=sum;
}
int main(){
//freopen("ran3c.in","r",stdin);
//freopen("ran.out","w",stdout);
scanf("%d%d",&n,&m);
int x,y;
for (int i=1;i<=n;i++){
scanf("%d",&x);
build(x,i); build(i,x);
fa[i]=x;
}
for (int i=1;i<=n;i++){
if (!can[i]) dfs(i,i);
//printf("%d\n",can[i]);
}
//printf("d\n");
memset(can,0,sizeof(can));
for (int i=1;i<=n;i++){
if (root[i]) dfs2(i);
}
//for (int i=1;i<=n;i++) printf("i=%d root=%d dis=%d pos=%d kind=%d\n",i,root[i],dis[i],pos[i],kind[i]);
for (int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
ansx=-1; ansy=-1;
get(x,y);
printf("%d %d\n",ansx,ansy);
}
}
poi2012 festival
强连通分量+最长路
#include<cstdio>
#include<cstring>
const int maxi=100000000;
int ft[610][610];
bool f[100001],can[100001];
int head[100001],next[200001],d[100001];
int dfn[100001],low[100001],sta[100001],g[100001];
int top=0,s=0,sum=0,ss=0,n,m1,m2,ans=0;
struct re{
int u,v,w;
} a[200001];
inline int min(int a,int b){return a<b? a:b;}
inline int max(int a,int b){return a>b? a:b;}
inline int abs(int x){return x>=0? x:-x;}
void done(int i){
++s;
while (sta[top]!=i){
g[sta[top]]=s;
can[sta[top]]=false;
top--;
}
g[i]=s;
can[i]=false;
top--;
}
void dfs(int i){
dfn[i]=low[i]=++ss;
sta[++top]=i;
f[i]=false;
for (int j=head[i];j;j=next[j]){
int k=a[j].v;
if (can[k]){
if (f[k]) dfs(k);
low[i]=min(low[i],min(low[k],dfn[k]));
}
}
if (low[i]==dfn[i]) done(i);
}
void build(int u,int v,int w){
a[++sum].u=u;
a[sum].v=v;
a[sum].w=w;
next[sum]=head[u];
head[u]=sum;
}
int main(){
//freopen("fes11a.in","r",stdin);
scanf("%d%d%d",&n,&m1,&m2);
int u,v;
for (int i=1;i<=m1;i++){
scanf("%d%d",&u,&v);
build(v,u,1);
build(u,v,-1);
}
for (int i=1;i<=m2;i++){
scanf("%d%d",&u,&v);
build(v,u,0);
}
memset(f,true,sizeof(f));
memset(can,true,sizeof(can));
for (int i=1;i<=n;i++){
if (f[i])dfs(i);
}
//for (int i=1;i<=n;i++) printf("g[%d]=%d\n",i,g[i]);
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
ft[i][j]=-maxi;
}
}
//printf("%d\n",ft[1][1]);
for (int i=1;i<=n;i++) ft[i][i]=0;
for (int i=1;i<=sum;i++){
if (g[a[i].u]==g[a[i].v]){
ft[a[i].u][a[i].v]=max(ft[a[i].u][a[i].v],a[i].w);
}
}
/*for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
printf("f[%d][%d]=%d ",i,j,ft[i][j]);
}
printf("\n");
}*/
for (int k=1;k<=n;k++){
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
//if (i==j) printf("i=%d j=%d k=%d f2=%d f3=%d\n",i,j,k,ft[i][k],ft[k][j]);
ft[i][j]=max(ft[i][j],ft[i][k]+ft[k][j]);
}
}
}
/*for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
printf("f[%d][%d]=%d ",i,j,ft[i][j]);
}
printf("\n");
}*/
for (int i=1;i<=n;i++){
if (ft[i][i]>0){
printf("NIE\n");
return 0;
}
}
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
if (g[i]==g[j]) d[g[i]]=max(d[g[i]],abs(ft[i][j]));
}
}
for (int i=1;i<=s;i++){
ans+=d[i]+1;
}
printf("%d\n",ans);
}
poi2012 distance
暴力水过。。就是d(a,b)=c[a]+c[b]-c[gcd(a,b)];c[i]表示i的质因子数。然后对每个a[i]暴力枚举gcd(),求一个b使c[a]+c[b]-2*c[gcd()]最小。。这个可以预处理后O(1)解决。。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxi=1000000000;
int n,m=0,tot=0;
bool ss[1000051];
int prime[1000051];
int f[1000051],g[1000051];
int a[1000051],c[1000051];
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
m=max(m,a[i]);
}
memset(ss,true,sizeof(ss));
for (int i=2;i<=m;i++){
if (ss[i]){
prime[++tot]=i;
c[i]=1;
}
for (int j=1;j<=tot&&prime[j]*i<=m;j++){
int k=i*prime[j];
ss[k]=false;
c[k]=c[i]+1;
if (i%prime[j]==0) break;
}
}
//for (int i=1;i<=tot;i++) printf("prime[%d]=%d\n",i,prime[i]);
//for (int i=1;i<=m;i++) printf("c[%d]=%d\n",i,c[i]);
c[0]=maxi;
for (int i=1;i<=n;i++){
for (int j=1;j*j<=a[i];j++){
if (a[i]%j!=0) continue;
int k=a[i]/j;
//printf("i=%d j=%d k=%d\n",i,j,k);
if (c[a[i]]<c[a[f[j]]]){g[j]=f[j]; f[j]=i;}
else if (c[a[i]]<c[a[g[j]]]) g[j]=i;
//printf("g=%d f=%d\n",g[j],f[j]);
if (j==k) continue;
if (c[a[i]]<c[a[f[k]]]){g[k]=f[k]; f[k]=i;}
else if (c[a[i]]<c[a[g[k]]]) g[k]=i;
}
//if (i%10000==0) printf("i=%d\n",i);
}
//for (int i=1;i<=m;i++) printf("i=%d f=%d g=%d\n",i,f[i],g[i]);
for (int i=1;i<=n;i++){
int h=maxi,d=0;
for (int j=1;j*j<=a[i];j++){
if (a[i]%j!=0) continue;
int k=a[i]/j,x;
if (f[j]==i) x=g[j];
else x=f[j];
//printf("i=%d x=%d j=%d k=%d h=%d\n",i,x,j,k,h[i]);
if (h>c[a[i]]+c[a[x]]-2*c[j]||(h==c[a[i]]+c[a[x]]-2*c[j]&&x<d)){
h=c[a[i]]+c[a[x]]-2*c[j];
d=x;
}
if (j==k) continue;
if (f[k]==i) x=g[k];
else x=f[k];
if (h>c[a[i]]+c[a[x]]-2*c[k]||(h==c[a[i]]+c[a[x]]-2*c[k]&&x<d)){
h=c[a[i]]+c[a[x]]-2*c[k];
d=x;
}
}
//if (i%10000==0) printf("%d\n",i);
printf("%d\n",d);
}
}
1109: [POI2007]堆积木Klo
树状数组维护序列，使{a[i]-i}不增，且{a[i]}递增。。。
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxi=~0u>>1;
int n,ans(0);
int f[200001],t[1000001];
struct re{
int n,h;
}a[200001];
int lowbit(int x){return x&(-x);}
bool cmp(re a,re b){return a.n==b.n? a.h<b.h:a.n>b.n;}
void change(int x,int c){
while (x<=n){
t[x]=max(t[x],c);
//printf("x=%d t[x]=%d\n",x,t[x]);
x+=lowbit(x);
}
}
int ques(int x){
int ans=0;
while (x){
ans=max(ans,t[x]);
//printf("%d t[x]=%d\n",x,t[x]);
x-=lowbit(x);
}
//printf("ans=%d\n",ans);
return ans;
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d",&a[i].h);
a[i].n=a[i].h-i;
//printf("a[%d]=%d\n",i,a[i].n);
}
sort(a+1,a+n+1,cmp);
for (int i=1;i<=n;i++){
//printf("i=%d n=%d h=%d\n",i,a[i].n,a[i].h);
if (a[i].n>0) continue;
int x;
if (a[i].h-1>0){
//printf("%d\n",a[i].h);
x=ques(a[i].h-1);
}else x=0;
//printf("x=%d\n",x);
f[i]=x+1;
//printf("f=%d\n",f[i]);
ans=max(ans,f[i]);
//printf("f[%d]=%d\n",i,f[i]);
change(a[i].h,f[i]);
}
printf("%d\n",ans);
}
2213: [Poi2011]Difference
裸扫一遍。。记下状态。注意一段中没有一个字母就不能算他为出现最少的字母= =！
#include<cstdio>
int n,ans=0;
char st[1000002];
int f[41][41],g[41][41];
int max(int a,int b){return a>b? a:b;}
int main(){
scanf("%d",&n);
scanf("%s",st);
for (int i=0;i<n;i++){
int y=st[i]-'a';
for (int j=0;j<26;j++){
f[j][y]++;
f[y][j]--;
if (!g[y][j]) g[y][j]=1;
if (g[y][j]==2){g[y][j]=1;f[y][j]++;}
if (f[y][j]<=-1){f[y][j]=-1;g[y][j]=2;}
if (g[y][j]) ans=max(ans,f[y][j]);
if (g[j][y]) ans=max(ans,f[j][y]);
//printf("f[%c][%c]=%d f[%c][%c]=%d ",j+'a',y+'a',f[j][y],y+'a',j+'a',f[y][j]);
}
//printf("\n");
}
printf("%d\n",ans);
}
两道水
2793: [Poi2012]Vouchers：暴力加小优化，据说是O(mlogm)的。
2091: [Poi2010]The Minima Game：之前做的USACO10的taking turns。。。一样的题额。。
#include<cstdio>
#include<cstring>
typedef long long ll;
int m,n;
ll x,maxi=0,tot=0,sum=0;
ll d[1000001];
ll ans[1000001];
bool c[1000001],f[1000001];
ll max(ll a,ll b){return a>b? a:b;}
int main(){
scanf("%d",&m);
memset(f,true,sizeof(f));
for (int i=1;i<=m;i++){
scanf("%lld",&x);
c[x]=true;
maxi=max(maxi,x);
}
scanf("%d",&n);
for (int i=1;i<=maxi;i++){
d[i]=i;
}
for (int i=1;i<=n;i++){
scanf("%lld",&x);
int s=x;
long long y=d[x];
while (s){
if (y>maxi) break;
if (f[y]){
tot++;
d[x]=y;
f[y]=false;
//printf("y=%d\n",y);
if (c[y]) ans[++sum]=tot;
s--;
}
y+=x;
}
//printf("s=%d tot=%d\n",s,tot);
tot+=s;
}
printf("%lld\n",sum);
for (int i=1;i<=sum;i++){
printf("%lld\n",ans[i]);
}
}
1510: [POI2006]Kra-The Disks
水题一道不解释，前缀和暴力裸过。。就是不知为什么，poi原数据我总有一个跑不对= =。详见程序