Codeforces Round #383 (Div. 2) 解题报告

时间:2022-09-03 19:15:01

  本来是打算所有半夜进行的CF都不参加的,但看到这次比赛22:35就开始,还是没有忍住orz……晚上总是不够清醒,做题思维不如白天活跃,低级错误常常出现。出的比较早的C因为一个书写错误有点小bug,在比赛快结束时被hack,还好一下子就发现改正了过来,b题很水,却刚开始没想到合适的做法,也卡了比较久。D题因为刚学到DP,还很不熟练,比赛前没能写完。整体来说这一场实在是表现的菜的一塌糊涂。不过因为现在rating低,还在神奇的上分,算是一点慰藉了。

A

题目地址

简要题意:

  输入一个整数n,输出1378的n次方的个位数。

思路分析:

  只要看8的n次方个位数是多少。显然是有循环节的,写几项发现循环节为4,所以只需要看n模4余几,注意n=0时要特殊判断一下,任何非0数的0次方都是1.

参考代码:

  

 #include<stdio.h>
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
int n;
scanf("%d",&n);
if(n==)
{
printf("1\n");
}
else if(n%==)
{
printf("8\n");
}
else if(n%==)
{
printf("4\n");
}
else if(n%==)
{
printf("2\n");
}
else if(n%==)
{
printf("6\n");
}
return ;
}

B

题目地址

简要题意:

  给若干数,要求判断这些这些数有多少对异或值为给定的另一个数。(每一对顺序固定,按给定时的顺序)

思路分析:

  注意到x^y=z则x^z=y。利用此,建立数组记录每个数出现的次数,因为每一对顺序固定,对于一个数x,只需看出现在x之前的(x^“目标数”)出现了多少次,就多形成了多少对。注意异或值可能会比给出的数的范围大,所以把数组大小开大一点。

参考代码:

  

 #include<stdio.h>
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
const int INF=1e6+;
ll an=;
int ci[INF],n,mu,i,tem;
int main()
{
memset(ci,,sizeof(ci));
scanf("%d%d",&n,&mu);
for(i=;i<n;i++)
{
scanf("%d",&tem);
an+=ci[tem^mu];
ci[tem]++;
}
printf("%I64d\n",an);
return ;
}

C

题目地址

简要题意:

  一个有向图,每一个点有且只有一条出的线。求最小的n,使任意从一点走2n步之后就回到本身。

思路分析:

  显然,有向图中的每一点入度都需要恰为1,否则必然有入度为0的点,那么不管n取多少,从这点都走不回这一点。而当满足每一点入度都恰为1时就一定可以找到符合要求的n。只需要求所有形成的环的“长度”(如果长度为偶数2x,n取x即可走2x步就回到本身,所以用于计算的“长度”取值为x)的最小公倍数即可。

参考代码:

  

 #include<stdio.h>
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
int gcd(int x,int y)
{
while(x%y!=&&y%x!=)
{
if(y>x)
y=y%x;
else
x=x%y;
}
if(x%y==)
{
return y;
}
else
{
return x;
}
}
int main()
{
int n,a[],i,an=,len=,j,b[],cnt=;
bool vi[];
memset(vi,false,sizeof(vi));
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%d",&a[i]);
vi[a[i]]=true;
}
for(i=;i<=n;i++)
{
if(!vi[i])
{
printf("-1\n");
return ;
}
}
memset(vi,false,sizeof(vi));
for(i=;i<=n;i++)
{
len=;
if(!vi[i])
{
j=a[i];
len=;
while(j!=i)
{ vi[j]=true;
len++;
j=a[j];
}
b[cnt++]=len;
}
}
if(b[]%!=)
an=b[];
else
an=b[]/;
for(i=;i<cnt;i++)
{
if(b[i]%!=)
an*=(b[i]/gcd(an,b[i]));
else
an*=((b[i]/)/gcd(an,b[i]/));
}
printf("%d\n",an);
return ;
}

D

题目地址

简要题意:

  有若干人,,每个人有一个体重值和颜值,且若干人组成一组,这一组必须全取或取小于等于1个人。要找到一种总体重小于等于W,而颜值之和最大的选人办法。

思路分析:

  0、1背包,不同的是题目中的限制。只需要先根据题意把同一组的标记出来,这一组的每个人,和这一组的整体作为第i个可选物品进行0、1背包即可。

