A 开个数组记录一下
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<vector> 7 #include<queue> 8 #include<cmath> 9 #include<map> 10 using namespace std; 11 #define LL long long 12 #define INF 1e10 13 #define N 300010 14 LL sum[N]; 15 int a[N]; 16 int pa[N]; 17 map<int,int>f; 18 int main() 19 { 20 int n,i,g=0,x; 21 cin>>n; 22 for(i = 1; i <= n ;i++) 23 { 24 cin>>a[i]; 25 if(a[i]>0) 26 sum[i] = sum[i-1]+a[i]; 27 else 28 sum[i] = sum[i-1]; 29 f[a[i]] = i; 30 } 31 LL maxz=-INF; 32 for(i = 1; i <= n ;i++) 33 { 34 if(i==f[a[i]]) continue; 35 LL s = sum[f[a[i]]]-sum[i-1]; 36 if(a[i]<0) s+=2*a[i]; 37 if(maxz<s) 38 { 39 x = i; 40 maxz = s; 41 } 42 } 43 for(i = 1 ; i < x ;i++) 44 pa[++g] = i; 45 for(i = f[a[x]]+1 ; i <= n ;i++) 46 pa[++g] = i; 47 for(i = x+1 ; i < f[a[x]] ; i++) 48 if(a[i]<0) 49 { 50 g++; 51 pa[g] = i; 52 } 53 cout<<maxz<<" "<<g<<endl; 54 sort(pa+1,pa+g+1); 55 for(i = 1; i < g ; i++) 56 cout<<pa[i]<<" "; 57 if(g) 58 cout<<pa[g]<<endl; 59 return 0; 60 }
B 线段树 连续的数中较大的数的位置如果比较小的小得话 就+1 求和询问下就行
把L写成了1 悲剧了。。
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<vector> 7 #include<queue> 8 #include<cmath> 9 #include<map> 10 using namespace std; 11 #define LL long long 12 #define INF 1e10 13 #define N 300010 14 int a[N],po[N]; 15 int s[N<<2]; 16 void up(int w) 17 { 18 s[w] = s[w<<1]+s[w<<1|1]; 19 } 20 void build(int l,int r,int w) 21 { 22 if(l==r) 23 { 24 if(po[l]>po[l+1]) 25 s[w] = 1; 26 else s[w] = 0; 27 return ; 28 } 29 int m = (l+r)>>1; 30 build(l,m,w<<1); 31 build(m+1,r,w<<1|1); 32 up(w); 33 } 34 int query(int a,int b,int l,int r,int w) 35 { 36 if(a<=l&&b>=r) 37 { 38 return s[w]; 39 } 40 int m = (l+r)>>1; 41 int ans = 0; 42 if(a<=m) 43 ans+=query(a,b,l,m,w<<1); 44 if(b>m) 45 ans+=query(a,b,m+1,r,w<<1|1); 46 return ans; 47 } 48 void update(int p,int l,int r,int w) 49 { 50 if(l==r) 51 { 52 if(po[l+1]<po[l]) 53 s[w] = 1; 54 else s[w] = 0; 55 return ; 56 } 57 int m = (l+r)>>1; 58 if(p<=m) 59 update(p,l,m,w<<1); 60 else 61 update(p,m+1,r,w<<1|1); 62 up(w); 63 } 64 int main() 65 { 66 int i,q,k,n; 67 cin>>n; 68 for(i = 1 ;i <= n ;i++) 69 { 70 cin>>a[i]; 71 po[a[i]] = i; 72 } 73 build(1,n-1,1); 74 cin>>q; 75 while(q--) 76 { 77 cin>>k; 78 int x,y; 79 if(k==1) 80 { 81 cin>>x>>y; 82 cout<<query(x,y-1,1,n-1,1)+1<<endl; 83 } 84 else 85 { 86 cin>>x>>y; 87 po[a[x]] = y; 88 po[a[y]] = x; 89 swap(a[x],a[y]); 90 if(a[x]<n) 91 update(a[x],1,n-1,1); 92 int k = a[x]-1; 93 if(k>0&&k<n) 94 update(k,1,n-1,1); 95 if(a[y]<n) 96 update(a[y],1,n-1,1); 97 k = a[y]-1; 98 if(k>0&&k<n) 99 update(k,1,n-1,1); 100 } 101 } 102 return 0; 103 }
C1 拿背包做的 因为不知道每次都应该减最大的
C2 知道了这个结论 可以先暴力出10^6 把10^12分为两部分 循环前一部分 这样复杂度指数级减小一般 然后开个二维数组c[i][j] 一维表示前一部分数的最大值 然后暴力j
这样每次减到《=0 小于0的部分再下一次循环中减去
注意点 减到0的时候 需注意要减的值 比如3999999 第一次减到3000000的话 下次不能直接循环c[2][1000000] 而是可以减一次3
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<cmath> 7 #include<vector> 8 #include<queue> 9 using namespace std; 10 #define LL long long 11 #define N 1000000 12 #define INF 0xfffffff 13 int dp[11][N+10]; 14 int o[11][N+10]; 15 int main() 16 { 17 int i,j; 18 LL n; 19 for(i = 0 ;i <= 9 ; i++) 20 { 21 dp[i][0] = 0; 22 } 23 for(i = 0; i <= 9; i++) 24 for(j = 1; j <= N ;j++) 25 { 26 int mm = i; 27 int k = j; 28 while(k) 29 { 30 int x = k%10; 31 mm = max(mm,x); 32 k/=10; 33 } 34 if(mm>=j) 35 { 36 dp[i][j] = dp[i][0]+1; 37 o[i][j] = j-mm; 38 } 39 else 40 { 41 dp[i][j] = dp[i][j-mm]+1; 42 o[i][j] = o[i][j-mm]; 43 } 44 } 45 while(cin>>n) 46 { 47 if(n<=N) 48 { 49 cout<<dp[0][n]<<endl; 50 continue; 51 } 52 LL m = n%N,nm = n/N; 53 LL s = 0; 54 int k = 0; 55 for(i = nm ; i >= 0; i--) 56 { 57 int y = i,ma = 0; 58 while(y) 59 { 60 int x = y%10; 61 y/=10; 62 ma = max(ma,x); 63 } 64 if(i!=nm) m = N+k; 65 s += dp[ma][m]; 66 k = o[ma][m]; 67 if(k==0&&i!=0) 68 { 69 s++; 70 k = -ma; 71 } 72 } 73 cout<<s<<endl; 74 } 75 return 0; 76 }