2022-7-5 个人排位赛2 比赛心得

比赛链接内网：10.7.95.2

资源访问控制系统

题目目录和过题数量（这场重点IJ卡了好久）：

B:Why Did the Cow Cross the Road V - Max Cross

Farmer John 的农场里有 N 条人行横道，编号为 1…N (1≤N≤100,000)。 为了让奶牛在这些人行横道上通过，FJ 安装了电子交叉信号灯，当奶牛可以通过时，该信号灯会亮起绿色的牛图标，否则会亮起红色。不幸的是，一场大的电磁风暴损坏了他的一些信号。 给定损坏信号的列表，请计算 FJ 需要修复的最少信号灯数，以便存在一段长度为 K 的连续编号的信号灯。

第一行包含 N, K, B。

接下来 B 行，每行给定被损坏的信号灯编号。

输出需要修复的最少信号灯数，以便存在一段长度为 K 的连续编号的信号灯。

Sample Input

10 6 5 2 10 1 5 9

Sample Output

1

思路：二分

#include <bits/stdc++.h>
#define int long long
#define CIO std::ios::sync_with_stdio(false)
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
const int N=2e5+5;
int a[N],d[N],ds[N];
int n,k,b;
int check(int x){x++;for (int i=1;i<=b-x+2;i++){if (ds[i+x-1]-ds[i-1]+(x-1)>=k){return true;}}return false;
}
void work(){cin>>n>>k>>b;a[0]=0;rep(i,1,b){cin>>a[i];}sort(a+1,a+b+1);rep(i,1,b){d[i]=a[i]-a[i-1]-1;}d[b+1]=n+1-a[b]-1;rep(i,1,b+1){ds[i]=ds[i-1]+d[i];}int l=0,r=b,mid;while(l<=r){mid=(l+r)/2;if (check(mid)==true){r=mid-1;}else{l=mid+1;}}cout<<l;
}
signed main(){CIO;work();return 0;
}

M:Angry Cows II

Bessie设计了一款新游戏: Angry Cows。在这个游戏中,玩家发射奶牛,每头奶牛落地时引爆一定范围内的干草。游戏的目标是使用一组奶牛引爆所有干草。N捆干草排列在数轴上的不同位置。第i捆干草的的位置为ci。如果一个威力为R的奶牛在z位置落地,她将引爆[z-R,x+R]范围内的所有干草。你现在可以发射K头奶牛,每头奶牛的威力都是R,现在你需要确定R的最小值,使得用K头奶牛可以引爆所有干草。

第一行两个整数N, K (1<N<5x 104, 1<K<10)。接下来N行,第i行一个整数z; (0<ci<109)

输出一个整数，即 R 的最小值。

Sample Input

7 2 20 25 18 8 10 3 1

Sample Output

5

思路：也是二分

#include <bits/stdc++.h>
#define int long long
#define CIO std::ios::sync_with_stdio(false)
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
const int N=2e5+5;
int a[N];
int n,k;
int check(int x){int ans=a[1];rep(i,1,k){ans+=2*x;if (ans>=a[n]){return true;}ans=*upper_bound(a+1,a+n+1,ans);}return false;
}
void work(){cin>>n>>k;rep(i,1,n){cin>>a[i];}sort(a+1,a+n+1);int l=1,r=N,mid;while (l<=r){mid=(l+r)/2;if (check(mid)==true){r=mid-1;}else{l=mid+1;}}cout<<l;
}
signed main(){CIO;work();return 0;
}

I:Subsequences Summing to Sevens

给你 n 个数，分别是 a[1],a[2],...,a[n]。

求一个最长的区间 [x,y]，使得区间中的数 (a[x],a[x+1],a[x+2],...,a[y-1],a[y]) 的和能被 7 整除。

输出最长的区间长度。n (1≤n≤50,000)

若没有符合要求的区间，输出 0。

Sample Input

7 3 5 1 6 2 14 10

Sample Output

5

思路：用前缀和维护到时间复杂度O(n^2)，然后发现卡了三个样例，显然n^2的时候已经是1e9了。（考试的时候一直在想常数卡掉，没想到动本质）之前也有过类似做法的题目。

遇到区间和而且和余数有关，前缀和取模后所得到的数组相等的值，表示这中间的一段可以整除。然后就可以优化到O（N).

通过额外两个数组，然后两边扫到最长区间的左右端点，就可以得到答案。

