首页 > 其他分享 >AtCoder Beginner Contest 330 ABCDE

AtCoder Beginner Contest 330 ABCDE

时间:2024-02-01 22:34:03浏览次数:38  
标签:AtCoder const int ABCDE 330 long cin tie 2010

AtCoder Beginner Contest 330 ABCDE

A - Counting Passes

签到题,不多说。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n,m; cin>>n>>m;
    int cnt = 0;
    for(int i = 1;i <= n; i++)
    {
        int x; cin>>x;
        cnt += (x >= m);
    }
    cout<<cnt<<"\n";


    return 0;
}

B - Minimize Abs 1

题意:有一个长为 \(N\) 的数列 \(A\) 和两个整数 \(L,R\)。对于每个 \(A_{i}\),你需要选出一个数 \(X_{i}\),满足如下条件:

  • \(L\le X_{i}\le R\)
  • 对于所有整数 \(L\le Y\le R\),\(|X_{i}-A_{i}|\le|Y-A_i|\)

思路:二分

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n,l,r; cin>>n>>l>>r;
    for(int i = 1;i <= n; i++)
    {
        int x; cin>>x;
        int L = l,R = r;
        while(L<=R)
        {
            int mid = (L+R)/2;
            if(mid >= x) R = mid-1;
            else L = mid+1;
        }
        cout<<min(r,R+1)<<" ";
    }


    return 0;
}

C - Minimize Abs 2

题意:给你一个整数\(D\),找到对于非负整数\(x,y\)的\(|x^2+y^2-D|\)的最小值

思路:相比上一题,这是2个数,怎么办哩。可以考虑枚举x,二分y。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    ll n; cin>>n;
    ll ans = 1e18;
    for(ll i = 1;i*i <= n; i++)
    {
        ll x = i;
        ll l = 0,r = 1e6;
        while(l<=r)
        {
            ll mid = (l+r)>>1;
            if(mid*mid+x*x >= n)r = mid-1;
            else l = mid+1;
        }
        //cout<<"x = "<<x<<" r+1 = "<<r+1<<"\n";
        ans = min({ans,min(abs(x*x+r*r-n),abs(x*x+(r+1)*(r+1)-n))});
    }
    cout<<ans<<"\n";

    return 0;
}

D - Counting Ls

题意:现有一个 \(N\) 行 \(N\) 列的字符数组,满足对于每个 \(1 \le i \le N,1 \le j \le N\) 都有 $ S_{i,j} \in {o,x} $

请问在该数组里有多少个满足以下条件的三方格组:

  • 三个格子内都是 \(o\)

  • 三个方格互不相同

  • 恰好有两个方格在同一行

  • 恰好有两个方格在同一列

思路:藕一开始的思路是,可以先用前缀和求出每个点朝四个方向的贡献,然后加起来。

