Codeforces 376 Div2

Title link and Code link

I VP’d this game in the evening, checked the album and wrote about it, TLE47. Question F: Regarding the data, you should pay attention to the data range, and then enumerate according to each number.

A Night at the Museum

$26$ letters are placed on a disk, and then the letters can be found clockwise and counterclockwise, and what is the minimum number of total rotations.

Get the minimum value greedily every time. res+=min(abs(k-cur),26-abs(k-cur))

B Coupons and Discounts

There are $n$ days, corresponding to the corresponding number of pizzas to be purchased on each day. There are two purchasing methods, the first is to buy two in one day, and the second is to buy one in two consecutive days. Ask whether the arrangement is feasible under these two purchasing methods.

Be greedy from the first day, don’t worry about the even number. If it is an odd number, then you must decrease it by 1 the next day if you want it to work. Determine whether the number of each day is greater than or equal to 0, and the last day must be an even number.

C Socks

There are n socks, k colors, and m days. There are corresponding arrangements for each day, which two socks to wear. Ask what is the minimum number of colors to change if you want the socks to be consistent every day.

And check the collection and put the socks you want to wear in a collection. Then select the one with the most colors in each collection, and the other socks will be changed to this color. . .

D 80-th Level Archeology

The meaning of the question is that $n$ sequences are given, and then all sequences can be shifted back by one bit. The last $C$ becomes $1$. Ask how many bits can be shifted at least so that the sequence is in lexicographically increasing order.

Comparing the two sequences, you will find that it is a legal interval. Combine all legal intervals to see if there are numbers that satisfy all intervals.

E Funny Game

The meaning of the question is that there are $n$ numbers. Petya and Gena follow the following rules to get the $n$ numbers: each time at least select the $2$ number in front of the leftmost number in the sequence, and the sum is included in the score, and then put the sum into the leftmost number of the sequence again until there is only one number left in the sequence. Everyone wants their own score - the opponent’s score is the largest, Petya takes it first and asks for the optimal solution.

Later I learned that this kind of game has a routine. . .

$DP[i]$ means that for the current player, take the first $[1..i]$ to get the optimal value. Then where does this optimal value $DP[i]$ transfer from? If taken from left to right, this optimal value depends on the optimal value taken by the opponent, that is, it is transferred from the right. Based on this, you can write a memorized $DP$ of $O(n^2)$.

int n;
int val[maxn],sum[maxn],dp[maxn];
int cal(int x)
{
	if(dp[x]!=-1)
	{
		return dp[x];
	}
	int res = -INF;
	for(int i=x+1;i<=n;i++)
	{
		res=max(res,cal(i));
	}
	if(res == -INF)
		res = 0;
	dp[x]=sum[x]-res;
	return dp[x];
}
void solve()
{
	memset(dp,-1,sizeof(dp));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&val[i]);
		sum[i]=sum[i-1]+val[i];
	}

	int res = -INF;
	for(int i=2;i<=n;i++)
	{
		res = max(res,cal(i));
	}
	printf("%d\n",res);
}

Observe the transfer. If you transfer from the back, you can go from the back to the front to maintain the maximum value and get the result.

ll n;
ll val[maxn], sum[maxn];

void solve()
{
	scanf("%lld", &n);
	repp(i, 1, n)
	{
		scanf("%lld", &val[i]);
		sum[i] = sum[i - 1] + val[i];
	}
	ll res = 0;
	for (int i = n; i >= 2; i--)
	{
		if (i == n)res = sum[i];
		else if (res < sum[i] - res)
		{
			res = sum[i] - res;
		}
	}
	printf("%lld\n", res);
}

F Video Cards

There are $n$ numbers. You can start with any number. The remaining numbers must be reduced to an integer multiple of this number. Record the sum of this sequence. Ask for the maximum value of the sum in all cases.

Note that the range of numbers is less than 200,000, then you can find the prefix sum and enumerate each number as the base, which is 2 times, 3 times… the number. Complexity$O(nlogn)$