【近期水题题解之2】

2015.05.20 08:49 Wed | 46次阅读 | 旧日oi | 固定链接 | 源码

bzoj3098       随机一个100000的字符串

我的程序

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<iostream>
using namespace std;
int n=100000,l=20;
int main()
{
    cout<<n<<' '<<l<<endl;
    for(int i=1;i<=n;i++) cout<<char(rand()%26+'a');
    cout<<endl;
    return 0;
}
bzoj2084  manacher算法,将原串的1变为2,中间填充位设为1,把判定回文串的条件改为a[i+p]+a[i-p]=2,求偶数回文串。
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 2000010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
char s[maxn];
int n,p[maxn],a[maxn];
int main()
{
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;i++) a[i<<1]=(s[i]=='0')?0:2;
    n=2*n+1;
    for(int i=1;i<=n;i+=2) a[i]=1;
    for(int mx=0,id=0,i=1;i<=n;i+=2)
    {
        if(mx>i) p[i]=min(p[2*id-i],mx-i);
        else p[i]=1;
        for(;i-p[i]>0&&i+p[i]<=n&&a[i+p[i]]+a[i-p[i]]==2;p[i]++);
        if(p[i]+i>mx) mx=p[i]+i,id=i;
    }
    ll ans=0;
    for(int i=1;i<=n;i+=2) ans+=(p[i]-1)>>1;
    cout<<ans<<endl;
}
bzoj1432 画图观察
#include<iostream>
#include<cstdio>
using namespace std;
int n,k;
int main()
{
    scanf("%d%d",&n,&k);
    if(n-k+1<k)k=n-k+1;
    if(n==1)printf("1");
    else printf("%d",2*k);
    return 0;
}
bzoj3767 a+b
a=[int(i) for i in raw_input().split()]
print a[1]+a[0]
bzoj1355   kmp
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 100010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char s[1000005];
int next[1000005],l;
int main()
{
    cin>>l;
    scanf("%s",s);
    int j=0,k=-1;next[0]=-1;
    while(j<l)
    {
        if(k==-1||s[j]==s[k])
        {
            k++;
            j++;
            next[j]=k;
        }
        else k=next[k];
    }
    cout<<l-next[l]<<endl;
}
bzoj1577   贪心考虑,维护一个set,里面存的是当前在车上的牛的下车时间。到达一个车站,让到站的下车,然后看这个车站的牛,如果车还没满载,就继续上,如果满载了,考虑车上下车最晚的牛的当前牛的下车时间,如果当前牛的比车上下车时间最晚的牛下车时间早,则踢掉那头牛,加入当前牛。
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 100010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int k,n,c,ans;
struct node{
    int l,r,m;
}a[50005];
bool cmp(const node &a,const node &b)
{
    return a.l<b.l;
}
multiset<int> s;
int main()
{
    k=read();n=read();c=read();
    for(int i=1;i<=k;i++)
    {
        a[i].l=read();a[i].r=read();a[i].m=read();
    }
    sort(a+1,a+k+1,cmp);
    for(int i=1;i<=k;i++)
    {
        while(s.size()&&(*s.begin())<=a[i].l) s.erase(s.find(*s.begin()));
        while(s.size()<c&&a[i].m) 
        {
            ans++;a[i].m--;
            s.insert(a[i].r);
        }
        while(a[i].m&&*s.rbegin()>a[i].r) 
        {
            a[i].m--;
            s.erase(s.find(*s.rbegin()));
            s.insert(a[i].r);
        }
    }
    cout<<ans<<endl;
}
bzoj3907  如果不考虑边界,相当于一共走n+m步,其中任意n步往右走,答案C(n+m,n),然后对于越界的,我们考虑如下方案:把终点和起点都向下移动一格,则不合法的方案是和x=y有交点的路线,考虑任意一条和xy有交点的路线,由对称性可知,从(0,-1)到(x,x) 和从(-1,0)到xx的方案是一样的,所以所有的不合法方案就变成了从(-1,0)到(n,m-1)的方案,C(n+m,n+1).
def c(x,y):
    ret=1
    for i in range(1,y+1):
        ret=ret*(x+1-i)/i
    return ret