关键就是前缀和进一步优化。

#include <bits/stdc++.h>
#define CIO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
const int N=1e5+5;
int a[N],s[N];
int bgin[N],endd[N]; 
int n;
void work(){int ma=-1;scanf("%d",&n);rep(i,1,n){scanf("%d",&a[i]);s[i]=(s[i-1]+a[i])%7; }rep(i,1,n){if (bgin[s[i]]==0)bgin[s[i]]=i;}rep(i,1,n){endd[s[i]]=i;}rep(i,1,n){ma=max(ma,endd[i]-bgin[i]);}cout<<ma;
}
signed main(){work();return 0;
}

J:There is no "Why Did the Cow Cross the Road I&II&III" here, only Emergency Dispatch

奶牛正在Farmer John的农场里吃草,但由于它们昨晚在牛圈里开派对时吃了太多的神秘食物,导致现在所有奶牛都想喷射。奶牛们都是懂文明讲礼貌的,因此它们每头牛都想找到最近的茅房。已知农场可以表示为一张nxm的网格图,每间茅房能够同时容纳无限只奶牛,每头奶牛每秒钟可以向四周(上、下、左、右)任意一个方向跑一格,同一位置在同一时刻也可以容纳无限只奶牛,但它们不能跑到稻草堆的位置上。紧急调度这件事可难坏了Farmer John,毕竟这可是个脑力活。因此请你帮帮他,问如果每一头奶牛都往离自己最近的茅房跑去,最多需要多少秒才能让所有奶牛都到达茅房?当然,可能有些奶牛被困在了稻草堆圈内无法动弹,因此也请你求出有多少只奶牛只能被迫就地解决吧。

第一行包含两个正整数n,m,分别表示农场的长与宽。其后n行,每行m个字符,表示农场,其中字符W表示一个茅房,字符C表示一头奶牛,字符,表示一个空地(可以经过),字符#表示稻草堆(不可以经过)数据保证农场内至少有一头牛,且至少有一间茅房,但茅房的总数量不会超过100间。4<n,m < 1000

输出两个整数,以空格隔开,分别表示让所有奶牛都到达离自己最近的茅房所需要的最少秒数及就地解决的奶牛数量。如果所有奶牛都无法到达任何一个茅房,秒数输出-1。

题意：多元的BFS。

思路：因为茅房数量少，所以从茅房下手，然后BFS。但是发现TL了，正解是全部茅房一起BFS因为先遇到的vis肯定比后面遇到这个点的茅房要小，其实某种意义上来说就是记忆化。

#include <bits/stdc++.h>
#define int long long
#define CIO std::ios::sync_with_stdio(false)
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
const int N=1e3+5;
int n,m;
struct maoce{int x,y;
}c[200];
char s[N][N];
int vis[N][N];
int cow[N][N];
struct node{int x;int y;int temp;
};
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
queue<node> q;
int cnt=0;
void bfs(){while(!q.empty()) q.pop();rep(i,1,cnt){q.push({c[i].x,c[i].y,0});vis[c[i].x][c[i].y]=1;}while (!q.empty()){int x=q.front().x;int y=q.front().y;int t=q.front().temp;q.pop();for (int i=0;i<4;i++){int xx=x+dx[i];int yy=y+dy[i];if (vis[xx][yy]!=1&&xx>=1&&xx<=n&&yy>=1&&yy<=m){if (s[xx][yy]=='.'){vis[xx][yy]=1;q.push({xx,yy,t+1});}if (s[xx][yy]=='C'){cow[xx][yy]=min(cow[xx][yy],t+1);vis[xx][yy]=1;q.push({xx,yy,t+1});}}}}
}
void work(){cin>>n>>m;rep(i,1,n){rep(j,1,m){cow[i][j]=INT_MAX;}}rep(i,1,n){rep(j,1,m){cin>>s[i][j];if (s[i][j]=='W'){c[++cnt].x=i;c[cnt].y=j;}}}int mei=0,ma=-1,zhi;bfs();rep(i,1,n){rep(j,1,m){if (s[i][j]=='C'){if (cow[i][j]==INT_MAX){mei++;}else{ma=max(ma,cow[i][j]);}}}}cout<<ma<<" "<<mei;
}
signed main(){CIO;work();return 0;
}

C题：我也是一道搜索题，就不拿出来了。

A题：贪心，我想当然用了尺取，实际上是n^2（sort里面不要习惯写n+1）