Codeforces Global Round 7 문제 해결(A-D2)

C o d e f o r c e s G l o b a l R o u n d 7 (A - D 2)\mathrm {Codeforces\Global\Round\7 (A-D2)} Codeforces Global Round 7 (A - D2) 문제 해결

아아!스몰 사이즈에 스몰 사이즈 sk i p skip skip, 나 취했어...

A   B a d   U g l y   N u m b e r s\mathrm{A\Bad\Ugly\Numbers} A Bad Ugly Numbers

1m i n 1min 1min을 잘랐습니다. 서열의 어떤 숫자도 정제할 수 없기 때문에 2333을 출력합니다.2333.. 2333..됐습니다.이 수는 분명히 222로 나누어질 수 없기 때문에 333...333... 333...333으로 나누어지고 2를 더하면 안 된다.그리고 특판 n=1 n=1 n=1 하면 됩니다

C o d e\mathcal{Code} Code

#include 
using namespace std;

inline int read()
{
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}

int T,n;

int main()
{
	T=read();
	for (;T--;)
	{
		n=read();
		if(n<=1) 
		{
			printf("-1
");
			goto rp;
		}
		putchar('2');
		for ( int j=2;j<=n;j++ ) putchar('3');
		printf("
");
		rp:;
	}
}

B   M a x i m u m s\mathrm{B\Maximums} B Maximums

한 줄기 물의 추이, a n = max ⁡ i = 1 n - 1 a i + b n an=\max_{i=1}^{n-1} a_i+b_n an​=maxi=1n−1​ai​+bn​

O(n) O(n) O(n) O(n) 밀면 된다

C o d e\mathcal{Code} Code

#include 
#define int long long
using namespace std;

inline int read()
{
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}

const int N=1e6+5;

int b[N];

signed main()
{
	int n,mx=0;
	n=read();
	for ( int i=1;i<=n;i++ ) b[i]=read();
	for ( int i=1;i<=n;i++ ) 
	{
		printf("%lld ",mx+b[i]); 
		mx=max(mx,b[i]+mx);
	}
	return 0;
}

C   P e r m u t a t i o n   P a r t i t i o n s\mathrm{C\Permutation\Partitions} C Permutation Partitions

첫 번째 질문은 배열이기 때문에 O(1)O(1)O(1)등차수열 공식만 있으면 된다.

두 번째 질문에 대해 우리는 방안수를 구한다. 서로 인접한 두 구간의 간격은 반드시 두 선택의 수 중간에 있기 때문에 위치차(첫 번째 질문의 수의 위치차)를 곱하면 된다.

C o d e\mathcal{Code} Code

#include 
#define int long long 
#define pb push_back
using namespace std;

inline int read()
{
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}

int n,m,ans,sum;

const int mo=998244353;

signed main()
{
	n=read();
	m=read();
	ans=1ll;
	int lp=0;
	for ( int i=1;i<=n;i++ )
	{
		int x=read();
		if(x>=n-m+1) 
		{
			sum+=x;
			if(lp)
				ans=ans*(i-lp)%mo;
			lp=i;
		}
	}
	printf("%lld %lld
",sum,ans);
	return 0;
}
			

D 1 , D 2   P r e f i x − S u f f i x P a l i n d r o m e ( E a s y + H a r d v e r s i o n )\mathrm{D1,D2\Prefix-Suffix Palindrome (Easy+Hard version)} D1,D2 Prefix−SuffixPalindrome(Easy+Hardversion)

또 한 문제인데 한참 동안 썼어요.

분명한 욕심이 있다. 먼저 양쪽 끝에서 중간으로 움츠리고 안 될 때까지 이것은 양쪽 끝이 연결되면 회문열로 병합할 수 있다.그러면 우리는 중간에 있는 문자열을 다시 캡처해서 접두사나 접두사에서 가장 긴 회문열을 찾으면 된다.이것은 m a n a c h a r\mathrm {manachar} manachar로 만들 수 있습니다.설마 m a n a c h a r\mathrm {manachar} manachar, 여기를 오른쪽으로 돌면서 배워요.

C o d e\mathcal{Code} Code

#include 
#define pb push_back
using namespace std;

inline int read()
{
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}

const int N=3e6+5;

int n,Q,m,ans,hw[N];
char s[N],t[N],c[N],b[N];

inline int get(char *s,int n)
{
	string cwy="##";
	for ( int i=1;i<=n;i++ ) cwy+=s[i],cwy+="#";
	int mx=0,mid=0,ans=1;
	for ( int i=1;i<cwy.length();i++ ) hw[i]=0;
	for ( int i=1;i<cwy.length();i++ ) 
	{
		if(i<mx) hw[i]=min(hw[mid*2-i],mx-i);
		else hw[i]=1;
		for (;cwy[i+hw[i]]==cwy[i-hw[i]]&&i+hw[i]<cwy.length();hw[i]++);
		if(i==hw[i]) ans=max(ans,hw[i]);
		if(i+hw[i]>mx) mx=i+hw[i],mid=i;
	}
	return ans-1;
}

inline void solve()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	int P=1;
	while(s[P]==s[n-P+1]&&P<=n) ++P;
	if(P==n+1) 
	{
		for ( int i=1;i<=n;i++ ) putchar(s[i]);
		printf("
");
		return;
	}
	m=0;
	for ( int i=P;i<=n-P+1;i++ ) c[++m]=s[i];
	int l=get(c,m);
	reverse(c+1,c+m+1);
	int r=get(c,m);
	reverse(c+1,c+m+1);
	if(l<r)  reverse(c+1,c+m+1),swap(l,r);
	for ( int i=1;i<P;i++ ) putchar(s[i]);
	for ( int i=1;i<=l;i++ ) putchar(c[i]);
	for ( int i=P-1;i;i-- ) putchar(s[i]);
	puts(""); 
}

int main()
{
	Q=read();
	for (;Q--;) solve();
	return 0;
}

E-G\mathrm {E-G} E-G의 구덩이를 먼저 파고 있다.