牛客小白月赛88（A,B,C,D,E,F,G）

这场神中神，题型都很新，学到了很多。比赛链接，官方视频讲解，出题人题解

这场官方讲解我觉得讲的还是很好的。

D是个不太裸的DP，是01背包的变种。

E有三种做法，在前两天的abc（atcoder beginner contest）出过一个弱化的一模一样的题，这题正解是逆推（题解说这个是并查集，感觉不像，顶多算沾点思想），次正解是个启发式合并，我赛时瞎搞出来一个并查集做法，也一并拿过来说了。

F是个暴力，不过需要看出来一个结论来减枝。这题有个超级涩情 nb的结论，我是不会证的。也没看到有讲的。有大佬会的话希望能不吝赐教。

G是个计算几何。之前没做过，用的高中知识瞎搞出来了。正解是用向量，可以向量旋转，再用个正弦定理就完事了。神！

A 超级闪光牛可乐

思路：

一定至少有一种零食，而这种零食至少有 $1$ 点的诱惑力。最多能吃 $1000$ 袋，再怎么说也够用了，所以直接输出 $1000$ 次第一种零食就完事了。

code：

#include #include using namespace std;int x,n;char ch;int main(){cin>>x>>n>>ch;for(int i=1;i<=1000;i++)cout<<ch;return 0;}

B 人列计算机

思路：

每一行的字符串有可能不相连，因此需要整行读入字符串，用 $getline$ 就行了。这个本来是 $istream$ 类中的一个成员函数，用于读入字符串并返回首字符指针，在 $cstring$ 中重载了一下，可以读入 $string$。

然后根据一些不同的信息判定是哪个门的一种，提取输入信息。然后输出结果即可。

code：

#include #include #include using namespace std;string s[10];bool x,y;int main(){for(int i=1;i<=5;i++)getline(cin,s[i]);if(s[3].substr(4,3)==" & "){x=s[2][0]=='1';y=s[4][0]=='1';cout<<(x&y);}else if(s[3].substr(4,3)==">=1"){x=s[2][0]=='1';y=s[4][0]=='1';cout<<(x|y);}else {cout<<(s[3][0]=='0');}return 0;}

C 时间管理大师

思路：

众所周知，$24$ 时制本质是个 $60$ 进制数，所以可以把它转化为 $10$ 进制数（其实就是把时，分都拆成秒，不过这题没用到秒，所以时拆成分就够用了），再把 $0$ 时 $0$ 分看作基准时刻（也就是 $0$ 时刻）。这样就可以方便的找到某个时刻前 $1,3,5$ 分钟时刻对应的 $10$ 进制数了，用 $set$ 去一下重，再转化为 $60$ 进制数输出即可。

code：

#include #include #include using namespace std;int n;set<int> s;int main(){cin>>n;for(int i=1,tm,tmp;i<=n;i++){cin>>tmp;tm=tmp*60;cin>>tmp;tm+=tmp;s.insert(tm-1);s.insert(tm-3);s.insert(tm-5);}cout<<s.size()<<endl;for(auto x:s){cout<<x/60<<" "<<x%60<<endl;}return 0;}

D 我不是大富翁

思路1：

先讲一下本人丑陋的做法。先把环拉直，$1\sim n$ 看成是数轴上的 $0\sim n-1$，顺时针走就相当于向右走，逆时针走就相当于向左走，循环就相当于取模。因为所有数都要用到，所以相当于取某些数为正，某些数为负，它们的和等于 $n$ 的倍数，这样一取模就回到了原点。

正数与负数之和等于 $n$ 的倍数，相当于正数绝对值之和与负数绝对值之和模 $n$ 同余。所以我们找到正数之和的所有可能的余数，然后枚举余数，$n$ 减去这个余数模 $n$ 就得到了负数绝对值之和的余数了，如果它与正数的余数同余，就说明有解。如果找一遍下来都不满足条件，就说明无解。

找正数之和所有可能的余数，这个过程就是个01背包了，不过下一个状态的位置需要对 $n$ 取模，这样可能会导致下一个状态的位置不一定在这个状态后面，如果用一维有可能会干扰到前面状态的枚举，因此需要开多维，或者使用临时数组来存储（滚动数组 ）。

code1：