下面是藕写的依托答辩QAQ...

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
char a[2010][2010];
int b[2010][2010],b1[2010][2010],b2[2010][2010],b3[2010][2010];
int c[2010][2010],c1[2010][2010],c2[2010][2010],c3[2010][2010];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n; cin>>n;
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= n; j++)
            cin>>a[i][j];
    for(int i = 1;i <= n; i++)
    {
        for(int j = n;j >= 1; j--)
        {
            b[i][j] = b[i][j+1]+(a[i][j]=='o');
        }
    }

    for(int j = 1;j <= n; j++)
    {
        for(int i = n;i >= 1; i--)
        {
            c[i][j] = c[i+1][j]+(a[i][j]=='o');
        }
    }

    for(int i = n;i >= 1; i--)
    {
        for(int j = 1;j <= n; j++)
        {
            b1[i][j] = b1[i][j-1]+(a[i][j]=='o');
        }
    }

    for(int j = n;j >= 1; j--)
    {
        for(int i = 1;i <= n; i++)
        {
            c1[i][j] = c1[i-1][j]+(a[i][j]=='o');
        }
    }


    for(int i = n;i >= 1; i--)
    {
        for(int j = n;j >= 1; j--)
        {
            b2[i][j] = b2[i][j+1]+(a[i][j]=='o');
        }
    }

    for(int j = 1;j <= n ; j++)
    {
        for(int i = 1;i <= n; i++)
        {
            c2[i][j] = c2[i-1][j]+(a[i][j]=='o');
        }
    }


    for(int i = 1;i <= n; i++)
    {
        for(int j = 1;j <= n; j++)
        {
            b3[i][j] = b3[i][j-1]+(a[i][j]=='o');
        }
    }

    for(int j = n;j >= 1 ; j--)
    {
        for(int i = n;i >= 1; i--)
        {
            c3[i][j] = c3[i+1][j]+(a[i][j]=='o');
        }
    }


    // for(int i = 1;i <= n; i++)
    // {
    //     for(int j = 1;j <= n; j++)
    //         cout<<b[i][j]<<" ";
    //     cout<<"\n";
    // }

    ll ans = 0;
    for(int i = 1;i <= n; i++)
    {
        for(int j = 1;j <= n; j++)
        {
            if(a[i][j]=='o'){
                ans += (b[i][j]-1)*(c[i][j]-1);
                ans += (b1[i][j]-1)*(c1[i][j]-1);
                ans += (b2[i][j]-1)*(c2[i][j]-1);
                ans += (b3[i][j]-1)*(c3[i][j]-1);
                
            }
        }
    }

   
    cout<<ans<<"\n";
    return 0;
}

但是想想其实没有那么复杂,因为不用考虑方向呀,直接统计行列的贡献即可。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
char a[2010][2010];
int r[2010],c[2010];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n; cin>>n;
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= n; j++)
            cin>>a[i][j];
    for(int i = 1;i <= n; i++)
    {
        for(int j = 1;j <= n; j++)
        {
            if(a[i][j]=='o')
                r[i]++,c[j]++;
        }
    }
    ll ans = 0;
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= n; j++)if(a[i][j]=='o'){
            ans += (r[i]-1)*(c[j]-1);
        }
    cout<<ans<<"\n";
    return 0;
}

E - Mex and Update

题意:给定一个序列,支持单点修改,每次修改后输出全局 \(\operatorname{mex}\)。

一个序列的 \(\operatorname{mex}\) 定义为,序列中最小的没有出现过的非负整数。

思路:权值树状数组+二分,具体看代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201000;
template<class T>
struct BIT {
    T c[N];
    int size;
    void resize(int s) { size = s;}
    T query(int x) { // 1 ... x
        assert(x <= size);
        T s = 0;
        for (; x; x -= x & (-x)) {
        s += c[x];
    }
    return s;
    }

    void modify(int x, T s) { // a[x] += s
        assert(x != 0);
        for (; x <= size; x += x & (-x)) {
            c[x] += s;
        }
    } 
};

BIT<ll> tr;
int n,q,a[N],vis[N];
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	tr.resize(n+1);
	for(int i = 1;i <= n; i++)
	{
		cin>>a[i];
		a[i]++;//树状数组1 base的
		a[i] = min(a[i],n+1);//虽然a[i]范围很大,但是mex的值只会在n+1以内。
		vis[a[i]]++;
		if(vis[a[i]]==1)tr.modify(a[i],1);//存在改为1
	}

	while(q--)
	{
		int i,x; cin>>i>>x;
		x = min(x,n+1);
		x++;
		vis[a[i]]--;
		if(vis[a[i]]==0)tr.modify(a[i],-1);
		a[i] = x;
		vis[a[i]]++;
		if(vis[a[i]]==1)tr.modify(a[i],1);

		int l = 1,r = n+1;
		while(l<=r)
		{
			int mid = (l+r)/2;
			if(tr.query(mid) == mid) l = mid+1;
			else r = mid-1;
		}
		cout<<l-1<<"\n";
	}

	return 0;
}

