2023-01-31 20:59 已编辑圣芙蕾雅学园 C++ 发布于福建

关注

题解 | #清楚姐姐学信息论#

清楚姐姐学信息论

https://ac.nowcoder.com/acm/contest/46812/A

alt

嗨，想我了吗~ 我的题解，要好好收下哦♪

注意：题解内代码省略了同步流，所以可能会导致超时，若有问题，请以提交记录为准。

A 清楚姐姐学信息论

签到题，结论

进制是效率最高的进制，越靠近e进制效率越高，所以除 $(2\ 3),(3\ 2)$ 外，都是小的进制更优。

代码如下：

#include <bits/stdc++.h>
 
using namespace std;

int main(){
    int T = 1;
    while(T--){
        int n,m;
        cin>>n>>m;
        if(n>m) swap(n,m);
        if(n==2 && m==3) cout<<3<<endl;
        else cout<<min(n,m)<<endl;
    }
    return 0;
}

提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60623689

B 清楚姐姐学构造

中等题，构造，同余

首先把对称的位置分别拆成一些数字对，然后优先考虑奇质数（大部分情况）。

以 $m = 7$ 为例，对于 $b$ 数组的数字对将会是 $(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1), (0, 0)$ ，他们的差值分别是 $2, 4, 6, 1, 3, 5, 0$ 。

那么对于 $c$ 数组的每一个数字对 $(x, y)$ 的差值 $x-y(mod\ m)$ ，将上面的相应的数字对填进去即可， $a$ 数组则用 $c$ 数组减 $b$ 数组得到。

而对于偶质数（有且仅有 $m = 2$ ）， $b$ 数组的数字对差值只会为 $0$ ，那么若是在 $c$ 数组中的任意一对数字对不同，则无解。

建议看仙人掌杀手——智乃哥哥的题解，我写的很怪。

代码如下：

#include <bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    while(T--){
        int n,m;
        cin>>n>>m;
        vector<int> c(n+1),a=c,b=c;
        for(int i=1;i<=n;i++){
            cin>>c[i];
        }
        if(m==2){
            for(int i=1;i+i-1<=n;i++){
                int l = i , r = n - i + 1;
                if(c[l]!=c[r]) goto no;
                a[l] = a[r] = c[l];
                b[l] = b[r] = 0;
            }
            goto yes;
        }
        for(int i=1;i+i-1<=n;i++){
            int l = i , r = n - i + 1;
            int d = (c[r] - c[l] + m) % m;
            if(d&1){
                int t = m-2;
                int x,y;
                x = 1 + (t-d)/2;
                y = m-1 - (t-d)/2;
                b[l] = x;
                b[r] = y;
                a[l] = a[r] = c[l] - x;
            }
            else{
                if(!d){
                    a[l] = a[r] = c[l];
                    b[l] = b[r] = 0;
                }
                else{
                    d = (c[l] - c[r] + m) % m;
                    int t = m-2;
                    int x,y;
                    x = 1 + (t-d)/2;
                    y = m-1 - (t-d)/2;
                    b[l] = y;
                    b[r] = x;
                    a[l] = a[r] = c[l] - y;
                }
            }
        }
        goto yes;
        if(0){
            yes: cout<<"YES"<<endl;
            for(int i=1;i<=n;i++){
                cout<<a[i]<<" ";
            }
            cout<<endl;
            for(int i=1;i<=n;i++){
                cout<<b[i]<<" ";
            }
            cout<<endl;
        }
        if(0) no:  cout<<"NO"<<endl;
    }
    return 0;
}

提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60641686

C 清楚姐姐学01背包(Easy Version)

简单题，01背包

把除了第i个物品以外的物品打一个01背包，判断第i个物品是否必须取（取这个物品后答案更优）即可。

	LL ans = dp[m]-dp[m-w[i]] - v[i] + 1;
    if(ans<0) cout<<0<<endl;
    else cout<<ans<<endl;

代码如下：

#include <bits/stdc++.h>

using namespace std;
 
using LL = long long;

