本来是打算所有半夜进行的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种食物都出现
思路分析:
大家初看可能觉得是二分图匹配,但其实并不是,只是一个普通的图随便整一下。
下面是对必定有解的证明。
#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) 解题报告的更多相关文章
-
Codeforces Round #324 (Div. 2)解题报告
---恢复内容开始--- Codeforces Round #324 (Div. 2) Problem A 题目大意:给二个数n.t,求一个n位数能够被t整除,存在多组解时输出任意一组,不存在时输出“ ...
-
Codeforces Round #382 (Div. 2) 解题报告
CF一如既往在深夜举行,我也一如既往在周三上午的C++课上进行了virtual participation.这次div2的题目除了E题都水的一塌糊涂,参赛时的E题最后也没有几个参赛者AC,排名又成为了 ...
-
Codeforces Round #380 (Div. 2) 解题报告
第一次全程参加的CF比赛(虽然过了D题之后就开始干别的去了),人生第一次codeforces上分--(或许之前的比赛如果都参加全程也不会那么惨吧),终于回到了specialist的行列,感动~.虽然最 ...
-
Codeforces Round #216 (Div. 2)解题报告
又范低级错误! 只做了两题!一道还被HACK了,囧! A:看了很久!应该是到语文题: 代码:#include<iostream> #include<]; ,m2=; ;i ...
-
Codeforces Round #281 (Div. 2) 解题报告
题目地址:http://codeforces.com/contest/493 A题 写完后就交了,然后WA了,又读了一遍题,没找出错误后就开始搞B题了,后来回头重做的时候才发现,球员被红牌罚下场后还可 ...
-
Codeforces Round #277 (Div. 2) 解题报告
题目地址:http://codeforces.com/contest/486 A题.Calculating Function 奇偶性判断,简单推导公式. #include<cstdio> ...
-
Codeforces Round #276 (Div. 2) 解题报告
题目地址:http://codeforces.com/contest/485 A题.Factory 模拟.判断是否出现循环,如果出现,肯定不可能. 代码: #include<cstdio> ...
-
Codeforces Round #350 (Div. 2)解题报告
codeforces 670A. Holidays 题目链接: http://codeforces.com/contest/670/problem/A 题意: A. Holidays On the p ...
-
Codeforces Round #479 (Div. 3)解题报告
题目链接: http://codeforces.com/contest/977 A. Wrong Subtraction 题意 给定一个数x,求n次操作输出.操作规则:10的倍数则除10,否则减1 直 ...
随机推荐
-
Atitit.兼具兼容性和扩展性的配置方案attilax总结
Atitit.兼具兼容性和扩展性的配置方案attilax总结 文件配置法1 Jdbc多数据源文件配置发1 Bat文件配置法1 改进的文件配置法(采用类似i18n技术) 推荐1 使用自动化pc_id的方 ...
-
jQuery实现手机竖直手风琴效果
效果:http://hovertree.com/texiao/jquery/65/ 效果图: 手机扫描二维码查看效果: 代码: <!doctype html> <html lang= ...
-
No.007:Reverse Integer
问题: Reverse digits of an integer.Example1:x = 123, return 321Example2:x = -123, return -321 官方难度: Ea ...
-
amCharts图表中的JavaScript中文注释引起的浏览器兼容性问题
近期用amCharts做图表.一切都很顺利,然后演示的时候掉链子了,平时开发的时候都是用的火狐和谷歌,加上这种图表框架本来就号称兼容性极好,也没有在ie上测试,演示的机器上恰巧用的是ie11,发现一个 ...
-
Shell练习
1 在终端下运行程序,首先清屏,然后提示:“Input a file or directory name, please!”.从键盘输入一个字符串(如:xxx),如果该字符串是目录,则显示:“xx ...
-
as3commons-bytecode 获取所有类的一个BUG
下载了这个swc,号称可以反射出所有加载的类.已经用在了spring. 可是一运行就报错,说bytearray.uncompress出错.操. 下载整个源码,单独加载as3commons-byteco ...
-
Android Bundle、Handler和Message类介绍
Bundle是一个载体,可以存放基本数据类型.对象等内容,相当于一辆汽车,可以装载很多东西,然后运到需要的地方,例如: Bundle mBundle=new Bundle(); mBundle.put ...
-
[Windows驱动]驱动包(Driver Packages)
在windows下安装一个驱动,我们你需要把所有需要的软件打包-称为驱动包.驱动包里包括系统提供的给所有设备类使用的一般安装工具,还包括了设备商提供的设备特定的组件.下面我们就来看看驱动包里具体需要哪 ...
-
swift语言开发的一个游戏------熊猫跑酷(KongfuPanda)
项目地址:https://github.com/jakciehoo/KongfuPanda 欢迎加QQ群:260558552.大家一起交流iOS开发,我们可以一起学习,我很想集结一些志同道合的朋友,一 ...
-
如何快速检查js语法学习Javascript
这里给大家推荐一个快速进行语法检查的方法,可以发现绝大多数语法错误,也可以作为在线编辑器,提高编程效率. 地址:http://www.jslint.com/ 同时推荐一个在线学习Javascript的 ...