[Question and answer] ABC365 (A~E)

First four questions 30min cut, then T5 deadlocked for 70min + a couple of small don errors, 16s to the end of the match to hand in the last round and AC'd.

A. Leap Year

Title Description

I'll give you a year.\(Y\)which outputs the number of days in the year (to determine leap years).\(1583\le Y\le2023\)。

reasoning

Just simulate it directly. Cannot be divided\(4\) or divide exactly\(4\) and divide exactly without remainder (in integer arithmetic)\(100\) outputs\(365\)The rest of the output\(366\)The Complexity\(O(1)\)。

coding

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register
#define inf 0x3f3f3f3f
int a;
int main()
{
	scanf("%d",&a);
	if(a%4!=0||(a%100==0&&a%400!=0)) 
	{
		puts("365");
	}
	else
	{
		puts("366");
	}
	return 0;
}

B. Second Best

Title Description

Give you a long as\(N\) sequences\(A\), outputs the next largest value of this sequence.\(2\le N\le100\)，\(1\le A_i\le10^9\)。

reasoning

The data range is small, and it is clear that the complexity\(O(n\log n)\) Solvable. Use either sort or priority queue. The race was played with a priority queue for convenience.

coding

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
int a,b;
priority_queue<pair<int,int>>que;
int main()
{
	scanf("%d",&a);
	for(ri i=1;i<=a;i++)
	{
		scanf("%d",&b);
		({b,i});
	}	
	();
	printf("%d",().second);
	return 0;
}

C. Transportation Expenses

Title Description

there are\(N\) Individuals, each with a transportation expense\(A_i\)You have to.ostentatiousGive them a transportation subsidy\(x\)The money given to each person for\(min(x,A_i)\)But your budget is\(M\) dollars, i.e.\(\sum\limits_{i=1}^{N}min(x,A_i)\le M\)to find the largest\(x\). Such as\(x\) Can be infinitely large, outputinfinite。\(1\le N\le2\times10^5\)，\(1\le M\le2\times10^{14}\)，\(1\le Ai\le10^9\)。

reasoning

There is an obvious conclusion to begin with:\(x=max_{i=1}^{N}A_i\) We spend the most at this value. This is because at this value everyone takes\(A_i\)After\(x\) Getting bigger can't affect what we spend anymore. So if\(\sum\limits_{i=1}^{N}A_i\ge M\)We'll just outputinfiniteOkay.
And then think about for other cases, obviously, with the\(x\) increases, our spending is monotonically undiminished, and a dichotomous answer comes to mind. For a deterministic\(x\), which is directly and violently evaluated, and then compared to\(M\) Comparison is sufficient. Complexity\(O(n\log n)\). Attention.\(M\) It's big, to drive LONG LONG.

coding

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register long long
#define inf 0x3f3f3f3f
long long a,b,c[200002],sm,mx;
il bool check(long long x)
{
	ri rn=0;
	for(ri i=1;i<=a;i++)
	{
		rn+=min(c[i],x);
		if(rn>b)
		{
			return false;
		}
	}
	return true;
}
int main()
{
	scanf("%lld%lld",&a,&b);
	for(ri i=1;i<=a;i++)
	{
		scanf("%lld",&c[i]);
		sm+=c[i];
		mx=max(mx,c[i]);
	}
	if(sm<=b)
	{
		puts("infinite");
		exit(0);
	}
	ri l,m=0,n=mx;
	while(n-m>1)
	{
		l=(m+n)>>1;
		if(check(l))
		{
			m=l;
		}
		else
		{
			n=l;
		}
	}
	if(check(n))
	{
		printf("%lld",n);
	}
	else
	{
		printf("%lld",m);
	}
	return 0;
}

D. AtCoder Janken 3

Title Description

Two people play rock-paper-scissors with the stipulation that A must not lose to B and that A's neighboring operations must not be identical. Now you are given the sequence of operations of B\(S\)The length is\(N\)seek\(A\) Maximum number of innings won. For\(S_i\)R is for rock, P is for cloth, and S is for scissors.\(N\le2\times10^5\)

reasoning

