正睿七连测 DAY5 T2

题是水题，也不难想，本来是想打暴力先过个小数据，

本来就想再搞搞优化试试能不能过，毕竟这个题理论上 O( $n^2$ ) 是能过的

题干

主要是觉得这个优化很有可取之处，本来超时，一加这个优化就好很多了，一下就过了

改前的代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define NUM 10010
using namespace std;
int n;
int a[NUM],dui[NUM];
struct dian{
int l,r;
char da;
};
dian ans[NUM];
int main(){
cin >> n;
for( int i = 1;i <= n;i++ ){
int t;
cin >> t;
a[i] = t + '0';
dui[t] = i;
}
ans[1].da = '1';ans[n].da = '1';
if( abs( dui[1] - dui[2] ) == 1 ){
ans[2].da = '1';
ans[2].l = min( dui[1],dui[2] );
ans[2].r = max( dui[1],dui[2] );
}
else ans[2].da = '0';
for( int i = 3;i < n;i++ ){
if( ans[i-1].da == '1' ){
if( a[ans[i-1].l-1] == i+'0' ){
ans[i].da = '1';
ans[i].l = ans[i-1].l - 1;
ans[i].r = ans[i-1].r;
continue;
}
if( a[ans[i-1].r+1] == i+'0' ){
ans[i].da = '1';
ans[i].l = ans[i-1].l;
ans[i].r = ans[i-1].r + 1;
continue;
}
ans[i].da = '0';
continue;
}
int ok = 1;
for( int j = 1;j <= n-i+1;j++ ){
int k;ok = 1;
for( k = 0;k <= i-1;k++ ){
if( a[k+j] > i+'0' ){
ok = 0;
break;
}
}
if( ok ){
ans[i].da = '1';
ans[i].l = j;
ans[i].r = j+i-1;
ok = 2;
break;
}
}
if( ok == 2 ) continue;
else ans[i].da = '0';
}
for( int i = 1;i <= n;i++ ){
cout << ans[i].da;
}
return 0;
} 

View Code

改后的代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define NUM 10010
using namespace std;
int n;
int a[NUM],dui[NUM];
struct dian{
int l,r;
char da;
};
dian ans[NUM];
int main(){
cin >> n;
for( int i = 1;i <= n;i++ ){
int t;
cin >> t;
a[i] = t + '0';
dui[t] = i;
}
ans[1].da = '1';ans[n].da = '1';
if( abs( dui[1] - dui[2] ) == 1 ){
ans[2].da = '1';
ans[2].l = min( dui[1],dui[2] );
ans[2].r = max( dui[1],dui[2] );
}
else ans[2].da = '0';
for( int i = 3;i < n;i++ ){
if( ans[i-1].da == '1' ){
if( a[ans[i-1].l-1] == i+'0' ){
ans[i].da = '1';
ans[i].l = ans[i-1].l - 1;
ans[i].r = ans[i-1].r;
continue;
}
if( a[ans[i-1].r+1] == i+'0' ){
ans[i].da = '1';
ans[i].l = ans[i-1].l;
ans[i].r = ans[i-1].r + 1;
continue;
}
ans[i].da = '0';
continue;
}
int ok = 1;
for( int j = 1;j <= n-i+1; ){
int k;ok = 1;
for( k = 0;k <= i-1;k++ ){
if( a[k+j] > i+'0' ){
ok = 0;
break;
}
}
if( ok ){
ans[i].da = '1';
ans[i].l = j;
ans[i].r = j+i-1;
ok = 2;
                break;
}
if( k > 0 ) j = k+j;
else j++;
}
if( ok == 2 ) continue;
else ans[i].da = '0';
}
for( int i = 1;i <= n;i++ ){
cout << ans[i].da;
}
return 0;
} 

以后还可以用这个优化，大大滴好使  (*^▽^*)

推荐这些文章：

1006 换个格式输出整数

#include<stdio.h>
int main(){
int n;
char a[100]={0};
scanf("%d",&n);
int b=n/100;
for(int i=0;i<b;i++){
a[i]='B';
}
int s=n/10%10;
for(int i=b;i<s+b;i++){
a[i]='S';
}
int x=n%100%10;
int j=1;
for(int i=b+s;i<s+b+x;...

AcWing 12. 背包问题求具体方案

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int N = 1010;

int f[N][N];
int v[N],w[N];
int main() {
int n,m;
cin >> n >> m;
for(int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];
for(int i = n; i >...

leecode-69. x 的平方根

69. x 的平方根
public int mySqrt(int x) {

if(x == 0) return 0;

if(x <= 3) return 1;

long ans = 1;
long L = 1,R = x;

long M = 0;

while(L <= R){

M = (L + R) / 2;

if(M * M <= x){
ans = M;
...

最短hamilton路径

#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N=20,M=1<<N;int n;int w[N][N];int f[M][N];int main(){ cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>w[i][j]; memset(f,0x3f,sizeof f); f[1][0]=0; for(int i=0;i...

170402 标题统计

 
参考程序：

#include <bits/stdc++.h>
using namespace std;
int main()
{
char a='a';
int ans=0;
while(a!='\n')
{
a=getchar();
if(a==' ')
{
continue;
}
else
{
ans++; ...

P1926 小书童——刷题大军 题解

P1926 小书童——刷题大军

#include<iostream>
#include<algorithm>
using namespace std;
int dp[200];
int a[20],b[20],c[20];
int n,m,k,r;
int main()
{
cin>>n>>m>>k>>r;
for (int i=1;i<=n;i++)
{
cin>>c[i];
}
for (int i=1;i<=m;i++)
{
cin>>a[i];
}
f...

leetcode 714. 买卖股票的最佳时机含手续费

class Solution {
public int maxProfit(int[] prices, int fee) {
int n=prices.length;
int low=prices[0];
int ans=0;
for(int i=1;i<n;i++){
if(prices[i]<=low) low=prices[i];
else if(prices[i]<=low+fee) continue;
else{
...

vector<vector<int>>初始化

class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

int n=mat.size();
int m=mat[0].size();
vector<vector<int>> ans(n, vector<int>...

130122 3的倍数II

 
 
 
 参考程序：
#include<bits/stdc++.h>using namespace std;int main(){ 　　int t,ans; 　　string s; 　　cin>>t; 　　for(int i=1;i<=t;i++) 　　{ 　　　　cin>>s; 　　　　ans=0; 　　　　for(int j=0;j<s.size();j++) 　　　　{ 　　　　　　an...

130942 输油管道问题

 
参考程序：

#include<iostream>
#include<cmath>
using namespace std;
int n,x,y[1000005];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x>>y[i];
}
int ans=2e9;
for(int i=1;i<=n;i++)
{
int sum=0;
for(int j=1...