首页 > 其他分享 >Codeforces Round 962 (Div. 3)

Codeforces Round 962 (Div. 3)

时间:2024-08-07 20:49:55浏览次数:13  
标签:962 int 题解 ll Codeforces cin while Div include

A. Legs

-------------------------------------题解------------------------------

经典鸡兔同笼,数据范围不大,跑暴力就行

点击查看代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        if(n<=2) cout<<1<<'\n';
        else
        {
            cout<<n/4+(n%4!=0)<<'\n';
        }
    }
}

B. Scale

-----------------------------------------题解----------------------------

题目规定一定是合法的所以只需要稍微调整一下二重for循环让i++变成i+=m就行

点击查看代码
#include<bits/stdc++.h>
using namespace std;
char a[1005][1005];
char b[1005][1005];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                cin>>a[i][j];
            }
        }
      
        int x=1,y=1;
        for(int i=1;i<=n;i+=m)
        {
            for(int j=1;j<=n;j+=m)
            {
               b[x][y]=a[i][j];
               y++;
            }
            if(x==n/m) break;
            y=1;
            x++;
            
        }
   
        for(int i=1;i<=x;i++)
        {
            for(int j=1;j<=y-1;j++)
            {
                cout<<b[i][j];
            }
            cout<<endl;
        }
        
    }
}

C. Sort

------------------------------题解-------------------------
其实翻译一下就是要让a串和b串拥有的字母一样,给你一个l,r区间查询区间内有几个字母不一样,之前想过前缀和的办法没跑对,后来还是决定暴力,处理了一整个字符串中每个位置上下的字母差别的前缀和数量,只需要查询的时候相减就好了

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int c[27][N];
int main()
{  ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n,q;
        cin>>n>>q;
 
        string a="",b="";
 
        cin>>a>>b;
        a=" "+a;
        b=" "+b;
        map<char,int> m1,m2;
        for(int i=0;i<=n;i++)
        {
        	for(int j=1;j<=26;j++)c[i][j]=0;
		}
        for(int i=1;i<=n;i++)
        { 
        	for(int j=1;j<=26;j++)
        	{
        		c[i][j]=c[i-1][j];
        		if(j==int (a[i]-'a'+1)) c[i][j]++;
        		if(j==int(b[i]-'a'+1)) c[i][j]--;
			}
			
		}
			
				 
        
       
        while(q--)
        {
            int l,r;
            cin>>l>>r;
            int cnt=0;
          for(int i=1;i<=26;i++)
          {
          	cnt+=abs(c[r][i]-c[l-1][i]);
		  }
		  cout<<cnt/2<<'\n';
        }
    }
}
/*
1
7 4
abbccde
ppbccab

*/

D. Fun

------------------------------题解------------------------------

看到这种题,首先想到推公式,推公式不行想优化暴力,这题我一直想推公式,结果最后是需要优化暴力

我们假定a<=b<=c由题目给出的第二个公式可以知道aa + aa + aa <= ab + bc + ca<= n由此可以优化一重a 只跑a从1到aa3<=n的循环,b也一样我们只需要跑b*b<=n的循环就够了

我们再想办法去优化b由于由公式2变化可知(x-(a*b))/(a+b)>=c ,c<=x-a-b,我们要把c的值在两个当中去min值,累加起来就是答案

点击查看代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,n,x;
ll cnt;
void solve(){
	for(int a=1;a*a*3<=n;a++){
		for(int b=a;b*b<=n;b++){
			if(a+b>=x) break;
			if(a*b+a+b>n) break;
			int fk=(n-a*b)/(a+b);
			int ck=min(fk,x-a-b);
			if(ck<b) continue;
			
			//计算贡献
			if(a==b){
				cnt++;//a=b=c
				cnt+=(ck-b)*3; 
			} 
			else{
				cnt+=3;
				cnt+=(ck-b)*6;
			}
		}
	}
}
int main(){
	cin>>t;
	while(t--){
		cin>>n>>x;
		cnt=0;
		solve();
		cout<<cnt<<endl;
	}
}

E. Decode

好题!
----------------------------题解--------------------------------
能看到这里的都是糕手了,我主要讲解思路。题意找[l,r]的对数,没对至少有一组x,y满足条件。

我们用一个变量now记录前缀中0和1的差值 现在我们这样假设有这样一个数组11011 now的变化不就会是1 2 1 2 3 整个数组里是不是有两个1与两个2,会看字符串,当x=2 y=3,

x=3,y=4的时候符合题目要求 我们以其中一个x=2,y=3为例,它可以满足(n-y)*x对[l,r]使其符合条件。这是一段的,我们要计算多段的,我在代码中采用的是> > 固定右边界 然后把左边界累加起来> 这里很难,要着重理解一下比如11010有两段now都是1,map记录了每一段now为1的时候他前面有几个数字可选

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;

signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        int n=s.size();
        map<int,int>m;
        int now=0;
        m[0]=1;
        ll ans=0;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='1') now++;
            else now--;
            ans+=((n-i)*m[now])%mod;
            m[now]=(m[now]+i+2)%mod;
        }
        cout<<ans<<'\n';
    }

}

F.Bomb

-------------------------题解-----------------------------------

