Znzryb's Blog
0%

Posted on Edited on

思路讲解

赛时其实什么都想到了，但因为代码编写的问题没过，唉，不多讲了。

image

唉，主要还是我不太熟悉0-based。

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
#include <bits/stdc++.h>

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

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while (T--) {
        string s;
        cin>>s;
        if(s.size()==1) {
            cout<<-1<<endl;
            continue;
        }
        int n=s.size();bool isBreak=false;
        for(int i=0;i<n-1;++i) {
            if(s[i]==s[i+1]) {  // ww pp 这种是可以的
                cout<<s[i]<<s[i+1]<<endl;
                isBreak=true;
                break;
            }
        }
        if(isBreak)
            continue;
        if(s.size()==2) {
            cout<<-1<<endl;
            continue;
        }
        // abc 可以分为a b c ab bc abc 6种 为偶数
        for(int i=0;i<n-2;++i) {
            if(s[i]!=s[i+1] && s[i]!=s[i+2] && s[i+1]!=s[i+2]) {
                cout<<s[i]<<s[i+1]<<s[i+2]<<endl;
                isBreak=true;
                break;
            }
        }
        if(isBreak)
            continue;
        // 能够逃过上面两重判定 必然是类似于abababab的  这种是无解的
        cout<<-1<<endl;
    }
    return 0;
}
// AC https://codeforces.com/contest/2039/submission/293064839

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

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……）