杭师训练赛3总结

反面教材

杭师训练赛第三场

A - Jumping Buildings

  • 题意:给出n个数,在位置i上可移动到min(i+a[i],n)且仅移动一次,若中间有大于a[i]的数a[j],则移动到j-1,求出每个位置移动的终点。
  • 思路:从后往前遍历,用递减单调栈维护右边第一个比它高的位置。
  • 读错题,以为可以多次跳;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int x[N],f[N],n;
int sta[N],tot=0;
int main(){
scanf("%d",&n);
rep(i,1,n) f[i]=i;
rep(i,1,n) scanf("%d",&x[i]);
sta[++tot]=n;
repd(i,n-1,1){
while(tot && (x[sta[tot]] <= x[i])) tot--;
int y=min(i+x[i],n);
if(x[sta[tot]]>x[i] && sta[tot]<=y) y=sta[tot]-1;
f[i] = y;
sta[++tot] = i;
}
rep(i,1,n){
printf("%d%c",f[i]-i," \n"[i==n]);
}
return 0;
}

B - Divples

  • 题意:给出a和b两个数,找出所有数c,满足a%c==0 && c%b==0。(1<=b<=a<=1e12)
  • 思路:找出a的所有因数,再在里面找出所有b的倍数,排序输出即可
  • 一开始想将a/b分解因式,找到所有约数,没想到这能T。。。然后老老实实sqrt(n)扫过去。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ll f[N],x[N];
int cnt=0,tot=0;
int main(){
ll a,b;
scanf("%lld%lld",&a,&b);
ll c=a/b;
int t=0;
for(ll i=1;i*i<=a;i++){
if(a%i==0) {
f[++tot] = i;
f[++tot] = a/i;
}
}
tot = unique(f+1,f+1+tot)-f-1;
for(int i=1;i<=tot;i++)
if(f[i]%b==0)
x[++cnt]=f[i];
sort(x+1,x+1+cnt);
rep(i,1,cnt) dbg(x[i],i,cnt);
return 0;
}

C - Rectangles

  • 题意:给出N(<=2000)个点,求这些点能组成的矩形个数,满足矩形内部和边界不包含其他点且矩形的边平行于坐标轴。
  • 思路:先将x,y离散化,按y轴从下至上扫描,对于同一高度,枚举相邻点i和j,再在i和j上方分别找到第一次出现的点,看两个点的y坐标是否相等,若相等,再判断这四个点构成的矩形中是否有其他点,可用二维前缀和预处理后O(1)询问。
  • 中途代错参数一直没找到(还过了15个点。。。),赛后又想了想,好像n方枚举对角顶点也不会T,费那么大力气干嘛。。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
struct node{
int x,y;
}a[N];
struct node1{
int p,q; // x y 坐标
};
bool cmp1(int i,int j){return a[i].x<a[j].x;}
bool cmp2(int i,int j){return a[i].y<a[j].y;}
int bx[N],by[N],n,mx=0,my=0;
vector<int> vx[N],vy[N];
map<int,node1> mp;
int hv[2001][2001];
bool check(int x1,int y1,int x2,int y2){
int num=hv[x2][y2]-hv[x1-1][y2]-hv[x2][y1-1]+hv[x1-1][y1-1];
return num==4;
}
int main(){
scanf("%d",&n);
rep(i,1,n){
scanf("%d%d",&a[i].x,&a[i].y);
bx[++mx]=a[i].x, by[++my]=a[i].y;
}
sort(bx+1,bx+1+mx);
sort(by+1,by+1+my);
mx=unique(bx+1,bx+1+mx)-bx-1;
my=unique(by+1,by+1+my)-by-1;
rep(i,1,n) {
a[i].x=lower_bound(bx+1,bx+1+mx,a[i].x) - bx;
a[i].y=lower_bound(by+1,by+1+my,a[i].y) - by;
vx[a[i].x].push_back(i);
vy[a[i].y].push_back(i);
hv[a[i].x][a[i].y]=1;
}
rep(i,1,mx) sort(vx[i].begin(),vx[i].end(),cmp2); //同x y递增
rep(i,1,my) sort(vy[i].begin(),vy[i].end(),cmp1); //同y x递增
rep(i,1,mx){
for(int j=0;j<vx[i].size();j++){
mp[vx[i][j]]=(node1){0,0};
mp[vx[i][j]].q = j;
}
}
rep(i,1,my){
for(int j=0;j<vy[i].size();j++){
mp[vy[i][j]].p = j;
}
}
rep(i,1,mx){
rep(j,1,my){
hv[i][j]+=(hv[i][j-1]+hv[i-1][j]-hv[i-1][j-1]);
}
}
int ans=0;
rep(i,1,my){
for(int j=0;j<vy[i].size()-1;j++){
int sit1=vy[i][j],sit2=vy[i][j+1];
int x1=a[sit1].x, x2=a[sit2].x;
int t1=mp[sit1].q, t2=mp[sit2].q;
if(t1+1>=vx[x1].size() || t2+1>=vx[x2].size()) continue;
int y1=a[vx[x1][t1+1]].y, y2=a[vx[x2][t2+1]].y;
if(y1==y2 && check(x1,i,x2,y2)) ans++;
}
}
printf("%d\n",ans);
return 0;
}