int main(){
    int T = 1;
    while(T--){
        int n,m;
        cin>>n>>m;
        vector<int> v(n+1),w(n+1);
        for(int i=1;i<=n;i++){
            cin>>w[i]>>v[i];
        }
        for(int i=1;i<=n;i++){
            vector<LL> dp(m+1);
            for(int j=1;j<=n;j++){
                if(i==j) continue;
                for(int k=m;k>=w[j];k--){
                    dp[k] = max(dp[k] , dp[k-w[j]] + v[j]);
                }
            }
            LL ans = dp[m]-dp[m-w[i]] - v[i] + 1;
            if(ans<0) cout<<0<<endl;
            else cout<<ans<<endl;
        }
    }
    return 0;
}

提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60620707

D 清楚姐姐学01背包(Hard Version)

中等题

注意：本做法歪门邪道，卡常战神。时间复杂度为 $O(n^2\sqrt n)$ 。

类似上题，但是显然无法暴力，但可以把每75个当成一组，打出接近75个背包，第 $i$ 个背包中不含第 $i$ 组的物品。

然后对于第 $j$ 个物品，找到其所在的组数，把这组除了 $j$ 以外的物品装入背包（最多74个），则打出如上题的背包，使用上题方法判断即可。

代码如下：

#include <bits/stdc++.h>

using namespace std;
 
using LL = long long;

int main(){
    int T = 1;
    while(T--){
        int n,m;
        cin>>n>>m;
        vector<int> v(n+1),w(n+1);
        vector dp(76,vector<LL>(m+1));
        for(int i=1;i<=n;i++){
            cin>>w[i]>>v[i];
            int t = i/75;
            for(int k=0;k<75;k++){
                if(k==t) continue;
                for(int j=m;j>=w[i];j--){
                    dp[k][j] = max(dp[k][j] , dp[k][j-w[i]] + v[i]);
                }                
            }
        }
        for(int i=1;i<=n;i++){
            int t = i/75;
            auto f = dp[t];
            for(int j=1;j<=n;j++){
                if(t != j/75 || i==j) continue;
                for(int k=m;k>=w[j];k--){
                    f[k] = max(f[k] , f[k-w[j]] + v[j]);
                }
            }
            LL ans = f[m]-f[m-w[i]] - v[i] + 1;
            if(ans<0) cout<<0<<endl;
            else cout<<ans<<endl;
        }
    }
    return 0;
}

提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60649997

E 清楚姐姐打怪升级

简单题，Um_nik算法

只要有一个怪物无法杀死，就输出-1。

否则，答案就是杀死每一个怪物所需的时间之和，也就是需要知道攻击次数。

杀死每一个怪物所需要的攻击次数可以使用公式将其 $O (1)$ 解决，也可以使用二分直接无脑解决。

二分恰好攻击 $x$ 次可以刚好击杀怪物，那么 $c h e c k$ 时，前面已经攻击了 $x - 1$ 次，然后加上血量回复，再补上第 $x$ 次攻击，若是怪物血量小于等于0，则 $c h e c k$ 为真。

最后计算答案，记得开 $long\ long$ ，要注意攻击是从时刻 1 开始的，所以需要稍微处理（样例诈骗，很容易WA）。

代码如下：

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){
    int T = 1;
    while(T--){
        LL n,t,a;
        cin>>n>>t>>a;
        LL ans = 0;
        for(int i=1;i<=n;i++){
            LL h,v;
            cin>>h>>v;
            auto check = [&](LL h,LL v,LL x){
                h -= max((x-1) * (a-v*t) , 0ll);
                h -= a;
                return h<=0;
            };
            int l = 1,r = 1e6+100;
            while(l<r){
                int mid = l + r>> 1;
                if(check(h,v,mid)) r = mid;
                else l = mid + 1;
            }
            if(l>1e6) goto no;
            else ans += l;
        }
        cout<<ans*t-t+1<<endl;
        if(0) no:  cout<<"-1"<<endl;
    }
    return 0;
}

提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60630705

F 清楚姐姐学树状数组

中等题，二叉树，DFS

手写前序遍历、中序遍历、后序遍历即可。（题目说了中序遍历等于输入数字本身）

