Codeforces Round 439(Div.2)题解(869A~869E)

2018-02-27jzqjzq?

传送门:CF Round439
在半年前现场打了这场比赛……
打了ABCE之后。。。
你能想象写出4题然后除了C纷纷fst的感觉么。。。
所以还是我太菜了QAQ

在csdn写了blog之后一直没去填D的坑……
然后又出事了!!!
zyy把D题出进了他的模拟赛里……
然后暴力滚粗QAQ
于是就把D的坑也填了

A:

方法1:
我们用$s[i]$表示$i$这个数在2n个数中是否出现过
然后$O(n^2)$枚举每种情况即可
要注意s数组一定要开到$2*max(x[i],y[i])$左右,否则WA到你怀疑人生。。。

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
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
using namespace std;
inline int read(){
int k=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
return k*f;
}
int a[10010],b[10010],s[4000010];
int main()
{
int n=read();
for(int i=1;i<=n;i++)a[i]=read(),s[a[i]]=1;
for(int i=1;i<=n;i++)b[i]=read(),s[b[i]]=1;
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)if(s[a[i]^b[j]]==1)ans++;
if(ans%2==1)puts("Koyomi");
else puts("Karen");
}

方法2:
不要想太多,直接输出Karen你就过了2333333
具体证明(我不太会)可以看一下官方题解。。。
代码的话PHP只有5B,不要虚

B:

同样是暴力
我们发现只要最后一位变成了0,那么接下来就都是0了
所以直接从l+1到r进行枚举,如果末位变0就可以直接跳出了
注意long long

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 <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
#define int long long
using namespace std;
inline int read(){
int k=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
return k*f;
}
signed main()
{
int n=read(),m=read();
int k=1;
for(int i=n+1;i<=m;i++){
k=k*(i%10)%10;if(!k)break;
}
printf("%lld",k);
}

C:

考虑DP,我们首先考虑两两之间连边的情况。
$f[i][j]$表示一种颜色的点连到i,另一种颜色的点连到j的方案数
状态转移考虑选与不选:$f[i][j]=f[i-1][j]+f[i-1][j-1]*j$
然后考虑三种颜色整合的状况,只要把ab,ac,bc的方案数乘起来就是了

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
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
#define int long long
using namespace std;
const int MOD=998244353;
inline int read(){
int k=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
return k*f;
}
int a,b,c,f[5010][5010];
signed main()
{
a=read();b=read();c=read();int p=max(a,max(b,c));
for(int i=1;i<=p;i++)f[i][1]=f[1][i]=i+1;
for(int i=2;i<=p;i++)
for(int j=2;j<=p;j++)f[i][j]=(f[i-1][j]+f[i-1][j-1]*j%MOD)%MOD;
int ans=f[a][b]*f[b][c]%MOD*f[a][c]%MOD;
printf("%lld",ans);
return 0;
}

D:

