1. 首页
  2. 文章中心
  3. 算法设计

Codeforces gym 2011-2012, Samara Interacademic Programming

113 阅读 0 评论
我是靠谱客的博主 洁净唇膏，这篇文章主要介绍Codeforces gym 2011-2012, Samara Interacademic Programming，现在分享给大家，希望可以做个参考。

Codeforces gym 2011-2012, Samara Interacademic Programming

题目地址：http://codeforces.com/gym/100030

今天(2014.11.12，周日)用了3个半小时完成了7道简单题，最后回来又过了一题，共8题

题目比较水，但有些题目比较好，也不是那么好想的，所以就认真做了下这篇总结

其中用到了博弈，dp，二进制状压及位运算，two pointers，lower_bound与upper_bound搜索

总的来说，都需要模拟或贪心，考一定算法而又不考很高深算法，属于简单题目


还有几道题没写出来，最后看了一下，目前还没过，改天过了再更新本博文

本比赛输入输出方式均为文件输入方式

所以根据要求代码要添加下面两行

freopen("input.txt","r",stdin);

freopen("output.txt","w",stdout);





这题是博弈论题，感觉算一道好题


注意到n和a[i]范围很小，应该是博弈判断来解决。这种题有点像博弈论里Nim游戏的题目，Nim游戏可以用异或 (^) 解决，但这里不是用异或解决

此博弈满足零和博弈，即“你死我活”，先手胜后手必败，先手败后手必胜

发现一：对于一叠石子，其数量为a[i]，a[i]如果是奇数，那么先手必胜，否则先手必败

那么，对于n叠石子

如果这一叠是最后一叠，直接通过“发现一”来解决

如果不是最后一叠，其可以通过上一叠石子状态来推得，如下：

假设第  i  和 第 i＋1  叠石子，假设 i 叠为奇数，则 i+1 叠先手后手顺序与 i 叠一致，否则就要变换

假设C为 第 i 叠的先手，M为后手，a[i]为奇数，那么对于这一叠来说，C必败，即C会进行到不能再进行的一步，所以C在下一叠还是先手

同理，加入a[i]为偶数，M会进行到不能再进行的一步，所以M在下一叠就是先手，此时先后说顺序要改变


所以我们可以知道第一叠的先手顺序和第一叠石子的奇偶性，由此可以推出第二叠(如果有的话)石子的先手顺序，又知道第二叠石子的奇偶性......

所以，就可以知道第n叠石子的先手顺序，又知道第n叠石子的奇偶性，利用“发现一”就可以知道最终赢家是谁

具体代码如下：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//Hello. I'm Peter.
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cctype>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double ld;
#define peter cout<<"i am peter"<<endl
#define input freopen("data.txt","r",stdin)
#define randin srand((unsigned int)time(NULL))
#define INT (0x3f3f3f3f)*2
#define LL (0x3f3f3f3f3f3f3f3f)*2
#define gsize(a) (int)a.size()
#define len(a) (int)strlen(a)
#define slen(s) (int)s.length()
#define pb(a) push_back(a)
#define clr(a) memset(a,0,sizeof(a))
#define clr_minus1(a) memset(a,-1,sizeof(a))
#define clr_INT(a) memset(a,INT,sizeof(a))
#define clr_true(a) memset(a,true,sizeof(a))
#define clr_false(a) memset(a,false,sizeof(a))
#define clr_queue(q) while(!q.empty()) q.pop()
#define clr_stack(s) while(!s.empty()) s.pop()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define dep(i, a, b) for (int i = a; i > b; i--)
#define repin(i, a, b) for (int i = a; i <= b; i++)
#define depin(i, a, b) for (int i = a; i >= b; i--)
#define pi acos(-1.0)
#define eps 1e-6
#define MOD 1000000007
#define MAXN 2014
#define N 100
#define M
int a[N],n;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin>>n;
repin(i,1,n){
scanf("%d",a+i);
}
bool Cfirst=true;
bool Cwin=true;
repin(i,1,n){
if(i==n){
if(Cfirst && a[i]%2) Cwin=false;
else if(Cfirst && a[i]%2==0) Cwin=true;
else if(!Cfirst && a[i]%2) Cwin=true;
else if(!Cfirst && a[i]%2==0) Cwin=false;
}
else{
if(Cfirst && a[i]%2) Cfirst=true;
else if(Cfirst && a[i]%2==0) Cfirst=false;
else if(!Cfirst && a[i]%2) Cfirst=false;
else if(!Cfirst && a[i]%2==0) Cfirst=true;
}
}
if(Cwin) printf("Constantinen");
else printf("Miken");
}