前序遍历：

1.走到哪加到哪
2.走左直接走
3.走右先加左子树结点数
4.走到即停

void fr(LL u,int deep){
    l++;		//l是答案
    if(u==x) return;		//走到了
    if(u>x) fr(u-(1ll<<deep),deep-1);	//往左走
    else{								//往右走
        l += 1ll<<(deep+1);
        l--;
        fr(u+(1ll<<deep),deep-1);
    }
}

后序遍历：

1.走左直接走
2.走右先加左子树结点数
3.走到了加上子树结点数

void ba(LL u,int deep){
    if(u==x){				//走到了
        r += (1ll<<deep+1)-1;		//r是答案，走到了加子树
        return;
    }
    if(u>x) dfs1(dfs1,u-(1ll<<deep-1),deep-1);	//往左走
    else{										//往右走
        r += (1ll<<deep)-1;
        dfs1(dfs1,u+(1ll<<deep-1),deep-1);
    }
 }

代码如下：

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){
    int T = 1;
    while(T--){
        LL k,q;
        cin>>k>>q;
        LL n = 1ll<<k;
        while(q--){
            LL x;
            cin>>x;
            LL l=0,m=0,r=0;
            m = x;
            LL d;
            for(d=0;d<=60;d++){
                if(x&(1ll<<d)) break;
            }
            auto fr = [&](auto fr,LL u,int deep)->void{
                l++;
                if(u==x) return;
                if(u>x) fr(fr,u-(1ll<<deep),deep-1);
                else{
                    l += 1ll<<(deep+1);
                    l--;
                    fr(fr,u+(1ll<<deep),deep-1);
                }
            };
            auto ba = [&](auto ba,LL u,int deep)->void{
                if(u==x){
                    r += (1ll<<deep+1)-1;
                    return;
                }
                if(u>x) ba(ba,u-(1ll<<deep-1),deep-1);
                else{
                    r += (1ll<<deep)-1;
                    ba(ba,u+(1ll<<deep-1),deep-1);
                }
            };
            fr(fr,n,k-1);
            ba(ba,n,k);
            if(x==n) r = r + 1>>1;
            cout<<l<<" "<<m<<" "<<r<<endl;
        }
    }
    return 0;
}

提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60648153

G 清楚姐姐逛街(Easy Version)

中等题，暴力BFS

（谁逛商场一直撞墙、原地踏步、转圈圈的啊）

首先要知道，智乃（喜欢仙人掌的hentai萝莉控）可以随意走，所以先用BFS遍历连通块，把走到每一个点的需要的步数计算出来。

然后清楚姐姐走的时候按照地图标志走，直到清楚姐姐走的步数大于等于智乃到达此格需要的步数时，就得出了答案。

alt

清楚姐姐一路向右走，走了5步，而智乃走到此只需要4步，智乃就可以提前走到这里等待清楚姐姐过来。

代码如下：

#include <bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    while(T--){
        int n,m,x0,y0,q;
        cin>>n>>m>>x0>>y0>>q;
        n--;
        m--;
        vector s(n+1,string(m,'#'));
        vector b(n+1,vector<int>(m+1,-1));
        vector ans = b;
        for(int i=0;i<=n;i++){
            cin>>s[i];
        }
        auto bfs = [&](){
            queue<PII> q;
            q.push({x0,y0});
            vector<PII> d = {{-1,0} , {1,0} , {0,-1} , {0,1}};
            b[x0][y0] = 0;
            while(q.size()){
                auto [x,y] = q.front();
                q.pop();
                for(auto &[dx,dy] : d){
                    int xx = x + dx;
                    int yy = y + dy;
                    if(s[xx][yy]=='#' || b[xx][yy]>=0) continue;
                    q.push({xx,yy});
                    b[xx][yy] = b[x][y] + 1;
                }
            }
        };
        bfs();
        while(q--){
            int x,y;
            cin>>x>>y;
            if(b[x][y]<0){
                cout<<-1<<endl;
                continue;
            }
            auto go = [&](){
                if(s[x][y]=='U' && s[x-1][y]!='#') x--;
                else if(s[x][y]=='D' && s[x+1][y]!='#') x++;
                else if(s[x][y]=='L' && s[x][y-1]!='#') y--;
                else if(s[x][y]=='R' && s[x][y+1]!='#') y++;
            };
            auto dis = [&](){
                return abs(x0-x) + abs(y0-y);
            };
            for(int t=1;t<=1919810;t++){
                go();
                if(b[x][y]<=t){
                    cout<<t<<endl;
                    break;
                }
            }
        }
    }
    return 0;
}

