Codeforces Round #516 (Div. 2) (A~E)

时间:2022-08-05 09:54:59


Codeforces 1064

比赛链接

唉 人生啊

during the contest:

Codeforces Round #516 (Div. 2) (A~E)

Codeforces Round #516 (Div. 2) (A~E)

system test:

Codeforces Round #516 (Div. 2) (A~E)

一位博友突然失去了梦想

Codeforces Round #516 (Div. 2) (A~E)

A.Make a triangle!

不放了。

B.Equations of Mathematical Magic

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
const int N=1e6+7; inline int read()
{
int now=0,f=1;register char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;
} int main()
{
int T=read();
while(T--)
{
long long a=read(), ans=1;
for(int i=31; i>=0; --i)
if(a>>i&1) ans<<=1ll;
printf("%I64d\n",ans);
}
return 0;
}

C.Oh Those Palindromes

sb了很长时间。。

为什么要把很多字符拼起来呢,同种字符放在一起就行了。

Why so? 注意到一个回文串首尾至少是两个相同字符,所以一个出现x次的字符最多可以(以它为首尾)形成x(x-1)/2个回文串,这和单个放一起的上界是一样的。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=1e5+5; inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
} int tm[N];
char s[N],Ans[N]; int main()
{
int n=read();
scanf("%s",s+1);
std::sort(s+1,s+1+n);
s[n+1]='\0', puts(s+1); return 0;
}

比赛结束后

D.Labyrinth(BFS)

  因为BFS一般是可以保证到达一个点时代价最小,所以考虑BFS。

  本题有向左和向右两个代价。显然如果上下没有格子阻碍,我们可以先一直向上下扩展状态。

  然后,如果一直向左或是向右,那么BFS到的点显然代价最小。

  如果要走回头路(即直接向上的路被堵住,但能绕上去),那么假设向左边走要走\(a\)步才能向右走绕回去,向右边走要\(b\)步才能向左走绕回去。那么前者向右也要走\(a\)步,后者向左也要走\(b\)步。所以我们只保证向左走的步数尽量少,就可以保证到达某一个点时向右走的步数也尽量少。好像也很符合BFS性质?直接BFS?

  但是向左走的步数少不代表距离近。比如下图,起点为白点,要到达绿点,显然从白点向左出发到它花费少(花费指向左向右的步数)。但是如果直接BFS,因为左边上上下下浪费了时间,所以实际先到绿点的是向白点右边出发的路径。这当然不优(花费多)。

Codeforces Round #516 (Div. 2) (A~E)

  因为向上向下是不计代价的(也就是距离为\(0\)),所以BFS到一个点时,要把它上下能直接到的点同时加入队列(代价相同,也就是距离相同,当然在BFS里要同时入队),而不是在把它弹出队首时才在队列中加入上下的点(BFS的意义?后加入的点花费/距离比之前的点高。但实际它们代价是一样的)。

//62ms	4100KB
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=2005;
const int D[]={-1,1}; int n,m,r,c,X,Y;
bool ok[N][N];
struct Node
{
int x,y,r1,r2;
};
std::queue<Node> q; inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
void Extend(int x,int y,int r1,int r2)
{
for(int i=x; ok[i][y]; --i)
ok[i][y]=0, q.push((Node){i,y,r1,r2});
for(int i=x+1; ok[i][y]; ++i)
ok[i][y]=0, q.push((Node){i,y,r1,r2});
}
void BFS()
{
int ans=0;
Extend(r,c,X,Y);
while(!q.empty())
{
++ans;
Node tmp=q.front(); q.pop();
int x=tmp.x,y=tmp.y,r1=tmp.r1,r2=tmp.r2;
if(r1&&ok[x][y-1]) Extend(x,y-1,r1-1,r2);
if(r2&&ok[x][y+1]) Extend(x,y+1,r1,r2-1);
}
printf("%d\n",ans);
} int main()
{
n=read(),m=read(),r=read(),c=read(),X=read(),Y=read();
for(int i=1; i<=n; ++i)
{
register char c=gc(); while(c!='*'&&c!='.') c=gc();
ok[i][1]=c=='.';
for(int j=2; j<=m; ++j) ok[i][j]=gc()=='.';
}
BFS(); return 0;
}

E.Dwarves,Hats and Extrasensory Abilities(交互 二分)

容易想到根据点的颜色,不断二分调整询问位置。

但是\(2^{30}>10^9\),\(30\)次二分要出事。。

我们可以先询问一次端点(\(0\)或\(10^9\)),后面的二分再根据这个判断位置,就是\(29\)次二分啦。

