Codeforces Round #403 (Div. 2, based on Technocup 2017 Finals)

时间:2022-03-03 09:57:50

Codeforces Round #403 (Div. 2, based on Technocup 2017 Finals)


说一点东西:

昨天晚上$9:05$开始太不好了,我在学校学校$9:40$放学我呆到十点然后还要跑回家耽误时间....要不然$D$题就写完了

周末一些成绩好的同学单独在艺术楼上课然后晚上下第一节晚自习和他们在回廊里玩开灯之后再关上一片漆黑真好玩


A.Andryusha and Socks

日常煞笔提.....我竟然$WA$了一次忘了$n<<1$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=2e5+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,a,vis[N],now,ans;
int main(){
//freopen("in","r",stdin);
n=read()<<;
for(int i=;i<=n;i++){
a=read();
if(!vis[a]) now++,vis[a]=;
else now--;
ans=max(ans,now);
}
printf("%d",ans);
}



B.The Meeting Place Cannot Be Changed

题意:数轴上$n$个点告诉你每个点坐标和移动速度,找一个点使得所有点都到那个点时间最短,求最短时间

各种加权平均没搞过去,最后急了我这是信息学竞赛不是数学竞赛不是物理竞赛,二分答案水过去...

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=6e4+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n;
double x[N],v[N];
bool check(double g){
double l=,r=1e9;
for(int i=;i<=n;i++) l=max(l,x[i]-g*v[i]),r=min(r,x[i]+g*v[i]);
return l<=r;
}
int main(){
//freopen("in","r",stdin);
n=read();
for(int i=;i<=n;i++) x[i]=read();
for(int i=;i<=n;i++) v[i]=read();
double l=,r=1e9;
double eps=1e-;
while(r-l>eps){
double mid=(l+r)/;
if(check(mid)) r=mid;
else l=mid;
}
printf("%lf",l);
}



C.Andryusha and Colored Balloons

题意:一棵树,$a--b--c$这样的三个点不能是相同颜色,求染色最少用几种颜色,并输出一个方案

一眼看出与同一个点相连的颜色不同,最大度数$+1$就行了

然后被构造方案卡住了.....

想记录每个点的相邻点的颜色集合感觉会被菊花图卡(为什么别人都几百ms我77ms)

于是发现对于一个点除了父亲和自己颜色不是从小到大其他都可以从小到大分配,记录一下一个点分配到哪里遇到自己和父亲跳过就行了

MD想了好长时间

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=2e5+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,de[N],u,v;
struct edge{
int v,ne;
}e[N<<];
int h[N],cnt;
inline void ins(int u,int v){
cnt++;
e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
cnt++;
e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;
}
int ans,col[N],fa[N],now[N];
void dfs(int u){
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(v==fa[u]) continue;
fa[v]=u;
now[u]++;
while(now[u]==col[u]||now[u]==col[fa[u]]) now[u]++;
col[v]=now[u];
dfs(v);
}
}
int main(){
//freopen("in","r",stdin);
n=read();
for(int i=;i<n;i++) u=read(),v=read(),de[u]++,de[v]++,ins(u,v);
for(int i=;i<=n;i++) ans=max(ans,de[i]+);
printf("%d\n",ans);
fa[]=;col[]=;
dfs();
for(int i=;i<=n;i++) printf("%d ",col[i]);
}



D.Innokenty and a Football League

题意:

队伍$i$有两种候选名字$a_i\ b_i$,选了$b_i$的话不能有其他队伍$j$选了$a_j\:a_i==a_j$

每个队伍名字不能相同,求一个方案


发现有相同$a$的队伍只能选$b$,先处理这些

$a$唯一的队伍任意选,只要满足没有两只队伍选一样就行了,我建了个网络流.....

$s \rightarrow team \rightarrow name_a,name_b \rightarrow t$

容量都为$1$

(好像只有$Candy?$这个沙茶用了这么$zz$的做法)

然后比赛结束好没写完,后来又发现好多细节问题:

$1.$先把$a$唯一的队伍中那些已经被不唯一的选过的名字处理掉不要建到图里去