提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60655201

H 清楚姐姐逛街(Hard Version)

防AK题，倍增

（谁家建商场建的跟个迷宫一样，绕来绕去的啊？哦，大润发？那没事了）

可以通过此题，学习一下倍增。也可以去洛谷刷刷ST表和LCA的模板，都是比较典型的倍增。

类似上题，但我们需要快速求出答案，所以清楚姐姐需要多步多步走，而不是一步一步走，但又不能走过头。

那么多步是多少步呢？1000步1000步走？显然是可行的，当即将走过头的时候，重新1步1步走，复杂度最坏就是 $O(q\times 1640)$ （智乃最多走 64000 步可以遍历全图，那么 1000 步 1000 步最多走 639 次，而若是剩余的 1000 步中恰好要走999步可以得到答案，大概就是这个复杂度了）。

如果把步数缩成 800 ，那就是根号级别的复杂度了，但有没有更快的呢，比如 log 级别？

显然是有的，假设共需要走75步，如果步数不固定，先试试走 1024 步，若是走过头了，那就试试走 512 步 ... 256 ... 直到试到走 64 步，发现可以走过去，那么就走，由于已经走了 64 步，所以剩下只需要走 11 步了，但由于我们不知道剩下需要几步，所以继续尝试 32，16，8 ，再走8步，就剩下 3 步，再尝试 2，1 就得到了答案。

那么怎么求出来呢？总不可能暴力走吧。看到 1，2，4，6，8......1024 想必大家都有了一点思路。假设一下：A位置走1步可以到B，B位置走1步可以到C，那么A位置走2步可以到C。而若是C位置走2步可以到D，那么A位置走4步就可以到D，依次类推，我们就可以把上述需要的功能进行实现。

而第一次尝试的步数必须可以走完全程（以免要走好多次这个尝试），所以不能取太小，只要比整个地图大即可，比如 2 的 20 次方、30 次方。

代码如下：

#include <bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    while(T--){
        int n,m,x0,y0,q;
        cin>>n>>m>>x0>>y0>>q;
        n--;
        m--;
        vector s(n+1,string(m,'#'));
        vector b(n+1,vector<int>(m+1,-1));
        vector ne(n+1,vector(m+1,vector<PII>(31)));
        for(int i=0;i<=n;i++){
            cin>>s[i];
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                int x=i,y=j;
                if(s[x][y]=='U' && s[x-1][y]!='#') ne[x][y][0] = {x-1,y};
                else if(s[x][y]=='D' && s[x+1][y]!='#') ne[x][y][0] = {x+1,y};
                else if(s[x][y]=='L' && s[x][y-1]!='#') ne[x][y][0] = {x,y-1};
                else if(s[x][y]=='R' && s[x][y+1]!='#') ne[x][y][0] = {x,y+1};
                else ne[x][y][0] = {x,y};
            }
        }
        for(int t=1;t<=30;t++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++){
                    auto [x,y] = ne[i][j][t-1];
                    ne[i][j][t] = ne[x][y][t-1];
                }
            }
        }
        auto bfs = [&](){
            queue<PII> q;
            q.push({x0,y0});
            vector<PII> d = {{-1,0} , {1,0} , {0,-1} , {0,1}};
            b[x0][y0] = 0;
            while(q.size()){
                auto [x,y] = q.front();
                q.pop();
                for(auto &[dx,dy] : d){
                    int xx = x + dx;
                    int yy = y + dy;
                    if(s[xx][yy]=='#' || b[xx][yy]>=0) continue;
                    q.push({xx,yy});
                    b[xx][yy] = b[x][y] + 1;
                }
            }
        };
        bfs();
        while(q--){
            int x,y;
            cin>>x>>y;
            if(b[x][y]<0){
                cout<<-1<<endl;
                continue;
            }
            int sum = 0;
            int t = 30;
            while(1){
                for(;t>=0;t--){
                    auto [nx,ny] = ne[x][y][t];
                    if(b[nx][ny]>sum+(1<<t) || t==0){
                        sum += 1<<t;
                        x = nx;
                        y = ny;
                        break;
                    }
                }
                if(b[x][y]<=sum) break;
            }
            cout<<sum<<endl;
        }
    }
    return 0;
}

