注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一个蒟蒻的代码回收站

最后一次省选求rp

 
 
 

日志

 
 

codeforces 298(div 2)  

2015-04-30 15:10:07|  分类: codeforces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
已经弱到去做div2还做不对的程度了QAQ
A:
给一个n,要求给出一个排列,使得相邻两个数差不能是1。
开始看错了一次题目QAQ(获得成就,WA div2A题)
n小的时候特判掉,n大的时候就先把偶数排前面,奇数排后面就好了。
#include<bits/stdc++.h>
using namespace std;

#define maxn 5010
int n,m;
bool a[maxn];
int ans[maxn];

int main()
{
scanf
("%d",&n);
if (n==1||n==2) printf("1\n1\n");
else if(n==3) printf("2\n1 3\n");
else
{
printf
("%d\n",n);
for (int i=2;i<=n;i+=2) printf("%d ",i);
for (int i=1;i<=n;i+=2) printf("%d ",i);
}
return 0;
}

B:
有一辆车,已知其初速度为v1,末速度为v2,行驶时间为t,每单位时间速度最少改变d,求最长行驶距离。
从后往前把每个时间能到达的最大速度预处理出来,然后从前往后做。如果大于最大速度就变成最大速度。
#include<bits/stdc++.h>
using namespace std;

#define maxn 100010
int v1,v2,t,d;
int n;
int a[maxn];
int ans;

int main()
{
scanf
("%d%d",&v1,&v2);
scanf
("%d%d",&t,&d);
a
[t]=v2;
for (int i=t-1;i>1;i--) a[i]=a[i+1]+d;
int hzh=v1;
ans
=hzh;
for (int i=2;i<=t;i++)
{
int mxh=hzh;
hzh
+=d;
if (hzh>a[i]) hzh=a[i];
ans
+=hzh;
}
printf
("%d\n",ans);
return 0;
}

C:
有n个骰子,每个骰子i能投出1~ai的数,现在他投了一次,记录下了这n个数的和。
问你每个骰子不可能投出多少数。
不考虑自身的范围限制的话
每个骰子最大投出的数=m-(n-1),最小投出的数=m-(s-a[i])
#include<bits/stdc++.h>
using namespace std;

#define maxn 200010
typedef long long ll;
ll n
,m,s;
ll a
[maxn];

int main()
{
scanf
("%I64d%I64d",&n,&m);
for (int i=1;i<=n;i++) scanf("%I64d",&a[i]),s+=a[i];
for (int i=1;i<=n;i++)
{
ll minx
=max(1LL,m-(s-a[i]));
ll maxx
=min(a[i],m-(n-1));
printf
("%I64d ",minx-1+a[i]-maxx);
}
return 0;
}

D:
有n个人,他们进入房间(进入房间的顺序不知),每次进入时要和房间里的每一个人握手。但是,房间里每三个人可以组成一些三人小团体,小团体组成之后就不用和别人握手了,小团体可以在任意时候组成,但是组成后就不能解散,已知每个人进来时的握手次数,求是否存在一种进入房间的顺序满足。
贪心,如果进来一个人能够不组成小团体就满足的,那就不组成小团体,否则在那一瞬间不停地组成小团体直到满足为止。
#include<bits/stdc++.h>
using namespace std;

#define maxn 200010
int n,m;
struct Edge
{
int b,next;
} edge[maxn];
int g[maxn],tot;
int ans[maxn];

void addedge(int a,int b)
{
tot
++;
edge
[tot].b=b;
edge
[tot].next=g[a];
g
[a]=tot;
}
int main()
{
scanf
("%d",&n);
for (int i=1;i<=n;i++)
{
int x;
scanf
("%d",&x);
addedge
(x,i);
}
int tmp=0;
for (int i=1;i<=n;i++)
{
while (tmp>=0 && g[tmp]==0) tmp-=3;
if (g[tmp]!=0)
{
ans
[i]=edge[g[tmp]].b;
g
[tmp]=edge[g[tmp]].next;
} else {printf("Impossible\n");return 0;}
tmp
++;
}
printf
("Possible\n");
for (int i=1;i<=n;i++) printf("%d ",ans[i]);
//system("pause");
return 0;
}

E:
数轴上有n个点,他们的坐标为a1~an,保证递增。
有一辆公交车,他从点1出发前往点n,然后返回,再前往点n,再返回……
现在知道了某一段时间内他的经过的站点(排过序的)
求公交车在这段时间内经过的路径长度(如果路径长度不唯一或不存在则输出-1)
我们先假定公交车从1出发,方向为正方向,走m次之后到了某个位置,然后判一判是否合法,如果不合法,就要把起点往右移,然后我们发现往右移一段就是把开头第一段距离减掉,再加上最后多走的距离,然后就好辣~
因为各种脑抽错了若干次
#include<bits/stdc++.h>
using namespace std;