pretest直接\(30\)次二分都可以过的吗。。明明大于1e9我怎么当时就觉得可以了呢。。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=2e6+5; inline char Get(int p)
{
static char s[233];
printf("10 %d\n",p), fflush(stdout);
scanf("%s",s); return s[0];
} int main()
{
int n; scanf("%d",&n);
int s=Get(0),l=0,r=1e9,mid;
for(int i=1; i<n; ++i)
{
mid=l+r>>1;
if(Get(mid)==s) l=mid;
else r=mid;
}
printf("9 %d 11 %d\n",l,l+1), fflush(stdout); return 0;
}

F.Candies for Children

大概是按照\(n\)的大小两种算法(暴力?)结合?

坑了


未AC代码

D.Labyrinth

#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=2005; inline int read()
{
int now=0,f=1;register char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;
} const int D[]={-1,1};
int n,m,r,c,X,Y;
char s[N];
bool mp[N][N],vis[N][N];
struct Node
{
int x,y,r1,r2;
};
std::queue<Node> q; void BFS()
{
int ans=0;
q.push((Node){r,c,X,Y});
vis[r][c]=1;
while(!q.empty())
{
++ans;
Node tmp=q.front(); q.pop();
int x=tmp.x,y=tmp.y,r1=tmp.r1,r2=tmp.r2;
for(int i=x-1; i>0; --i)
{
if(!mp[i][y]) break;
if(vis[i][y]) break;//continue;
vis[i][y]=1, q.push((Node){i,y,r1,r2});
}
for(int i=x+1; i<=n; ++i)
{
if(!mp[i][y]) break;
if(vis[i][y]) break;//continue;
vis[i][y]=1, q.push((Node){i,y,r1,r2});
}
for(int i=0; i<2; ++i)
{
int yn=y+D[i];
if(!mp[x][yn]||vis[x][yn]) continue;
vis[x][yn]=1;
if(r1>0&&i==0) q.push((Node){x,yn,r1-1,r2});
if(r2>0&&i==1) q.push((Node){x,yn,r1,r2-1});
}
}
printf("%d\n",ans);
} int main()
{
n=read(),m=read(),r=read(),c=read(),X=read(),Y=read();
for(int i=1; i<=n; ++i)
{
scanf("%s",s+1);
for(int j=1; j<=m; ++j)
if(s[j]=='.') mp[i][j]=1;
else mp[i][j]=0;
}
BFS(); return 0;
}

E.Dwarves,Hats and Extrasensory Abilities

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
#define mp std::make_pair
#define pr std::pair<int,int>
typedef long long LL;
const int N=2e6+5; struct Node
{
int col,pos;//0:w 1:b
bool operator <(const Node &x)const
{
return col==x.col?pos<x.pos:col<x.col;
}
}p[N]; bool Check(int pos,int now)
{
static char s[233];
p[now].pos=pos;
printf("10 %d\n",pos); fflush(stdout);
scanf("%s",s+1);
if(s[1]=='w') return p[now].col=0,0;
else return p[now].col=1,1;
} int main()
{
int n;
scanf("%d",&n);
int l=1,r=1e9,mid;
for(int i=1; i<=n; ++i)
{
mid=l+r>>1;
if(Check(mid,i)) r=mid;
else l=mid+1;
}
int ans=0;
std::sort(p+1,p+1+n);
for(int i=2; i<=n; ++i)
if(p[i].col!=p[i-1].col)
{
ans=p[i-1].pos+1;
break;
}
// for(int i=1; i<=n; ++i) printf("%d:%d\n",p[i].col,p[i].pos);
if(ans!=0) printf("9 %d 11 %d\n",ans-1,ans), fflush(stdout);
else printf("9 %d 11 %d\n",ans,ans), fflush(stdout); return 0;
}

