Codeforces Round Rockethon 2015

A. Game

题目大意:A有N1个球,B有N2个球,A每次可以扔1-K1个球,B每次可以扔1-K2个球,谁先不能操作谁熟

思路:.....显然每次扔一个球最优....

 1 #include<iostream>
 2 #include<cstdio>
 3 #include <math.h>
 4 #include<algorithm>
 5 #include<string.h>
 6 #include<queue>
 7 #define MOD 10000007
 8 #define maxn 200000
 9 #define LL long long
10 using namespace std;
11 int main()
12 {
13         int a,b,c,d;
14         scanf("%d%d%d%d",&a,&b,&c,&d);
15         if(a<=b)printf("Second\n");else printf("First\n");
16         return 0;
17 }

B. Permutations

题目大意:给你一个1-n的排列p,要你求在f(p)最大的前提下,字典序为m的排列

思路:一开始想烦了...对于1-n-1的排列,新的数n一定是插入n-1的左边或者右边,这样的排列才是满足f(p)最大的,于是写出来就会发现从小到大每一个数字要么放在当前序列的最前面,要么放在当前序列的最后面,然后就没有然后了

 1 #include<iostream>
 2 #include<cstdio>
 3 #include <math.h>
 4 #include<algorithm>
 5 #include<string.h>
 6 #include<queue>
 7 #define MOD 10000007
 8 #define maxn 200000
 9 #define LL long long
10 using namespace std;
11 long long bin[100];
12 int visit[maxn],ans[maxn];
13 int main()
14 {
15         bin[0]=1;
16         for(int i=1;i<=51;i++)bin[i]=bin[i-1]*2LL;
17         int n,anss;
18         long long m;
19         while(scanf("%d%I64d",&n,&m)!=EOF)
20         {
21                 int last=n;
22                 for(int i=1,j=1;i<=n;i++)
23                 {
24                         int u=bin[n-i-1];
25                         if(m<=u)ans[j]=i,j++;
26                         else ans[last]=i,last--,m-=u;
27                 }
28                 for(int i=1;i<=n;i++)printf("%d ",ans[i]);
29         }
30         return 0;
31 }

G1:Inversions problem

题目大意:对于每个1-n的排列,可以进行K次操作,每次操作可以对随机的一段子序列逆向,问K次操作后逆序数的期望是多少?

思路:敲了发暴力过了G1

 1 #include<iostream>
 2 #include<cstdio>
 3 #include <math.h>
 4 #include<algorithm>
 5 #include<string.h>
 6 #include<queue>
 7 #define MOD 10000007
 8 #define maxn 200000
 9 #define LL long long
10 using namespace std;
11 int a[100],m,n,up=0,down=0;
12 void dfs(int kk,int b[])
13 {
14         int c[100],d[100];
15         memcpy(d,b,sizeof(d));
16         if(kk==m+1)
17         {
18                 int inv=0;
19                 for(int i=1;i<=n;i++)
20                 {
21                         for(int j=i+1;j<=n;j++)
22                         {
23                                 if(b[j]<b[i])inv++;
24                         }
25                 }
26                 up+=inv;down++;
27                 return;
28         }
29         for(int i=1;i<=n;i++)
30                 for(int j=i;j<=n;j++)
31                 {
32                         for(int k=1;k<=j-i+1;k++)
33                         {
34                                 c[k]=b[j-k+1];
35                         }
36                         for(int k=1;k<=j-i+1;k++)
37                         {
38                                 b[i+k-1]=c[k];
39                         }
40                         dfs(kk+1,b);
41                         for(int k=1;k<=j-i+1;k++)
42                         {
43                                 c[k]=b[j-k+1];
44                         }
45                         for(int k=1;k<=j-i+1;k++)
46                         {
47                                 b[i+k-1]=c[k];
48                         }
49                 }
50 }
51 int main()
52 {
53         scanf("%d%d",&n,&m);
54         for(int i=1;i<=n;i++)
55         {
56                 scanf("%d",&a[i]);
57         }
58         dfs(1,a);
59         printf("%.9lf",1.0*up/down);
60         return 0;
61 }

时间: 02-06

Codeforces Round Rockethon 2015的相关文章

Codeforces Round #290 (Div. 2) b