#define maxn 200010
typedef long long ll;
int a[maxn];
int b[maxn];
int c[maxn];
int n,m,cnt,cnt1;
ll ans
=-1,sum;

void getans(ll x)
{
if (ans==-1) ans=x;else
if (ans!=x) {printf("-1\n");exit(0);}
}
void add(int x,int y)
{
if (y==0) return;
if (b[x]==0) cnt1++;
b
[x]+=y;
if (b[x]==0) cnt1--;
}
int main()
{
scanf
("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
scanf
("%d",&m);
for (int i=1;i<=m;i++)
{
int x;
scanf
("%d",&x);
c
[x]++;
if (c[x]==1) cnt++;
}
{
memcpy
(b,c,sizeof(c));
sum
=0;
cnt1
=cnt;
int dire=1;
int pos=1;
add
(1,-1);
for (int i=2;i<=m;i++)
{
pos
+=dire;
add
(pos,-1);
if (dire==1) sum+=a[pos]-a[pos-1];else sum+=a[pos+1]-a[pos];
if (pos==1) dire=1;
if (pos==n) dire=-1;
}
int pos1=1;
int dire1=1;
for (int i=1;i<=2*n;i++)
{
if (cnt1==0) getans(sum);
sum
-=abs(a[pos1+dire1]-a[pos1]);
add
(pos1,1);
pos1
+=dire1;
if (pos1==1) dire1=1;
if (pos1==n) dire1=-1;
sum
+=abs(a[pos+dire]-a[pos]);
pos
+=dire;
add
(pos,-1);
if (pos==1) dire=1;
if (pos==n) dire=-1;
}
}
cout
<<ans<<endl;
return 0;
}

F:
给定n,m,问是否存在一个n*m的01矩阵,使得每行每列的连续1的段数满足要求。
输出任意解即可。
因为n<=5,m<=20
装压dp
f[i][j][k]表示到第i列连续段数情况为j,当前列情况为k是否可行。
然后就暴力转移好了
输出方案的话再搜一遍即可。
刚开始是记录方案的,然后MLE了QAQ
#include<bits/stdc++.h>
using namespace std;

struct PII
{
int first;
short second;
};
#define fi first
#define se second
int n,m;
int a[30],b[30];
bool f[21][161060][33];
PII c
[5154000],d[5154000];
int h1,h2;
int ans[30][30],ans1,ans2;

int haha(int s,int t)
{
int q=1;
int sum=0;
for (int i=1;i<=n;i++)
{
if ((s%2==0) && (t%2==1)) sum+=q;
q
*=11;
t
>>=1;
s
>>=1;
}
return sum;
}
bool ok(int s,int t)
{
int q=0;bool bo=false;
while (t>0)
{
if (t&1)
{
if (!bo) q++;
bo
=true;
} else bo=false;
t
>>=1;
}
return b[s]==q;
}
int main()
{
scanf
("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
scanf
("%d",a+i);
ans1
*=11;
ans1
+=a[i];
}
for (int i=1;i<=m;i++) scanf("%d",b+i);
PII
*x=c,*y=d;
x
[1]=(PII){0,0};
h1
=1;
for (int i=1;i<=m;i++)
{
h2
=0;
for (int k=0;k<(1<<n);k++)
if (ok(i,k))
for (int j=1;j<=h1;j++)
{
if (i==12 && x[j].fi==45256 && x[j].se==16 && k==31)
{
int qqqqq=31;
}
int qqq=x[j].fi+haha(x[j].se,k);
if (!f[i][qqq][k]) f[i][qqq][k]=true,y[++h2]=(PII){qqq,k};
//if (h2>=5154000) cerr<<"biubiu"<<endl;
if (i==m && qqq==ans1) ans2=k;
}
swap
(x,y);
//cerr<<h2<<endl;
swap
(h1,h2);
}
for (int i=m;i>=1;i--)
{
int last=ans2;
for (int j=n;j>=1;j--)
{
ans
[j][i]=last&1;
last>>=1;
}
for (int k=0;k<(1<<n);k++)
if (ok(i-1,k))
{
int qqq=ans1-haha(k,ans2);
if (f[i-1][qqq][k])
{
ans2
=k;
ans1
=qqq;
break;
}
}
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
if (ans[i][j]) printf("*");else printf(".");
printf
("\n");
}
return 0;
}

  评论这张
 
阅读(78)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018