今天被高一狂踩,两个手抖,t1一个1写成2,t3一个+=写成=,所谓失之毫厘谬以千里,直接丢了50分。
完全背包
看到背包体积如此之大物品体积如此之小容易很想到贪心,肯定要先加很多很多的性价比最高的最后一部分再背包处理。
具体到底要加到多少随便估计一下都能过,我非常暴力地把1~100跟其他所有数取lcm再取最大值也就4.8e5的样子,5e5的背包都跑得飞快。
而数据似乎很水有人只跑了100的背包都过了。。。
题解证明出了更小的限制,最多跑100*100的背包就够了
1 //Achen 2 #include3 #define For(i,a,b) for(int i=(a);i<=(b);i++) 4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--) 5 #define Formylove return 0 6 const int N=5e5+7,up=5e5; 7 typedef long long LL; 8 typedef double db; 9 using namespace std;10 int n,v[107],a[N],b[N],tot,sta[107],top;11 LL m,f[N],ans;12 13 template void read(T &x) {14 char ch=getchar(); x=0; T f=1;15 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();16 if(ch=='-') f=-1,ch=getchar();17 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;18 }19 20 #define ANS21 int main() {22 #ifdef ANS23 freopen("backpack.in","r",stdin);24 freopen("backpack.out","w",stdout);25 #endif26 read(n); read(m);27 memset(v,-1,sizeof(v));28 For(i,1,n) {29 int a,b;30 read(a); read(b);31 if(b>v[a]) v[a]=b;32 }33 For(i,1,100) if(v[i]!=-1) {34 a[++tot]=i;35 b[tot]=v[i];36 }37 For(i,1,up) {38 For(j,1,tot) {39 if(i-a[j]<0) break;40 if(f[i-a[j]]+b[j]>f[i]) f[i]=f[i-a[j]]+b[j];41 } 42 }43 int mx=1;44 For(i,2,tot) {45 if(b[i]*a[mx]>b[mx]*a[i]) mx=i;46 }47 For(i,1,tot) {48 if(b[i]*a[mx]==b[mx]*a[i]) sta[++top]=i;49 }50 if(m<=up) ans=f[m];51 else {52 For(i,1,top) {53 for(LL v=m/a[sta[i]]*a[sta[i]];v>=0&&m-v<=up;v-=a[sta[i]]) {54 if(v/a[sta[i]]*b[sta[i]]+f[m-v]>ans) ans=v/a[sta[i]]*b[sta[i]]+f[m-v];55 }56 }57 }58 printf("%lld\n",ans);59 Formylove;60 }
快速排序
数据结构水题。发现取法就是合法的括号序列,第一个答案就是后一半的和-前一半的和,第二个答案就是偶数和-奇数和,第三个答案就是卡特兰数。
1 //Achen 2 #include3 #define For(i,a,b) for(int i=(a);i<=(b);i++) 4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--) 5 #define Formylove return 0 6 const int N=1e6+7,p=1e9+7; 7 typedef long long LL; 8 typedef double db; 9 using namespace std; 10 int n,m,a[N],fac[N],inv[N],invp[N]; 11 12 template void read(T &x) { 13 char ch=getchar(); x=0; T f=1; 14 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); 15 if(ch=='-') f=-1,ch=getchar(); 16 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f; 17 } 18 19 LL mo(LL x) { return x<0?x+p:(x>=p?x-p:x); } 20 21 LL Ct(int n) { 22 return (LL)fac[2*n]*invp[n]%p*invp[n]%p*inv[n+1]%p; 23 } 24 25 int sg[N<<2],sg2[N<<2],lz[N<<2]; 26 #define lc x<<1 27 #define rc ((x<<1)|1) 28 #define mid ((l+r)>>1) 29 void add(int x,int len,LL v) { 30 sg[x]=mo(v*len%p+sg[x]); 31 if(len&1) sg2[x]=mo(v+sg2[x]); 32 lz[x]=mo(v+lz[x]); 33 } 34 35 void down(int x,int l_len,int r_len) { 36 if(!lz[x]) return; 37 add(lc,l_len,lz[x]); 38 add(rc,r_len,lz[x]); 39 lz[x]=0; 40 } 41 42 void upd(int x,int l,int r) { 43 sg[x]=mo((LL)sg[lc]+sg[rc]); 44 if((mid-l+1)&1) sg2[x]=mo((LL)sg2[lc]-sg2[rc]); 45 else sg2[x]=mo((LL)sg2[lc]+sg2[rc]); 46 } 47 48 void build(int x,int l,int r) { 49 if(l==r) { sg[x]=sg2[x]=a[l]; return; } 50 build(lc,l,mid); build(rc,mid+1,r); 51 upd(x,l,r); 52 } 53 54 void update(int x,int l,int r,int ql,int qr,LL v) { 55 if(l>=ql&&r<=qr) { 56 add(x,r-l+1,v); return; 57 } 58 down(x,mid-l+1,r-mid); 59 if(ql<=mid) update(lc,l,mid,ql,qr,v); 60 if(qr>mid) update(rc,mid+1,r,ql,qr,v); 61 upd(x,l,r); 62 } 63 64 LL qry1(int x,int l,int r,int ql,int qr) { 65 if(l>=ql&&r<=qr) return sg[x]; 66 down(x,mid-l+1,r-mid); 67 if(qr<=mid) return qry1(lc,l,mid,ql,qr); 68 if(ql>mid) return qry1(rc,mid+1,r,ql,qr); 69 return mo(qry1(lc,l,mid,ql,qr)+qry1(rc,mid+1,r,ql,qr)); 70 } 71 72 LL nowans,nowlen; 73 void qry2(int x,int l,int r,int ql,int qr) { 74 if(l>=ql&&r<=qr) { 75 if(nowlen&1) nowans=mo(nowans-sg2[x]); 76 else nowans=mo(nowans+sg2[x]); 77 nowlen+=(r-l+1); 78 return ; 79 } 80 down(x,mid-l+1,r-mid); 81 if(ql<=mid) qry2(lc,l,mid,ql,qr); 82 if(qr>mid) qry2(rc,mid+1,r,ql,qr); 83 } 84 85 86 #define ANS 87 int main() { 88 #ifdef ANS 89 freopen("sort.in","r",stdin); 90 freopen("sort.out","w",stdout); 91 #endif 92 read(n); read(m); 93 For(i,1,n*2) read(a[i]); 94 95 fac[0]=inv[0]=inv[1]=invp[0]=1; 96 For(i,2,n*2) inv[i]=mo(p-(LL)p/i*inv[p%i]%p); 97 For(i,1,n*2) fac[i]=(LL)fac[i-1]*i%p,invp[i]=(LL)invp[i-1]*inv[i]%p; 98 99 build(1,1,n*2);100 101 For(cs,1,m) {102 int o,l,r; LL v;103 read(o); read(l); read(r);104 if(o) {105 LL ans1=mo(qry1(1,1,n*2,l+(r-l)/2+1,r)-qry1(1,1,n*2,l,l+(r-l)/2));106 nowans=nowlen=0; qry2(1,1,n*2,l,r);107 nowans=mo(p-nowans);108 LL ans3=Ct((r-l+1)/2);109 /*if(cs==5) {110 LL tp=0;111 for(int i=l+1;i<=r;i+=2) 112 tp=tp+a[i];113 for(int i=l;i<=r;i+=2) 114 tp=tp-a[i];115 cout< <
数位 DP
f[i][j]表示长度为i的各位之和mod 60=j的数的个数。50分随便dp一下就好了。
发现f[i]仅有f[i-1]转移来,考虑矩阵乘法优化。
题解到这里就完了,我一看,这不是sb题吗,马上敲。
好像不对啊,f[i]确实很好求,但是我要求f[1]~f[i]啊。emmmmm,思考了一下给矩阵对角线上+1,然后发现并不对,这样虽然把i-1的信息加过来了,但是更新i+1的时候就不止i在更新i-1也在更新了。那我矩阵岂不是要开到120*120,时间爆炸了啊。
然后yy了一个转移,相当于每次转移是从1~len转移到1+1~len+1,再加上f[1],就变成1~len+1了,因为f[1]只有两种,60*60的矩阵变成62*62就可以了。
1 //Achen 2 #include3 #define For(i,a,b) for(int i=(a);i<=(b);i++) 4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--) 5 #define Formylove return 0 6 const int p=1e9+7; 7 typedef long long LL; 8 typedef double db; 9 using namespace std;10 LL l,r,k,f[62];11 12 template void read(T &x) {13 char ch=getchar(); x=0; T f=1;14 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();15 if(ch=='-') f=-1,ch=getchar();16 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;17 }18 19 struct jz {20 LL a[62][62];21 friend jz operator *(const jz&A,const jz&B) {22 jz rs;23 For(i,0,61) For(j,0,61) {24 rs.a[i][j]=0;25 For(k,0,61) 26 rs.a[i][j]=(rs.a[i][j]+A.a[i][k]*B.a[k][j]%p)%p;27 }28 return rs;29 }30 }bs,rs,base;31 32 void jzksm(LL b) {33 For(i,0,61) For(j,0,61) {34 if(i==j) rs.a[i][j]=1;35 else rs.a[i][j]=0;36 }37 bs=base;38 while(b) {39 if(b&1) rs=rs*bs;40 bs=bs*bs;41 /*For(i,0,61) {42 For(j,0,61) printf("%lld ",bs.a[i][j]);43 puts("");44 }*/45 b>>=1;46 }47 }48 49 void pre() {50 LL t1=(k-1)/60; t1%=p;51 LL t2=(k-1)%60;52 For(i,0,59) {53 f[i]=t1;54 if(i&&t2>=i) f[i]=(f[i]+1)%p;55 if(f[i]==t1) base.a[60][i]=1;56 else base.a[61][i]=1;57 }58 f[60]=t1; f[61]=(t1+1)%p;59 For(i,0,59) {60 base.a[i][i]=(base.a[i][i]+1)%p;61 For(j,0,59) 62 base.a[i][(i+j)%60]=(base.a[i][(i+j)%60]+f[j])%p;63 }64 base.a[60][60]=1;65 base.a[61][61]=1;66 /*For(i,0,61) {67 For(j,0,61) printf("%lld ",base.a[i][j]);68 puts("");69 }*/70 }71 72 LL F(LL x) {73 if(!x) return 0;74 jzksm(x-1);75 LL res=0;76 For(i,0,59) if(i%4==0||i%5==0||i%6==0) {77 LL x=0;78 For(j,0,61) x=(x+f[j]*rs.a[j][i]%p)%p;79 res=(res+x)%p;80 }81 return res;82 }83 84 #define ANS85 int main() {86 #ifdef ANS87 freopen("digit.in","r",stdin);88 freopen("digit.out","w",stdout);89 #endif90 read(l); read(r); read(k);91 pre();92 printf("%lld\n",(F(r)-F(l-1)+p)%p);93 //cerr< <
---------------------6-22upd-------------------------------
我真是个大sb,60阶矩阵怎么做,直接允许前导0这就是sb题了,一开始我还说这天标准分250,现在看来怕应该是中位数300吧……