#include #include using namespace std;const int maxn=5005;int n,m;long long tot;bool dp[maxn],t[maxn];int main(){cin>>n>>m;dp[0]=true;for(int i=1,a;i<=m;i++){cin>>a;tot+=a;for(int j=0;j<n;j++){if(dp[j])t[(j+a)%n]=t[j]=1;}for(int j=0;j<n;j++){dp[j]=t[j];t[j]=0;}}for(int i=0;i<n;i++){if(dp[i] && i==(tot-i)%n){puts("YES");return 0;}}puts("NO");return 0;}

思路2：

官方讲解的思路，就是把一个数的正负两种状态都看作一件物品来跑01背包，不允许不拿物品。跑一遍之后直接看 $dp[m][0]$ 是否为 $1$ 即可。其他的处理还是一样的

code2：

E 多重映射

思路1：

和abc的这场的C题一模一样，这题的数据量更大，题解的思路2本质上是个合并的思想，再加个合并小的数组的思想，就变成本题的次正解 启发式合并的思路了。

发现我的做法和题解的做法思维模型有点相似，先讲我现场yy的神秘做法了。

不难看出这个题不能简单粗暴的用值来并查集，不然先把 $2$ 变成 $3$，再把 $2$ 变成 $1$，这样 $123$ 都变成了 $3$，但是答案应该是 $1$ 是 $2$，$23$ 是 $3$。但是它应该是在合并某些东西的。

这里合并的应该是位置。某些位置有相同的某个数 $a$，把等于 $a$ 的所有位置看成一个集合，当我们把其他的一个数 $b$ 变成 $a$ 的时候，就相当于将等于 $b$ 的所有位置集合合并到等于 $a$ 的所有位置集合上，在并查集中只需要把代表元素合并一下即可，这个过程需要查询等于 $b$ 的位置集合的代表元素。而具体等于什么数，相当于这个集合的一个描述信息，直接在代表元素上记录一下即可。

其实想一下这个合并过程，就像一棵树一样，每个节点是个集合，也就是 某个数的位置集合，一直从叶子节点合并到根节点。暴力会超时就是因为节点的合并是集合的合并，最坏情况每次合并都是 $1e5$ 级别的。

用 $f$ 数组实现并查集，$nw$ 数组记录代表元素具体等于什么数，$mp$ 数组表示某个数的位置集合的代表元素是什么。之后就是愉快的coding了一点都不愉快。

code1：

#include #include #include #include #define donothing 0using namespace std;const int maxn=1e5+5,maxf=1e6+5;int T,n,m,a[maxn];int f[maxn],nw[maxn],mp[maxf];int findf(int x){if(f[x]==x)return x;else return f[x]=findf(f[x]);}void merge(int a,int b){//把a合并到b上 int fa=findf(a),fb=findf(b);f[fa]=fb;}int main(){cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=n;i++)f[i]=i;//for(int i=1;i<=1e6;i++)mp[i]=0;for(int i=1;i<=n;i++){cin>>a[i];nw[i]=a[i];if(!mp[a[i]])mp[a[i]]=i;else merge(i,mp[a[i]]);}for(int i=1,x,y;i<=m;i++){cin>>x>>y;if(!mp[x] || x==y)donothing;else if(!mp[y]){nw[mp[x]]=y;mp[y]=mp[x];mp[x]=0;}else {merge(mp[x],mp[y]);mp[x]=0;}}for(int i=1;i<=n;i++)cout<<nw[findf(i)]<<" \n"[i==n];for(int i=1;i<=n;i++)mp[nw[findf(i)]]=0;//直接memset会超时，只能这样清空}return 0;}

思路2：

正解做法，正难则反。根据上面说的那个把合并过程看成从叶子节点走到根节点的过程，既然集合的合并很难，那么不如从根节点向叶子节点走。因为我们只关心叶子节点最后走到根节点时，根节点上是什么值，那我们从根走到叶子的时候只需要告诉叶子，根等于什么就好了。

code2：

#include #include #include #include using namespace std;const int maxn=1e5+5,maxf=1e6+5;int T,n,m,a[maxn];pair<int,int> opt[maxn];int main(){cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++)cin>>opt[i].first>>opt[i].second;map<int,int> mp;for(int i=m;i>=1;i--){if(mp.find(opt[i].second)!=mp.end())mp[opt[i].first]=mp[opt[i].second];else mp[opt[i].first]=opt[i].second;}for(int i=1;i<=n;i++)cout<<((mp.find(a[i])==mp.end()?a[i]:mp[a[i]]))<<" \n"[i==n];}return 0;}

