ABC418
|
比赛,题解
|

619 字
|
15 分钟

A

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
signed main() {
    int n;
    n=read();
    string s;
    cin>>s;
    s=" "+s;
    if(n<3||!(s[n-2]=='t'&&s[n-1]=='e'&&s[n]=='a')) {
        puts("No");
        exit(0);
    }
    puts("Yes");
    return 0;
}

B

注意精度。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
string s;
int n;
signed main() {
    cin>>s;
    n=s.size();
    s=" "+s;
    long double ans=0.0;
    rep(l,1,n) rep(r,l+2,n) {
        int len=r-l+1;
        if(!(s[l]=='t'&&s[r]=='t')) continue;
        int cnt=0;
        rep(i,l+1,r-1) if(s[i]=='t') cnt++;
        long double k=1.0;
        ans=max(ans,k*cnt/(len-2));
    }
    cout<<fixed<<setprecision(17)<<ans;
    return 0;
}

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)$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N=3e5+5;
int n, q, p, a[N];
ll s[N];
int check(ll mid,int b) {
    int p=lower_bound(a+1,a+n+1,b)-a;
    ll res=s[p-1]+(n-p+1)*1ll*(b-1);
    return res<mid;
}
signed main() {
    n=read(), q=read();
    rep(i,1,n) a[i]=read();
    sort(a+1,a+n+1);
    rep(i,1,n) s[i]=s[i-1]+a[i];
    while(q--) {
        int b=read();
        ll l=b, r=s[n];
        while(l<r) {
            ll mid=(l+r)>>1;
            if(check(mid,b)) r=mid; else l=mid+1;
        }
        if(check(l,b)) cout<<l<<endl; else puts("-1");
    }
    return 0;
}

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)$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N=2e5+5;
int n, a[N], sum[N];
int cnt[N][2], c[2];
string s;
int op(int x,int y) {
    if(x==y) return 1;
    return 0;
}
signed main() {
    n=read();
    cin>>s;
    s=" "+s;
    ll ans=0;
    rep(i,1,n) {
        a[i]=s[i]-'0';
        if(a[i]==1) ans++;
    }
    sum[1]=a[1];
    rep(i,2,n) {
        sum[i]=op(sum[i-1],a[i]);
    }
    c[1]++;
    rep(r,2,n) {
        // printf("sum[%d]=%d c=%d\n",r,sum[r],c[sum[r]]);
        ans+=c[sum[r]];
        c[sum[r-1]]++;
    }
    // 存在k，使得 ^[l,k]=^[k+1,r]
    // 即使得 sum[k]^sum[l-1]=sum[r]^sum[k]
    // 即 sum[l-1]=sum[r]
    cout<<ans;
    return 0;
}

E

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

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

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

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N=2005;
int n, m, tot;
struct node {
    ll x, y;
    node() {};
    node(int a,int b) { x=a, y=b; }
    friend bool operator<(const node& a,const node& b) {
        return a.y*b.x<a.x*b.y;
        // a:y/x < b:y/x -> ay*bx<ax*by
    }
} a[N];
PII zh[N*N];
long double slp[N*N];
signed main() {
    n=read();
    rep(i,1,n) {
        a[i].x=read(), a[i].y=read();
    }
    ll ttt=0;
    rep(i,1,n) rep(j,i+1,n) {
        // solpe[++m]=node(a[j].x-a[i].x,a[j].y-a[i].y);
        long double k=1.0;
        if(a[i].x!=a[j].x) slp[++m]=k*(a[j].y-a[i].y)/(a[j].x-a[i].x);
        else slp[++m]=-1e18;
    }
    sort(slp+1,slp+m+1);
    int lst=0;
    ll ans=0;
    rep(i,1,m) {
        // cout<<slp[i]<<endl;
        if(i==m||slp[i]!=slp[i+1]) {
            ll cnt=i-lst;
            ll dlt=cnt*(cnt-1)/2;
            ans+=dlt;
            lst=i;
        }
    }
    rep(i,1,n) rep(j,i+1,n) {
        zh[++tot]={a[i].x+a[j].x,a[i].y+a[j].y};
    }
    sort(zh+1,zh+tot+1);
    lst=0;
    rep(i,1,tot) {
        if(i==tot||!(zh[i].fi==zh[i+1].fi&&zh[i].se==zh[i+1].se)) {
            ll cnt=i-lst;
            ll dlt=cnt*(cnt-1)/2;
            if(dlt>0) {
                // printf("[%d,%d]\n",zh[i].fi,zh[i].se);
                // cout<<dlt<<endl;
            }
            ans-=dlt; 
            lst=i;
        }
    }
    cout<<ans;
    return 0;
}

F

等着吧。

DP计数
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