- 浏览: 317081 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
xialluyouyue:
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294:
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412:
su1216 写道竖线代表或者,不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216:
竖线代表或者,不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu:
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
KIDx 的解题报告
题目链接:http://codeforces.com/contest/136
以下省略头文件
前三题是超级水题,不解释;后两题是很不错的水题,详细解释
A题
#include <iostream>
using namespace std;
#define M 105
int pre[M];
int main()
{
int n, i, x;
while (~scanf ("%d", &n))
{
for (i = 1; i <= n; i++)
scanf ("%d", &x), pre[x] = i;
for (i = 1; i < n; i++)
printf ("%d ", pre[i]);
printf ("%d\n", pre[i]);
}
return 0;
}
B题
#include <iostream>
#include <cmath>
using namespace std;
#define M 105
int a[M], c[M], b[M];
int main()
{
int x, y, k, n, maxs, res, i;
while (~scanf ("%d%d", &x, &y))
{
memset (a, 0, sizeof(a));
memset (c, 0, sizeof(c));
k = 0;
while (x)
{
a[k++] = x % 3;
x /= 3;
}
n = 0;
while (y)
{
c[n++] = y % 3;
y /= 3;
}
maxs = max (n, k);
res = 0;
for (i = 0; i < maxs; i++)
{
if (c[i] >= a[i])
b[i] = c[i] - a[i];
else b[i] = c[i] + 3 - a[i];
res += b[i] * pow (3.0, i);
}
printf ("%d\n", res);
}
return 0;
}
C题
#include <iostream>
#include <algorithm>
using namespace std;
#define M 100005
int a[M];
int main()
{
int n, i;
while (~scanf ("%d", &n))
{
for (i = 0; i < n; i++)
scanf ("%d", a+i);
sort (a, a+n);
if (a[n-1] == 1) //注意一下全部是1的情况即可
a[n-1] = 2;
else a[n-1] = 1, sort (a, a+n);
printf ("%d", a[0]);
for (i = 1; i < n; i++)
printf (" %d", a[i]);
printf ("\n");
}
return 0;
}
D题
#include <iostream> #include <algorithm> #include <cmath> using namespace std; #define eps 1e-8 #define M 10 struct point{ double x, y; }p[M], tp[M]; double dist (point a, point b) { return sqrt ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); } double dianmulti (point a, point b, point c) //求ab与bc的点积 { double x1 = b.x - a.x; double y1 = b.y - a.y; double x2 = c.x - b.x; double y2 = c.y - b.y; return x1*x2+y1*y2; } int main() { int i, j, k, l, ind, q, v, ed, mid, snum[M], ans; bool hash[M]; double maxs, a[5]; while (~scanf ("%lf%lf", &p[0].x, &p[0].y)) { for (i = 1; i < 8; i++) scanf ("%lf%lf", &p[i].x, &p[i].y); memset (hash, false, sizeof(hash)); for (i = 0; i < 8; i++) { for (j = i + 1; j < 8; j++) { for (k = j + 1; k < 8; k++) { for (l = k + 1; l < 8; l++) { ind = ans = 0; tp[ind++] = p[i]; tp[ind++] = p[j]; tp[ind++] = p[k]; tp[ind++] = p[l]; //tp存放四边形的点 snum[ans++] = i + 1; snum[ans++] = j + 1; snum[ans++] = k + 1; snum[ans++] = l + 1; //记录组成四边形的点的编号 maxs = 0; for (q = 1; q < ind; q++) { //找出v使得tp[0],tp[v]组成对角线 double dis = dist (tp[0], tp[q]); if (dis > maxs) maxs = dis, v = q; } ed = 0; for (q = 1; q < ind; q++) { if (q != v) { //找出四边形边长 a[ed++] = dist (tp[0], tp[q]); a[ed++] = dist (tp[v], tp[q]); } } if (fabs (a[0]-a[1]) < eps && fabs (a[0]-a[2]) < eps && fabs (a[0]-a[3]) < eps) { //判正方形四条边相等 for (q = 1; q < ind; q++) { if (q != v) { mid = q; //tp[mid]是不同于tp[0],tp[v]的点 break; } } if (fabs (dianmulti (tp[0], tp[mid], tp[v])) < eps) { //点积判0->mid是否垂直于mid->v //来到这里,说明i,j,k,l可以组成正方形 //以下基本上同理了! ind = 0; for (q = 0; q < 8; q++) { //找到非正方形的点存放到tp if (q != i && q != j && q != k && q != l) tp[ind++] = p[q]; } maxs = 0; for (q = 1; q < ind; q++) { double dis = dist (tp[0], tp[q]); if (dis > maxs) maxs = dis, v = q; } ed = 0; for (q = 1; q < ind; q++) { if (q != v) { a[ed++] = dist (tp[0], tp[q]); a[ed++] = dist (tp[v], tp[q]); } } sort (a, a+ed); //排序方便判对边相等 if (fabs (a[0]-a[1]) < eps && fabs (a[2]-a[3]) < eps) { //判长方形对边相等 for (q = 1; q < ind; q++) { if (q != v) { mid = q; break; } } if (fabs (dianmulti (tp[0], tp[mid], tp[v])) < eps) goto end;//到这里,说明另外4点可以组成长方形 } } } } } } } puts ("NO"); continue; end:; puts ("YES"); for (i = 0; i < ans - 1; i++) printf ("%d ", snum[i]), hash[snum[i]] = true; printf ("%d\n", snum[i]), hash[snum[i]] = true; ans = 0; for (i = 1; i <= 8; i++) { if (!hash[i]) snum[ans++] = i; //找出不是组成正方形的点 } for (i = 0; i < ans - 1; i++) //再次输出 printf ("%d ", snum[i]); printf ("%d\n", snum[i]); } return 0; }
E题
思路:
设0的个数为n0,1的个数为n1,遇到?也会有n0++,n1++,因为0,1的个数完全可能由?构成
设w为?的个数
因为答案只有4种情况(00,01,10,11),只要分别想办法试着构造即可
①n0 > len-n0 (0的个数>1的个数)即必然可以构造出"00"
②n1 > len-n1+1 (1的个数>0的个数+1)必然可以构造出"11"
③除了①②情况外只剩下两种情况:
1.a个1,a个0(如果n0<=n1&&n0>=len/2则有可能出现此情况):
按照游戏程序,必然要删掉a-1个1,a-1个0
2.a+1个1,a个0(n0>n1&&n1>=(len+1)/2……):
按照游戏程序,必然要删掉a个1,a-1个0
即最后必然只剩下一个1,一个0
所以最后一个字符显然是不会被删掉的
那么
如果最后一个字符是1,显然答案01是可构造的
如果最后一个字符是0,显然10是可构造的
如果最后一个字符是?,则需分类讨论:
1.设?=1,则对于当前n0--,n1不变,然后再用上面绿色条件判定
2.设?=0,则对于当前n1--,n0不变,然后同理
#include <iostream> using namespace std; #define M 100005 char s[M]; int main() { int i, len, n0, n1, w; while (~scanf ("%s", s)) { len = strlen (s); n0 = n1 = w = 0; for (i = 0; i < len; i++) { if (s[i] == '?') n0++, n1++, w++; if (s[i] == '0') n0++; if (s[i] == '1') n1++; } if (n0 > len-n0) puts ("00"); if (n0 <= n1 && n0 >= len/2 || n0 > n1 && n1 >= (len+1)/2) { if (s[len-1] == '0') puts ("10"); else if (s[len-1] == '1') puts ("01"); else //如果最后是?, 根据条件构造 { if (n0-1 <= n1 && (n0-1) >= len/2 || n0-1 > n1 && n1 >= (len+1)/2) puts ("01"); if (n0 <= n1-1 && n0 >= len/2 || n0 > n1-1 && (n1-1) >= (len+1)/2) puts ("10"); } } if (n1 - (len-n1) > 1) puts ("11"); } return 0; }
发表评论
-
hdu 4170 Supply Mission
2012-09-22 10:03 1279KIDx的解题报告 ... -
UVA 10202 + HDU 1270 小希的数表
2012-09-15 20:01 2759KIDx的解题报告 题目链接:http://ac ... -
HDU 1979 Fill the blanks
2012-08-20 12:40 1129KIDx的解题报告 题目链接:http://ac ... -
【数学】HDU 1719 Friend
2012-03-02 16:44 1208KIDx的解题报告 好久没写博客了,来题数学提提神 ... -
【BKDR_hash】HDU 2648 Shopping
2011-12-10 19:35 1828KIDx 的解题报告 题目链接:http://acm. ... -
Codeforces Beta Round #96 (Div. 2)【完整题解】
2011-12-06 17:03 1478KIDx 的解题报告 题目链接:http://codeforc ... -
2011 ACM/ICPC 北京赛区现场赛 B题(hdu 4082)
2011-11-12 14:15 2115KIDx 的解题报告 题目链接:http://acm.hdu. ... -
Codeforces Beta Round #4 (Div. 2 Only) 【完整题解】
2011-11-08 00:33 1429KIDx 的解题报告 http://codeforces.c ... -
Codeforces Beta Round #1【完整题解】
2011-11-05 15:54 1608KIDx 的解题报告 http://codeforces.c ... -
大连2011ACM网络赛【5道水题总结】……很黄很暴力
2011-09-04 18:04 2590KIDx 的解题报告 http://acm.hdu.ed ... -
【超级hash大法】HDU 1496 Equations
2011-08-10 21:21 3281http://acm.hdu.edu.cn/showprobl ... -
【矩阵乘法+快速取幂模】HDU 1575 Tr A
2011-08-15 14:54 1593http://acm.hdu.edu.cn/showprobl ... -
【TMD的陷阱题】HDU 2143 box
2011-07-28 20:42 1475http://acm.hdu.edu.cn/showprobl ... -
HDU 2072 单词数
2011-07-23 18:31 1295http://acm.hdu.edu.cn/showprobl ... -
【让我悲催的水题】HDU 1070 Milk
2011-07-17 07:38 1630http://acm.hdu.edu.cn/showprobl ... -
POJ 2271 HTML
2011-06-05 09:54 1105http://poj.org/problem?id=2271 ... -
HDU_2096_小明A+B
2011-05-22 08:08 2605http://acm.hdu.edu.cn/showprobl ... -
POJ_1002_487-3279
2011-05-19 09:49 1000http://poj.org/problem?id=1002 ...
相关推荐
Codeforces Round #723 (Div. 2).md
### Codeforces Round 961 (Div. 2):深度解析与实战技巧 #### 引言 Codeforces 是一个国际知名的在线编程竞赛平台,它汇聚了来自世界各地的编程爱好者和专业人士。每一轮比赛都旨在测试参赛者的算法思维、编程...
codeforces round 961 (div. 2)
传送门 题意: 开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include ...typedef long long l
就是把所有相等的数放到一个vector里,如果他出现大于2次,看最远的间距是否大于2即可,找到一个就可以 代码: #include #include #include #include #include #include #include #include #include #include #...
### Codeforces Round 961 (Div. 2) A题解析 #### 题目背景 Codeforces Round 961 (Div. 2) 是一场针对中级水平程序员的编程竞赛,通常会包含几个不同难度级别的题目。A题作为入门级题目,旨在测试参赛者的基础算法...
codeforces round 962 (div. 3)tion-ma笔记
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
Codeforces Round 962 (Div. 3) 是一场编程竞赛,其中包含了多个编程题目,每个题目都有其独特的挑战和解题思路。以下是对该竞赛中部分题目的简要介绍及解题思路概述: A题: Legs 题意: 一只鸡有2条腿,一头奶牛有...
Codeforces Round 962 (Div. 3) 是一场编程竞赛,旨在测试参赛者在算法和数据结构方面的能力。由于篇幅限制,我将对这场竞赛中的几个关键问题进行详细解析,但请注意,由于具体实现细节可能因题目而异,且无法在此...
E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...
### Codeforces Round #627 (Div. 3) D. Pair of Topics(二分,思维) #### 题目背景与概述 本题目来自Codeforces Round #627 (Div. 3),编号为D的题目“Pair of Topics”,这是一道结合了二分搜索与逻辑思维的...
题目链接:B. Longest Palindrome 题目 Returning back to problem solving, Gildong is now studying about palindromes. He learned that a palindrome is a string that is the same as its reverse....
题目“Anu Has a Function”源自Codeforces Round #618 (Div. 2)的一道竞赛编程问题,主要涉及进制转换、位运算和贪心算法。问题要求定义一个函数f(x, y) = (x | y) - y,并对数组进行排序,以最大化最后的结果。 ...
给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。其他边从最大点开始赋值。 证明:一...
标题中的"Codeforces Round #629 (Div. 3) E – Tree Queries dfs序判祖先关系"指的是一场编程竞赛中的问题,涉及到树结构的查询和深度优先搜索(DFS)来判断节点间的祖先关系。这个问题的目标是设计算法来确定在...
A~G
B. Longest Palindrome time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Returning back to problem solving, Gildong is now studying about ...
题解:6nlogn,先sort三个数组a,b,c, 六次枚举二分查找,再每次min找最小值,例如:先固定数组a,再在数组b,c中利用lower_bound找到第一个大于等于a[i]的数, #pragma GCC optimize(2) #include #define ll long long...