当时不会做……
现在想想,真是暴力……
考虑一棵子树中没有环的情况,可以发现子树内的点走到根的方案就是子树大小
对于这棵子树内的路径我们可以直接计算后计入答案,之后就不再统计了
然后考虑环。可以发现我们可以把一些没有环的子树缩成一个点,权值设为子树大小
重构整个图然后……直接暴力dfs统计路径即可(雾
因为完全二叉树的性质,树高最多log,可以计算出缩点后点数最多300
所以复杂度是对的(雾

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
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
#define int long long
#define pa pair<int,int>
#define fi first
#define se second
using namespace std;
const int MOD=1e9+7;
inline int read(){
int k=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
return k*f;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writeln(int x){
write(x);puts("");
}
int n,m,nedge=0,p[200010],nex[200010],head[200010],ans=0,a[100010];
bool vis[10010];
map<int,int>mp;
inline void addedge(int a,int b){
p[++nedge]=b;nex[nedge]=head[a];head[a]=nedge;
}
inline void Dfs(int x){
int p=mp[x];
if(mp[x*2]){
a[p]=(a[p]-a[mp[x*2]]+MOD)%MOD;Dfs(x*2);
}
if(mp[x*2+1]){
a[p]=(a[p]-a[mp[x*2+1]]+MOD)%MOD;Dfs(x*2+1);
}
}
inline void dfs(int x){
ans=(ans+a[x])%MOD;vis[x]=1;
for(int k=head[x];k;k=nex[k])if(!vis[p[k]])dfs(p[k]);
vis[x]=0;
}
inline int cal(int x){
int l=x,r=x,ans=0;
while(r<=n){
ans+=r-l+1;
l*=2;r=r*2+1;
}
if(l<=n)ans+=n-l+1;
return ans;
}
signed main()
{
n=read();m=read();
int cnt=0;mp[1]=++cnt;
for(int i=1;i<=m;i++){
int x=read(),y=read();
for(int X=x;X;X/=2)if(!mp[X])mp[X]=++cnt;
for(int Y=y;Y;Y/=2)if(!mp[Y])mp[Y]=++cnt;
addedge(mp[x],mp[y]);addedge(mp[y],mp[x]);
}
map<int,int>::iterator it;
for(it=mp.begin();it!=mp.end();it++){
pa now=*it;
if(now.fi!=1)addedge(now.se,mp[now.fi/2]),addedge(mp[now.fi/2],now.se);
a[now.se]=cal(now.fi)%MOD;
}
Dfs(1);
int Ans=0;
for(int i=1;i<=cnt;i++){
ans=0;dfs(i);
Ans=(Ans+ans*a[i]%MOD)%MOD;
}
writeln(Ans);
return 0;
}

E:

二维矩阵然后求区间不难想到数据结构
首先,如果两个点能够互相走到的话,必定属于同一区间内
所以我们只需判断两个点是否在同一区间即可
如何判断是否在同一区间呢?我们给每个矩形都赋一个专属值,然后整个矩形都加上这个值,减的时候减掉这个值就可以了
但是一个个的专属很容易出事,因为如果两个点即使属于不同区间,如国把这两个点上的矩形的值都加起来,还是有可能出现相等的情况的
所以嘛……随机不就好了。不过rand一定要取好,否则还是有概率出现巧合的
区间加用二维树状数组即可

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
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
#define mp make_pair
#define pa pair<int,int>
#define int long long
using namespace std;
inline int read(){
int k=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
return k*f;
}
map<pa,int>p;
int n,m,q,f[3010][3010];
inline void add(int x,int y,int p){
for(int i=x;i<=n;i+=i&-i)
for(int j=y;j<=m;j+=j&-j)f[i][j]+=p;
}
inline int ssum(int x,int y){
int ans=0;
for(int i=x;i;i-=i&-i)
for(int j=y;j;j-=j&-j){
ans+=f[i][j];
}
return ans;
}
signed main()
{
srand(time(0));
n=read();m=read();q=read();
for(int i=1;i<=q;i++){
int op=read(),x1=read(),y1=read(),x2=read(),y2=read();
if(op==1){
x2++;y2++;int rp=rand()+rand()+rand()*rand();pa rpp=mp(x1*n+y1,x2*n+y2);
p[rpp]=rp;
add(x1,y1,rp);add(x1,y2,-rp);add(x2,y1,-rp);add(x2,y2,rp);
}if(op==2){
x2++;y2++;pa rpp=mp(x1*n+y1,x2*n+y2);
int k=p[rpp];
add(x1,y1,-k);add(x1,y2,k);add(x2,y1,k);add(x2,y2,-k);
}if(op==3){
int x=ssum(x1,y1),y=ssum(x2,y2);
if(x==y)puts("Yes");
else puts("No");
}
}
return 0;
}

总结:

不要fst!!!
不要fst!!!
不要fst!!!
还有……Div2的ABCD会有高深的算法?
不存在的!所以,能暴力则暴力……