Preface
周末紧张刺激的两连赛，周六打完篮球杯后周日就要打百度之星的第一场省赛
由于第二场时间和四川省赛冲突了，第三场时间又在考试前一天，比较阴间，想着最好是一次打进决赛节省点钱和时间
虽然学校不报销去北京决赛的钱，但转念一想反正XCPC也都不报销也差不了多少，去北京旅个游也未尝不可
回到这场比赛，虽然总体来看感觉一堆Math Problem恰逢软肋（怎么和蓝桥杯一样），但好在比赛的时候选择开自己擅长的大分类讨论和大模拟，最后40minRush第六题也把思路出的七七八八了
最后写出前5题，总排Rank25，看了眼大学组里好像排Rank3，比较可惜的是和大学组Rank1的川大✌差了半小时的罚时，如果P3或者P5少WA两发就好了（但这种题不WA感觉是不可能的）
由于百度之星在自己电脑上存了代码，因此就和一般的题解一样顺便讲下做法吧，但现在题目还没公开因此题目名就先用个序号代替吧
P1
这题没啥好说的，看到数据范围就知道直接\(O(n^2)\)甚至\(O(n^2\log n)\)模拟一遍即可
当然由于每次只有一个位置会发生变化，理论上可以用平衡树/线段树等东西来做到\(O(n\log n)\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
int n,ans,B,p[N],s[N],w[N];
int main()
{
RI i,j; for (scanf("%d%d",&n,&B),i=1;i<=n;++i) scanf("%d%d",&p[i],&s[i]);
for (i=1;i<=n;++i)
{
for (j=1;j<=n;++j)
if (i==j) w[j]=p[j]/2+s[j]; else w[j]=p[j]+s[j];
sort(w+1,w+n+1); int cnt=0; long long sum=0;
for (j=1;j<=n;++j)
if (sum+w[j]<=B) sum+=w[j],++cnt; else break;
ans=max(ans,cnt);
}
return printf("%d",ans),0;
}
P2
很有CF风格的一个题，难点在于求\(1\sim n\)的\(\operatorname{LCM}\)，如果实现不够精细的话可能会在这里T掉
首先不妨设\(M=\operatorname{LCM}(1,2,\dots,n)\)，则第\(i\)个人最后会跑\(\frac{M}{i}\)圈
显然对于两个人\(i,j(i<j)\)，它们相遇的次数就是\(\frac{M}{i}-\frac{M}{j}\)
然后这个二维的求和式子很容易化成一维的，直接考虑第\(i\)个人的系数就是\(n-2i+1\)，用这个值乘上\(\frac{1}{i}\)求和后，最后乘上\(M\)即可
现在的问题就是怎么快速计算\(M\)，根据经典套路还是想到要把数分解质因数后比较好统计
对于质因数\(p_i\)，不妨设\(1\sim n\)中它出现且指数最大值为\(c_i\)，则其贡献就是\(p_i^{c_i}\)
可以先筛出\(1\sim n\)中所有的质数，然后暴力计算每个数最大的指数，这部分复杂度是\(O(\pi(n)\times \log n)\)，差不多就是\(O(n)\)
最后总复杂度为\(O(n)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1e7+5,mod=998244353;
int n,M,fact[N],ifac[N],inv[N],ans,p[N],cnt,vis[N];
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
for (ifac[n]=quick_pow(fact[n]),i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
for (i=1;i<=n;++i) inv[i]=1LL*fact[i-1]*ifac[i]%mod;
}
inline void sieve(CI n)
{
for (RI i=2;i<=n;++i)
{
if (!vis[i]) p[++cnt]=i;
for (RI j=1;j<=cnt&&i*p[j]<=n;++j)
if (vis[i*p[j]]=1,i%p[j]==0) break;
}
}
int main()
{
RI i; for (scanf("%d",&n),init(n),i=1;i<=n;++i)
(ans+=1LL*inv[i]*(n-2*i+1+mod)%mod)%=mod;
for (sieve(n),M=1,i=1;i<=cnt;++i)
{
int c=0; long long ret=1;
while (ret*p[i]<=n) ret*=p[i],++c;
M=1LL*M*quick_pow(p[i],c)%mod;
}
return printf("%d",1LL*ans*M%mod),0;
}
P3
这题其实没啥思维难度，因为就是纯爆搜，但由于写起来比较繁琐导致最后过的人就不是很多吧，反正很适合我这种写不来思维题的人去大力硬干
首先先大力BFS搜出连通块并判掉连通块数量\(>1\)的情况后，并且对于没有黑子的情况要人为地加一个子进去
由于数据范围很小，我们就考虑每次在一个合法的连通块的所有与之连通的格子中挑选一个扩展，因此现在问题集中在如何判断一个连通块是否和另一个同构
考虑用二维坐标来表示一个黑子的位置，并将所有黑子的位置存入vector中
将vector中的所有坐标排序后，将每个点的坐标统一减去第一个点的坐标，即可消除平移同构的影响
（因为这样相当于定下一个基准点并放到\((0,0)\)处，然后把所有点的坐标都转化为和它的相对位置，显然可以去除平移带来的影响）
接下来考虑旋转同构和对称同构，这个也很简单，直接用对应的变换公式把所有点的坐标变换一下即可
注意这些操作之间是可以组合的，因此我在实现时选择枚举顺时针旋转的次数\(r\in[0,3]\)，水平镜像的次数\(fx\in[0,1]\)，垂直镜像的次数\(fy\in[0,1]\)
算出对应的点集后用前面的方法去除平移的影响后，扔到set <vector <int>>里就可以判重了，最后输出这个set的大小即可
另外实现的时候还要注意连通块不能超出棋盘大小\(n\times m\)，具体地只需判断点集横纵坐标的极差是否小于等于\(n,m\)即可
具体实现可以看代码，感觉思路还是很自然的，难点在于怎么优美地处理各种同构操作
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<set>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=15,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
struct Point
{
int x,y;
inline Point(CI X=0,CI Y=0)
{
x=X; y=Y;
}
friend inline bool operator < (const Point& A,const Point& B)
{
return A.x!=B.x?A.x<B.x:A.y<B.y;
}
friend inline Point operator - (const Point& A,const Point& B)
{
return Point(A.x-B.x,A.y-B.y);
}
inline void rotate(void)
{
int tx=x,ty=y; x=ty; y=-tx;
}
inline void flip_x(void)
{
y=-y;
}
inline void flip_y(void)
{
x=-x;
}
};
int t,k,n,m,a[N][N],vis[N][N]; set <vector <Point>> rst;
inline void BFS(CI x,CI y)
{
queue <Point> q; q.push(Point(x,y)); vis[x][y]=1;
while (!q.empty())
{
auto [x,y]=q.front(); q.pop();
for (RI i=0;i<4;++i)
{
int nx=x+dx[i],ny=y+dy[i];
if (nx<1||nx>n||ny<1||ny>m) continue;
if (a[nx][ny]==1&&!vis[nx][ny])
q.push(Point(nx,ny)),vis[nx][ny]=1;
}
}
}
inline void normal(vector <Point>& vec)
{
sort(vec.begin(),vec.end()); Point st=vec[0];
for (auto &it:vec) it=it-st;
}
inline int calcx(vector <Point>& vec)
{
int mnx=vec[0].x,mxx=mnx;
for (auto [x,y]:vec) mnx=min(mnx,x),mxx=max(mxx,x);
return mxx-mnx+1;
}
inline int calcy(vector <Point>& vec)
{
int mny=vec[0].y,mxy=mny;
for (auto [x,y]:vec) mny=min(mny,y),mxy=max(mxy,y);
return mxy-mny+1;
}
inline bool check(vector <Point>& vec)
{
int bx=calcx(vec),by=calcy(vec);
if ((bx<=n&&by<=m)||(by<=n&&bx<=m))
{
for (RI r=0;r<4;++r)
for (RI fx=0;fx<2;++fx)
for (RI fy=0;fy<2;++fy)
{
vector <Point> tmp=vec;
for (RI i=1;i<=r;++i)
{
for (auto &it:tmp) it.rotate();
}
if (fx)
{
for (auto &it:tmp) it.flip_x();
}
if (fy)
{
for (auto &it:tmp) it.flip_y();
}
normal(tmp);
if (rst.count(tmp)) return 0;
}
return 1;
} else return 0;
}
inline void DFS(vector <Point> vec,CI k)
{
rst.insert(vec);
if (k==0) return;
set <Point> ext;
for (auto it:vec) ext.insert(it);
for (auto [x,y]:vec)
{
for (RI i=0;i<4;++i)
{
int nx=x+dx[i],ny=y+dy[i];
if (ext.count(Point(nx,ny))) continue;
vector <Point> tmp=vec; tmp.push_back(Point(nx,ny));
normal(tmp); if (check(tmp)) DFS(tmp,k-1);
}
}
}
int main()
{
for (scanf("%d",&t);t;--t)
{
RI i,j; for (scanf("%d%d%d",&k,&n,&m),i=1;i<=n;++i)
for (j=1;j<=m;++j) scanf("%d",&a[i][j]);
int tot=0; Point st; memset(vis,0,sizeof(vis));
for (i=1;i<=n;++i) for (j=1;j<=m;++j)
if (a[i][j]==1&&!vis[i][j]) st=Point(i,j),BFS(i,j),++tot;
if (tot>=2) { puts("-1"); continue; }
vector <Point> vec;
if (tot==0)
{
if (k==0) { puts("1"); continue; }
--k; st=Point(0,0); vec.push_back(st);
}
for (i=1;i<=n;++i) for (j=1;j<=m;++j)
if (a[i][j]==1) vec.push_back(Point(i,j)-st);
normal(vec); rst.clear(); DFS(vec,k); printf("%d\n",rst.size());
}
return 0;
}
P4
这题比赛的时候写完前两题后看了眼榜就先跟了这个题，还是非常典的
看一眼数据范围可以\(O(n^2)\)，那就直接大力设状态\(f_{i,j,p=0/1,q=0/1}\)表示处理了前\(i\)个位置，一共修改了\(j\)次，且当前\(a_{i-1}\)和\(a_i\)的值分别为\(p,q\)时的方案数
转移的话十分trivial就不再赘述，值得一提的是这题空间限制很小，需要把第一维滚存
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=5005,mod=998244353;
int n,m,f[2][N][2][2],a[N]; char s[N];
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
int main()
{
RI i,j,p,q; scanf("%d%d%s",&n,&m,s+1);
for (i=1;i<=n;++i) a[i]=s[i]-'0';
if (n==1||n==2) return printf("%d",1<<min(n,m)),0;
f[0][0][a[1]][a[2]]=1;
f[0][1][a[1]^1][a[2]]=1;
f[0][1][a[1]][a[2]^1]=1;
f[0][2][a[1]^1][a[2]^1]=1;
for (i=2;i<n;++i)
{
int now=i&1,nxt=now^1;
for (j=0;j<=m;++j) for (p=0;p<2;++p) for (q=0;q<2;++q) f[nxt][j][p][q]=0;
for (j=0;j<=m;++j) for (p=0;p<2;++p) for (q=0;q<2;++q)
if (f[now][j][p][q])
{
if (!(p==1&&q==1&&a[i+1]==0))
inc(f[nxt][j][q][a[i+1]],f[now][j][p][q]);
if (!(p==1&&q==1&&a[i+1]==1))
inc(f[nxt][j+1][q][a[i+1]^1],f[now][j][p][q]);
}
}
int ans=0; for (i=0;i<=m;++i)
for (p=0;p<2;++p) for (q=0;q<2;++q) inc(ans,f[n&1][i][p][q]);
return printf("%d",ans),0;
}
P5
分类讨论你罪大恶极，写这种东西确实挺容易让人红温的，不过好在那天状态挺好WA了两发后就过了
首先一个大致的思路就是要把正数和负数分开，然后两边单独算出一个最大/最小值来算极差
考虑对于若干个符号相同的非负数（非正数的情况同理），如果数的数量\(\ge 2\)，则最后能得到的最大数就是所有数之和再加上最大数；否则就只能得到那个数本身
因此我们首先可以看出\(0\)的作用来，我们首先搞出两个集合\(P,N\)分别放入正数和负数，同时记\(z\)表示\(0\)的数量
显然把\(0\)归到\(P,N\)中都是可以的，但不同的归法对上面式子的计算会有影响，不过好在我们稍微思考后就能发现每个集合中放入一个\(0\)和放入多个\(0\)是等价的，因此这部分可以枚举讨论一下
然后还有一大类情况就是没有正数/负数的情况，以没有负数为例
显然如果此时有\(0\)就直接钦定\(0\)为最小值，剩下部分用上述规则构造出最大值是最优的
否则分情况讨论，如果此时只有两个数，则答案为最大的那个正数，比如\(3,5\)这种情况，我们可以先操作一次把序列变成\(8,5\)
否则钦定最小的那个数为最小值，剩下部分用上述规则构造出最大值，相减得到的结果一定最优
然后写完后感觉自信满满直接提交，直接返回满屏的WA，遂开始反思漏了什么Corner Case
由于出错的情况肯定是数很少的时候，因此索性手动枚举各种情况，然后发现了\(-3,-2,-1,100\)这组数据
按照之前正负分开的规则最小能构造出\(-9\)，最大就是\(100\)不变，最后答案就是\(109\)
但实际上我们可以先用\(-3,-2\)构造出\(-8\)，再用\(-1,100\)构造出\(199\)，最后答案就是\(207\)
这就提醒我们还需要讨论一种情况，即可以把每个集合中绝对值最小的那个数放到另一个集合中，看看答案是否会变大
然后写完交一发发现又挂了，后面手玩了下发现原来是只有一个正数和一个负数的情况就不能这样移动了，因此需要再特判一下移动后对应的集合不能为空
把上面的Case全部讨论清楚就可以通过此题了，上述做法仅代表我个人比赛时的思路过程，更加简单的分类方法应该也是有的，但只要能过题都是好方法
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
int t,n,x;
signed main()
{
for (scanf("%lld",&t);t;--t)
{
RI i; vector <int> P,N; int zero=0;
for (scanf("%lld",&n),i=1;i<=n;++i)
{
scanf("%lld",&x);
if (x==0) ++zero; else
if (x>0) P.push_back(x); else N.push_back(-x);
}
if (n==1) { puts("0"); continue; }
if (P.empty()&&N.empty()) { puts("0"); continue; }
sort(P.begin(),P.end(),greater <int>());
sort(N.begin(),N.end(),greater <int>());
auto calc=[&](vector <int>& vec,CI z)
{
int sum=0; for (auto x:vec) sum+=x;
if (vec.size()+z>=2&&!vec.empty()) sum+=vec[0];
return sum;
};
if (N.empty())
{
if (zero) printf("%lld\n",calc(P,zero-1));
else
{
if (P.size()==2) printf("%lld\n",P[0]); else
{
int tmp=P.back(); P.pop_back();
printf("%lld\n",calc(P,0)-tmp);
}
}
continue;
}
if (P.empty())
{
if (zero) printf("%lld\n",calc(N,zero-1));
else
{
if (N.size()==2) printf("%lld\n",N[0]); else
{
int tmp=N.back(); N.pop_back();
printf("%lld\n",calc(N,0)-tmp);
}
}
continue;
}
auto solve=[&](vector <int>& P,vector <int>& N)
{
int ret=0; for (RI i=0;i<=min(1LL,zero);++i)
ret=max(ret,calc(N,i)+calc(P,zero-i)); return ret;
};
int ans=solve(P,N); vector <int> TP=P,TN=N;
if (N.size()>1)
{
P.push_back(-N.back()); N.pop_back();
sort(P.begin(),P.end(),greater <int>()); ans=max(ans,solve(P,N));
}
P=TP; N=TN;
if (P.size()>1)
{
N.push_back(-P.back()); P.pop_back();
sort(N.begin(),N.end(),greater <int>()); ans=max(ans,solve(P,N));
}
printf("%lld\n",ans);
}
return 0;
}
P6
感觉很有意思的一个构造题，比赛的时候想到了二分找最大的填数位置然后贪心往下检验，但没想到最后多出的数很少可以直接处理
主要感觉还是时间不足没有去跑一下\(10^{11}\)看下剩下来几个数的缘故
首先如果\(n\)比较小时有个很自然的做法，就是把数一个个加进去，初始时都默认加在\(1\)号位置
显然我们可以发现这样一个Rule，如果当前\(1\)号位置有至少\(2\)个数，且\(2\sim i\)号位置都有至少\(1\)个数，同时\(i+1\)号位置是空的
那我们显然可以把\(1\sim i\)这\(i+1\)个数全部放到\(i+1\)位置上，这个做法的正确性显然，用线段树维护每个位置的值，然后线段树上二分查询第一个\(0\)即可
但现在的问题是\(n=10^{11}\)没法直接这样处理，那我们不妨转换思路，根据题目的性质，下标最靠后的位置\(x\)填的数一定是\(x\)
而根据反字典序的比较规则，\(x\)的值是区分方案的第一要素，因此我们可以先利用二分找到最大的\(x\)，并先构造一组合法的方案
验证的过程也很自然，给位置\(x\)填上\(x\)后，从高到低枚举每个位置，由于知道后面会有多少个数分下来，因此就能算出当前位置最少要填多少数才能满足要求，直接暴力往下处理即可
由于这样计算最少所需的数时，枚举的次数大致是\(O(\sqrt n)\)级别的，因此复杂度也是正确的
最后按照这样方法显然会多出一部分数，但实际跑一下后会发现\(n=10^{11}\)时大概会剩下\(300000\)个数，同时放到的最大的位置大概是\(560000\)左右
那么我们对多出的这部分直接跑一开始讲的那个做法即可，然后这题就做完了
不过由于题目还没开放同时接下来一堆期末考试，代码就先坑着了等题目放出来/考试考完后再来补吧
Postscript
剩下的两个题比赛的时候都没怎么看，后面看榜后感觉也不是我这种水平能做的题，暂且就先坑着了
这个学期剩下的比赛应该就只有6.18的省赛了，希望有银牌✌加持，把冠军留在UESTC吧
标签：CI,int,back,初赛,2024,vec,include,之星,RI From： https://www.cnblogs.com/cjjsb/p/18231027