此题为经典dp题

题意如下：

给一个长度为n的数列a[ ]，给定m，对于1=<i<=n，则要求 1=<a[i]<=m，a[i]为整数；

同时，要求数列为严格单调递增数列，即对于任意 1=<i<j<=n ，a[i]<a[j]；

给定了n和m，问符合条件的数列有多少个，答案需要模上10^9+7


设dp[i][j]表示  数列第 i 个位置 放 j 这个数时的情况数，1<=i<=n，1=<j<=m

先预处理

起初dp[i][j]里所有值均为0

for j: 1 to m

   dp[1][j]=1;

表示第一个位置放 j 这个数时情况数为1

由于严格单调递增性质，得到如下转移方程：

for i: 2 to n

  for j: 1 to m

      for k: 1 to j-1

           dp[i][j]=dp[i][j]+dp[i-1][k]；

表示，当i>=2时候，dp[i][j] 由上一层获得，上一层dp[i-1][k] 中满足题意的当且仅当 1<=k<j （因为数列单调递增）

最后统计答案：

for j : 1 to m

    ans=ans+dp[n][j];

（再上面过程适当补上取模操作即可）

代码如下：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//Hello. I'm Peter.
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cctype>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double ld;
#define peter cout<<"i am peter"<<endl
#define input freopen("data.txt","r",stdin)
#define randin srand((unsigned int)time(NULL))
#define INT (0x3f3f3f3f)*2
#define LL (0x3f3f3f3f3f3f3f3f)*2
#define gsize(a) (int)a.size()
#define len(a) (int)strlen(a)
#define slen(s) (int)s.length()
#define pb(a) push_back(a)
#define clr(a) memset(a,0,sizeof(a))
#define clr_minus1(a) memset(a,-1,sizeof(a))
#define clr_INT(a) memset(a,INT,sizeof(a))
#define clr_true(a) memset(a,true,sizeof(a))
#define clr_false(a) memset(a,false,sizeof(a))
#define clr_queue(q) while(!q.empty()) q.pop()
#define clr_stack(s) while(!s.empty()) s.pop()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define dep(i, a, b) for (int i = a; i > b; i--)
#define repin(i, a, b) for (int i = a; i <= b; i++)
#define depin(i, a, b) for (int i = a; i >= b; i--)
#define pi acos(-1.0)
#define eps 1e-6
#define MOD 1000000007
#define MAXN 2014
#define N 300
#define M
int dp[N][N],n,m,ans;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin>>n>>m;
repin(j,1,m){
dp[1][j]=1;
}
repin(i,2,n){
repin(j,1,m){
rep(k,1,j){
dp[i][j]+=dp[i-1][k];
dp[i][j]%=MOD;
}
}
}
ans=0;
repin(j,1,m){
ans+=dp[n][j];
ans%=MOD;
}
cout<<ans<<endl;
}





此题很容易

题意如下：

有n台电脑，每一次每台电脑都可以给k台电脑“充电”（与题意一个意思，换种表述）

一开始只有一台电脑有电，这一次此台电脑给k个电脑充电后，下一次仍然可以

问，最少多少次把n台电脑都充满电？

假设now表示当前有now台电脑有电，起初now=1;

while(now<n)

   now=now+now*k;

   ans=ans+1

主要代码就上面三行，now<n表示还需要给其他电脑充电，已经充过的就没有再充的必要(贪心)

下一次的now由上一次的得来，这一次有now台有电，那么这一次可以给now*k台电脑充电，所以下一次now=now+now*k；此时ans+=1表示充了一次

这个while loop的时间复杂度是O(logn)级别的

因为now+now*k>=2*now (k>=1)，所以now是以指数级别增长，跳出循环条件是now<n，是O(logn)级别，具体就不证明解释了