a=[int(i) for i in raw_input().split()]
print c(a[0]+a[1],a[0])-c(a[0]+a[1],a[0]+1)
bzoj1102 传说中的floodfill,如此高深的算法实现竟然如此简单,实在是涨姿势~
#include<cstring>
#include<cstdio>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
int n,flag,ans;
int a[1005][1005];
bool vis[1005][1005];
queue< pair<int,int> > q;
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};
void bfs(int x,int y)
{
    vis[x][y]=1;
    while(!q.empty()) q.pop();
    q.push(make_pair(x,y));
    while(!q.empty())
    {
        x=q.front().first,y=q.front().second;q.pop();
        for(int tx,ty,i=0;i<8;i++)
        {
            tx=x+dx[i],ty=y+dy[i];
            if(tx<1||ty<1||tx>n||ty>n) continue;
            if(a[tx][ty]>a[x][y]) flag=0;
            if(!vis[tx][ty]&&a[tx][ty]==a[x][y]) 
            {
                vis[tx][ty]=1;
                q.push(make_pair(tx,ty));
            }
        }
    }
}
void work()
{
    ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(!vis[i][j])
            {
                flag=1;
                bfs(i,j);
                ans+=flag;
            }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    work();cout<<ans<<" ";
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=-a[i][j],vis[i][j]=0;
    work();cout<<ans<<endl;
    return 0;
}
bzoj1345 SB 
#include<iostream>
#include<cstdio>
using namespace std;
int n,x,y;
long long ans;
int main()
{
    cin>>n>>x;
    for(int i=1;i<n;i++) 
    {
        scanf("%d",&y);
        ans+=max(x,y);x=y;
    }
    cout<<ans<<endl;
}
bzoj1 575   dp[i][j]表示前i个选j个(必选第i个)的最小误差,预处理出cost数组,然后转移很简单。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,e,a[105];
int dp[105][105],cost[105][105];
int main()
{
    cin>>n>>e;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    memset(dp,0x3f,sizeof(dp));dp[0][0]=0;
    for(int i=0;i<=n;i++)
    for(int j=i+1;j<=n+1;j++)
    {
        for(int k=i+1;k<j;k++)
        {
            if(i==0) cost[i][j]+=2*abs(a[j]-a[k]);
            else if(j==n+1) cost[i][j]+=2*abs(a[i]-a[k]);
            else cost[i][j]+=abs(2*a[k]-a[i]-a[j]);
        }
    }
    for(int i=1;i<=n+1;i++)
    {
        for(int j=1;j<=i;j++)
        {
            for(int k=0;k<i;k++)
            dp[i][j]=min(dp[i][j],dp[k][j-1]+cost[k][i]);
        }
    }
    for(int i=2;i<=n+1;i++) 
    if(dp[n+1][i]<=e)
    {
        printf("%d %d\n",i-1,dp[n+1][i]);
        return 0;
    }
}
bzoj1143    拓扑图上的最大独立点集,用floyd传递闭包,然后二分图就行
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int n,m;
int map[105][105],mp[205][205],match[205];
bool vis[205];
bool dfs(int u)
{
    for(int v=n+1;v<=n+n;v++)
    if(mp[u][v]&&!vis[v])
    {
        vis[v]=1;
        if(!match[v]||dfs(match[v]))
        {
            match[v]=u;
            return 1;
        }
    }
    return 0;
}
int main()
{
    cin>>n>>m;
    for(int u,v,i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        map[u][v]=1;
    }
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    map[i][j]|=(map[i][k]&map[k][j]);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    if(i!=j&&map[i][j]) 
    mp[i][j+n]=1;
    int ans=n;
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        if(dfs(i)) ans--;
    }
    cout<<ans<<endl;
}
bzoj2721   可以打表找下规律,发现答案只和每个质因数的次数有关。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
#define mod 1000000007
using namespace std;
ll prime[100005],have[100005],ans=1;
bool vis[1000005];
int n,cnt;
int main()
{
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt&&prime[j]*i<=n;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        ll k=prime[i];
        while(k<=n)
        {
            have[i]+=n/k;
            k*=prime[i];
        }
    }
    for(int i=1;i<=cnt;i++) ans=ans*(2*have[i]+1)%mod;
    cout<<ans<<endl;
}
bzoj1334 SBdp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,a[305],sum;
bool dp[305][100005];
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
    sort(a+1,a+n+1,cmp);
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=sum;j++) dp[i][j]=dp[i-1][j];
        for(int j=0;j<=sum/2;j++)
        if(dp[i-1][j]) dp[i][j+a[i]]=1;
    }
    for(int i=sum;i>sum/2;i--)
    if(dp[n][i]) 
    {
        cout<<i<<endl;
        return 0;
    }
}
bzoj1572  又是那个经典模型
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define ll long long
using namespace std;
struct node{
    int d;long long p;
}a[100005];
int n;
long long ans;
bool cmp(const node &a,const node &b)
{
    return a.d<b.d;
}
priority_queue<ll,vector<ll>,greater<ll> > q;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d%lld",&a[i].d,&a[i].p);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(q.size()<a[i].d) 
        {
            ans+=a[i].p;
            q.push(a[i].p);
        }
        else if(q.top()<a[i].p)
        {
            ans-=q.top();q.pop();
            ans+=a[i].p;q.push(a[i].p);
        }
    }
    cout<<ans<<endl;
}
bzoj1342 一眼水题
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
using namespace std;
multiset<int> s;
int n,m,c;
int a[1000005];
int main()
{
    cin>>n>>m>>c;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(i<m) s.insert(a[i]);  
    }
    if(m>n) 
    {
        puts("NONE");
        return 0;
    }
    bool flag=0;
    for(int i=m;i<=n;i++)
    {
        s.insert(a[i]);
        if(*s.rbegin()-*s.begin()<=c) printf("%d\n",i-m+1),flag=1;
        s.erase(s.find(a[i-m+1]));
    }
    if(!flag) puts("NONE");
    return 0;
}
bzoj1770  高斯消元裸题
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int a[40][40],ans=0x3f3f3f3f,x[40];
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
int sure[105];
int gauss(int equ,int var)
{
    int i,id,j,k;
    for(i=1,id=1;i<=var;i++,id++)
    {
        for(j=id;j<=equ&&!a[j][i];j++);
        if(j>equ) {id--;continue;}
        sure[id]=i;
        if(j!=id) for(k=1;k<=var+1;k++) swap(a[j][k],a[id][k]);
        for(j=id+1;j<=equ;j++) if(a[j][i]) for(k=i;k<=var+1;k++) 
            a[j][k]^=a[id][k];
    }
    return id-1;
}
void dfs(int cur,int now,int ret)
{
    if(cur<1)
    {
        ans=min(ans,ret);
        return;
    }
    if(ret>=ans) return;
    if(now==sure[cur]) 
    {
        bool tmp=a[cur][n+1];
        for(int i=now+1;i<=n;i++) tmp^=a[cur][i]*x[i];
        x[now]=tmp;
        dfs(cur-1,now-1,ret+x[now]);
    }
    else
    {
        x[now]=0;dfs(cur,now-1,ret);
        x[now]=1;dfs(cur,now-1,ret+1);
    }
}
int main()
{
    cin>>n>>m;
    for(int u,v,i=1;i<=m;i++)
    {
        u=read();v=read();
        a[u][v]=a[v][u]=1;
    }
    for(int i=1;i<=n;i++)
    a[i][i]=a[i][n+1]=1;
    int t=gauss(n,n);
    dfs(t,n,0);
    cout<<ans<<endl;
    return 0;
}
bzoj1596 简单的树dp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define inf 0x3f3f3f3f
using namespace std;
int n;
int dp[10005][3];
struct edge{
    int to,next;
}e[20005];
int h[10005],tp;
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;
}
void dfs(int u,int f)
{
    dp[u][1]=1;
    int tmp=inf,flag=1;
    for(int v,i=h[u];e[i].to;i=e[i].next)
    if((v=e[i].to)!=f)
    {
        dfs(v,u);tmp=min(tmp,dp[v][1]-dp[v][0]);
        if(dp[v][1]<=dp[v][0])
        {
            flag=0;
            dp[u][0]+=dp[v][1];
        }
        else dp[u][0]+=dp[v][0];
        dp[u][1]+=min(dp[v][0],min(dp[v][1],dp[v][2]));
        dp[u][2]+=min(dp[v][0],dp[v][1]);
    }
    if(flag) dp[u][0]+=tmp;
}
int main()
{
    cin>>n;
    for(int u,v,i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        ae(u,v);ae(v,u);
    }
    dfs(1,0);
    cout<<min(dp[1][0],dp[1][1])<<endl;
}
bzoj1207     类似lis,上界n^2,可以剪枝
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,x[10005],y[10005],t[10005];
int dp[10005],mx[10005],ans;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        dp[i]=1;
        scanf("%d%d%d",&t[i],&x[i],&y[i]);
        for(int j=i-1;j;j--)
        {
            if(mx[j]<dp[i]) break;
            if(abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j]&&dp[j]>=dp[i]) 
            dp[i]=dp[j]+1;
        }
        mx[i]=max(dp[i],mx[i-1]);
    }
    cout<<mx[m]<<endl;
}
bzoj1121 ……太难不会
#include<cstdio>
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%*d%*d");
    printf("%d\n",n/2);
}```