栗子栗子

CodeForces 742 解题报告

写在最前

可能是因为是十点半场,所以报名人数激增,本来是个好现象,但是却也因此变成了hack专场

不知道为什么大家都没有估算数据量的习惯,或者像我一样无脑longlong也可以啊

听说有用一组极限数据hack掉20份代码的。。。不做评价

还是希望能细心吧

思路

Problem A

有两种思路

第一种是找循环节,当然这就牵涉到0次的情况要特判

第二种是我的做法,无脑快速幂即可,适用于任何正常情况嘿嘿嘿

Problem B

开一个桶来存每个值的数有几个

考虑异或的这样一个性质x^y=z<===>x^z=y

因此我们可以遍历一边整个数组,加上对应的值的个数就好,记得最后除以2

注意输入的异或值为0的情况,以及需要longlong存答案

Problem C

这题的题目是真的难读= =

大致要注意以下几个点

  1. 注意是对于任意的人,最后的t都要满足

  2. 注意是存在一对x和y,它们只是可以相等,并不代表一定要循环到自己

下面给出做法:

首先已知这是个有向图,而且每个点仅有一条出边

由此我们得到一个重要结论:凡是不少于两点的SCC必定是一整个有向环!!!

对整个图跑一遍Tarjan求SCC,再对所有的单点SCC判断一下是否有自环

对于某一单点SCC,若其不构成自环,则不满足条件,输出-1

在所有的SCC均满足条件的情况下

对偶数点的SCC点数除以2!!!

然后对所有的SCC点数求最小公倍数即可

P.S.目前尚不清楚是否会爆int,不过无脑开longlong总是没错的嘿嘿嘿

Problem D

昨天老眼昏花脑子短路也是气哭QAQ

这题很简单的啦,所有的互相有朋友关系的分到一组,然后整组合起来

按组进行枚举,来一个01背包的变种就好啦

Problem E

又学到了一个新套路,有的时候2-SAT不好做可以构造二分图解决!!!

看了题解才会,自己万万想不出来QAQ

题解这么说的:

$2n$个点,每对情侣连边,然后把$2k$和$2k+1$连边,则整个图是一个二分图

下面我来说明一下

首先我们已知每个点的度数均为2,且这是无向图

对于任意一个环,由于环中每个点度数不小于2,所以每个点的相邻点一定在环中

即对于每个人,其情侣都在环中,那么这一定是个偶环

没有奇环的图就必定为二分图

对每个点黑白染色即可,最后一定有解

好巧妙呀

代码

A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
LL mi(LL x,LL n)
{
LL ans=1;
while(n>0)
{
if(n&1)ans=(ans*x)%10;
x=(x*x)%10;
n>>=1;
}
return ans;
}

int main()
{
LL t;
scanf("%lld",&t);
printf("%lld",mi(8,t));
return 0;
}

B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
LL tot[200005];
LL a[100005];
LL n,i,m;
LL ans;

int main()
{
scanf("%lld%lld",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
tot[a[i]]++;
}
for(i=1;i<=n;i++)
{
if(m==0)ans+=tot[a[i]]-1;
else ans+=tot[a[i]^m];
}
printf("%lld",ans/2);
return 0;
}

C

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
const int maxn=105;

int pre[maxn],low[maxn],a[maxn],sccno[maxn],tot[maxn];
int edge[100005][2];
int dfs_clock,scc_cnt,maxx;
vector<int> g[maxn];
stack<int> s;

int n,m,p0,p1,i,j,k,l;

void dfs(int u)
{
pre[u]=low[u]=++dfs_clock;
s.push(u);
for(unsigned int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(!pre[v])
{
dfs(v);
low[u]=min(low[u],low[v]);
}else if(!sccno[v])low[u]=min(low[u],pre[v]);
}
if(low[u]==pre[u])
{
scc_cnt++;
for(;;)
{
int x=s.top();s.pop();
sccno[x]=scc_cnt;
if(x==u)break;
}
}
}