代码如下：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//Hello. I'm Peter.
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cctype>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double ld;
#define peter cout<<"i am peter"<<endl
#define input freopen("data.txt","r",stdin)
#define randin srand((unsigned int)time(NULL))
#define INT (0x3f3f3f3f)*2
#define LL (0x3f3f3f3f3f3f3f3f)*2
#define gsize(a) (int)a.size()
#define len(a) (int)strlen(a)
#define slen(s) (int)s.length()
#define pb(a) push_back(a)
#define clr(a) memset(a,0,sizeof(a))
#define clr_minus1(a) memset(a,-1,sizeof(a))
#define clr_INT(a) memset(a,INT,sizeof(a))
#define clr_true(a) memset(a,true,sizeof(a))
#define clr_false(a) memset(a,false,sizeof(a))
#define clr_queue(q) while(!q.empty()) q.pop()
#define clr_stack(s) while(!s.empty()) s.pop()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define dep(i, a, b) for (int i = a; i > b; i--)
#define repin(i, a, b) for (int i = a; i <= b; i++)
#define depin(i, a, b) for (int i = a; i >= b; i--)
#define pi acos(-1.0)
#define eps 1e-6
#define MOD 1000000007
#define MAXN 2014
#define N 300
#define M
ll n,k,now,ans;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin>>n>>k;
ans=0;
now=1;
while(now<n){
now+=now*k;
ans+=1;
}
cout<<ans<<endl;
}







此题好题，用到了两次二进制状态压缩


如上图有20个空格，是一个二进制数，发现，第2，6，7，19，20空为1，其余空为0. 表示选择第2，6，7，19，20题目，其余题目不选择

这样子用二进制表示状态，就可以知道每一个数对应的状态下哪几道题被选择了，是一种枚举的方法

数的下限是0，上限是2^n-1，即查找[0,2^n-1]里的每一个数

然后用适当的方法，查找当前数中哪几个位置为1，适当存储下来(具体过程不描述了，方法多样简单，可以脑补粗来)

那么，我们得到一个vector<int>vt，其中存储的是选择的题目的编号

根据题目，我们知道每一个题目对应哪一个程序(solution，同样的意思，姑且用程序描述)

发现，程序个数不超过60，也可以用二进制表示(2^60<9*10^18，不超过longlong的范围)


如上图，是一个含有60个空的二进制数

与第一副题类似，其表示的是，每个题目是否含有每个程序，发现上面这个二进制数，3，4，5，6...等程序为1，表示含有该程序，其余0表示不含有

那么在输入的时候，就可以维护每个题目程序所表示的二进制数

long long a[i]; //a[i]表示第 i 个题目所含有的程序对应的二进制数

for i: 1 to n

   scanf->k;

   a[i]=0;

   for j: 1 to k

       scanf->t;

      a[i]=a[i] + (1LL<<(t-1));

题目保证k个数都不一样，这样a[i]就可以准确表示第 i 个程序对应的二进制数

现在回到之前枚举[0,2^n-1]里的数的环节

我们通过vector<int>vt已经知道哪些题目被选择了

那么这些题目对应的a[i]全部异或起来，即anst=(a[vt[0]] | a[vt[1]] | ...... | a[vt[len-1]]);  len=vt.size();

ant表示的是所选择的题目对应的所有程序的集合，同样把其看成一个二进制数

题目要求所有程序必须被选择，则anst中m个格子必须全为1，即anst==(1<<m)-1，此时满足题意，就可以动态规划维护答案

