CQUPT 2025级 数据科学与大数据技术英才班 周测#04

CQUPT 2025级 数据科学与大数据技术英才班 周测#04

A 约瑟夫问题

链表

经典问题，写法有很多：

• 解法1：数组模拟链表

  数组 \(nxt[i]\) 表示第 \(i\) 个人的后一个人是谁，然后 \(nxt[n]=1\) 首尾相连成环即可。

  scanf("%d%d",&n,&m);
  for(int i=1;i<n;i++)nxt[i]=i+1;
  nxt[n]=1;int pos=1;
  while(nxt[pos]!=pos)
  {for(int i=1;i<m-1;i++)pos=nxt[pos];printf("%d ",nxt[pos]);nxt[pos]=nxt[nxt[pos]];pos=nxt[pos];
  }
  printf("%d\n",nxt[pos]);
  

• 解法2：指针模拟链表

  struct Link
  {int dat;struct Link *Next;
  };struct Link *add(struct Link *head,int x)
  {struct Link *p=NULL,*pr=head;p=(struct Link *)malloc(sizeof(struct Link));while(pr->Next!=NULL)pr=pr->Next;pr->Next=p;p->dat=x;p->Next=NULL; return head;
  }
  

  scanf("%d%d",&n,&m);struct Link *head=NULL;
  head=(struct Link *)malloc(sizeof(struct Link));
  head->dat=1;
  head->Next=NULL; 
  for(int i=2;i<=n;i++)head=add(head,i);
  struct Link *p=head;
  while(p->Next!=NULL)p=p->Next;
  p->Next=head;p=head;
  int cnt=0;
  struct Link *pr=head;
  while(p->Next!=p)
  {cnt++;if(cnt%m==0){printf("%d ",p->dat);p=p->Next;pr->Next=p;}else{pr=p;p=p->Next;}
  }
  printf("%d\n",p->dat);
  

当然，本题也可以不用链表做，洛谷的题解里有很多做法，可以自行学习。

B Cities and States S

map

对于一个城市，城市前两个字母为字符串 \(s\)，所在州为 \(s2\)

那么我们需要统计有多少个城市前两个字母为 \(s2\)，所在州 \(s\)

字符串的数量不方便统计，可以使用 map：map<string,int> ma;

统计数量即可。注意特判 \(s=s2\) 的情况

scanf("%d",&n);
for(int i=1;i<=n;i++)
{string s,s1,s2;cin>>s1>>s2;s=s1[0]; s+=s1[1];if(s==s2) continue;ans=(LL)ans+ma[s+s2];ma[s2+s]++;
}
printf("%lld\n",ans);

C Swappable

map 或 vector

题意很简单，但是 \(a[i]\) 的范围很大，不能用数组下标统计 \(a[i]\) 出现了几次

• 解法1：

  考虑 map：map<int,int> ma;

  直接统计前 \(i-1\) 个数中有几个数和 \(a[i]\) 不相等不太方便

  正难则反，统计前 \(i-1\) 个数中有几个数和 \(a[i]\) 相等，不相等的数有 \(i-1-ma[a[i]]\) 个

  scanf("%d",&n);
  for(int i=1;i<=n;i++)
  {int x;scanf("%d",&x);ans+=i-1-ma[x];ma[x]++;
  }
  printf("%lld\n",ans);
  

• 解法2：

  虽然 \(a[i]\) 很大，但是对于本题我们 并不关心每个数具体值是多少，只关心每个数的相对大小

  而 \(a[i]\) 最多有 \(n\) 的不同的值，\(n\) 并不大，所以可以使用 离散化：vector + lower_bound

  scanf("%d",&n);
  for(int i=1;i<=n;i++)
  {scanf("%d",&a[i]);vec.push_back(a[i]);
  }sort(vec.begin(),vec.end());
  vec.erase(unique(vec.begin(),vec.end()),vec.end());
  for(int i=1;i<=n;i++)a[i]=lower_bound(vec.begin(),vec.end(),a[i])-vec.begin()+1;for(int i=1;i<=n;i++)
  {ans+=i-1-cnt[a[i]];cnt[a[i]]++;
  }
  printf("%lld\n",ans);
  