标签:AtCoder,const,int,ABCDE,330,long,cin,tie,2010
From: https://www.cnblogs.com/nannandbk/p/18002272

相关文章

  • AtCoder Beginner Contest 336
    ABC336总结AtCoderBeginnerContest336A-LongLoong翻译给定一个数\(n\),请输出一个由一个L、\(n\)个o、一个n和一个g组成的字符串(区分大小写)。分析按题意模拟即可。code#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1......
  • AtCoder Beginner Contest 337 D
    AtCoderBeginnerContest337DD-CheatingGomokuNarabe题意:\(W\)列的矩阵,矩阵由o、x、.三种字符组成。你可以进行若干次操作(可以不做),每次操作可以把矩阵中的一个.改成o。请问最少经过多少次操作后,能在矩阵中找到位于同一行或同一列的连续\(K\)个o。思路:这题......
  • AtCoder Regular Contest 170
    A贪心。首先判无解。如果一个位置要变成A,那么它右边必须要有个B。如果一个位置要变成B,那么它右边必须要有个A。然后算答案,首先有一个明显的上限:\[\sum_{i=1}^{n}[s_i\neqt_i]\]假设我们有\(i\)位置要变成A,\(j\)位置要变成B,且\(i<j\),那么可以减少一次操作,扫一遍......
  • AtCoder Beginner Contest 338
    ABC338总结A-Capitalized?翻译给你一个由大写和小写英文字母组成的非空字符串\(S\)。请判断是否满足以下条件:\(S\)的第一个字符是大写字母,其他所有字符都是小写字母。如果满足,输出Yes,否则输出No。分析按题目说的判断即可。code#include<bits/stdc++.h>usingn......
  • AtCoder Beginner Contest 337
    ABC337总结A.Scoreboard翻译Takahashi队和Aoki队进行了\(N\)场比赛。在\(i\)/th比赛\((1\leqi\leqN)\)中,Takahashi队得了\(X_i\)分,Aoki队得了\(Y_i\)分。在\(N\)场比赛中总得分较高的队伍获胜。输出获胜者。如果两队总得分相同,则输出Draw。分析将得分分别加起来......
  • AtCoder Beginner Contest 338 c题二分思路
    观察题目可知,会有一个最大的x(两个菜的最大制作数),大于这个x就不能做任何一盘菜,小于这个x那么一定可以做出来,这样分析就是显而易见的递归。实现递归的check函数,那么我们就可以把两个菜的总制作数传进去。那么什么时候true什么时候false呢,就是判断每种材料的制作量有没有超过原材料......
  • AtCoder Beginner Contest 338
    A-Capitalized?#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongusingvi=vector<int>;usingi32=int32_t;usingpii=pair<int,int>;constintinf=1e9,INF=1e18;i32main(){strings;cin>>......
  • AtCoder Beginner Contest 338
    基本情况A忘记大小写敏感卡了20分钟,BC秒了,E用树状数组草过去了,D错了25个点,似乎是交界没有判断好。B-FrequencyB-Frequency(atcoder.jp)这题还可以更优雅点。intmain(){strings;cin>>s;map<char,int>cnt;for(inti=0;i<s.size();i++......
  • AtCoder Beginner Contest 338
    基本情况:A和B直接秒了,C题没写出来大致是思路的问题,下面就讲一下C自己的思路和题解C-LeftoverRecipes题目概述,先输入一个数字代表有多少中配料,然后依次输入A菜每种配料所需的量,然后输入B菜每种配料所需的量,最后输出最多可以做多少盘菜样例:280030010010020010输出为......
  • AtCoder Beginner Contest 338
    AtCoderBeginnerContest338ABC切ABC,什么实力。C-LeftoverRecipesProblemStatementYourrefrigeratorhas\(N\)kindsofingredients.Letuscallthemingredient\(1\),\(\dots\),ingredient\(N\).Youhave\(Q_i\)gramsofingredient\(i\).......