代码如下：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
//Hello. I'm Peter.
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cctype>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double ld;
#define peter cout<<"i am peter"<<endl
#define input freopen("data.txt","r",stdin)
#define randin srand((unsigned int)time(NULL))
#define INT (0x3f3f3f3f)*2
#define LL (0x3f3f3f3f3f3f3f3f)*2
#define gsize(a) (int)a.size()
#define len(a) (int)strlen(a)
#define slen(s) (int)s.length()
#define pb(a) push_back(a)
#define clr(a) memset(a,0,sizeof(a))
#define clr_minus1(a) memset(a,-1,sizeof(a))
#define clr_INT(a) memset(a,INT,sizeof(a))
#define clr_true(a) memset(a,true,sizeof(a))
#define clr_false(a) memset(a,false,sizeof(a))
#define clr_queue(q) while(!q.empty()) q.pop()
#define clr_stack(s) while(!s.empty()) s.pop()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define dep(i, a, b) for (int i = a; i > b; i--)
#define repin(i, a, b) for (int i = a; i <= b; i++)
#define depin(i, a, b) for (int i = a; i >= b; i--)
#define pi acos(-1.0)
#define eps 1e-6
#define MOD 1000000007
#define MAXN 100100
#define N 100
#define M
int n,m,k,ans;
int limit1;
ll a[N],llt;
vector<int>ansv;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin>>n>>m;
rep(i,0,n){
scanf("%d",&k);
a[i]=0;
int t;
rep(j,0,k){
scanf("%d",&t);
a[i]+=(1LL<<(t-1));
}
}
limit1=(1<<n)-1;
vector<int>ansvt;
ans=INT;
int anst;
repin(i,0,limit1){
llt=0;
ansvt.clear();
anst=0;
rep(j,0,n){
if(i&(1<<j)){
llt|=a[j];
ansvt.pb(j+1);
anst+=1;
}
}
if(llt==(1LL<<m)-1 && anst<ans){
ans=anst;
ansv=ansvt;
}
}
sort(ansv.begin(),ansv.end());
printf("%dn",ans);
int lenv=gsize(ansv);
bool first=true;
rep(i,0,lenv){
if(first) first=false;
else printf(" ");
printf("%d",ansv[i]);
}
printf("n");
}









此题用一个结构体排序，后统计一下就好了。不解释了。是签到题

代码如下：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//Hello. I'm Peter.
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cctype>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double ld;
#define peter cout<<"i am peter"<<endl
#define input freopen("data.txt","r",stdin)
#define randin srand((unsigned int)time(NULL))
#define INT (0x3f3f3f3f)*2
#define LL (0x3f3f3f3f3f3f3f3f)*2
#define gsize(a) (int)a.size()
#define len(a) (int)strlen(a)
#define slen(s) (int)s.length()
#define pb(a) push_back(a)
#define clr(a) memset(a,0,sizeof(a))
#define clr_minus1(a) memset(a,-1,sizeof(a))
#define clr_INT(a) memset(a,INT,sizeof(a))
#define clr_true(a) memset(a,true,sizeof(a))
#define clr_false(a) memset(a,false,sizeof(a))
#define clr_queue(q) while(!q.empty()) q.pop()
#define clr_stack(s) while(!s.empty()) s.pop()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define dep(i, a, b) for (int i = a; i > b; i--)
#define repin(i, a, b) for (int i = a; i <= b; i++)
#define depin(i, a, b) for (int i = a; i >= b; i--)
#define pi acos(-1.0)
#define eps 1e-6
#define MOD 1000000007
#define MAXN 100100
#define N 3000
#define M 30
struct Subject{
int id;
int num_class;
int ans;
}sub[N];
int k,n,now;
bool comp1(const Subject a,const Subject b){
return a.num_class<b.num_class;
}
bool comp2(const Subject a,const Subject b){
return a.id<b.id;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin>>k>>n;
repin(i,1,n){
sub[i].id=i;
sub[i].ans=0;
scanf("%d",&sub[i].num_class);
}
sort(sub+1,sub+1+n,comp1);
now=0;
repin(i,1,n){
if(now+sub[i].num_class<k){
sub[i].ans=sub[i].num_class;
now+=sub[i].num_class;
}
else if(now+sub[i].num_class>=k){
sub[i].ans=k-now;
break;
}
}
sort(sub+1,sub+1+n,comp2);
bool first=true;
repin(i,1,n){
if(first) first=false;
else printf(" ");
printf("%d",sub[i].ans);
}
printf("n");
}





此题算一道好题，我记得这个方法可以叫two pointers吧？就算不行，也类似了，姑且是吧

要求最长符合题意的子串(实际输出对应原串的起始和终止位置)，要求子串中字符种类不超过k

设两个pointers，也就是两个变量from, i ，from表示头指针，i 表示当前指针，i-from+1表示当前的子串的长度，s[from]...s[i]表示当前子串

设int num[26]，表示'a'-'z'(对应0-25)出现的次数

for i : 0 to len-1

  int t=s[i]-'a';

  num[t]+=1;

  if(num[t]==1) num_dif+=1;

num_dif表示当前s[from]...s[i]这个子串中种类数

为什么num[t]==1就+=1呢？因为num[t]==1，说明之前num[t]==0，说明当前串之前没有s[i]这个字符，现在有了，所以种类数+=1

