牛客算法周周练15
数列下标
https://ac.nowcoder.com/acm/contest/6290/A
A数列下标
题意：给出n个元素A数组，定义B数组为A数组下标右边第一个比该元素大的下标，如果没找到则为0.
解法：单调栈，维护单调递减栈，每次被弹出的元素下标的第一个比该元素大的值，为当前遍历下标值。
#include<bits/stdc++.h>
typedef long long ll ;
#define mod 1000000007
#define gcd __gcd
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j) for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
#define SC scanf
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define size(v) (int)(v.size())
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define int ll
using namespace std;
const int N = 2e5+9;
const int maxn = 1e4+9;
int a[maxn];
int st[maxn] , top ;
int b[maxn];
void solve(){
int n ;
scanf("%lld" , &n);
a[n+1] = -INF ;
rep(i , 1 , n){
scanf("%lld" , &a[i]);
while(top && a[i] > a[st[top]]){
b[st[top]] = i ;
top--;
}
st[++top] = i ;
}
rep(i , 1 , n){
cout << b[i] << " " ;
}
cout << endl;
}
signed main()
{
/*#ifdef ONLINE_JUDGE
#else
freopen("D:\\c++\\out.txt", "w", stdout);
#endif*/
//int _ ;cin>>_;while(_--)
solve() ;
}
B可持久化动态图上树状数组维护01背包
题意：给出一个n长序列，每次可以从任意位置i花费ai * i 的代价来把ai删除，删除后后面元素依次补上
问删完所有元素的最小代价为多少？
解法：很容易想到：如果序列全为正数，则一直删除第一个元素，代价最小。
如果全为负数，则一直删最后一个。
那么一般情况，则优先删除负数，再删正数
#include<bits/stdc++.h>
typedef long long ll ;
#define mod 1000000007
#define gcd __gcd
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j) for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
#define SC scanf
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define size(v) (int)(v.size())
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define int ll
using namespace std;
const int N = 2e5+9;
const int maxn = 1e6+9;
int a[maxn];
int st[maxn] , top ;
int b[maxn];
bool cmp(int a, int b){
return a > b ;
}
void solve(){
int n , ans = 0;
scanf("%lld" , &n);
rep(i , 1 , n){
scanf("%lld" , &a[i]);
if(a[i] > 0)
ans += a[i];
}
red(i , n , 1){
if(a[i] < 0){
ans += a[i] * i ;
}
}
cout << ans << endl;
}
signed main()
{
/*#ifdef ONLINE_JUDGE
#else
freopen("D:\\c++\\out.txt", "w", stdout);
#endif*/
//int _ ;cin>>_;while(_--)
solve() ;
}树上求和
题意：给出1为根的一棵树，给出初始结点值，q次操作，有两种操作。1、将以x为根的子树都加上y。2、求出以x为根的子树平方和。
输出二操作值。
解法：dfs序区间化，线段树维护，普通和和平方和。
#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
typedef long long ll ;
#define mod 23333
#define gcd __gcd
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j) for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
//ll lcm(ll a , ll b){return a*b/gcd(a,b);}
ll quickpow(ll a , ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;b>>=1,a=a*a%mod;}return ans;}
//int euler1(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans-=ans/i;while(x%i==0)x/=i;}if(x>1)ans-=ans/x;return ans;}
//const int N = 1e7+9; int vis[n],prime[n],phi[N];int euler2(int n){ME(vis,true);int len=1;rep(i,2,n){if(vis[i]){prime[len++]=i,phi[i]=i-1;}for(int j=1;j<len&&prime[j]*i<=n;j++){vis[i*prime[j]]=0;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];}}}return len}
#define SC scanf
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define size(v) (int)(v.size())
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define int ll
using namespace std;
const int N = 1e6+9;
const int maxn = 1e5+9;
int n , m , p ;
int a[maxn];
int in[maxn] , out[maxn] , cnt , dfn[maxn];
vector<int>g[maxn];
struct tree{
int l , r , Val , val , lazy;
}tr[maxn<<2];
void dfs(int u , int pre){
in[u] = ++cnt;
dfn[cnt] = u ;
for(auto v : g[u]){
if(v == pre) continue;
dfs(v , u);
}
out[u] = cnt;
}
void pushup(int root){
tr[root].val = (tr[root<<1].val + tr[root<<1|1].val)%mod ;
tr[root].Val = (tr[root<<1].Val + tr[root<<1|1].Val)%mod ;
}
void pushdown(int root){
int x = tr[root].lazy ;
tr[root<<1].Val = (tr[root<<1].Val + 2 * x * tr[root<<1].val % mod + (tr[root<<1].r - tr[root<<1].l + 1) * x * x % mod) % mod ;
tr[root<<1].val = (tr[root<<1].val + (tr[root<<1].r - tr[root<<1].l + 1) * x % mod) % mod ;
tr[root<<1].lazy = (tr[root<<1].lazy + x) % mod ;
tr[root<<1|1].Val = (tr[root<<1|1].Val + 2 * x * tr[root<<1|1].val % mod + (tr[root<<1|1].r - tr[root<<1|1].l + 1) * x * x % mod) % mod ;
tr[root<<1|1].val = (tr[root<<1|1].val + (tr[root<<1|1].r - tr[root<<1|1].l + 1) * x % mod) % mod ;
tr[root<<1|1].lazy = (tr[root<<1|1].lazy + x) % mod ;
tr[root].lazy = 0 ;
}
void build(int l , int r , int root){
tr[root].l = l , tr[root].r = r , tr[root]. lazy = 0 ;
if(l == r){
tr[root].val = a[dfn[l]];
tr[root].Val = tr[root].val * tr[root].val % mod ;
return ;
}
int mid = (l + r) >> 1 ;
build(lson);
build(rson);
pushup(root);
}
void update(int L , int R , int val , int root){
if(tr[root].l >= L && tr[root].r <= R){
tr[root].Val = (tr[root].Val + 2 * val * tr[root].val % mod + ((tr[root].r - tr[root].l + 1) * val * val % mod)) % mod ;
tr[root].val = (tr[root].val + (tr[root].r - tr[root].l + 1) * val % mod) % mod;
tr[root].lazy = (tr[root].lazy + val) % mod ;
return ;
}
if(tr[root].lazy) pushdown(root);
int mid = (tr[root].l + tr[root].r) >> 1 ;
if(mid >= L){
update(L , R , val , root<<1);
}
if(mid < R){
update(L , R , val , root<<1|1);
}
pushup(root);
}
int query(int L , int R , int root){
int sum = 0 ;
if(tr[root].l >= L && tr[root].r <= R){
return tr[root].Val;
}
if(tr[root].lazy) pushdown(root);
int mid = (tr[root].l + tr[root].r) >> 1 ;
if(mid >= L){
sum = (sum + query(L , R , root<<1))%mod;
}
if(mid < R){
sum = (sum + query(L , R , root<<1|1))%mod;
}
return sum ;
}
void solve(){
int n , q ;
scanf("%lld%lld" , &n , &q);
rep(i , 1 , n){
scanf("%lld" , &a[i]);
}
rep(i , 2 , n){
int u , v ;
scanf("%lld%lld" , &u , &v);
g[u].pb(v);
g[v].pb(u);
}
dfs(1 , 0);
build(1 , n , 1);
while(q--){
int t , x , y ;
scanf("%lld%lld" , &t , &x);
if(t == 1){
scanf("%lld" , &y);
update(in[x] , out[x] , y , 1);
}else{
cout << query(in[x] , out[x] , 1) << endl;
}
}
}
signed main()
{
/*#ifdef ONLINE_JUDGE
#else
freopen("D:\\c++\\in.txt", "r", stdin);
#endif*/
//init();
//int _ ;cin>>_;while(_--)
solve();
}算式子
题意：不多说
解法：统计a，考虑右半边式子，枚举a的值域，枚举商，考虑商对连续的x的贡献，利用差分统计。同理统计小于i的数量数组cnt[i]，枚举a值域，枚举商，商为k的a区间的数量对此时的x的贡献。
#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
typedef long long ll ;
#define mod 23333
#define gcd __gcd
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j) for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
//ll lcm(ll a , ll b){return a*b/gcd(a,b);}
ll quickpow(ll a , ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;b>>=1,a=a*a%mod;}return ans;}
//int euler1(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans-=ans/i;while(x%i==0)x/=i;}if(x>1)ans-=ans/x;return ans;}
//const int N = 1e7+9; int vis[n],prime[n],phi[N];int euler2(int n){ME(vis,true);int len=1;rep(i,2,n){if(vis[i]){prime[len++]=i,phi[i]=i-1;}for(int j=1;j<len&&prime[j]*i<=n;j++){vis[i*prime[j]]=0;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];}}}return len}
#define SC scanf
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define size(v) (int)(v.size())
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define int ll
using namespace std;
const int N = 1e6+9;
const int maxn = 2e6+9;
int cnt[maxn<<1] , ans[maxn<<1];
void solve(){
int n , m ;
scanf("%lld%lld" , &n , &m);
rep(i , 1 , n){
int x ;
scanf("%lld" , &x);
cnt[x]++;
}
rep(i , 1 , m){//枚举a[i]值域
if(cnt[i]){
for(int k = 1 ; k * i <= m ; k++){//枚举右半边的商
int l = k * i , r = (k + 1) * i - 1 ;//考虑商会对连续x有贡献
ans[l] += cnt[i] * k , ans[r+1] -= cnt[i]*k;//差分
}
}
}
for(int i = 1 ; i <= 2*m ; i++){
cnt[i] += cnt[i-1] ;//小于i的数量
ans[i] += ans[i-1] ;
}
int kk = 0 ;
rep(i , 1 , m){
int sum = ans[i];
for(int k = 1 ; k * i <= m ; k++){//枚举商
int l = k * i , r = (k + 1) * i - 1;//商为k的a的区间
sum += (cnt[r] - cnt[l - 1]) * k ;//商为k的贡献
}
kk ^= sum ;
}
cout << kk << endl;
}
signed main()
{
/*#ifdef ONLINE_JUDGE
#else
freopen("D:\\c++\\in.txt", "r", stdin);
#endif*/
//init();
//int _ ;cin>>_;while(_--)
solve();
}
投递腾讯等公司10个岗位 >