BestCoder Round #86

tonyfang posted @ 2016年8月07日 14:46 in HDU with tags c++ OI , 312 阅读

第一场bestcoder,做之前先了解了下规则

话不多说,下面来看题啦

A. Price List

给出$n$种商品,价格分别为$w_i$,小A可以少记录商品价格但是不能多记录,给出小A记录的商品价值之和(每种商品只能选1件),问是否一定是错的。

【题解】很明显,当询问$q>\sum_{i=1}^{n}w_i$的时候一定是错的。复杂度$O(n)$

 

# include <stdio.h>
using namespace std;
int T, n, m, v;
long long sumsss=0, x;
int main() {
    scanf("%d", &T);
    while(T--) {
        sumsss=0;
        scanf("%d%d", &n, &m);
        for (int i=1; i<=n; ++i) {
            scanf("%d", &v);
            sumsss=sumsss+v;
        }
        for (int i=1; i<=m; ++i) {
            scanf("%I64d", &x);
            if(x>sumsss)printf("1");
            else printf("0");
        }
        printf("\n");
    }
    return 0;
}

B. NanoApe Loves Sequence I

给出$n$个数$a_1, a_2, ..., a_n$,求出删去一个数后,相邻两数差的最大值的期望值。

为了防止误差,假设原来的答案为$ans$,那么输出$ans \times n$。

【题解】

这题考场上想这不就是set吗,好像multiset可以水过去,复杂度$O(nlog_{2}n)$,还问了问经常打bc的老司机$fjzzq2002$,他说没问题,我就大胆写了STL。

然后呢?瞬间爆炸fst啦!

 

# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <set>
using namespace std;

int T, n;
int a[666666];
int delta[666666]; //i, i+1
bool f[666666];
long long ans=0;
multiset<int> s;

inline int ABS(int a) {
	return a>0?a:-a;
}

int getmax() {
	multiset<int>::iterator g;
	g=s.end();
	return *(--g);
}

int main() {
	scanf("%d", &T);
	while(T--) {
		memset(f,0,sizeof(f));
		memset(delta,0,sizeof(delta));
		s.clear();
		ans=0;
		scanf("%d", &n);
		for (int i=1; i<=n; ++i) 
			scanf("%d", &a[i]);
		for (int i=1; i<n; ++i) {
			s.insert(ABS(a[i]-a[i+1]));
		}
		/*
		int Max=0, js;
		for (int i=1; i<n; ++i) Max=max(Max, delta[i]);
		int MMax=Max; Max=0;
		for (int i=2; i<=n; ++i) Max=max(Max, delta[i]);
		ans=ans+Max;
		Max=0;
		for (int i=1; i<n; ++i) Max=max(Max, delta[i]);
		ans=ans+Max;
		Max=MMax;
		for (int i=2; i<n; ++i) {
			// a[i], a[i+1], a[i+2]
			if(!(f[i-1]^f[i])) {
				int newdelta=delta[i-1]+delta[i];
				if(newdelta>Max)
					Max=newdelta;
			}
			ans = ans+Max;
		}*/
		for (int i=1; i<=n; ++i) {
			if(i!=1) 
				s.erase(s.lower_bound(ABS(a[i]-a[i-1])));
			if(i!=n)
				s.erase(s.lower_bound(ABS(a[i]-a[i+1])));
			if(2<=i && i<n) s.insert(ABS(a[i+1]-a[i-1]));
			ans=ans+getmax();
			if(2<=i && i<n) s.erase(s.lower_bound(ABS(a[i+1]-a[i-1])));
			if(i!=1) 
				s.insert(ABS(a[i]-a[i-1]));
			if(i!=n)
				s.insert(ABS(a[i]-a[i+1]));
		}
		printf("%I64d\n", ans);
	}

	return 0;
}

然后呢,我们发现我们可以$O(n)$求出$left_{i}, right_{i}$,其中$left_{i}$代表$[1,i]$中的相邻差的最大值,$right_{i}$对应表示$[i,n]$中相邻差最大值。那么我们就可以$O(n)$搞定这题啦!

 

# include <stdio.h>
# include <stdlib.h>
# include <algorithm>
using namespace std;

int T, n, a[666666];
int left[666666], right[666666];