D Ringo's Favorite Numbers 2

map

和上题类似

需要考虑一个性质：若 \((a-b)/c=0\)，则 \(a\%c=b\%c\)，记作 \(a\) 和 \(b\) 同余：\(a\equiv b \pmod c\)

那么我们可以用 map 统计 \(a[i]\%200\) 出现了几次，累加即可

scanf("%d",&n);
for(int i=1;i<=n;i++)
{int x;scanf("%d",&x);x%=200;ans+=ma[x];ma[x]++;
}
printf("%lld\n",ans);

E Counting Arrays

map + vector

统计有几个不重复的序列，序列可以用 vector 来存

用 map 标记序列是否出现过：map<vector<int>,int> ma;

scanf("%d",&n);
for(int i=1;i<=n;i++)
{int cnt;scanf("%d",&cnt);vector<int> vec;for(int j=1;j<=cnt;j++){int x;scanf("%d",&x);vec.push_back(x);}if(!ma[vec]) ans++;ma[vec]=true;
}
printf("%d\n",ans);

F 2x2 Placing

map + pair 或 结构体

直观想法，开一个二维数组，按照题意模拟，统计放置了多少个图块。

观察数据范围，\(1\leq M \leq 2 \times 10^{5}\)，需要开大小为 \(4\times 10 ^{10}\) 的数组，但是最大空间限制为 \(1024 Mb\)，会爆空间。所以转换思路，使用 map。

• 解法1：map + 结构体

  由于 map 存储的内容必须有序，需要重载运算符，有点麻烦

  struct node
  {int x,y;
  };bool operator < (node x,node y)
  {if(x.x!=y.x) return x.x<y.x;else return x.y<y.y;
  }map<node,bool> ma;
  

• 解法2：map + pair

  pair 默认有序，可以直接作为 map 的下标

  map<pair<int,int>,bool> ma;
  

两种做法在定义时有区别，后续过程完全一致

scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{int r,c;scanf("%d%d",&r,&c);if(ma[{r,c}]||ma[{r+1,c}]||ma[{r,c+1}]||ma[{r+1,c+1}]) continue;ma[{r,c}]=ma[{r+1,c}]=ma[{r,c+1}]=ma[{r+1,c+1}]=true;cnt++;
}
printf("%d\n",cnt);

• 解法3：map

  如果前两种方法都不会，也可以只使用 map 做。

  可以自定义 \(calc\) 函数 将二维坐标转换为一维

  inline LL calc(int x,int y)
  {return (LL)x*n+y;
  }map<LL,bool> a;
  

  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++)
  {int r,c;scanf("%d%d",&r,&c);if(a[calc(r,c)]||a[calc(r+1,c)]||a[calc(r,c+1)]||a[calc(r+1,c+1)]) continue;a[calc(r,c)]=a[calc(r+1,c)]=a[calc(r,c+1)]=a[calc(r+1,c+1)]=true;cnt++;
  }printf("%d\n",cnt);
  

G 木材仓库

set + 二分

存储不相同的木材长度，可以想到 set：set<int> ss;

主要用到 set 中的 insert()，erase()，find()，lower_bound() 等函数

按照题意模拟即可

scanf("%d",&n);
for(int i=1;i<=n;i++)
{int op,x;scanf("%d%d",&op,&x);if(op==1){if(ss.find(x)!=ss.end()) puts("Already Exist");else ss.insert(x);}else{if(ss.empty()) puts("Empty");else if(ss.find(x)!=ss.end()){printf("%d\n",x);ss.erase(x);}else{auto it=ss.lower_bound(x);if(it==ss.begin()) // 全部木材都 ≥x{printf("%d\n",*it);ss.erase(it);}else if(it==ss.end()) // 全部木材都 ＜x{it--;printf("%d\n",*it);ss.erase(it);}else{auto it1=it;it1--;if(abs(x-*it1)>abs(x-*it)){printf("%d\n",*it);ss.erase(it);}else {printf("%d\n",*it1);ss.erase(it1);}}}}
}