思路3：

启发式合并，本质是个优化的暴力。我们每次集合合并的时候，都把小集合合并到大集合上，就能减少合并次数，而最多合并 m 2+m 4+m 8+ ⋯ +m m≥m 1+m 2+m 3+ ⋯ +m m≈ m l o g m\dfrac m2+\dfrac m4+\dfrac m8+\dots+\dfrac mm\ge \dfrac m1+\dfrac m2+\dfrac m3+\dots+\dfrac mm\approx mlogm2m​+4m​+8m​+⋯+mm​≥1m​+2m​+3m​+⋯+mm​≈mlogm 次元素，可以通过。

code3：

#include #include #include #include using namespace std;const int maxn=1e5+5,maxf=1e6+5;int T,n,m,a[maxn];vector<int> f[maxf];int main(){ios::sync_with_stdio(false);cin.tie(0);cin>>T;while(T--){cin>>n>>m;vector<int> opt;for(int i=1;i<=n;i++){cin>>a[i];f[a[i]].push_back(i);opt.push_back(a[i]);}for(int i=1,x,y;i<=m;i++){cin>>x>>y;if(x==y)continue;if(f[x].size()<f[y].size()){f[y].insert(f[y].end(),f[x].begin(),f[x].end());f[x].clear();}else {f[x].insert(f[x].end(),f[y].begin(),f[y].end());f[y].clear();swap(f[x],f[y]);//只交换指针，O(1)}opt.push_back(y);}for(auto i:opt){for(auto idx:f[i])a[idx]=i;f[i].clear();}for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[i==n];}return 0;}

F 现在是消消乐时间

思路1：

这题非常色情。先说暴力思路，题解一两句话其实说的很明白了。对位置 $(d,1)$ 这个砖块（也就是左下角那个砖块），我们消除它的方法只有两种，一种是主对角线，一种是副对角线，也就是下图中红线描红的那两条。

你无论从哪里开始走，往哪走，路径上一定会包含这么一小段对角线，那么我们不如直接从这里开始走。方向无所谓，所以可以只判断一下从 $(d,0)$ 向右上以及 $(d,1)$ 向左上两种情况是否可行即可。如果不可行，那么就一定无解，因为至少这块砖无法被消除。

实际上，在其他位置进行判断也是可行的，证明看出题人题解

code1：

#include #include #include #include using namespace std;const int maxn=2005;int n,m,d;bool mp[maxn][maxn],vis[maxn][maxn][4];int fx[]={1,1,-1,-1},fy[]={-1,1,-1,1};struct state{int x,y;int dir;state(int x,int y,int dir):x(x),y(y),dir(dir){};};queue<state> q;bool solve(int a,int b,int st){memset(mp,0,sizeof(mp));memset(vis,0,sizeof(vis));q.push(state(a,b,st));while(!q.empty()){int ux=q.front().x,uy=q.front().y,dir=q.front().dir,nw=dir;q.pop();//printf("%d %d %d\n",ux,uy,dir);if(ux==0 && uy==m && dir!=0)break;if(ux==0 && uy==0 && dir!=1)break;if(ux==n && uy==m && dir!=2)break;if(ux==n && uy==0 && dir!=3)break;if((ux==0 && (dir==2 || dir==3)) || (ux==n && (dir==0 || dir==1)))nw=dir^2;if((uy==0 && (dir==0 || dir==2)) || (uy==m && (dir==1 || dir==3)))nw=dir^1;int x=ux+fx[nw],y=uy+fy[nw];mp[(ux+x+1)/2][(uy+y+1)/2]=true;//printf("%d %d\n",(ux+x+1)/2,(uy+y+1)/2);if(!vis[x][y][nw]){q.push(state(x,y,nw));vis[x][y][nw]=true;}}for(int i=d+1;i<=n;i++)for(int j=1;j<=m;j++)if(!mp[i][j])return false;return true;}int main(){cin>>n>>m>>d;if(solve(0,0,1))printf("YES\n%d %d\nUL\n",0,0);else if(solve(0,1,0))printf("YES\n%d %d\nUR\n",0,1);else puts("NO");return 0;}