D - Guessing Messages

  • 题意:给两个串a,b,问b是否是a的子序列
  • 思路:扫过去即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
string a,b;
int main(){
cin>>a>>b;
int i=0,j=0;
while(i<a.size() && j<b.size()){
while(i<a.size() && a[i]!=b[j]) i++;
if(i>=a.size()) break;
else i++,j++;
}
if(j==b.size()) puts("YES");
else puts("NO");
return 0;
}

E - Chi’s performance

  • 题意:有n个人,每个人会一种类型的乐器v[i],每个人有能力值p[i],对于不同的v,按v从小到大排序,对于相同的v,顺序任意。对于相邻两个乐器,相同乐器之间贡献为0,不同乐器间的贡献为二者能力值差的绝对值,问如何排序可使贡献和最大。
  • 思路:对于每个v相等的块,首尾值为:1:最大值、2:次大值、3:最小值、4:次小值时存在最优解。设f[i][j]为第i块的第一个数字为状态j时前i块的最优解。f[i][j] = max(f[i-1][p] + abs(w[i-1][k]-w[i][j])),p!=k。复杂度为O(4^3 * tot)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
struct node{
ll v,p;
bool operator < (const node &e)const{
return v<e.v;
}
}a[N];
int n,tot=0;
ll f[N][5],w[N][5],num[N];
void prework(){
sort(a+1,a+1+n);
rep(i,1,n) {
w[i][3] = w[i][4] = inf;
w[i][1] = w[i][2] = -inf;
}
int i=1, sum;
ll pre=a[1].v;
while(i<=n){
tot++, sum=0;
while(i<=n && a[i].v==pre){
if(a[i].p > w[tot][2]) w[tot][2]=a[i].p;
if(w[tot][2] > w[tot][1]) swap(w[tot][2],w[tot][1]);
if(a[i].p < w[tot][4]) w[tot][4]=a[i].p;
if(w[tot][4] < w[tot][3]) swap(w[tot][3],w[tot][4]);
i++, sum++;
}
pre = a[i].v;
num[tot] = min(sum,4);
}
}
int main(){
scanf("%d",&n);
rep(i,1,n) scanf("%lld%lld",&a[i].v,&a[i].p);
prework();
rep(i,1,tot)
rep(j,1,num[i])
rep(p,1,num[i-1])
rep(k,1,num[i-1]){
if(p==k && num[i-1]!=1) continue;
f[i][j] = max(f[i][j], f[i-1][p] + abs(w[i-1][k]-w[i][j]) );
}
ll ans=-1;
rep(i,1,num[tot]) ans = max(ans, f[tot][i]);
printf("%lld\n",ans);
return 0;
}

F - Drawing cards

  • 题意:共1到n张纸牌,每次抽一张牌,如果抽到重复的就放回去,否则放到桌子上,并把一张新的相同的牌放进去,求第一次抽到1时桌上纸牌的期望值。
  • 思路:桌上牌数可为(1~n)张且等概率出现,每种结果的概率均为1/n,E(x)=(1+2+…+n)/n
  • 读错题,开局狂卡。。。
1
2
3
4
5
6
7
int main(){
double n,ans=0;
scanf("%lf",&n);
rep(i,1,n) ans+=(1.0/n)*i;
printf("%.9f\n",ans);
return 0;
}

G - Left Stack Game

  • 题意:给出三堆石子x,y,z,每次一堆中取1~m颗,当左边存在石子时右边不能为空,问是否先手必胜
  • 思路:从y,z中各去掉一个石子后限制条件即可消除,求三堆函数的sg值,每一堆都是一个巴什博弈,最后由于y、z各剩一颗,所以上面的处理方法不会对答案有影响。
