cf round 425

自用笔记算法

cf round 425

A

题目要求

n个火柴每次依次拿走k个 无法拿走的人输

参考AC代码

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>
#define maxn 100000
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	LL n,k;
	cin>>n>>k;
	LL ans=n/k;
	if(ans&1) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}

思路

模拟

B

题目要求

先给出一些字母 为好的字母 其余的字母均为差的字母
给出由小写字母和？*组成的子串 ？代表可以由任意的好字母替换 *最多只有一个 可以用差的字母 查的字母构成的子串
或者空的字符串组成
接下来有q个询问 对于每个询问给出目标字符串 问是否可以由母串变化得到

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100000
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int hashh[30];
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	string s1,s;
	cin>>s1;
	mm(hashh,0);
	for(int i=0;i<s1.length();i++) hashh[s1[i]-'0']++;
	cin>>s;
	int q; cin>>q;
	while(q--){
		string t;
		cin>>t;
		int flag=1; 
		int j=0;
		for(int i=0;i<s.length();i++){
			if(s[i]=='*'){
				if(s.length()>t.length()) continue;
				else{
					int len=t.length()-s.length();
					for(;j<=i+len;j++){
						if(hashh[t[j]-'0']>0){
							flag=0;
							break;
						}
					}
				}
			}
			else if(s[i]=='?'){
				if(hashh[t[j]-'0']==0){
					flag=0;
					break;
				}
				j++;
			}
			else{
				if(s[i]!=t[j]){
					flag=0;
					break;
				}
				j++;
			}
		}
		if(j<t.length()){
			cout<<"NO"<<endl;
			continue;
		}
		if(flag) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}

思路

模拟
注意*的判断 若s的长度大于t的长度 那么*为空串
*可以替换的长度最多为s的长度-t的长度 这是为了确保后面的字符还能一一对应
最后特判如果t字符串未扫描到最后 输出NO

D

题目要求

给出一棵树
接下来给出一些三元组 可以任意组成fst三个点
A要从s走到f 路径为最短路
B要从t走到f 路径为最短路
问他们相交的点最多为多少

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int vis[maxn],deep[maxn],f[maxn],anc[maxn][25];
int dis[maxn];
vector<int>e[maxn];
void dfs(int x,int fa){
    anc[x][0]=f[x];
    for(int i=1;i<=20;i++) anc[x][i]=anc[anc[x][i-1]][i-1];
    for(int i=0;i<e[x].size();i++){
        int next=e[x][i];
        if(next!=fa){
            f[next]=x;
            deep[next]=deep[x]+1;
            dfs(next,x);
        }
    }
}
int lca(int x,int y){
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=20;i>=0;i--) if(deep[anc[x][i]]>=deep[y]) x=anc[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--) if(anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
    return f[x];
}
void dfs2(int id){
    for(int i=0;i<e[id].size();i++){
        int next=e[id][i];
        if(vis[next]) continue;
        dis[next]=dis[id]+1;
        vis[next]=1;
        dfs2(next);
    }
}
int solve(int f,int s,int t){
	int l1=lca(f,s);
	int len1=dis[s]+dis[f]-2*dis[l1];
	int l2=lca(f,t);
	int len2=dis[f]+dis[t]-2*dis[l2];
	int l3=lca(s,t);
	int len3=dis[s]+dis[t]-2*dis[l3];
	return (len1+len2-len3)/2+1;
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n,q;
	cin>>n>>q;
	for(int i=2;i<=n;i++){
		int x;
		cin>>x;
		e[x].pb(i);
		e[i].pb(x);
	}
	mm(vis,0),mm(f,0),mm(anc,0),mm(deep,0),mm(dis,0);
	deep[1]=1;
	dfs(1,0);
	vis[1]=1;
	dfs2(1);
	while(q--){
		int a,b,c;
		cin>>a>>b>>c;
		int ans=0;
		ans=max(ans,solve(a,b,c));
		ans=max(ans,solve(b,a,c));
		ans=max(ans,solve(c,b,a));
		cout<<ans<<endl;
	}
	return 0;
}

思路

求两条路径的共同长度 使用lca
　F
S　　T
如上图 s到f和t到f的共同长度=(len(s,f)+len(t,f)-len(s,t))/2
而树上两点距离使用lca len=dis[a]+dis[b]-2*dis[lca(a,b)]
dis表示到任意点的距离 本题是到点1的距离
最后需要注意公共长度需要+1 因为本题求得是公共点数 = 路径长度+1

本文标题:cf round 425

文章作者:Hippopmonkey

发布时间:2017-07-25, 23:47:45

最后更新:2017-07-26, 00:06:44

原始链接:http://xuboming8.github.io/2017/07/25/cf-round-425/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. cf round 425
    1. 1.1. A
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. B
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. D
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
|