接下来

  if(num_dif>k)

      while(num_dif>k)

           int t2=s[from]-'a';

           num[t2]-=1;

   if(num[t2]==0)  num_dif －=1;

           from++;

题目要求种类数不能大于k，所以当num_dif>k的时候，当前子串已经不符合题意，就需要将from往右移动，即from++；

移动过程，需要维护num[]和种类数num_dif，当移动到一个地方满足num_dif<=k时候立刻跳出while loop，这样子就可以保证最优性

接下来统计答案

if(i-from+1>ans)

   ans=i-from+1;

   ansfrom=from;

   ansto=ansto;

最后，ansfrom和ansto就是需要输出的答案

由于子串的连续性，可以保证这样的two pointers方法求出的答案是最优的

具体代码如下：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
//Hello. I'm Peter.
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cctype>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double ld;
#define peter cout<<"i am peter"<<endl
#define input freopen("data.txt","r",stdin)
#define randin srand((unsigned int)time(NULL))
#define INT (0x3f3f3f3f)*2
#define LL (0x3f3f3f3f3f3f3f3f)*2
#define gsize(a) (int)a.size()
#define len(a) (int)strlen(a)
#define slen(s) (int)s.length()
#define pb(a) push_back(a)
#define clr(a) memset(a,0,sizeof(a))
#define clr_minus1(a) memset(a,-1,sizeof(a))
#define clr_INT(a) memset(a,INT,sizeof(a))
#define clr_true(a) memset(a,true,sizeof(a))
#define clr_false(a) memset(a,false,sizeof(a))
#define clr_queue(q) while(!q.empty()) q.pop()
#define clr_stack(s) while(!s.empty()) s.pop()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define dep(i, a, b) for (int i = a; i > b; i--)
#define repin(i, a, b) for (int i = a; i <= b; i++)
#define depin(i, a, b) for (int i = a; i >= b; i--)
#define pi acos(-1.0)
#define eps 1e-6
#define MOD 1000000007
#define MAXN 100100
#define N
#define M 30
int num[M],lens,num_dif,from,ans,ansfrom,ansto,k;
char s[MAXN];
int idx(char c){
return c-'a';
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin>>k;
scanf("%s",s+1);
lens=len(s+1);
int ct,ct2;
num_dif=0;
from=1;
ans=0;
repin(i,1,lens){
ct=idx(s[i]);
num[ct]+=1;
if(num[ct]==1) num_dif+=1;
if(num_dif>k){
while(1){
ct2=idx(s[from]);
num[ct2]-=1;
if(num[ct2]==0) num_dif-=1;
from++;
if(num_dif<=k) break;
}
}
if(i-from+1>ans){
ans=i-from+1;
ansfrom=from;
ansto=i;
}
}
printf("%d %dn",ansfrom,ansto);
}





 这题很逗，被题意卡了一下，最后百度才发现 Triskaidekaphobia

的意思是黑色星期五，同时也有13恐惧症的意思

所以，主人公不希望所给的串中出现“13”，题目问最少删除多少个字符保证字符串没有“13”。


题意卡了下，方法也卡了下，不过被我的一个发现给解决了

假设如下串(S1)

3333333333311111113333333111111111333331111331111111333333311111111111

发现一：串开头的3和结尾的1 不会构成“13”

所以不妨把头尾的3和结尾的1给删除，删除后若串空了，说明答案为0

删除后，串变为(S2)：

111111133333331111111113333311113311111113333333

那么，我们就可以得到4组“13”连续串

第一组：11111113333333

第二组：11111111133333

第三组：111133

第四组：11111113333333

将每一组存储在一个结构体数组中，存储字符1和3的个数

发现二：答案一定不超过S2中1和3总数的最小值

即ans=min(num1,num3);

发现二是显然的，但不是答案，答案可能会比其更小

举个栗子：

1133333311111133

此时，含有8个1和8个3，但如果删除头两个1和后两个3，串就变为333333111111，不含有“13”符合题意，这样最优答案就是4


那么怎么办呢？百思不得其解时，忽得发现三四

发现三：对于每组连续串，要不删除1，要不删除3，这样子是最优的

发现四：对于第 i 组连续串，若我选择删除3，那么，后面的连续串 i+1...n 选择删除3一定比选择删除1会更好

我们回到之前S2：111111133333331111111113333311113311111113333333