参考代码:

  

 #include<stdio.h>
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
#define num 1010
vector <int> group[num];
int pre[num],w[num],b[num],ww[num],bb[num],dp[num][num],cnt,fpre[num],org;
int n,m,W,i,l,r,an=;
int trimax(int x,int y,int z)
{
if(x>=y&&x>=z)
return x;
if(y>=x&&y>=z)
return y;
if(z>=x&&z>=y)
return z;
}
int trace (int s)
{
if(pre[s]==s)
return s;
else
return trace(pre[s]);
} int main()
{
scanf("%d%d%d",&n,&m,&W);
for(i=;i<=n;i++)
{
scanf("%d",&w[i]);
}
for(i=;i<=n;i++)
{
scanf("%d",&b[i]);
}
for(i=;i<=n;i++)
{
pre[i]=i;
}
for(i=;i<=m;i++)
{
scanf("%d%d",&l,&r);
if(trace(l)!=trace(r))
pre[trace(l)]=trace(r);
}
cnt=;
for(i=;i<=n;i++)
{
int st=-;
int org=trace(i);
int j;
for(j=;j<cnt;j++)
{
if(fpre[j]==org)
{
st=j;
break;
}
}
if(st==-)
{
ww[cnt]+=w[i];
bb[cnt]+=b[i];
group[cnt].push_back(i);
fpre[cnt++]=org;
}
else
{
ww[st]+=w[i];
bb[st]+=b[i];
group[st].push_back(i);
}
}
for(i=;i<cnt;i++)
{
for(int k=W;k>=;k--)
{
if(k>=ww[i])
dp[i][k]=trimax(dp[i][k],dp[i-][k],dp[i-][k-ww[i]]+bb[i]);
else
dp[i][k]=max(dp[i][k],dp[i-][k]);
}
for(int j=;j<group[i].size();j++)
{
for(int k=W;k>=;k--)
{
if(k>=w[group[i][j]])
dp[i][k]=trimax(dp[i][k],dp[i-][k],dp[i-][k-w[group[i][j]]]+b[group[i][j]]);
else
dp[i][k]=max(dp[i][k],dp[i-][k]);
}
}
}
for(i=;i<=W;i++)
if(dp[cnt-][i]>an)
an=dp[cnt-][i];
printf("%d\n",an);
return ;
}

E

题目地址

简要题意:

  n对情侣坐在一个圆桌上(情侣都是一男一女的,没有别的情况),给他们发两种食物,要求:

  1、一对情侣食物不同

  2、任意连续3个人,必须2种食物都出现

思路分析:

  大家初看可能觉得是二分图匹配,但其实并不是,只是一个普通的图随便整一下。

  下面是对必定有解的证明。

   2n个点的无向图 将1\2 3\4 …… 2n-1\2n 连线  再将一组的两点连线 这样组成的图只存在偶回路(若不然 存在2*k+1个点组成奇回路 将这2*k+1条边 编上号 为1——2*k+1 因为相邻的两边必定一个是 按之前的编号相邻点连线 另一个是 情侣点连线 从1出发 如果1是前者 那么2是后者…… 2*k+1是前者 矛盾 如果1是后者 同理矛盾 )故此图为二部图  可分为两个点集 U、V 将U中点赋为1 V中点赋为2 这样图中任意一条线两个端点颜色不同 任意连续3个点必存在一条连线 而连线两端点值不同 即证明了必定有解。
 #include<stdio.h>
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
const int N=;
vector <int> a[N];
int b[N],g[N];
int an[N];
bool vi[N];
void dfs(int x,int t)
{
vi[x]=true;an[x]=t;
for(int i:a[x])
{
if(!vi[i])
dfs(i,(t^));}
}
int main()
{
memset(vi,false,sizeof(vi));
int n,i;
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%d%d",&b[i],&g[i]);
a[b[i]].push_back(g[i]);
a[g[i]].push_back(b[i]);
}
for(i=;i<=n;i++)
{
a[*i-].push_back(*i);
a[*i].push_back(*i-);
}
for(i=;i<=*n;i++)
if(!vi[i])
dfs(i,);
for(i=;i<=n;i++)
printf("%d %d\n",an[b[i]]+,an[g[i]]+);
return ;
}