$2.$一个名字只能往$t$连一条边,所以判断一下$builded$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
const int N=,M=1e5+,INF=1e9;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,a[N],b[N],m;
char str[];
int has[M],c[M]; int s,t;
struct edge{
int v,c,f,ne;
}e[M<<];
int cnt,h[N];
inline void ins(int u,int v,int c){
cnt++;
e[cnt].v=v;e[cnt].c=c;e[cnt].f=;e[cnt].ne=h[u];h[u]=cnt;
cnt++;
e[cnt].v=u;e[cnt].c=;e[cnt].f=;e[cnt].ne=h[v];h[v]=cnt;
}
int cur[N],d[N],vis[N];
int q[N],head,tail;
bool bfs(){
head=tail=;
memset(vis,,sizeof(vis));
d[s]=;vis[s]=;q[tail++]=s;
while(head!=tail){
int u=q[head++];
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(!vis[v]&&e[i].c>e[i].f){
vis[v]=;d[v]=d[u]+;
q[tail++]=v;
if(v==t) return true;
}
}
}
return false;
}
int dfs(int u,int a){
if(u==t||a==) return a;
int flow=,f;
for(int &i=cur[u];i;i=e[i].ne){
int v=e[i].v;
if(d[v]==d[u]+&&(f=dfs(v,min(e[i].c-e[i].f,a)))>){
flow+=f;
e[i].f+=f;
e[((i-)^)+].f-=f;
a-=f;
if(a==) break;
}
}
if(a) d[u]=-;
return flow;
}
int dinic(){
int flow=;
while(bfs()){
for(int i=s;i<=t;i++) cur[i]=h[i];
flow+=dfs(s,INF);
}
return flow;
} int id[M],tot;
string ss[M];
int choose[N];
int builded[N];
int main(){
//freopen("in","r",stdin);
n=read();
for(int i=;i<=n;i++){
scanf("%s",str);
int x=str[]-'A'+,y=str[]-'A'+,z=str[]-'A'+;
a[i]=x**+y*+z;
has[a[i]]++;
ss[a[i]]=string(str,); scanf("%s",str);
z=str[]-'A'+;
b[i]=x**+y*+z;
ss[b[i]]=ss[a[i]];ss[b[i]][]=str[]; m=max(m,max(a[i],b[i]));
//printf("hi %d %d ",a[i],b[i]);cout<<ss[a[i]]<<" "<<ss[b[i]]<<endl;
}
for(int i=;i<=n;i++) if(has[a[i]]>){
c[b[i]]++,choose[i]=b[i];
if(c[b[i]]>) {puts("NO");return ;}
} tot=n;
for(int i=;i<=n;i++) if(has[a[i]]==){
if(!id[a[i]]&&c[a[i]]==) id[a[i]]=++tot;
if(!id[b[i]]&&c[b[i]]==) id[b[i]]=++tot;
}
s=;t=tot+;
int sum=;
for(int i=;i<=n;i++) if(has[a[i]]==){
sum++;
ins(s,i,);
if(id[a[i]]){
int x=id[a[i]];
ins(i,x,);
if(!builded[x]) ins(x,t,),builded[x]=;
}
if(id[b[i]]){
int x=id[b[i]];
ins(i,x,);
if(!builded[x]) ins(x,t,),builded[x]=;
}
}
int flow=dinic();
if(flow!=sum){puts("NO");return ;} puts("YES"); for(int u=;u<=n;u++) if(has[a[u]]==){
for(int i=h[u];i;i=e[i].ne) if(e[i].f==){
if(e[i].v==id[a[u]]) choose[u]=a[u];
if(e[i].v==id[b[u]]) choose[u]=b[u];
}
} //for(int i=1;i<=n;i++) printf("choose %d %d %d\n",i,choose[i],1);
for(int i=;i<=n;i++) cout<<ss[choose[i]]<<'\n';
}

然后从__stdcall(我发现这个名字有毒卡latex)和$zyf2000$哪里看到$2SAT$做法

1、第一种相同,那么必须都选第二种 2、第二种相同,不能同时选第二种 3、第一种和第二种相同,不能同时选第一种和第二种




E.Underground Lab

题意:

$n$点$m$边找$k$条路径每个点至少覆盖一次,每条路径长度$\le \lceil \frac{2n}{k}\rceil$


赛后补提...

直接搞一个既不是$dfs$序也不是欧拉序列的$dfs$序列,访问完一个孩子就把父亲加入序列,序列长度不会超过$2*n$因为一个点最多给父亲贡献一次

然后第$7$个点貌似整除了$WA$了几次....又改了一个输出方式才过

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=4e5+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,k;
struct edge{
int v,ne;
}e[N<<];
int h[N],cnt;
inline void ins(int u,int v){
cnt++;
e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
cnt++;
e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;
}
int vis[N];
int a[N<<],p;
void dfs(int u){
vis[u]=;
a[++p]=u;
for(int i=h[u];i;i=e[i].ne)
if(!vis[e[i].v]) dfs(e[i].v),a[++p]=u;
}
int main(){
//freopen("in","r",stdin);
n=read();m=read();k=read();
for(int i=;i<=m;i++) ins(read(),read());
dfs();
int c=ceil((double)*n/k);
int x=p/c,y=p%c,now=;
for(int i=;i<=k;i++){
if(i<=x){
printf("%d ",c);
for(int j=i;j<=i+c-;j++) printf("%d ",a[++now]);
}else if(i==x+&&y!=){
printf("%d ",y);
for(int j=;j<=y;j++) printf("%d ",a[++now]);
}else printf("1 1");
puts("");
}
return ;
}

F.http://www.cnblogs.com/candy99/p/6511222.html