假设第2个连续串选择了删除3，串会变为：11111113333333111111111_11113311111113333333

（'_' 只是为了表示之前3字符串所在的位置，实际上不存在'_'）

那么，此时，如果第3个连续串我选择删除1，串会变为：11111113333333111111111_3311111113333333

会发现，此时，第2个连续串的1也必须删除，或者第3个连续串的3必须删除

也就是说，要不然第二连续串全部删除了，要不然第三个连续串全部删除了，这与发现三是矛盾的。


由此可以得到一个结论，假设第 i 个连续串我删除了3，后面的连续穿必然也要删除3

于是乎，我们已经得到ans=min(num1,num3);

for i: 1 to n // n表示连续串的个数

   t=从1到 i-1所有连续串1的总数  ＋  从 i 到 n 所有连续串3的总数;

   ans=min(ans,t); 

至于t怎么求解，前缀和以及后缀和就可以了。

具体代码如下：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
//Hello. I'm Peter.
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cctype>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double ld;
#define peter cout<<"i am peter"<<endl
#define input freopen("data.txt","r",stdin)
#define randin srand((unsigned int)time(NULL))
#define INT (0x3f3f3f3f)*2
#define LL (0x3f3f3f3f3f3f3f3f)*2
#define gsize(a) (int)a.size()
#define len(a) (int)strlen(a)
#define slen(s) (int)s.length()
#define pb(a) push_back(a)
#define clr(a) memset(a,0,sizeof(a))
#define clr_minus1(a) memset(a,-1,sizeof(a))
#define clr_INT(a) memset(a,INT,sizeof(a))
#define clr_true(a) memset(a,true,sizeof(a))
#define clr_false(a) memset(a,false,sizeof(a))
#define clr_queue(q) while(!q.empty()) q.pop()
#define clr_stack(s) while(!s.empty()) s.pop()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define dep(i, a, b) for (int i = a; i > b; i--)
#define repin(i, a, b) for (int i = a; i <= b; i++)
#define depin(i, a, b) for (int i = a; i >= b; i--)
#define pi acos(-1.0)
#define eps 1e-6
#define MOD 1000000007
#define MAXN 100100
#define N 10100
#define M 30
string s;
int ans;
struct Segment{
int num1,num3;
}seg[N];
int preone[N],suffixthree[N];
int num_seg;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin>>s;
ans=0;
int len=slen(s);
while(len){
if(s[0]=='3') s.erase(0,1);
else break;
len=slen(s);
}
while(len){
if(s[len-1]=='1') s.erase(len-1,1);
else break;
len=slen(s);
}
len=slen(s);
if(!len){
printf("%dn",0);
exit(0);
}
clr(seg);
clr(preone);
clr(suffixthree);
num_seg=0;
int last=3;
rep(i,0,len){
if(last==3 && s[i]=='1'){
num_seg+=1;
seg[num_seg].num1+=1;
last=1;
}
else if(last==1 && s[i]=='3'){
seg[num_seg].num3+=1;
last=3;
}
else if(last==1 && s[i]=='1') seg[num_seg].num1+=1;
else if(last==3 && s[i]=='3') seg[num_seg].num3+=1;
}
repin(i,1,num_seg){
preone[i]=preone[i-1]+seg[i].num1;
}
depin(i,num_seg,1){
suffixthree[i]=suffixthree[i+1]+seg[i].num3;
}
int num1=0,num3=0;
rep(i,0,len){
if(s[i]=='1') num1+=1;
else num3+=1;
}
ans=min(num1,num3);
int t;
repin(i,1,num_seg){
t=preone[i-1]+suffixthree[i];
ans=min(ans,t);
}
cout<<ans<<endl;
}




题意就不讲了，都能看得懂，讲起来有点绕口

发现一：ans1一定是所有ai 或 bi 里的一个数

那么，就可以用lower_bound和upper_bound求出答案，复杂度为O(nlogn)

for i: 1 to num// num表示所有a[i]和b[i]的总数

   p=a[i]或者b[i];

   k1=满足p<a[j]的所有 j 的总数 //可以用upper_bound求出

   k2=满足p>b[j]的所有 j 的总数 //可以用lower_bound求出

   k3=n-(k1+k2);

   // k3表示满足a[j]=<p<=b[j]的所有 j 的总数

   ....再维护答案