提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60662760

I 清楚姐姐采蘑菇

防AK题，构造（莫队）

首先是这个问题：冬天到了，天很冷，清楚姐姐想给大家做一锅蘑菇汤给智乃、兰子、小沙、斌斌、阿宁、炸鸡块、时津风几个人喝。（PS：这几个人里面有一个人不能吃蘑菇，会是谁捏）

答案是⬛⬛，你猜对了吗？

据说这题会莫队就非常简单，但我不会莫队（然后出题人说我发明了莫队）。四个方向先ban一个方向，假设不能向上走。

以下图为例：

alt

现在有一个优秀的解法：

alt

但怎么写呢？我也不知道啊（写个AI）。

我还有一个很傻逼的解法：

alt

这个解法很傻逼，但由于我是傻逼，所以我会写！

想必大家也看出来了一些，我把三列三列分成一块，查看当前行有没有蘑菇，没有就往下，有就从左到右采完所有的蘑菇，采完本行就继续往下，直到走回第一行，那么这三列就走完了，走到下一个三列，依次循环直到走完所有的三列。观察第三个三列第七行可知，即使已经经过了第七行第九列，依旧会再走过去一次，是一种非常笨的方法。

考虑一下复杂度，假设蘑菇数量最多时，也就是和地图边长一致。首先，每个三列都会从上到下走满9步，然后若每次向下搜索到有一个蘑菇的行最多只要走2步就可以采到，若是有更多蘑菇，每一个蘑菇也最多只需要两步，然后每次走完三列到下一个三列，也只需要走3步，那么步数大概是 $n \times \sqrt n + n \times (\sqrt n-1) + n = 2n\sqrt n$ 数据范围是 $1 0^{4}$ ，那么最大步数就是 $2 \times 10^6$ ，符合题目的步数限制，并且还多给了 $1 0^{4}$ 步可供乱搞（快说谢谢清楚姐夫）。

最后根据四个方向写四份代码即可。。。。。。（以下省略114514行，共1919810个字，点击下方“龙门粗口”进行查看）

龙门粗口

代码如下：

