ABC418

A

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define pf push_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
signed main() {
25
    int n;
26
    n=read();
27
    string s;
28
    cin>>s;
29
    s=" "+s;
30
    if(n<3||!(s[n-2]=='t'&&s[n-1]=='e'&&s[n]=='a')) {
31
        puts("No");
32
        exit(0);
33
    }
34
    puts("Yes");
35
    return 0;
36
}

B

注意精度。

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define pf push_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
string s;
25
int n;
26
signed main() {
27
    cin>>s;
28
    n=s.size();
29
    s=" "+s;
30
    long double ans=0.0;
31
    rep(l,1,n) rep(r,l+2,n) {
32
        int len=r-l+1;
33
        if(!(s[l]=='t'&&s[r]=='t')) continue;
34
        int cnt=0;
35
        rep(i,l+1,r-1) if(s[i]=='t') cnt++;
36
        long double k=1.0;
37
        ans=max(ans,k*cnt/(len-2));
38
    }
39
    cout<<fixed<<setprecision(17)<<ans;
40
    return 0;
41
}

C

注意到答案具有单调性，于是二分答案转为判定问题。

一个 $x$ 合法，当且仅当对方无论怎么选都会选出 $b$ 个同类元素。那么对方最多选出 $\\sum\_{i=1}^n \\min(a\_i,b-1)$ 个元素，与 $x$ 比较一下即可。

如何快速求这个东西呢？按照 $a\_i$ 排序，每次二分出临界位置，利用前缀和就行。

复杂度 $O(Q \\log\\sum\_{i=1}^nA\_i \\log n)$ 。

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define pf push_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N=3e5+5;
25
int n, q, p, a[N];
26
ll s[N];
27
int check(ll mid,int b) {
28
    int p=lower_bound(a+1,a+n+1,b)-a;
29
    ll res=s[p-1]+(n-p+1)*1ll*(b-1);
30
    return res<mid;
31
}
32
signed main() {
33
    n=read(), q=read();
34
    rep(i,1,n) a[i]=read();
35
    sort(a+1,a+n+1);
36
    rep(i,1,n) s[i]=s[i-1]+a[i];
37
    while(q--) {
38
        int b=read();
39
        ll l=b, r=s[n];
40
        while(l<r) {
41
            ll mid=(l+r)>>1;
42
            if(check(mid,b)) r=mid; else l=mid+1;
43
        }
44
        if(check(l,b)) cout<<l<<endl; else puts("-1");
45
    }
46
    return 0;
47
}

D

这个操作与异或是反着的。仍然满足结合律，可以差分。也就是说同一个区间，无论怎么操作，得到的结果都是一样的。

如果 $[l,r]$ 合法，那么一定存在 $k$ ，使得 $\text{op}([l,k]) = \text{op}(k+1,r)$ 。

即

S(k) \oplus S(l-1) = S(r) \oplus S(k)

即

S(l-1) = S(r)

开个桶扫一遍即可。

注意 $S(r) \\oplus 1 = S(r)$ 。

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define pf push_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N=2e5+5;
25
int n, a[N], sum[N];
26
int cnt[N][2], c[2];
27
string s;
28
int op(int x,int y) {
29
    if(x==y) return 1;
30
    return 0;
31
}
32
signed main() {
33
    n=read();
34
    cin>>s;
35
    s=" "+s;
36
    ll ans=0;
37
    rep(i,1,n) {
38
        a[i]=s[i]-'0';
39
        if(a[i]==1) ans++;
40
    }
41
    sum[1]=a[1];
42
    rep(i,2,n) {
43
        sum[i]=op(sum[i-1],a[i]);
44
    }
45
    c[1]++;
46
    rep(r,2,n) {
47
        // printf("sum[%d]=%d c=%d\n",r,sum[r],c[sum[r]]);
48
        ans+=c[sum[r]];
49
        c[sum[r-1]]++;
50
    }
51
    // 存在k，使得 ^[l,k]=^[k+1,r]
52
    // 即使得 sum[k]^sum[l-1]=sum[r]^sum[k]
53
    // 即 sum[l-1]=sum[r]
54
    cout<<ans;
55
    return 0;
56
}

E

两条斜率相同的线确定一个四边形。

平行四边形可能每组对边统计一次，求出平行四边形数量减一遍就行。

如何确定？平行四边形的充要条件是对角线中点重合。统计每条边的中点，中点相同的选一下即可。

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define pf push_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N=2005;
25
int n, m, tot;
26
struct node {
27
    ll x, y;
28
    node() {};
29
    node(int a,int b) { x=a, y=b; }
30
    friend bool operator<(const node& a,const node& b) {
31
        return a.y*b.x<a.x*b.y;
32
        // a:y/x < b:y/x -> ay*bx<ax*by
33
    }
34
} a[N];
35
PII zh[N*N];
36
long double slp[N*N];
37
signed main() {
38
    n=read();
39
    rep(i,1,n) {
40
        a[i].x=read(), a[i].y=read();
41
    }
42
    ll ttt=0;
43
    rep(i,1,n) rep(j,i+1,n) {
44
        // solpe[++m]=node(a[j].x-a[i].x,a[j].y-a[i].y);
45
        long double k=1.0;
46
        if(a[i].x!=a[j].x) slp[++m]=k*(a[j].y-a[i].y)/(a[j].x-a[i].x);
47
        else slp[++m]=-1e18;
48
    }
49
    sort(slp+1,slp+m+1);
50
    int lst=0;
51
    ll ans=0;
52
    rep(i,1,m) {
53
        // cout<<slp[i]<<endl;
54
        if(i==m||slp[i]!=slp[i+1]) {
55
            ll cnt=i-lst;
56
            ll dlt=cnt*(cnt-1)/2;
57
            ans+=dlt;
58
            lst=i;
59
        }
60
    }
61
    rep(i,1,n) rep(j,i+1,n) {
62
        zh[++tot]={a[i].x+a[j].x,a[i].y+a[j].y};
63
    }
64
    sort(zh+1,zh+tot+1);
65
    lst=0;
66
    rep(i,1,tot) {
67
        if(i==tot||!(zh[i].fi==zh[i+1].fi&&zh[i].se==zh[i+1].se)) {
68
            ll cnt=i-lst;
69
            ll dlt=cnt*(cnt-1)/2;
70
            if(dlt>0) {
71
                // printf("[%d,%d]\n",zh[i].fi,zh[i].se);
72
                // cout<<dlt<<endl;
73
            }
74
            ans-=dlt;
75
            lst=i;
76
        }
77
    }
78
    cout<<ans;
79
    return 0;
80
}

F

等着吧。

A

B

C

D

E

F

觉得这篇文章怎么样？

分享这篇文章

评论区

搜索结果

标签

分类

搜索结果

标签

分类

A

B

C

D

E

F

觉得这篇文章怎么样？

分享这篇文章

评论区