Codeforces Round #403 (Div. 2, based on Technocup 2017 Finals)的更多相关文章

  1. Codeforces Round &num;403 &lpar;Div&period; 2&comma; based on Technocup 2017 Finals&rpar; D&period; Innokenty and a Football League

    地址:http://codeforces.com/contest/782/problem/D 题目: D. Innokenty and a Football League time limit per ...

  2. 树的性质和dfs的性质 Codeforces Round &num;403 &lpar;Div&period; 2&comma; based on Technocup 2017 Finals&rpar; E

    http://codeforces.com/contest/782/problem/E 题目大意: 有n个节点,m条边,k个人,k个人中每个人都可以从任意起点开始走(2*n)/k步,且这个步数是向上取 ...

  3. 2-sat Codeforces Round &num;403 &lpar;Div&period; 2&comma; based on Technocup 2017 Finals&rpar; D

    http://codeforces.com/contest/782/problem/D 题意: 每个队有两种队名,问有没有满足以下两个条件的命名方法: ①任意两个队的名字不相同. ②若某个队 A 选用 ...

  4. Codeforces Round &num;403 &lpar;Div&period; 2&comma; based on Technocup 2017 Finals&rpar; E Underground Lab

    地址:http://codeforces.com/contest/782/problem/E 题目: E. Underground Lab time limit per test 1 second m ...

  5. Codeforces Round &num;403 &lpar;Div&period; 2&comma; based on Technocup 2017 Finals&rpar; C Andryusha and Colored Balloons

    地址:http://codeforces.com/contest/782/problem/C 题目: C. Andryusha and Colored Balloons time limit per ...

  6. Codeforces Round &num;403 &lpar;Div&period; 2&comma; based on Technocup 2017 Finals&rpar; B&period; The Meeting Place Cannot Be Changed

    地址:http://codeforces.com/contest/782/problem/B 题目: B. The Meeting Place Cannot Be Changed time limit ...

  7. Codeforces Round &num;403 &lpar;Div&period; 2&comma; based on Technocup 2017 Finals&rpar; A&period; Andryusha and Socks

    地址:http://codeforces.com/contest/782/problem/A 题目: A. Andryusha and Socks time limit per test 2 seco ...

  8. Codeforces Round &num;403 &lpar;Div&period; 2&comma; based on Technocup 2017 Finals&rpar;A模拟 B三分 C dfs D map

    A. Andryusha and Socks time limit per test 2 seconds memory limit per test 256 megabytes input stand ...

  9. Codeforces Round &num;403 &lpar;Div&period; 2&comma; based on Technocup 2017 Finals )D&period; Innokenty and a Football League(2-sat)

    D. Innokenty and a Football League time limit per test 2 seconds memory limit per test 256 megabytes ...

随机推荐

  1. popupwindow的基本使用以及基本动画效果

    1.创建一个popupwindow view的布局文件自己写一个就好了,这里就不说了 View view= LayoutInflater.from(context).inflate(R.layout. ...

  2. js数组中indexOf&sol;filter&sol;forEach&sol;map&sol;reduce详解

    今天在网上看到一篇帖子,如题: 出处:前端开发博客 (http://caibaojian.com/5-array-methods.html) 在ES5中一共有9个Array方法,分别是: Array. ...

  3. 首届Ignite China微软技术大会见闻

    10.26-10.28,有幸参加微软在中国北京举办的首届Ignite China技术大会.世界那么大,技术那么多,我想去看看. 为期三天的技术大会在小汤山九华山庄举办,吐槽一下,太特么远了,每天要跑3 ...

  4. 找出现有Vector或ArrayList或数组中重复的元素&amp&semi;给现有Vector或ArrayList或数组去重

    //直接上代码: public static void main(String[] args) { List<Integer> list = new Vector<Integer&g ...

  5. IE6 背景透明

    IE6 背景透明 第 1 种方法:定义一个样式,给某个div应用这个样式后,div的透明png背景图片自动透明了.(注意两处图片的路径写法不一样,本例中,icon_home.png图片与html文件在 ...

  6. &lpar;数学 尾0的个数&rpar; 51nod1003 阶乘后面0的数量

    n的阶乘后面有多少个0? 6的阶乘 = 1*2*3*4*5*6 = 720,720后面有1个0. 收起   输入 一个数N(1 <= N <= 10^9) 输出 输出0的数量 输入样例 5 ...

  7. ModelState&period;IsValid always returning true while mocking a request

    ASB.net  MVC 视图验证里有一个IValidatableObject接口.这里面有一个验证方法.通常我们表单提交的时候dto就是用一个实现IValidatableObject这个接口的实体. ...

  8. 撩课-Web大前端每天5道面试题-Day2

    1.伪类与伪元素的区别? 1) 定义区别 伪类 伪类用于选择DOM树之外的信息,或是不能用简单选择器进行表示的信息. 前者包含那些匹配指定状态的元素,比如:visited,:active:后者包含那些 ...

  9. mavan下scala编译中文乱码的问题&period;以及内存溢出问题解决

    网上都没有找到我这个问题.都是自己解决的.也不知道后来者能不能遇到 关键字: java.lang.*Error scala not found scala <config ...

  10. 学习动态性能表&lpar;20&rpar;--v&dollar;waitstat

    学习动态性能表 第20篇--V$WAITSTAT  2007.6.15 本视图保持自实例启动所有的等待事件统计信息.常用于当你发现系统存在大量的"buffer busy waits&quot ...