再维护答案的代码在这里讲一下，题目说了，p>b[j]的话，捐钱数为0；p<a[j]的话，捐钱数为a[j]，所以捐钱总数就为所有 p<a[j] 的 a[j]的总和

在求k1是用upper_bound来求，用upper_bound前提是所求数组要单调，这里是单调递增，那么就可以用前缀和的办法求出所有p<a[j] 的 a[j]的总和

而当 a[j]=<p<=b[j]，捐钱数就为 p，则捐钱总数就为 k3*p（如果用int定义的话，注意int到longlong的坑）

这样子不断维护的答案即可

代码如下：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//Hello. I'm Peter.
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cctype>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double ld;
#define peter cout<<"i am peter"<<endl
#define input freopen("data.txt","r",stdin)
#define randin srand((unsigned int)time(NULL))
#define INT (0x3f3f3f3f)*2
#define LL (0x3f3f3f3f3f3f3f3f)*2
#define gsize(a) (int)a.size()
#define len(a) (int)strlen(a)
#define slen(s) (int)s.length()
#define pb(a) push_back(a)
#define clr(a) memset(a,0,sizeof(a))
#define clr_minus1(a) memset(a,-1,sizeof(a))
#define clr_INT(a) memset(a,INT,sizeof(a))
#define clr_true(a) memset(a,true,sizeof(a))
#define clr_false(a) memset(a,false,sizeof(a))
#define clr_queue(q) while(!q.empty()) q.pop()
#define clr_stack(s) while(!s.empty()) s.pop()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define dep(i, a, b) for (int i = a; i > b; i--)
#define repin(i, a, b) for (int i = a; i <= b; i++)
#define depin(i, a, b) for (int i = a; i >= b; i--)
#define pi acos(-1.0)
#define eps 1e-6
#define MOD 1000000007
#define MAXN
#define N 100100
#define M
int n;
int a[N],b[N],c[N<<1],numc,ans1;
ll suffixa[N],ans2,anst;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin>>n;
numc=0;
repin(i,1,n){
scanf("%d %d",a+i,b+i);
c[++numc]=a[i];
c[++numc]=b[i];
}
sort(a+1,a+1+n);
suffixa[n+1]=0;
depin(i,n,1){
suffixa[i]=suffixa[i+1]+a[i];
}
sort(b+1,b+1+n);
int k1=1,k2=1,k3=1;
ans1=INT;
ans2=0;
repin(i,1,numc){
k1=(int)(upper_bound(a+1,a+1+n,c[i])-a);
k1=n-(k1-1);
k2=(int)(lower_bound(b+1,b+1+n,c[i])-b);
k2-=1;
k3=n-(k1+k2);
k1=n-k1+1;
anst=suffixa[k1]+(ll)k3*c[i];
if(anst>ans2){
ans2=anst;
ans1=c[i];
}
else if(anst==ans2 && c[i]<ans1){
ans1=c[i];
}
}
cout<<ans1<<" "<<ans2<<endl;
}

最后

以上就是洁净唇膏最近收集整理的关于Codeforces gym 2011-2012, Samara Interacademic Programming的全部内容，更多相关Codeforces内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(75)

相关文章

selenium element.findElement() 会在网页全局找？
selenium element.findElement() 会在网页全局找？
GetRect：通过提供点和宽度返回对应矩形RECT
GetRect：通过提供点和宽度返回对应矩形RECT
关于GetWindowRect()、GetClientRect()和SetWindowRgn()的问题
关于GetWindowRect()、GetClientRect()和SetWindowRgn()的问题
jquery tr 遍历单元格_JS与jQuery遍历Table所有单元格内容的方法
jquery tr 遍历单元格_JS与jQuery遍历Table所有单元格内容的方法
Codeforces gym 2011-2012, Samara Interacademic Programming
Codeforces gym 2011-2012, Samara Interacademic Programming
gym 101667 A -Broadcast Stations【树形dp】
gym 101667 A -Broadcast Stations【树形dp】
PaddlePaddle版Flappy-Bird—使用DQN算法实现游戏智能
PaddlePaddle版Flappy-Bird—使用DQN算法实现游戏智能
Codeforces Gym100935
Codeforces Gym100935

评论列表共有 0 条评论

立即
投稿
返回
顶部