145 条题解
-
-35
用线段树+标记永久化即可
#include <cstdio> #define mid L + (R-L >> 1) const int maxn = 1e5+5; int n, a[maxn], m; int sl, sr, add; struct segtree{ int sum[maxn<<2], tag[maxn<<2]; inline int lc(int o){return o<<1;} inline int rc(int o){return o<<1|1;} void build(int o, int L, int R){ if(L == R){sum[o] = a[L];return;} int M = mid; build(lc(o), L, M); build(rc(o), M+1, R); sum[o] = sum[lc(o)] + sum[rc(o)]; } void maintain(int o, int L, int R){ if(R>L){ sum[o] = sum[lc(o)] + sum[rc(o)]; sum[o] += tag[o] * (R-L+1); } else { sum[o] += tag[o]; tag[o] = 0; } } void updata(int o, int L, int R){ if(sl <= L && R <= sr)tag[o] += add; else{ int M = mid; if(sl <= M)updata(lc(o), L, M); if(sr > M)updata(rc(o), M+1, R); } maintain(o, L, R); } int query(int o, int L, int R, int tags){ if(sl <= L && R <= sr)return sum[o] + tags * (R-L+1); else { int M = mid, res = 0; if(sl <= M)res += query(lc(o), L, M, tags+tag[o]); if(sr > M)res += query(rc(o), M+1, R, tags+tag[o]); return res; } } } sol; signed main(){ n = 1; int a, b; scanf("%d%d", &a, &b); sol.build(1, 1, n); add=a; sl=1; sr=1; sol.updata(1, 1, 1); add=b; sol.updata(1, 1, 1); printf("%d\n", sol.query(1, 1, n, 0)); return 0; }
当然,树状数组也可以,并且更快
#include <iostream> using namespace std; const int n = 1; int a, b; int c[500005]; inline int lowbit(int x){ return x & (-x); } inline int sum(int x){ int ans=0; for(int i=x;i>0;i-=lowbit(i)) ans+=c[i]; return ans; } void add(int x,int y){ for(int i=x;i<=n;i+=lowbit(i)) c[i]+=y; } int main(){ cin>>a>>b; add(1, a); add(1, b); printf("%d\n", sum(1)); return 0; }
-
-38
高精度水一发......
#include <iostream> #include <string> #include <algorithm> using namespace std; string a,b; int x[1005],y[1005],ans[1005]; int main() { cin>>a>>b; int la=a.size(),lb=b.size(); reverse(a.begin(),a.end()); reverse(b.begin(),b.end()); int n,i,j; for(i=0;i<la;i++) x[i]=a[i]-'0'; for(i=0;i<lb;i++) y[i]=b[i]-'0'; int temp,jin=0; for(i=0;i<1000;i++) { temp=x[i]+y[i]+jin; if(temp>=10) { jin=1; ans[i]=temp-10; } if(temp<10) { jin=0; ans[i]=temp; } } for(i=1000;i>=0;i--) if(ans[i]!=0) break; for(;i>=0;i--) { cout<<ans[i]; } return 0; }
信息
- ID
- 56
- 时间
- 1000ms
- 内存
- 1024MiB
- 难度
- 1
- 标签
- 递交数
- 9107
- 已通过
- 4056
- 上传者