#include <bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    while(T--){
        int n,m;
        char ch;
        cin>>n>>m>>ch;
        vector<PII> a(m);
        for(auto &[x,y] : a){
            cin>>x>>y;
        }
        vector mp(n/100+1,map<int,map<int,int>>());
        string ans;
        if(ch=='U' || ch=='D'){
            for(auto &[x,y] : a){
                mp[y/100][x][y]++;
            }
            int x = 0 , y = 0;
            for(int i=0;i<=n/100;i++){
                for(;;){
                    if(mp[i].count(x)){
                        for(auto &[yy,_] : mp[i][x]){
                            if(y<yy){
                                for(;y<yy;y++){
                                    ans += 'R';
                                }
                            }
                            else{
                                for(;y>yy;y--){
                                    ans += 'L';
                                }
                            }
                        }
                    }
                    if(ch=='U'){
                        ans += 'D';
                        x = (x+1)%n;
                    }
                    else{
                        ans += 'U';
                        x = (x-1+n)%n;
                    }
                    if(x==0) break;
                }
                for(;y<=(i+1)*100;y++){
                    ans += 'R';
                }
            }
        }
        else{
            for(auto &[x,y] : a){
                mp[x/100][y][x]++;
            }
            int x = 0 , y = 0;
            for(int i=0;i<=n/100;i++){
                for(;;){
                    if(mp[i].count(y)){
                        for(auto &[xx,_] : mp[i][y]){
                            if(x<xx){
                                for(;x<xx;x++){
                                    ans += 'D';
                                }
                            }
                            else{
                                for(;x>xx;x--){
                                    ans += 'U';
                                }
                            }
                        }
                    }
                    if(ch=='L'){
                        ans += 'R';
                        y = (y+1)%n;
                    }
                    else{
                        ans += 'L';
                        y = (y-1+n)%n;
                    }
                    if(y==0) break;
                }
                for(;x<=(i+1)*100;x++){
                    ans += 'D';
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60660399

J 清楚姐姐学排序

中等题，拓扑排序

注意：这又是歪门邪道，暴力大师，常数战神！std 复杂度为 $O (n m / 64)$ ，我的复杂度为 $O (n m l o g_{2} n)$ （也就小小640倍常数罢了，小问题）。

首先，不确定的排序显然大概率是拓扑，那么要求出精确排名，就要知道，比 $x$ 大的数的个数 + 比 $x$ 小的个数 + 1 要恰好等于 $n$ ，若是小于 $n$ ，则说明不确定位置，若大于 $n$ ，则说明题目给的大小关系一定有问题（显然，但不会证明）。

那么，维护比每个数小或等的数有哪些即可（反过来维护大的也行，但要把建边方向也修改），我用的是 map 维护，也可以和 std 一样使用 bitset 维护。

拓扑肯定要先建边，建边方式就是将小的数字向大的数字连一条有向边，拓扑转移的时候把比小的数字对应的 map 加入到大的数字对应的 map 。

最后寻找答案，对于 $x$ 的位置，若是 $x$ 对应的 map 的 size（小于等于 $x$ 的数字有哪些）+ 可以找到 $x$ 的 map 数量（大于等于 $x$ 的数字对应的 map ） - $1$ 恰好等于 $n$ (小于等于，大于等于，恰好重复一个)，那么 $x$ 所在的位置就是 $x$ 对应的 map 的 size 。

代码如下：

#include <bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    while(T--){
        int n,m;
        cin>>n>>m;
        vector ve(n+1,vector<int>());
        vector<int> in(n+1),a(n+1,-1);
        vector mp(n+1,map<int,int>());
        for(int i=1;i<=m;i++){
            int u,v;
            cin>>u>>v;
            ve[u].push_back(v);
            in[v]++;
        }
        auto topu = [&](){
            queue<int> q;
            for(int i=1;i<=n;i++){
                if(!in[i]) q.push(i);
            }
            while(q.size()){
                auto u = q.front();
                q.pop();
                mp[u][u]++;
                for(auto &i : ve[u]){
                    in[i]--;
                    if(!in[i]) q.push(i);
                    for(auto &[x,y] : mp[u]){
                        mp[i][x]++;
                    }
                }
            }
        };
        topu();
        for(int i=1;i<=n;i++){
            int l = mp[i].size();
            int r = 0;
            for(int j=1;j<=n;j++){
                if(mp[j].count(i)) r++;
            }
            if(l+r-1==n) a[l] = i;
        }
        for(int i=1;i<=n;i++){
            cout<<a[i]<<" ";
        }
    }
    return 0;
}

提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60652166

K 清楚姐姐玩翻翻乐

防AK题（确实防住了我AK），暴力期望DP，不会做，听不明白。

L 清楚姐姐的三角形I

签到题，人类智慧（我不是人类，没有智慧）

已知 $V_{A} = l_{b} + l_{c}, V_{B} = l_{a} + l_{c}, V_{C} = l_{a} + l_{b}$ 。

那 $l_{a} = ?$ 有菜逼卡了好久，是谁呢？

显然， $l_a \times 2 = V_B + V_B - V_a = l_a + l_c + l_a + l_b - (l_b + l_c)$ 。

剩下俩同理，然后注意这仨必须是偶数且能构成三角形。

代码如下：

#include <bits/stdc++.h>

using namespace std;
 
int main(){
    int T = 1;
    cin>>T;
    while(T--){
        int a,b,c;
        cin>>a>>b>>c;
        int A = b + c - a;
        int B = a + c - b;
        int C = a + b - c;
        if(A&1) goto no;
        if(B&1) goto no;
        if(C&1) goto no;
        if(A<1) goto no;
        if(B<1) goto no;
        if(C<1) goto no;
        if(A+B>C && A+C>B && B+C>A){
            cout<<"Yes\n"<<A/2<<" "<<B/2<<" "<<C/2<<endl;
        }
        else goto no;
        if(0) no:  cout<<"No"<<endl;
    }
    return 0;
}

提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60626984

M 清楚姐姐的三角形II

签到题，诈骗题（请下载国家反诈骗APP）

首先排除斐波那契。

然后考虑 1 2 1 无法构成三角形，好，这题结束了，记得不要写成模2，要写成模3（是谁 WA 了一发呢？）。

代码如下：

#include <bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    while(T--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            if(i%3) cout<<"114514 ";
            else cout<<"1919810 ";
        }
    }
    return 0;
}

