2017-2018 ACM-ICPC East Central North America Regional Contest (ECNA 2017)

C - DRM Messages

模拟题

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
#include<bits/stdc++.h>
using namespace std;
int main()
{
string a,b,c;
cin>>a;
b=a.substr(0,a.length()/2);c=a.substr(a.length()/2);
int cntb=0,cntc=0;
for(auto x:b){
cntb+=x-'A';
}
for(auto x:c){
cntc+=x-'A';
}
for(auto &x:b){
x=(x-'A'+cntb)%26+'A';
}
for(auto &x:c){
x=(x-'A'+cntc)%26+'A';
}
for(int i=0;i<b.length();i++){
cout<<(char)((b[i]-'A'+c[i]-'A')%26+'A');
}

return 0;
}
/*
EWPGAJRB
*/

D - Game of Throwns

处理一下输入,用栈保存一下即可。

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
#include<bits/stdc++.h>
using namespace std;
int can(string s)
{
int res=0;bool isfu=false;
for(auto a:s){
if(a=='-')isfu=true;
else res=res*10+(a-'0');
}
if(isfu)res=-res;
return res;
}
int main()
{
int i,j,k,n;string str,s;
cin>>n>>k;
getline(cin,str);
getline(cin,str);
stringstream command(str);
vector<int>cc;
while(command>>s){
if(s=="undo"){
command>>s;
int qx=can(s);
while(!cc.empty()&&qx){
qx--;cc.pop_back();
}
}
else{
cc.push_back(can(s));
}
}
int sum=0;
for(auto a:cc)sum+=a;
sum+=(int)1e6*n;
cout<<sum%n<<endl;

return 0;
}
/*
5 4
8 -2 3 undo 2
5 10
7 -3 undo 1 4 3 -9 5 undo 2 undo 1 6
*/

H-Sheba’s Amoebas

题意:有一堆黑白染色的格子,每个黑格的8个邻居中必有2个是黑格,同时每个黑格必然是某个黑格形成的圈里的一部分,求黑格组成了多少个圈。(圈与圈之间不会重复或交叉)

因为题意说的非常明确了,所以要考虑的情况其实非常少,直接dfs即可

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
#include<bits/stdc++.h>
using namespace std;
int move1[8][2]={-1,0,1,0,0,-1,0,1,-1,-1,1,-1,-1,1,1,1};
char mp[105][105];
void color(int x,int y)
{
if(mp[x][y]!='#')return;
mp[x][y]=' ';
for(int i=0;i<8;i++){
color(x+move1[i][0],y+move1[i][1]);
}
}
int main()
{
int m,n,i,j,k;
scanf("%d%d",&m,&n);
for(i=1;i<=m;i++)scanf("%s",mp[i]+1);//printf("%s\n",mp[i]+1);;

int cnt=0;
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
if(mp[i][j]=='#'){
color(i,j);cnt++;
}
}
}
cout<<cnt<<endl;

return 0;
}

F-Keeping On Track

题意:有$n+1$个节点,构成了一棵树,现在要摧毁其中一个节点,使得摧毁这个节点后两两之间不存在路径的点对的数目最大,但是在摧毁前允许你在原本没有边相连的两个点之间添加一条边,输出在没有加边之前摧毁节点后两两之间不存在路径的点对数目以及加边后这样的点对数目(加边前后摧毁的都是同一个顶点)。

做法:第一问的关键是处理出摧毁每个点后会存在的两两之间不存在路径的点对的数目。假设对于顶点$i$,它有一个直接相连的顶点$j$,那么如果以$i$为顶点,摧毁$i$之后造成的两两之间没有路径的点对数目就是$\Sigma( size[j] \times (n-1-size[j]))$

