Znzryb's Blog
0%

Posted on Edited on 
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
// https://www.acwing.com/problem/content/791/
#include <iostream>
using namespace std;
const int maxn=100007;
int n,q,k,a[maxn];

int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }
    for(int _=1;_<=q;_++) {
        cin>>k;
        int l=1,r=n;
        while (l<r) {
            int mid=l+r>>1;
            if(a[mid]>=k) r=mid;
            else l=mid+1;
        }
        if(a[l]!=k) {
            cout<<"-1 -1"<<endl;
            continue;
        }
        int l2=1,r2=n;
        while (l2<r2) {
            int mid=l2+r2+1>>1;
            if(a[mid]<=k) l2=mid;
            else r2=mid-1;
        }
        cout<<l-1<<" "<<l2-1<<endl;
    }
    return 0;
}
// AC  https://www.acwing.com/problem/content/submission/code_detail/37312161/


Posted on Edited on

题目大意

给定 n 条线段，每条线段有两个端点坐标。移动时分为两种速度：移动到某条线段的起点/终点使用速度 s，沿着线段绘制使用速度 t。需要选择绘制线段的顺序及每条线段从哪一端开始，求完成全部绘制的最短总时间。

Pass 10/74 WA https://atcoder.jp/contests/abc374/submissions/58484468 赛时代码

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
#include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <deque>
using namespace std;
int n,s,t,pos[10][6];  // s->not emitting laser && t-> emitting ......
bool vis[10][6],vis2[10];
double ans=10000000,dis;
void dfs(int x,int y,int cnt){
    if(cnt>=n){
        ans=min(dis,ans);
        return;
    }
    for(int i=1;i<=n;i++){
        if(vis2[i]) continue;
        vis2[i]=true;
        double squareS1=(pos[i][3]-pos[i][1])*(pos[i][3]-pos[i][1]);
        double squareS2=(pos[i][4]-pos[i][2])*(pos[i][4]-pos[i][2]);
        double lenSeg=sqrt(squareS1+squareS2)/t;
        for(int j=1;j<=3;j+=2){
            double square1=(pos[i][j]-pos[x][y])*(pos[i][j]-pos[x][y]);
            double square2=(pos[i][j+1]-pos[x][y+1])*(pos[i][j+1]-pos[x][y+1]);
            double ldis=sqrt(square1+square2)/s;
            dis=dis+(ldis+lenSeg);
            dfs(i,j,cnt+1);
            dis=dis-(ldis+lenSeg);
        }
        vis2[i]=false;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>s>>t;
    for(int i=1;i<=n;i++){
        cin>>pos[i][1]>>pos[i][2]>>pos[i][3]>>pos[i][4];
    }
    dis=0;
    dfs(0,0,0);
    cout<<ans<<endl;
    //cin>>n;
}
// WA https://atcoder.jp/contests/abc374/submissions/58484468

只改了一个地方就AC了
dfs(i,4-j,cnt+1); // 进入点和终止点不是一个，这条线段的终止点就是下一条线段的起始点

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
#include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <deque>
using namespace std;
int n,s,t,pos[10][6];  // s->not emitting laser && t-> emitting ......
bool vis[10][6],vis2[10];
double ans=10000000,dis;
void dfs(int x,int y,int cnt){
    if(cnt>=n){
        ans=min(dis,ans);
        return;
    }
    for(int i=1;i<=n;i++){
        if(vis2[i]) continue;
        vis2[i]=true;
        double squareS1=(pos[i][3]-pos[i][1])*(pos[i][3]-pos[i][1]);
        double squareS2=(pos[i][4]-pos[i][2])*(pos[i][4]-pos[i][2]);
        double lenSeg=sqrt(squareS1+squareS2)/t;
        for(int j=1;j<=3;j+=2){
            double square1=(pos[i][j]-pos[x][y])*(pos[i][j]-pos[x][y]);
            double square2=(pos[i][j+1]-pos[x][y+1])*(pos[i][j+1]-pos[x][y+1]);
            double ldis=sqrt(square1+square2)/s;
            dis=dis+(ldis+lenSeg);
            dfs(i,4-j,cnt+1);   // 进入点和终止点不是一个，这条线段的终止点就是下一条线段的起始点
            dis=dis-(ldis+lenSeg);
        }
        vis2[i]=false;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>s>>t;
    for(int i=1;i<=n;i++){
        cin>>pos[i][1]>>pos[i][2]>>pos[i][3]>>pos[i][4];
    }
    dis=0;
    dfs(0,0,0);
    cout.precision(17);   // 打印double全精度
    cout<<ans<<endl;
    //cin>>n;
}
//AC https://atcoder.jp/contests/abc374/submissions/58506793
//AC https://www.luogu.com.cn/record/180435741

Posted on Edited on

题目大意

给定一个数组，通过若干次“除以 2 取整”的操作把元素压到一定范围内，要求最终能覆盖 0 到 x-1 的所有数（每个数至少出现一次），求最大的可行 x。通常用二分答案 + 贪心检查。

AC 代码 二分答案 相比于那个过了93.33%的还是修改了很多。

总体的check函数的贪心思路是 ≥x 的没用，之前就到过的（vis中有的）也没用。

没用，那怎么让他有用那？那当然是>>1才有用，不断的>>1，直到有用（注意条件，不要死循环了）。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71786526

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
#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <set>
using namespace std;
const int maxn=1e5+7,maxA=static_cast<int>(1e6)+7;
int n,t,a[maxA],A;
set<int> vis;
inline bool check(int x) {
    for(int i=n;i>=1;i--) {
        int ai=a[i];
        while(ai>=x)
            ai>>=1;
        while(vis.count(ai)!=0 && ai!=0)  // 到过以前到过的值不算有用 ai！=0防止死循环的发生
            ai>>=1;
        vis.insert(ai);
    }
    for(int i=0;i<=x-1;i++) {
        if(vis.count(i)==0)
            return false;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    for(int _=1;_<=t;_++) {
        cin>>n;
        for(int i=1;i<=n;i++) {
            cin>>a[i];
        }
        sort(&a[1],&a[n+1],less<int>());
        int l=0,r=n+1;  // 如果n个数连续，那么就是n
        while(l<r) {
            vis.clear();
            int mid=l+r+1>>1;
            if(check(mid)) l=mid;
            else r=mid-1;
        }
        cout<<l<<endl;
    }
    return 0;
}
// TLE https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785349
// 53.33% WA https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785676
// 93.33% WA https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785979
// AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71786526

TLE pass 2/30

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
#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=1e5+7,maxA=static_cast<int>(1e6)+7;
int n,t,a[maxA],A;
bitset<maxA> ovis,vis;
inline bool check(int x) {
    for(int i=n;i>=1;i--) {
        int ai=a[i];
        if(ai<x)
            break;
        while(ai>>=1) {
            if(!vis[ai] && ai<x) {vis[ai]=true;break;}
        }
    }
    for(int i=1;i<=x-1;i++) {
        if(!vis[i])
            return false;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    for(int _=1;_<=t;_++) {
        cin>>n;
        vis.reset();ovis.reset();   // 初始化
        for(int i=1;i<=n;i++) {
            cin>>a[i];A=max(A,a[i]);ovis[a[i]]=true;
        }
        sort(&a[1],&a[n+1],less<int>());
        int l=0,r=A;
        while(l<r) {
            for(int i=1;i<=A;i++)
                vis[i]=ovis[i];
            int mid=l+r+1>>1;
            if(check(mid)) l=mid;
            else r=mid-1;
        }
        cout<<l<<endl;
    }
    return 0;
}
// TLE https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785349

int l=0,r=n+1; // 如果n个数连续，那么就是n

for(int i=1;i<=n+1;i++)
vis[i]=ovis[i];

把上界换成n+1过了53.33% https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785676

但出现了WA

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
#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=1e5+7,maxA=static_cast<int>(1e6)+7;
int n,t,a[maxA],A;
bitset<maxA> ovis,vis;
inline bool check(int x) {
    for(int i=n;i>=1;i--) {
        int ai=a[i];
        if(ai<x)
            break;
        while(ai>>=1) {
            if(!vis[ai] && ai<x) {vis[ai]=true;break;}
        }
    }
    for(int i=1;i<=x-1;i++) {
        if(!vis[i])
            return false;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    for(int _=1;_<=t;_++) {
        cin>>n;
        vis.reset();ovis.reset();   // 初始化
        for(int i=1;i<=n;i++) {
            cin>>a[i];ovis[a[i]]=true;
        }
        sort(&a[1],&a[n+1],less<int>());
        int l=0,r=n+1;  // 如果n个数连续，那么就是n
        while(l<r) {
            for(int i=1;i<=n+1;i++)
                vis[i]=ovis[i];
            int mid=l+r+1>>1;
            if(check(mid)) l=mid;
            else r=mid-1;
        }
        cout<<l<<endl;
    }
    return 0;
}
// TLE https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785349

WA pass93.33% https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785979

应该是快了

增加了

1
2
3
4
for(int i=2;i<=n;i++) {
        if(a[i]>=x) break;
        if(a[i]==a[i-1]) vis[0]=true;break;
    }
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
#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=1e5+7,maxA=static_cast<int>(1e6)+7;
int n,t,a[maxA],A;
bitset<maxA> ovis,vis;
inline bool check(int x) {
    for(int i=2;i<=n;i++) {
        if(a[i]>=x) break;
        if(a[i]==a[i-1]) vis[0]=true;break;
    }
    for(int i=n;i>=1;i--) {
        int ai=a[i];
        if(ai<x)
            break;
        while(true) {
            ai>>=1;
            if(!vis[ai] && ai<x) {vis[ai]=true;break;}
            if(ai==0)
                break;
        }
    }
    for(int i=0;i<=x-1;i++) {
        if(!vis[i])
            return false;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    for(int _=1;_<=t;_++) {
        cin>>n;
        vis.reset();ovis.reset();   // 初始化
        for(int i=1;i<=n;i++) {
            cin>>a[i];ovis[a[i]]=true;
        }
        sort(&a[1],&a[n+1],less<int>());
        int l=0,r=n+1;  // 如果n个数连续，那么就是n
        while(l<r) {
            for(int i=0;i<=n+1;i++)
                vis[i]=ovis[i];
            int mid=l+r+1>>1;
            if(check(mid)) l=mid;
            else r=mid-1;
        }
        cout<<l<<endl;
    }
    return 0;
}
// TLE https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785349
// 53.33% WA https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785676

Posted on Edited on

题目大意

给定一段字符串（或若干字符串），需要按题意进行判断/构造，输出对应结果。（该页目前为空，我先补上题意标题，具体题意可后续再补充链接或样例。）

Posted on Edited on

题目大意

给定若干根木棍长度，要求从中选出 3 根组成一个三角形，并使三角形周长最大；若无法组成任何三角形则输出 -1。

25pts，暴力dfs，TLE

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
#include <iostream>
#include <vector>
using namespace std;
const int maxn=1e4+10;
long long int T,n,aa[maxn],ans;
bool vis[maxn];

long long int summ(vector<int> tri,int c) {
    int a=tri[0],b=tri[1];
    if(a+b<=c) {
        return -1;
    }else if(a+c<=b) {
        return -1;
    }else if(b+c<=a) {
        return -1;
    }
    return a+b+c;
}

void dfs(int y,vector<int>triangle) {
    for(int i=0;i<n;i++) {
        if(!vis[i]) {
            if(y+1==3) {
                //cout<<triangle[0]<<" "<<triangle[1]<<" "<<aa[i]<<endl;
                ans=max(ans,summ(triangle,aa[i]));
                continue;
            }
            triangle.push_back(aa[i]);vis[i]=true;
            dfs(y+1,triangle);
            triangle.pop_back();vis[i]=false;
        }
    }
}

int main()
{
    cin>>T;
    while (T--) {
        fill(begin(aa),end(aa),0);
        fill(begin(vis),end(vis),false);
        ans=-1;
        cin>>n;
        for(int i=0;i<n;i++) {
            cin>>aa[i];
        }
        dfs(0,{});
        cout<<ans<<endl;
    }
    return 0;
}

参考的题解思路

https://ac.nowcoder.com/acm/discuss/blogs?tagId=271232

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
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e4+7;
const ll maxLen=static_cast<ll>(1e18)+7;
ll len[maxn],n,t,ans;
int main() {
    cin>>t;
    for(int _=1;_<=t;_++) {
        cin>>n;
        for(int i=1;i<=n;i++) {
            cin>>len[i];
        }
        ans=0;
        sort(&len[1],&len[n+1],less<int>());
        for(int i=n;i>=3;i--) {
            for(int j=i-1;j>=2;j--) {
                if(len[j-1]+len[j]<=len[i])  // 别写反了，这是不满足条件的情况
                    break;
                ans=max(ans,len[j-1]+len[j]+len[i]);  // 如果这个不能，那继续往下枚举也没有意义，因为次大+次次大<大边
                break;
            }
        }
        if(ans==0) {
            cout<<-1<<endl;
        }else {
            cout<<ans<<endl;
        }
    }
}
//AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71774749