KTLT1. Dãy Wavio

Tiêu đề: KTLT1. Dãy Wavio Tue May 10, 2022 2:51 pm

1) DÃY SỐ WAVIO
Dãy số Wavio là dãy số nguyên thoả mãn các tính chất:
• Số lượng phần tử (độ dài của dãy) L là lẻ, tức là L = 2*N+1,
• N+1 phần tử đầu tiên là một dãy tăng ngặt,
• N+1 phần tử cuối là một dãy giảm ngặt.
Ví dụ, dãy số 1, 2, 3, 4, 5, 4, 3, 2, 0 là một dãy Wavio độ dài 9, còn dãy 1, 2, 3, 4, 5, 4, 3, 2, 2 không phải là dãy Wavio.
Yêu cầu: Cho dãy số nguyên độ dài N, hãy tìm dãy con Wavio độ dài lớn nhất từ dãy đã cho.
Ví dụ: cho dãy 1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1. Dãy con Wavio dài nhất là 1 2 3 4 5 4 3 2 1 và có độ dài 9.
Dữ liệu: Vào từ file văn bản WAVIO.INP gồm:
• Dòng thứ nhất chứa số nguyên N (0 < N ≤ 10 000),
• Dòng thứ 2 chứa N số nguyên, các số cách nhau một dấu cách.
Kết quả: Đưa ra file văn bản WAVIO.OUT độ dài của dãy con Wavio dài nhất. Ví dụ:
WAVIO.INP
10
1 2 3 4 5 4 3 2 1 10
WAVIO.OUT
9

Tổng số bài gửi : 34 Join date : 08/05/2022

Code:: #include<bits/stdc++.h>

#define nmax 10005

using namespace std;

int n;
int a[nmax], p[nmax], t[nmax], b[nmax], c[nmax];
int res;

void inp(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
}
bool check(){
int d1 = 0;
int d2 = 0;
for(int i = 1; i < n/2; i++)
while(a[i] < a[i+1]) d1++;
for(int i = n; i > n/2; i--){
while(a[i] < a[i-1]) d2++;
}
if(d1 == d2 && d1 == n/2) return true;
return false;
}

void xuli(){
int k = 0;
for(int i = 1; i <= n; i++){
if(b[i] == 1){
k++;
c[k] == a[i];
}
}
if(check()){
if(k > res) res = k;
}
}

void sinh(int i){
for(int j = 0; j <= 1; j++){
b[i] = j;
if(i == n) xuli();
else sinh(i+1);
}
}

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
freopen("WAVIO.INP" , "r" , stdin);
freopen("WAVIO.OUT" , "w" , stdout);
inp();
sinh(1);
cout << res;
return 0;
}

Tổng số bài gửi : 19 Join date : 09/05/2022

-Không biết trình bày ý tưởng thế nào, mong mọi người xem code có thể hiểu ạ :<

Code:: #include <iostream>
#include <bits/stdc++.h>
using namespace std;
int r,l,n,j,a[10000],d;
   int g[10000]={0};
void kq()
{
   d=2;
   for (int j=l+1;j<=r;j++)
   {
   if (a[j]>a[j-1]) {d++;}
   }
   l=l+d;
   for (int j=r-1;j>=l;j--)
   {
   if (a[j]>a[j+1]) {d++;} else {break;}
   }
}
int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   freopen("wavio.inp","r",stdin);
   freopen("wavio.out","w",stdout);
   cin >> n;
   for (int i=1;i<=n;i++)
   {
   cin >> a[i];
   if (a[i]>a[i-1]) {g[i]=g[i-1]+1;}
   else {g[i]=1;}
   }
   int res=0;
   for (int i=2;i<=n;i++)
   {
   if (a[i]<a[i-1]) {g[i]=g[i]+g[i-1];}
   if (g[i]!=1&&g[i]>res&&g[i]%2==1)
   {
   r=i;
   l=r-g[i];
   cout << r << " " << l << endl;
   kq();
   res=max(res,d);
   }
   }
   cout << res;
   return 0;
}

Tổng số bài gửi : 13 Join date : 10/05/2022

Code:: #include <iostream>

using namespace std;
int a[100007],n,b[1000007],c[100007],res;
void in()
{
for(int i=1;i<=n;i++)
{
cout << a[i];
}
cout << endl;
}
void xuly()
{
int k=0;
for(int i=1;i<=n;i++)
{
if(a[i]==1)
{
k++;
b[k]=c[i];
}
}
if(k%2==1)
{
for(int i=2;i<=k/2+1;i++)
{
if(b[i]<=b[i-1]) return;
}
for(int i=k/2+2;i<=k;i++)
{
if(b[i]>=b[i-1]) return;
}
res=max(k,res);
}
}
void snt(int i)
{
for(int j=0;j<=1;j++)
{
a[i]=j;
if(i==n) xuly();
else snt(i+1);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
freopen("WAVIO.INP","r",stdin);
freopen("WAVIO.OUT","w",stdout);
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> c[i];
}
snt(1);
cout << res;
//cout << "Hello world!" << endl;
return 0;
}

Tổng số bài gửi : 14 Join date : 10/05/2022

Code:: #include <bits/stdc++.h>

#define io freopen("wavio.inp","r",stdin); freopen("wavio.out","w",stdout);
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define FOR(i,l,r) for (int i=l;i<=r;i++)
#define pb push_back
#define fr first
#define sc second
#define ll long long

using namespace std;

int r,l,n,j,a[10000],d;
   int g[10000]={0};
void kq()
{
   d=2;
   FOR(i,l+1,r)
   {
   if (a[j]>a[j-1]) {d++;}
   }
   l=l+d;
   for (int j=r-1;j>=l;j--)
   {
   if (a[j]>a[j+1]) {d++;} else {break;}
   }
}
int main()
{
   faster;
   io;
   cin >> n;
   for (int i=1;i<=n;i++)
   {
   cin >> a[i];
   if (a[i]>a[i-1]) {g[i]=g[i-1]+1;}
   else {g[i]=1;}
   }
   int res=0;
   FOR(i,2,n)
   {
   if (a[i]<a[i-1]) {g[i]=g[i]+g[i-1];}
   if (g[i]!=1&&g[i]>res&&g[i]%2==1)
   {
   r=i;
   l=r-g[i];
   cout << r << " " << l << endl;
   kq();
   res=max(res,d);
   }
   }
   cout << res;
   return 0;
}

» T1.2 Dãy số Wavio