这场的题目也很水,但是我竟然在第二题浪费了5次提交,罚时严重啊T T
果然还是太水了,姑且写个题解。。。
A - Difference Row
手速题,我还蛋疼把最大值和最小值提取出来重新排序了。。。
其实只要全部排序,让最大和最小位置调换下就行了。
复杂度为sort的O(nlogn)
代码:
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: a.cpp
* Create Date: 2013-09-20 23:32:37
* Descripton: a
*/
#include <cstdio>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
const int MAXN = 1001;
int n, ra, ri, a[MAXN];
int Max = -1000, Min = 1001;
int main() {
scanf("%d", &n);
rep(i, n) {
scanf("%d", &a[i]);
if (Max < a[i]) {
Max = a[i];
ra = i;
}
if (Min > a[i]) {
Min = a[i];
ri = i;
}
}
a[ra] = 1001;
a[ri] = 1001;
sort(a, a + n);
if (n == 2)
printf("%d %d\n", Max, Min);
else {
printf("%d", Max);
rep(i, n - 2)
printf(" %d", a[i]);
printf(" %d\n", Min);
}
return 0;
}
B - Fixed Points
定义一个全排列上,如果该位置上的数和序号一样为fixed point,比如0,1,2就有3个,0,2,1就只有1个了。(这个序列一定是排列)
给出一个序列,最多交换一次任意两个数,求交换后fixed point最多多少。
如果达到上限就不用交换了。
否则,我们可以发现,如果一个数是fixed point,那它就没有必要交换了,因为这样不会产生更好的结果,我们只要交换位置不对的数。
如果直接枚举不对的数肯定会超时。
位置不对的数,直接找它位置上的数对应的位置,那个位置肯定也不对,和它交换能够得到1或2的fixed point增量。
于是遍历不对的数,尝试和对应的位置交换,如果交换后增量为2就可以直接退出了,否则增量为1。
复杂度为O(n)。
代码:
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: b.cpp
* Create Date: 2013-09-20 23:43:46
* Descripton: b
*/
#include <cstdio>
#define rep(i, n) for (int i = 0; i < (n); i++)
const int MAXN = 100100;
int a[MAXN], n, cnt;
int rec[MAXN], r;
int main() {
scanf("%d", &n);
rep(i, n) {
scanf("%d", &a[i]);
if (a[i] == i)
cnt++;
else
rec[r++] = i;
}
int cg = r > 0 ? 1 : 0;
rep(i, r)
if (a[a[rec[i]]] == rec[i]) {
cg = 2;
break;
}
printf("%d\n", cnt + cg);
return 0;
}
C - Alice and Bob
A 和 B玩游戏,A每次先手,游戏规则:在一个集合中找到两个数,他们的差不在集合中,然后添加到集合里。如果找不到那个人就是输了。
模拟肯定超时的。。。
于是在纸上模拟了一遍样例和想出来的一个简单样例,发现其实最后集合里就只剩1-max了。
后来又想到如果都是10的倍数就不一样了。
然后题目就出来了,求出全部值的gcd,最后游戏的操作数就是max/gcd - n,然后就知道谁赢了。
代码:
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: c.cpp
* Create Date: 2013-09-21 00:41:09
* Descripton: gcd
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long LL;
LL g, t;
LL gcd(LL a, LL b) {
if(b == 0)
return a;
return gcd(b, a % b);
}
int main() {
int n;
LL Max = 0;
cin >> n;
rep(i, n) {
cin >> t;
if (i)
g = gcd(g, t);
else
g = t;
Max = max(Max, t);
}
LL cnt = Max / g - n;
if (cnt % 2 == 0) printf("Bob\n");
else printf("Alice\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 #...
其实这道题比较水,但当时思路错,一心想着化简公式,浪费了好多时间a.a 题意:三个数组,求(x-y)(x-y)+(x-z)(x-z)+(y-z)*(y-z)的最小值 题解:6nlogn,先sort三个数组a,b,c, 六次枚举二分查找,再每次min找最小值,...
给一个长度为n的数组,两种操作,一个是把任意一个ai变成ai+2a_i变成a_i+2ai变成ai+2,另一个是如果所有数都大于0,可以把所有数减1,问通过这些操作能否把所有数变为0 思路: 如果任意两个数之差为奇数,那么就...
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
C(n-2,i-1)*C(j-1,n-2)*(i-1) __ j: n-1 -> m 我们发现内层循环,每次只是j加一,我们就可以只用一次组合数剩下的用差量表示 对于外层循环同理 只有(i-1) * C(n-2,i-1) i会每次加一。我们也只算一次剩下的用差量...
给一个长为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
题目链接: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....