Codeforces Round #516 (Div. 2) (A~E)的更多相关文章

  1. Codeforces Round &num;516 &lpar;Div&period; 2)D&period; Labyrinth&lpar;BFS&rpar;

    题目链接:http://codeforces.com/contest/1064/problem/D 题目大意:给你一个n*m的图,图中包含两种符号,'.'表示可以行走,'*'表示障碍物不能行走,规定最 ...

  2. Codeforces Round &num;516 &lpar;Div&period; 2&comma; by Moscow Team Olympiad&rpar; D&period; Labyrinth

    http://codeforces.com/contest/1064/problem/D 向上/向下加0,向左/右加1, step = 0,1,…… 求的是最少的步数,所以使用bfs. step=k ...

  3. Codeforces Round &num;516 &lpar;Div&period; 2&comma; by Moscow Team Olympiad&rpar; D&period; Labyrinth(重识搜索)

    https://codeforces.com/contest/1064/problem/D 题意 给你一个有障碍的图,限制你向左向右走的次数,问你可以到达格子的个数 思路 可以定义状态为vi[x][y ...

  4. Codeforces Round &num;516 &lpar;Div&period; 2)D&period; Labyrinth

    D. Labyrinth 题目链接:https://codeforces.com/contest/1064/problem/D 题意: 给出一个n*m的矩阵以及人物的起点,并且给出x,y,分别代表这个 ...

  5. Codeforces Round &num;516 &lpar;Div&period; 2&comma; by Moscow Team Olympiad&rpar;

    题目链接 A. Make a triangle! 题意 让某段最少增加多少使得构成三角形 思路 让较小两段往最长段去凑 代码 #include <bits/stdc++.h> #defin ...

  6. Codeforces Round &num;516&lpar;Div 2&rpar;

    比赛链接:传送门 A. Make a triangle!(简单思维) 题目大意: 给你三条边,问你最多加多少长度能使这三条边能构成三角形. 思路: 最大边小于答案加另外两条边的和. #include ...

  7. Codeforces Round&num;516 Div&period;1 翻车记

    A:开场懵逼.然后发现有人1min过,于是就sort了一下,于是就过了.正经证明的话,考虑回文串两端点一定是相同的,所以最多有Σcnti*(cnti+1)/2个,cnti为第i种字母出现次数.而sor ...

  8. &lbrack;Codeforces Round &num;516 &lpar;Div&period; 2&comma; by Moscow Team Olympiad&rpar; &rsqb;&lpar;A~E&rpar;

    A: 题目大意:给你$a,b,c$三条边,可以给任意的边加任意的长度,求最少共加多少长度使得可以构成三角形 题解:排个序,若可以组成,输出$0$,否则输出$c-a-b+1(设a\leqslant b\ ...

  9. Codeforces Round &num;366 &lpar;Div&period; 2&rpar; ABC

    Codeforces Round #366 (Div. 2) A I hate that I love that I hate it水题 #I hate that I love that I hate ...

随机推荐

  1. HDFS的Java操作

    实验环境: Windows 10 Eclipse Mars.2 Release (4.5.2) CentOS 7 Hadoop-2.7.3 先决条件: 1) Windows上各环境变量已配置OK.   ...

  2. Linux I2C总线控制器驱动&lpar;S3C2440&rpar;

    s3c2440的i2c控制器驱动(精简DIY),直接上代码,注释很详细: #include <linux/kernel.h> #include <linux/module.h> ...

  3. C&num; DevExpress&lowbar;gridControl 行号行样式

    #region 行号 /// <summary> /// 行号 /// </summary> /// <param name="sender"> ...

  4. BOM头的来源

    类似WINDOWS自带的记事本等软件,在保存一个以UTF-8编码的文件时,会在文件开始的地方插入三个不可见的字符(0xEF 0xBB 0xBF,即BOM).它是一串隐藏的字符,用于让记事本等编辑器识别 ...

  5. 选择符优先级-----&colon;link伪类

    问题:请指出以下结构中,A标签内的字体颜色. <style> a{ color:#ccc}/* 灰色 */ .alink a{color:#F60}/* 橙色 */ h1 a{color: ...

  6. 跨平台渲染框架尝试 - GPU Buffer的管理(1)

    buffer资源 下面来谈谈buffer的管理.buffer资源从广义上就是C语言的数组.如下图所示. 图 buffer的广义模型 在渲染管线中,无论是opengl还是dx或者其他的渲染api,都会提 ...

  7. 解决 Visual Studio 点击添加引用无反应的问题

    如遇到vs2010 点击添加引用无反应,主要是因为windows系统推送的更新问题,把windows系统推送的更新都更新一遍就好了. 如果已经安装VS后 Windows系统推荐的更新.360推荐的安全 ...

  8. H5和CSS

    参考文档:https://blog.csdn.net/caseywei/article/details/81105544 *)DOCTYPE的作用 如:<!DOCTYPE html>  标 ...

  9. 【maven】依赖、继承、聚合

    依赖: <dependency> <groupId>junit</groupId> <artifactId>junit</artifactId&g ...

  10. docker local registry server gave HTTP response to HTTPS client

    server gave HTTP response to HTTPS client报错是在insecure_registry中加入了http前缀,如果本地registry不是https的 就不要加任何 ...