思路2：

结论：

1. 如果 $d=n$，那么显然一定有解。
2. 如果 $gcd(n,m)=1$，那么在 $(0,0)$ 向右上
3. 如果 $gcd(n,m)=2$，那么在 $(1,0)$ 向左上
4. 其他情况无解。

证明，我是理解不能

code2：

某位大佬的

G 三点不共线

思路1：

赛时丑陋的想法，根据高中解三角形的知识来解。直觉上感觉这个 $C$ 点应该离 $AB$ 边越远，夹角就越小，反之则越大，而在所有点中，在中垂线上的点的性质最为美妙，因为它是对称的。$C$ 点在 $AB$ 上的中点沿着中垂线开始向外走，走的越远，形成的夹角就越小。

考虑用数学语言表示每个值。要模拟 $C$ 点在 $AB$ 上的中点沿着中垂线向外走，就需要知道中垂线上的点的坐标，而要知道线上点的坐标，就需要知道xy值的变化率，直线 $AB$ 与中垂线垂直，那么就可以通过 $AB$ 来算这个变化率。设 $len=|AB|$ 。通过画图可以比较容易算出来，如下图：

然后中点坐标 ( x 1+ x 22, y 1+ y 22)(\dfrac{x_1+x_2}2,\dfrac{y_1+y_2}2)(2x1​+x2​​,2y1​+y2​​)，加上移动距离 $dis$ 乘上单位向量 e→ \overrightarrow ee 就能得到 中垂线上 到中点距离为 $dis$ 的点的坐标了。

所以问题变成了怎么求得这个距离 $dis$。因为形成的夹角为 $\alpha$ 时，腰的长度应该是固定的，当 $dis$ 变大的时候，夹角 $\alpha$ 就会变小，三角形的腰就会变长。因此可以二分答案。当腰长小于答案腰长时，就增大 $dis$，否则就减少。

答案腰长可以根据余弦定理求得，假设腰长为 $x$，有： x 2+ x 2−le n 2=2∗x∗x∗cos   αx^2+x^2-len^2=2*x*x*cos\,\alpha x2+x2−len2=2∗x∗x∗cosα2∗ x 2∗(1−cos   α)=le n 22*x^2*(1-cos\,\alpha)=len^2 2∗x2∗(1−cosα)=len2 x 2= le n 22∗(1−cos   α) x^2=\dfrac{len^2}{2*(1-cos\,\alpha)} x2=2∗(1−cosα)len2​

而当 $dis$ 取得某个值的时候根据勾股定理可以得到此时的腰长： x 2= le n 24+di s 2x^2=\dfrac{len^2}4+dis^2 x2=4len2​+dis2

需要用到的 $\pi$ 可以通过 $4\ast arctan(1)$ 来计算（因为 t a n π 4= 1tan\,\dfrac{\pi}{4}=1tan4π​=1）。

code1：

#include #include #include using namespace std;const double eps=1e-7;int T;double x11,y11,x22,y22,alpha,pi;double dis(double a1,double b1,double a2,double b2){return sqrt((a1-a2)*(a1-a2)+(b1-b2)*(b1-b2));}double angle(double a0,double b0,double a1,double b1,double a2,double b2){double a=dis(a0,b0,a1,b1),b=dis(a0,b0,a2,b2),c=dis(a1,b1,a2,b2);return acos((a*a+b*b-c*c)/(2*a*b));}int main(){pi=4*atan(1);cin>>T;while(T--){cin>>x11>>y11>>x22>>y22>>alpha;alpha=alpha*pi/180;double x0=(x11+x22)/2,y0=(y11+y22)/2;double len2=(x11-x22)*(x11-x22)+(y11-y22)*(y11-y22),len=sqrt(len2);double kx=(y11-y22)/len,ky=(x22-x11)/len;//printf("***(%lf,%lf) %lf %lf\n",x0,y0,kx,ky);double l=0,r=1e9,mid;while(l+eps<r){mid=(l+r)/2;if(len2/4+mid*mid<len2/(2*(1-cos(alpha))))l=mid;else r=mid;}double ans=(l+r)/2;printf("%.9lf %.9lf\n",x0+kx*ans,y0+ky*ans);//printf("***%lf\n",angle(x0+kx*ans,y0+ky*ans,x11,y11,x22,y22)*180/pi);}return 0;}

