AtCoder Regular Contest 075

This set of questions is relatively simple overall, with the first three questions worth 300, 400, and 600 points. Mainly I want to record question D.

Title link

C - Bugged

Given a set of numbers ($N<100$), select part or all of them, and ask what is the maximum value when it and $sum%10$ are not $0$.

Calculate the sum first to see if the conditions are met, and output it directly if the conditions are met. If the conditions are not met, the numbers removed will be enumerated.

int n;
int val[maxn];
void solve()
{
	sa(n);
	int ans=0;
	repp(i,1,n)
	{
		sa(val[i]);
		ans+=val[i];
	}
	int maxx=0;
	if(ans%10)
	{
		printf("%d\n", ans);
		return;
	}
	repp(i,1,n)
	{
		int sum=ans-val[i];
		if(sum%10)maxx=max(maxx,sum);
	}
	printf("%d\n", maxx);
}

D - Widespread

There are a group of monsters ($N<10^5$), each monster has its own blood volume $h_i$. You now have an attack method: select one of the monsters to cause $A$ points of damage, and the remaining monsters will cause $B$ points of damage ($B<A$). Ask how many times you need to attack at least to make the health of these monsters become $0$ or negative.

Number of two-point attacks. Because $A>B$, the blood volume of $B*x$ is subtracted from each monster each time. The remaining damage is equivalent to $A-B$ damage caused by each attack. See if it can be completed in $x$ attacks.

ll n,a,b;
ll h[maxn];
ll val[maxn];
vector<int>v;
 
bool check(ll x)
{
	v.clear();
	repp(i,1,n)
	{
		val[i]=h[i]-x*b;
		if(val[i]>0)
			v.push_back(val[i]);
	}
	if(v.size()==0)return true;
	//sort(v.begin(),v.end());
 
	ll cnt=0;
	for(int i=0;i<v.size();i++)
	{
		cnt+= (v[i]+a-b-1)/(a-b);
	}
	return cnt<=x;
}
 
void solve()
{
	scanf("%lld%lld%lld",&n,&a,&b);
	repp(i,1,n)
	{
		scanf("%lld",&h[i]);
	}
	ll le=0,ri=1e9+5;
	while(le<ri)
	{
		ll mid=(le+ri)/2;
		if(check(mid))
		{
			ri=mid;
		}
		else
		{
			le=mid+1;
		}
	}
	printf("%lld\n",le);
}

E - Meaningful Mean

Given a set of numbers ($N<2*10^5$), there are a total of $\frac{N*(N+1)}{2}$ consecutive subsequences. Ask how many of these subsequences have an average value greater than the given $K$.

Subtract $K$ from each element in the array, and you will find that what is left is the classic reverse order problem.

ll num[maxn];
int lowbit(int x)
{
	return x&(-x);
}
ll getsum(ll x)
{
	ll ans = 0;
	while (x>0)
	{
		ans += num[x];
		x -= lowbit(x);
	}
	return ans;
}
ll add(int x, int v)
{
	int up = maxn - 1;
	while (x <= up)
	{
		num[x] += v;
		x += lowbit(x);
	}
	return x;
}
 
ll n, k;
ll val[maxn], sum[maxn];
ll stmp[maxn], s[maxn];
 
void solve()
{
	scanf("%lld%lld", &n, &k);
	repp(i, 1, n)
	{
		scanf("%lld", &val[i]);
		val[i] -= k;
		sum[i] = sum[i - 1] + val[i];
		stmp[i] = sum[i];
	}
	sort(stmp + 1, stmp + n + 1);
	repp(i, 1, n)
	{
		s[i] = lower_bound(stmp + 1, stmp + n + 1, sum[i]) - stmp;
	}
	ll ans = 0;
	repp(i, 1, n)
	{
		if (sum[i] >= 0)ans++;
		ans +=  (getsum(s[i]));
		add(s[i], 1);
	}
	printf("%lld\n", ans);
}

F - Mirrored

The meaning of the question is $N$, and its reverse order $rev(N)$, and then it is given $D$. Ask how many $N$ satisfy $rev(N)=N+D$.

I had a long discussion with Firefly. . . Considering each value bit by bit, it seems difficult to express it in detail. I feel like this is a very pure idea question. . .

ll num[22];
 
ll dfs(int le, int ri, ll d)
{
	if (le >= ri)
	{
		if (d == 0)
		{
			if (le == ri)
			{
				return 10;
			}
			else
			{
				return 1;
			}
		}
		else
		{
			return 0;
		}
	}
	int t = (10 - d % 10) % 10;
	ll sur = d - t*num[ri - le] + t;
	return ((le ? 10 : 9) - t)*(dfs(le + 1, ri - 1, llabs(sur) / 10));
}
 
int main()
{
	num[0] = 1;
	for (int i = 1; i <= 20; i++)
	{
		num[i] = num[i - 1] * 10;
	}
	ll d;
	scanf("%lld", &d);
	ll ans = 0;
	for (int i = 0; i < 19; i++)
	{
		ans += dfs(0, i, d);
	}
	printf("%lld", ans);
	//system("pause");
	return 0;
}