【2021杭电多校赛】2021“MINIEYE杯”中国大学生算法设计超级联赛（8）签到题5题
【摘要】
Current Server Time : 2021-08-12 17:17:29
Solved Pro.ID Title Ratio(Accepted / Submitted) 1001 X-like...
Current Server Time : 2021-08-12 17:17:29
Solved Pro.ID Title Ratio(Accepted / Submitted)
1001 X-liked Counting 15.15%(35/231)
1002 Buying Snacks 33.18%(70/211)
1003 Ink on paper 19.94%(743/3727)（生成树，或二分答案建图+并查集联通性）
1004 Counting Stars 16.76%(299/1784)（线段树，区间加，乘，标记）
1005 Separated Number 31.65%(138/436)
1006 GCD Game 20.05%(730/3640) (博弈论，nim游戏， 线性筛，质因子个数)
1007 A Simple Problem 0.00%(0/28)
1008 Square Card 22.40%(353/1576)（计算几何，两圆相交面积）
1009 Singing Superstar 28.63%(635/2218)（字符串，AC自动机）
1010 Yinyang 12.73%(7/55)
1003 Ink on paper
题意：
- 给出平面中的n个点，每个点每秒向外扩散0.5cm，求多少时间后所有点的点会连在一起，输出时间的平方。
思路：
- 其实是很简单的最小生成树板子，Kruskal或Prim都行大概O(nlogn)，但是比赛的时候没想到。
- 然后写了个二分答案，二分时间的平方，每次n^2枚举所有的点对建图，并查集维护联通性check时间是否可行，复杂度大概O(n^2logn)，防止超时可以提前预处理出所有点对之间的距离，避免每次重新算一遍。
- 开始用 double 二分的，精度一直WA，后来直接long long 二分时间的平方就过了。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5050;
int fa[maxn+10];
void init(int n){for(int i = 1; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}
LL n, d[maxn][maxn];
struct node{LL x, y; }a[maxn];
LL getd(node x, node y){return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);}
bool check(LL t){
init(n);
int cnt = 1;
for(int i = 1; i <= n; i++){
for(int j = i+1; j <= n; j++){
if(t>=d[i][j]){
if(find(i)!=find(j)){
cnt++;
if(cnt==n)break;
merge(i,j);
}
}
}
if(cnt==n)break;
}
return cnt==n;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T; cin>>T;
while(T--){
cin>>n;
for(int i = 1; i <= n; i++)
cin>>a[i].x>>a[i].y;
for(int i = 1; i <= n; i++)
for(int j = i+1; j <= n; j++)
d[i][j] = getd(a[i],a[j]);
LL l = 0, r = 1e15+10;
while(l < r){
LL mid = (l+r)/2;
if(check(mid))r = mid;
else l = mid+1;
}
cout<<r<<"\n";
}
return 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
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
1004 Counting Stars
题意：
- 给出一个长为n的序列（1e5），支持3种操作：
1：查询[l,r]的区间和
2：修改[l,r]中每个数，都减去lowbit(x)
3：修改[l,r]中每个数，都加上2^k, 2^k<=ai
思路：
- 对于操作2，减去lowbit(x)相当于去掉最后一位的1。可以发现，不断删1后，一个数最多删32次就会变为0，此后修改查询都是0。所以我们可以打个tag表示该区间是否所有数为0，用标记下传维护，剩余的情况暴力修改。
- 对于操作3，加上2^k相当于第一位1左移一位。可以发现，该操作仅与最高位有关，与后面的位无关。所以我们可以把最高位单独维护，操作3相当于整个区间乘2，线段树维护区间乘法即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
const LL mod = 998244353;
LL a1[maxn], a2[maxn];
LL lowbit(LL x){ return x&(-x);}
//线段树：s1维护最高位, s2维护剩余位，tg1表示区间乘2，tg2表示区间全为0。
LL s1[maxn<<2], s2[maxn<<2], tg1[maxn<<2], tg2[maxn<<2];
#define lch p<<1
#define rch p<<1|1
void pushup(int p){ //更新完pushup
s1[p] = (s1[lch]+s1[rch])%mod; //维护区间和
s2[p] = (s2[lch]+s2[rch])%mod; //维护区间和
tg2[p] = tg2[lch]&tg2[rch]; //左右子树都全为0了才为0
}
void pushdown(int p){ //查询前pushdown
tg1[lch] = tg1[lch]*tg1[p]%mod;
tg1[rch] = tg1[rch]*tg1[p]%mod;
s1[lch] = s1[lch]*tg1[p]%mod;
s1[rch] = s1[rch]*tg1[p]%mod;
tg1[p] = 1;
tg2[lch] |= tg2[p];
tg2[rch] |= tg2[p];
if(tg2[lch])s2[lch] = 0;
if(tg2[rch])s2[rch] = 0;
}
void build(int p, int l, int r){
tg1[p] = 1, tg2[p] = 0; //区间乘标记1,全为0标记0。
if(l == r){
s1[p] = a1[l], s2[p] = a2[l];
return ;
}
int mid = l+r>>1;
build(lch, l, mid);
build(rch, mid+1, r);
pushup(p);
}
LL query(int p, int l, int r, int ll, int rr){//return sum{s1+s2}[ll,rr];
if(ll>r || rr<l)return 0;
if(ll<=l && r<=rr){
return (s1[p]+s2[p])%mod;
}
pushdown(p);
int mid = l+r>>1;
LL ans = 0;
ans += query(lch, l, mid, ll, rr);
ans += query(rch, mid+1, r, ll, rr);
ans %=mod;
return ans;
}
void update1(int p, int l, int r, int ll, int rr){//s2[ll,rr]-=lowbit;(暴力)
if(ll>r || rr<l)return ;//区间在范围外
if(tg2[p])return ; //区间全为0，再见
if(l==r){ //到叶节点才能单点暴力修改
if(s2[p]!=0){ s2[p]-=lowbit(s2[p]);}//去掉一个lowbit
else {s1[p]=0; tg2[p]=1;}//除了最高位已经都是0了，那最高位没了
return ;
}
pushdown(p);
int mid = l+r>>1;
update1(lch, l, mid, ll, rr);
update1(rch, mid+1, r, ll, rr);
pushup(p);
}
void update2(int p, int l, int r, int ll, int rr){//s1[ll,rr] *= 2;(Lazy)
if(ll>r || rr<l)return ; //区间完全在范围外
if(ll<=l && r<=rr){ //区间完全被包含
s1[p] = s1[p]*2%mod; //sum[l,r] *= 2;
tg1[p] = tg1[p]*2%mod; //lazy tag, then return ;
return ;
}
pushdown(p);
int mid = l+r>>1;
update2(lch, l, mid, ll, rr);
update2(rch, mid+1, r, ll, rr);
pushup(p);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T; cin>>T;
while(T--){
int n; cin>>n;
for(int i = 1; i <= n; i++){
LL x; cin>>x;
for(int k=30; k>=0; k--){
if((1ll<<k)<=x){ //找到最高位
a1[i] = 1ll<<k; //提取最高位
a2[i] = x-a1[i];//存剩余的数
break;
}
}
}
build(1,1,n);
int q; cin>>q;
for(int i = 1; i <= q; i++){
int op, l, r; cin>>op>>l>>r;
if(op==1)cout<<query(1,1,n,l,r)<<"\n";
else if(op==2)update1(1,1,n,l,r);
else update2(1,1,n,l,r);
}
}
return 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
- 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
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
1006 GCD Game
题意：
- 给出n个数字ai，A和B轮流操作，每次任意选一个数ai，用任意x（1<=x<ai）计算gcd(ai, x)替换ai，不能操作时为输，求谁能赢。
思路：
- nim游戏，把每个数看成一堆石子，石子个数就是每个数的质因子个数，提前用线性筛预处理一下10^7以内的质因子个数就行了，然后每次按照这个取数即可。
- （质因数：gcd(ai,x)一定是ai的因数，相当于每次取走ai一个因数，所有因数都可以被分解成质因数，即有多少个质因数相当于这一堆石头有多少个石子。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e7+10;
int num[maxn];//num[i]维护i的质因子个数
//线性筛
int vis[maxn], primes[maxn], cnt;
void get_primes(int n){
vis[0]=vis[1]=1;
for(int i = 2; i < n; i++){
if(!vis[i])primes[++cnt]=i, num[i]=1;
for(int j = 1; primes[j] <= n/i; j++){
vis[primes[j]*i] = 1;
num[primes[j]*i] = num[i]+1;
if(i%primes[j]==0)break;
}
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
get_primes(maxn-10);
int T; cin>>T;
while(T--){
int n; cin>>n;
int ans = 0;
for(int i = 1; i <= n; i++){
int x; cin>>x; ans ^= num[x];
}
if(ans!=0)cout<<"Alice\n";
else cout<<"Bob\n";
}
return 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
- 37
1008 Square Card
题意：
- 给出两个圆，分别代表得分区域和奖励区域，边长为a的正方形卡片以均等概率扔到平面后绕得分区域的圆心旋转。
- 如果某一刻卡片完整的落在得分区域或奖励区域内，它将获得相应的分数，求卡片同时获得奖励和得分的概率 比 卡片单独获得得分的概率 的比率。
思路：
- 可以发现，要使正方形卡片有可能被一个圆完全包含，它的中心轨迹一定是一个圆，所以本题就转化为了计算两圆相交面积与第一个圆面积的比值。
- 一些细节：如数据中奖励区域不一定能完全包含卡片的不同情况要加特判。
- printf和cin一起用，关了流同步会WA。
#include<bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
//求两圆相交面积
struct point{int x, y;};
double area(point a, double r1, point b, double r2){
double d = sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
if(d >= r1+r2)return 0;
if(r1 > r2)swap(r1,r2);
if(r2-r1>=d)return pi*r1*r1;
double ang1 = acos((r1*r1+d*d-r2*r2)/(2*r1*d));
double ang2 = acos((r2*r2+d*d-r1*r1)/(2*r2*d));
return ang1*r1*r1 + ang2*r2*r2 - r1*d*sin(ang1);
}
int main(){
int T; cin>>T;
while(T--){
double ra,xa,ya,rb,xb,yb,aa;
cin>>ra>>xa>>ya>>rb>>xb>>yb>>aa;
if(rb*rb-aa*aa/4<0){cout<<"0.000000\n"; continue;}
point a = point{(int)xa,(int)ya}, b = point{(int)xb,(int)yb};
double r1 = sqrt(ra*ra-aa*aa/4)-aa/2, r2 = sqrt(rb*rb-aa*aa/4)-aa/2;
double res = area(a, r1, b, r2);
printf("%.6f\n", res/(pi*r1*r1));
}
return 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
1009 Singing Superstar
题意：
- 给出一个长度小于1e5的字符串s，q<1e5次询问，每次问一个长小于30的串t在s中的出现次数，t不可重叠。
思路：
- 开始写了个循环n遍kmp TLE了，算了一下复杂度大概O((|s|+30)*q)，肯定超时。然后写了个字典树将原先字符串s每隔30个字母插入字典树询问，但是这样获得的结果是t可以重叠时的答案。
- 最后想到kmp+字典树不如直接上自动机，找了一下ZOJ3228的板子改了一下，过了。对于允许重叠的情况，就是裸的AC自动机，不允许重叠的只需要：记录trie树上每个结尾节点一次匹配是在长串的哪个位置，若这次与上次不重叠则记录。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
struct node{ int type, index; char s[30];}a[maxn];
struct AC{
int num,ch[6*maxn][30],f[6*maxn],last[6*maxn],val[6*maxn];
int times[6*maxn][2],dep[7*maxn],pos[6*maxn];
void init(){
num=0;
memset(ch,0,sizeof(ch));
memset(f,0,sizeof(f));
memset(last,0,sizeof(last));
memset(val,0,sizeof(val));
memset(times,0,sizeof(times));
memset(dep,0,sizeof(dep));
memset(pos,-1,sizeof(pos));
return;
}
void insert(char *s,int qN){
int u=0,len=strlen(s),id;
for(int i=0;i<len;i++){
id=s[i]-'a';
if(!ch[u][id])ch[u][id]=++num;
u=ch[u][id];
}
val[u]=1;
dep[u]=len;
a[qN].index=u;
return;
}
void getfail(){
queue<int> Q;
Q.push(0);
int x,u,v;
while(!Q.empty()){
x=Q.front();Q.pop();
for(int i=0;i<26;i++){
u=ch[x][i];
if(!u){
ch[x][i]=ch[f[x]][i];
continue;
}
Q.push(u);
if(x==0) continue;
v=f[x];
while(v&&!ch[v][i]) v=f[v];
f[u]=ch[v][i];
last[u]=val[f[u]]?f[u]:last[f[u]];
}
}
return;
}
void find(char *s){
memset(times,0,sizeof(times));
int len=strlen(s),u=0,id,j;
for(int i=0;i<len;i++){
id=s[i]-'a';
u=ch[u][id];
j=u;
do{
times[j][0]++;
if(i-pos[j]>=dep[j]){
times[j][1]++;
pos[j]=i;
}
j=last[j];
}while(j);
}
return;
}
}ac;
int main(){
int T; cin>>T;
while(T--){
char s[maxn]; scanf("%s", s);
ac.init();
int q; cin>>q;
for(int i = 1; i <= q; i++){
scanf("%s", a[i].s);
a[i].type = 1; //不可重叠
ac.insert(a[i].s, i);
}
ac.getfail();
ac.find(s);
for(int i = 1; i <= q; i++){
if(a[i].type==0)printf("%d\n",ac.times[a[i].index][0]);
else printf("%d\n",ac.times[a[i].index][1]);
}
}
return 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
- 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
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。
原文链接：gwj1314.blog.csdn.net/article/details/119649303
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）