提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60621794

我永远喜欢爱莉希雅！

快来加入爱莉神教吧！

爱门！！！

alt

「某一日，祂从天坠落。人们抬头仰望，于是看见了星空。」

「星月送来神的女儿，她愿成为人的伴侣。」

「长风化作她的轺车，四海落成她的园圃。鸟雀衔来善的种子，百花编织爱的颂歌。」

「她便是这样降生于世，行于大地，与人类一同长大，与世界一起发芽。」

「而今，终焉之时将至。」

「而今，归去之时已至。」

「就此告别吧，美丽的世界。」

「此后，将有群星闪耀，因为我如今来过。」

「此后，将有百花绽放，因为我从未离去。」

「请将我的箭、我的花、与我的爱，织成新生的种子，带向那枯萎的大地。」

「然后，便让它开出永恒而无瑕的…人性之华吧。」

「我名为爱莉希雅……」

「最初的律者，人之律者。」

alt

全部评论

推荐最新楼层

DullBean

哈尔滨工业大学(威海) Java

谢谢大佬！但是大佬吃了一天的饭吗

点赞回复分享

发布于 2023-01-31 20:17 江苏

Amigomust

北京师范大学机器学习

j题是可以O(n + m)吗

点赞回复分享

发布于 2023-01-31 21:17 广西

11-22 16:36

辽宁工程技术大学 C++

给牛友们释放一个京东offer

签了其他的了，今年就先不去东子做兄弟了，江湖再见

OfferJiaYi：给lz磕一个

点赞评论收藏

11-23 12:12

华东师范大学 FAE

现在可能唯一的offer都要没了

之前在校招会上拿到的地方国企职能岗的机会，每次被问秋招进展时，我都只能尴尬地说还在流程中。可如果继续这样拖下去，这个offer恐怕真的要泡汤了……每次想到这些，我开始怀疑自己，难道我真的不够优秀吗？希望接下来的面试能有转机吧。

牛客创作赏金赛

点赞评论收藏

10-09 09:39

门头沟学院 C++

第一个正式offer

😭😭😭

HHHHaos：这也太虚了，工资就一半是真的

点赞评论收藏

昨天 15:09

已编辑

北京戏曲艺术职业学院硬件开发

华为报批

和对接人沟通确认意向，地点等信息，属于第一批。已经报批，结果会在12.5号前公布，最晚推迟两个周。武汉终端硬件电源，bg985本。苦等两个月，一定要给我发offer

沉淀一会：1.同学你面试评价不错，概率很大，请耐心等待； 2.你的排名比较靠前，不要担心，耐心等待； 3.问题不大，正在审批，不要着急签其他公司，等等我们！ 4.预计9月中下旬，安心过节； 5.下周会有结果，请耐心等待下； 6.可能国庆节前后，一有结果我马上通知你； 7.预计10月中旬，再坚持一下； 8.正在走流程，就这两天了； 9.同学，结果我也不知道，你如果查到了也告诉我一声； 10.同学你出线不明朗，建议签其他公司保底！ 11.同学你找了哪些公司，我也在找工作。

点赞评论收藏