BestCoder Round #86
第一场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;
}
2023年4月18日 18:38
10th Board Model Paper 2023 Aspirants who had Registered for the Board 10th Class Exam can Download the Previous Paper When Board Announces the Dates to Download the Question Paper. 10thmodelpapers.in Board Question Papers will be Provided Very Soon Through Online Mode and all the Applicants Should Visit the Official Page Regularly for More Information Regarding Previous Paper, Examination Date. Check the Below Provided Details for More Information About the Board Model Paper.