BUPT Summer Training #7 for Grade 14 题解

A. CodeForces 396C

题意就不描述啦。

自己在纸上推推公式，很容易就能知道为何是对的了

这里用两个树状数组即可维护，

这里的区间操作可以用线段树，也可以用树状数组。当然树状数组比较简单。我用的是树状数组。

这题还有一个做法是用树链剖分，如果学过树链剖分的话，可以尝试着做一下~

代码：

#include <iostream>#include <cstdio>#include <stack>#include <cstring>#include <queue>#include <algorithm>#include <cmath>//#include <unordered_map>#define N 500010//#define lson x<<1//#define rson x<<1|1//#define mid ((lt[x].l+lt[x].r)/2)//#define ID(x, y) ((x)*m+(y))//#define CHECK(x, y) ((x)>=0 && (x)<n && (y)>=0 && (y)<m)using namespace std;typedef pair<long long,long long> PII;const long long INF=0x3f3f3f3f;const long long mod = 1e9+7;void Open(){#ifndef ONLINE_JUDGEfreopen("D:/in.txt","r",stdin);//freopen("D:/my.txt","w",stdout);#endif // ONLINE_JUDGE}long long n, m, Tn;long long c1[N], c2[N], dep[N], st[N], ed[N];vector<long long> G[N];void add(long long c[], long long x, long long val){for(long long i = x; i <= n+10; i += ((-i) & i)) c[i] = (c[i] + val) % mod;}long long getsum(long long c[], long long x){long long rnt = 0;for(long long i=x;i>0;i -= ((-i) & i)) rnt = (rnt + c[i])%mod;return rnt;}void dfs(long long u, long long d){dep[u] = d; st[u] = ++Tn;for(long long i=0;i<G[u].size();i++) dfs(G[u][i], d+1);ed[u] = Tn;}int main(){Open();Tn = 0;scanf("%I64d", &n);for(long long i=2;i<=n;i++){long long x;scanf("%I64d", &x);G[x].push_back(i);}dfs(1, 0);scanf("%I64d", &m);while(m–){long long op;scanf("%I64d", &op);if(op == 1){long long v, x, k;scanf("%I64d%I64d%I64d", &v, &x, &k);add(c1, st[v], x + k * dep[v] % mod);add(c1, ed[v]+1, – (x + k * dep[v] % mod));add(c2, st[v], k);add(c2, ed[v]+1, – k);}else {long long v;scanf("%I64d", &v);long long tmp = getsum(c1, st[v]) – getsum(c2, st[v]) * dep[v];tmp = (tmp%mod + mod)%mod;printf("%I64d\n", tmp);}}return 0;}

B. CodeForces 362C点这里看题解~~

C.POJ 3468 A Simple Problem with Integers

点这里看题解~~

这里直接用线段树就可以啦，，线段树区间修改区间查询基本功就不说了，我当时做这个题是学习了树状数组的区间修改区间查询姿势，所以写得是树状数组的。

D. CodeForces 546D

代码：

#include <iostream>#include <cstdio>#include <stack>#include <cstring>#include <queue>#include <algorithm>#include <cmath>//#include <unordered_map>#define N 5000010using namespace std;typedef pair<long long,long long> PII;const long long INF=0x3f3f3f3f;void Open(){#ifndef ONLINE_JUDGEfreopen("D:/in.txt","r",stdin);//freopen("D:/my.txt","w",stdout);#endif // ONLINE_JUDGE}//long long pn;long long vis[N];void get_prime(){memset(vis,0,sizeof(vis));for(long long i=2;i<N;i++){if(vis[i]!=0) continue;vis[i]=1;for(long long j=i*2;j<N;j+=i){long long tmp = j;long long rnt=0;while(tmp%i==0){tmp/=i;rnt++;}vis[j]+=rnt;}}}long long a[N];int main(){//Open();get_prime();a[0]=0;for(long long i=1;i<N;i++)a[i]=vis[i]+a[i-1];long long T;scanf("%I64d",&T);while(T–){long long A,B;scanf("%I64d%I64d",&A,&B);printf("%I64d\n",a[A]-a[B]);}return 0;}E. POJ 2533 Longest Ordered Subsequence

。。最长上升子序列，各种书上都有的，这里就不说了吧，而且数据量只有1000，随便暴力dp做就行

题解在这里

如果哪里不明白可以直接Q我。

而是他们在同伴们都睡着的时候，一步步艰辛地

相关文章：

你感兴趣的文章：

标签云：