受大神队友的感召,也开始刷CF的水题了。

A

拿python写的…

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
#f=file('test')

n=int(raw_input())
t={}
mp=[]
cnt=0

def dfs(n,k):
global cnt
cnt=max(cnt,k)
for i in mp[n]:
dfs(i,k+1)

for i in range(0,n):
s=raw_input()
for ch in s.split():
if ch.lower()=='reposted': continue
if ch.lower() in t:
pass
else:
mp.append([])
t[ch.lower()]=cnt
cnt+=1
mp[t[s.split()[0].lower()]].append(t[s.split()[2].lower()])

ans=0
for i in range(0,len(mp)):
if mp[i]!=[]:
global cnt
cnt=0
dfs(i,1)
ans=max(cnt,ans)

print ans
#f.close()

B

模拟,维护最高高度和长度就可以了。

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
#include<bits/stdc++.h>
using namespace std;

const int maxn=1000+10;
vector<int> arr[maxn];
int p[maxn],que[2000000+10];

void init()
{
for(int i=0;i<maxn;++i) arr[i].clear();
memset(p,0,sizeof(p));
}

int main()
{
int n,H,W;
H=W=0;
scanf("%d",&n);
for(int i=0;i<n;++i){
int w,h;
scanf("%d %d",&w,&h);
H=max(H,h);
W+=w;
arr[h].push_back(w);
que[i]=h;
}
int h1=H;
if(arr[H].size()==1)
while(--h1) if(arr[h1].size()) break;
for(int i=0;i<n;++i){
int h=que[i],res;
res=(W-arr[h][p[h]++])*(h==H?h1:H);
if(i) printf(" ");
printf("%d",res);
}
puts("");
return 0;
}

C

贪心,原来一直过不了,后来队友纠正了一个细节就好了。
关键是第一次心情不好出现的位置,说明在这之前必有一道菜已经为0(注意若以后有人选某道菜,这道菜在此时必不为0)
记录不知道选那一道菜的人的个数dec,确定的就直接所选的这道菜-1。
然后此时所有小于dec的菜个数都有可能为0,dec再减去一个最小的菜的个数。
最后对于所有菜-dec若<0则说明有可能已经选完。

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
#include<bits/stdc++.h>
using namespace std;

const int maxn=100000+10;
int save[maxn],rem[maxn];

int main()
{
//freopen("./test.txt","r",stdin);
int T,m,k;
scanf("%d",&T);
while(T--){
scanf("%d %d",&m,&k);
for(int i=1;i<=k;++i){
scanf("%d",save+i);
}
memset(rem,0,sizeof(rem));
int person[maxn],mood[maxn];
int dec=0,first=0;
for(int i=1;i<m;++i){
scanf("%d %d",&person[i],&mood[i]);
if(!first && mood[i]) first=i;
if(first && person[i]) rem[person[i]]=1;
}
for(int j=1;j<m;++j){
if(j==first){
int res=dec;
for(int i=1;i<=k;++i) if(!rem[i] && save[i]<=dec){
res=min(save[i],res);
save[i]=0;
}
dec-=res;
if(!person[j]) ++dec;
else --save[person[j]];
continue;
}
if(person[j])
--save[person[j]];
else
++dec;
}

for(int i=1;i<=k;++i)
if(save[i]-dec>0) putchar('N');
else putchar('Y');
putchar('\n');
}

return 0;
}