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

清楚姐姐学信息论

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

alt

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

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

A 清楚姐姐学信息论

签到题，结论

进制是效率最高的进制，越靠近e进制效率越高，所以除 (2 3),(3 2)(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=7m=7 为例，对于 bb 数组的数字对将会是 (1,6),(2,5),(3,4),(4,3),(5,2),(6,1),(0,0)(1,6),(2,5),(3,4),(4,3),(5,2),(6,1),(0,0) ，他们的差值分别是 2,4,6,1,3,5,02,4,6,1,3,5,0 。

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

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

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

代码如下：

#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(n2n)O(n^2\sqrt n)。

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

然后对于第 jj 个物品，找到其所在的组数，把这组除了 jj 以外的物品装入背包（最多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)O(1) 解决，也可以使用二分直接无脑解决。

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

最后计算答案，记得开 long longlong\ 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×1640)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×n+n×(n−1)+n=2nnn \times \sqrt n + n \times (\sqrt n-1) + n = 2n\sqrt n 数据范围是 10410 ^ 4 ，那么最大步数就是 2×1062 \times 10^6 ，符合题目的步数限制，并且还多给了 10410^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(nm/64)O(nm/64) ，我的复杂度为 O(nmlog2n)O(nmlog_2n) （也就小小640倍常数罢了，小问题）。

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

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

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

最后寻找答案，对于 xx 的位置，若是 xx 对应的 map 的 size（小于等于 xx 的数字有哪些）+ 可以找到 xx 的 map 数量（大于等于 xx 的数字对应的 map ） - 11 恰好等于 nn (小于等于，大于等于，恰好重复一个)，那么 xx 所在的位置就是 xx 对应的 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

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

已知 VA=lb+lc,VB=la+lc,VC=la+lbV_A = l_b + l_c , V_B = l_a + l_c , V_C = l_a + l_b 。

那 la=?l_a = ? 有菜逼卡了好久，是谁呢？

显然，la×2=VB+VB−Va=la+lc+la+lb−(lb+lc)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

全部评论
谢谢大佬！但是大佬吃了一天的饭吗
点赞 回复 分享
发布于 2023-01-31 20:17 江苏
j题是可以O(n + m)吗
点赞 回复 分享
发布于 2023-01-31 21:17 广西

相关推荐

11-19 13:05
河北大学 电力电子工程师
点赞 评论 收藏
分享
头像
11-19 20:17
门头沟学院 C++
点赞 评论 收藏
分享
11-19 12:10
湖南财政经济学院 Java
点赞 评论 收藏
分享
10-30 21:50
门头沟学院 测试工程师
点赞 评论 收藏
分享
11-19 09:47
陕西理工大学 Java
点赞 评论 收藏
分享
15 2 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
286811次浏览 2518人参与
# 学历or实习经历，哪个更重要 #
48873次浏览 378人参与
# 北方华创开奖 #
25201次浏览 274人参与
# 地方国企笔面经互助 #
3457次浏览 7人参与
# 美团求职进展汇总 #
1323123次浏览 12416人参与
# 选完offer后，你后悔学本专业吗 #
18273次浏览 130人参与
# 阿里云管培生offer #
4185次浏览 86人参与
# 如何一边实习一边秋招 #
990076次浏览 12628人参与
# 得物求职进展汇总 #
65519次浏览 677人参与
# 腾讯求职进展汇总 #
194771次浏览 1632人参与
# 银行笔面经互助 #
82088次浏览 872人参与
# 提前批简历挂麻了怎么办 #
145967次浏览 1942人参与
# 0offer是寒冬太冷还是我太菜 #
895333次浏览 7985人参与
# 海康威视求职进展汇总 #
397851次浏览 3403人参与
# 机械人，你在招聘流程中的企业有哪些？ #
17755次浏览 186人参与
# 许愿池 #
213166次浏览 2529人参与
# 国央企薪资爆料 #
5162次浏览 38人参与
# 网申一定要掌握的小技巧 #
5242次浏览 52人参与
# 你们公司几号发工资 #
10656次浏览 99人参与
# 没有实习经历，还有机会进大厂吗 #
810512次浏览 13914人参与
# 你最想要的公司福利是？ #
44606次浏览 178人参与
# 听到哪句话就代表面试稳了or挂了？ #
93705次浏览 785人参与
牛客网
牛客企业服务