NOIP2016滚粗记
考完...身败名裂\(QAQ\)
day1
T1
\(Description\)
顺时针逆时针数小人(迷之\(mengbier,mogician\)).
\(Solution\)
模拟.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define M 15
#define N 100005
using namespace std;
struct toy{
int t;char c[M];
}a[N];
int n,m,t,s,u=1;
inline void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d%s",&a[i].t,a[i].c+1);
while(m--){
scanf("%d%d",&t,&s);
if(t){//right
if(a[u].t) u=(u-s+n)%n;
else u=(u+s)%n;
if(!u) u=n;
}
else{
if(a[u].t) u=(u+s)%n;
else u=(u-s+n)%n;
if(!u) u=n;
}
}
printf("%s\n",a[u].c+1);
}
int main(){
freopen("toy.in","r",stdin);
freopen("toy.out","w",stdout);
init();
fclose(stdin);
fclose(stdout);
return 0;
} T2
\(Description\)
给定一课大小为n的树，m个人同时从\(s_i\)到\(t_i\)(第0时刻开始，走最短路), 对每个点u求第\(w_u\)秒这个点上的人数.
\(Solution\)
把t=0时，从\(s_i\)到\(t_i\)拆成：t=0时从\(s_i\)走到\(lca(s_i,t_i)\) 和 \(t=|dep[s_i]-dep[lca(s_i,t_i)]|\)时从\(lca(s_i,t_i)\)走到\(t_i\).
在t时从x出发, 对\(i\)点有贡献需满足\(w_i-t=|dep[x]-dep[i]|\), 即\(\begin{cases}w_i+dep[i]=t+dep[x]&bottom-up\\w_i-dep[i]=t-dep[x]&top-down\end{cases}\).
然后只讨论从下往上走怎么处理(因为从上往下走处理方式同理):
对树上\(w_i+dep[i]\)的值相同的点进行差分,进出的时候+1,-1即可.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define K 20
#define N 300000
#define M 900000
using namespace std;
typedef long long ll;
stack s;
struct graph{
int nxt,to,ty;
}e[N<<1],e2[M];
int f[N][K],px[N<<1],py[N<<1],t1[N],t2[N],w[N],g[N],g2[N],dep[N],ans[N],n,m,cnt;
//px[x]:w[i]+dep[i]=x最近的点
//t1[i]:从下往上时,i能看到的人数
inline int read(){
int ret=0;char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
ret=(ret<<1)+(ret<<3)+c-'0';
c=getchar();
}
return ret;
}
inline void adde(int x,int y){
e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;
}
inline void adde2(int x,int y,int ty){
e2[++cnt].nxt=g2[x];g2[x]=cnt;e2[cnt].to=y;e2[cnt].ty=ty;
}
inline void dfs(int u){
dep[u]=1;s.push(u);
while(!s.empty()){
u=s.top();s.pop();
if(u==1) for(int i=0;i>=1)
if(h&1) u=f[u][i];
return u;
}
inline int lca(int x,int y){
if(dep[x]dep[u]) dfs2(c);
change(u);
ans[u]+=t1[u]+t2[u];
t1[x]+=t1[u];t2[y]+=t2[u];
px[wx]=x;py[wy]=y;
}
inline void Aireen(){
n=read();m=read();
for(int i=1,x,y;i T3
\(Description\)
一个人为了少走路可以选择去另一个教室上课,换课需申请,申请有概率不通过.求上课需要行走的路程和的期望.
\(Solution\)
\(floyd\)+数学期望+\(01\)背包.
\(f[i][j][0/1]\)表示前 \(i\) 个时间段换过 \(j\) 次教室，第 \(i\) 个时间段是否换过教室的体力值和的期望.
\(f[i][j][0]=min\{f[i-1][j][0]+dis[c_{i-1}][c_i],f[i-1][j][1]+p(i,g_{i-1},0.0)\}\)
\(f[i][j][1]=min\{f[i-1][j-1][0]+p(i,0.0,g_i),f[i-1][j-1][1]+p(i,g_{i-1},g_i)\}\)
其中，\(p(i,p_{i-1},p_i)\) 表示在走到 \(d_{i-1}\) 的概率为 \(p_{i-1}\)，走到 \(d_{i}\) 的概率为 \(p_{i}\)的前提下，从第 \((i-1)\) 个教室到第 \(i\) 个教室的期望体力值.
\(p(i,p_{i-1},p_i)=dis[c_{i-1}][c_i]*(1.0-p_{i-1})*(1.0-p_i)+dis[c_{i-1}][d_i]*(1.0-p_{i-1})*p_i+dis[d_{i-1}][c_i]*p_{i-1}*(1.0-p_i)+dis[d_{i-1}][d_i]*p_{i-1}*p_i\).
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define M 305
#define N 2005
#define INF 1e9
using namespace std;
int c[N],d[N],n,m,v,e;
double f[N][N][2],dis[M][M],g[N],ans;
//x:走到d[i-1]的概率; y:走到d[i]的概率
inline double p(int i,double x,double y){
return dis[c[i-1]][c[i]]*(1.0-x)*(1.0-y)+dis[c[i-1]][d[i]]*(1.0-x)*y+dis[d[i-1]][c[i]]*x*(1.0-y)+dis[d[i-1]][d[i]]*x*y;
}
inline void init(){
scanf("%d%d%d%d",&n,&m,&v,&e);
for(int i=1;i<=n;++i)
scanf("%d",&c[i]);
for(int i=1;i<=n;++i)
scanf("%d",&d[i]);
for(int i=1;i<=n;++i)
scanf("%lf",&g[i]);
for(int i=1;i day2
T1
\(Description\)
给定\(n,m\),求\(\sum_{i=0}^{i=n}\sum_{j=0}^{j=min(i,m)}C_{i}^{j}\equiv0(mod\;k)\)的对数.
\(Solution\)
质因数分解,递推,前缀和维护.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define M 8
#define N 2001
using namespace std;
bool flag;
int p[M]={2,3,5,7,11,13,17,19};
int tot[N][M],f[N][N],sum[N][N],a[M],n,m,t,k;
inline void init(){
scanf("%d%d",&t,&k);
for(int i=2,l;i T2
\(Description\)
蚯蚓切呀切,某次打\(ACM\)的时候遇到过.
\(Solution\)
满足单调性,三个数组维护.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 7100005
using namespace std;
typedef long long ll;
typedef long double ld;
struct worm{
ll x,s;
}q1[N],q2[N],q3[N];
ld p;
ll len[N],q,sum;
int n,m,t,h1,h2,h3,t1,t2,t3,ty,cnt;
inline int read(){
int ret=0;char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
ret=(ret<<1)+(ret<<3)+c-'0';
c=getchar();
}
return ret;
}
inline ld rd(){
int ret=0;char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
ret=(ret<<1)+(ret<<3)+c-'0';
c=getchar();
}
return (ld)(ret);
}
inline ll rd_ll(){
ll ret=0;char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
ret=(ret<<1LL)+(ret<<3LL)+c-'0';
c=getchar();
}
return ret;
}
inline ll f(ll sum){
ld k=(ld)(sum)*p;
return (ll)(k);
}
inline ll tot(worm x){
return x.x-x.s+sum;
}
inline bool cmp(worm x,worm y){
return x.x>y.x;
}
inline void init(){
n=read();m=read();q=rd_ll();
p=rd();p/=rd();t=read();
for(int i=1;i<=n;++i)
q1[i].x=(ll)(read());
h1=h2=h3=1;t1=n;
sort(q1+1,q1+1+t1,cmp);
n+=m;
while(m--){
++cnt;
if(h1<=t1){
len[cnt]=tot(q1[h1]);ty=1;
}
if(h2<=t2&&tot(q2[h2])>=len[cnt]){
len[cnt]=tot(q2[h2]);ty=2;
}
if(h3<=t3&&tot(q3[h3])>=len[cnt]){
len[cnt]=tot(q3[h3]);ty=3;
}
q2[++t2].x=f(len[cnt]);
q3[++t3].x=len[cnt]-q2[t2].x;
sum+=q;q2[t2].s=q3[t3].s=sum;
if(ty==1) ++h1;
else if(ty==2) ++h2;
else ++h3;
}
for(int i=t;i<=cnt;i+=t)
printf("%lld ",len[i]);
printf("\n");
for(int i=1;i<=n;++i){
len[0]=0LL;
if(h1<=t1){
len[0]=tot(q1[h1]);ty=1;
}
if(h2<=t2&&tot(q2[h2])>=len[0]){
len[0]=tot(q2[h2]);ty=2;
}
if(h3<=t3&&tot(q3[h3])>=len[0]){
len[0]=tot(q3[h3]);ty=3;
}
if(ty==1) ++h1;
else if(ty==2) ++h2;
else ++h3;
if(!(i%t)) printf("%lld ",len[0]);
}
printf("\n");
}
int main(){
freopen("earthworm.in","r",stdin);
freopen("earthworm.out","w",stdout);
init();
fclose(stdin);
fclose(stdout);
return 0;
} T3
\(Description\)
求至少需要多少条抛物线可以过所有的点.
\(Solution\)
观察到N很小，考虑状压\(DP\).
预处理出所有可能的抛物线，\(g[i]\)表示第\(i\)条抛物线可以经过的点集的二进制状态 (每个点可以单独地被一条合法的抛物线经过).
\(f[i][j]\)表示前\(i\)条抛物线到达状态\(j\)所需的最小抛物线数，\(f[i][j|g[i]]=min\{f[i-1][j|g[i]],f[i-1][j]+1\}\), 第一维可以在实现时被优化掉.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 20
#define M 160
#define K 262145
#define eps 1e-13
using namespace std;
struct line{
double a,b;
}a[M];
double x[N],y[N];
int f[K],g[M],n,m,k,l,t,cnt;
inline double sqr(double k){
return k*k;
}
inline bool cmp(line x,line y){
if(fabs(x.a-y.a)eps||fabs(a[i].b-a[i-1].b)>eps)
a[++k]=a[i];
memset(g,0,sizeof(g));
for(int i=1;i<=k;++i)
for(int j=1;j<=n;++j)
if(chk(i,j)) g[i]|=(1<=0;--j)
f[j|g[i]]=min(f[j|g[i]],f[j]+1);
printf("%d\n",f[l]);
}
}
}
int main(){
freopen("angrybirds.in","r",stdin);
freopen("angrybirds.out","w",stdout);
init();
fclose(stdin);
fclose(stdout);
return 0;
}