其中$size[j]$是以$j$为顶点的子树的大小。而这些计算,都可以通过一次dfs来$O(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
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
vector<int>G[N];
int res1=0,res2=0,n;
int size[N];
void dfs(int x,int fa)
{
size[x]++;int ans=0,total=n;//此处total其实相当于是n-1
vector<int>subtree;//记录所有x的子树的大小
for(auto a:G[x]){
if(a==fa)continue;
dfs(a,x);
size[x]+=size[a];//统计以x为根的子树
total-=size[a];//避免重复计算
ans+=total*size[a];
subtree.push_back(size[a]);
}
if(ans>res1){//如果第一个答案更新了,第二个答案才有更新的必要
res1=ans;subtree.push_back(n+1-size[x]);//特别注意此处的n+1,因为整个树的大小是n+1,那么
//除去以x为顶点的子树,剩下那个树的顶点数当然是n+1-size[x]
res2=0;sort(subtree.begin(),subtree.end());
int temp=subtree.back();subtree.pop_back();subtree.back()+=temp;total=n;
for(auto a:subtree){
total-=a;//同样避免重复计算
res2+=total*a;
}
}
}
int main()
{
int i,j,k,a,b;
cin>>n;
for(i=1;i<=n;i++){
scanf("%d%d",&a,&b);
G[a].push_back(b);G[b].push_back(a);
}
dfs(0,-1);//任意从哪个店开始dfs都是可以的
cout<<res1<<' '<<res2<<endl;

return 0;
}

G-A Question of Ingestion

有个人去吃饭,他有一个初始的胃口容量,如果连续吃,那么每一天的胃口容量都是前一天的$\frac{2}{3}$,但是如果他休息一天,那么他后一天的胃口就是他之前那一天的胃口(休息的前一天的胃口)。如果他休息2天,那么胃口容量就恢复初始值。同时,每天的食物量也有一个限制的数字,求这个人最多能吃多少东西

做法:dp,$f[i][j]$表示在第$i$天时,这个人已经连续吃了$j$天了,设当日食物限量为$v[i]$,连续吃了$j$天之后的胃口容量为$limit[j]$,那么对于所有的$i$,必然有$f[i][0]=min(v[i],limit[0])$,同时转移方程为:$f[i+1][j+1]=f[i][j]+min(v[i+1],limit[j+1])$,休息1天与2天的同理。

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
#include<bits/stdc++.h>
using namespace std;
int limit[105],f[105][105],v[105];
int main()
{
int n,m,i,j,k;
cin>>n>>m;
for(i=1;i<=n;i++)cin>>v[i];
limit[0]=m;
for(i=1;i<105;i++)limit[i]=limit[i-1]*2/3;
for(i=1;i<=n;i++)f[i][0]=min(m,v[i]);
for(i=1;i<=n;i++){
for(j=0;j<=i;j++){
f[i+1][j+1]=max(f[i+1][j+1],f[i][j]+min(v[i+1],limit[j+1]));//不休息
f[i+2][j]=max(f[i+2][j],f[i][j]+min(v[i+2],limit[j]));//休息1天
f[i+3][0]=max(f[i+3][0],f[i][j]+min(v[i+3],m));//休息2天
}
}
int ans=0;
for(i=1;i<=n;i++){
for(j=0;j<=n;j++){
ans=max(ans,f[i][j]);
}
}
cout<<ans<<endl;

return 0;
}

J-Workout for a Dumbbell

一个看起来很复杂很麻烦事实上考虑清楚之后也不是特别复杂的题目

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
#include <bits/stdc++.h>
using namespace std;
struct machine{
int work,rest,lasttime; //lasttime last start
int jimwork,jimrest;
} mac[15];

int ac(machine &mac,int lasttime){ //ret:end time
int ret;
if (lasttime<mac.lasttime){ // zhi jie kai shi (ta hai mei kai shi)
ret=lasttime+mac.jimwork+mac.jimrest;
mac.lasttime=max(mac.lasttime,lasttime+mac.jimwork);
}
else {
mac.lasttime=(lasttime-mac.lasttime)/(mac.work+mac.rest)*(mac.work+mac.rest)+mac.lasttime;
int mod=(lasttime-mac.lasttime)%(mac.work+mac.rest);
if (mod<mac.work){ // deng dai jie shu
ret=mac.lasttime+mac.work+mac.jimwork+mac.jimrest;
mac.lasttime=max(mac.lasttime+mac.work+mac.jimwork,mac.lasttime+mac.rest+mac.work);
}
else { // zhi jie kai shi
ret=lasttime+mac.jimwork+mac.jimrest;
mac.lasttime=max(mac.lasttime+mac.work+mac.rest,lasttime+mac.jimwork);
}
}
return ret;
}

int main(){
for (int i=1;i<=10;i++){
cin>>mac[i].jimwork>>mac[i].jimrest;
}
for (int i=1;i<=10;i++){
cin>>mac[i].work>>mac[i].rest>>mac[i].lasttime;
}
int lasttime=0;
for (int i=1;i<=3;i++){
for (int j=1;j<=10;j++){
lasttime=ac(mac[j],lasttime);
//cout<<i<<' '<<j<<' '<<lasttime<<' '<<mac[j].lasttime<<endl;
}
}
cout<<lasttime-mac[10].jimrest;

return 0;
}