思路2：

我们把 A B→ \overrightarrow {AB}AB 旋转到 B C→ \overrightarrow {BC}BC 的位置上，然后算出腰长，然后就可以从 $B$ 点直接算出 $C$ 点了。

旋转的角度从图上很容易算出来等于 π 2−α 2 \dfrac{\pi} 2-\dfrac{\alpha} 22π​−2α​，腰长根据正弦公式可以很容易算出来： x sin  π 2 =l e n2sin  α 2 \dfrac x{sin\,\dfrac{\pi}{2}}=\dfrac {\dfrac{len}{2}}{sin\,\dfrac{\alpha}{2}} sin2π​x​=sin2α​2len​​x= len2∗sin  α 2 x=\dfrac {len}{2*sin\,\dfrac{\alpha}{2}} x=2∗sin2α​len​

关于求逆时针旋转 $\alpha$ 度的旋转矩阵的方法：

使用待定系数法，假设这个旋转矩阵为 [ a b c d ]\left[\begin{matrix} a & b\\ c & d \end{matrix}\right][ac​bd​]。先画一个单位圆，我们可以把向量 $(1,0)$ 逆时针旋转 $\alpha$ 到 $(cos\alpha ,sin\alpha )$，于是有： [ a b c d ]× [ 1 0 ]= [ cos   αsin   α]\left[\begin{matrix}a & b\\c & d\end{matrix}\right]\times\left[\begin{matrix}1\\0\end{matrix}\right]=\left[\begin{matrix}cos\,\alpha\\sin\,\alpha\end{matrix}\right] [ac​bd​]×[10​]=[cosαsinα​]{a = c o s  αc = s i n  α\left\{\begin{aligned} a & = cos\,\alpha\\ c & = sin\,\alpha \end{aligned}\right. {ac​=cosα=sinα​
同理，把向量 $(0,1)$ 逆时针旋转 $\alpha$ 到 $(cos\alpha ,sin\alpha )$ 同时相当于把向量 $(1,0)$ 旋转到 ( c o s  ( α +π 2) , s i n  ( α +π 2) ) = ( − s i n  α , c o s  α )(cos\,(\alpha+\dfrac\pi2),sin\,(\alpha+\dfrac\pi2))=(-sin\,\alpha,cos\,\alpha)(cos(α+2π​),sin(α+2π​))=(−sinα,cosα) ，那么有： [ a b c d ]× [ 0 1 ]= [ −sin   αcos   α]\left[\begin{matrix}a & b\\c & d\end{matrix}\right]\times\left[\begin{matrix}0\\1\end{matrix}\right]=\left[\begin{matrix}-sin\,\alpha\\cos\,\alpha\end{matrix}\right] [ac​bd​]×[01​]=[−sinαcosα​]{b = − s i n  αd = c o s  α\left\{\begin{aligned} b & = -sin\,\alpha\\ d & = cos\,\alpha \end{aligned}\right. {bd​=−sinα=cosα​

所以这个旋转矩阵就是 [ cos   α−sin   αsin   αcos   α]\left[\begin{matrix} cos\,\alpha & -sin\,\alpha\\ sin\,\alpha & cos\,\alpha \end{matrix}\right][cosαsinα​−sinαcosα​]。

code：

#include #include #include using namespace std;int T;double a1,b1,a2,b2,alpha,pi;int main(){pi=4*atan(1);cin>>T;while(T--){cin>>a1>>b1>>a2>>b2>>alpha;alpha=alpha*pi/180;double peta=(pi-alpha)/2;pair<double,double> AB=make_pair(a2-a1,b2-b1);pair<double,double> AC=make_pair(AB.first*cos(peta)-AB.second*sin(peta),AB.first*sin(peta)+AB.second*cos(peta));//printf("***%.9lf %.9lf\n",AC.first,AC.second);double ABl=sqrt(AB.first*AB.first+AB.second*AB.second);double ACl=ABl/(2*sin(alpha/2));AC.first=AC.first/ABl*ACl;AC.second=AC.second/ABl*ACl;printf("%.9lf %.9lf\n",a1+AC.first,b1+AC.second);}return 0;}