按照通过和赛后补题顺序：A、B、G、J、H、C、F。
请确保您在阅读本文前已经严肃阅读原题面并且简单理解，因为这里并不提供题面和简要题意。
原题指路：https://ac.nowcoder.com/acm/contest/120563#question
钝评
总体来说比较友好，A开起来就是一个直白的签到，难度梯度比较平滑，好评++。坏消息是一些题还是比较阴，H题卡精度是我没想到的。
A：宙天
由于数据范围只有100，拆成数字就是10*10。那么开一个 i 从1到10往下遍历，检测 i*i+1 是不是输入的数字 x 即可。
void solve() {
// code here'
int x;
cin>>x;
bool flag=false;
for(int i=1,j;i<=10;i++)
{
j=i+1;
if(x==i*j)
{
flag=true;
break;
}
}
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}B：Random
这里提供两个解答方案。
1.官方解：题目中强调了随机数据，可以严格证明，生成的数字只有极小概率不能用暴力做出来。
严格证明请见：https://ac.nowcoder.com/discuss/1609142
做法：对每个位置 i，只检查后面固定数量的元素（例如 30 个）：
总 gcd 次数为 ，当 时约为 ，非常快。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[202020];
void solve(){
int n,i,j;
cin>>n;
for(i=1;i<=n;i++)cin>>a[i];
for(i=1;i<=n;i++){
for(j=i+1;j<=n&&j<=i+30;j++){
if(__gcd(a[i],a[j])>1){
cout<<a[i]<<" "<<a[j]<<"\n";
return;
}
}
}
cout<<-1<<"\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}2.个人解：经典的暴力美学，先预处理一个质数表，并手写一个分解质因数（应该有人猜到我怎么想的了）。读入数组数据后用 unordered_map 存下数组中所有数字及其出现次数（这里，如果同一个数出现多次，那么我们直接输出这个数字两次并结束即可。另外，从这里开始到后续的步骤，我们都将跳过元素 1 的存在，毕竟这个数字不算质数也没啥贡献）。然后对数组中非 1 的元素进行分解质因数，并对某个元素的质因数表中含有的元素在原数组中进行搜索，一旦存在该元素的质因数在原数组中，我们输出这对数，否则搜索失败。（好消息：hash了；坏消息：白hash了）
void init() { vector<bool> isp(maxn+1,true); isp[0]=isp[1]=false; for(int i=2;i<=maxn;i++) { if(isp[i]) { sprime.push_back(i); if(1LL*i*i<=maxn) { for(int j=i*i;j<=maxn;j+=i) isp[j]=false; } } } } vector<int> fac(int x) { vector<int> factor; if(x%2==0) { factor.push_back(2); while(x%2==0) x/=2; } for(int p:sprime) { if(1ll*p*p>x) break; if(p==2) continue; if(x%p==0) { factor.push_back(p); while(x%p==0) x/=p; } } if(x > 1) factor.push_back(x); return factor; } void solve() { // code here int n; cin >> n; vector<ll> a(n); for(int i=0;i<n;i++) cin>>a[i]; ftval.clear(); unordered_map<int, int> val_count; for(int i = 0; i < n; i++) { if(a[i] != 1) { val_count[a[i]]++; if(val_count[a[i]] >= 2) { cout<<a[i]<<" "<<a[i]<<endl; return; } } } for(int i=0;i<n;i++) { if(a[i]==1) continue; vector<int> fs=fac(a[i]); for(int f:fs) { if(ftval.count(f)) { cout<<ftval[f]<<" "<<a[i]<<endl; return; } ftval[f]=a[i]; } } cout<<"-1"<<endl; }
G：スピカの天秤
读入数据之后先判断当前属于什么状态，用 cntl cntr 两个变量维护左右两侧的总重量，如果是平衡态那么很简单，只需要任意拿左边或者右边的一个秤砣就可以破坏平衡，所以如果 cntl==cntr 那么直接输出 1 即可。如果不平衡，我们只需要让偏重的那一侧的重量减小到小于等于偏轻的那一侧。为了尽可能少取，我们肯定优先拿走大的秤砣。
void solve() {
// code here
int n,m;
cin>>n>>m;
int state=0;
vector<ll> a(n),b(m);
ll suml=0,sumr=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
suml+=a[i];
}
for(int j=0;j<m;j++)
{
cin>>b[j];
sumr+=b[j];
}
if(suml>sumr) state=1;
else if(suml<sumr) state=-1;
if(state==0) cout<<1<<endl;
else if(state==1)
{
sort(a.begin(),a.end());
ll sum=0;
int i=0;
while(i<n&&sum+a[i]<=sumr)
{
sum+=a[i];
i++;
}
cout<<n-i<<endl;
}
else
{
sort(b.begin(),b.end());
ll sum=0;
int i=0;
while(i<m&&sum+b[i]<=suml)
{
sum+=b[i];
i++;
}
cout<<m-i<<endl;
}
}J：Branch of Faith
考察了完全二叉树的常识，对于一个有 n 个节点的完全二叉树，我们定义根节点编号为 1，那么对于节点 i 来说，编号为 2i 的节点就是其左儿子，编号为 2i+1 的节点就是其右儿子。询问节点 x，我们想知道与 x 节点深度相同的节点数（包括 x 节点）。
对于 x，它的深度是由十进制数字 x 转为二进制序列后最高位的位数决定。如果 x 用 2 的幂表达，最高位就是 ，那么 d 就是 x 节点的深度。显然，同一层的节点编号范围就是 [ , ]. 不过需要注意下最大不超过总结点数 n就好了。答案就是 .
int cal_len(ll x)
{
int res=0;
while(x>0)
{
x>>=1;
res++;
}
return res;
}
void solve() {
// code here
ll n,q;
cin>>n>>q;
int maxd=cal_len(n)-1;
while(q--)
{
ll x;
cin>>x;
int depth=cal_len(x)-1;
if(depth<maxd) cout<<(1ll<<depth)<<endl;
else
{
ll lst_d=1ll<<depth;
cout<<n-lst_d+1<<endl;
}
}
}H：Tic Tac DREAMIN’
说是算法题，不如说是解析几何的公式推导题。
给定 、，要在 轴上找点 使得三角形 面积为 ，即
令 ，，则二维叉积为
把它写成关于 的一次函数：
目标是：
个人采取了暴力求解，直接解 。当 时，取 的一个解即可：
void solve() {
// code here
int xa,ya,xb,yb;
cin>>xa>>ya>>xb>>yb;
ll c=xa*yb-xb*ya;
ll d=ya-yb;
if(d==0)
{
if(abs(c)==4) cout<<"0.0"<<endl;
else cout<<"no answer"<<endl;
}
else
{
double res=(4-c)*1.000/d*1.000;
cout<<fixed<<setprecision(10)<<res<<endl;
}
}值得一提的是，提交前最好多确认一下精度是否符合要求。这道题因为卡精度害得我吃了两发罚时。
C：Inverted World
首先明确，根据题意不管是怎么样的原始串给到手，我们最后得到的目标串只有两种形式：010101...和101010... 所以我们需要考虑两种模式串下分别需要对原始串进行几次改动，并选择改动次数最小的。
在开始思考怎么计算改动次数之前，请一定！一定！一定！要读一下题目中对于子序列概念的表述（是的，我赛时没有写出来就是因为没看这个），子序列允许元素不相邻，但是子序列中相邻元素必须相异。
既然子序列允许元素不连续，那么干脆把原始串和模式串对比，当某个位置的字符与模式串不匹配，我们把这个字符放入一个新串。也就是说，这个新串记录了当前模式串下所有不匹配的字符，我们称作不匹配串。我们希望对于这个不匹配串中挑选出尽可能少的子序列数，完成扭转。
由于扭转操作是把字符 0 和 1 进行交换，所以我们希望在子序列中挑选出尽可能长的01交替子序列来减少我们的操作次数。聪明的你已经意识到，根据子序列的要求，我们可以用DP方法求出最少的子序列个数。具体地，我们用 c0 c1 这两个变量分别记录以字符 0 和字符 1 为结尾的子序列，计数规则如下：
如果当前遍历到的字符为 1，那么我们第一想法是，如果当前有一个用 0 结尾的子序列（也就是说，变量c0 的值大于0），我们会把这个 1 加入到这个以 0 结尾的子序列后面，这样我们可以少开一个子序列，也就意味着可以减少一次操作次数。当然如果没有以 0 结尾的子序列我们就不强求，另外单独开一个串，也就是 c1++. 同理我们可以知道字符为 0 的处理方式。
int cal(string s) {
int c0=0,c1=0;
for(auto i:s)
{
if(i=='1')
{
if(c0==0) c1++;
else
{
c0--;
c1++;
}
}
else
{
if(c1==0) c0++;
else
{
c1--;
c0++;
}
}
}
return c0+c1;
}
void solve() {
int n;
cin >> n;
string s;
cin >> s;
string s_n = "";
for (int i = 0; i < n; i++) {
char tar = (i % 2 == 0) ? '0' : '1';
if (tar != s[i]) s_n += s[i];
}
int res1 = cal(s_n);
s_n = "";
for (int i = 0; i < n; i++) {
char tar = (i % 2 == 0) ? '1' : '0';
if (tar != s[i]) s_n += s[i];
}
int res2 = cal(s_n);
cout << min(res1, res2) << endl;
}E：Energy Synergy Matrix
这道题目不一定用嘴巴能说明清楚...大概知识点在：构造，博弈，最短路（请一定要磕好博弈和最短路这两个关键词）。再次提醒，请确保您已经认真阅读题面并简要理解题面。
由于是小红先手，作为小红方希望每一步都能下成妙手的效果，也就是意味着一次操作要尽可能让小小红到达的位置远，而且路径长度小。所以小小红在我们（小红）的控制下肯定不能向下拐弯。接下来我们转换视角，来到后手的小紫，由于是后手我们第一要义就是见招拆招，但是又不能让游戏没法玩，不能把路一口气堵死。所以小小红在我们（小紫）的控制下要尽可能产生路线的拐弯。需要注意，小小红也不是傻子，会根据当前地图情况自己规划最优路线。
接下来我们把玩几个小范围样例：n=1 情况下没有啥好玩的，直接 0 步就能走到目标位置。n=2 的时候小红任意选择下方的格子进行放置，小紫为了保证有一条路，如果小红在 (1, 2) 位置放置障碍，那么小紫在被迫放置障碍 (2, 2) 处放置，如果小红在 (2, 2) 位置放置，那么小紫相反，在 (1, 2) 位置放置。此时路径长度为 1 步。
接下来我们把 n 拓展到 3，小红先手堵住 (2, 1) 的位置才能保证小小红从起点出发不会拐弯。当我们再切换回小紫视角就会发现，小红这一步非常绝妙，如果我们想要满足小紫的目标，我们此时已经无计可施（显然，我们不能堵住上面这一列中的任何一个区块）。此时最短路径长度为 2 步。进一步思考，小红找到了一个绝佳位置 (2, 2)，我们把 n 拓展到 4 发现，小红的操作效果还在持续，我们照样没有办法堵路。此时最短路径长度为 3 步。
到这里，我们应该有猜想，一般情况下结论就是 最短路径长度为 . 可是样例告诉我们 n = 5 的时候就不成立了。有几种可能：1.这个结论不完全，还缺少了几个多项式；2.这个结论不完全，我们还需要分类讨论。所以接下来我们开始看看 n = 5 的情况：
根据前面的分析，小红在有一次操作机会的时候最优选择只有 (2, 1) 的位置。但是此时这个位置防止小小红转弯的效果已经无法持续了，作为小紫，我们选择 (5, 1) 的位置填堵，此时小小红必然需要转一次弯，所以当 n = 5 的时候必然会有一步多余步数产生。并且不难验证，每 5 格拓展下去必然会多一次拐弯，因此，我们知道，对于上面的结论，正确的应该写为：
void solve() {
// code here
ll n;
cin>>n;
cout<<n-1+(n/5)<<endl;
}
Comments NOTHING