/** * @brief Codeforces Round #290 (Div. 2) b * @file a.cpp * @author mianma * @created 2015/02/04 15:17 * @edited 2015/02/04 15:17 * @type brute * @note */ #include <fstream> #include <iostream> #include <string> #include <cstring>

Educational Codeforces Round 21 G. Anthem of Berland(dp+kmp)

题目链接:Educational Codeforces Round 21 G. Anthem of Berland 题意: 给你两个字符串,第一个字符串包含问号,问号可以变成任意字符串. 问你第一个字符串最多包含多少个第二个字符串. 题解: 考虑dp[i][j],表示当前考虑到第一个串的第i位,已经匹配到第二个字符串的第j位. 这样的话复杂度为26*n*m*O(fail). fail可以用kmp进行预处理,将26个字母全部处理出来,这样复杂度就变成了26*n*m. 状态转移看代码(就是一个kmp

Codeforces Round #428 (Div. 2)

Codeforces Round #428 (Div. 2) A    看懂题目意思就知道做了 #include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i

Codeforces Round #424 (Div. 2) D. Office Keys(dp)

题目链接:Codeforces Round #424 (Div. 2) D. Office Keys 题意: 在一条轴上有n个人,和m个钥匙,门在s位置. 现在每个人走单位距离需要单位时间. 每个钥匙只能被一个人拿. 求全部的人拿到钥匙并且走到门的最短时间. 题解: 显然没有交叉的情况,因为如果交叉的话可能不是最优解. 然后考虑dp[i][j]表示第i个人拿了第j把钥匙,然后 dp[i][j]=max(val(i,j),min(dp[i-1][i-1~j]))   val(i,j)表示第i个人拿

Codeforces Round #424 (Div. 2) C. Jury Marks(乱搞)

题目链接:Codeforces Round #424 (Div. 2) C. Jury Marks 题意: 给你一个有n个数序列,现在让你确定一个x,使得x通过挨着加这个序列的每一个数能出现所有给出的k个数. 问合法的x有多少个.题目保证这k个数完全不同. 题解: 显然,要将这n个数求一下前缀和,并且排一下序,这样,能出现的数就可以表示为x+a,x+b,x+c了. 这里 x+a,x+b,x+c是递增的.这里我把这个序列叫做A序列 然后对于给出的k个数,我们也排一下序,这里我把它叫做B序列,如果我

Codeforces Round #400 C 前缀和,思维

ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined) C. Molly's Chemicals 题意:n个数,问有多少个区间的和是k的次方数,即sum([l, r])=k^x, x>=0. abs(k)<=10. tags:一开始O(n^2)统计,果然炸了.. 这题要在统计到第 i 个数时,看s[i]-k^x是否在前面出现过.因为k指数增长很快,这样就是O(n). // #400 #include<b

[Codeforces] Round #352 (Div. 2)

人生不止眼前的狗血,还有远方的狗带 A题B题一如既往的丝帛题 A题题意:询问按照12345678910111213...的顺序排列下去第n(n<=10^3)个数是多少 题解:打表,输出 1 #include<bits/stdc++.h> 2 using namespace std; 3 int dig[10],A[1005]; 4 int main(){ 5 int aa=0; 6 for(int i=1;;i++){ 7 int x=i,dd=0; 8 while(x)dig[++dd

Codeforces Round #273 (Div. 2)

Codeforces Round #273 (Div. 2) 题目链接 A:签到,仅仅要推断总和是不是5的倍数就可以,注意推断0的情况 B:最大值的情况是每一个集合先放1个,剩下都丢到一个集合去,最小值是尽量平均去分 C:假如3种球从小到大是a, b, c,那么假设(a + b) 2 <= c这个比較明显答案就是a + b了.由于c肯定要剩余了,假设(a + b)2 > c的话,就肯定能构造出最优的(a + b + c) / 3,由于肯定能够先拿a和b去消除c,而且控制a和b成2倍关系或者消除

Codeforces Round #339 (Div. 2) B. Gena&#39;s Code

B. Gena's Code It's the year 4527 and the tanks game that we all know and love still exists. There also exists Great Gena's code, written in 2016. The problem this code solves is: given the number of tanks that go into the battle from each country, f