- 浏览: 308700 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
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 1206KIDx的解题报告 ... -
UVA 10202 + HDU 1270 小希的数表
2012-09-15 20:01 2696KIDx的解题报告 题目链接:http://ac ... -
HDU 1979 Fill the blanks
2012-08-20 12:40 1076KIDx的解题报告 题目链接:http://ac ... -
【数学】HDU 1719 Friend
2012-03-02 16:44 1163KIDx的解题报告 好久没写博客了,来题数学提提神 ... -
【BKDR_hash】HDU 2648 Shopping
2011-12-10 19:35 1780KIDx 的解题报告 题目链接:http://acm. ... -
Codeforces Beta Round #96 (Div. 2)【完整题解】
2011-12-06 17:03 1444KIDx 的解题报告 题目链接:http://codeforc ... -
2011 ACM/ICPC 北京赛区现场赛 B题(hdu 4082)
2011-11-12 14:15 2065KIDx 的解题报告 题目链接:http://acm.hdu. ... -
Codeforces Beta Round #4 (Div. 2 Only) 【完整题解】
2011-11-08 00:33 1365KIDx 的解题报告 http://codeforces.c ... -
Codeforces Beta Round #1【完整题解】
2011-11-05 15:54 1554KIDx 的解题报告 http://codeforces.c ... -
大连2011ACM网络赛【5道水题总结】……很黄很暴力
2011-09-04 18:04 2547KIDx 的解题报告 http://acm.hdu.ed ... -
【超级hash大法】HDU 1496 Equations
2011-08-10 21:21 3245http://acm.hdu.edu.cn/showprobl ... -
【矩阵乘法+快速取幂模】HDU 1575 Tr A
2011-08-15 14:54 1536http://acm.hdu.edu.cn/showprobl ... -
【TMD的陷阱题】HDU 2143 box
2011-07-28 20:42 1445http://acm.hdu.edu.cn/showprobl ... -
HDU 2072 单词数
2011-07-23 18:31 1259http://acm.hdu.edu.cn/showprobl ... -
【让我悲催的水题】HDU 1070 Milk
2011-07-17 07:38 1584http://acm.hdu.edu.cn/showprobl ... -
POJ 2271 HTML
2011-06-05 09:54 1047http://poj.org/problem?id=2271 ... -
HDU_2096_小明A+B
2011-05-22 08:08 2563http://acm.hdu.edu.cn/showprobl ... -
POJ_1002_487-3279
2011-05-19 09:49 965http://poj.org/problem?id=1002 ...
相关推荐
Codeforces Round #723 (Div. 2).md
上面代码跑出来的dp[n][m]是0,然后从(1,1)(1,2)(2,2)(2,3)这样的相与值是k (看懂ans+k是啥应该就懂了) 代码: int main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int ans=(1&...
传送门 题意: 开始位置在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 #...
长度为n的字符串包含n−2n−2n−2个aaa和222个bbb,求按照字典序排列输出第kkk个字符串 解题思路 第一个bbb在倒数第二位有1个字符串,在倒数第三位有2个字符串…在倒数第nnn位时有n−1n-1n−1个字符串 可以根据第一...
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...
题目链接: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....
给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。其他边从最大点开始赋值。 证明:一...
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...
输入一个正整数x,找出这样的2个正整数a和b,使得gcd(a,b)+lcm(a,b)=x 解题思路 找最特殊的情况a=1,b=x-1即可 这样a,b两个数最大公因数为1,最小公倍数x-1,满足题意√ 附上代码 #include #define int long long #...
A #include using namespace std; typedef long long ll; int main(){ int t; cin>>t; while(t--){ ll x; cin>>x; cout<<1>>t; while(t--){ st.clear(); ll n; cin >>n;... ll re
传送门 A. EhAb AnD gCd 直接输出1,n-1即可 #include #include #include #include #include #include #include #include #include #include #define pb push_back #define lb lower_bound ...con
传送门 题意: 找规律,题意就是有多少种方式填充该图形 画两个就发现,输出n即可 代码: #include #include #include #include #include #include #include #include ...#define SZ(x) ((int)(x)
给一个长度为n的数组,两种操作,一个是把任意一个ai变成ai+2a_i变成a_i+2ai变成ai+2,另一个是如果所有数都大于0,可以把所有数减1,问通过这些操作能否把所有数变为0 思路: 如果任意两个数之差为奇数,那么就...
-2,4,5,5,6,8 要输出的序列应该是每次从前面选一个,然后从后面选一个 -2,8,4,6,5,5 然后把该序列倒着输出即可 代码: #include #include #include #include #include #include #include #include #...
将所有数字看成2进制,从最高位看起,如果第i位上为1的数只有一个的话,那么这个数必然对答案有贡献,就把它排在第一个,后面任意排。 例:11,6,4,0 二进制表示为:1011,110,100,0 右起第四位为1的只有1011,...