TheForces Round #16 (2^4-Forces) Editorial

Правка en25, от wuhudsm, 2023-06-12 12:49:00

A

code
Solution

B

code
solution

C

code
solution

D

include<bits/stdc++.h>

define ll long long int

using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while(t--) { int n, x; cin >> n >> x; int fst = -1; int val = 0; for(int i = 29; i >= 0; i--) { int a = (x >> i)&1; if(!a) { fst = i; break; } val ^= (1 << i); } if(fst + 2 >= n) { cout << x; for(int i = 2; i <= n; i++) { val ^= (1 << (fst — i + 2)); cout << " " << val; } cout << "\n"; } else cout << "-1\n"; } }

Note $$$maxdif(x,y)=max(k)(bit(x,k)!=bit(y,k))$$$.

It can be proved that $$$maxdif(a[i],a[i+1])$$$ is strictly decreasing.

Why?

Consider $$$b_i$$$,$$$k=max(j)(bit(b_i,j)=1)$$$.What about $$$b_{i+1}$$$?First,$$$bit_{j>k}(b_{i+1},j)=0$$$(otherwise,it contradicts the strict decrease of $$$b$$$).Then $$$bit(b_{i+1},k)$$$ must be $$$0$$$.Otherwise,we get $$$bit(a_i,k)!=bit(a_{i+1},k)$$$ and $$$bit(a_{i+1},k)!=bit(a_{i+2},k)$$$,which contradicts the strict increase of $$$a$$$.

Based on the above conclusion, we can make the optimal construction.

Note $$$x=(1...10???)_2$$$,construct $$$a=[(1...10???)_2,(1...110...0)_2,(1...111...0)_2,...,(1...111...1)_2]$$$.

E

code

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=2010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
ll  T,n,m,c;
ll  a[N][N];
ll  dp[N][N];

void init()
{
	scanf("%I64d%I64d%I64d",&n,&m,&c);
	for(int i=1;i<=n;i++)
    	for(int j=1;j<=m;j++)
    		scanf("%I64d",&a[i][j]);
}

void DP()
{
	for(int i=1;i<=n;i++)
	{
		ll maxl[N]={0},maxr[N]={0},left[N]={0},right[N]={0};
		for(int j=1;j<=m;j++) maxl[j]=max(0LL,a[i][j]-2*c+maxl[j-1]);
		for(int j=m;j>=1;j--) maxr[j]=max(0LL,a[i][j]-2*c+maxr[j+1]);
		for(int j=1;j<=m;j++) left[j]=max(max(0LL,dp[i-1][j]-c)+a[i][j]+maxl[j-1],left[j-1]+a[i][j]-c);
		for(int j=m;j>=1;j--) right[j]=max(max(0LL,dp[i-1][j]-c)+a[i][j]+maxr[j+1],right[j+1]+a[i][j]-c);
		for(int j=1;j<=m;j++) dp[i][j]=max(left[j]+maxr[j+1],right[j]+maxl[j-1]);
	}
	ll ans=-INF;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			ans=max(ans,dp[i][j]);
	printf("%I64d\n",ans);
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
    	init();
    	DP();
	}
	
	return 0;
}

solution

Consider DP.

Note $$$dp_{i,j}$$$ as the maximum score we can get at the end of $$$(i,j)$$$.

Note $$$lmax_{i,j}=max(0,max_(1 \leq k \leq j)((a_{i,k}-2c)+...+(a_{i,j}-2c)))$$$ and $$$rmax$$$ similarly.

Now consider which cell we go from to $$$(i,j)$$$.There are four situations.

$$$1.$$$ We just start at $$$(i,j)$$$.The answer is $$$a_{i,j}+lmax_{i,j-1}+rmax_{i,j+1}$$$;

$$$2.(i-1,j) \rightarrow (i,j)$$$.The answer is $$$dp_{i-1,j}-c+a_{i,j}+lmax_{i,j-1}+rmax_{i,j+1}$$$;

$$$3.(i,j-1) \rightarrow (i,j)$$$.The answer is $$$left_{i-1,j}-c+a_{i,j}+rmax_{i,j+1}$$$;

$$$4.(i,j+1) \rightarrow (i,j)$$$.The answer is $$$right_{i+1,j}-c+a_{i,j}+lmax_{i,j-1}$$$.

$$$left_{i,j}=max(max(0,dp_{i-1,j}-c)+a_{i,j}+lmax_{i,j-1},left_{i,j-1}-c+a_{i,j})$$$,and $$$right_{i,j}$$$ similarly.

$$$dp_{i,j}$$$ is the maximum value of the answers for the four situations mentioned above.And the final answer is $$$max(dp_{i,j})$$$.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en28 Английский wuhudsm 2023-06-12 12:50:20 2 Tiny change: ' summary="Solution">\' -> ' summary="solution">\'
en27 Английский wuhudsm 2023-06-12 12:50:02 0 (published)
en26 Английский wuhudsm 2023-06-12 12:49:49 36
en25 Английский wuhudsm 2023-06-12 12:49:00 124
en24 Английский wuhudsm 2023-06-12 12:47:03 176 (saved to drafts)
en23 Английский wuhudsm 2023-06-12 12:45:30 3132 (published)
en22 Английский wuhudsm 2023-06-12 12:39:25 6811
en21 Английский wuhudsm 2023-06-12 12:35:46 2800
en20 Английский wuhudsm 2023-06-12 12:32:57 11
en19 Английский wuhudsm 2023-06-12 12:31:48 313 (saved to drafts)
en18 Английский wuhudsm 2023-06-12 12:10:19 2 Tiny change: 'r $y_i=0$,then can we' -> 'r $y_i=0$,when can we'
en17 Английский wuhudsm 2023-06-12 12:07:37 0 (published)
en16 Английский wuhudsm 2023-06-12 12:07:05 131
en15 Английский wuhudsm 2023-06-12 12:05:19 112 Tiny change: 'ons.\n\n$1$. We just s' -> 'ons.\n\n$1.$ We just s'
en14 Английский wuhudsm 2023-06-12 12:01:25 52
en13 Английский wuhudsm 2023-06-12 11:59:55 586
en12 Английский wuhudsm 2023-06-12 11:46:44 9
en11 Английский wuhudsm 2023-06-12 11:45:41 250
en10 Английский wuhudsm 2023-06-12 11:40:37 181
en9 Английский wuhudsm 2023-06-12 11:37:38 13
en8 Английский wuhudsm 2023-06-12 11:36:08 785
en7 Английский wuhudsm 2023-06-12 11:20:08 243
en6 Английский wuhudsm 2023-06-11 19:49:05 56
en5 Английский wuhudsm 2023-06-11 19:48:24 28
en4 Английский wuhudsm 2023-06-11 19:47:49 100
en3 Английский wuhudsm 2023-06-11 19:46:05 45
en2 Английский wuhudsm 2023-06-11 19:44:08 121
en1 Английский wuhudsm 2023-06-11 19:40:02 646 Initial revision (saved to drafts)