1
2
3
4
5
6
7
8
9
10
ll x,y,z,m;
int main(){
scanf("%lld%lld%lld%lld",&m,&x,&y,&z);
ll a=0,b=0,c=0;
a=x%(m+1);
b=(y-1)%(m+1);
c=(z-1)%(m+1);
puts((a^b^c)?"Tomaz":"Danftito");
return 0;
}

H - Log Concave Sequences

  • 题意:给出一个n,要求用0,1,2构造长为n<1e18的串,且满足`1a[i-1]*a[i+1]`,问能构造出多少种方案。
  • 思路
    • 一眼dp题,f[i][x][y]表示当前构造第i个串,最后两个为x和y,转移方程为f[i][x][y] = ∑f[i-1][z][x],z*y<=x*x。但是n很大,显然不能直接推过去。
    • 通过观察我们可以发现i的状态只与i-1有关,x和y的取值只有固定的9种,因此我们可以将xy取值的9中状态放入1*9的矩阵中,用矩阵快速幂进行优化。
    • 矩阵a[x-1] * h = a[x] , 其中a[x]为阶段x的答案矩阵,h为我们需要的转移矩阵。观察目标矩阵的第j个状态,若原矩阵的第i个状态满足转移条件,就将h矩阵的第j列的第i行置为1,否则为0。
      即:将目标矩阵作为列,原矩阵作为行,每一列根据所需要的原矩阵元素赋予相应参数。
  • 太久没写,当时忘记怎么构造矩阵了…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int q[9][2] = {0,0,0,1,0,2, 1,0,1,1,1,2, 2,0,2,1,2,2};
struct rec{
ll h[10][10];
rec(){clr(h,0);}
rec operator * (const rec &e)const{
rec ans;
rep(i,0,8)
rep(j,0,8)
rep(k,0,8)
ans.h[i][j] = (ans.h[i][j] + h[i][k]*e.h[k][j]%mod)%mod;
return ans;
}
}unit;
rec qpow(rec a,ll n){
rec ans;
rep(i,0,8) ans.h[0][i] = 1;
for(;n;n>>=1){
if(n&(1ll)) ans = ans*a;
a = a*a;
}
return ans;
}

int main(){
rep(j,0,8)
rep(i,0,8){
if(q[i][1]==q[j][0] && q[i][0]*q[j][1]<=q[j][0]*q[j][0])
unit.h[i][j] = 1;
}
ll n; scanf("%lld",&n);
rec ans = qpow(unit,n-2);
ll res=0;
rep(i,0,8) (res += ans.h[0][i])%=mod;
printf("%lld\n",res);
return 0;
}

J - Weird Sanchola

  • 题意:给出n个数,找到一个素数x,使得∑|a[i]-x|最小。
  • 思路:众所周知,若需要找的x没有素数限制,当x为序列a的中位数时上式值最小。也就是说,找到离中位数最近的素数即可找到答案。
  • Miller-Robbin判素数T了,试除法过了???
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
bool isprime(ll x){
if(x==1)return false;
for(ll i=2;i*i<=x;i++)
if(x%i==0) return false;
return true;
}
int n; ll x[N];
int main(){
scanf("%d",&n);
rep(i,1,n) scanf("%lld",&x[i]);
sort(x+1,x+1+n);
ll p=0,num1,num2;
if(n&1) num1= num2 = x[n/2+1];
else {
ll num=(x[n/2]+x[n/2+1]);
if(num%2==0) num1 = num2 = num/2;
else {
num1=num/2;
num2=num1+1;
}
}
while(!isprime(num1)) num1--;
while(!isprime(num2)) num2++;
ll ans1 = 0, ans2 = 0;
rep(i,1,n) {
ans1+=abs(x[i]-num1);
ans2+=abs(x[i]-num2);
}
printf("%lld\n",min(ans1,ans2));
return 0;
}

本场总结

主要涵盖的知识点:单调栈,离散化,模拟,数学公式,素数判定,中位数,随机等概率模型,dp,矩阵快速幂,巴什博奕,sg函数,主席树(K),后缀数组(K)等,其中ABCDEFGHJ均可做。

个人总结

把简单的问题复杂化,读错题,算错复杂度…总的来说,这场全程翻车,开局卡题搞心态,导致后面没有足够的时间完成本应完成的题,其中最大的问题还是读题不仔细(好像已经因为读错题翻过无数次车了…)。

Donate comment here