BestCoder Round# 45 题解

http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=604

题目在HDOJ上是5272~5275

A:给你一个数,问你它的二进制表示中有多少组1(两个1如果中间没有0算一组)

模拟

#include <iostream>
using namespace std;
int T;
int main() {
	ios::sync_with_stdio(0);
	cin >> T;
	while (T--) {
		long long n;
		int ans = 0;
		cin >> n;
		while (n) {
			if (n & 1) {
				++ans;
				while (n & 1) n >>= 1;
			}
			else n >>= 1;
		}
		cout << ans << endl;
	}
	return 0;
}

B:给出一个序列\(a_1\sim a_n\),每次询问区间\([L,R]\)的逆序对个数

令\(ans[i][j]\)为区间\([i,j]\)的逆序对个数,暴力算出\(ans[1][1\dots n]\),然后考虑\(ans[i][j](i\ge 2)\)。\(ans[i][j]\)比\(ans[i-1][j]\)少了\(a_{i-1}\)这个数的贡献,所以计算\(ans[i]\)这一维的时候开一个变量\(cnt\),扫到\(j\)的时候,如果\(a_{i-1}>a_j\)则\(cnt++\),那么\(ans[i][j]=ans[i-1][j]-cnt\)。

当然也可以枚举起点用树状数组算出\(ans[i][j]\)(归并是做不到的233,BIT大法好),只不过复杂度由\(O(n^2)\)变成了\(O(n^2\ log\ n)\)。

#include <cstdio>
const int MAXN = 1000 + 5;
int ans[MAXN][MAXN];
int a[MAXN];
int n, nQ;
void pre_do() {
	ans[0][0] = 0;
	for (int i = 1; i < n; ++i) {
		ans[0][i] = ans[0][i - 1];
		for (int j = 0; j < i; ++j) if (a[j] > a[i])
			++ans[0][i];
	}
	for (int i = 1; i < n; ++i) {
		int cnt = 0;
		for (int j = i; j < n; ++j) {
			if (a[i - 1] > a[j]) ++cnt;
			ans[i][j] = ans[i - 1][j] - cnt;
		}
	}
}
int main() {
	scanf("%d%d", &n, &nQ);
	for (int i = 0; i < n; ++i) scanf("%d", a + i);
	pre_do();
	while (nQ--) {
		int l, r;
		scanf("%d%d", &l, &r);
		--l; --r;
		printf("%d\n", ans[l][r]);
	}
	return 0;
}

C:给一棵树,资瓷两种操作:

\(0\ x\ y\):把编号为\(x\)的点的权值修改成\(y\)

\(1\ x\ y\):询问对于\(x~y\)路径上的点权是否都出现偶数次。如果不是,输出出现奇数次的那个点权。否则输出-1。保证每次询问的路径上最多只有一种点权出现了奇数次。

树链剖分模板题。。注意点权可以是0,要全部+1,输出的时候再减掉

注意如果是dfs树链剖分的话要开栈外挂。

这题我写的LCT TLE了,不知道有没有人用LCT过。。

呃。。贴的以前的模板,所以代码风格不太对不要在意。。

