Znzryb's Blog
0%

Posted on Edited on

思路讲解

题意概括——最少修改使任意3元组可以组成三角形

感觉这位的写的比较清楚，思路也比较易懂

排序什么的很好想，后面的有点难

总的来说就是不断选取（ai，ai+1）然后看以这个为母体，需要修改多少次，得到最少修改数，输出

这个具体的计算我们结合代码来讲

核心代码：

1
2
3
4
5
6
7
8
9
for(int i=0;i<n-2;++i) {
      ll l=lower_bound(A.begin(),A.end(),A[i+1])-A.begin();
      if(A[i]!=A[i+1])
          l-=1;
      if(l<0) l=0;
      ll r=lower_bound(A.begin(),A.end(),A[i]+A[i+1])-A.begin();
      ll lans=l+(n-r);
      ans=min(ans,lans);
}

l就是前面所有需要改成 A[i+1]A[i+1] 的数量（忽略A[i]A[i] ）

r就是后面所有需要改成 A[i]+A[i+1]A[i]+A[i+1] 的起始索引（哈哈，稍微有点混乱，不好意思）

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll MAXN=static_cast<ll>(2e5+10);
ll T,n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while (T--) {
        cin>>n;
        vector<ll> A(n);
        for(int i=0;i<n;++i) {
            cin>>A[i];
        }
        sort(A.begin(),A.end());
        ll ans=MAXN;
        for(int i=0;i<n-2;++i) {
            ll l=lower_bound(A.begin(),A.end(),A[i+1])-A.begin();
            if(A[i]!=A[i+1])
                l-=1;
            if(l<0) l=0;
            ll r=lower_bound(A.begin(),A.end(),A[i]+A[i+1])-A.begin();
            ll lans=l+(n-r);
            ans=min(ans,lans);
        }
        cout<<ans<<"\n";
    }
    return 0;
}
// AC https://codeforces.com/contest/2032/submission/292856092

心路历程（WA，TLE，MLE……）

毕竟采用了我不太熟悉的0-based-index，还是稍微有点小翻车，

lans=l+(n−r);lans=l+(n-r);

我因为比较熟悉1-based，写成了 n+1−rn+1-r 但这在0-based里是不对的，n-r其实是n−1−r+1n-1-r+1

n−1n-1为索引上界

Posted on Edited on

思路讲解

利用矩阵乘法结合律减少时间与空间复杂度

image

（W(QxKt)) x V → W*Q x (Kt x V) (其实这些括号都是吓唬你的，乘法哪来的什么括号)*

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll N=1e4+10;
ll n,d;
ll Q[N][25],K[N][25],Kt[25][N],V[N][25],W[N],Ktv[25][25];
//                  Kt即K的转置矩阵
ll QK[N][25];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>d;
    for(ll i=1;i<=n;++i)
        for(ll j=1;j<=d;++j)
            cin>>Q[i][j];
    for(ll i=1;i<=n;++i)
        for(ll j=1;j<=d;++j)
            cin>>K[i][j];
    for(ll i=1;i<=n;++i)
        for(ll j=1;j<=d;++j)
            cin>>V[i][j];
    for(ll i=1;i<=n;++i)
        cin>>W[i];
    for(int i=1;i<=n;++i)
        for(int j=1;j<=d;++j)
            Kt[j][i]=K[i][j];
    //  W*Q x (Kt x V)
    // (Kt x V)
    for(int i=1;i<=d;++i) {
        for(int j=1;j<=d;++j) {
            for(int k=1;k<=n;++k)
                        //  第i行    第j列
                Ktv[i][j]+=Kt[i][k]*V[k][j];
        }
    }
    // (W*Q)
    for(int i=1;i<=n;++i)
        for(int j=1;j<=d;++j)
            Q[i][j]=W[i]*Q[i][j];
    // (W*Q) x Ktv
    // (Q 为n*d大小)    (Ktv 为d x d 大小)
    // 乘完之后大小为（n*d）
    // 不存了，直接输出
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=d;++j) {
            ll res=0;
            for(int k=1;k<=d;++k) {
                res+=Q[i][k]*Ktv[k][j];
            }
            cout<<res<<" ";
        }
        cout<<endl;
    }
    return 0;
}
// AC https://oj.saikr.com/problem/detail/1893/submit

心路历程（WA，TLE，MLE……）

哈哈，矩阵嘛，总是有点烦人的，特别是那个乘法的循环很容易写错，不过还好，样例比较强，直接AC了

今天还比较顺利

Posted on Edited on

AC代码

1
2
3
4
5
6
7
8
class Solution {
public:
    int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        int x=max(0,min(ax2,bx2)-max(bx1,ax1));
        int y=max(0,min(ay2,by2)-max(by1,ay1));
        return (ax2-ax1)*(ay2-ay1)+(bx2-bx1)*(by2-by1)-x*y;
    }
};

心路历程（WA，TLE，MLE……）

Posted on Edited on

AC代码

主要思路见此题解

其实说白了就是有个公式可以算x轴投影重叠长度 y轴投影重叠长度 两个相乘就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll a,b;
    cin>>n>>a>>b;
    ll ans=0;
    for(ll i=1;i<=n;++i) {
        ll c,d,e,f;
        cin>>c>>d>>e>>f;
                // x 轴上投影                           // y 轴上投影
        ans+=max(0LL,min(a,e)-max(0LL,c))*max(0LL,min(b,f)-max(0LL,d));
    }
    cout<<ans<<endl;
    return 0;
}

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

无向图判环模版题，做cf之前来练练手

// 如果union函数发现根本不需要合并，那么a本来就在b的这个集合内

// 说明b有两条到达a的通路即形成了环

比较重要的两句话

AC代码

union是保留字，建议改为add（意思反正是这个意思）；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        vector<int> fa(1010);
        int n=edges.size();
        for(int i=1;i<=n;++i){  // 并查集初始化
            fa[i]=i;
        }
        for(int i=0;i<n;++i){
            int a=edges[i][0],b=edges[i][1];
            // 如果union函数发现根本不需要合并，本来就在这个集合内
            // 说明b有两条到达a的通路即形成了环
            if(!unionn(a,b,fa)){
                return {a,b};
            }
        }
        return {0,0};
    }
    int find(int x , vector<int> &fa){
        if(fa[x]!=x)
            fa[x]=find(fa[x],fa);
        return fa[x];
    }
    bool unionn(int a, int b, vector<int>& fa){
        if(find(a,fa)==find(b,fa)){
            return false;
        }else{
            fa[find(a,fa)]=find(b,fa);
            return true;
        }
    }
};

心路历程（WA，TLE，MLE……）

哈哈，第一次写力扣嘛，总归会遇到点问题，比如啥全角字符，什么union保留字，什么·······，不多赘述。