Codeforces Round #383 (Div. 2) 解题报告的更多相关文章

  1. Codeforces Round &num;324 &lpar;Div&period; 2&rpar;解题报告

    ---恢复内容开始--- Codeforces Round #324 (Div. 2) Problem A 题目大意:给二个数n.t,求一个n位数能够被t整除,存在多组解时输出任意一组,不存在时输出“ ...

  2. Codeforces Round &num;382 &lpar;Div&period; 2&rpar; 解题报告

    CF一如既往在深夜举行,我也一如既往在周三上午的C++课上进行了virtual participation.这次div2的题目除了E题都水的一塌糊涂,参赛时的E题最后也没有几个参赛者AC,排名又成为了 ...

  3. Codeforces Round &num;380 &lpar;Div&period; 2&rpar; 解题报告

    第一次全程参加的CF比赛(虽然过了D题之后就开始干别的去了),人生第一次codeforces上分--(或许之前的比赛如果都参加全程也不会那么惨吧),终于回到了specialist的行列,感动~.虽然最 ...

  4. Codeforces Round &num;216 &lpar;Div&period; 2&rpar;解题报告

    又范低级错误! 只做了两题!一道还被HACK了,囧! A:看了很久!应该是到语文题: 代码:#include<iostream> #include<];    ,m2=;    ;i ...

  5. Codeforces Round &num;281 &lpar;Div&period; 2&rpar; 解题报告

    题目地址:http://codeforces.com/contest/493 A题 写完后就交了,然后WA了,又读了一遍题,没找出错误后就开始搞B题了,后来回头重做的时候才发现,球员被红牌罚下场后还可 ...

  6. Codeforces Round &num;277 &lpar;Div&period; 2&rpar; 解题报告

    题目地址:http://codeforces.com/contest/486 A题.Calculating Function 奇偶性判断,简单推导公式. #include<cstdio> ...

  7. Codeforces Round &num;276 &lpar;Div&period; 2&rpar; 解题报告

    题目地址:http://codeforces.com/contest/485 A题.Factory 模拟.判断是否出现循环,如果出现,肯定不可能. 代码: #include<cstdio> ...

  8. Codeforces Round &num;350 &lpar;Div&period; 2&rpar;解题报告

    codeforces 670A. Holidays 题目链接: http://codeforces.com/contest/670/problem/A 题意: A. Holidays On the p ...

  9. Codeforces Round &num;479 &lpar;Div&period; 3&rpar;解题报告

    题目链接: http://codeforces.com/contest/977 A. Wrong Subtraction 题意 给定一个数x,求n次操作输出.操作规则:10的倍数则除10,否则减1 直 ...

随机推荐

  1. Atitit&period;兼具兼容性和扩展性的配置方案attilax总结

    Atitit.兼具兼容性和扩展性的配置方案attilax总结 文件配置法1 Jdbc多数据源文件配置发1 Bat文件配置法1 改进的文件配置法(采用类似i18n技术) 推荐1 使用自动化pc_id的方 ...

  2. jQuery实现手机竖直手风琴效果

    效果:http://hovertree.com/texiao/jquery/65/ 效果图: 手机扫描二维码查看效果: 代码: <!doctype html> <html lang= ...

  3. No&period;007:Reverse Integer

    问题: Reverse digits of an integer.Example1:x = 123, return 321Example2:x = -123, return -321 官方难度: Ea ...

  4. amCharts图表中的JavaScript中文注释引起的浏览器兼容性问题

    近期用amCharts做图表.一切都很顺利,然后演示的时候掉链子了,平时开发的时候都是用的火狐和谷歌,加上这种图表框架本来就号称兼容性极好,也没有在ie上测试,演示的机器上恰巧用的是ie11,发现一个 ...

  5. Shell练习

    1   在终端下运行程序,首先清屏,然后提示:“Input a file or directory name, please!”.从键盘输入一个字符串(如:xxx),如果该字符串是目录,则显示:“xx ...

  6. as3commons-bytecode 获取所有类的一个BUG

    下载了这个swc,号称可以反射出所有加载的类.已经用在了spring. 可是一运行就报错,说bytearray.uncompress出错.操. 下载整个源码,单独加载as3commons-byteco ...

  7. Android Bundle、Handler和Message类介绍

    Bundle是一个载体,可以存放基本数据类型.对象等内容,相当于一辆汽车,可以装载很多东西,然后运到需要的地方,例如: Bundle mBundle=new Bundle(); mBundle.put ...

  8. &lbrack;Windows驱动&rsqb;驱动包&lpar;Driver Packages&rpar;

    在windows下安装一个驱动,我们你需要把所有需要的软件打包-称为驱动包.驱动包里包括系统提供的给所有设备类使用的一般安装工具,还包括了设备商提供的设备特定的组件.下面我们就来看看驱动包里具体需要哪 ...

  9. swift语言开发的一个游戏------熊猫跑酷(KongfuPanda)

    项目地址:https://github.com/jakciehoo/KongfuPanda 欢迎加QQ群:260558552.大家一起交流iOS开发,我们可以一起学习,我很想集结一些志同道合的朋友,一 ...

  10. 如何快速检查js语法学习Javascript

    这里给大家推荐一个快速进行语法检查的方法,可以发现绝大多数语法错误,也可以作为在线编辑器,提高编程效率. 地址:http://www.jslint.com/ 同时推荐一个在线学习Javascript的 ...