void find(int n)
{
dfs_clock=scc_cnt=0;
memset(sccno,0,sizeof(sccno));
memset(pre,0,sizeof(pre));
memset(low,0,sizeof(low));
while(!s.empty())s.pop();
for(i=1;i<=n;i++)
{
if(pre[i])continue;
if(g[i][0]==i)
{
sccno[i]=++scc_cnt;
continue;
}
dfs(i);
}
}

LL gcd(LL x,LL y)
{
if(x==0)return y;
if(y==0)return x;
return gcd(y,x%y);
}
vector<int> sc[maxn];
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&j);
g[i].push_back(j);
}
find(n);
LL cnt[105];
memset(cnt,0,sizeof(cnt));
for(i=1;i<=n;i++)
{
cnt[sccno[i]]++;
sc[sccno[i]].push_back(i);
}
for(i=1;i<=scc_cnt;i++)
{
if(cnt[i]==1 && g[sc[i][0]][0]!=sc[i][0])
{
printf("-1");return 0;
}
}
for(i=1;i<=scc_cnt;i++)
if(cnt[i]%2==0)cnt[i]/=2;
LL ans=1;
for(i=1;i<=scc_cnt;i++)
{
LL tt=gcd(ans,cnt[i]);
ans/=tt;
ans*=cnt[i];
}
printf("%lld",ans);
return 0;
}

D

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
const int maxn=1005;

int i,j,k,l,m,n,w,sum;
struct hos
{
int w,b;
}dat[maxn],tot[maxn];
vector<int> g[maxn];
int fat[maxn],ans[maxn][1005];
int vis[maxn];

int find(int now)
{
if(fat[now]==now)return now;
else return fat[now]=find(fat[now]);
}

int main()
{
scanf("%d%d%d",&n,&m,&w);
for(i=1;i<=n;i++)scanf("%d",&dat[i].w);
for(i=1;i<=n;i++)scanf("%d",&dat[i].b);
for(i=1;i<=n;i++)fat[i]=i;
for(i=1;i<=m;i++)
{
scanf("%d%d",&j,&k);
int x=find(j),y=find(k);
if(x==y)continue;
fat[x]=fat[y];
}
sum=0;
for(i=1;i<=n;i++)
{
k=find(i);
if(vis[k]==0)vis[k]=++sum;
g[vis[k]].push_back(i);
tot[vis[k]].b+=dat[i].b;
tot[vis[k]].w+=dat[i].w;
}
for(i=1;i<=sum;i++)
{
for(j=0;j<=w;j++)ans[i][j]=ans[i-1][j];
for(j=tot[i].w;j<=w;j++)
ans[i][j]=max(ans[i][j],ans[i-1][j-tot[i].w]+tot[i].b);
for(unsigned int t=0;t<g[i].size();t++)
{
k=g[i][t];
for(j=dat[k].w;j<=w;j++)
ans[i][j]=max(ans[i][j],ans[i-1][j-dat[k].w]+dat[k].b);
}
}
int answer=0;
for(i=0;i<=w;i++)answer=max(answer,ans[sum][i]);
printf("%d",answer);
return 0;
}

E

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
const int maxn=100005;
int ans[2*maxn];
vector<int> g[2*maxn];
int dat[maxn][2];
int n,i;

void dfs(int now,int num)
{
ans[now]=num;
for(unsigned int t=0;t<g[now].size();t++)
if(ans[g[now][t]]==0)
dfs(g[now][t],3-num);
}

int main()
{
scanf("%d",&n);
for(i=1;i<=n-1;i++)
{
g[2*i].push_back(2*i+1);
g[2*i+1].push_back(2*i);
}
g[1].push_back(2*n);
g[2*n].push_back(1);
for(i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
dat[i][0]=x;
dat[i][1]=y;
}
for(i=1;i<=2*n;i++)
if(ans[i]==0)dfs(i,1);
for(i=1;i<=n;i++)
{
printf("%d %d\n",ans[dat[i][0]],ans[dat[i][1]]);
}
return 0;
}