#pragma comment(linker, "/STACK:102400000")
#include<cstdio>
#include<algorithm>
#include<vector>
typedef std::vector<int>::iterator it;
const int MAXN=100000+5;
const int MAXO=4 * MAXN;
const int INF=~0U>>3;
int sumv[MAXO];
int top[MAXN],dep[MAXN],fa[MAXN],son[MAXN],sz[MAXN],w[MAXN];
int val[MAXN];
std::vector<int> G[MAXN];
int n,m,root;
void dfs(int u)
{
    sz[u]=1;son[u]=-1;
    for(it e=G[u].begin();e!=G[u].end();++e) if(*e!=fa[u])
        {
            fa[*e]=u;
            dep[*e]=dep[u]+1;
            dfs(*e);
            if(son[u]==-1 || sz[*e]>sz[son[u]]) son[u]=*e;
            sz[u]+=sz[*e];
        }
}
int dfs_clock=0;
void dfs2(int u,int tp)
{
    w[u]=++dfs_clock;top[u]=tp;
    if(~son[u]) dfs2(son[u],tp);
    for(it e=G[u].begin();e!=G[u].end();++e)
        if(*e!=son[u] && *e!=fa[u])
            dfs2(*e,*e);
}
inline void maintain(int o)
{
    int lc=o<<1,rc=o<<1|1;
    sumv[o]=sumv[lc] ^ sumv[rc];
}
void update(int o,int l,int r,int x,int a)
{
    if(x<l || x>r) return;
    if(l==r) {sumv[o]=a;return;}
    int m=l+r>>1;
    if(x<=m) update(o<<1,l,m,x,a);
    else update(o<<1|1,m+1,r,x,a);
    maintain(o);
}
int asksum(int o,int l,int r,int x1,int x2)
{
    if(x1>r || x2<l) return 0;
    if(l>=x1 && r<=x2) return sumv[o];
    int m=l+r>>1;
    return asksum(o<<1,l,m,x1,x2) ^ asksum(o<<1|1,m+1,r,x1,x2);
}
void init()
{
    dfs_clock = 0;
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; ++i) G[i].clear();
    root=1;
    fa[root]=-1;
    dep[root]=0;
    for(int i=0;i<n-1;++i)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1;i<=n;++i) scanf("%d",val+i), val[i]++;
    dfs(root);
    dfs2(root,root);
    for(int i=1;i<=n;++i)
        update(1,1,n,w[i],val[i]);
}
void work()
{
    int q,a,b;
    char s[10];
    while(m--)
    {
        scanf("%d%d%d",&q,&a,&b);
        if(q == 0)
            update(1,1,n,w[a],b + 1);
        else
        {
            int ans=0,f1=top[a],f2=top[b];
            while(f1!=f2)
            {
                if(dep[f1]<dep[f2]) std::swap(f1,f2),std::swap(a,b);
                ans^=asksum(1,1,n,w[f1],w[a]);
                a=fa[f1];f1=top[a];
            }
            if(dep[a]<dep[b]) std::swap(a,b);
            ans^=asksum(1,1,n,w[b],w[a]);
            if(ans == 0) ans = -1;
            else --ans;
            printf("%d\n",ans);
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--) 
    {
        init();
        work();
    }
    return 0;
}

D:给出一堆平面上的点,每次询问\((L,R,x)\) ,要求用\([L,R]\)这些点拟合一个\(R-L\)阶多项式,输出\(x\)带入多项式之后得到的值。

牛顿插值模板题,不会的话请百度

#include <cstdio>
typedef long long LL;
const int MAXN  = 3000 + 5;
const int MOD = 1000000007;
int n;
int X[MAXN], Y[MAXN];
int c[MAXN][MAXN];
int inv[250005];
int pow_mod(LL a, int b) {
	LL ans = 1;
	for (a %= MOD; b; b >>= 1, (a *= a) %= MOD)
		if (b & 1) (ans *= a) %= MOD;
	return (int)ans;
}

void pre_do() {
	for (int i = 1; i <= 250000; ++i) inv[i] = pow_mod(i, MOD - 2);
	for (int j = 0; j < n; ++j)
		for (int i = 0; i + j < n; ++i) {
			if (j == 0) c[i][i + j] = Y[i];
			else if(X[i + j] > X[i]) c[i][i + j] = (LL) (c[i + 1][i + j] - c[i][i + j - 1] + MOD) % MOD *
						inv[X[i + j] - X[i]] % MOD;
			else c[i][i + j] = (LL) (-c[i + 1][i + j] + c[i][i + j - 1] + MOD) % MOD *
						inv[-X[i + j] + X[i]] % MOD;
		}
}

int calc(int l, int r, int x) {
	LL t = 1, ans = 0;
	for (int i = l; i <= r; ++i) {
		(ans += (LL) c[l][i] * t) %= MOD;
		(t *= ((x - X[i] + MOD) % MOD)) %= MOD;
	}
	return ans;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) scanf("%d%d", X + i, Y + i);
	pre_do();
	int nQ;
	scanf("%d", &nQ);
	while (nQ--) {
		int l, r, x;
		scanf("%d%d%d", &l, &r, &x);
		printf("%d\n", calc(l - 1, r - 1, x));
	}
	return 0;
}

 

发表评论

电子邮件地址不会被公开。