Codeforces Round #203 (Div. 2)
这场在最后千钧一发交了一发过了C,不然又要掉rating了。。。
B敲了太久了,orz编码能力不足啊~
A - TL
求编程比赛的时限,使得正确答案都能过,错误答案都不能过,且至少有一个正确答案的时间能小于时限的一半。
模拟水题,看题目看了好久。。
代码:
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: a.cpp
* Create Date: 2013-10-01 23:38:47
* Descripton: a
*/
#include <cstdio>
#include <iostream>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
int main() {
int n, m, Mina = 100, Maxa = 0, Minb = 100, t;
cin >> n >> m;
rep(i, n) {
cin >> t;
Mina = min(Mina, t);
Maxa = max(Maxa, t);
}
rep(i, m) {
cin >> t;
Minb = min(Minb, t);
}
if (Mina * 2 >= Minb || Minb <= Maxa) {
puts("-1");
return 0;
}
cout << max(Mina * 2, Maxa) << endl;
return 0;
}
B - Resort
要找一条到达hotel的最长的路,注意路上不能有分叉且路是又向的。
直接dfs+剪枝就行了,图用set存的。。。看别人用一维数组好神。
代码:
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: b.cpp
* Create Date: 2013-10-02 00:17:29
* Descripton: b
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repf(i, a, b) for (int i = (a); i <= (b); i++)
#define ms(a, i) memset(a, i, sizeof(a))
#define FI(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
const int MAXN = 100010;
set<int> pre[MAXN], nex[MAXN];
int n, t, obj[MAXN], path[MAXN];
int d[MAXN], used[MAXN];
int Max = 0, rec;
int dp(int o) {
if (d[o] != -1) return d[o];
if (nex[o].size() > 1 || used[o]) return d[o] = 0;
if (pre[o].size() == 0) {
path[o] = 0;
return d[o] = 1;
}
d[o] = 0;
used[o] = 1;
FI(i, pre[o]) {
int ts = dp(*i);
if (ts > d[o]) {
d[o] = ts;
path[o] = *i;
}
}
return d[o] + 1;
}
void F(int p, int cnt) {
if (p == 0) return;
F(path[p], cnt + 1);
if (cnt) printf("%d ", p);
else printf("%d\n", p);
}
int main() {
ms(d, -1);
scanf("%d", &n);
rep(i, n) {
scanf("%d", &obj[i + 1]);
}
rep(i, n) {
scanf("%d", &t);
if (t) {
pre[i + 1].insert(t);
nex[t].insert(i + 1);
}
}
repf(i, 1, n) if (obj[i]) {
t = dp(i);
if (Max < t) {
Max = t;
rec = i;
}
}
cout << Max << endl;
F(rec, 0);
return 0;
}
C - Bombs
排雷,给出几个雷的地点,挖出那些雷回到原点炸掉。
本来做出b题血槽就已近空了,还有20多分钟,在qq闲侃了几句,无聊过来看看c题,发现是大水题。。。
按距离排下序输出就行了。
代码:
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: c.cpp
* Create Date: 2013-10-02 01:14:06
* Descripton: c
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long LL;
const int MAXN = 100010;
struct P {
int x, y;
int step;
} p[MAXN];
int n;
bool cmp(P a, P b) {
return a.step < b.step;
}
int main() {
cin >> n;
LL cnt = 0;
rep(i, n) {
scanf("%d%d", &p[i].x, &p[i].y);
p[i].step = abs(p[i].x) + abs(p[i].y);
if (p[i].x) cnt+= 2;
if (p[i].y) cnt+=2;
cnt += 2;
}
sort (p, p + n, cmp);
cout << cnt << endl;
rep(i, n) {
if (p[i].x > 0)
printf("1 %d R\n", p[i].x);
else if (p[i].x < 0)
printf("1 %d L\n", -p[i].x);
if (p[i].y > 0)
printf("1 %d U\n", p[i].y);
else if (p[i].y < 0)
printf("1 %d D\n", -p[i].y);
printf("2\n");
if (p[i].x > 0)
printf("1 %d L\n", p[i].x);
else if (p[i].x < 0)
printf("1 %d R\n", -p[i].x);
if (p[i].y > 0)
printf("1 %d D\n", p[i].y);
else if (p[i].y < 0)
printf("1 %d U\n", -p[i].y);
printf("3\n");
}
return 0;
}
分享到:
相关推荐
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
一个长度为n的数组,为删除一些数后,剩下的数能否构成长度大于3的回文数组 思路: 只要能找到两个相等的数,且他们的间距大于2即可 o(n^2)的暴力就能过 比赛时写了一个o(n)的 就是把所有相等的数放到一个vector里,...
长度为n的字符串包含n−2n−2n−2个aaa和222个bbb,求按照字典序排列输出第kkk个字符串 解题思路 第一个bbb在倒数第二位有1个字符串,在倒数第三位有2个字符串…在倒数第nnn位时有n−1n-1n−1个字符串 可以根据第一...
E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
给两两节点放一个数字(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 ...
输入一个正整数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 #...
给一个长度为n的数组,两种操作,一个是把任意一个ai变成ai+2a_i变成a_i+2ai变成ai+2,另一个是如果所有数都大于0,可以把所有数减1,问通过这些操作能否把所有数变为0 思路: 如果任意两个数之差为奇数,那么就...
其实这道题比较水,但当时思路错,一心想着化简公式,浪费了好多时间a.a 题意:三个数组,求(x-y)(x-y)+(x-z)(x-z)+(y-z)*(y-z)的最小值 题解:6nlogn,先sort三个数组a,b,c, 六次枚举二分查找,再每次min找最小值,...
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
给一个长为n(≤5000)的数组,问是否存在一个长度至少为3的子序列是回文的,子序列的数可以不连续但是相对顺序不可变 解题思路 暴力,因为可以不连续,只要找有两位相等的而且不相邻的数即可 附上代码 #include #...
传送门 题意: 找规律,题意就是有多少种方式填充该图形 画两个就发现,输出n即可 代码: #include #include #include #include #include #include #include #include ...#define SZ(x) ((int)(x)
传送门 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
time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output There are n points on a coordinate axis OX. The i-th point is located at the integer point xi ...
题目链接: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....