# Codeforces Round #287 (Div. 2) 解题报告 A.B.C.D.E

A - Amr and Music

```#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=9901;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
struct node {
int x, n;
} fei[400];
int cmp(node f1, node f2)
{
return f1.x<f2.x;
}
int main()
{
int n, m, i, sum=0, j, pos;
scanf("%d%d",&n,&m);
for(i=0; i<n; i++) {
scanf("%d",&fei[i].x);
fei[i].n=i+1;
}
sort(fei,fei+n,cmp);
pos=n-1;
for(i=0; i<n; i++) {
if(sum+fei[i].x>m) {
pos=i-1;
break;
} else {
sum+=fei[i].x;
}
}
printf("%d\n",pos+1);
for(j=0; j<=pos; j++) {
printf("%d ",fei[j].n);
}
return 0;
}```
B - Amr and Pins

```#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=9901;
const int INF=0x3f3f3f3f;
const double eqs=1e-11;
int main()
{
LL r, x1, y1, x2, y2;
LL a;
double d, c;
while(scanf("%I64d%I64d%I64d%I64d%I64d",&r,&x1,&y1,&x2,&y2)!=EOF){
r*=2;
d=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
c=d/r;
a=(LL)c;
if(c==a){
printf("%I64d\n",a);
}
else
printf("%I64d\n",a+1);
}
return 0;
}```

C - Guess Your Way Out!

```#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=9901;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
LL ans, c, num[100], cnt, p[100], H;
void update(LL n, LL l, LL r, LL rt)
{
num[cnt++]=rt;
if(l==r) return ;
LL mid=l+r>>1;
if(n<=mid) update(n,lson);
else update(n,rson);
}
void dfs(int f, int h, LL l, LL r, LL rt)
{
if(l==r) return ;
LL next;
if(f==-1) next=rt<<1;
else next=rt<<1|1;
if(next!=num[h+1]) {
ans+=p[H-h-1];
f=-f;
}
c>>=1;
LL mid=l+r>>1;
if(f==-1) {
dfs(-f,h+1,lson);
} else {
dfs(-f,h+1,rson);
}
}
void init()
{
p[0]=1;
for(int i=1; i<=60; i++) {
p[i]=p[i-1]+((LL)1<<i);
//printf("%I64d\n",p[i]);
}
}
int main()
{
LL n, i;
while(scanf("%I64d%I64d",&H,&n)!=EOF) {
ans=0;
c=(LL)1<<H;
cnt=0;
init();
update(n-1,0,c-1,1);
/*for(i=0;i<cnt;i++){
printf("%I64d\n",num[i]);
}*/
dfs(-1,0,0,c-1,1);
printf("%I64d\n",ans+H);
}
return 0;
}```

D - The Maths Lecture

```#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
int mod, k, n;
const int INF=0x3f3f3f3f;
const double eqs=1e-6;
LL dp[1002][101][3], mo[1002];
LL dfs(int cnt, int mods, int in, int zero)
{
if(cnt==-1) return in;
if(zero&&dp[cnt][mods][in]!=-1) return dp[cnt][mods][in];
int l=(cnt==0), i, m, z;
LL ans=0;
for(i=l;i<=9;i++){
m=(mods+i*mo[n-cnt])%k;
if(i||zero) z=1;
else z=0;
ans+=dfs(cnt-1,m,in||(m==0&&z),z);
}
ans%=mod;
if(zero)    {
dp[cnt][mods][in]=ans;
}
return ans;
}
void init()
{
int i;
mo[1]=1%k;
for(i=2;i<=1000;i++){
mo[i]=(mo[i-1]*10)%k;
}
}
int main()
{
memset(dp,-1,sizeof(dp));
scanf("%d%d%d",&n,&k,&mod);
init();
printf("%I64d\n",dfs(n-1,0,0,0));
return 0;
}```

E - Breaking Good

```#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
int mod, k, n;
const int INF=0x3f3f3f3f;
const double eqs=1e-6;
int head[110000], cnt, vis[110000], dd[110000], pre[110000], c[110000];
struct node
{
int u, v, w, next, f, s;
}edge[210000];
void add(int u, int v, int w, int f)
{
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].f=f;
}
void spfa()
{
queue<int>q;
memset(vis,0,sizeof(vis));
q.push(1);
dd[1]=0;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
int v=edge[i].v;
if(dd[v]>dd[u]+edge[i].w){
dd[v]=dd[u]+edge[i].w;
pre[v]=u;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
}
void init()
{
cnt=0;
memset(dd,INF,sizeof(dd));
memset(pre,-1,sizeof(pre));
}
int main()
{
int n, m, i, u, v, w, j, sum=0, cnt1=0;
scanf("%d%d",&n,&m);
init();
while(m--){
scanf("%d%d%d",&u,&v,&w);
}
spfa();
for(i=n;i!=-1;i=pre[i]){
c[cnt1++]=i;
}
for(i=1;i<=n;i++){
edge[j].s=0;
}
}
for(i=cnt1-1;i>=1;i--){
u=c[i];
int v=edge[j].v;
if(v==c[i-1]){
edge[j].s=1;
edge[j^1].s=1;
//printf("%d %d %d\n",u,v,edge[j].w);
}
}
}
for(i=1;i<=n;i++){
if(edge[j].s+edge[j].f==1){
edge[j^1].f=1-edge[j^1].f;
//printf("%d %d %d %d\n",i,edge[j].v,edge[j].s,edge[j].w);
sum++;
}
}
}
printf("%d\n",sum);
for(i=1;i<=n;i++){
if(edge[j].s+edge[j].f==1){
printf("%d %d %d\n",i,edge[j].v,edge[j].s);
}
}
}
return 0;
}
```

Codeforces Round #287 (Div. 2) 解题报告 A.B.C.D.E

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