A glance at the dp question. Set\(dp[i][0]\) refers the Communiqué of the International Conference on Financing for Development (ICFD)\(i\) Maximum number of wins out of the rock.\(dp[i][1]\) refers the Communiqué of the International Conference on Financing for Development (ICFD)\(i\) Maximum number of wins out of the cloth.\(dp[i][0]\) refers the Communiqué of the International Conference on Financing for Development (ICFD)\(i\) Maximum number of wins for scissors. If the opponent is rock in that game, we must not play scissors, so we do not update it.\(dp[i][2]\)(initial value is 0); if we play rock, we inherit the state of scissors and cloth from the previous game, but the game is not won, so we transfer directly; if we play cloth, we inherit the state of scissors and rock from the previous game, and the game is won, so we also need to +1. The same applies when the opponent plays scissors and cloth. Finally in the first\(N\) It is sufficient to remove the maximum value from the three answers of the next time. Complexity\(O(n)\)。

coding

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register long long
#define inf 0x3f3f3f3f
int a,b[200002],dp[200002][5],ans;
char ch;
int main()
{
	scanf("%d",&a);
	for(ri i=1;i<=a;i++)
	{
		ch=getchar();
		if(ch=='R')
		{
			b[i]=1;
			continue;
		}
		if(ch=='P')
		{
			b[i]=2;
			continue;
		}
		if(ch=='S')
		{
			b[i]=3;
			continue;
		}
		i--;
	}
	for(ri i=1;i<=a;i++)
	{
		if(b[i]==1)
		{
			dp[i][1]=max(dp[i-1][2],dp[i-1][3]);
			dp[i][2]=max(dp[i-1][1],dp[i-1][3])+1;
			continue;
		}
		if(b[i]==2)
		{
			dp[i][2]=max(dp[i-1][1],dp[i-1][3]);
			dp[i][3]=max(dp[i-1][1],dp[i-1][2])+1;
			continue;
		}
		if(b[i]==3)
		{
			dp[i][3]=max(dp[i-1][1],dp[i-1][2]);
			dp[i][1]=max(dp[i-1][2],dp[i-1][3])+1;
			continue;
		}
	}
	ans=max(dp[a][1],max(dp[a][2],dp[a][3]));
	printf("%d",ans);
	return 0;
}

E. Xor Sigma Problem

Title Description

Give you a long as\(N\) sequences\(A\)seek\(\sum\limits_{i=1}^{N-1}\sum\limits_{j=i+1}^{N}A_i\oplus A_{i+1}\oplus\cdots\oplus A_j\)。\(1\le N\le2\times10^5\)，\(1\le A_i\le10^8\)

reasoning

in the first place\(O(N^2)\) Process the prefix sum and then\(O(1)\) Solving is something I'm sure we all know how to do, but it's definitely TLE. to AC, you have to squash off at least one bit, that is, for every number realized\(O(1)\) Ask for contributions.Developing human wisdomConsidering the essence of the different-or operation, let's try to split an integer into a binary string, and for each new addition, find the number of occurrences of 0/1 in each preceding bit. Note that the number we find here is for each suffix, since only consecutive intervals can produce a contribution. But if you store them separately, the time goes back to the\(O(N^2)\). Thus, the setup\(num[i][j][k]\) In order to find the first\(i\) digit number one (i.e. number two)\(j\) emerging needs\(k\) The number of\(dp[i]\) refers the Communiqué of the International Conference on Financing for Development (ICFD)\(i\) for the cumulative contribution generated.\(pre[i]\) for the different or prefix sum, transfer with attention to the details of handling, pay attention to open large arrays and long long. complexity.\(O(30N)\)。

coding

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register long long
#define inf 0x3f3f3f3f
long long a,b[200002],pre[200002],num[200002][33][2],dp[33],ans;
int main()
{
	scanf("%lld",&a);
	for(ri i=0;i<=30;i++)
	{
		num[0][i][0]=1;
	}
	scanf("%lld",&b[1]);
	pre[1]=b[1];
	for(ri j=0;j<=30;j++)
	{
		ri k=(pre[1]>>j)&1;
		num[1][j][k]=num[0][j][k]+1;
		num[1][j][k^1]=num[0][j][k^1];
	}
	for(ri i=2;i<=a;i++)
	{
		scanf("%lld",&b[i]);
		pre[i]=pre[i-1]^b[i];
		for(ri j=0;j<=30;j++)
		{
			ri k=(pre[i]>>j)&1;
			dp[j]+=num[i-2][j][k^1];
			num[i][j][k]=num[i-1][j][k]+1;
			num[i][j][k^1]=num[i-1][j][k^1];
		}
	for(ri i=0;i<=30;i++)
	{
		ans+=dp[i]*(1<<i);
	}
	printf("%lld",ans);
	return 0;
}