P1006：真不会线段树，更不会带LAZY的线段树。
思想就是延迟标记
#include<stdio.h> #include<algorithm> #include<string.h> #include<math.h> #include<iostream> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define N 111111 typedef long long ll; ll a[N*4],add[N*4]; int n; int gcd(int a,int b) { if (a%b==0) return b; return gcd(b,a%b); } void build(int l,int r,int rt) { add[rt]=0; if (l==r) { scanf("%d",&a[rt]); return; } int m=(l+r)>>1; build(lson); build(rson); } void pushdown(int rt) { if (add[rt]) { add[rt<<1]=add[rt<<1|1]=add[rt]; a[rt<<1]=a[rt<<1|1]=a[rt]; add[rt]=0; } } void update1(int L,int R,int l,int r,int rt,int x) { if (L<=l&&R>=r) { add[rt]=1; a[rt]=x; return; } pushdown(rt); int m=(l+r)>>1; if (L<=m) update1(L,R,lson,x); if (R>m) update1(L,R,rson,x); } void update2(int L,int R,int l,int r,int rt,int x) { if (add[rt]&&L<=l&&R>=r) { if (a[rt]>x) a[rt]=gcd(a[rt],x); return; } if (l==r) { if (a[rt]>x) a[rt]=gcd(a[rt],x); return ; } pushdown(rt); int m=(l+r)>>1; if (L<=m) update2(L,R,lson,x); if (R>m) update2(L,R,rson,x); } int query(int x,int l,int r,int rt) { if (l==r) return a[rt]; int m=(l+r)>>1; pushdown(rt); if (x<=m) return query(x,lson); else if (x>m) return query(x,rson); } int main() { int T; scanf("%d",&T); while (T--){ scanf("%d",&n); build(1,n,1); int Q; scanf("%d",&Q); while (Q--) { int t,l,r,x; scanf("%d%d%d%d",&t,&l,&r,&x); if (t==1) update1(l,r,1,n,1,x); else update2(l,r,1,n,1,x); } for (int i=1;i<=n;i++) printf("%d ",query(i,1,n,1)); printf(" "); } return 0; }
P1005:状态DP一直没调出来，
原来方程里有个MOD操作，然后相减时出现负的，尼玛快疯了。
#include<stdio.h> #include<algorithm> #include<string.h> #include<math.h> typedef long long ll; using namespace std; #define mod 1000000007 ll l[1234][1124],r[1234][1124]; int a[1234]; int n; int main() { int T; scanf("%d",&T); while (T--) { scanf("%d",&n); memset(l,0,sizeof(l)); memset(r,0,sizeof(r)); for (int i=1;i<=n;i++) scanf("%d",&a[i]);//分别左右两边记录状态 for (int i=n;i>=1;i--) { r[i][a[i]]++; for (int j=0;j<1024;j++) if (r[i+1][j]) { r[i][j]+=r[i+1][j]; if (r[i][j]>mod) r[i][j]-=mod; r[i][j&a[i]]+=r[i+1][j]; if (r[i][j&a[i]]>mod) r[i][j&a[i]]-=mod; } } for (int i=1;i<=n;i++) { l[i][a[i]]++; for (int j=0;j<1024;j++) if (l[i-1][j]) { l[i][j]+=l[i-1][j]; if (l[i][j]>mod) l[i][j]-=mod; l[i][j^a[i]]+=l[i-1][j]; if (l[i][j^a[i]]>mod) l[i][j^a[i]]-=mod; } } ll ans=0; for (int i=1;i<n;i++) for (int j=0;j<1024;j++) { ll ok=l[i][j]-l[i-1][j];//最重要的一步，确保第I个已经选择了，然后去和右边的搭配 if (ok<0) ok+=mod; if () ok=ok*r[i+1][j]%mod; ans+=ok; if (ans>mod) ans-=mod; } printf("%I64d ",ans); } }