inline int ABS(int x) {
     return x>0?x:-x;
}
long long ans=0;

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        ans=0;
        left[1]=right[n]=0;
        for (int i=1; i<=n; ++i) scanf("%d", &a[i]);
        for (int i=2; i<=n; ++i) left[i] = max(left[i-1], ABS(a[i]-a[i-1]));
        for (int i=n-1; i>=1; --i) right[i] = max(right[i+1], ABS(a[i]-a[i+1]));
        ans=ans+right[2];
        ans=ans+left[n-1];
        for (int i=2; i<n; ++i) {
            ans=ans+max(max(left[i-1], right[i+1]), ABS(a[i-1]-a[i+1]));
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

C. NanoApe Loves Sequence II

给出一个长度为$n$的序列$a_1, a_2, ..., a_n$,求出有多少个子串(连续),满足这个子串的第$k$大数不想小于$m$。

【题解】

看上去就是一道尺取(two_pointers),我们把大于$m$的数设为1,小于$m$的数设为0,那么假设一个子串的和比$k$大,那么就满足啦!为了方便,我们假设一个区间$[begin, end]$,那么我们发现,对于$end \leq i \leq n$的所有$i$,$[begin, i]$都满足这个结论,那么我们就随便尺取咯!

 

# include <stdio.h>

using namespace std;

int T, n, m, k, a[666666];
long long ans=0;

int main() {
    scanf("%d", &T);
    while(T--) {
        ans=0;
        scanf("%d%d%d",&n,&m,&k);
        for (int i=1; i<=n; ++i) scanf("%d", &a[i]);
        int begin=1, end=0, gs=0;
        while(begin<=n) {
            while(gs<k && end+1<=n) {
                gs=gs+(a[end+1]>=m);
                ++end;    
            }
            if(gs==k) {
                ans=ans+(n-end+1);
            }
            gs-=(a[begin]>=m);
            ++begin;
        }
        printf("%I64d\n", ans);
    }

    return 0;
}

D. Keep In Touch

给出一个n个点m条边的有向图,保证每条边出发编号总是小于到达编号,没有重边。

给出每个点的无线电高度$w_i$,一个人每次只能从一条边上走过,花费1时刻。

一个合法的方案在三个人的移动路线上的任意整时刻,他们都能互相联系。

互相联系定义为,他们之间的$w$的差值小于等于$K$

$q$组x询问$x,y,z$,意为三个人分别在$x,y,z$的时候,有多少种合法方案?

$n \leq 50, m \leq 2500, q \leq 125000$

【题解】

比赛的时候想到做法没调出来,尴尬QAQ

$f[i, j, k, 0/1/2]$表示一个人走到i,一个人走到j,一个人走到k,现在是第x个人走的方案数

那么转移还是很方便的。注意到题目保证了拓扑序,所以不需要拓扑排序了。复杂度$O(n^3)$

# include <stdio.h>
# include <string.h>
using namespace std;

long long f[51][51][51][3];

void add(long long &x, long long y) {
	x=(x+y)%998244353;
}

int T, n, m, K, Q;
int w[51];
/*
int head[51], next[66666], to[66666], tot;
inline void add(int u, int v) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}
*/
int head2[51], next2[66666], to2[66666], tot2;
inline void add2(int u, int v) {
	++tot2;
	next2[tot2]=head2[u];
	head2[u]=tot2;
	to2[tot2]=v;
}
inline int ABS(int x) {
	return x>0?x:-x;
}


int main() {
	scanf("%d", &T);
	while(T--) {
		//memset(head, 0, sizeof(head));
		memset(head2, 0, sizeof(head2));
		memset(f, 0, sizeof(f));
		scanf("%d%d%d%d", &n, &m, &K, &Q);
		for (int i=1; i<=n; ++i) scanf("%d", &w[i]);
		for (int i=1, u, v; i<=m; ++i) {
			scanf("%d%d", &u, &v);
			add2(v, u);
		}
		for (int i=1; i<=n; ++i)
			for (int j=1; j<=n; ++j)
				for (int k=1; k<=n; ++k) 
					if(ABS(w[i]-w[j]) <= K && ABS(w[j]-w[k]) <= K && ABS(w[i]-w[k]) <= K)
						f[i][j][k][0] = 1;
		for (int i=n; i>=1; --i)
			for (int j=n; j>=1; --j)
				for (int k=n; k>=1; --k) {
					int X=i, Y=j, Z=k;
					for (int kk=head2[X]; kk; kk=next2[kk]) {
						int TO=to2[kk];
						add(f[TO][j][k][1], f[i][j][k][0]);
					}
					for (int kk=head2[Y]; kk; kk=next2[kk]) {
						int TO=to2[kk];
						add(f[i][TO][k][2], f[i][j][k][1]);
					}
					for (int kk=head2[Z]; kk; kk=next2[kk]) {
						int TO=to2[kk];
						if(ABS(w[TO] - w[X]) <= K && ABS(w[TO] - w[Y]) <= K && ABS(w[Y] - w[X]) <= K)
							add(f[i][j][TO][0], f[i][j][k][2]);
					}
				}
		/*
		 for (int i=1; i<=n; ++i)
        	for (int j=1; j<=n; ++j)
        		for (int k=1; k<=n; ++k) printf("i=%d, j=%d, k=%d, 0=%d, 1=%d, 2=%d\n",i,j,k,f[i][j][k][0],f[i][j][k][1],f[i][j][k][2]);
		*/
		while(Q--) {
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			printf("%I64d\n", f[x][y][z][0]);
		}
	}
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter