2018.07.17【2018提高组】模拟C组

本文主要是介绍2018.07.17【2018提高组】模拟C组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言：OTL。。。

题目

JZOJ 1264 乱头发节

题目

求一头牛到后面第一头不低于该牛身高的牛之间的牛的数量（不包括两头牛，如果没有不低于的，就当做最后有一头无限高的牛）

分析

单调栈！如果不想开long long，那就用unsigned

代码

#include <cstdio>
#include <cctype>
#include <stack>
using namespace std;
typedef unsigned u;
u n,a[80002],ans; stack<u>st;
u in(){u ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
int main(){freopen("badhair.in","r",stdin);freopen("badhair.out","w",stdout);n=in(); st.push(n+1); a[n+1]=1<<31;for (u i=1;i<=n;i++) a[i]=in();for (u i=n;i>=1;i--){while (a[st.top()]<a[i]&&st.size()) st.pop();ans+=st.top()-i-1; st.push(i);}return !printf("%u",ans);
}

JZOJ 1265 Round Numbers

题目

求区间 $[l\cdot\cdot\cdot r]中$ 在二进制下0的个数不少于1的个数的数的个数。

分析

数位dp，用类似于前缀和的方式相减，可以发现对于最高位, 答案是
$\sum _{len=1}^{len<Len}\sum C_{len-1}^i|i*2>=len$ (kind of easy)
处理边界也比较简单，但是问题是非最高位怎么求，用一个duo表示1的个数。
然后剩下的挺像的，关键是细节部分！

代码

#include <cstdio>
#define min(a,b) (a<b)?a:b
using namespace std;
int len,l,r,num[31],f[31][31];
void init(){for (int i=0;i<31;i++) f[i][0]=1;for (int i=1;i<31;i++)for (int j=1;j<=i;j++) f[i][j]=f[i-1][j-1]+f[i-1][j];
}
int make(int x,int y){int resu=0;for (int i=0;i<=x;i++) if (i<<1>=x+y) resu+=f[x][i];return resu;
}
int ans(int x){if (x<2) return 0;int len=0,answer=0;while (x) num[++len]=x&1,x>>=1;for (int i=1;i<len;i++) answer+=make(i-1,1);int duo=1; len--;while (len){if (num[len]) answer+=make(len-1,duo-1);//如果是1说明可以扩展答案duo+=num[len--]?1:-1;//是不是1}return answer+=(duo<=0);//如果全是0那么答案加1
}
int main(){freopen("rndnum.in","r",stdin);freopen("rndnum.out","w",stdout);init(); scanf("%d%d",&l,&r);return !printf("%d",ans(r)-ans(l-1));//前缀和
}

JZOJ 1266 玉米田

题目

在M*N个格子里选择若干个互不相邻的格子并不能在规定的格子里，求方案数mod $10^8$

分析

状压dp，状态转移方程 $d p [i] [j] + = d p [i - 1] [k ∣ f [i - 1]]$ ，枚举k，为上一行的状态，f[i]表示不能选择的状态。

代码

#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;
typedef short sr;
sr n,m,f[13]; int dp[13][4097];
sr in(){sr ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
int main(){freopen("cowfood.in","r",stdin);freopen("cowfood.out","w",stdout);n=in(); m=in();for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)if (!in()) f[i]|=1<<j-1;//0不能选for (int i=0;i<1<<m;i++) dp[0][i]=1;//一开始方案都只有一种for (int i=1;i<=n;i++){for (int j=0;j<1<<m;j++){//枚举当前状态if (~j&f[i]) continue; //不匹配for (int k=0;k<1<<m;k++) if (!(k&(k<<1))&&!(k&j))//若状态可选且上一个状态的格子与当前状态的格子互不相邻dp[i][j]=(dp[i][j]+dp[i-1][k|f[i-1]])%100000000;//dp}}return !printf("%d",dp[n][f[n]]);
}

JZOJ 1267 路障

题目

求单源次短路径

分析

在比赛的时候，spfa都打出来了，就是答案算错了V^V。双向SPFA，再枚举每一条边算出次短路径。

代码

#include <bits/stdc++.h>
using namespace std;
struct node{int y,w,next;}e[200001]; int ls[5001];
int n,m,k,dis1[5001],dis[5001]; bool v[5001]; queue<int>q;
int in(){int ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
void spfa(int s,int *dis){v[s]=1; dis[s]=0; q.push(s);while (q.size()){int x=q.front(); q.pop();for (int i=ls[x];i;i=e[i].next)if (dis[x]+e[i].w<dis[e[i].y]){dis[e[i].y]=dis[x]+e[i].w;if (!v[e[i].y]) v[e[i].y]=1,q.push(e[i].y);}v[x]=0;} 
}
int main(){freopen("block.in","r",stdin);freopen("block.out","w",stdout);n=in(); m=in();for (int i=1;i<=m;i++){int x=in(),y=in(),w=in();e[++k]=(node){y,w,ls[x]}; ls[x]=k;e[++k]=(node){x,w,ls[y]}; ls[y]=k;}memset(dis,127/3,sizeof(dis)); spfa(1,dis); //从起点spfaint z=dis[n],ans=2147483647; memset(dis1,127/3,sizeof(dis1));memset(v,0,sizeof(v)); spfa(n,dis1);//从终点spfafor (int i=1;i<=n;i++)for (int j=ls[i];j;j=e[j].next)if (dis[i]+dis1[e[j].y]+e[j].w>z&&dis[i]+dis1[e[j].y]+e[j].w<ans) ans=dis[i]+dis1[e[j].y]+e[j].w;//每条边找次短路径return !printf("%d",ans);
}