A.长春花
简单题。打表发现情况并不多，记录下平方后模 \(p\) 对应的值，然后枚举 \(a\)，用链表维护即可。
点击查看代码
#include<bits/stdc++.h>
using ll=long long;using ull=unsigned long long;
int a[100005],b[100005],p,ans,mx;
bool vis[100005];
std::list<int> l;
std::stack<std::list<int>::iterator> stk;
int main(){
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cin>>p;
for(int i=0;i<=p-1;++i){
int mo=1ll*i*i%p;
l.push_back(i);
if(!vis[mo])vis[mo]=true,a[i]=b[i]=mo,mx=i;
}
for(int i=0,lst;i<=mx;++i){
for(auto it=l.begin();it!=l.end();++it){
lst=(*it-a[i]+p)%p;
if(vis[lst])stk.push(it),ans=i;
}
while(!stk.empty())l.erase(stk.top()),stk.pop();
}
std::cout<<ans;
return 0;
}
B.紫罗兰
无向无权图求最小环的个数。
考场上用 Floyd 找最小环，只有 55pts。
正解是以每个点为源点 bfs。把最短路拼成最小环，记录方案数。
根据 bfs 的性质，队列中的元素任何时刻至多只有两个层次的节点。我们可以判断当前搜索的节点是否被访问过。
如果当前搜索的节点未被访问过就更新最短路和方案数，否则就更新下最小环的长度和个数。虽然不能保证该环为简单环，但所有情况拼成的环中一定存在简单环，所以对所有的环长度取 \(\min\) 就一定是最小环。
这样求出的长度为 \(L\) 的最小环会被重复搜 \(L\) 遍，所以答案要除以 \(L\)。\(L\) 为奇数时，\(dis_i=dis_j\) 会被算两次，还要除以 \(2\)。
直接粘的 chancelong 赛时的代码加了点注释。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int>edge[3010];
int n,m;
int minn=2e9+10;
int tot=0;
int dis[3010],len[3010];//dis:源点到点i的最短路 len:源点到点i最短路的方案数
void search(int x){
queue<int>q;
memset(dis,0x3f,sizeof(dis));
memset(len,0,sizeof(len));
q.push(x);
dis[x]=0,len[x]=1;
while(!q.empty()){
int i=q.front();
q.pop();
for(auto j:edge[i]){//i->j
// 搜索到环: x->...i->j->...x
int turnd=dis[i]+dis[j]+1;//环的长度
int turnc=len[i]*len[j];//求拼成环的方案数
if(dis[j]==dis[i]||dis[j]==(dis[i]+1)){//j节点已被访问过
if(turnd<minn){
minn=turnd;
tot=turnc;
}
else if(turnd==minn){
tot+=turnc;
}
}
if(dis[j]>dis[i]+1){
dis[j]=dis[i]+1;
len[j]=len[i];
q.push(j);
}
else if(dis[j]==dis[i]+1){
len[j]+=len[i];
}
}
}
}
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
edge[x].push_back(y);
edge[y].push_back(x);
}
for(int i=1;i<=n;i++){
search(i);
}
tot/=minn;
if(minn%2)tot/=2;
cout<<tot;
}
C.天竺葵
这基本就是 LIS 吧......
朴素的转移方程：\(f_i=\max_{1\le j<i}\{f_j+1\}(a_j b_{f_j}<a_i)\)
这样直接做是 \(O(n^2)\) 的。
考虑像 LIS 一样的优化，贪心地想，末尾肯定是越小越容易往后接东西。所以定义 \(f_i\) 为长度为 \(i\) 的子序列末尾 \(a b_i\) 的最小值。转移的时候直接二分查找转移点即可，复杂度 \(O(n\log n)\)。
点击查看代码
#include<bits/stdc++.h>
using ll=long long;using ull=unsigned long long;
int n,ans;
ll a[1000005],b[1000005],f[1000005];
int main(){
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cin>>n;
for(int i=1;i<=n;++i)std::cin>>a[i];
for(int i=1;i<=n;++i)std::cin>>b[i];
memset(f,0x3f,sizeof f);
for(int i=1;i<=n;++i){
int pos=std::lower_bound(f+1,f+1+ans,a[i])-f;
ans=std::max(ans,pos);
f[pos]=std::min(f[pos],b[pos]*a[i]);
}
std::cout<<ans;
return 0;
}
D.风信子
类似于 超级钢琴。那道题是把询问元组放入堆中，每次取最大值，根据答案的位置把询问分裂开再放入堆中维护。
我直接搬官方题解吧(
这场暴力分比较多，T1 T3比较简单。T2 找环应该想到 bfs，但不知道为啥用 Floyd 只有 55。我估的 70 啊www
T4 部分分应该有 65。但 \(k=1\) 拿线段树维护的 15 分没打完。
标签：std,int,long,联测,len,using,2023NOIP,dis From： https://www.cnblogs.com/UNowen/p/17758239.html