二分出一个值,使得数组中每个数减小到超过这个数的值,然后利用等差数列,知道a[i]-b[i](公差),首项a[i],末项(首相-公差)的次数来求得每个a[i]给最后的答案贡献了多少,最后输出

点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll a[N];
ll b[N];
 ll n,k;
 ll x1=0;
bool check(ll x)
{   ll cnt=0;
    for(ll i=1;i<=n;i++)
    {
        if(a[i]<x) continue;
        else cnt+=(a[i]-x)/b[i]+1;
    }
     if(cnt>=k) return 0;
    return 1;
}
ll su1(ll sx, ll d, ll n1) {
    ll mx=sx-d*(n1-1);
    return (sx + mx) * n1 / 2;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
       
        cin>>n>>k;
        x1=0;
        for(ll i=1;i<=n;i++) cin>>a[i];
        for(ll i=1;i<=n;i++) cin>>b[i];
        ll l=0,r=1e9;
        while(l<=r)
        {
            ll mid=(l+r)/2;
            if(check(mid)==1) r=mid-1;
            else x1=mid,l=mid+1;
        }
        x1++;
        ll ans=0;
        for(ll i=1;i<=n;i++)
        {   if(a[i]<x1) continue;

            ll time=(a[i]-x1)/b[i]+1;
            ans+=su1(a[i],b[i],time);
            k-=time;
        }
        ans+=k*(x1-1);
        cout<<ans<<'\n';
    }
}

标签:962,int,题解,ll,Codeforces,cin,while,Div,include
From: https://www.cnblogs.com/qau-marisa3/p/18339612

相关文章

  • 题解:Codeforces Round 964 (Div. 4) D
    D.Slavic'sExamtimelimitpertest:2secondsmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputSlavichasaverytoughexamandneedsyourhelpinordertopassit.Hereisthequestionheisstrugglingwith:Ther......
  • 题解:Codeforces Round 964 (Div. 4) C
    C.Showeringtimelimitpertest:2secondsmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputAsacomputersciencestudent,Alexfacesahardchallenge —showering.Hetriestoshowerdaily,butdespitehisbestefforts......
  • Codeforces Round 964 (Div. 4)
    比赛链接:CodeforcesRound964(Div.4)A思路    水题代码#include<iostream>usingnamespacestd;#definelllonglonginlineintread(void){intx=0,f=1;charch=getchar();while(ch<'0'||ch>'9'){......
  • 题解:Codeforces Round 964 (Div. 4) A
    A.A+BAgain?timelimitpertest:1secondmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputGivenatwo-digitpositiveinteger\(n\),findthesumofitsdigits.InputThefirstlinecontainsaninteger\(t\)(\(1......
  • Codeforces Round 964 (Div. 4) 补题记录(A~G2)
    难绷事实:Bwa一发A......#include<bits/stdc++.h>#definepbpush_back#defineintlonglongusingnamespacestd;constintN=500100;inta[N];signedmain(){intT;cin>>T;while(T--){intn;cin>>n;strings=......
  • Codeforces Round 964 (Div. 4)
    CodeforcesRound964(Div.4)A计算数位和。voidsolve(){ inta=0,n; cin>>n; while(n)a+=n%10,n/=10; cout<<a<<'\n';}B模拟,直接枚举4种出牌顺序,按题目给的规则判断即可。boolchk(intx1,inty1,intx2,inty2){ intc1=(x1&g......
  • Codeforces Round 963 (Div. 2)
    第一次上蓝名,指不准哪天掉下来就可以第二次蓝名了,好耶B.ParityandSum(CF1993B)首先特判原数组奇偶性相同的情况,奇偶不同时,由于替换过程只能产生奇数,故目标是将所有偶数变成奇数。假设当前选中奇数\(a_i\)和偶数\(a_j\),若\(a_i<a_j\),第一次操作时\(a_i:=a_j+a_i\),故最多......
  • CodeForces - 765F
    不妨套用P9058的套路,记点对\((i,j),a_i\gea_j\)被支配当且仅当存在\(i<k<j\),满足\(a_i\gea_k\gea_j\),同样,猜测对于\(i\),不被支配的点对\((k,i)\)只满足\(k<i\)最大且\(a_k>a_i\)。证明不妨使用反证法,记\(pre\),满足\(pre<j<i\)且\(a_{pre},a_j>a_i\),假设\((p......
  • Codeforces Round 963 (Div. 2)
    A.QuestionMarks题目大意有4n道题,每道题有4个选项,且正确答案中每个选项各占有n个。给定一个字符串s,s中ABCD分别代表4个选项,?代表放弃这道题,求可能的最大正确数解题思路统计每个选项的出现次数,假设每次选的都对,即ans+=min(x,n)点击查看代码#include<bits/stdc++.h>usi......
  • Codeforces Round 963 (Div. 2)
    CodeforcesRound963(Div.2)A对A,B,C,D的数量和\(n\)取个\(\min\)相加B只有奇数或只有偶数答案为\(0\),否则,只能把所有的偶数改为奇数,因为不可能把所有奇数改为偶数。然后就是改的大小问题了。考虑找到最大的奇数,然后把偶数从小到大依次修改。C显然对\(2k\)......