Category: Data Structure

不能再快了的read

credit : http://zonelikewonderland.tk/#/user/blog/details/481e27461fe6602e138b154ca8379587

const int buffsize=1e5;
char buf[buffsize],*pp=buf-1;
int readsize=0,freadsize=0;
inline void readinit(){
    fread(buf+(((readsize+buffsize-1)%buffsize>=buffsize/2-1)?0:buffsize/2),1,buffsize/2,stdin);
    freadsize+=buffsize/2;
}
inline int read(){
    if(readsize+buffsize/2>freadsize)readinit();
    while((++readsize,*++pp)<'-')if(pp==buf+buffsize-1)pp=buf-1;
    register int x=*pp&15;
    if(pp==buf+buffsize-1)pp=buf-1;
    while((++readsize,*++pp)>'-'){
        x=x*10+(*pp&15);
        if(pp==buf+buffsize-1)pp=buf-1;
    }
    if(pp==buf+buffsize-1)pp=buf-1;
    return x;
}

比我那个快。

这道DP有点精妙~，大概最优子结构的转移函数写法长这样：

$$f_{max,i,j,0}=max(f_{max,i,j-1,0},f_{max,i,j-1,1}+1)$$

$$f_{max,i,j,1}=max(f_{max,i-1,j,0}+1,f_{max,i-1,j,1})$$

$$f_{min,i,j,0}=max(f_{min,i,j-1,0},f_{min,i,j-1,1}+1)$$

$$f_{min,i,j,1}=max(f_{min,i-1,j,0}+1,f_{min,i-1,j,1})$$

为了防止在起始点拐弯，最好的办法是-1越界。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define re register int 
#define LL long long 
using namespace std;
int n,m;
int f[1010][1010][2],g[1010][1010][2];
char a[1010][1010];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	cin>>a[i][j];
	memset(f,63,sizeof(f));
	if(a[1][1]=='#'){cout<<-1;return 0;}
	g[1][1][0]=g[1][1][1]=0;
	f[1][1][0]=f[1][1][1]=0;//0 left 1 down
	for(int i=1;i<=m;i++)g[0][i][1]=g[0][i][0]=-2147483647;
	for(int i=1;i<=n;i++)g[i][0][1]=g[i][0][0]=-2147483647;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	if(a[i][j]=='o')
	{
		if(i==1&&j==1)continue;
		g[i][j][1]=max(g[i-1][j][1],g[i][j-1][0]+1);
		f[i][j][1]=min(f[i-1][j][1],f[i][j-1][0]+1);
		g[i][j][0]=max(g[i-1][j][1]+1,g[i][j-1][0]);
		f[i][j][0]=min(f[i-1][j][1]+1,f[i][j-1][0]);
	}
	int Ansa=max(g[n][m][1],g[n][m][0]);
	int Ansb=min(f[n][m][1],f[n][m][0]);
	if(Ansb>n+m-2)cout<<-1<<endl;
	else cout<<Ansa-1<<" "<<Ansb<<endl;
	return 0;
}

getchar+fread+位运算存入

char ss[1<<17],*A=ss,*B=ss;
inline char gc(){if(A==B){B=(A=ss)+fread(ss,1,1<<17,stdin);if(A==B)return EOF;}return *A++;}
template<class T>inline void read(T&x){
    char c;re y=1;while(c=gc(),c<48||57<c)if(c=='-')y=-1;x=c^48;
    while(c=gc(),47<c&&c<58)x=(x<<1)+(x<<3)+(c^48);x*=y;
}

用法 in BNF

<any type> read(a);

水题

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>

using namespace std;
const int inf = 1e5 + 5;
int n, s[inf],cnt;
deque<int> q;
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &s[i]);
	sort(s, s + n + 1);
    for(int i=n;i>=1;i--)
    {
        if(cnt)q.push_front(s[i]),cnt^=1;
        else q.push_back(s[i]),cnt^=1;
    }
    cnt=0;
    deque<int>::iterator it;
    for(it=q.begin();it!=q.end();it++)
    s[++cnt]= *it ;
    for(int i=2;i<=n-1;i++)
    if(s[i-1]+s[i+1]<=s[i]){cout<<"NO";return 0;}
    if(s[n-1]+s[1]<=s[n]){cout<<"NO";return 0;}
    cout<<"YES"<<endl;
	for (int i = 1; i <= n; i++)cout << s[i] << " ";
	return 0;
}